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.
Type de document :
Communication dans un congrès
Kristian Kersting and Marc Toussaint. STAIRS'12 - Sixth "Starting Artificial Intelligence Research" Symposium, Aug 2012, Montpellier, France. IOS Press, pp.180-191, 2012
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00719204
Contributeur : Victorin Martin <>
Soumis le : jeudi 26 juillet 2012 - 16:42:52
Dernière modification le : vendredi 25 mai 2018 - 12:02:03
Document(s) archivé(s) le : samedi 27 octobre 2012 - 02:22:42

Fichiers

FreeSTAIRS.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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. Kristian Kersting and Marc Toussaint. STAIRS'12 - Sixth "Starting Artificial Intelligence Research" Symposium, Aug 2012, Montpellier, France. IOS Press, pp.180-191, 2012. 〈hal-00719204〉

Partager

Métriques

Consultations de la notice

338

Téléchargements de fichiers

126