Lifted variable elimination: decoupling the operators from the constraint language

DOI10.1613/JAIR.3793MaRDI QIDQ2838233zbMATH OpenOpenAlexFDO

Authors Nima Taghipour, Daan Fierens, Jesse Davis, Hendrik Blockeel

Publication date 9 July 2013

Published in The Journal of Artificial Intelligence Research (JAIR) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.0565

Mathematics Subject Classification ID

Reasoning under uncertainty in the context of artificial intelligence (68T37)

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 per group, as opposed to once per 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 use specific languages for (in)equality constraints, which often have limited expressivity. In this article, we decouple lifted inference from the constraint language. We define operators for lifted inference in terms of relational algebra operators, so that they operate on the semantic level (the constraints extension) rather than on the syntactic level, making them language-independent. As a result, lifted inference can be performed using more powerful constraint languages, which provide more opportunities for lifting. We empirically demonstrate that this can improve inference efficiency by orders of magnitude, allowing exact inference where until now only approximate inference was feasible.

Recommendations

• Generalized counting for lifted variable elimination
• Lifted variable elimination for probabilistic logic programming
• Inference in probabilistic logic programs using lifted explanations
• Counting and conjunctive queries in the lifted junction tree algorithm
• Lifted Dynamic Junction Tree Algorithm

Cited in

(19)

• Lifted graphical models: a survey
• A survey of lifted inference approaches for probabilistic logic programming under the distribution semantics
• Lifted discriminative learning of probabilistic logic programs
• Generalized counting for lifted variable elimination
• Lower complexity bounds for lifted inference
• Inference in probabilistic logic programs using lifted explanations
• Lifted Dynamic Junction Tree Algorithm
• Explainable and explorable decision support
• Lifted inference for statistical statements in probabilistic answer set programming
• Lifted inference with tree axioms
• Automatic conjecturing of P-recursions using lifted inference
• Towards Preventing Unnecessary Groundings in the Lifted Dynamic Junction Tree Algorithm
• A Priori Approximation of Symmetries in Dynamic Probabilistic Relational Models
• An extended view on lifting Gaussian Bayesian networks
• Lifted algorithms for symmetric weighted first-order model sampling
• Lifting factor graphs with some unknown factors
• Estimating causal effects in partially directed parametric causal factor graphs
• Lifting factor graphs with some unknown factors for new individuals
• PETS: predicting efficiently using temporal symmetries in temporal probabilistic graphical models

This page was built for publication: Lifted variable elimination: decoupling the operators from the constraint language

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2838233)