nips nips2002 nips2002-80 nips2002-80-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Martin J. Wainwright, Tommi S. Jaakkola, Alan S. Willsky
Abstract: We describe a method for computing provably exact maximum a posteriori (MAP) estimates for a subclass of problems on graphs with cycles. The basic idea is to represent the original problem on the graph with cycles 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 optimal configuration in common. An important implication is that any such shared configuration must also be the MAP configuration for the original problem. Next we develop a tree-reweighted max-product algorithm for attempting to find convex combinations of tree-structured problems that share a common optimum. We give necessary and sufficient conditions for a fixed 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.
[1] R. G. Cowell, A. P. Dawid, S. L. Lauritzen, and D. J. Spiegelhalter. Probablistic Networks and Expert Systems. Statistics for Engineering and Information Science. Springer-Verlag, 1999.
[2] M. J. Wainwright, T. S. Jaakkola, and A. S. Willsky. A new class of upper bounds on the log partition function. In Proc. Uncertainty in Artificial Intelligence, volume 18, pages 536–543, August 2002.
[3] W. T. Freeman and Y. Weiss. On the optimality of solutions of the max-product belief propagation algorithm in arbitrary graphs. IEEE Trans. Info. Theory, 47:736–744, 2001.
[4] B. J. Frey and R. Koetter. Exact inference using the attenuated max-product algorithm. In Advanced mean field methods: Theory and Practice. MIT Press, 2000.
[5] M. J. Wainwright, T. S. Jaakkola, and A. S. Willsky. Tree consistency and bounds on the maxproduct algorithm and its generalizations. LIDS Tech. report P-2554, MIT; Available online at http://www.eecs.berkeley.edu/ martinw, July 2002. D
[6] D.P. Bertsekas. Nonlinear programming. Athena Scientific, Belmont, MA, 1995.
[7] J. Feldman, M. J. Wainwright, and D. R. Karger. Linear programming-based decoding and its relation to iterative approaches. In Proc. Allerton Conf. Comm. Control and Computing, October 2002.