Understanding belief propagation and its generalizations
Understanding belief propagation and its generalizations
复制标题
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
J. Yedidia;W. Freeman;Yair Weiss
中科院分区：
文献类型：
--
作者：
J. Yedidia;W. Freeman;Yair Weiss
“推理”问题出现在统计物理、计算机视觉、纠错编码理论和人工智能中。我们解释了信念传播（BP）算法背后的原理，这是一种基于传递本地消息来解决推理问题的有效方法。我们开发了一种统一的方法，包括从相关学科借来的例子、符号和图形模型。我们解释了BP算法与统计物理的贝特近似之间的密切联系。特别地，我们证明了BP只能收敛到一个固定点，这个固定点也是自由能的贝特近似的一个固定点。这一结果有助于解释BP算法的成功，并使变分方法与近似推理建立联系。BP与Bethe近似的联系也提出了一种基于Kikuchi等人对Bethe近似的改进来构建新的消息传递算法的方法。对于某些问题，新的广义信念传播（GBP）算法的准确率明显高于普通BP算法。我们用一个详细的例子来说明如何构造GBP算法。
"Inference" problems arise in statistical physics, computer vision, error-correcting coding theory, and AI. We explain the principles behind the belief propagation (BP) algorithm, which is an efficient way to solve inference problems based on passing local messages. We develop a unified approach, with examples, notation, and graphical models borrowed from the relevant disciplines.We explain the close connection between the BP algorithm and the Bethe approximation of statistical physics. In particular, we show that BP can only converge to a fixed point that is also a stationary point of the Bethe approximation to the free energy. This result helps explaining the successes of the BP algorithm and enables connections to be made with variational approaches to approximate inference.The connection of BP with the Bethe approximation also suggests a way to construct new message-passing algorithms based on improvements to Bethe's approximation introduced Kikuchi and others. The new generalized belief propagation (GBP) algorithms are significantly more accurate than ordinary BP for some problems. We illustrate how to construct GBP algorithms with a detailed example.