Approximate inference on planar graphs using Loop Calculus and Belief Propagation

Vicenç Gómez, Bert Kappen, Misha Chertkov
Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, PMLR R7:185-192, 2009.

Abstract

We introduce novel results for approximate inference on planar graphical models using the loop calculus framework. The loop calculus (Chertkov and Chernyak, 2006) allows to express the exact partition function of a graphical model as a finite sum of terms that can be evaluated once the belief propagation (BP) solution is known. In general, full summation over all correction terms is intractable. We develop an algorithm for the approach presented in (Certkov et al., 2008) which represents an efficient truncation scheme on planar graphs and a new representation of the series in terms of Pfaffians of matrices. We analyze the performance of the algorithm for the partition function approximation for models with binary variables and pairwise interactions on grids and other planar graphs. We study in detail both the loop series and the equivalent Pfaffian series and show that the first term of the Pfaffian series for the general, intractable planar model, can provide very accurate approximations. The algorithm outperforms previous truncation schemes of the loop series and is competitive with other state-of-the-art methods for approximate inference.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR7-gomez09a, title = {Approximate inference on planar graphs using Loop Calculus and Belief Propagation}, author = {G{\'o}mez, Vicen{\c{c}} and Kappen, Bert and Chertkov, Misha}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {185--192}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/gomez09a/gomez09a.pdf}, url = {https://proceedings.mlr.press/r7/gomez09a.html}, abstract = {We introduce novel results for approximate inference on planar graphical models using the loop calculus framework. The loop calculus (Chertkov and Chernyak, 2006) allows to express the exact partition function of a graphical model as a finite sum of terms that can be evaluated once the belief propagation (BP) solution is known. In general, full summation over all correction terms is intractable. We develop an algorithm for the approach presented in (Certkov et al., 2008) which represents an efficient truncation scheme on planar graphs and a new representation of the series in terms of Pfaffians of matrices. We analyze the performance of the algorithm for the partition function approximation for models with binary variables and pairwise interactions on grids and other planar graphs. We study in detail both the loop series and the equivalent Pfaffian series and show that the first term of the Pfaffian series for the general, intractable planar model, can provide very accurate approximations. The algorithm outperforms previous truncation schemes of the loop series and is competitive with other state-of-the-art methods for approximate inference.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Approximate inference on planar graphs using Loop Calculus and Belief Propagation %A Vicenç Gómez %A Bert Kappen %A Misha Chertkov %B Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2009 %E Jeff Bilmes %E Andrew Y. Ng %F pmlr-vR7-gomez09a %I PMLR %P 185--192 %U https://proceedings.mlr.press/r7/gomez09a.html %V R7 %X We introduce novel results for approximate inference on planar graphical models using the loop calculus framework. The loop calculus (Chertkov and Chernyak, 2006) allows to express the exact partition function of a graphical model as a finite sum of terms that can be evaluated once the belief propagation (BP) solution is known. In general, full summation over all correction terms is intractable. We develop an algorithm for the approach presented in (Certkov et al., 2008) which represents an efficient truncation scheme on planar graphs and a new representation of the series in terms of Pfaffians of matrices. We analyze the performance of the algorithm for the partition function approximation for models with binary variables and pairwise interactions on grids and other planar graphs. We study in detail both the loop series and the equivalent Pfaffian series and show that the first term of the Pfaffian series for the general, intractable planar model, can provide very accurate approximations. The algorithm outperforms previous truncation schemes of the loop series and is competitive with other state-of-the-art methods for approximate inference. %Z Reissued by PMLR on 04 October 2026.
APA
Gómez, V., Kappen, B. & Chertkov, M.. (2009). Approximate inference on planar graphs using Loop Calculus and Belief Propagation. Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R7:185-192 Available from https://proceedings.mlr.press/r7/gomez09a.html. Reissued by PMLR on 04 October 2026.

Related Material