TR2001-22

Understanding Belief Propagation and its Generalizations


    •  Yedidia, J.S.; Freeman, W.T.; Weiss, Y., "Understanding Belief Propagation and Its Generalizations" in Exploring Artificial Intelligence in the New Millennium, Lakemeyer, G. and Nebel, B., Eds., ISBN: 1-55860-811-7, chapter 8, pp. 239-236, Morgan Kaufmann Publishers, January 2003.
      BibTeX Download PDF
      • @incollection{Yedidia2003jan1,
      • author = {Yedidia, J.S. and Freeman, W.T. and Weiss, Y.},
      • title = {Understanding Belief Propagation and Its Generalizations},
      • booktitle = {Exploring Artificial Intelligence in the New Millennium},
      • year = 2003,
      • editor = {Lakemeyer, G. and Nebel, B.},
      • chapter = 8,
      • pages = {239--236},
      • month = jan,
      • publisher = {Morgan Kaufmann Publishers},
      • isbn = {1-55860-811-7},
      • url = {http://www.merl.com/publications/TR2001-22}
      • }

TR Image
The belief equation b1245 = k[φ1φ2φ4φ5ψ12ψ14ψ25ψ45][m36→25m78→45m6→5m8→5], for the region [1245], illustrated both on the region graph (left) and on the original pairwise MRF (right).

"Inference" problems arise in statistical physics, computer vision, error-correcting coding theory, and AI. We explain the principles behind the belief propagation (BP) algorithm, which is an efficient way to solve inference problems based on passing local messages. We develop a unified approach with examples, notation, and graphical models borrowed from the relevant disciplines.We explain the close connection between the BP algorithm and the Bethe approximation of statistical physics. In particular, we show that BP can only converge to a fixed point that is also a stationary point of the Bethe approximation to the free energy. This result helps explain the successes of the BP algorithm and enables connections to be made with variational approaches to approximate inference.