Martin J. Wainwright, Tommi Jaakkola, Alan Willsky
We describe a method for computing provably exact maximum a poste- riori (MAP) estimates for a subclass of problems on graphs with cycles. The basic idea is to represent the original problem on the graph with cy- cles as a convex combination of tree-structured problems. A convexity argument then guarantees that the optimal value of the original problem (i.e., the log probability of the MAP assignment) is upper bounded by the combined optimal values of the tree problems. We prove that this upper bound is met with equality if and only if the tree problems share an opti- mal conﬁguration in common. An important implication is that any such shared conﬁguration must also be the MAP conﬁguration for the original problem. Next we develop a tree-reweighted max-product algorithm for attempting to ﬁnd convex combinations of tree-structured problems that share a common optimum. We give necessary and sufﬁcient conditions for a ﬁxed point to yield the exact MAP estimate. An attractive feature of our analysis is that it generalizes naturally to convex combinations of hypertree-structured distributions.