Sufficient Conditions for Convergence of the Sum–Product Algorithm

DOI10.1109/TIT.2007.909166MaRDI QIDQ3549121zbMATH OpenOpenAlexWikidataFDO

Authors Joris Mooij, Hilbert J. Kappen

Publication date 21 December 2008

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0504030

zbMATH Keywords

Contractionconvergencefactor graphsgraphical modelsloopy belief propagationmarginalizationmessage passingsum-product algorithm

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Decoding (94B35)

Abstract: We derive novel conditions that guarantee convergence of the Sum-Product algorithm (also known as Loopy Belief Propagation or simply Belief Propagation) to a unique fixed point, irrespective of the initial messages. The computational complexity of the conditions is polynomial in the number of variables. In contrast with previously existing conditions, our results are directly applicable to arbitrary factor graphs (with discrete variables) and are shown to be valid also in the case of factors containing zeros, under some additional conditions. We compare our bounds with existing ones, numerically and, if possible, analytically. For binary variables with pairwise interactions, we derive sufficient conditions that take into account local evidence (i.e., single variable factors) and the type of pair interactions (attractive or repulsive). It is shown empirically that this bound outperforms existing bounds.

Recommendations

• On the Uniqueness of Loopy Belief Propagation Fixed Points
• On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs
• Convergence analysis of distributed inference with vector-valued Gaussian belief propagation
• Correctness of belief propagation in Gaussian graphical models of arbitrary topology
• The sum-product algorithm on small graphs

Cited in

(15)

• Neural network implementation of inference on binary Markov random fields with probability coding
• Step-by-step community detection in volume-regular graphs
• Convergence of a belief propagation algorithm for biological networks
• Convergence analysis of distributed inference with vector-valued Gaussian belief propagation
• Local stability of belief propagation algorithm with multiple fixed points
• On the Uniqueness of Loopy Belief Propagation Fixed Points
• The sum-product algorithm: algebraic independence and computational aspects
• Latent binary MRF for online reconstruction of large scale systems
• Find Your Place: Simple Distributed Algorithms for Community Detection
• Diagonal stationary points of the Bethe functional
• Convergence of Gaussian belief propagation under general pairwise factorization: connecting Gaussian MRF with pairwise linear Gaussian model
• Exact or approximate inference in graphical models: why the choice is dictated by the treewidth, and how variable elimination can be exploited
• Convergence of the belief propagation algorithm for RB model instances
• The sum-product algorithm on small graphs
• High-Dimensional Macroeconomic Forecasting Using Message Passing Algorithms

This page was built for publication: Sufficient Conditions for Convergence of the Sum–Product Algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3549121)