Factor graphs and the sum-product algorithm
Frank R. Kschischang, Brendan J. Frey, Hans‐Andrea Loeliger · IEEE Transactions on Information Theory · 2001
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 (1988) belief propagation algorithm for Bayesian networks, the Kalman filter, and certain fast Fourier transform (FFT) algorithms.
Cited by 6,435 works. doi:10.1109/18.910572
Authors
References
- Computers and Intractability: A Guide to the Theory of NP-Completeness
- A tutorial on hidden Markov models and selected applications in speech recognition
- Low-density parity-check codes
- Optimal decoding of linear codes for minimizing symbol error rate (Corresp.)
- Optimal decoding of linear codes for minimizing symbol error rate
- Near Shannon limit error-correcting coding and decoding: Turbo-codes. 1
- Low-Density Parity-Check Codes
- Stochastic models, estimation, and control
- Local Computations with Probabilities on Graphical Structures and Their Application to Expert Systems
- Learning and Relearning in Boltzmann Machines