Bisimulation-based Approximate Lifted Inference

Prithviraj Sen, Amol Deshpande, Lise Getoor
Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, PMLR R7:504-513, 2009.

Abstract

There has been a great deal of recent interest in methods for performing lifted inference; however, most of this work assumes that the first-order model is given as input to the system. Here, we describe lifted inference algorithms that determine symmetries and automatically lift the probabilistic model to speedup inference. In particular, we describe approximate lifted inference techniques that allow the user to trade off inference accuracy for computational efficiency by using a handful of tunable parameters, while keeping the error bounded. Our algorithms are closely related to the graph-theoretic concept of bisimulation. We report experiments on both synthetic and real data to show that in the presence of symmetries, run-times for inference can be improved significantly, with approximate lifted inference providing orders of magnitude speedup over ground inference.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR7-sen09a, title = {Bisimulation-based Approximate Lifted Inference}, author = {Sen, Prithviraj and Deshpande, Amol and Getoor, Lise}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {504--513}, 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/sen09a/sen09a.pdf}, url = {https://proceedings.mlr.press/r7/sen09a.html}, abstract = {There has been a great deal of recent interest in methods for performing lifted inference; however, most of this work assumes that the first-order model is given as input to the system. Here, we describe lifted inference algorithms that determine symmetries and automatically lift the probabilistic model to speedup inference. In particular, we describe approximate lifted inference techniques that allow the user to trade off inference accuracy for computational efficiency by using a handful of tunable parameters, while keeping the error bounded. Our algorithms are closely related to the graph-theoretic concept of bisimulation. We report experiments on both synthetic and real data to show that in the presence of symmetries, run-times for inference can be improved significantly, with approximate lifted inference providing orders of magnitude speedup over ground inference.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Bisimulation-based Approximate Lifted Inference %A Prithviraj Sen %A Amol Deshpande %A Lise Getoor %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-sen09a %I PMLR %P 504--513 %U https://proceedings.mlr.press/r7/sen09a.html %V R7 %X There has been a great deal of recent interest in methods for performing lifted inference; however, most of this work assumes that the first-order model is given as input to the system. Here, we describe lifted inference algorithms that determine symmetries and automatically lift the probabilistic model to speedup inference. In particular, we describe approximate lifted inference techniques that allow the user to trade off inference accuracy for computational efficiency by using a handful of tunable parameters, while keeping the error bounded. Our algorithms are closely related to the graph-theoretic concept of bisimulation. We report experiments on both synthetic and real data to show that in the presence of symmetries, run-times for inference can be improved significantly, with approximate lifted inference providing orders of magnitude speedup over ground inference. %Z Reissued by PMLR on 04 October 2026.
APA
Sen, P., Deshpande, A. & Getoor, L.. (2009). Bisimulation-based Approximate Lifted Inference. Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R7:504-513 Available from https://proceedings.mlr.press/r7/sen09a.html. Reissued by PMLR on 04 October 2026.

Related Material