Skip to Main content Skip to Navigation
New interface
Conference papers

Local stability of Belief Propagation algorithm with multiple fixed points

Victorin Martin 1 Jean-Marc Lasgouttes 1 Cyril Furtlehner 2 
2 TAO - Machine Learning and Optimisation
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : A number of problems in statistical physics and computer science can be expressed as the computation of marginal probabilities over a Markov random field. Belief propagation, an iterative message-passing algorithm, computes exactly such marginals when the underlying graph is a tree. But it has gained its popularity as an efficient way to approximate them in the more general case, even if it can exhibits multiple fixed points and is not guaranteed to converge. In this paper, we express a new sufficient condition for local stability of a belief propagation fixed point in terms of the graph structure and the beliefs values at the fixed point. This gives credence to the usual understanding that Belief Propagation performs better on sparse graphs.
Document type :
Conference papers
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download
Contributor : Victorin Martin Connect in order to contact the contributor
Submitted on : Thursday, July 26, 2012 - 4:42:52 PM
Last modification on : Sunday, June 26, 2022 - 11:56:43 AM
Long-term archiving on: : Saturday, October 27, 2012 - 2:22:42 AM


Files produced by the author(s)


  • HAL Id : hal-00719204, version 1



Victorin Martin, Jean-Marc Lasgouttes, Cyril Furtlehner. Local stability of Belief Propagation algorithm with multiple fixed points. STAIRS'12 - Sixth "Starting Artificial Intelligence Research" Symposium, Aug 2012, Montpellier, France. pp.180-191. ⟨hal-00719204⟩



Record views


Files downloads