Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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
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 : 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.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download
Contributor : Jean-Marc Lasgouttes Connect in order to contact the contributor
Submitted on : Friday, January 21, 2011 - 4:55:22 PM
Last modification on : Wednesday, October 26, 2022 - 8:16:04 AM
Long-term archiving on: : Tuesday, November 6, 2012 - 12:00:24 PM


Files produced by the author(s)


  • HAL Id : inria-00558444, version 1


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⟩



Record views


Files downloads