Bethe free energy, Kikuchi approximations, and belief
propagation algorithms
Jonathan S. Yedidia, William T. Freeman, Yair Weiss
Belief propagation (BP) was only supposed to work for tree-like
networks but works surprisingly well in many applications involving
networks with loops, including turbo codes. However, there has been
little understanding of the algorithm or the nature of the solutions
it finds for general graphs.
We show that BP can only converge to a stationary point of an
approximate free energy, known as the Bethe free energy in statistical
physics. This result characterizes BP fixed-points and makes
connections with variational approaches to approximate inference.
More importantly, our analysis lets us build on the progress made in
statistical physics since Bethe's approximation was introduced in
1935. Kikuchi and others have shown how to construct more accurate
free energy approximations, of which Bethe's approximation is the
simplest. Exploiting the insights from our analysis, we derive
generalized belief propagation (GBP) versions of these Kikuchi
approximations. These new message passing algorithms can be
significantly more accurate than ordinary BP, at an adjustable
increase in complexity. We illustrate such a new GBP algorithm on a
grid Markov network and show that it gives much more accurate marginal
probabilities than those found using ordinary BP.