Lirias (KU Leuven) · 2011 · 145 citations · 11 references
ComputingComputer ScienceAlgorithmsKnowledge RepresentationLogicAutomated ReasoningDeductive ReasoningFirst-order LogicFirst-order Logic ReasoningKnowledge CompilationLogical InferenceProbabilistic CircuitsProbabilistic LogicPropositional InferencePropositional Knowledge RepresentationPropositional Reasoning
Probabilistic logical languages provide power-ful formalisms for knowledge representation and learning. Yet performing inference in these lan-guages is extremely costly, especially if it is done at the propositional level. Lifted inference algo-rithms, which avoid repeated computation by treat-ing indistinguishable groups of objects as one, help mitigate this cost. Seeking inspiration from logical inference, where lifted inference (e.g., resolution) is commonly performed, we develop a model theo-retic approach to probabilistic lifted inference. Our algorithm compiles a first-order probabilistic the-ory into a first-order deterministic decomposable negation normal form (d-DNNF) circuit. Compi-lation offers the advantage that inference is poly-nomial in the size of the circuit. Furthermore, by borrowing techniques from the knowledge compi-lation literature our algorithm effectively exploits the logical structure (e.g., context-specific indepen-dencies) within the first-order model, which allows more computation to be done at the lifted level. An empirical comparison demonstrates the utility of the proposed approach. 1
11
2002 · 625 citations
Context-Specific Independence in Bayesian Networks
Craig Boutilier, Nir Friedman, Moisés Goldszmidt et al. · arXiv (Cornell University) · 2013 · 557 citations · Full text
First-order probabilistic inference
David Poole · 2003 · 423 citations
AND/OR search spaces for graphical models
Rina Dechter, Robert Mateescu · Artificial Intelligence · 2007 · 242 citations