On the Convergence of Loopy Belief Propagation Algorithm for Different Update Rules

Nobuyuki TAGA  Shigeru MASE  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E89-A   No.2   pp.575-582
Publication Date: 2006/02/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e89-a.2.575
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Information Theory
belief propagation algorithm,  Markov random field,  unwrapped network,  phase transition,  

Full Text: PDF(825.3KB)>>
Buy this Article

The belief propagation (BP) algorithm is a tool with which one can calculate beliefs, marginal probabilities, of probabilistic networks without loops (e.g., Bayesian networks) in a time proportional to the number of nodes. For networks with loops, it may not converge and, even if it converges, beliefs may not be equal to exact marginal probabilities although its application is known to give remarkably good results such as in the coding theory. Tatikonda and Jordan show a theoretical result on the convergence of the algorithm for probabilistic networks with loops in terms of the theory of Markov random fields on trees and give a sufficient condition of the convergence of the algorithm. In this paper, we discuss the "impatient" update rule as well as the "lazy" update rule discussed in Tatikonda and Jordan. In the viewpoint of the theory of Markov random fields, it is shown that the rule for updating both gives essentially the same results and the impatient update rule is expected to converge faster than the lazy one. Numerical experiments are also given.