Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Understanding the Complexity of Lifted Inference and Asymmetric Weighted Model Counting
Eric Gribkoff, Guy Van den Broeck, Dan Suciu
Abstract:
In this paper we study lifted inference for the Weighted First-Order Model Counting prob- lem (WFOMC), which counts the assignments that satisfy a given sentence in first-order logic (FOL); it has applications in Statisti- cal Relational Learning (SRL) and Probabilis- tic Databases (PDB). We present several results. First, we describe a lifted inference algorithm that generalizes prior approaches in SRL and PDB. Second, we provide a novel dichotomy result for a non-trivial fragment of FO CNF sentences, showing that for each sentence the WFOMC problem is either in PTIME or #P- hard in the size of the input domain; we prove that, in the first case our algorithm solves the WFOMC problem in PTIME, and in the second case it fails. Third, we present several proper- ties of the algorithm. Finally, we discuss limi- tations of lifted inference for symmetric proba- bilistic databases (where the weights of ground literals depend only on the relation name, and not on the constants of the domain), and prove the impossibility of a dichotomy result for the complexity of probabilistic inference for the en- tire language FOL.
Keywords:
Pages: 280-289
PS Link:
PDF Link: /papers/14/p280-gribkoff.pdf
BibTex:
@INPROCEEDINGS{Gribkoff14,
AUTHOR = "Eric Gribkoff and Guy Van den Broeck and Dan Suciu",
TITLE = "Understanding the Complexity of Lifted Inference and Asymmetric Weighted Model Counting",
BOOKTITLE = "Proceedings of the Thirtieth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-14)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2014",
PAGES = "280--289"
}


hosted by DSL   •   site info   •   help