Generalized Belief Propagation
Generalized Belief Propagation
复制标题
DOI：
--
复制
发表时间：
2000
期刊：
影响因子：
9.4
通讯作者：
J. Yedidia;W. Freeman;Yair Weiss
中科院分区：
文献类型：
--
作者：
J. Yedidia;W. Freeman;Yair Weiss
置信传播（BP）原本只适用于树状网络，但在许多涉及循环网络（包括 Turbo 码）的应用中却出奇地好用。然而，人们对该算法或其为一般图找到的解决方案的性质知之甚少。我们证明 BP 只能收敛到近似自由能的驻点，在统计物理学中称为 Bethe 自由能。该结果表征了 BP 不动点，并与变分方法联系起来以进行近似推理。更重要的是，我们的分析让我们能够以自 1935 年贝特近似提出以来统计物理学取得的进展为基础。菊池和其他人已经展示了如何构建更准确的自由能近似，其中贝特近似是最简单的。利用我们分析中的见解，我们推导出这些菊池近似的广义置信传播（GBP）版本。这些新的消息传递算法可以比普通的 BP 更准确，并且复杂性可调节增加。我们在网格马尔可夫网络上说明了这种新的 GBP 算法，并表明它给出的边际概率比使用普通 BP 的边际概率要准确得多。
Belief propagation (BP) was only supposed to work for treelike networks but works surprisingly well in many applications involving networks with loops, including turbo codes. However, there has been little understanding of the algorithm or the nature of the solutions it finds for general graphs. We show that BP can only converge to a stationary point of an approximate free energy, known as the Bethe free energy in statistical physics. This result characterizes BP fixed-points and makes connections with variational approaches to approximate inference. More importantly, our analysis lets us build on the progress made in statistical physics since Bethe's approximation was introduced in 1935. Kikuchi and others have shown how to construct more accurate free energy approximations, of which Bethe's approximation is the simplest. Exploiting the insights from our analysis, we derive generalized belief propagation (GBP) versions of these Kikuchi approximations. These new message passing algorithms can be significantly more accurate than ordinary BP, at an adjustable increase in complexity. We illustrate such a new GBP algorithm on a grid Markov network and show that it gives much more accurate marginal probabilities than those found using ordinary BP.