Stochastic Systems Group  

Dr. Jonathan Yedidia
MERL
Important inference problems in statistical physics, computer vision, errorcorrecting coding theory, and artificial intelligence can all be reformulated as the computation of marginal probabilities on factor graphs. The belief propagation (BP) or "sumproduct" 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 previously showed that BP fixed points correspond to the stationary points of the Bethe approximation to the free energy for pairwise Markov random fields, and that new generalized belief propagation (GBP) algorithms could be derived from better "Kikuchi" approximations to the free energy.
In this talk I explain in more detail a variety of methods to obtain "valid" Kikuchi approximations and their corresponding GBP algorithms for general factor graphs. In particular, I describe the relationship between four different methods: the "Bethe method," the "junction graph method," the "cluster variational method," and the "region graph method."
The region graph method is the most general of these methods, and also provides a natural graphical setting for GBP algorithms. I will explain how to obtain a GBP algorithm corresponding to any region graph approximation to the free energy, and sketch the proofs of two important theorems. The first theorem tells us that the GBP fixed points correspond to the stationary points of the region graph approximation to the free energy, and the second theorem tells us that the region graph approximation is exact when the region graph has no cycles.
Problems with this site should be emailed to jonesb@mit.edu