Constraint Processing in Lifted Probabilistic Inference

Jacek Kisynski, David Poole
Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, PMLR R7:293-302, 2009.

Abstract

First-order probabilistic models combine representational power of first-order logic with graphical models. There is an ongoing effort to design lifted inference algorithms for first-order probabilistic models. We analyze lifted inference from the perspective of constraint processing and, through this viewpoint, we analyze and compare existing approaches and expose their advantages and limitations. Our theoretical results show that the wrong choice of constraint processing method can lead to exponential increase in computational complexity. Our empirical tests confirm the importance of constraint processing in lifted inference. This is the first theoretical and empirical study of constraint processing in lifted inference.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR7-kisynski09a, title = {Constraint Processing in Lifted Probabilistic Inference}, author = {Kisynski, Jacek and Poole, David}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {293--302}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/kisynski09a/kisynski09a.pdf}, url = {https://proceedings.mlr.press/r7/kisynski09a.html}, abstract = {First-order probabilistic models combine representational power of first-order logic with graphical models. There is an ongoing effort to design lifted inference algorithms for first-order probabilistic models. We analyze lifted inference from the perspective of constraint processing and, through this viewpoint, we analyze and compare existing approaches and expose their advantages and limitations. Our theoretical results show that the wrong choice of constraint processing method can lead to exponential increase in computational complexity. Our empirical tests confirm the importance of constraint processing in lifted inference. This is the first theoretical and empirical study of constraint processing in lifted inference.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Constraint Processing in Lifted Probabilistic Inference %A Jacek Kisynski %A David Poole %B Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2009 %E Jeff Bilmes %E Andrew Y. Ng %F pmlr-vR7-kisynski09a %I PMLR %P 293--302 %U https://proceedings.mlr.press/r7/kisynski09a.html %V R7 %X First-order probabilistic models combine representational power of first-order logic with graphical models. There is an ongoing effort to design lifted inference algorithms for first-order probabilistic models. We analyze lifted inference from the perspective of constraint processing and, through this viewpoint, we analyze and compare existing approaches and expose their advantages and limitations. Our theoretical results show that the wrong choice of constraint processing method can lead to exponential increase in computational complexity. Our empirical tests confirm the importance of constraint processing in lifted inference. This is the first theoretical and empirical study of constraint processing in lifted inference. %Z Reissued by PMLR on 04 October 2026.
APA
Kisynski, J. & Poole, D.. (2009). Constraint Processing in Lifted Probabilistic Inference. Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R7:293-302 Available from https://proceedings.mlr.press/r7/kisynski09a.html. Reissued by PMLR on 04 October 2026.

Related Material