Loopy Belief Propagation Gives Exact Posterior Means for Gaussian
Yaakov Weiss, William T. Freeman · 1999
Graphical models, such as Bayesian networks and Markov Random Fields represent joint distributions over a set of variables by means of a graph. When the graph is singly connected, local rules of the sort proposed by Pearl (1988) are guaranteed to converge to the correct posterior probabilities. Recently, a number of researchers have empirically demonstrated good performance belief -- 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 very little theoretical understanding of the performance of loopy propagation. Here we prove that when the nodes in the graph describe jointly Gaussian random variables, if belief propagation converges then it will give the correct posterior means for all graph topologies, not just networks with a single loop. This justifies using belief propagation in a broader class of networks, and helps clarify the empirical performance results.