optimize <> MPE

[dellaert]

Description

The optimize methods in DiscreteFactorGraph and DiscreteBayesNet do not actually compute the MPE, but optimize first the marginal of the parents, and then the conditional marginals of the children. While often agreeing with the MPE (I had to work a bit to find a counterexample in addition to the Darwiche example) this computation is not the same, and in fact is not a common thing to do (as opposed to max-marginal, which optimizes all individual marginals).

This will probably of interest to @keevindoherty , @varunagrawal , @ProfFan

Steps to reproduce

I created a counter-example in a branch where I am fixing the issue.

TEST(DiscreteFactorGraph, marginalIsNotMPE) {
  // Declare 2 keys
  DiscreteKey A(0, 2), B(1, 2);

  // Create Bayes net such that marginal on A is bigger for 0 than 1, but the
  // MPE does not have A=0.
  DiscreteBayesNet bayesNet;
  bayesNet.add(B | A = "1/1 1/2");
  bayesNet.add(A % "10/9");

  // The expected MPE is A=1, B=1
  DiscreteValues mpe;
  insert(mpe)(0, 1)(1, 1);

  // Which we verify using max-product:
  DiscreteFactorGraph graph(bayesNet);
  auto actualMPE = graph.optimize();
  EXPECT(assert_equal(mpe, actualMPE));
  EXPECT_DOUBLES_EQUAL(0.315789, graph(mpe), 1e-5);  // regression

  // Optimize on BayesNet maximizes marginal, then the conditional marginals:
  auto notOptimal = bayesNet.optimize();
  EXPECT(graph(notOptimal) < graph(mpe));
  EXPECT_DOUBLES_EQUAL(0.263158, graph(notOptimal), 1e-5);  // regression
}

Expected behavior

DiscreteFactorGraph::optimize should compute the MPE.

Additional information

I already fixed what optimize does. To maintain the API and the common use case, I will leave the eliminate methods as they are, producing a BayesNet, but will deprecated BayesNet optimize. There will be new maxProduct methods in DFG.

[keevindoherty]

Wow, really great find. Thanks for keeping us in the loop on this!

[varunagrawal]

I came back to this after fully understanding the difference between sum-product and max-product, and I think the test in the description is not correct. You're running elimination on an already eliminated graph $P(B|A)P(A)$, instead of eliminating $\phi(A, B)\phi(A)$ i.e. not the joint probability, so sum-product doesn't actually know about the influence of A on B.

To construct $\phi(A, B)$, I multiplied the two probabilities (aka the chain rule) and passed that as a factor to a DiscreteFactorGraph (without the factor on A since elimination will generate $P(B|A)\tau(A)$ and $\tau(A)$ corresponds to $P(A)$, and the MPE being spit out by sum-product is (0, 0)(1, 0) which matches what max-product is giving us.

[varunagrawal]

I get the same value for the MPE for both Max-Product and Sum-Product, as well as the same graph "value" aka graph(actualMPE) as the test in the description.

[dellaert]

I came back to this after fully understanding the difference between sum-product and max-product, and I think the test in the description is not correct. You're running elimination on an already eliminated graph P(B|A)P(A), instead of eliminating ϕ(A,B)ϕ(A) i.e. not the joint probability, so sum-product doesn't actually know about the influence of A on B.

To construct ϕ(A,B), I multiplied the two probabilities (aka the chain rule) and passed that as a factor to a DiscreteFactorGraph (without the factor on A since elimination will generate P(B|A)τ(A) and τ(A) corresponds to P(A), and the MPE being spit out by sum-product is (0, 0)(1, 0) which matches what max-product is giving us.

Hmmmm. Not following you there, but let’s chat about it in our next meeting. Pls schedule it?