Correctness of Belief Propagation in Bayesian Networks with Loops
Bayesian networks represent statistical dependencies of variables by a
graph. For example, in the figure, the "y" variables may be image
values, and the "x" variables may be quantities to estimate by
computer vision. Bayesian networks are used in many machine learning
applications. Local "belief propagation" rules are guaranteed perform
inference correctly in networks without loops. Recently, researchers
have found good performance of "loopy belief propagation"--using these
same rules on graphs with loops.
We provide theoretical understanding of this good performance. We show that belief propagation converges to the correct posterior means for Gaussian random variables. We show that the convergence points of a related algorithm are at least local maxima of the posterior probability.
These results motivate using the powerful belief propagation algorithm in a broader class of networks.
Background and objectives: Problems involving probabilistic belief propagation arise in a wide variety of applications, including error correcting codes, speech recognition and medical diagnosis. Typically, a probability distribution is assumed over a set of variables and the task is to infer the values of the unobserved variables given the observed ones. If the graph is singly connected (i.e. there is only one path between any two given nodes) then there exist efficient local message--passing schemes to calculate the posterior probability of an unobserved variable given the observed variables. Pearl (1988) derived such a scheme for singly connected Bayesian networks and showed that this ``belief propagation'' algorithm is guaranteed to converge to the correct posterior probabilities (or ``beliefs''). However, as Pearl noted, the same algorithm will not give the correct beliefs for multiply connected networks:
In this work we analyze belief propagation in graphs of arbitrary
topology but focus primarily on nodes that describe jointly Gaussian
random variables. We give an exact formula that relates the correct
marginal posterior probabilities with the ones calculated using loopy
belief propagation. We show that if belief propagation converges then
it will give the correct posterior means for all graph topologies, not
just networks with a single loop. The covariance estimates will
generally be incorrect but we present a relationship between the error
in the covariance estimates and the convergence speed. For Gaussian or
non-Gaussian variables, we show that the "max-product" algorithm,
which calculates the MAP estimate in singly connected networks, only
converges to points that are at least local maxima of the posterior
probability of loopy networks. This motivates using this powerful
algorithm in a broader class of networks.