Domain Recursion for Lifted Inference with Existential Quantifiers
  In recent work, we proved that the domain recursion inference rule makes
domain-lifted inference possible on several relational probability models
(RPMs) for which the best known time complexity used to be exponential. We also
identified two classes of RPMs for which inference becomes domain lifted when
using domain recursion. These two classes subsume the largest lifted classes
that were previously known. In this paper, we show that domain recursion can
also be applied to models with existential quantifiers. Currently, all lifted
inference algorithms assume that existential quantifiers have been removed in
pre-processing by Skolemization. We show that besides introducing potentially
inconvenient negative weights, Skolemization may increase the time complexity
of inference. We give two example models where domain recursion can replace
Skolemization, avoids the need for dealing with negative numbers, and reduces
the time complexity of inference. These two examples may be interesting from
three theoretical aspects: 1- they provide a better and deeper understanding of
domain recursion and, in general, (lifted) inference, 2- they may serve as
evidence that there are larger classes of models for which domain recursion can
satisfyingly replace Skolemization, and 3- they may serve as evidence that
better Skolemization techniques exist.
