Sum-Product Algorithm

定义 Definition

Sum-product algorithm（和-积算法）是一种在因子图/贝叶斯网络/马尔可夫随机场上进行消息传递（message passing）的推断算法，用来高效计算边缘概率或后验分布（例如 (p(x_i))）。它也是信道编码中（如 LDPC、Turbo 码）译码的核心思想之一。除“求边缘”外，还有用于求最可能解释的变体（如 max-product）。

发音 Pronunciation

/ˈsʌm ˈprɑːdʌkt ˈælɡəˌrɪðəm/

例句 Examples

The sum-product algorithm computes marginal probabilities by passing messages on a factor graph.
和-积算法通过在因子图上传递消息来计算边缘概率。

In iterative decoding of LDPC codes, the sum-product algorithm approximates posterior beliefs efficiently, even for very large graphs.
在 LDPC 码的迭代译码中，和-积算法能够在图规模很大时仍高效地近似计算后验信念（概率）。

词源 Etymology

“Sum-product”这个名称来自它在推断中反复进行的两类运算：对某些变量进行求和（sum，边缘化），并把来自不同因子的贡献进行相乘（product，组合/累积似然）。该算法与因子图（factor graph）表示密切相关，20 世纪末在编码理论与概率推断领域被系统化与推广，常被视为“belief propagation（信念传播）”在一般因子图上的形式。

相关词 Related Words

• Belief Propagation
• Factor Graph
• Message Passing
• Marginalization
• Bayesian Network
• Markov Random Field
• LDPC Code
• Max-Product Algorithm

文献与作品 Literary Works

• Kschischang, Frey & Loeliger：《Factor Graphs and the Sum-Product Algorithm》（IEEE Transactions on Information Theory, 2001）
• David J. C. MacKay：《Information Theory, Inference, and Learning Algorithms》
• Christopher M. Bishop：《Pattern Recognition and Machine Learning》（涉及图模型推断与消息传递思想）
• Richardson & Urbanke：《Modern Coding Theory》（讨论 LDPC 等编码的迭代译码与相关算法）