Sufficient Conditions for Convergence of the Sum–Product Algorithm

DOI10.1109/TIT.2007.909166zbMATH Open1314.94112arXivcs/0504030OpenAlexW2167149929WikidataQ56431750 ScholiaQ56431750MaRDI QIDQ3549121FDOQ3549121

Authors: Joris Mooij, Hilbert J. Kappen 

Publication date: 21 December 2008

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

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.

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

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

zbMATH Keywords

convergencegraphical modelsloopy belief propagationsum-product algorithmmessage passingfactor graphsmarginalizationContraction

Mathematics Subject Classification ID

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

Cited In (15)

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