Journal
IEEE TRANSACTIONS ON INFORMATION THEORY
Volume 51, Issue 7, Pages 2282-2312Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2005.850085
Keywords
belief propagation (BP); Bethe free energy; cluster variation method; generalized belief propagation (GBP); Kikuchi free energy; message passing; sum-product algorithm
Ask authors/readers for more resources
Important inference problems in statistical physics, computer vision, error-correcting coding theory, and artificial intelligence can all be reformulated as. the computation of marginal probabilities on factor graphs. The belief propagation (BP) algorithm is an efficient way to solve these problems that is exact when the factor graph is a tree, but only approximate when the factor graph has cycles. We show that BP fixed points correspond to the stationary points of the Bethe approximation of the free energy for a factor graph. We explain how to obtain region-based free energy approximations that improve the Bethe approximation, and corresponding generalized belief propagation (GBP) algorithms. We emphasize the conditions a free energy approximation must satisfy in order to be a valid or maxent-normal approximation. We describe the relationship between four different methods that can be used to generate valid approximations: the Bethe method, the junction graph method, the cluster variation method, and the region graph method. Finally, we explain how to tell whether a region-based approximation, and its corresponding GBP algorithm, is likely to be accurate, and describe empirical results showing that GBP can significantly outperform BP.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available