Local stability of Belief Propagation algorithm with multiple fixed points - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2012

Local stability of Belief Propagation algorithm with multiple fixed points

Résumé

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.
Fichier principal
Vignette du fichier
FreeSTAIRS.pdf (150.82 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00719204 , version 1 (26-07-2012)

Identifiants

  • HAL Id : hal-00719204 , version 1

Citer

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⟩
229 Consultations
108 Téléchargements

Partager

Gmail Facebook X LinkedIn More