nips nips2001 nips2001-192 nips2001-192-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Martin J. Wainwright, Tommi Jaakkola, Alan S. Willsky
Abstract: We develop a tree-based reparameterization framework that provides a new conceptual view of a large class of iterative algorithms for computing approximate marginals in graphs with cycles. It includes belief propagation (BP), which can be reformulated as a very local form of reparameterization. More generally, we consider algorithms that perform exact computations over spanning trees of the full graph. On the practical side, we find that such tree reparameterization (TRP) algorithms have convergence properties superior to BP. The reparameterization perspective also provides a number of theoretical insights into approximate inference, including a new characterization of fixed points; and an invariance intrinsic to TRP /BP. These two properties enable us to analyze and bound the error between the TRP /BP approximations and the actual marginals. While our results arise naturally from the TRP perspective, most of them apply in an algorithm-independent manner to any local minimum of the Bethe free energy. Our results also have natural extensions to more structured approximations [e.g. , 1, 2]. 1
[1] J. Yedidia, W. T. Freeman, and Y. Weiss. Generalized belief propagation. In NIPS 13, pages 689- 695. MIT Press, 2001. Bounds on single node marginals - - - - -0 - - - -0- - Bounds on single node marginals - e- - - - M M 0.8 _ 0 - - - - 0 - - - -0- - - - €l - - - - ;o: V
[2] T. P. Minka. A family of algorithms for approximate Bayesian inference. PhD thesis, MIT Media Lab, 2001.
[3] J. Pearl. Probabilistic reasoning in intelligent systems. Morgan Kaufman, San Mateo, 1988.
[4] F. Kschischang and B. Frey. Iterative decoding of compound codes by probability propagation in graphical models. IEEE Sel. Areas Comm., 16(2):219- 230, February 1998.
[5] J. B. Anderson and S. M. Hladnik. Tailbiting map decoders. IEEE Sel. Areas Comm., 16:297- 302, February 1998.
[6] Y. Weiss. Correctness of local probability propagation in graphical models with loops. Neural Computation, 12:1-41, 2000.
[7] Y. Weiss and W. T. Freeman. Correctness of belief propagation in Gaussian graphical models of arbitrary topology. In NIPS 12, pages 673- 679 . MIT Press, 2000 .
[8] P. Rusmevichientong and B. Van Roy. An analysis of turbo decoding with Gaussian densities. In NIPS 12, pages 575- 581. MIT Press, 2000.
[9] T. Richardson. The geometry of turbo-decoding dynamics. IEEE Trans. Info. Theory, 46(1):9- 23, January 2000.
[10] R. Kikuchi. The theory of cooperative phenomena. Physical Review, 81:988- 1003, 1951.
[11] M. Welling and Y. Teh. Belief optimization: A stable alternative to loopy belief propagation. In Uncertainty in Artificial Intelligence, July 2001.
[12] A. Yuille. A double-loop algorithm to minimize the Bethe and Kikuchi free energies. Neural Computation, To appear, 2001.
[13] M. J . Wainwright, T. Jaakkola, and A. S. Willsky. Tree-based reparameterization for approximate estimation on graphs with cycles. LIDS Tech. report P-2510: available at http://ssg.rnit.edu/group/rnjyain/rnjyain.shtrnl, May 2001.
[14] M. Wainwright . Stochastic processes on graphs with cycles: geometric and variational approaches. PhD thesis, MIT, Laboratory for Information and Decision Systems, January 2002. [1 5] S. L. Lauritzen. Graphical models. Oxford University Press, Oxford, 1996.
[16] W. 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.