HOME HELP FEEDBACK SUBSCRIPTIONS ARCHIVE SEARCH TABLE OF CONTENTS		QUICK SEARCH:   [advanced] Author: Keyword(s): Year:  Vol:  Page:

This Article Full Text Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Similar articles in this journal Similar articles in PubMed Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Weiss, Y. Search for Related Content PubMed PubMed Citation Articles by Weiss, Y.

Correctness of Local Probability Propagation in Graphical Models with Loops

Department of Brain and Cognitive Sciences, MIT, Cambridge, MA 02139, U.S.A.

Graphical models, such as Bayesian networks and Markov networks, represent joint distributions over a set of variables by means of a graph. When the graph is singly connected, local propagation rules of the sort proposed by Pearl (1988) are guaranteed to converge to the correct posterior probabilities. Recently a number of researchers have empirically demonstrated good performance of these same local propagation schemes on graphs with loops, but a theoretical understanding of this performance has yet to be achieved.

For graphical models with a single loop, we derive an analytical relationship between the probabilities computed using local propagation and the correct marginals. Using this relationship we show a category of graphical models with loops for which local propagation gives rise to provably optimal maximum a posteriori assignments (although the computed marginals will be incorrect). We also show how nodes can use local information in the messages they receive in order to correct their computed marginals.

We discuss how these results can be extended to graphical models with multiple loops and show simulation results suggesting that some properties of propagation on single-loop graphs may hold for a larger class of graphs. Specifically we discuss the implication of our results for understanding a class of recently proposed error-correcting codes known as turbo codes.

This article has been cited by other articles:

				J. A. BILMES What HMMs Can Do IEICE Trans D: Information, March 1, 2006; E89-D(3): 869 - 891. [Abstract] [PDF]

				N. TAGA and S. MASE On the Convergence of Loopy Belief Propagation Algorithm for Different Update Rules IEICE Trans A: Fundamentals, February 1, 2006; E89-A(2): 575 - 582. [Abstract] [PDF]

				P. Pakzad and V. Anantharam Estimation and Marginalization Using the Kikuchi Approximation Methods Neural Comput., August 1, 2005; 17(8): 1836 - 1873. [Abstract] [Full Text] [PDF]

				T. Heskes On the Uniqueness of Loopy Belief Propagation Fixed Points Neural Comput., November 1, 2004; 16(11): 2379 - 2413. [Abstract] [Full Text] [PDF]

				S. Ikeda, T. Tanaka, and S.-i. Amari Stochastic Reasoning, Free Energy, and Information Geometry Neural Comput., September 1, 2004; 16(9): 1779 - 1810. [Abstract] [Full Text] [PDF]

				M. Welling and Y. W. Teh Linear Response Algorithms for Approximate Inference in Graphical Models Neural Comput., January 1, 2004; 16(1): 197 - 221. [Abstract] [Full Text] [PDF]

				N. A. Pierce and E. Winfree Protein Design is NP-hard Protein Eng. Des. Sel., October 1, 2002; 15(10): 779 - 782. [Abstract] [Full Text] [PDF]

				Y. Weiss and W. T. Freeman Correctness of Belief Propagation in Gaussian Graphical Models of Arbitrary Topology Neural Comput., October 1, 2001; 13(10): 2173 - 2200. [Abstract] [Full Text] [PDF]

				E. Mjolsness and D. DeCoste Machine Learning for Science: State of the Art and Future Prospects Science, September 14, 2001; 293(5537): 2051 - 2055. [Abstract] [Full Text] [PDF]