|
|
|
|
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"
}
|
|
