Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(16)
Artificial Intelligent
Belief Propagation
Bipartite Graph
Digital Communication
Factor Graph
forwardbackward algorithm
Graphical Model
Indexing Terms
Message Passing
Signal Processing
Sum Product Algorithm
Turbo Decoding
bayesian network
Fast Fourier Transform
kalman filter
viterbi algorithm
Related Publications
(148)
The generalized distributive law
Probabilistic reasoning in intelligent systems
Codes and Decoding on General Graphs
Probabilistic Reasoning in Intelligent Systems: Networks of PlausibleInference
LowDensity ParityCheck Codes
Subscribe
Academic
Publications
Factor graphs and the sumproduct algorithm
Factor graphs and the sumproduct algorithm,10.1109/18.910572,IEEE Transactions on Information Theory,Frank R. Kschischang,Brendan J. Frey,Hansandrea
Edit
Factor graphs and the sumproduct algorithm
(
Citations: 1959
)
BibTex

RIS

RefWorks
Download
Frank R. Kschischang
,
Brendan J. Frey
,
Hansandrea Loeliger
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 messagepassing algo rithm, the sumproduct algorithm, that operates in a factor graph. Following a single, simple computational rule, the sumproduct algorithm computes—either exactly or approximately—var ious 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 sumproduct 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. Index Terms—Belief propagation, factor graphs, fast Fourier transform, forward/backward algorithm, graphical models, iter ative decoding, Kalman filtering, marginalization, sumproduct algorithm, Tanner graphs, Viterbi algorithm.
Journal:
IEEE Transactions on Information Theory  TIT
, vol. 47, no. 2, pp. 498519, 2001
DOI:
10.1109/18.910572
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.comm.utoronto.ca
)
(
www.comm.utoronto.ca
)
(
www.cs.helsinki.fi
)
(
cba.mit.edu
)
(
www2.ife.ee.ethz.ch
)
(
www.engr.pitt.edu
)
(
ieeexplore.ieee.org
)
(
www.mit.edu
)
(
www.engr.pitt.edu
)
(
www.psi.toronto.edu
)
(
research.microsoft.com
)
(
wwwusers.itlabs.umn.edu
)
(
www.wisdom.weizmann.ac.il
)
(
www.mac.pitt.edu
)
(
ieeexplore.ieee.org
)
(
wwwclasses.usc.edu
)
(
ieeexplore.ieee.org
)
(
www.comm.toronto.edu
)
(
www.mit.edu
)
(
www.informatik.unitrier.de
)
(
www.comm.toronto.edu
)
(
www.psi.toronto.edu
)
(
www.isiweb.ee.ethz.ch
)
More »
Citation Context
(1450)
...medoids, all points are simultaneously considered as potential exemplars, instead of initially picking random data points as exemplars. A random choice of exemplars might lead to completely different results for every run with new initial random assignments. Instead, affinity propagation needs to be run only once, and will always come up with the same or very similar results. A further advantage is that the number of desired clusters does not have to be specified in advance. In contrast, the number of clusters as well as the cluster exemplars and the assignments of data points to exemplars emerge from an iterative message passing algorithm on a factor graph representation
...
Michael Pfeiffer
,
et al.
Probing Real Sensory Worlds of Receivers with Unsupervised Clustering
...functions are often referred to as “messages” in the machinelearning literature
...
Oscar Westesson
,
et al.
Accurate Reconstruction of InsertionDeletion Histories by Statistical...
...In particular, genes may cooperate to produce proteins that assemble the basal transcription apparatus [
33
], or disjunctively by their proteins competing for binding site within a promoter [34]...
Bane Vasic
,
et al.
An Information Theoretic Approach to Constructing Robust Boolean Gene ...
...Treated as a factor graph [
7
] with particular variabledegree restrictions, and interpreted using the standard semantics of factor graphs, a normal factor graph represents a multivariate function that factors as the product of all of the local functions that are represented by the graph vertices...
...When treated as a factor graph under the conventional semantics [
7
], the NFG represents the product of all functions in . This product, expressing a function on , will be called the interior function6 realized by the NFG...
...In the framework of factor graphs [
7
], the product of any collection of multivariate functions may be represented by a factor graph...
Ali AlBashabsheh
,
et al.
Normal Factor Graphs and Holographic Transformations
...At the same time as [5] (in an adjacent paper in the same special issue), the conceptual framework of “factor graphs” was introducedbyKschischang,Frey,andLoeliger[
11
]tounifyvarious styles of graphical models such as Tanner graphs, Bayesian networks, Markov randomfields, Kalman filtering, and so forth, and the various computational algorithms that have been developed independently in these various fields...
G. David Forney Jr.
.
Codes on Graphs: Duality and MacWilliams Identities
References
(31)
The generalized distributive law
(
Citations: 305
)
Srinivas M. Aji
,
Robert J. Mceliece
Journal:
IEEE Transactions on Information Theory  TIT
, vol. 46, no. 2, pp. 325343, 2000
Codes on graphs: Normal realizations
(
Citations: 250
)
G. David Forney Jr.
Journal:
IEEE Transactions on Information Theory  TIT
, vol. 47, no. 2, pp. 520548, 2001
Good Codes Based on Very Sparse Matrices
(
Citations: 165
)
David J. C. Mackay
,
Radford Neal
Conference:
IMA Conference on Cryptography and Coding
, pp. 100111, 1995
Good ErrorCorrecting Codes Based on Very Sparse Matrices
(
Citations: 1504
)
David J. C. Mackay
Journal:
IEEE Transactions on Information Theory  TIT
, vol. 45, no. 2, pp. 399431, 1999
Optimal decoding of linear codes for minimizing symbol error rate
(
Citations: 3161
)
L. Bahl
,
J. Cocke
,
F. Jelinek
,
J. Raviv
Journal:
IEEE Transactions on Information Theory  TIT
, 1974
Sort by:
Citations
(1959)
iSAM2: Incremental smoothing and mapping using the Bayes tree
Michael Kaess
,
Hordur Johannsson
,
Richard Roberts
,
Viorela Ila
,
John J Leonard
,
Frank Dellaert
Journal:
International Journal of Robotic Research  IJRR
, vol. 31, no. 2, pp. 216235, 2012
Probing Real Sensory Worlds of Receivers with Unsupervised Clustering
Michael Pfeiffer
,
Manfred Hartbauer
,
Alexander B. Lang
,
Wolfgang Maass
,
Heinrich Römer
Journal:
PLOS One
, vol. 7, no. 6, 2012
Accurate Reconstruction of InsertionDeletion Histories by Statistical Phylogenetics
Oscar Westesson
,
Gerton Lunter
,
Benedict Paten
,
Ian Holmes
Journal:
PLOS One
, vol. 7, no. 4, 2012
An Information Theoretic Approach to Constructing Robust Boolean Gene Regulatory Networks
Bane Vasic
,
Vida Ravanmehr
,
Anantha Raman Krishnan
Journal:
IEEE/ACM Transactions on Computational Biology and Bioinformatics  TCBB
, vol. 9, no. 1, pp. 5265, 2012
Normal Factor Graphs and Holographic Transformations
(
Citations: 6
)
Ali AlBashabsheh
,
Yongyi Mao
Journal:
IEEE Transactions on Information Theory  TIT
, vol. 57, no. 2, pp. 752763, 2011