IEICE TRANSACTIONS on Fundamentals
On the Convergence of Loopy Belief Propagation Algorithm for Different Update Rules
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E89-A No.2 pp.575-582
- Publication Date
- 2006/02/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1093/ietfec/e89-a.2.575
- Type of Manuscript
- PAPER
- Category
- Information Theory
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Nobuyuki TAGA, Shigeru MASE, "On the Convergence of Loopy Belief Propagation Algorithm for Different Update Rules" in IEICE TRANSACTIONS on Fundamentals,
vol. E89-A, no. 2, pp. 575-582, February 2006, doi: 10.1093/ietfec/e89-a.2.575.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e89-a.2.575/_p
Copy
@ARTICLE{e89-a_2_575,
author={Nobuyuki TAGA, Shigeru MASE, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On the Convergence of Loopy Belief Propagation Algorithm for Different Update Rules},
year={2006},
volume={E89-A},
number={2},
pages={575-582},
abstract={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.},
keywords={},
doi={10.1093/ietfec/e89-a.2.575},
ISSN={1745-1337},
month={February},}
Copy
TY - JOUR
TI - On the Convergence of Loopy Belief Propagation Algorithm for Different Update Rules
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 575
EP - 582
AU - Nobuyuki TAGA
AU - Shigeru MASE
PY - 2006
DO - 10.1093/ietfec/e89-a.2.575
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E89-A
IS - 2
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - February 2006
AB - 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.
ER -
English
