Correctness of belief propagation in Gaussian graphical models of arbitrary topology
Correctness of belief propagation in Gaussian graphical models of arbitrary topology
复制标题
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
Yair Weiss
中科院分区：
文献类型：
--
作者：
Yair Weiss
图形模型，例如贝叶斯网络和马尔可夫随机场，通过图形表示变量的统计依赖性。 Pearl [20] 提出的局部“置信传播”规则保证在单连通图中收敛到正确的后验概率。最近，通过在具有循环的图上使用这些相同的规则（一种称为“循环置信传播”的方法）获得了良好的性能。也许最引人注目的例子是“Turbo码”的近香农极限性能，其解码算法相当于循环传播。除了单循环图的情况外，对循环传播的理论理解很少。这里我们分析了任意拓扑网络中的置信传播，当图中的节点共同描述高斯随机变量时，我们给出了一个将真实后验概率与使用循环传播计算的后验概率联系起来的解析公式。我们给出了收敛的充分条件，并表明当置信传播收敛时给出所有图拓扑的正确后验均值，而不仅仅是具有单个循环的网络。相关的“最大乘积”算法找到单连接网络的最大后验概率估计。我们证明，即使对于非高斯概率分布，循环网络中最大乘积算法的固定点至少是后验概率的局部最大值。这些结果激励在更广泛的网络类别中使用强大的置信传播算法，并有助于阐明经验性能结果。提交给神经计算。初步版本出现在 Proc 中。尼普斯99
Graphical models, such as Bayesian networks and Markov random elds represent statistical dependencies of variables by a graph. Local \belief propagation" rules of the sort proposed by Pearl [20] 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 known 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 su cient 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" algorithm nds the maximumposterior probability estimate for singly connected networks. We show that, even for non-Gaussian probability distributions, the xed 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 a broader class of networks, and help clarify the empirical performance results. Sumbitted to Neural Computation. Preliminary version appeared in Proc. NIPS 99