Fixing the Bethe approximation: How structural modifications in a graph improve belief propagation

Harald Leisenberger, Franz Pernkopf, Christian Knoll
Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence, PMLR 180:1085-1095, 2022.

Abstract

Belief propagation is an iterative method for inference in probabilistic graphical models. Its well-known relationship to a classical concept from statistical physics, the Bethe free energy, puts it on a solid theoretical foundation. If belief propagation fails to approximate the marginals, then this is often due to a failure of the Bethe approximation. In this work, we show how modifications in a graphical model can be a great remedy for fixing the Bethe approximation. Specifically, we analyze how the removal of edges influences and improves belief propagation, and demonstrate that this positive effect is particularly distinct for dense graphs.

Cite this Paper

BibTeX
@InProceedings{pmlr-v180-leisenberger22a, title = {Fixing the Bethe approximation: How structural modifications in a graph improve belief propagation}, author = {Leisenberger, Harald and Pernkopf, Franz and Knoll, Christian}, booktitle = {Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence}, pages = {1085--1095}, year = {2022}, editor = {Cussens, James and Zhang, Kun}, volume = {180}, series = {Proceedings of Machine Learning Research}, month = {01--05 Aug}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v180/leisenberger22a/leisenberger22a.pdf}, url = {https://proceedings.mlr.press/v180/leisenberger22a.html}, abstract = {Belief propagation is an iterative method for inference in probabilistic graphical models. Its well-known relationship to a classical concept from statistical physics, the Bethe free energy, puts it on a solid theoretical foundation. If belief propagation fails to approximate the marginals, then this is often due to a failure of the Bethe approximation. In this work, we show how modifications in a graphical model can be a great remedy for fixing the Bethe approximation. Specifically, we analyze how the removal of edges influences and improves belief propagation, and demonstrate that this positive effect is particularly distinct for dense graphs.} }
Endnote
%0 Conference Paper %T Fixing the Bethe approximation: How structural modifications in a graph improve belief propagation %A Harald Leisenberger %A Franz Pernkopf %A Christian Knoll %B Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2022 %E James Cussens %E Kun Zhang %F pmlr-v180-leisenberger22a %I PMLR %P 1085--1095 %U https://proceedings.mlr.press/v180/leisenberger22a.html %V 180 %X Belief propagation is an iterative method for inference in probabilistic graphical models. Its well-known relationship to a classical concept from statistical physics, the Bethe free energy, puts it on a solid theoretical foundation. If belief propagation fails to approximate the marginals, then this is often due to a failure of the Bethe approximation. In this work, we show how modifications in a graphical model can be a great remedy for fixing the Bethe approximation. Specifically, we analyze how the removal of edges influences and improves belief propagation, and demonstrate that this positive effect is particularly distinct for dense graphs.
APA
Leisenberger, H., Pernkopf, F. & Knoll, C.. (2022). Fixing the Bethe approximation: How structural modifications in a graph improve belief propagation. Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 180:1085-1095 Available from https://proceedings.mlr.press/v180/leisenberger22a.html.

Related Material