Fixing the Bethe Approximation: How Structural Modifications in a Graph Improve Belief Propagation

Harald Leisenberger; Franz Pernkopf; Christian Knoll

Fixing the Bethe Approximation: How Structural Modifications in a Graph Improve Belief Propagation

Harald Leisenberger, Franz Pernkopf, Christian Knoll

Institute of Signal Processing and Speech Communication (4420)

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

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

Original language	English
Title of host publication	Proceedings of the 38th Conference on Uncertainty in Artificial Intelligence (UAI 2022)
Subtitle of host publication	Uncertainty in Artificial Intelligence, 1-5 August 2022, Eindhoven, The Netherlands
Pages	1085–1095
Publication status	Published - 2022
Event	38th Conference on Uncertainty in Artificial Intelligence: UAI 2022 - Eindhoven, Netherlands Duration: 1 Aug 2022 → 5 Aug 2022 https://www.auai.org/uai2022/

Publication series

Name	Proceedings of Machine Learning Research
Volume	180

Conference

Conference	38th Conference on Uncertainty in Artificial Intelligence
Abbreviated title	UAI 2022
Country/Territory	Netherlands
City	Eindhoven
Period	1/08/22 → 5/08/22
Internet address	https://www.auai.org/uai2022/

Fields of Expertise

Information, Communication & Computing

Access to Document

https://proceedings.mlr.press/v180/leisenberger22a/leisenberger22a.pdfLicence: Other

Inference - General Framework for Inference on Graphical Models
Pernkopf, F.
1/10/20 → 30/09/22
Project: Research project

Cite this

Leisenberger, H., Pernkopf, F., & Knoll, C. (2022). Fixing the Bethe Approximation: How Structural Modifications in a Graph Improve Belief Propagation. In Proceedings of the 38th Conference on Uncertainty in Artificial Intelligence (UAI 2022): Uncertainty in Artificial Intelligence, 1-5 August 2022, Eindhoven, The Netherlands (pp. 1085–1095). (Proceedings of Machine Learning Research ; Vol. 180). https://proceedings.mlr.press/v180/leisenberger22a/leisenberger22a.pdf

Fixing the Bethe Approximation: How Structural Modifications in a Graph Improve Belief Propagation. / Leisenberger, Harald ; Pernkopf, Franz ; Knoll, Christian.
Proceedings of the 38th Conference on Uncertainty in Artificial Intelligence (UAI 2022): Uncertainty in Artificial Intelligence, 1-5 August 2022, Eindhoven, The Netherlands. 2022. p. 1085–1095 (Proceedings of Machine Learning Research ; Vol. 180).

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

Leisenberger, H , Pernkopf, F & Knoll, C 2022, Fixing the Bethe Approximation: How Structural Modifications in a Graph Improve Belief Propagation. in Proceedings of the 38th Conference on Uncertainty in Artificial Intelligence (UAI 2022): Uncertainty in Artificial Intelligence, 1-5 August 2022, Eindhoven, The Netherlands. Proceedings of Machine Learning Research , vol. 180, pp. 1085–1095, 38th Conference on Uncertainty in Artificial Intelligence, Eindhoven, Netherlands, 1/08/22. <https://proceedings.mlr.press/v180/leisenberger22a/leisenberger22a.pdf>

Leisenberger H , Pernkopf F , Knoll C. Fixing the Bethe Approximation: How Structural Modifications in a Graph Improve Belief Propagation. In Proceedings of the 38th Conference on Uncertainty in Artificial Intelligence (UAI 2022): Uncertainty in Artificial Intelligence, 1-5 August 2022, Eindhoven, The Netherlands. 2022. p. 1085–1095. (Proceedings of Machine Learning Research ).

Leisenberger, Harald ; Pernkopf, Franz ; Knoll, Christian. / Fixing the Bethe Approximation: How Structural Modifications in a Graph Improve Belief Propagation. Proceedings of the 38th Conference on Uncertainty in Artificial Intelligence (UAI 2022): Uncertainty in Artificial Intelligence, 1-5 August 2022, Eindhoven, The Netherlands. 2022. pp. 1085–1095 (Proceedings of Machine Learning Research ).

@inproceedings{4c02a21343e8444a9610e5c8f3d39533,

title = "Fixing the Bethe Approximation: How Structural Modifications in a Graph Improve Belief Propagation",

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",

author = "Harald Leisenberger and Franz Pernkopf and Christian Knoll",

year = "2022",

language = "English",

series = "Proceedings of Machine Learning Research ",

pages = "1085–1095",

booktitle = "Proceedings of the 38th Conference on Uncertainty in Artificial Intelligence (UAI 2022)",

note = "38th Conference on Uncertainty in Artificial Intelligence : UAI 2022, UAI 2022 ; Conference date: 01-08-2022 Through 05-08-2022",

url = "https://www.auai.org/uai2022/",

}

TY - GEN

T1 - Fixing the Bethe Approximation: How Structural Modifications in a Graph Improve Belief Propagation

AU - Leisenberger, Harald

AU - Pernkopf, Franz

AU - Knoll, Christian

PY - 2022

Y1 - 2022

N2 - 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

AB - 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

M3 - Conference paper

T3 - Proceedings of Machine Learning Research

SP - 1085

EP - 1095

BT - Proceedings of the 38th Conference on Uncertainty in Artificial Intelligence (UAI 2022)

T2 - 38th Conference on Uncertainty in Artificial Intelligence

Y2 - 1 August 2022 through 5 August 2022

ER -

Fixing the Bethe Approximation: How Structural Modifications in a Graph Improve Belief Propagation

Abstract

Publication series

Conference

Fields of Expertise

Access to Document

Projects

Inference - General Framework for Inference on Graphical Models

Cite this