Sufficient conditions for convergence of Loopy Belief Propagation

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.

Appears in Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence (UAI2005)

Cited by in corpus (6)

• Residual Belief Propagation: Informed Scheduling for Asynchronous Message Passing
• Convergent Message-Passing Algorithms for Inference over General Graphs with Convex Free Energies
• Generalized Belief Propagation on Tree Robust Structured Region Graphs
• From Learning to Analytics: Improving Model Efficacy with Goal-Directed Client Selection
• Accuracy Bounds for Belief Propagation
• $\alpha$ Belief Propagation for Approximate Inference