Approximating the Bethe Partition Function

Adrian Weller Columbia University, Tony Jebara Columbia University
Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, PMLR R12:264-273, 2014.

Abstract

When belief propagation (BP) converges, it does so to a stationary point of the Bethe free en- ergy F, and is often strikingly accurate. How- ever, it may converge only to a local optimum or may not converge at all. An algorithm was recently introduced by Weller and Jebara for at- tractive binary pairwise MRFs which is guaran- teed to return an $\epsilon$-approximation to the global minimum of F in polynomial time provided the maximum degree $\Delta$= O(log n), where n is the number of variables. Here we extend their ap- proach and derive a new method based on an- alyzing first derivatives of F, which leads to much better performance and, for attractive mod- els, yields a fully polynomial-time approxima- tion scheme (FPTAS) without any degree restric- tion. Further, our methods apply to general (non- attractive) models, though with no polynomial time guarantee in this case, demonstrating that approximating log of the Bethe partition func- tion, log ZB = -min F, for a general model to additive $\epsilon$-accuracy may be reduced to a discrete MAP inference problem. This allows the merits of the global Bethe optimum to be tested.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR12-university14h, title = {Approximating the {B}ethe Partition Function}, author = {University, Adrian Weller Columbia and University, Tony Jebara Columbia}, booktitle = {Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence}, pages = {264--273}, year = {2014}, editor = {Zhang, Nevin L. and Tian, Jin}, volume = {R12}, series = {Proceedings of Machine Learning Research}, month = {23--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r12/main/assets/university14h/university14h.pdf}, url = {https://proceedings.mlr.press/r12/university14h.html}, abstract = {When belief propagation (BP) converges, it does so to a stationary point of the Bethe free en- ergy F, and is often strikingly accurate. How- ever, it may converge only to a local optimum or may not converge at all. An algorithm was recently introduced by Weller and Jebara for at- tractive binary pairwise MRFs which is guaran- teed to return an $\epsilon$-approximation to the global minimum of F in polynomial time provided the maximum degree $\Delta$= O(log n), where n is the number of variables. Here we extend their ap- proach and derive a new method based on an- alyzing first derivatives of F, which leads to much better performance and, for attractive mod- els, yields a fully polynomial-time approxima- tion scheme (FPTAS) without any degree restric- tion. Further, our methods apply to general (non- attractive) models, though with no polynomial time guarantee in this case, demonstrating that approximating log of the Bethe partition func- tion, log ZB = -min F, for a general model to additive $\epsilon$-accuracy may be reduced to a discrete MAP inference problem. This allows the merits of the global Bethe optimum to be tested.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Approximating the Bethe Partition Function %A Adrian Weller Columbia University %A Tony Jebara Columbia University %B Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2014 %E Nevin L. Zhang %E Jin Tian %F pmlr-vR12-university14h %I PMLR %P 264--273 %U https://proceedings.mlr.press/r12/university14h.html %V R12 %X When belief propagation (BP) converges, it does so to a stationary point of the Bethe free en- ergy F, and is often strikingly accurate. How- ever, it may converge only to a local optimum or may not converge at all. An algorithm was recently introduced by Weller and Jebara for at- tractive binary pairwise MRFs which is guaran- teed to return an $\epsilon$-approximation to the global minimum of F in polynomial time provided the maximum degree $\Delta$= O(log n), where n is the number of variables. Here we extend their ap- proach and derive a new method based on an- alyzing first derivatives of F, which leads to much better performance and, for attractive mod- els, yields a fully polynomial-time approxima- tion scheme (FPTAS) without any degree restric- tion. Further, our methods apply to general (non- attractive) models, though with no polynomial time guarantee in this case, demonstrating that approximating log of the Bethe partition func- tion, log ZB = -min F, for a general model to additive $\epsilon$-accuracy may be reduced to a discrete MAP inference problem. This allows the merits of the global Bethe optimum to be tested. %Z Reissued by PMLR on 04 October 2026.
APA
University, A.W.C. & University, T.J.C.. (2014). Approximating the Bethe Partition Function. Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R12:264-273 Available from https://proceedings.mlr.press/r12/university14h.html. Reissued by PMLR on 04 October 2026.

Related Material