Academic
Publications
Factor graphs and the sum-product algorithm

Factor graphs and the sum-product algorithm,10.1109/18.910572,IEEE Transactions on Information Theory,Frank R. Kschischang,Brendan J. Frey,Hans-andrea

Factor graphs and the sum-product algorithm   (Citations: 1959)
BibTex | RIS | RefWorks Download
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 algo- rithm, 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—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 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. Index Terms—Belief propagation, factor graphs, fast Fourier transform, forward/backward algorithm, graphical models, iter- ative decoding, Kalman filtering, marginalization, sum-product algorithm, Tanner graphs, Viterbi algorithm.
Journal: IEEE Transactions on Information Theory - TIT , vol. 47, no. 2, pp. 498-519, 2001
Cumulative Annual
    • ...-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 Pfeifferet al. Probing Real Sensory Worlds of Receivers with Unsupervised Clustering

    • ...functions are often referred to as “messages” in the machine-learning literature ...

    Oscar Westessonet al. Accurate Reconstruction of Insertion-Deletion 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 Vasicet al. An Information Theoretic Approach to Constructing Robust Boolean Gene ...

    • ...Treated as a factor graph [7] with particular variable-degree 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 Al-Bashabshehet 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

Sort by: