Copyright © 2006 The Institute of Electronics, Information and Communication Engineers
Regular Section -- Papers -- Information Theory |
On the Convergence of Loopy Belief Propagation Algorithm for Different Update Rules
1 The authors are with Tokyo Institute of Technology, Tokyo, 152-8552 Japan. E-mail: Nobuyuki.Taga{at}is.titech.ac.jp, E-mail: mase{at}is.titech.ac.jp
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.
Key Words: belief propagation algorithm, Markov random field, unwrapped network, phase transition
Manuscript received January 12, 2005. Manuscript revised June 18, 2005. Final manuscript received October 18, 2005.