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 metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/hal-00719204
Contributor : Victorin Martin <>
Submitted on : Thursday, July 26, 2012 - 4:42:52 PM
Last modification on : Friday, May 25, 2018 - 12:02:03 PM
Long-term archiving on : Saturday, October 27, 2012 - 2:22:42 AM

Files

FreeSTAIRS.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00719204, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

389

Files downloads

151