Sufficient conditions for convergence of Loopy Belief Propagation

arXiv (Cornell University)Published 4 July 2012Open access

Joris M. Mooij, Hilbert J. Kappen

DOI10.48550/arxiv.1207.1405

Citations53

TL;DR

Novel sufficient conditions for convergence of Loopy Belief Propagation to a unique fixed point are derived and the results improve upon previously known conditions.

Abstract

We derive novel sufficient conditions for convergence of Loopy Belief Propagation (also known as the Sum-Product algorithm) to a unique fixed point. Our results improve upon previously known conditions. For binary variables with (anti-)ferromagnetic interactions, our conditions seem to be sharp.

Keywords

Computer ScienceEngineering

Neural ComputationCorrectness of Local Probability Propagation in Graphical Models with Loops

470 Citations2000Yair Weiss

An analytical relationship is derived between the probabilities computed using local propagation and the correct marginals and 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).

Journal of Machine Learning ResearchLoopy Belief Propagation: Convergence and Effects of Message Errors

304 Citations2005Alexander Ihler, John W. Fischer +1 more

This analysis leads to convergence conditions for traditional BP message Passing, and both strict bounds and estimates of the resulting error in systems of approximate BP message passing.

Loopy belief propagation and Gibbs measures

190 Citations2002Sekhar Tatikonda, Michael I. Jordan

This work relates convergence of LBP to the existence of a weak limit for a sequence of Gibbs measures defined on the LBP's associated computation tree, and develops easily testable sufficient conditions for convergence.

Neural ComputationOn the Uniqueness of Loopy Belief Propagation Fixed Points

141 Citations2004Tom Heskes

Qualifying conditions for the uniqueness of loopy belief propagation fixed points are derived and possible implications for convergent algorithms, as well as for other approximate free energies, are discussed.

Advances in MathematicsA Polynomial Counterexample to the Markus–Yamabe Conjecture

106 Citations1997Anna Cima, Arno van den Essen +3 more

Neural Information Processing SystemsMessage Errors in Belief Propagation

41 Citations2004Alexander Ihler, John W. Fisher +1 more

This work analyzes the effect of introducing errors into the BP message computations with respect to a particular measure of message error, and shows bounds on the accumulation of errors in the system.

Uncertainty in Artificial IntelligenceLoopy Belief Propogation and Gibbs Measures.

14 Citations2002Sekhar Tatikonda, Michael I. Jordan