| |
Abstract:
Local "belief propagation" rules of the sort proposed by
Pearl 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 code", 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
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 multiply
connected networks, and help clarify the empirical performance
results.
|
