Lifted Variable Elimination with Arbitrary Constraints

Nima Taghipour; Daan Fierens; Jesse Davis; Hendrik Blockeel

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.

Related Material

Download PDF

@InProceedings{pmlr-v22-taghipour12, title = {Lifted Variable Elimination with Arbitrary Constraints}, author = {Nima Taghipour and Daan Fierens and Jesse Davis and Hendrik Blockeel}, booktitle = {Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics}, pages = {1194--1202}, year = {2012}, editor = {Neil D. Lawrence and Mark Girolami}, 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 = {http://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.} }

%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 %J Proceedings of Machine Learning Research %P 1194--1202 %U http://proceedings.mlr.press %V 22 %W PMLR %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.

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 PY - 2012/03/21 DA - 2012/03/21 ED - Neil D. Lawrence ED - Mark Girolami ID - pmlr-v22-taghipour12 PB - PMLR SP - 1194 DP - PMLR EP - 1202 L1 - http://proceedings.mlr.press/v22/taghipour12/taghipour12.pdf UR - http://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 -

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 PMLR 22:1194-1202