Loop Corrected Belief Propagation

Joris Mooij, Bastian Wemmenhove, Bert Kappen, Tommaso Rizzo
Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, PMLR 2:331-338, 2007.

Abstract

We propose a method for improving Belief Propagation (BP) that takes into account the influence of loops in the graphical model. The method is a variation on and generalization of the method recently introduced by Montanari and Rizzo [2005]. It consists of two steps: (i) standard BP is used to calculate cavity distributions for each variable (i.e. probability distributions on the Markov blanket of a variable for a modified graphical model, in which the factors involving that variable have been removed); (ii) all cavity distributions are combined by a messagepassing algorithm to obtain consistent single node marginals. The method is exact if the graphical model contains a single loop. The complexity of the method is exponential in the size of the Markov blankets. The results are very accurate in general: the error is often several orders of magnitude smaller than that of standard BP, as illustrated by numerical experiments.

Cite this Paper

BibTeX
@InProceedings{pmlr-v2-mooij07a, title = {Loop Corrected Belief Propagation}, author = {Mooij, Joris and Wemmenhove, Bastian and Kappen, Bert and Rizzo, Tommaso}, booktitle = {Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics}, pages = {331--338}, year = {2007}, editor = {Meila, Marina and Shen, Xiaotong}, volume = {2}, series = {Proceedings of Machine Learning Research}, address = {San Juan, Puerto Rico}, month = {21--24 Mar}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v2/mooij07a/mooij07a.pdf}, url = {https://proceedings.mlr.press/v2/mooij07a.html}, abstract = {We propose a method for improving Belief Propagation (BP) that takes into account the influence of loops in the graphical model. The method is a variation on and generalization of the method recently introduced by Montanari and Rizzo [2005]. It consists of two steps: (i) standard BP is used to calculate cavity distributions for each variable (i.e. probability distributions on the Markov blanket of a variable for a modified graphical model, in which the factors involving that variable have been removed); (ii) all cavity distributions are combined by a messagepassing algorithm to obtain consistent single node marginals. The method is exact if the graphical model contains a single loop. The complexity of the method is exponential in the size of the Markov blankets. The results are very accurate in general: the error is often several orders of magnitude smaller than that of standard BP, as illustrated by numerical experiments.} }
Endnote
%0 Conference Paper %T Loop Corrected Belief Propagation %A Joris Mooij %A Bastian Wemmenhove %A Bert Kappen %A Tommaso Rizzo %B Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2007 %E Marina Meila %E Xiaotong Shen %F pmlr-v2-mooij07a %I PMLR %P 331--338 %U https://proceedings.mlr.press/v2/mooij07a.html %V 2 %X We propose a method for improving Belief Propagation (BP) that takes into account the influence of loops in the graphical model. The method is a variation on and generalization of the method recently introduced by Montanari and Rizzo [2005]. It consists of two steps: (i) standard BP is used to calculate cavity distributions for each variable (i.e. probability distributions on the Markov blanket of a variable for a modified graphical model, in which the factors involving that variable have been removed); (ii) all cavity distributions are combined by a messagepassing algorithm to obtain consistent single node marginals. The method is exact if the graphical model contains a single loop. The complexity of the method is exponential in the size of the Markov blankets. The results are very accurate in general: the error is often several orders of magnitude smaller than that of standard BP, as illustrated by numerical experiments.
RIS
TY - CPAPER TI - Loop Corrected Belief Propagation AU - Joris Mooij AU - Bastian Wemmenhove AU - Bert Kappen AU - Tommaso Rizzo BT - Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics DA - 2007/03/11 ED - Marina Meila ED - Xiaotong Shen ID - pmlr-v2-mooij07a PB - PMLR DP - Proceedings of Machine Learning Research VL - 2 SP - 331 EP - 338 L1 - http://proceedings.mlr.press/v2/mooij07a/mooij07a.pdf UR - https://proceedings.mlr.press/v2/mooij07a.html AB - We propose a method for improving Belief Propagation (BP) that takes into account the influence of loops in the graphical model. The method is a variation on and generalization of the method recently introduced by Montanari and Rizzo [2005]. It consists of two steps: (i) standard BP is used to calculate cavity distributions for each variable (i.e. probability distributions on the Markov blanket of a variable for a modified graphical model, in which the factors involving that variable have been removed); (ii) all cavity distributions are combined by a messagepassing algorithm to obtain consistent single node marginals. The method is exact if the graphical model contains a single loop. The complexity of the method is exponential in the size of the Markov blankets. The results are very accurate in general: the error is often several orders of magnitude smaller than that of standard BP, as illustrated by numerical experiments. ER -
APA
Mooij, J., Wemmenhove, B., Kappen, B. & Rizzo, T.. (2007). Loop Corrected Belief Propagation. Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 2:331-338 Available from https://proceedings.mlr.press/v2/mooij07a.html.

Related Material