Skolemization for Weighted First-Order Model Counting

Abstract

First-order model counting emerged recently as a novel reasoning task, at the core of efficient algorithms for probabilistic logics. We present a Skolemization algorithm for model counting problems that eliminates existential quantifiers from a first-order logic theory without changing its weighted model count. For certain subsets of first-order logic, lifted model counters were shown to run in time polynomial in the number of objects in the domain of discourse, where propositional model counters require exponential time. However, these guarantees apply only to Skolem normal form theories (i.e., no existential quantifiers) as the presence of existential quantifiers reduces lifted model counters to propositional ones. Since textbook Skolemization is not sound for model counting, these restrictions precluded efficient model counting for directed models, such as probabilistic logic programs, which rely on existential quantification. Our Skolemization procedure extends the applicability of first-order model counters to these representations. Moreover, it simplifies the design of lifted model counting algorithms.

To appear in Proceedings of the 14th International Conference on Principles of Knowledge Representation and Reasoning (KR), Vienna, Austria, July 2014

References in corpus (3)

• Context-Specific Independence in Bayesian Networks
• Probabilistic Theorem Proving
• Inference in Probabilistic Logic Programs using Weighted CNF's

Cited by in corpus (13)

• Quantum Enhanced Inference in Markov Logic Networks
• Lifted Variable Elimination for Probabilistic Logic Programming
• Understanding the Complexity of Lifted Inference and Asymmetric Weighted Model Counting
• A Dichotomy for the Generalized Model Counting Problem for Unions of Conjunctive Queries
• Symbolic Querying of Vector Spaces: Probabilistic Databases Meets Relational Embeddings
• On the Tractability of SHAP Explanations
• Complex Markov Logic Networks: Expressivity and Liftability
• Lifted Inference in 2-Variable Markov Logic Networks with Function and Cardinality Constraints Using Discrete Fourier Transform
• An epistemic approach to model uncertainty in data-graphs
• Lifted Algorithms for Symmetric Weighted First-Order Model Sampling
• Domain-Liftability of Relational Marginal Polytopes
• Weighted Model Counting in the two variable fragment with Cardinality Constraints: A Closed Form Formula
• Lifted Inference beyond First-Order Logic