The Role of Normalization in the Belief Propagation Algorithm

Victorin Martin 1 Jean-Marc Lasgouttes 1 Cyril Furtlehner 2
2 TAO - Machine Learning and Optimisation
CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique
Résumé : Une part importante des problèmes en physique statistique et en informatique peut s'écrire en termes de calcul de probabilités marginales d'un champ markovien aléatoire. L'algorithme de propagation des croyance (belief propagation), qui permet de calculer ces marginales quand le graphe sous-jacent est un arbre, est devenu populaire comme moyen efficace de les approximer dans le cas général. Dans cet article, on s'intéresse à un aspect de l'algorithme qui n'a pas été étudié de très près dans la littérature : l'effet de la normalisation des messages. On montre en particulier que pour une grande classe de stratégies de normalisation, il est possible de s'intéresser uniquement à la convergence des croyances. De plus, les conditions nécessaires et suffisantes de stabilité des points fixes sont exprimées en fonction de la structure du graphe et de la valeurs des croyances. Finalement, on décrit la relation entre les constantes de normalisations et l'énergie libre de Bethe sous-jacente.
Type de document :
Rapport
[Research Report] RR-7514, INRIA. 2011, pp.31
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00558444
Contributeur : Jean-Marc Lasgouttes <>
Soumis le : vendredi 21 janvier 2011 - 16:55:22
Dernière modification le : mardi 17 avril 2018 - 11:32:23
Document(s) archivé(s) le : mardi 6 novembre 2012 - 12:00:24

Fichier

RR-7514.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00558444, version 1

Collections

Citation

Victorin Martin, Jean-Marc Lasgouttes, Cyril Furtlehner. The Role of Normalization in the Belief Propagation Algorithm. [Research Report] RR-7514, INRIA. 2011, pp.31. 〈inria-00558444〉

Partager

Métriques

Consultations de la notice

412

Téléchargements de fichiers

191