A Cluster-Cumulant Expansion at the Fixed Points of Belief Propagation

Max Welling, Andrew E. Gelfand, Alexander T. Ihler
Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, PMLR R10:882-891, 2012.

Abstract

We introduce a new cluster-cumulant expansion (CCE) based on the fixed points of iterative belief propagation (IBP). This expansion is similar in spirit to the loop-series (LS) recently introduced in [1]. However, in contrast to the latter, the CCE enjoys the following important qualities: 1) it is defined for arbitrary state spaces 2) it is easily extended to fixed points of generalized belief propagation (GBP), 3) disconnected groups of variables will not contribute to the CCE and 4) the accuracy of the expansion empirically improves upon that of the LS. The CCE is based on the same M{ö}bius transform as the Kikuchi approximation, but unlike GBP does not require storing the beliefs of the GBP-clusters nor does it suffer from convergence issues during belief updating.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR10-welling12a, title = {A Cluster-Cumulant Expansion at the Fixed Points of Belief Propagation}, author = {Welling, Max and Gelfand, Andrew E. and Ihler, Alexander T.}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {882--891}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/welling12a/welling12a.pdf}, url = {https://proceedings.mlr.press/r10/welling12a.html}, abstract = {We introduce a new cluster-cumulant expansion (CCE) based on the fixed points of iterative belief propagation (IBP). This expansion is similar in spirit to the loop-series (LS) recently introduced in [1]. However, in contrast to the latter, the CCE enjoys the following important qualities: 1) it is defined for arbitrary state spaces 2) it is easily extended to fixed points of generalized belief propagation (GBP), 3) disconnected groups of variables will not contribute to the CCE and 4) the accuracy of the expansion empirically improves upon that of the LS. The CCE is based on the same M{ö}bius transform as the Kikuchi approximation, but unlike GBP does not require storing the beliefs of the GBP-clusters nor does it suffer from convergence issues during belief updating.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T A Cluster-Cumulant Expansion at the Fixed Points of Belief Propagation %A Max Welling %A Andrew E. Gelfand %A Alexander T. Ihler %B Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2012 %E Nando de Freitas %E Kevin Murphy %F pmlr-vR10-welling12a %I PMLR %P 882--891 %U https://proceedings.mlr.press/r10/welling12a.html %V R10 %X We introduce a new cluster-cumulant expansion (CCE) based on the fixed points of iterative belief propagation (IBP). This expansion is similar in spirit to the loop-series (LS) recently introduced in [1]. However, in contrast to the latter, the CCE enjoys the following important qualities: 1) it is defined for arbitrary state spaces 2) it is easily extended to fixed points of generalized belief propagation (GBP), 3) disconnected groups of variables will not contribute to the CCE and 4) the accuracy of the expansion empirically improves upon that of the LS. The CCE is based on the same M{ö}bius transform as the Kikuchi approximation, but unlike GBP does not require storing the beliefs of the GBP-clusters nor does it suffer from convergence issues during belief updating. %Z Reissued by PMLR on 04 October 2026.
APA
Welling, M., Gelfand, A.E. & Ihler, A.T.. (2012). A Cluster-Cumulant Expansion at the Fixed Points of Belief Propagation. Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R10:882-891 Available from https://proceedings.mlr.press/r10/welling12a.html. Reissued by PMLR on 04 October 2026.

Related Material