Weiss Y, Freeman W T
Computer Science Division, University of California, Berkeley CA 94720-1776, USA.
Neural Comput. 2001 Oct;13(10):2173-200. doi: 10.1162/089976601750541769.
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 graphs. Recently, good performance has been obtained by using these same rules on graphs with loops, a method we refer to as loopy belief propagation. Perhaps the most dramatic instance is the near Shannon-limit performance of "Turbo codes," whose decoding algorithm is equivalent to loopy propagation. Except for the case of graphs with a single loop, there has been little theoretical understanding 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. These results motivate using the powerful belief propagation algorithm in a broader class of networks and help clarify the empirical performance results.
诸如贝叶斯网络和马尔可夫随机场之类的图形模型，通过图形来表示变量之间的统计相关性。Pearl（1988）提出的那种局部“信念传播”规则，在单连通图中能保证收敛到正确的后验概率。最近，通过在有环图上使用相同的规则也取得了良好的性能，我们将这种方法称为循环信念传播。也许最引人注目的例子是“Turbo码”接近香农极限的性能，其解码算法等同于循环传播。除了具有单个环的图的情况外，对循环传播几乎没有理论上的理解。在此，当图中的节点描述联合高斯随机变量时，我们分析任意拓扑网络中的信念传播。我们给出了一个将真实后验概率与使用循环传播计算出的概率相关联的解析公式。我们给出了收敛的充分条件，并表明当信念传播收敛时，它能给出所有图拓扑的正确后验均值，而不仅仅是具有单个环的网络。这些结果促使在更广泛的网络类别中使用强大的信念传播算法，并有助于阐明实证性能结果。
