Convergence behavior of belief propagation: estimating regions of attraction via Lyapunov functions

Harald Leisenberger, Christian Knoll, Richard Seeber, Franz Pernkopf
Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, PMLR 161:1863-1873, 2021.

Abstract

In this work, we estimate the regions of attraction for belief propagation. This extends existing stability analysis and provides initial message values for which belief propagation is guaranteed to converge. Our approach utilizes the theory of Lyapunov functions that, however, does not readily yield useful regions of attraction. Therefore, we utilize polynomial sum-of-squares relaxations and provide an algorithm that computes valid Lyapunov functions. This admits a novel way of studying the solution space of belief propagation. Finally, we apply our approach to small-scale models and discuss the effect of the potentials on the regions of attraction.

Cite this Paper

BibTeX
@InProceedings{pmlr-v161-leisenberger21a, title = {Convergence behavior of belief propagation: estimating regions of attraction via Lyapunov functions}, author = {Leisenberger, Harald and Knoll, Christian and Seeber, Richard and Pernkopf, Franz}, booktitle = {Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence}, pages = {1863--1873}, year = {2021}, editor = {de Campos, Cassio and Maathuis, Marloes H.}, volume = {161}, series = {Proceedings of Machine Learning Research}, month = {27--30 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v161/leisenberger21a/leisenberger21a.pdf}, url = {https://proceedings.mlr.press/v161/leisenberger21a.html}, abstract = {In this work, we estimate the regions of attraction for belief propagation. This extends existing stability analysis and provides initial message values for which belief propagation is guaranteed to converge. Our approach utilizes the theory of Lyapunov functions that, however, does not readily yield useful regions of attraction. Therefore, we utilize polynomial sum-of-squares relaxations and provide an algorithm that computes valid Lyapunov functions. This admits a novel way of studying the solution space of belief propagation. Finally, we apply our approach to small-scale models and discuss the effect of the potentials on the regions of attraction.} }
Endnote
%0 Conference Paper %T Convergence behavior of belief propagation: estimating regions of attraction via Lyapunov functions %A Harald Leisenberger %A Christian Knoll %A Richard Seeber %A Franz Pernkopf %B Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2021 %E Cassio de Campos %E Marloes H. Maathuis %F pmlr-v161-leisenberger21a %I PMLR %P 1863--1873 %U https://proceedings.mlr.press/v161/leisenberger21a.html %V 161 %X In this work, we estimate the regions of attraction for belief propagation. This extends existing stability analysis and provides initial message values for which belief propagation is guaranteed to converge. Our approach utilizes the theory of Lyapunov functions that, however, does not readily yield useful regions of attraction. Therefore, we utilize polynomial sum-of-squares relaxations and provide an algorithm that computes valid Lyapunov functions. This admits a novel way of studying the solution space of belief propagation. Finally, we apply our approach to small-scale models and discuss the effect of the potentials on the regions of attraction.
APA
Leisenberger, H., Knoll, C., Seeber, R. & Pernkopf, F.. (2021). Convergence behavior of belief propagation: estimating regions of attraction via Lyapunov functions. Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 161:1863-1873 Available from https://proceedings.mlr.press/v161/leisenberger21a.html.

Related Material