Completeness Results for Lifted Variable Elimination

Nima Taghipour, Daan Fierens, Guy Van den Broeck, Jesse Davis, Hendrik Blockeel
Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, PMLR 31:572-580, 2013.

Abstract

Lifting aims at improving the efficiency of probabilistic inference by exploiting symmetries in the model. Various methods for lifted probabilistic inference have been proposed, but our understanding of these methods and the relationships between them is still limited, compared to their propositional counterparts. The only existing theoretical characterization of lifting is a completeness result for weighted first-order model counting. This paper addresses the question whether the same completeness result holds for other lifted inference algorithms. We answer this question positively for lifted variable elimination (LVE). Our proof relies on introducing a novel inference operator for LVE.

Cite this Paper

BibTeX
@InProceedings{pmlr-v31-taghipour13a, title = {Completeness Results for Lifted Variable Elimination}, author = {Taghipour, Nima and Fierens, Daan and Van den Broeck, Guy and Davis, Jesse and Blockeel, Hendrik}, booktitle = {Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics}, pages = {572--580}, year = {2013}, editor = {Carvalho, Carlos M. and Ravikumar, Pradeep}, volume = {31}, series = {Proceedings of Machine Learning Research}, address = {Scottsdale, Arizona, USA}, month = {29 Apr--01 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v31/taghipour13a.pdf}, url = {https://proceedings.mlr.press/v31/taghipour13a.html}, abstract = {Lifting aims at improving the efficiency of probabilistic inference by exploiting symmetries in the model. Various methods for lifted probabilistic inference have been proposed, but our understanding of these methods and the relationships between them is still limited, compared to their propositional counterparts. The only existing theoretical characterization of lifting is a completeness result for weighted first-order model counting. This paper addresses the question whether the same completeness result holds for other lifted inference algorithms. We answer this question positively for lifted variable elimination (LVE). Our proof relies on introducing a novel inference operator for LVE.} }
Endnote
%0 Conference Paper %T Completeness Results for Lifted Variable Elimination %A Nima Taghipour %A Daan Fierens %A Guy Van den Broeck %A Jesse Davis %A Hendrik Blockeel %B Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2013 %E Carlos M. Carvalho %E Pradeep Ravikumar %F pmlr-v31-taghipour13a %I PMLR %P 572--580 %U https://proceedings.mlr.press/v31/taghipour13a.html %V 31 %X Lifting aims at improving the efficiency of probabilistic inference by exploiting symmetries in the model. Various methods for lifted probabilistic inference have been proposed, but our understanding of these methods and the relationships between them is still limited, compared to their propositional counterparts. The only existing theoretical characterization of lifting is a completeness result for weighted first-order model counting. This paper addresses the question whether the same completeness result holds for other lifted inference algorithms. We answer this question positively for lifted variable elimination (LVE). Our proof relies on introducing a novel inference operator for LVE.
RIS
TY - CPAPER TI - Completeness Results for Lifted Variable Elimination AU - Nima Taghipour AU - Daan Fierens AU - Guy Van den Broeck AU - Jesse Davis AU - Hendrik Blockeel BT - Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics DA - 2013/04/29 ED - Carlos M. Carvalho ED - Pradeep Ravikumar ID - pmlr-v31-taghipour13a PB - PMLR DP - Proceedings of Machine Learning Research VL - 31 SP - 572 EP - 580 L1 - http://proceedings.mlr.press/v31/taghipour13a.pdf UR - https://proceedings.mlr.press/v31/taghipour13a.html AB - Lifting aims at improving the efficiency of probabilistic inference by exploiting symmetries in the model. Various methods for lifted probabilistic inference have been proposed, but our understanding of these methods and the relationships between them is still limited, compared to their propositional counterparts. The only existing theoretical characterization of lifting is a completeness result for weighted first-order model counting. This paper addresses the question whether the same completeness result holds for other lifted inference algorithms. We answer this question positively for lifted variable elimination (LVE). Our proof relies on introducing a novel inference operator for LVE. ER -
APA
Taghipour, N., Fierens, D., Van den Broeck, G., Davis, J. & Blockeel, H.. (2013). Completeness Results for Lifted Variable Elimination. Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 31:572-580 Available from https://proceedings.mlr.press/v31/taghipour13a.html.

Related Material