The Role of Normalization in the Belief Propagation Algorithm

An important part of problems in statistical physics and computer science can be expressed as the computation of marginal probabilities over a Markov Random Field. The belief propagation algorithm, which is an exact procedure to compute these marginals when the underlying graph is a tree, has gained its popularity as an efficient way to approximate them in the more general case. In this paper, we focus on an aspect of the algorithm that did not get that much attention in the literature, which is the effect of the normalization of the messages. We show in particular that, for a large class of normalization strategies, it is possible to focus only on belief convergence. Following this, we express the necessary and sufficient conditions for local stability of a fixed point in terms of the graph structure and the beliefs values at the fixed point. We also explicit some connexion between the normalization constants and the underlying Bethe Free Energy.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