• 
• 
• 
• 
• 
• 

Generalized Belief Propagation Algorithms

Many problems in computer vision, machine learning and inference, diagnosis, statistical physics, error-correcting coding, and combinatorial optimization can be posed in terms of a probabilistic graphical model consisting of a lattice of nodes with links connecting nodes that influence each other. Typically, one asks for the probability that a given node or collection of nodes is in some state, given the states of another set of nodes. We have developed a new class of algorithms that can often solve such problems much more quickly and accurately than previously-known algorithms.

Background & Objective:  Our generalized belief propagation (GBP) algorithms generalize and improve previously developed "belief propagation" (BP) algorithms, and give more accurate results with fewer convergence problems. Applied to the specific application of decoding error-correcting codes, we have shown that GBP decoding outperforms standard BP decoding for codes whose graphical representation contains short cycles. Since standard BP decoding has proven to be remarkably powerful for such codes as turbocodes and low-density parity check codes, this is a potentially exciting result.

Technical Discussion:  GBP algorithms are theoretically based on the insight that their fixed points are equivalent to the stationary points of an approximate region-based "free energy." We have developed a general theory for constructing good free energy approximations, based on a "region graph" approach. In this approach, the region graph also indicates directly which regions of nodes send information to other regions of nodes in the corresponding GBP algorithm. The standard BP algorithm and the GBP algorithms that we previously developed based on the cluster variational method (giving Kikuchi approximations to the free energy) are special cases of those developed with the more general region graph approach. An important advantage of the region graph approach is that it gives guidance about how to construct GBP algorithms that can be expected to give good results without excessive computational cost.

Publications:
*   Yedidia, J.S.; Freeman, W.T.; Weiss, Y., "Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms", IEEE Transactions on Information Theory, ISSN; 0018-9448, Vol. 51, Issue 7, pp. 2282-2312, July 2005 (IEEE Xplore, TR2004-040)

Yedidia, J.S., "Sparse Factor Graph Representations of Reed-Solomon and Related Codes", DIMACS Workshop on Algebraic Coding, December 2003 (TR2003-135)

Fossorier, M.; Palanki, R.; Yedidia, J.S., "Iterative Decoding of Multi-Step Majority Logic Decodable Codes", International Symposium on Turbo Codes and Related Topics, September 2003 (Intl Symposium on Turbo Codes and Related Topics, TR2003-107)

Yedidia, J.; Chen, J.; Fossorier, M., "Representing Codes for Belief Propagation Decoding", IEEE International Symposium on Information Theory (ISIT), pp.176, June 2003 (IEEE Xplore, TR2003-106)

Yedidia, J.S.; Freeman, W.T.; Weiss, Y., "Understanding Belief Propagation and Its Generalizations", Exploring Artificial Intelligence in the New Millennium, ISBN 1558608117, Chap. 8, pp. 239-236, January 2003 (Science & Technology Books, TR2001-022)

Yedidia, J.S.,; Chen, J.; Fossorier, M., "Generating Code Representations Suitable for Belief Propagation Decoding", Proceedings of the 40th Annual Allerton Conference on Communications, Control and Computing, October 2002 (TR2002-040)

Yedidia, J.S., "An Idiosyncratic Journey Beyond Mean Field Theory", Advanced Mean Field Methods, Theory and Practice, ISBN: 0-262-15045-9, pps 21-36, February 2001 (The MIT Press, TR2000-027)

Yedidia, J.S.; Freeman, W.T.; Weiss, Y., "Generalized Belief Propagation", Advances in Neural Information Processing Systems (NIPS), Vol 13, pps 689-695, December 2000 (NIPS Online , TR2000-026)

Technical Reports:
TR2002-035	Constructing Free Energy Approximations and Generalized Belief Propagation Algorithms

Technology Areas:
Algorithms
Artificial Intelligence
Computer Vision
Digital Communications

Modification Date:  May 28, 2009