\section{Related Work}
\label{sec:related}
Symbolic inference based on OSDDs was first proposed by
\citeNS{nampally2015constraint}. The present work expands on it two significant ways: Firstly, the construction of OSDDs is 
driven by tabled evaluation of transformed programs instead of by
abstract resolution. Secondly, we give an exact inference procedure for
probability computation using OSDDs which generalizes the exact inference
procedure with ground explanation graphs.

Probabilistic Constraint Logic Programming \cite{michels2013inference}
extends PLP with constraint logic programming (CLP). It allows the
specification of models with imprecise probabilities. Whereas a world
in PLP denotes a specific assignment of values to random
variables, a world in PCLP can define constraints on random
variables, rather than specific values. Lower and upper bounds are
given on the probability of a query by summing the probabilities of
worlds where query follows and worlds where query is possibly true
respectively. While the way in which ``proof constraints'' of a PCLP
query are obtained is similar to the way in which symbolic derivations are
obtained (i.e., through constraint based evaluation), the inference
techniques employed are completely different with PCLP employing
satisfiability modulo theory (SMT) solvers. \comment{The compairson of PCLP and
our constraint based evaluation is a subject of further study.}

cProbLog extends ProbLog with first-order constraints
\cite{fierens2012constraints}. This gives the ability to express
complex evidence in a succinct form. The semantics and inference are
based on ProbLog. In contrast, our work makes the underlying constraints in
a query explicit and uses the OSDDs to drive inference.

CLP($\mathcal{BN}$) \cite{costa2002clp} extends logic programming with
constraints which encode conditional probability tables. A CLP($\mathcal{BN}$) program defines a
joint distribution on the ground skolem terms. Queries
are answered by performing inference over a corresponding BN.  

There has been a significant interest in the area of lifted inference
as exemplified by the works of
\citeNS{poole2003first}, \citeNS{braz2005lifted} and \citeNS{milch2008lifted}. The main idea of
lifted inference is to treat indistinguishable \emph{instances} of random
variables as one unit and perform inference at the population level.
Lifted inference in the context of PLP has been performed by
converting the problem to parfactor representation~\cite{bellodi2014lifted} or weighted
first-order model counting~\cite{van2011lifted}. Lifted explanation graphs
\cite{nampally2016inference} are a generalization of ground
explanation graphs, which treat instances of random processes in a
symbolic fashion. In contrast, exact inference using OSDDs treats
 \emph{values} of random variables symbolically,
thereby computing probabilities without grounding the random
variables.  Consequently, the method in this paper can be used when instance-based lifting is inapplicable.  Its relationship to more recent liftable classes~\cite{Kazemi:NIPS2016} remains to be explored. 

The use of sampling methods for inference in PLPs has been
widespread.  The evidence has generally been handled by heuristics to
reduce the number of rejected samples
\cite{cussens2000stochastic,moldovan2013mcmc}.  More recently, \citeNS{Nitti:2016} present an algorithm that generalizes the applicability of LW samples by recognizing when valuation of a random variable will lead to query failure.  Our technique propagates constraints imposed by evidence.  With a rich constraint language and a propagation algorithm of sufficient power, the sampler
can generate consistent samples without any rejections.

Adaptive sequential rejection sampling \cite{mansinghka2009exact} is
an algorithm that adapts its proposal distributions to avoid
generating samples which are likely to be rejected. However, it
requires a decomposition of the target distribution, which may not be
available in PLPs. Further, in our work the distribution from which
samples are generated is not adapted. It is an interesting direction
of research to combine adaptivity with the proposed sampling
algorithm.

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "main"
%%% End: