Locally Conditioned Belief Propagation

Thomas Geier Ulm University, Felix Richter Ulm University, Susanne Biundo Ulm University
Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, PMLR R13:477-486, 2015.

Abstract

Conditioned Belief Propagation (CBP) is an algorithm for approximate inference in probabilistic graphical models. It works by conditioning on a subset of variables, and solving the remainder using loopy Belief Propagation. Unfortunately, CBP’s runtime scales exponentially in the number of conditioned variables. Locally Conditioned Belief Propagation (LCBP) approximates the results of CBP by treating conditions locally, and in this way avoids the exponential blow-up. We formulate LCBP as a variational optimization problem and derive a set of update equations that can be used to solve it. We show empirically that LCBP delivers results that are close to those obtained from CBP, while the computational cost scales favorably with problem size.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR13-university15i, title = {Locally Conditioned Belief Propagation}, author = {University, Thomas Geier Ulm and University, Felix Richter Ulm and University, Susanne Biundo Ulm}, booktitle = {Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence}, pages = {477--486}, year = {2015}, editor = {Meila, Marina and Heskes, Tom}, volume = {R13}, series = {Proceedings of Machine Learning Research}, month = {12--16 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r13/main/assets/university15i/university15i.pdf}, url = {https://proceedings.mlr.press/r13/university15i.html}, abstract = {Conditioned Belief Propagation (CBP) is an algorithm for approximate inference in probabilistic graphical models. It works by conditioning on a subset of variables, and solving the remainder using loopy Belief Propagation. Unfortunately, CBP’s runtime scales exponentially in the number of conditioned variables. Locally Conditioned Belief Propagation (LCBP) approximates the results of CBP by treating conditions locally, and in this way avoids the exponential blow-up. We formulate LCBP as a variational optimization problem and derive a set of update equations that can be used to solve it. We show empirically that LCBP delivers results that are close to those obtained from CBP, while the computational cost scales favorably with problem size.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Locally Conditioned Belief Propagation %A Thomas Geier Ulm University %A Felix Richter Ulm University %A Susanne Biundo Ulm University %B Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2015 %E Marina Meila %E Tom Heskes %F pmlr-vR13-university15i %I PMLR %P 477--486 %U https://proceedings.mlr.press/r13/university15i.html %V R13 %X Conditioned Belief Propagation (CBP) is an algorithm for approximate inference in probabilistic graphical models. It works by conditioning on a subset of variables, and solving the remainder using loopy Belief Propagation. Unfortunately, CBP’s runtime scales exponentially in the number of conditioned variables. Locally Conditioned Belief Propagation (LCBP) approximates the results of CBP by treating conditions locally, and in this way avoids the exponential blow-up. We formulate LCBP as a variational optimization problem and derive a set of update equations that can be used to solve it. We show empirically that LCBP delivers results that are close to those obtained from CBP, while the computational cost scales favorably with problem size. %Z Reissued by PMLR on 04 October 2026.
APA
University, T.G.U., University, F.R.U. & University, S.B.U.. (2015). Locally Conditioned Belief Propagation. Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R13:477-486 Available from https://proceedings.mlr.press/r13/university15i.html. Reissued by PMLR on 04 October 2026.

Related Material