Lifted Variable Elimination with Arbitrary Constraints

Nima Taghipour, Daan Fierens, Jesse Davis, Hendrik Blockeel
Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, PMLR 22:1194-1202, 2012.

Abstract

Lifted probabilistic inference algorithms exploit regularities in the structure of graphical models to perform inference more efficiently. More specifically, they identify groups of interchangeable variables and perform inference once for each group, as opposed to once for each variable. The groups are defined by means of constraints, so the flexibility of the grouping is determined by the expressivity of the constraint language. Existing approaches for exact lifted inference rely on (in)equality constraints. We show how inference methods can be generalized to work with arbitrary constraints. This allows them to capture a broader range of symmetries, leading to more opportunities for lifting. We empirically demonstrate that this improves inference efficiency with orders of magnitude, allowing exact inference in cases where until now only approximate inference was feasible.

Cite this Paper

BibTeX
@InProceedings{pmlr-v22-taghipour12, title = {Lifted Variable Elimination with Arbitrary Constraints}, author = {Taghipour, Nima and Fierens, Daan and Davis, Jesse and Blockeel, Hendrik}, booktitle = {Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics}, pages = {1194--1202}, year = {2012}, editor = {Lawrence, Neil D. and Girolami, Mark}, volume = {22}, series = {Proceedings of Machine Learning Research}, address = {La Palma, Canary Islands}, month = {21--23 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v22/taghipour12/taghipour12.pdf}, url = {https://proceedings.mlr.press/v22/taghipour12.html}, abstract = {Lifted probabilistic inference algorithms exploit regularities in the structure of graphical models to perform inference more efficiently. More specifically, they identify groups of interchangeable variables and perform inference once for each group, as opposed to once for each variable. The groups are defined by means of constraints, so the flexibility of the grouping is determined by the expressivity of the constraint language. Existing approaches for exact lifted inference rely on (in)equality constraints. We show how inference methods can be generalized to work with arbitrary constraints. This allows them to capture a broader range of symmetries, leading to more opportunities for lifting. We empirically demonstrate that this improves inference efficiency with orders of magnitude, allowing exact inference in cases where until now only approximate inference was feasible.} }
Endnote
%0 Conference Paper %T Lifted Variable Elimination with Arbitrary Constraints %A Nima Taghipour %A Daan Fierens %A Jesse Davis %A Hendrik Blockeel %B Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2012 %E Neil D. Lawrence %E Mark Girolami %F pmlr-v22-taghipour12 %I PMLR %P 1194--1202 %U https://proceedings.mlr.press/v22/taghipour12.html %V 22 %X Lifted probabilistic inference algorithms exploit regularities in the structure of graphical models to perform inference more efficiently. More specifically, they identify groups of interchangeable variables and perform inference once for each group, as opposed to once for each variable. The groups are defined by means of constraints, so the flexibility of the grouping is determined by the expressivity of the constraint language. Existing approaches for exact lifted inference rely on (in)equality constraints. We show how inference methods can be generalized to work with arbitrary constraints. This allows them to capture a broader range of symmetries, leading to more opportunities for lifting. We empirically demonstrate that this improves inference efficiency with orders of magnitude, allowing exact inference in cases where until now only approximate inference was feasible.
RIS
TY - CPAPER TI - Lifted Variable Elimination with Arbitrary Constraints AU - Nima Taghipour AU - Daan Fierens AU - Jesse Davis AU - Hendrik Blockeel BT - Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics DA - 2012/03/21 ED - Neil D. Lawrence ED - Mark Girolami ID - pmlr-v22-taghipour12 PB - PMLR DP - Proceedings of Machine Learning Research VL - 22 SP - 1194 EP - 1202 L1 - http://proceedings.mlr.press/v22/taghipour12/taghipour12.pdf UR - https://proceedings.mlr.press/v22/taghipour12.html AB - Lifted probabilistic inference algorithms exploit regularities in the structure of graphical models to perform inference more efficiently. More specifically, they identify groups of interchangeable variables and perform inference once for each group, as opposed to once for each variable. The groups are defined by means of constraints, so the flexibility of the grouping is determined by the expressivity of the constraint language. Existing approaches for exact lifted inference rely on (in)equality constraints. We show how inference methods can be generalized to work with arbitrary constraints. This allows them to capture a broader range of symmetries, leading to more opportunities for lifting. We empirically demonstrate that this improves inference efficiency with orders of magnitude, allowing exact inference in cases where until now only approximate inference was feasible. ER -
APA
Taghipour, N., Fierens, D., Davis, J. & Blockeel, H.. (2012). Lifted Variable Elimination with Arbitrary Constraints. Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 22:1194-1202 Available from https://proceedings.mlr.press/v22/taghipour12.html.

Related Material