Factor graphs and the sum-product algorithm

by: FR Kschischang, BJ Frey, HA Loeliger

Information Theory, IEEE Transactions on, Vol. 47, No. 2. (2001), pp. 498-519.

View FullText article

DOI, IEEE Explore

Reviews [Write a review of this article]

There are no reviews of this article

Find related articles from these CiteULike users

tkollar, XIANG, nojhan, markusd, dlmace, yaroslavvb, metamerist, pcarbo, marcosmuller, rwm101, chenjinhui, rsantana, ElQuijote42, zeppe, john_ardelius, daniel51, delip

Find related articles with these CiteULike tags

aland-07, algorithm, bayesian, belief, beliefpropagation, belief-propagation, bp, factor, factor_graph, factor-graph, factor-graphs, factorization, fft, graph, graphical, graphicalmodel, graphicalmodels, graphical-models, graphs, imaging, inference, information_theory, information-theory, loopybp, machine-learning, message-passing, mimo, models, morphology-project, network, no-tag, probability, product, propagation, propogation, sum, sum_product, sum-product

摘要

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

@article{citeulike:474507, abstract = {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}, author = {Kschischang, F. R. and Frey, B. J. and Loeliger, H. A. }, citeulike-article-id = {474507}, doi = {10.1109/18.910572}, journal = {Information Theory, IEEE Transactions on}, keywords = {machine-learning, morphology-project}, number = {2}, pages = {498--519}, posted-at = {2008-05-07 19:41:44}, priority = {2}, title = {Factor graphs and the sum-product algorithm}, url = {http://dx.doi.org/10.1109/18.910572}, volume = {47}, year = {2001} }

RIS record

TY - JOUR ID - citeulike:474507 L3 - citeulike-article-id:474507 TI - Factor graphs and the sum-product algorithm JF - Information Theory, IEEE Transactions on VL - 47 IS - 2 SP - 498 EP - 519 N2 - 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 KW - machine-learning KW - morphology-project AU - Kschischang, FR AU - Frey, BJ AU - Loeliger, HA PY - 2001/// UR - http://dx.doi.org/10.1109/18.910572 ER -

RIS BibTeX