Sum-product algorithm（和-积算法）是一种在因子图/贝叶斯网络/马尔可夫随机场上进行消息传递（message passing）的推断算法，用来高效计算边缘概率或后验分布（例如 \(p(x_i)\)）。它也是信道编码中（如 LDPC、Turbo 码）译码的核心思想之一。除“求边缘”外，还有用于求最可能解释的变体（如 max-product）。
/sm prdkt lrm/
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 码的迭代译码中，和-积算法能够在图规模很大时仍高效地近似计算后验信念（概率）。
“Sum-product”这个名称来自它在推断中反复进行的两类运算：对某些变量进行求和（sum，边缘化），并把来自不同因子的贡献进行相乘（product，组合/累积似然）。该算法与因子图（factor graph）表示密切相关，20 世纪末在编码理论与概率推断领域被系统化与推广，常被视为“belief propagation（信念传播）”在一般因子图上的形式。
Select Language