AAAI Publications, Workshops at the Twenty-Eighth AAAI Conference on Artificial Intelligence

Font Size: 
Understanding the Complexity of Lifted Inference and Asymmetric Weighted Model Counting
Eric Gribkoff, Guy Van den Broeck, Dan Suciu

Last modified: 2014-06-18

Abstract


We highlight our work on lifted inference for the asymmetric Weighted First-Order Model Counting problem (WFOMC), which counts the assignments that satisfy a given sentence in first-order logic. This work is at the intersection of probabilistic databases and statistical relational learning. First, we discuss how adding negation can lower the query complexity, and describe the essential element (resolution) necessary to extend a previous algorithm for positive queries to handle queries with negation. Second, we describe our novel dichotomy result for a non-trivial fragment of first-order CNF sentences with negation.Finally, we discuss directions for future work.

Keywords


lifted inference

Full Text: PDF