Factor Graphs and Algorithms
Brendan J. Frey, Frank R. Kschischang, Hans‐Andrea Loeliger · 2008
A factor graph is a bipartite graph that expresses how a global function of several variables factors into a product of local functions. Factor graphs subsume many other graphical models, including Bayesian networks, Markov random fields, and Tanner graphs. We describe a general algorithm for computing "marginals" of the global function by distributed message-passing in the corresponding factor graph. A wide variety of algorithms developed in the artificial intelligence, statistics, signal processing, and digital communications communities can be derived as specific instances of this general algorithm, including Pearl's "belief propagation" and "belief revision" algorithms, the fast Fourier transform, the Viterbi algorithm, the forward/backward algorithm, and the iterative "turbo" decoding algorithm. 1 Introduction A factor graph is a bipartite graph that expresses how a global function of several variables factors into a product of local functions. Example 1. Suppose the real-valued...