Primal View on Belief Propagation

Tomas Werner
Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, PMLR R8:650-656, 2010.

Abstract

It is known that fixed points of loopy be- lief propagation (BP) correspond to station- ary points of the Bethe variational problem, where we minimize the Bethe free energy subject to normalization and marginalization constraints. Unfortunately, this does not en- tirely explain BP because BP is a dual rather than primal algorithm to solve the Bethe variational problem – beliefs are infeasible before convergence. Thus, we have no bet- ter understanding of BP than as an algo- rithm to seek for a common zero of a system of non-linear functions, not explicitly related to each other. In this theoretical paper, we show that these functions are in fact explic- itly related – they are the partial derivatives of a single function of reparameterizations. That means, BP seeks for a stationary point of a single function, without any constraints. This function has a very natural form: it is a linear combination of local log-partition functions, exactly as the Bethe entropy is the same linear combination of local entropies.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR8-werner10a, title = {Primal View on Belief Propagation}, author = {Werner, Tomas}, booktitle = {Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence}, pages = {650--656}, year = {2010}, editor = {Grünwald, Peter and Spirtes, Peter}, volume = {R8}, series = {Proceedings of Machine Learning Research}, month = {08--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r8/main/assets/werner10a/werner10a.pdf}, url = {https://proceedings.mlr.press/r8/werner10a.html}, abstract = {It is known that fixed points of loopy be- lief propagation (BP) correspond to station- ary points of the Bethe variational problem, where we minimize the Bethe free energy subject to normalization and marginalization constraints. Unfortunately, this does not en- tirely explain BP because BP is a dual rather than primal algorithm to solve the Bethe variational problem – beliefs are infeasible before convergence. Thus, we have no bet- ter understanding of BP than as an algo- rithm to seek for a common zero of a system of non-linear functions, not explicitly related to each other. In this theoretical paper, we show that these functions are in fact explic- itly related – they are the partial derivatives of a single function of reparameterizations. That means, BP seeks for a stationary point of a single function, without any constraints. This function has a very natural form: it is a linear combination of local log-partition functions, exactly as the Bethe entropy is the same linear combination of local entropies.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Primal View on Belief Propagation %A Tomas Werner %B Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2010 %E Peter Grünwald %E Peter Spirtes %F pmlr-vR8-werner10a %I PMLR %P 650--656 %U https://proceedings.mlr.press/r8/werner10a.html %V R8 %X It is known that fixed points of loopy be- lief propagation (BP) correspond to station- ary points of the Bethe variational problem, where we minimize the Bethe free energy subject to normalization and marginalization constraints. Unfortunately, this does not en- tirely explain BP because BP is a dual rather than primal algorithm to solve the Bethe variational problem – beliefs are infeasible before convergence. Thus, we have no bet- ter understanding of BP than as an algo- rithm to seek for a common zero of a system of non-linear functions, not explicitly related to each other. In this theoretical paper, we show that these functions are in fact explic- itly related – they are the partial derivatives of a single function of reparameterizations. That means, BP seeks for a stationary point of a single function, without any constraints. This function has a very natural form: it is a linear combination of local log-partition functions, exactly as the Bethe entropy is the same linear combination of local entropies. %Z Reissued by PMLR on 04 October 2026.
APA
Werner, T.. (2010). Primal View on Belief Propagation. Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R8:650-656 Available from https://proceedings.mlr.press/r8/werner10a.html. Reissued by PMLR on 04 October 2026.

Related Material