TR on loopy belief propagation

[Yair Weiss]

Hi,

The following paper showing that belief propagation gives the exact means
for Gaussian graphical models regardless of the number of loops
is available online via:

http://www.cs.berkeley.edu/~yweiss/gaussTR.ps.gz

Comments are most welcome.

 Yair

--------------------------------------------------------------------------
Title: Correctness of belief propagation in Gaussian graphical models
of arbitrary topology.
Authors: Yair Weiss and William T. Freeman
Reference: UC Berkeley CS Department TR UCB//CSD-99-1046

Abstract: Graphical models, such as Bayesian networks and Markov
Random Fields represent statistical dependencies of variables by a
graph.  Local ``belief propagation'' rules of the sort proposed by
Pearl (1988) are guaranteed to converge to the correct posterior
probabilities in singly connected graphical models.  Recently, a
number of researchers have empirically demonstrated good performance
of ``loopy belief propagation''--using these same rules on graphs with
loops. Perhaps the most dramatic instance is the near Shannon-limit
performance of ``Turbo codes'', whose decoding algorithm is equivalent
to loopy belief propagation.

Except for the case of graphs with a single loop, there has been
little theoretical understanding of the performance of loopy
propagation. Here we analyze belief propagation in networks with
arbitrary topologies when the nodes in the graph describe jointly
Gaussian random variables. We give an analytical formula relating the
true posterior probabilities with those calculated using loopy
propagation. We give sufficient conditions for convergence and show
that when belief propagation converges it gives the correct posterior
means {\em for all graph topologies}, not just networks with a single
loop.

The related ``max-product'' belief propagation algorithm finds the
maximum posterior probability estimate for singly connected networks.
We show that, even for non-Gaussian probability distributions, the
convergence points of the max-product algorithm in loopy networks are
at least local maxima of the posterior probability.  

These results motivate using the powerful belief propagation algorithm
in a broader class of networks, and help clarify the empirical
performance results.