nips nips2000 nips2000-62 nips2000-62-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Jonathan S. Yedidia, William T. Freeman, Yair Weiss
Abstract: Belief propagation (BP) was only supposed to work for tree-like networks but works surprisingly well in many applications involving networks with loops, including turbo codes. However, there has been little understanding of the algorithm or the nature of the solutions it finds for general graphs. We show that BP can only converge to a stationary point of an approximate free energy, known as the Bethe free energy in statistical physics. This result characterizes BP fixed-points and makes connections with variational approaches to approximate inference. More importantly, our analysis lets us build on the progress made in statistical physics since Bethe's approximation was introduced in 1935. Kikuchi and others have shown how to construct more accurate free energy approximations, of which Bethe's approximation is the simplest. Exploiting the insights from our analysis, we derive generalized belief propagation (GBP) versions ofthese Kikuchi approximations. These new message passing algorithms can be significantly more accurate than ordinary BP, at an adjustable increase in complexity. We illustrate such a new GBP algorithm on a grid Markov network and show that it gives much more accurate marginal probabilities than those found using ordinary BP. 1
[1] W. T. Freeman and E. Pasztor. Learning low-level vision. In 7th Intl. Conf. Computer Vision, pages 1182- 1189, 1999.
[2] B. J. Frey. Graphical Models for Machine Learning and Digital Communication. MIT Press, 1998.
[3] M. Jordan, Z. Ghahramani, T. Jaakkola, and 1. Saul. An introduction to variational methods for graphical models. In M. Jordan, editor, Learning in Graphical Models. MIT Press, 1998.
[4] Y. Kabashima and D. Saad. Belief propagation vs. TAP for decoding corrupted messages. Euro. Phys. Lett., 44:668, 1998.
[5] R. Kikuchi. Phys. Rev., 81:988, 1951.
[6] R. McEliece, D. MacKay, and J. Cheng. Turbo decoding as an instance of Pearl's 'belief propagation' algorithm. IEEE J. on Sel. Areas in Comm., 16(2):140- 152, 1998.
[7] K. Murphy, Y. Weiss, and M. Jordan. Loopy belief propagation for approximate inference: an empirical study. In Proc. Uncertainty in AI, 1999.
[8] J. Pearl. Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan Kaufmann, 1988.
[9] T. J. Richardson. The geometry of turbo-decoding dynamics. IEEE Trans. Info. Theory, 46(1):9-23, Jan. 2000.
[10] Special issue on Kikuchi methods. Progr. Theor. Phys. Suppl., vol. 115, 1994.