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
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/inria-00558444
Contributor : Jean-Marc Lasgouttes <>
Submitted on : Friday, January 21, 2011 - 4:55:22 PM
Last modification on : Friday, May 25, 2018 - 12:02:03 PM
Long-term archiving on : Tuesday, November 6, 2012 - 12:00:24 PM

File

RR-7514.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

457

Files downloads

216