Lifted Relax, Compensate and then Recover: From Approximate to Exact Lifted Probabilistic Inference

Guy Van den Broeck, Arthur Choi, Adnan Darwiche
Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, PMLR R10:129-139, 2012.

Abstract

We propose an approach to lifted approximate inference for first-order probabilistic models, such as Markov logic networks. It is based on performing exact lifted inference in a simplified first-order model, which is found by relaxing first-order constraints, and then compensating for the relaxation. These simplified models can be incrementally improved by carefully recovering constraints that have been relaxed, also at the first-order level. This leads to a spectrum of approximations, with lifted belief propagation on one end, and exact lifted inference on the other. We discuss how relaxation, compensation, and recovery can be performed, all at the firstorder level, and show empirically that our approach substantially improves on the approximations of both propositional solvers and lifted belief propagation.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR10-broeck12a, title = {Lifted Relax, Compensate and then Recover: From Approximate to Exact Lifted Probabilistic Inference}, author = {Broeck, Guy Van den and Choi, Arthur and Darwiche, Adnan}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {129--139}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/broeck12a/broeck12a.pdf}, url = {https://proceedings.mlr.press/r10/broeck12a.html}, abstract = {We propose an approach to lifted approximate inference for first-order probabilistic models, such as Markov logic networks. It is based on performing exact lifted inference in a simplified first-order model, which is found by relaxing first-order constraints, and then compensating for the relaxation. These simplified models can be incrementally improved by carefully recovering constraints that have been relaxed, also at the first-order level. This leads to a spectrum of approximations, with lifted belief propagation on one end, and exact lifted inference on the other. We discuss how relaxation, compensation, and recovery can be performed, all at the firstorder level, and show empirically that our approach substantially improves on the approximations of both propositional solvers and lifted belief propagation.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Lifted Relax, Compensate and then Recover: From Approximate to Exact Lifted Probabilistic Inference %A Guy Van den Broeck %A Arthur Choi %A Adnan Darwiche %B Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2012 %E Nando de Freitas %E Kevin Murphy %F pmlr-vR10-broeck12a %I PMLR %P 129--139 %U https://proceedings.mlr.press/r10/broeck12a.html %V R10 %X We propose an approach to lifted approximate inference for first-order probabilistic models, such as Markov logic networks. It is based on performing exact lifted inference in a simplified first-order model, which is found by relaxing first-order constraints, and then compensating for the relaxation. These simplified models can be incrementally improved by carefully recovering constraints that have been relaxed, also at the first-order level. This leads to a spectrum of approximations, with lifted belief propagation on one end, and exact lifted inference on the other. We discuss how relaxation, compensation, and recovery can be performed, all at the firstorder level, and show empirically that our approach substantially improves on the approximations of both propositional solvers and lifted belief propagation. %Z Reissued by PMLR on 04 October 2026.
APA
Broeck, G.V.d., Choi, A. & Darwiche, A.. (2012). Lifted Relax, Compensate and then Recover: From Approximate to Exact Lifted Probabilistic Inference. Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R10:129-139 Available from https://proceedings.mlr.press/r10/broeck12a.html. Reissued by PMLR on 04 October 2026.

Related Material