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:

Technical discussion: 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.


Y. Weiss and W. T. Freeman
Correctness of Belief Propagation in Gaussian Graphical Models of Arbitrary Topology. in: Advances in Neural Information Processing Systems 12, edited by S. A. Solla, T. K. Leen, and K-R Muller, 2000. MERL-TR99-38.


Y. Weiss and W. T. Freeman
Correctness of Belief Propagation in Gaussian Graphical Models of Arbitrary Topology. submitted journal version.