Factor graphs and the sum-product algorithm
Factor graphs and the sum-product algorithm
复制标题
DOI：
10.1109/18.910572
复制
发表时间：
2001-02-01
影响因子：
2.5
通讯作者：
Loeliger, HA
中科院分区：
文献类型：
--
作者：
Kschischang, FR;Frey, BJ;Loeliger, HA
必须处理包含多个变量的复杂全局函数的算法通常利用这样一种方式，即给定的函数作为“局部”函数的乘积，每个局部函数依赖于变量的一个子集。这样的因式分解可以用我们称为因子图的二部图来可视化。在这篇教程论文中，我们提出了一种通用的消息传递算法-和积算法，它在因子图中运行，遵循一个简单的计算规则，和积算法计算-精确或近似-从全局函数派生的各种边缘函数。在人工智能、信号处理和数字通信中开发的各种算法可以作为和积算法的具体实例而得到，包括前向/后向算法、维特比算法、迭代“加速”译码算法、用于贝叶斯网络的珀尔的信任传播算法、卡尔曼滤波和某些快速傅里叶变换(FFT)算法。
Algorithms that must deal with complicated global functions of many variables often exploit the manner in which the given functions factor as a product of "local" functions, each of which depends on a subset of the variables. Such a factorization can be visualized with a bipartite graph that we call a factor graph. In this tutorial paper, we present a generic message-passing algorithm, the sum-product algorithm, that operates in a factor graph, Following a single, simple computational rule, the sum-product algorithm computes-either exactly or approximately-various marginal functions derived from the global function. A wide variety of algorithms developed in artificial intelligence, signal processing, and digital communications can be derived as specific instances of the sum-product algorithm, including the forward/backward algorithm, the Viterbi algorithm, the iterative "turbo" decoding algorithm, Pearl's belief propagation algorithm for Bayesian networks, the Kalman filter, and certain fast Fourier transform (FFT) algorithms.