Understanding Belief Propagation and its Generalizations
| Citation: |
|
| MERL Report: | TR2001-22 : Jonathan S. Yedidia, William T. Freeman, and Yair Weiss |
| Research Area: | Algorithms |
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.
|
| Read the full technical report (PDF: 532.7 kB) |