Understanding the Bethe approximation: when and how can it go wrong?

Adrian Weller Columbia University, Kui Tang Columbia University, Tony Jebara Columbia University, David Sontag New York University
Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, PMLR R12:274-283, 2014.

Abstract

Belief propagation is a remarkably effective tool for inference, even when applied to networks with cycles. It may be viewed as a way to seek the minimum of the Bethe free energy, though with no convergence guarantee in general. A variational perspective shows that, compared to exact inference, this minimization employs two forms of approximation: (i) the true entropy is approximated by the Bethe entropy, and (ii) the minimization is performed over a relaxation of the marginal polytope termed the local polytope. Here we explore when and how the Bethe ap- proximation can fail for binary pairwise models by examining each aspect of the approximation, deriving results both analytically and with new experimental methods.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR12-university14i, title = {Understanding the {B}ethe approximation: when and how can it go wrong?}, author = {University, Adrian Weller Columbia and University, Kui Tang Columbia and University, Tony Jebara Columbia and University, David Sontag New York}, booktitle = {Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence}, pages = {274--283}, 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/university14i/university14i.pdf}, url = {https://proceedings.mlr.press/r12/university14i.html}, abstract = {Belief propagation is a remarkably effective tool for inference, even when applied to networks with cycles. It may be viewed as a way to seek the minimum of the Bethe free energy, though with no convergence guarantee in general. A variational perspective shows that, compared to exact inference, this minimization employs two forms of approximation: (i) the true entropy is approximated by the Bethe entropy, and (ii) the minimization is performed over a relaxation of the marginal polytope termed the local polytope. Here we explore when and how the Bethe ap- proximation can fail for binary pairwise models by examining each aspect of the approximation, deriving results both analytically and with new experimental methods.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Understanding the Bethe approximation: when and how can it go wrong? %A Adrian Weller Columbia University %A Kui Tang Columbia University %A Tony Jebara Columbia University %A David Sontag New York 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-university14i %I PMLR %P 274--283 %U https://proceedings.mlr.press/r12/university14i.html %V R12 %X Belief propagation is a remarkably effective tool for inference, even when applied to networks with cycles. It may be viewed as a way to seek the minimum of the Bethe free energy, though with no convergence guarantee in general. A variational perspective shows that, compared to exact inference, this minimization employs two forms of approximation: (i) the true entropy is approximated by the Bethe entropy, and (ii) the minimization is performed over a relaxation of the marginal polytope termed the local polytope. Here we explore when and how the Bethe ap- proximation can fail for binary pairwise models by examining each aspect of the approximation, deriving results both analytically and with new experimental methods. %Z Reissued by PMLR on 04 October 2026.
APA
University, A.W.C., University, K.T.C., University, T.J.C. & University, D.S.N.Y.. (2014). Understanding the Bethe approximation: when and how can it go wrong?. Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R12:274-283 Available from https://proceedings.mlr.press/r12/university14i.html. Reissued by PMLR on 04 October 2026.

Related Material