Workshop on Probabilistic Logic Programming (PLP) location:Vienna, Austria date:17 July 2014
First-order model counting emerged recently as a novel rea-
soning task, at the core of efficient algorithms for probabilistic logics such
as MLNs. 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 expo-
nential time. However, these guarantees apply only to Skolem normal
form theories (i.e., no existential quantifiers). Since textbook Skolemiza-
tion 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. Recently, we presented a novel
Skolemization algorithm for model counting problems that eliminates ex-
istential quantifiers from a first-order logic theory without changing its
weighted model count. Our Skolemization procedure extends the appli-
cability of first-order model counters to probabilistic logic programming.
For the first time, this enables lifted inference with these representations.