# First-Order Context-Specific Likelihood Weighting in Hybrid Probabilistic
Logic Programs

Nitesh Kumar<EMAIL_ADDRESS>
Department of Computer Science,
KU Leuven, Belgium Ondřej Kuželka<EMAIL_ADDRESS>
Faculty of Electrical Engineering,
Czech Technical University in Prague, Czech Republic Luc De Raedt
<EMAIL_ADDRESS>
Department of Computer Science,
KU Leuven, Belgium

###### Abstract

Statistical relational AI and probabilistic logic programming have so far
mostly focused on discrete probabilistic models. The reasons for this is that
one needs to provide constructs to succinctly model the independencies in such
models, and also provide efficient inference.

Three types of independencies are important to represent and exploit for
scalable inference in hybrid models: conditional independencies elegantly
modeled in Bayesian networks, context-specific independencies naturally
represented by logical rules, and independencies amongst attributes of related
objects in relational models succinctly expressed by combining rules.

This paper introduces a hybrid probabilistic logic programming language, DC#,
which integrates distributional clauses’ syntax and semantics principles of
Bayesian logic programs. It represents the three types of independencies
qualitatively. More importantly, we also introduce the scalable inference
algorithm FO-CS-LW for DC#. FO-CS-LW is a first-order extension of the
context-specific likelihood weighting algorithm (CS-LW), a novel sampling
method that exploits conditional independencies and context-specific
independencies in ground models. The FO-CS-LW algorithm upgrades CS-LW with
unification and combining rules to the first-order case.

Under consideration for publication in the journal of artificial intelligence
research.

##  1 Introduction

Statistical relational AI (StarAI) and probabilistic logic programming (PLP)
(?, ?) have contributed many languages for declaratively modeling expressive
probabilistic models and have devised numerous inference techniques. They have
been applied to many applications in databases, knowledge graphs, social
networks, robotics, chemical compounds, genomics, etc.

To enable scalable probabilistic inference, it is essential to represent three
different types of independencies in the modeling language. Firstly, the
traditional classical conditional independencies (CIs) represented by Bayesian
networks (BNs). Secondly, the context-specific independencies (CSIs):
independencies that hold only in certain contexts (?). These independencies
arise due to structures present in conditional probability distributions
(CPDs) of BNs, which BNs do not qualitatively represent, but rule-based
representations do by making structures explicit in the clauses (?). Thirdly,
the combining rules such as NoisyOR to express probabilistic influences among
attributes of related objects (?, ?). Combining rules are particularly
interesting since they allow one to qualitatively represent independence of
causal influences (?, ICIs), where each influence is considered independent of
others. This independence is natural and commonly assumed to keep relational
models succinct (?). In probabilistic logic programs that deal with only
discrete random variables, combining rules are the core component (?, ?).

Over the past few decades, many PLP languages have been proposed; however,
only a few of them are hybrid, i.e., support both discrete and continuous
random variables. Nevertheless, such hybrid PLP are needed to cope with
applications in areas such as activity recognition, robotics, sensing,
perception, etc. Current hybrid PLP languages suffer from two problems. First,
they generally do not support combining rules (?, ?, ?, ?, ?). Secondly, and
more importantly, there exist, to the best of our knowledge, no inference
techniques that exploit all three types of independencies for hybrid PLPs.

To remedy this, we first introduce DC# (pronounced “DC sharp”), a hybrid PLP
language that supports combining rules. DC# uses a special form of clauses
called distributional clauses (DCs) to express probabilistic knowledge. We
borrow the syntax of DCs from (?) but introduce an extended new semantics
based on Bayesian Logic Programs (?, BLPs). Thus, in terms of representation,
DC#, a rule-based representation, differs from graphical model-based
relational representations, such as BLPs, which are associated with CPDs.
However, the semantics of DC# are based on BLPs, so DC# programs can be seen
as BLPs qualitatively representing CSIs.

Our second contribution is the first-order context-specific likelihood
weighting (FO-CS-LW) algorithm that exploits these three types of
independencies for scalable inference in DC# programs. Before going to the
first-order case, we introduce the CS-LW algorithm for ground programs. CS-LW
exploits both CIs and CSIs, which is an approximate inference algorithm that,
until our earlier work, has not been well-studied yet (?).

There exist state-of-the-art inference algorithms for exact inference (?) in
discrete models. These algorithms are based on the knowledge compilation
technique (?) that uses logical reasoning to exploit CSIs. However, for many
models, exact inference quickly becomes infeasible. Stochastic sampling for
approximate inference is a standard solution. Sampling algorithms are simple
yet powerful tools, and they can be applied to arbitrary complex hybrid
models, unlike exact inference. It is widely believed that CSI properties in
distributions are difficult to exploit for approximate inference (?). To solve
this difficult problem, we introduce the context-specific likelihood weighting
(CS-LW), a sampling algorithm that exploits both CI and CSI properties,
leading to faster convergence and faster sampling speed than standard
likelihood weighting (LW).

Next, we extend CS-LW to first-order DC# programs specifying relational
probabilistic models. Due to the use of combining rules, such models, when
grounded, have many symmetrically repeated parameters. Inference algorithms
designed for grounded models can not exploit these symmetries, rendering
inference infeasible even for very simple relational models. It is widely
believed that the inference can be feasible if one does not ground out these
models, but reason at the first-order level with unification (?). There have
been several attempts at doing this for various simple languages (?, ?, ?, ?),
but not for hybrid and expressive languages like DC#. For example, well-known
graphical model-based relational representation languages that do not
qualitatively represent CSIs, construct ground BNs for inference (?, ?).
Similarly, well-known PLP systems, which do represent CSIs qualitatively,
first ground the first-order programs and then perform inference at the ground
level (?). In contrast, first-order context-specific likelihood weighting (FO-
CS-LW) reasons at the first-order level. Using the tools of logic, i.e.,
unification, substitution, and resolution, FO-CS-LW samples only relevant
variables from first-order DC# programs determined by various forms of
independencies present in the programs. We empirically demonstrate that FO-CS-
LW scales with domain size and provide an open-source implementation of our
framework111The code is publicly available: https://github.com/niteshroyal/DC-
Sharp.

This paper is a significantly extended and completed version of our previous
paper (?), where we introduced CS-LW to exploit the structures present in CPDs
of BNs. The present paper first introduces a language to describe first-order
probabilistic models and then extends CS-LW to the first-order case.

##### Contribution

We summarise our contributions in this paper as follows:

  * •

We introduce a new PLP language DC# that supports combining rules to describe
hybrid relational probabilistic models succinctly.

  * •

We present a novel sampling methodology, CS-LW, that exploits both CIs and
CSIs for probabilistic inference in BNs and ground probabilistic logic
programs.

  * •

We present a first-order extension of CS-LW that applies directly to first-
order DC# programs and in additional exploits the symmetries present through
combining rules.

  * •

We empirically show that our inference algorithm scales with the domain size
when applied to hybrid relational probabilistic models described as DC#
programs.

##### Organization

The paper is organized as follows. We start by motivating our discussion with
some examples in Section 2. In Section 3, we review the standard likelihood
weighting and basic concepts of logic programming. Section 4 presents the DC#
language. Section 5 presents the CS-LW algorithm for ground DC# programs
describing BNs, which is then extended to first-order DC# programs in Section
6. We then evaluate our algorithms in Section 7. Before concluding, we finally
touch upon related work and directions for future work.

##  2 Motivating Examples

Let us illustrate, with examples, the independencies that DC# programs will
qualitatively represent and that our algorithm will exploit. Consider a BN in
Figure 1(a), where a tree-structure is present in the CPD of variable $E$. If
one observes the CPD carefully, one can conclude that $P(E\mid
A=1,B,C)=P(E\mid A=1)$, that is, $P(E\mid A=1,B,C)$ is the same for all values
of $B$ and $C$. The variable $E$ is said to be independent of variables
$\\{B,C\\}$ in the context $A=1$. This local independence statement
corresponds to the influence of edges $\\{B\rightarrow E,C\rightarrow E\\}$
vanishing in this context; consequently, it may have global implications. For
example, $E\perp B,C\mid A=1$ implies $E\perp D\mid H,A=1$. These
independencies are called CSIs. They arise naturally in various real-world
situations (?), including when one writes if-then conditions in probabilistic
programs (?). Our CS-LW algorithm aims to exploit CSIs arising due to the
structures present within CPDs of BNs when ground DC# programs describe such
BNs.

(a)

(b)

Figure 1: (a) Context-Specific Independence; (b) A Bayesian network with
client and loan plates

The exploitation of CSIs in relational probabilistic models is even more
crucial since a huge amount of CSIs is present in these models. As a simple
example, consider the model in Figure 1(b), where plate notation is used to
represent direct influence relationships among credit scores of $\mathtt{c}$
clients, statuses of $\mathtt{l}$ loans, and $\mathtt{c}\times\mathtt{l}$
number of $\mathtt{has\\_loan}$ type random variables for each client-loan
pair, which can be either true or false. Given that a client has a loan, it is
easy to imagine that the status of the loan may affect the client’s credit
score. On the other hand, if a client has only a few loans, then it is just as
easy to imagine that the status of the loans that the client does not have
will not affect the client’s credit score. That is, the client’s credit is
independent of the status of all those loans that the client does not have.
This is a first-order level CSI, which BNs with plates do not qualitatively
represent. We will introduce a PLP language to represent it.

Furthermore, it is natural to imagine that the client’s credit score depends
on the number of loans that the client has with approved and rejected statuses
but not on the identity of those approved and rejected loans. That is, loans
are exchangeable objects. In such a case, it is common to consider that each
loan’s status independently has its own probabilistic influence on the
client’s credit score, and the final probabilistic influence is a combination
of all these influences (?, ?). This independence assumption implies
exchangeability. Relational models written as DC# programs qualitatively
represent these independencies and first-order level CSIs that our FO-CS-LW
algorithm aims to exploit for scalability.

##  3 Background

A Bayesian network $\mathcal{B}$ is a pair $(\mathcal{G},\mathcal{D})$, where
$\mathcal{G}$ is a directed acyclic graph structure specifying direct
influence relationships among random variables (nodes), and $\mathcal{D}$ is a
set of CPDs associated with each node. The CPD specifies the conditional
probability of the variable given its parents. The graph structure
$\mathcal{G}$ represents local CI statements, which states that each variable
is conditionally independent of its non-descendants given its parents. The
local CIs and the set of CPDs $\mathcal{D}$ together induce a joint
probability distribution $P$ over all the variables.

We denote random variables (RVs) with uppercase letters ($A$) and their
assignments with lowercase letters ($a$). Bold letters denote sets of RVs
($\mathbf{A}$) and their assignments ($\mathbf{a}$). Parents of the variable
$A$ are denoted with $\mathbf{Pa}(A)$ and their assignments with
$\mathbf{pa}(A)$. Suppose $P$ is a probability distribution over disjoint sets
of variables $\mathbf{E},\mathbf{X},\mathbf{Z}$, then $\mathbf{E}$ denotes a
set of observed variables, $\mathbf{X}$ a set of unobserved query variables
and $\mathbf{Z}$ a set of unobserved variable other than query variables. The
expected value of $A$ relative to a distribution $Q$ is denoted by
$\mathbb{E}_{Q}[A]$.

###  3.1 Likelihood Weighting

Next, we briefly review likelihood weighting (LW), one of the most popular
sampling algorithms for BNs.

A typical query to the distribution $P(\mathbf{E},\mathbf{X},\mathbf{Z})$ is
to compute $P(\mathbf{x}_{q}\mid\mathbf{e})$, that is, the probability of
$\mathbf{X}$ being assigned $\mathbf{x}_{q}$ given that $\mathbf{E}$ is
assigned $\mathbf{e}$. Following Bayes’s rule, we have:

$\displaystyle
P(\mathbf{x}_{q}\mid\mathbf{e})=\frac{P(\mathbf{x}_{q},\mathbf{e})}{P(\mathbf{e})}=\frac{\sum_{\mathbf{x},\mathbf{z}}P(\mathbf{x},\mathbf{z},\mathbf{e})f(\mathbf{x})}{\sum_{\mathbf{x},\mathbf{z}}P(\mathbf{x},\mathbf{z},\mathbf{e})}=\mu,$

where $f(\mathbf{x})$ is an indicator function
$\mathds{1}\\{\mathbf{x}=\mathbf{x}_{q}\\}$, which takes value $1$ when
$\mathbf{x}=\mathbf{x}_{q}$, and $0$ otherwise. We can estimate $\mu$ using LW
if we specify $P$ using a Bayesian network. LW belongs to a family of
importance sampling schemes that are based on the observation,

$\displaystyle\mu=\frac{\sum_{\mathbf{x},\mathbf{z}}Q(\mathbf{x},\mathbf{z},\mathbf{e})f(\mathbf{x})(P(\mathbf{x},\mathbf{z},\mathbf{e})/Q(\mathbf{x},\mathbf{z},\mathbf{e}))}{\sum_{\mathbf{x},\mathbf{z}}Q(\mathbf{x},\mathbf{z},\mathbf{e})(P(\mathbf{x},\mathbf{z},\mathbf{e})/Q(\mathbf{x},\mathbf{z},\mathbf{e}))},$
(1)

where $Q$ is a proposal distribution such that $Q>0$ whenever $P>0$. The
distribution $Q$ is different from $P$ and is used to draw independent
samples. Generally, $Q$ is selected such that the samples can be drawn easily.
In the case of LW, to draw a sample, variables
$X_{i}\in\mathbf{X}\cup\mathbf{Z}$ are assigned values drawn from
$P(X_{i}\mid\mathbf{pa}(X_{i}))$ and variables in $\mathbf{E}$ are assigned
their observed values. These variables are assigned in a topological ordering
relative to the graph structure of $\mathcal{B}$. Thus, the proposal
distribution in the case of LW can be described as follows:

$\begin{aligned}
Q(\mathbf{X},\mathbf{Z},\mathbf{E})=\prod_{X_{i}\in\mathbf{X}\cup\mathbf{Z}}P(X_{i}\mid\mathbf{Pa}(X_{i}))\mid_{\mathbf{E}=\mathbf{e}}\end{aligned}.$

Consequently, it is easy to compute the likelihood ratio
$P(\mathbf{x},\mathbf{z},\mathbf{e})/Q(\mathbf{x},\mathbf{z},\mathbf{e})$ in
Equation 1. All factors in the numerator and denominator of the fraction
cancel out except for $P(x_{i}\mid\mathbf{pa}(X_{i}))$ where
$x_{i}\in\mathbf{e}$. Thus,

$\displaystyle\frac{P(\mathbf{X},\mathbf{Z},\mathbf{e})}{Q(\mathbf{X},\mathbf{Z},\mathbf{e})}=\prod_{x_{i}\in\mathbf{e}}P(x_{i}\mid\mathbf{Pa}(X_{i}))=\prod_{x_{i}\in\mathbf{e}}W_{x_{i}}=W_{\mathbf{e}},$

where $W_{x_{i}}$, which is also a RV, is the weight of evidence $x_{i}$. The
likelihood ratio $W_{\mathbf{e}}$ is the product of all of these weights, and
thus, it is also a RV. Given $M$ independent weighted samples from
$Q(\mathbf{X},\mathbf{Z},\mathbf{E})$, we can estimate the query:

$\displaystyle\hat{\mu}=\frac{\sum_{m=1}^{M}f(\mathbf{x}[m])w_{\mathbf{e}}[m]}{\sum_{m=1}^{M}w_{\mathbf{e}}[m]}.$
(2)

###  3.2 Likelihood Weighting + Bayes-Ball

In the previous section, we used all random variables to estimate $\mu$.
However, due to CIs encoded by the graph structure in a Bayesian network
$\mathcal{B}$, observed states and CPDs of only some variables “might” be
required for computing $\mu$. These variables are called requisite variables.
To get a better estimate of $\mu$, it is recommended to use only these
variables. The standard approach is to first apply the Bayes-ball algorithm
(?) over the graph to obtain a sub-network of requisite variables, then
simulate the sub-network to obtain the weighted samples. An alternative
approach is to use Bayes-ball to simulate the original network $\mathcal{B}$
and focus on only requisite variables to obtain the weighted samples. This
approach is trivial and might already be used by many BN inference tools.
However, it is not described in the literature clearly, so we will describe it
next. It will form the basis of our discussion on CS-LW, where we will also
exploit structures within CPDs of BNs.

Figure 2: The four rules of Bayes-ball algorithm that decide next visits
(indicated using ) based on the direction of the current visit (indicated
using ) and the type of variable. To distinguish observed variables from
unobserved variables, the former type of variables are shaded.

To obtain the samples, we need to traverse the graph in a topological
ordering. The Bayes-ball algorithm, which is linear in the graph’s size, can
be used for it. The advantage of using Bayes-ball is that it also detects CIs;
thus, it traverses only a sub-graph that depends on the query and evidence. We
can also keep assigning unobserved variables, and weighting observed variables
along with traversing the graph. In this way, we assign/weigh only requisite
variables. The Bayes-ball algorithm uses four rules to traverse the graph
(when deterministic variables are absent in $\mathcal{B}$), and marks
variables to avoid repeating the same action. These rules are illustrated in
Figure 2. Next, we discuss these rules and also indicate how to assign/weigh
variables, resulting in a new algorithm that we call Bayes-ball simulation of
BNs. Starting with all query variables scheduled to be visited as if from one
of their children, we apply the following rules until no more variables can be
visited:

  1. 1.

When the visit of an unobserved variable $U\in\mathbf{X}\cup\mathbf{Z}$ is
from a child, and $U$ is not marked on top, then do these in the order: i)
Mark $U$ on top; ii) Visit all its parents; iii) Sample a value $y$ from
$P(U\mid\mathbf{pa}(U))$ and assign $y$ to $U$; iv) If $U$ is not marked on
bottom, then mark $U$ on bottom and visit all its children.

  2. 2.

When the visit of an unobserved variable is from a parent, and the variable is
not marked on bottom, then mark the variable on bottom and visit all its
children.

  3. 3.

When the visit of an observed variable is from a child, then do nothing.

  4. 4.

When the visit of an observed variable $E\in\mathbf{E}$ is from a parent, and
$E$ is not marked on top, then do these in the order: i) Mark $E$ on top; ii)
Visit all its parents; iii) Let $e$ be an observed value of $E$ and let $w$ be
the probability at $e$ according to $P(E\mid\mathbf{pa}(E))$, then the weight
of $E$ is $w$.

The above rules define an order for visiting parents and children so that
variables are assigned/weighted in a topological ordering. Indeed we can
define the order since the original rules for Bayes-ball do not prescribe any
order. The marks record important information, and the following result holds.

######  Lemma 1.

Let $\mathbf{E}_{\star}\subseteq\mathbf{E}$ be marked on top,
$\mathbf{E}_{\smwhitestar}\subseteq\mathbf{E}$ be visited but not marked on
top, and $\mathbf{Z}_{\star}\subseteq\mathbf{Z}$ be marked on top. Then the
query $\mu$ can be computed as follows,

$\displaystyle\mu=\frac{\sum_{\mathbf{x},\mathbf{z}_{\star}}P(\mathbf{x},\mathbf{z}_{\star},\mathbf{e}_{\star}\mid\mathbf{e}_{\smwhitestar})f(\mathbf{x})}{\sum_{\mathbf{x},\mathbf{z}_{\star}}P(\mathbf{x},\mathbf{z}_{\star},\mathbf{e}_{\star}\mid\mathbf{e}_{\smwhitestar})}$
(3)

The proof is straightforward and is present in Appendix A. Now, since
$\mathbf{X},\mathbf{Z}_{\star},\mathbf{E}_{\star},\mathbf{E}_{\smwhitestar}$
are variables of $\mathcal{B}$ and they form a sub-network
$\mathcal{B}_{\star}$ such that variables in $\mathbf{E}_{\smwhitestar}$ do
not have any parent, we can write,

$\displaystyle
P(\mathbf{x},\mathbf{z}_{\star},\mathbf{e}_{\star}\mid\mathbf{e}_{\smwhitestar})=\prod_{u_{i}\in\mathbf{x}\cup\mathbf{z}_{\star}\cup\mathbf{e}_{\star}}P(u_{i}\mid\mathbf{pa}(U_{i}))$

such that $\forall
p\in\mathbf{pa}(U_{i}):p\in\mathbf{x}\cup\mathbf{z}_{\star}\cup\mathbf{e}_{\star}\cup\mathbf{e}_{\smwhitestar}$.
This means the CPDs of some observed variables are not required for computing
$\mu$. Now we define these variables.

######  Definition 1.

The observed variables whose observed states and CPDs might be required to
compute $\mu$ will be called diagnostic evidence.

######  Definition 2.

The observed variables whose observed states, but not their CPDs, might be
required to compute $\mu$ will be called predictive evidence.

Diagnostic evidence (denoted by $\mathbf{e}_{\star}$) is marked on top, while
predictive evidence (denoted by $\mathbf{e}_{\smwhitestar}$) is visited but
not marked on top. The variables $\mathbf{X}$, $\mathbf{Z}_{\star}$,
$\mathbf{E}_{\star}$, $\mathbf{E}_{\smwhitestar}$ will be called requisite
variables.

######  Example 1.

Consider the network of Figure 1(a), and assume that our evidence is
$\\{D=1,F=1,G=0,H=1\\}$, and our query is $\\{E=0\\}$. Suppose we start by
visiting the query variable from its child and apply the four rules of Bayes-
ball. One can easily verify that observed variables $F,G,H$ will be marked on
top; hence $\\{F=1,G=0,H=1\\}$ is diagnostic evidence ($\mathbf{e}_{\star}$).
The observed variable $D$ will only be visited; hence $\\{D=1\\}$ is
predictive evidence ($\mathbf{e}_{\smwhitestar}$). Variables $A,B,C,E$ will be
marked on top and are requisite unobserved variables
($\mathbf{X}\cup\mathbf{Z}_{\star}$).

Now, we can sample from a factor $Q_{\star}$ of $Q$ such that,

$\displaystyle
Q_{\star}(\mathbf{X},\mathbf{Z}_{\star},\mathbf{E}_{\star}\mid\mathbf{E}_{\smwhitestar})=\prod_{X_{i}\in\mathbf{X}\cup\mathbf{Z}_{\star}}P(X_{i}\mid\mathbf{Pa}(X_{i}))\mid_{\mathbf{E}_{\star}=\mathbf{e}_{\star}}$
(4)

When we use Bayes-ball, precisely this factor is considered for sampling.
Starting by first setting $\mathbf{E}_{\smwhitestar}$ to their observed
values, $\mathbf{X}\cup\mathbf{Z}_{\star}$ is assigned and
$\mathbf{e}_{\star}$ is weighted in the topological ordering. Given $M$
weighted samples
$\mathcal{D}_{\star}=\langle\mathbf{x}[1],w_{\mathbf{e}_{\star}}[1]\rangle,\dots,\langle\mathbf{x}[M],w_{\mathbf{e}_{\star}}[M]\rangle$
from $Q_{\star}$, we can estimate:

$\displaystyle\tilde{\mu}=\frac{\sum_{m=1}^{M}f(\mathbf{x}[m])w_{\mathbf{e_{\star}}}[m]}{\sum_{m=1}^{M}w_{\mathbf{e_{\star}}}[m]}.$
(5)

In this way, we sample from a lower-dimensional space; thus, the new estimator
$\tilde{\mu}$ has a lower variance compared to $\hat{\mu}$ due to the Rao-
Blackwell theorem. Consequently, fewer samples are needed to achieve the same
accuracy. Hence, for improved inference, we exploit CIs encoded by the graph
structure in $\mathcal{B}$.

###  3.3 Context-Specific Independence

Next, we formally define the independencies that arise due to the structures
present within CPDs, which were informally discussed in Section 2.

######  Definition 3.

Let $P$ be a probability distribution over variables $\mathbf{U}$, and let
$\mathbf{A},\mathbf{B},\mathbf{C},\mathbf{D}$ be disjoint subsets of
$\mathbf{U}$. The variables $\mathbf{A}$ and $\mathbf{B}$ are independent
given $\mathbf{D}$ and context $\mathbf{c}$ if
$P(\mathbf{A}\mid\mathbf{B},\mathbf{D},\mathbf{c})=P(\mathbf{A}\mid\mathbf{D},\mathbf{c})$
whenever $P(\mathbf{B},\mathbf{D},\mathbf{c})>0$. This is denoted by
$\mathbf{A}\perp\mathbf{B}\mid\mathbf{D},\mathbf{c}$. If $\mathbf{D}$ is empty
then $\mathbf{A}$ and $\mathbf{B}$ are independent given context $\mathbf{c}$,
denoted by $\mathbf{A}\perp\mathbf{B}\mid\mathbf{c}$.

Independence statements of the above form are called context-specific
independencies (CSIs). When $\mathbf{A}$ is independent of $\mathbf{B}$ given
all possible assignments to $\mathbf{C}$ then we have:
$\mathbf{A}\perp\mathbf{B}\mid\mathbf{C}$. The independence statements of this
form are generally referred to as conditional independencies (CIs). Thus, CSI
is a more fine-grained notion than CI. The graphical structure in
$\mathcal{B}$ can only represent CIs. Any CI can be verified in linear time in
the size of the graph. However, verifying any arbitrary CSI has been recently
shown to be coNP-hard (?).

###  3.4 A Bit of Logic Programming

Probabilistic logic programming is a probabilistic characterization of logic
programming. So, before describing our system, in this section, we review
relevant syntactic and semantic notions related to logic programming. More
details can be found in (?).

An atom $\mathtt{p(t_{1},\dots,t_{n})}$ consists of a predicate $\mathtt{p/n}$
of arity $\mathtt{n}$ and terms $\mathtt{t_{1},\dots,t_{n}}$. A term is either
a constant (written in lowercase), a variable (in uppercase), or a structured
term of the form $\mathtt{f(u_{1},\dots,u_{k})}$ where $\mathtt{f}$ is a
functor and the $\mathtt{u_{i}}$ are terms. For example,
$\mathtt{has\\_account(ann,L)}$, $\mathtt{has\\_account(ann,a\\_1)}$ and
$\mathtt{has\\_account(ann,func(A))}$ are atoms and $\mathtt{ann}$,
$\mathtt{L}$, $\mathtt{a\\_1}$ and $\mathtt{func(A)}$ are terms. A literal is
an atom or the negation of an atom. A positive literal is an atom. A negative
literal is the negation of an atom. A clause is a universally quantified
disjunction of literals. A definite clause is a clause which contains exactly
one positive literal and zero or more negative literals. For example,
$\mathtt{\forall(A_{0}\vee\neg A_{1}\vee\dots\vee\neg A_{n})}$ is a definite
clause, where $\mathtt{A_{0},A_{1},\dots,A_{n}}$ are atoms. In logic
programming, one usually writes definite clauses in the implication form
$\mathtt{A_{0}\leftarrow A_{1},\dots,A_{n}}$ (where we omit the universal
quantifiers for ease of writing). Here, the atom $\mathtt{A_{0}}$ is called
head of the clause; and the set of atoms $\mathtt{\\{A_{1},\dots,A_{n}\\}}$ is
called body of the clause. A clause with an empty body is called a fact. A
definite program consists of a finite set of definite clauses.

######  Example 2.

A clause $\mathcal{C}\equiv\mathtt{has\\_loan(C,L)\leftarrow
has\\_account(C,A),account\\_loan(A,L)}$ is a definite clause. Intuitively, it
states that a client $\mathtt{C}$ has a loan $\mathtt{L}$ if $\mathtt{C}$ has
an account $\mathtt{A}$ and $\mathtt{A}$ is associated to the loan
$\mathtt{L}$.

An expression, which can be either a term, an atom or a clause, is ground if
it does not contain any variable. A substitution
$\mathtt{\theta=\\{V_{1}/t_{1},...,V_{m}/t_{m}\\}}$ assigns terms
$\mathtt{t_{i}}$ to variables $\mathtt{V_{i}}$. The element
$\mathtt{V_{i}/t_{i}}$ is a binding for variable $\mathtt{V_{i}}$. Applying
$\mathtt{\theta}$ to an expression $\mathcal{E}$ yields $\mathcal{E}\theta$,
the instance of $\mathcal{E}$, where all occurrences of $\mathtt{V_{i}}$ in
$\mathcal{E}$ are replaced by the corresponding terms $\mathtt{t_{i}}$. A
substitution $\theta$ is a grounding for $\mathcal{E}$ if $\mathcal{E\theta}$
is ground, i.e., contains no variables (when there is no risk of confusion we
drop “for $\mathcal{E}$”).

######  Example 3.

Applying a substitution $\mathtt{\theta=\\{C/ann\\}}$ to the clause
$\mathcal{C}$ from Example 2 yields $\mathcal{C\theta}$ which is
$\mathtt{has\\_loan(ann,L)\leftarrow
has\\_account(ann,A),account\\_loan(A,L)}$.

A substitution $\theta$ unifies two expressions $\mathcal{E}_{1}$ and
$\mathcal{E}_{2}$ if $\mathcal{E}_{1}\theta$ and $\mathcal{E}_{2}\theta$ are
identical (denoted $\mathcal{E}_{1}\theta=\mathcal{E}_{2}\theta$). Such a
substitution is called a unifier. Unifiers may not always exist. If there
exists a unifier for two expressions $\mathcal{E}_{1}$ and $\mathcal{E}_{2}$,
we call such atoms unifiable and we say that $\mathcal{E}_{1}$ and
$\mathcal{E}_{2}$ unify.

######  Example 4.

A substitution $\mathtt{\theta=\\{C/ann,M/l\\_1,L/l\\_1\\}}$ unify atoms
$\mathtt{has\\_loan(ann,L)}$ and $\mathtt{has\\_loan(C,M)}$.

A substitution $\theta$ is said to be more general than a substitution
$\sigma$ iff there exists a substitution $\sigma^{\prime}$ such that
$\sigma=\theta\sigma^{\prime}$. A unifier $\theta$ is said to be a most
general unifier (mgu) of two expressions iff $\theta$ is more general than any
other unifier of the expressions. Expression $\mathcal{E}_{1}$ is a renaming
of $\mathcal{E}_{2}$ if they differ only in the names of variables.

######  Example 5.

Unifiers $\mathtt{\\{C/ann,M/L\\}}$ and $\mathtt{\\{C/ann,L/M\\}}$ are both
most general unifiers of $\mathtt{has\\_loan(ann,L)}$ and
$\mathtt{has\\_loan(C,M)}$. The resulting applications,

$\displaystyle\mathtt{has\\_loan(C,M)\\{C/ann,M/L\\}=has\\_loan(ann,L)}$
$\displaystyle\mathtt{has\\_loan(ann,L)\\{C/ann,L/M\\}=has\\_loan(ann,M)}$

are renamings of each other.

The Herbrand universe of a definite program $\mathcal{P}$, denoted
$U_{\mathcal{P}}$, is the set of all ground terms constructed from functors
and constants appearing in $\mathcal{P}$. The Herbrand base $B_{\mathcal{P}}$
is the set of all ground atoms that can be constructed by using predicates
from $\mathcal{P}$ with ground terms from $U_{\mathcal{P}}$ as arguments.
Subsets of the Herbrand base are called Herbrand interpretations. A Herbrand
interpretation $\mathcal{I}$ is a model of a clause $\mathtt{A_{0}\leftarrow
A_{1},\dots A_{n}}$ iff for all grounding substitutions $\theta$, such that
$\\{\mathtt{A_{1}\theta,\dots,A_{n}\theta}\\}\subseteq\mathcal{I}$, it also
holds that $\mathtt{A_{0}\theta}\in\mathcal{I}$. A Herbrand model of a set of
clauses is a Herbrand interpretation which is a model of every clause in the
set.

The least Herbrand model of a definite program $\mathcal{P}$, denoted
$M_{\mathcal{P}}$, is the intersection of all Herbrand models of
$\mathcal{P}$, i.e., $M_{\mathcal{P}}$ is the set of all ground atoms that are
logical consequences of the program. $M_{\mathcal{P}}$ is unique for definite
programs and can be constructed by repeatedly applying the so-called
$T_{\mathcal{P}}$ operator, which is defined as a function on Herbrand
interpretations of $\mathcal{P}$ as follows:

$T_{\mathcal{P}}(\mathcal{I}):=\\{\mathtt{A_{0}\theta\mid A_{0}\leftarrow
A_{1},\dots,A_{n}}\in\mathcal{P}\wedge\mathtt{\\{A_{1}\theta,\dots,A_{n}\theta\\}}\subseteq\mathcal{I}\\},$

where, $\theta$ are grounding substitutions. Let $\mathcal{I}_{1}$ be the set
of all ground facts in the program. Now, applying the operator on
$\mathcal{I}_{1}$, it is possible to use every ground instance of each clause
to construct new ground atoms from $\mathcal{I}_{1}$. In this way, a new set
$\mathcal{I}_{2}:=T_{\mathcal{P}}(\mathcal{I}_{1})$ is obtained, which can be
used again to construct more ground atoms. The new atoms added to
$\mathcal{I}_{i+1}$ are those which must follow immediately from
$\mathcal{I}_{i}$. It is possible to construct $M_{\mathcal{P}}$ by
recursively applying the operator until a fixpoint is reached
($T_{\mathcal{P}}(M_{\mathcal{P}})=M_{\mathcal{P}}$), i.e., until no more
ground atoms can be constructed.

A query  $\mathtt{Q}$ is of the form $\mathtt{B_{1},\dots,B_{m}}$ where the
$\mathtt{B_{j}}$ are atoms and all variables are understood to be
existentially quantified. Given a definite program $\mathcal{P}$, a correct
answer to the query $\mathtt{Q}$ is a substitution $\theta$ such that
$\mathtt{Q\theta}$ is entailed by $\mathcal{P}$, denoted by
$\mathcal{P}\models\mathtt{Q\theta}$. That is, $\mathtt{Q\theta}$ belongs to
$M_{\mathcal{P}}$. The answer substitution $\theta$ is often computed using
SLD-resolution. Finally, the answer set of $\mathtt{Q}$ is the set of all
correct answer substitutions to $\mathtt{Q}$.

##  4 DC#: A Representation Language for Hybrid Relational Models

This section presents a PLP language DC# for describing hybrid relational
probabilistic models. The syntax of our language is based on the elegant
syntax of distributional clauses (DCs) used by (?). However, we extend its
semantics to support combining rules. The new semantics, however, do not allow
for describing open-universe probabilistic models (OUPMs) (?), which was
possible in the previous system. The semantics supporting both OUPMs and
combining rules is another topic of research. We do not study it in this
paper. The new semantics have been developed along the lines of Bayesian Logic
Programs (BLPs) (?).

###  4.1 Syntax

DC is a natural extension of definite clauses for representing conditional
probability distributions.

######  Definition 4.

A DC is a formula of the form $\mathtt{A_{0}\sim D\leftarrow
A_{1},\dots,A_{n}}$, where $\mathtt{\sim}$ is a special binary predicate used
in infix notation, and $\mathtt{A_{i}}(i>0)$ are atoms. Term $\mathtt{A_{0}}$
is called a random variable term and $\mathtt{D}$ is called a distributional
term.

Intuitively, the clause states that RV $\mathtt{A_{0}\theta}$ is distributed
as $\mathtt{D\theta}$ whenever all $\mathtt{A_{i}\theta}$ are true for a
grounding substitution $\theta$. Here, the ground terms $\mathtt{A_{0}\theta}$
and $\mathtt{D\theta}$ belong to the Herbrand universe.

Ground RV terms are interpreted as RVs. To refer to the values of RV terms, we
use a binary predicate $\cong$, which is used in infix notation for
convenience. A ground atom $\mathtt{A\theta\cong x}$ is defined to be true if
$\mathtt{x}$ is the value of RV (or ground RV term) $\mathtt{A\theta}$.

######  Example 6.

Consider the following clause,

$\mathtt{credit\\_score(C)\sim gaussian(755.5,0.1)\leftarrow
has\\_loan(C,L)\cong true,status(L)\cong appr.}$

Applying a grounding substitution $\mathtt{\\{C/ann,L/l\\_1\\}}$ to the clause
results in defining a RV $\mathtt{credit\\_score(ann)}$ distributed as
$\mathtt{gaussian(755.5,0.1)}$ when RVs $\mathtt{has\\_loan(ann,l\\_1)}$ and
$\mathtt{status(l\\_1)}$ take values $\mathtt{true}$ and $\mathtt{appr}$
(“approved”) respectively; that is, when atoms
$\mathtt{has\\_loan(ann,l\\_1)\cong true}$ and $\mathtt{status(l\\_1)\cong
appr}$ are true.

A DC without body is called a probabilistic fact, for example:

$\mathtt{age(bob)\sim gaussian(40,0.2).}$

This clause states that the age of $\mathtt{bob}$ is normally distributed with
mean $40$ and variance $0.2$. It is also possible to define deterministic
variables that take only one value with probability 1, e.g., to express our
absolute certainty that the age of $\mathtt{bob}$ takes value $40$, we can
write,

$\mathtt{\mathtt{age(bob)\sim val(40).}}$

Hence, it is also possible to write the definite clause $\mathcal{C}$ of
Example 2 as a DC like this:

$\mathtt{\mathtt{has\\_loan(C,L)\sim val(true)\leftarrow
has\\_account(C,A)\cong true,account\\_loan(A,L)\cong true}}$

DC also supports comparing the values of RVs with constants or with values of
other RVs in the ground instance of clauses. This can be done using the binary
infix predicates $\mathtt{==,<,>,\geq,and\leq}$, which are especially useful
while conditioning continuous RVs as illustrated by the following clause:

$\mathtt{credit\\_score(C)\sim gaussian(645.5,0.1)\leftarrow age(C)\cong
X,X<40.}$

This clause specifies the distribution of a client’s credit score when the
client’s age is less than $40$.

A distributional program $\mathbb{P}$ consists of a set of distributional
clauses.

######  Example 7.

The following program describes probabilistic influences among attributes of
clients and related loans. Here, we have used $\mathtt{t}$ as a shorthand for
$\mathtt{true}$, $\mathtt{f}$ for $\mathtt{false}$, $\mathtt{a}$ for approved,
and $\mathtt{d}$ for declined.

$\displaystyle\mathtt{client(ann)\sim val(t).}$
$\displaystyle\mathtt{loan(l\\_1)\sim val(t).}$
$\displaystyle\mathtt{loan(l\\_2)\sim val(t).}$
$\displaystyle\mathtt{has\\_loan(C,L)\sim bernoulli(0.2)\leftarrow
client(C)\cong t,loan(L)\cong t.}$ $\displaystyle\mathtt{status(L)\sim
discrete([0.3:a,0.7:d])\leftarrow loan(L)\cong t.}$
$\displaystyle\mathtt{credit\\_score(C)\sim gaussian(650,15.4)\leftarrow
has\\_loan(C,L)\cong Y,Y==f.}$ $\displaystyle\mathtt{credit\\_score(C)\sim
gaussian(700,10.9)\leftarrow has\\_loan(C,L)\cong t,status(L)\cong X,X==a.}$
$\displaystyle\mathtt{credit\\_score(C)\sim gaussian(600,20.5)\leftarrow
has\\_loan(C,L)\cong t,status(L)\cong X,X==d.}$

Now, we provide the semantics of such a program.

###  4.2 Semantics

First, we specify the form of DCs allowed in our programs.

######  Definition 5.

A DC# program is a finite set of DCs $\mathtt{A_{0}\sim D\leftarrow
A_{1},\dots,A_{n}}$ whose atoms $\mathtt{A_{i}(i>0)}$ are either of the
following form222Even though only two forms of atoms are allowed, one can
still write a deterministic atom $\mathtt{u(t_{1},\dots,t_{n})}$ as in
definite clauses like this: $\mathtt{u(t_{1},\dots,t_{n})\cong true}$. So, by
restricting the form of allowed atoms, we are not losing expressivity. Recall
that a definite clause can be expressed as a DC.:

  1. 1.

$\mathtt{q(t_{1},\dots,t_{k})\cong V}$, where $\mathtt{q(t_{1},\dots,t_{k})}$
is a RV term and $\mathtt{V}$ can either be a variable or a constant belonging
to the domain of the RV. If $\mathtt{V}$ is a variable then it must not appear
in RV terms of the DC.

  2. 2.

$\mathtt{V_{1}\diamond V_{2}}$, where $\mathtt{V_{1},V_{2}}$ can be logical
variables or constants belonging to the corresponding domains of RVs, and
$\diamond$ is a comparison infix predicate that can be either of these:
$==,<,>,\geq,\leq$. The predicates $\diamond$ have the same meaning as they
have in Prolog.

For example, all clauses shown in Section 4.1 are already of this form, and
the program in Example 7 is a DC# program. The reason why logical variables
$\mathtt{V_{i}}$, in the above-stated form (Condition 1), are not allowed to
appear in RV terms is that the existence of RVs is not uncertain in DC#
programs. This is not the case in the following program:

$\displaystyle\mathtt{loan\\_id\sim poisson(10).}$
$\displaystyle\mathtt{status(L)\sim discrete([0.3:a,0.7:d])\leftarrow
loan\\_id\cong L.}$

Here, the first clause models the identity of loans as a Poisson distribution
with a mean of $10$. Thus, $\mathtt{loan\\_id}$ can be any natural number
starting with $0$, and the existence of the statuses of loans, say
$\mathtt{status(12)}$, is uncertain. We disallow writing such open-universe
models in the DC# framework because identifying RVs in such models requires
complicated dynamic analysis of programs. For closed-universes, they can be
identified using simple static analysis, which we describe next.

######  Definition 6.

Let $\mathbb{P}$ be a DC# program. An RV set of the program, denoted
$rv(\mathbb{P})$, is the set of definite clauses obtained by transforming each
clause $\mathtt{A_{0}\sim D\leftarrow A_{1},\dots,A_{n}}\in\mathbb{P}$ as
follows:

  1. 1.

Let $\mathtt{Body}$ be the empty set.

  2. 2.

For each atom $\mathtt{A_{i}(i>0)}$ of the form
$\mathtt{q(t_{1},\dots,t_{k})\cong V}$, an atom
$\mathtt{rv(q(t_{1},\dots,t_{k}))}$ is added to $\mathtt{Body}$.

  3. 3.

A clause $\mathtt{rv(A_{0})\leftarrow Body}$ is added to $rv(\mathbb{P})$.

Notice that we ignore comparison atoms while constructing the RV set since
they do not contain RV terms. They only deal with the values of RVs.

######  Example 8.

The RV set for the program in Example 7 is:

$\displaystyle\mathtt{rv(client(ann)).}$
$\displaystyle\mathtt{rv(loan(l\\_1)).}$
$\displaystyle\mathtt{rv(loan(l\\_2)).}$
$\displaystyle\mathtt{rv(has\\_loan(C,L))\leftarrow
rv(client(C)),rv(loan(L)).}$ $\displaystyle\mathtt{rv(status(L))\leftarrow
rv(loan(L)).}$ $\displaystyle\mathtt{rv(credit\\_score(C))\leftarrow
rv(has\\_loan(C,L)).}$ $\displaystyle\mathtt{rv(credit\\_score(C))\leftarrow
rv(has\\_loan(C,L)),rv(status(L)).}$

Atom $\mathtt{rv(has\\_loan(ann,l\\_1))}$ is in the least Herbrand model of
the above RV set but $\mathtt{rv(has\\_loan(l\\_1,l\\_2))}$ is not. So, term
$\mathtt{has\\_loan(ann,l\\_1)}$ is identified as a RV but the meaningless
term $\mathtt{has\\_loan(l\\_1,l\\_2)}$ is not, even though it belongs to the
Herbrand universe. Recall that a ground instance of a DC defines a RV only
when its body is true. No ground DC defines $\mathtt{has\\_loan(l\\_1,l\\_2)}$
as a RV since term $\mathtt{l\\_1}$ is a loan and not a client. We will show
that the RV set of a program identifies all RVs defined by the program. This
is similar to Bayesian clauses in Bayesian logic programs, where atoms in the
least Herbrand model of Bayesian clauses are RVs over which a probability
distribution is defined (?).

Now, it is possible to ground a DC# program $\mathbb{P}$ given an assignment
$\mathbf{u}$ of RVs. We denote such ground programs by
$ground(\mathbb{P})_{\mathbf{u}}$.

######  Example 9.

Given the following assignment of RVs identified from the RV set (Example 8),

$\displaystyle\mathtt{\mathbf{u}=\mathtt{\\{client(ann)\cong
t,loan(l\\_1)\cong t,loan(l\\_2)\cong t,has\\_loan(ann,l\\_1)\cong t,}}$
$\displaystyle\mathtt{has\\_loan(ann,l\\_2)\cong t,status(l\\_1)\cong
a,status(l\\_2)\cong d,credit\\_score(ann)\cong 601.2\\}},$

the program of Example 7 grounds like this:

$\displaystyle\mathtt{client(ann)\sim val(t).}$
$\displaystyle\mathtt{loan(l\\_1)\sim val(t).}$
$\displaystyle\mathtt{loan(l\\_2)\sim val(t).}$
$\displaystyle\mathtt{has\\_loan(ann,l\\_1)\sim bernoulli(0.2)\leftarrow
client(ann)\cong t,loan(l\\_1)\cong t.}$
$\displaystyle\mathtt{has\\_loan(ann,l\\_2)\sim bernoulli(0.2)\leftarrow
client(ann)\cong t,loan(l\\_2)\cong t.}$
$\displaystyle\mathtt{status(l\\_1)\sim discrete([0.3:a,0.7:d])\leftarrow
loan(l\\_1)\cong t.}$ $\displaystyle\mathtt{status(l\\_2)\sim
discrete([0.3:a,0.7:d])\leftarrow loan(l\\_2)\cong t.}$
$\displaystyle\mathtt{credit\\_score(ann)\sim gaussian(650,15.4)\leftarrow
has\\_loan(ann,l\\_1)\cong t,t==f.}$
$\displaystyle\mathtt{credit\\_score(ann)\sim gaussian(650,15.4)\leftarrow
has\\_loan(ann,l\\_2)\cong t,t==f.}$
$\displaystyle\mathtt{credit\\_score(ann)\sim gaussian(700,10.9)\leftarrow
has\\_loan(ann,l\\_1)\cong t,status(l\\_1)\cong a,a==a.}$
$\displaystyle\mathtt{credit\\_score(ann)\sim gaussian(700,10.9)\leftarrow
has\\_loan(ann,l\\_2)\cong t,status(l\\_2)\cong d,d==a.}$
$\displaystyle\mathtt{credit\\_score(ann)\sim gaussian(600,20.5)\leftarrow
has\\_loan(ann,l\\_1)\cong t,status(l\\_1)\cong a,a==d.}$
$\displaystyle\mathtt{credit\\_score(ann)\sim gaussian(600,20.5)\leftarrow
has\\_loan(ann,l\\_2)\cong t,status(l\\_2)\cong d,d==d.}$

Notice that neither meaningless terms like $\mathtt{has\\_loan(l\\_1,l\\_2)}$
and $\mathtt{status(ann)}$ appear in this ground program, nor atoms like
$\mathtt{has\\_loan(ann,l\\_1)\cong f}$ and $\mathtt{credit\\_score(ann)\cong
599.2}$ appear.

Clearly, the next step is to identify direct influence relationships among RVs
defined by programs.

######  Definition 7.

Let $\mathbb{P}$ be a DC# program, $\mathbf{u}$ be an assignment of RVs, and
$ground(\mathbb{P})_{\mathbf{u}}$ be a ground program constructed given
$\mathbf{u}$. A ground RV term $\mathtt{A}$ directly influences $\mathtt{B}$
if there is clause $\mathtt{B\sim D\leftarrow B_{1},\dots,B_{n}}\in
ground(\mathbb{P})_{\mathbf{u}}$ for some $\mathbf{u}$ such that
$\mathtt{n>0}$, $\mathtt{A}$ is in the body of the clause, and the body is
true with respect to $\mathbf{u}$.

For example, we observe from the ground program of Example 9 that ground RV
terms $\mathtt{has\\_loan(ann,l\\_1)}$, $\mathtt{has\\_loan(ann,l\\_2)}$,
$\mathtt{status(l\\_1)}$, and $\mathtt{status(l\\_2)}$ directly influence
$\mathtt{credit\\_score(ann)}$. These relationships can also be identified
using a simple transformation, but this time of the RV set of $\mathbb{P}$.

######  Definition 8.

Let $rv(\mathbb{P})$ be the RV set of a DC# program $\mathbb{P}$. The
dependency set $dep(\mathbb{P})$ is the union of $rv(\mathbb{P})$ and the set
of definite clauses $pa(\mathbb{P})$ obtained by transforming each clause
$\mathtt{rv(A_{0})\leftarrow rv(A_{1}),\dots,rv(A_{n})}\in rv(\mathbb{P})$
with non empty body as follows:

  * •

For each $\mathtt{rv(A_{i})}$, such that $i>0$, a clause
$\mathtt{pa(A_{0},A_{i})\leftarrow rv(A_{0}),rv(A_{1}),\dots,rv(A_{n})}$ is
added to $pa(\mathbb{P})$.

######  Example 10.

By transforming the RV set constructed in Example 8, we obtain the dependency
set of Example 7 that consists of the RV set and the following extra clauses:

$\displaystyle\mathtt{pa(has\\_loan(C,L),client(C))\leftarrow
rv(has\\_loan(C,L)),rv(client(C)),rv(loan(L)).}$
$\displaystyle\mathtt{pa(has\\_loan(C,L),loan(L))\leftarrow
rv(has\\_loan(C,L)),rv(client(C)),rv(loan(L)).}$
$\displaystyle\mathtt{pa(status(L),loan(L))\leftarrow
rv(status(L)),rv(loan(L)).}$
$\displaystyle\mathtt{pa(credit\\_score(C),has\\_loan(C,L))\leftarrow
rv(credit\\_score(C)),rv(has\\_loan(C,L)).}$
$\displaystyle\mathtt{pa(credit\\_score(C),has\\_loan(C,L))\leftarrow
rv(credit\\_score(C)),rv(has\\_loan(C,L)),rv(status(L)).}$
$\displaystyle\mathtt{pa(credit\\_score(C),status(L))\leftarrow
rv(credit\\_score(C)),rv(has\\_loan(C,L)),rv(status(L)).}$

One can easily infer from the above definite program that
$\mathtt{status(l\\_1)}$ directly influences $\mathtt{credit\\_score(ann)}$
since $\mathtt{pa(credit\\_score(ann),status(l\\_1))}$ is entailed by the
above program. Basically, $\mathtt{pa(A,B)}$ states that the parent of
$\mathtt{A}$ is $\mathtt{B}$. The dependency set is similar to the dependency
graph in BLPs (?). The only difference is that we use definite clauses instead
of graphs to represent direct influences. These clauses can be automatically
constructed from DC# programs using the transformations.

However, it is still unclear how to interpret the clauses, in the ground
programs, which may specify multiple distributions for RVs.

######  Definition 9.

Let $ground(\mathbb{P})_{\mathbf{u}}$ be a ground DC# program constructed
given an assignment $\mathbf{u}$, and let

$\displaystyle\mathtt{A_{0}\sim D_{A_{10}}\leftarrow A_{11},\dots,A_{1n_{1}}}$
$\displaystyle\qquad\qquad\quad\vdots$ $\displaystyle\mathtt{A_{0}\sim
D_{A_{k0}}\leftarrow A_{k1},\dots,A_{kn_{k}}}$

be $k$ clauses for $\mathtt{A_{0}}$ in $ground(\mathbb{P})_{\mathbf{u}}$,
whose bodies are true with respect to $\mathbf{u}$. Then, there is a multiset
of distributions $\mathtt{[D_{A_{10}},\dots,D_{A_{k0}}]}$ specified for
$\mathtt{A_{0}}$ in $ground(\mathbb{P})_{\mathbf{u}}$. If $\mathtt{k>1}$ for
some $\mathtt{A}_{0}$ then we say the clauses in
$ground(\mathbb{P})_{\mathbf{u}}$ are mutually inclusive; otherwise, they are
mutually exclusive.

For example, there are two distributions specified for
$\mathtt{credit\\_score(ann)}$ in the above example since client
$\mathtt{ann}$ has two loans and these loans make the bodies of two clauses
for $\mathtt{credit\\_score(ann)}$ true according to the used assignment of
RVs. This, however, raises several questions: According to which distribution
is the RV distributed? How to describe that multiple loans probabilistically
influence the credit score using DCs?

The standard answer to these questions is to combine multiple distributions
into a single distribution using so-called combining rules (?, ?, ?, ?).
Combining rules are based on the assumption of independence of causal
influence (ICI), where it is assumed that multiple causes on a target variable
can be decomposed into several independent causes whose effects are combined
to yield a final value (?). In terms of the above example, this means that we
can let each loan independently define a distribution for the credit score and
then somehow combine all the defined distributions into a single distribution
using a combining rule $\mathcal{CR}$. The most commonly used combining rules
in relational systems are Mean, and noisy OR (?, ?, ?).

Let $[\mathcal{D}_{1},\dots,\mathcal{D}_{n}]$ be a non-empty multiset of
probability distributions. Then, the mean combining rule is defined as
follows:

$\mathrm{Mean}([\mathcal{D}_{1},\dots,\mathcal{D}_{n}])=\dfrac{1}{m}\sum_{i=1}^{n}\mathcal{D}_{n}$

where the right-hand side of the equation is a mixture of distributions. When
all distributions in the multiset are Bernoulli distributions, denoted
$\mathtt{bernoulli(p_{i})}$, with parameters $\mathtt{p_{i}}$, then generally
noisy OR combining rule is used, which is defined as follows:

$\mathrm{NoisyOR}(\mathtt{[bernoulli(p_{1}),\dots,bernoulli(p_{n})]})=\mathtt{bernoulli}(1-\prod_{i=1}^{n}(1-\mathtt{p_{i}}))$

To specify a proper probability distribution, a DC# program has to be well-
defined.

######  Definition 10.

Let $\mathbb{P}$ be a DC# program, $\mathbf{V}_{\mathbb{P}}$ be the set of all
RVs identified from $rv(\mathbb{P})$, $\omega$ be an assignment of
$\mathbf{V}_{\mathbb{P}}$, and $\Omega$ is the set of all such $\omega$. The
program $\mathbb{P}$ is well-defined if it satisfies the following conditions:

  1. 1.

Exhaustiveness: For all $\mathtt{A_{0}}\in\mathbf{V}_{\mathbb{P}}$ and for all
$\omega\in\Omega$, there is at least one clause of the form $\mathtt{A_{0}\sim
D\leftarrow A_{1},\dots,A_{n}}$ in $ground(\mathbb{P})_{\omega}$ such that the
clause’s body is true with respect to $\omega$.

  2. 2.

Acyclicity: There exists a function $rank(.)$ that maps
$\mathtt{A}\in\mathbf{V}_{\mathbb{P}}$ to natural numbers $\mathbb{N}$. Let
$\mathtt{A_{0}\sim D\leftarrow A_{1},\dots,A_{n}}$ be a clause in
$ground(\mathbb{P})_{\omega}$, and let $\\{\mathtt{rv_{1},\dots rv_{m}}\\}$ be
the set of RV terms in $\\{\mathtt{A_{1},\dots,A_{n}}\\}$. For all $\omega$,
for all clauses in $ground(\mathbb{P})_{\omega}$, and for all $i$,
$rank(\mathtt{A_{0}})>rank(\mathtt{rv_{i}})$.

  3. 3.

Finite Support: The set $\mathbf{V}_{\mathbb{P}}$ is non-empty and each
$\mathtt{A_{0}}\in\mathbf{V}_{\mathbb{P}}$ is influenced by a finite set of
RVs.

These conditions are similar to the conditions imposed on BLPs for them to be
well-defined (?). Since BLPs consist of Bayesian clauses along with CPDs, the
exhaustiveness condition is implicitly imposed. Recall that CPDs define a
conditional probability distribution for an RV given any possible assignment
of the RV’s parents, which means CPDs are exhaustive.

Let us investigate some ill-defined programs.

######  Example 11.

The program

$\mathtt{a(X)\sim bernoulli(0.2)\leftarrow b(X)\cong t.}$

is not well-defined since the least Herbrand model of the RV set of the
program is empty. The program

$\displaystyle\mathtt{s(a,b)\sim val(t).}$ $\displaystyle\mathtt{s(X,f(Y))\sim
val(t)\leftarrow s(X,Y)\cong t.}$ $\displaystyle\mathtt{r(X)\sim
val(t)\leftarrow s(X,f(Y))\cong t.}$

is ill-defined because $\mathtt{r(a)}$ is influenced by infinite number of
RVs: $\mathtt{s(a,b)}$, $\mathtt{s(a,f(b))}$, $\mathtt{s(a,f(f(b)))}$, and so
on. However, the following program

$\displaystyle\mathtt{s(a,b)\sim val(t).}$ $\displaystyle\mathtt{s(X,f(Y))\sim
val(t)\leftarrow s(X,Y)\cong t.}$

is well-defined since each RV is influenced by a finite number of RVs. Such
programs allow for writing models that can have infinite RVs such as hidden
Markov models. The following program violates the exhaustiveness condition.

$\displaystyle\mathtt{a(1)\sim discrete([0.2:t,0.8:f]).}$
$\displaystyle\mathtt{b(1)\sim bernoulli(0.6)\leftarrow a(1)\cong t.}$

This is because the distribution of $\mathtt{b(1)}$ when $\mathtt{a(1)}$ is
$\mathtt{f}$ (“false”) is undefined. The program

$\displaystyle\mathtt{a(1)\sim discrete([0.2:t,0.8:f]).}$
$\displaystyle\mathtt{a(1)\sim discrete([0.1:t,0.9:f])\leftarrow a(1)\cong
t.}$ $\displaystyle\mathtt{a(1)\sim discrete([0.7:t,0.3:f])\leftarrow
a(1)\cong f.}$

is ill-defined as well since it has a cyclic dependency.

We can show that the RV set of a well-defined DC# program identifies all RVs
defined by the program, and the dependency set all direct influences among
RVs.

######  Proposition 2.

Let $rv(\mathbb{P})$ be a RV set of a well-defined DC# program $\mathbb{P}$.
Then, $\mathbb{P}$ defines $\mathtt{A}$ as a RV iff $\mathtt{rv(A)}$ is in the
least Herbrand model of $rv(\mathbb{P})$.

The proofs of all results presented in this paper are in Appendix A.

######  Proposition 3.

Let $dep(\mathbb{P})$ be a dependency set of a well-defined DC# program
$\mathbb{P}$. Then, $\mathtt{A}$ directly influences $\mathtt{B}$ iff
$\mathtt{pa(B,A)}$ is in the least Herbrand model of $dep(\mathbb{P})$.

A possible world is an assignment of all RVs $\mathbf{V}_{\mathbb{P}}$ defined
by a program. Since $\mathbf{V}_{\mathbb{P}}$ can be an infinite set, as
discussed in Example 11, defining how probabilities are assigned to possible
worlds is difficult. However, we can still define how probabilities are
assigned to assignments of a certain subset of RVs.

######  Definition 11.

Let $\mathbf{V}_{\mathbb{P}}$ be the set of all RVs defined by a well-defined
DC# program $\mathbb{P}$, $\mathbf{u}$ be an assignment of a finite subset
$\mathbf{U}\subseteq\mathbf{V}_{\mathbb{P}}$. Denote the set of RVs that
directly influence $X$ by $\mathbf{Pa}(X)$. The assignment $\mathbf{u}$ is
said to be closed under direct influence relationships if $X\in\mathbf{U}$
implies $\mathbf{Pa}(X)\subseteq\mathbf{U}$.

######  Example 12.

Reconsider the DC# program of Example 7. Partial assignment $\mathbf{u}_{1}=$
$\\{\mathtt{client(ann)\cong t,}$ $\mathtt{loan(l\\_1)\cong t,}$
$\mathtt{has\\_loan(ann,l\\_1)\cong f}$ $\\}$ is closed under direct influence
relationships, but partial assignment $\mathbf{u}_{2}=$
$\\{\mathtt{credit\\_score(ann)\cong 651.2,}$ $\mathtt{client(ann)\cong t,}$
$\mathtt{loan(l\\_1)\cong t,}$ $\mathtt{has\\_loan(ann,l\\_1)\cong f}\\}$ is
not closed under such influences. This is because RV term
$\mathtt{has\\_loan(ann,l\\_2)}$ directly influences
$\mathtt{credit\\_score(ann)}$, but is not assigned in $\mathbf{u}_{2}$.

######  Definition 12.

Let $\mathbb{P}$ be a well-defined DC# program, $\mathbf{u}$ be an assignment
that is closed under direct influence relationships, and
$ground(\mathbb{P})_{\mathbf{u}}$ be the ground program constructed given
$\mathbf{u}$. Then the probability (or density) that
$ground(\mathbb{P})_{\mathbf{u}}$ assigns to $\mathbf{u}$ is given by

$P(\mathbf{u})=\prod_{\mathtt{A_{i}\cong
x}\in\mathbf{u}}{\mathcal{CR}([\mathtt{D}_{\mathtt{A_{1i}}},\dots,\mathtt{D}_{\mathtt{A_{ki}}}])}(\mathtt{A_{i}\cong
x})$

where $[\mathtt{D}_{\mathtt{A_{1i}}},\dots,\mathtt{D}_{\mathtt{A_{ki}}}]$ is a
multiset of distributions specified for RV term $\mathtt{A_{i}}$ in
$ground(\mathbb{P})_{\mathbf{u}}$ and
${\mathcal{CR}([\mathtt{D}_{\mathtt{A_{1i}}},\dots,\mathtt{D}_{\mathtt{A_{ki}}}])}(\mathtt{A_{i}\cong
x})$ is the conditional probability density/mass of $\mathtt{A_{i}}$ at
$\mathtt{x}$ according to the combined distribution
${\mathcal{CR}([\mathtt{D}_{\mathtt{A_{1i}}},\dots,\mathtt{D}_{\mathtt{A_{ki}}}])}$
obtained after applying $\mathcal{CR}$ on the multiset.

######  Example 13.

Suppose we use Mean as a combining rule for the program of Example 9. Then, to
compute the probability density given to the assignment in the example, we
will use the following conditional probability densities/masses:

$\mathtt{client(ann)\cong t}$ | $1.00$
---|---
$\mathtt{loan(l\\_1)\cong t}$ | $1.00$
$\mathtt{loan(l\\_2)\cong t}$ | $1.00$
$\mathtt{has\\_loan(ann,l\\_1)\cong t}$ | $0.20$
$\mathtt{has\\_loan(ann,l\\_2)\cong t}$ | $0.20$
$\mathtt{status(l\\_1)\cong a}$ | $0.30$
$\mathtt{status(l\\_2)\cong d}$ | $0.70$
$\mathtt{credit\\_score(ann)\cong 601.2}$ | $0.04$

where, the last entry is the probability density at $\mathtt{601.2}$ according
to the mixture of Gaussians $\\{\mathcal{N}(x\mid 700,10.9)+\mathcal{N}(x\mid
600,20.5)\\}/2$. Thus, the density assigned to the assignment is $0.20\times
0.20\times 0.30\times 0.70\times 0.04$.

We can show that these probability (or density) assignments define a unique
probability distribution.

######  Proposition 4.

Let $\mathbb{P}$ be a well-defined DC# program, and $\mathbf{V}_{\mathbb{P}}$
be a set of all RVs defined by it. Then $\mathbb{P}$ specifies a unique
probability distribution over $\mathbf{V}_{\mathbb{P}}$.

Since well-defined DC# programs satisfy all conditions of well-defined BLPs,
this proposition follows from Proposition 1 of (?)

##  5 Inference in Ground DC# Programs

Before presenting the sampling algorithm for first-order DC# programs, we will
first design an efficient sampling algorithm for ground DC# programs
describing BNs with structured CPDs. Thus, this section will focus only on
programs having mutually exclusive clauses, which are sufficient to describe
such BNs. The algorithm presented in this section aims to exploit structures
within CPDs or the structure of clauses in ground programs. However, in this
section, we will assume that continuous RVs are absent for simplicity. Once
this algorithm is clear, the extended algorithm for first-order DC# programs
presented in the next section will be easy to comprehend.

A natural representation of the structures in CPDs is via tree-CPDs (?), as
illustrated in Figure 1(a). For all assignments to the parents of a variable
$A$, a unique leaf in the tree specifies a (conditional) distribution over
$A$. The path to each leaf dictates the contexts, i.e., partially assigned
parents, given which this distribution is used. We can easily represent tree-
CPDs using DCs, where each path from the root to a leaf in each tree-CPD maps
to a rule.

######  Example 14.

A set of clauses for the tree-CPD in Figure 1(a):

$\mathtt{e\sim bernoulli(0.2)\leftarrow a\cong 1.}$

$\mathtt{e\sim bernoulli(0.9)\leftarrow a\cong 0,b\cong 1.}$

$\mathtt{e\sim bernoulli(0.6)\leftarrow a\cong 0,b\cong 0,c\cong 1.}$

$\mathtt{e\sim bernoulli(0.3)\leftarrow a\cong 0,b\cong 0,c\cong 0.}$

Conversely, we can view a ground program with mutually exclusive clauses as a
representation of tree-CPDs of all variables of a BN. Thus, we can
alternatively define the probability distribution specified by such ground
programs as follows,

######  Definition 13.

Let $\mathcal{B}$ be a Bayesian network with tree-CPDs specifying a
distribution $P$. Let $\mathbb{P}$ be a set of distributional clauses such
that each path from the root to a leaf of each tree-CPD corresponds to a
clause in $\mathbb{P}$. Then $\mathbb{P}$ specifies the same distribution $P$.

To avoid confusion, such ground programs will be called DC($\mathcal{B}$)
programs.

While an efficient sampling algorithm for $\mathcal{B}$ only exploits the
graph structure (CIs properties) in $\mathcal{B}$, the key to designing an
efficient sampling algorithm for DC($\mathcal{B}$) programs is to exploit both
the underlying graph and the clause structure (CSIs properties). To this end,
we start with our discussion on the estimation of unconditional probability
queries, which is necessary to support our further discussion on conditional
probability queries, where we present the full algorithm for DC($\mathcal{B}$)
programs.

###  5.1 Top-Down Proof Procedure for DC($\mathcal{B}$) programs

Estimating unconditional probability queries in BNs is easy. We just need to
generate some random samples of query variables and to find the fraction of
times the query is true, which is the estimated probability of the query. In
this sampling process, all ancestors of query variables are also sampled.
However, due to the clause structure in DC($\mathcal{B}$) programs, it is
possible to generate random samples of query variables by sampling only some
(not all) ancestors, which makes the sampling process more efficient. A
simplified version of an approach due to (?) is discussed in Algorithm 1. This
approach resembles SLD resolution (?) for definite programs. However, there
are some differences due to the stochastic nature of sampling. Unlike SLD
resolution, this approach maintains global variable $\mathtt{Asg}$ to record
sampled values of RVs.

Algorithm 1 DC($\mathcal{B}$) Proof Procedure

procedure prove-ground($\mathtt{G}$)

  * •

Proves a conjunction of ground atoms $\mathtt{G}$.

  * •

Returns $\mathtt{yes}$ if there is a choice that makes $\mathtt{G}$ empty;
otherwise the procedure fails.

  1. 1.

While $\mathtt{G}$ is not empty:

    1. (a)

Select the first atom $\mathtt{A}$ from $\mathtt{G}$.

    2. (b)

If $\mathtt{A}$ is of the form $\mathtt{t\cong v}$:

      1. i.

If a value of $\mathtt{t}$ is recorded in $\mathtt{Asg}$:

        1. A.

If $\mathtt{Asg[t]==v}$: remove $\mathtt{A}$ from $\mathtt{G}$.

      2. ii.

Else:

        1. A.

Choose $\mathtt{t\sim D\leftarrow B_{1},\dots,B_{n}}\in\mathbb{P}$ with
$\mathtt{t}$ in the head.

        2. B.

Set $\mathtt{G:=B_{1},\dots,B_{n},sample(t,D),G}$.

    3. (c)

Else If $\mathtt{A}$ is of the form $\mathtt{sample(t,D)}$:

      1. i.

Sample a value $\mathtt{v}$ from $\mathtt{D}$, record $\mathtt{Asg[t]:=v}$,
and remove $\mathtt{A}$ from $\mathtt{G}$.

  2. 2.

Return $\mathtt{yes}$.

Given an initial goal $\mathtt{G_{0}}$ and global variable $\mathtt{Asg}$, the
algorithm recursively produces new goals $\mathtt{G_{1}}$,$\mathtt{G_{1}}$,
etc., and updates $\mathtt{Asg}$. There are two cases when it is not possible
to obtain $\mathtt{G_{i+1}}$ from $\mathtt{G_{i}}$:

  * •

the first is when the selected subgoal of the form $\mathtt{t\cong v}$ cannot
be resolved because the sampled value of the RV term already recorded in
$\mathtt{Asg}$ is different from $\mathtt{v}$.

  * •

the other case appears when $\mathtt{G_{i}=\square}$ (i.e. the empty goal).

The procedure333Since cyclic dependency among RVs is not allowed in well-
defined programs, and the number of clauses in the program is finite, the
procedure is guaranteed to terminate. results in a derivation of
$\mathtt{G_{0}}$, a finite sequence of goals starting with the initial goal

######  Example 15.

Consider the initial goal ($\mathtt{G_{0}}$) $\mathtt{\leftarrow e\cong 1}$,
which signifies that the probability of $\mathtt{e}$ assigned to $\mathtt{1}$
is asked, and the following DC($\mathcal{B}$) program:

$\mathtt{a\sim bernoulli(0.1).}$

$\mathtt{d\sim bernoulli(0.3).}$

$\mathtt{b\sim bernoulli(0.2)\leftarrow a\cong 0.}$

$\mathtt{b\sim bernoulli(0.6)\leftarrow a\cong 1.}$

$\mathtt{c\sim bernoulli(0.2)\leftarrow a\cong 1.}$

$\mathtt{c\sim bernoulli(0.7)\leftarrow a\cong 0,b\cong 1.}$

$\mathtt{c\sim bernoulli(0.8)\leftarrow a\cong 0,b\cong 0.}$

$\mathtt{e\sim bernoulli(0.9)\leftarrow c\cong 1.}$

$\mathtt{e\sim bernoulli(0.4)\leftarrow c\cong 0,d\cong 1.}$

$\mathtt{e\sim bernoulli(0.3)\leftarrow c\cong 0,d\cong 0.}$

Use $\mathtt{sample(k,l)}$ as a shorthand notation for
$\mathtt{sample(k,bernoulli(l))}$. A derivation of $\mathtt{G_{0}}$ together
with the state of $\mathtt{Asg}$ and the program clause used in each step is
shown below:

As usual, the derivation of goal $\mathtt{G_{0}}$ that ends in the empty goal
corresponds to a refutation of the goal. Not all derivations lead to
refutations. As already pointed out, if the selected subgoal cannot be
resolved, the derivation fails. A refutation or a failed derivation is a
complete derivation. If the selected subgoal of some goal can be resolved with
more than one program clause, there can be many complete derivations. The
procedure searches a refutation by generating multiple complete derivations in
a depth-first search fashion. Notice that, unlike SLD-resolution, here
derivations might depend on previous complete derivations. This is because the
previous derivations might have updated the $\mathtt{Asg}$ table, which in
turn might influence the current derivation. Additionally, it should be clear
that no or only one derivation can be the refutation when clauses in a program
are mutually exclusive. So, for efficiency, one should stop generating more
derivations in such programs once a refutation is obtained.

The fraction of times we get refutation is the estimated probability of the
query. Notice that some ancestors of the query variables may not be sampled on
some occasions, e.g., in Example 15, variables $\mathtt{d}$ and $\mathtt{b}$
were not sampled. Thus, we speed up the sampling process and, in this way,
exploit the structure of clauses while estimating marginal probabilities.

###  5.2 Exploiting Context-Specific Independencies

We now turn our attention to the problem of estimating conditional
probabilities, which is more interesting but is significantly more
complicated. This problem is not well studied in (?). Here we introduce a
sampling algorithm that combines the proof procedure, discussed in the
previous section, with the Bayes-ball simulation, discussed in Section 3.2.
The combined algorithm then exploits both the clause structures and the
underlying graph structure of DC($\mathcal{B}$) programs. As we will see, it
samples variables given the states of only some of their requisite ancestors.
This contrasts with the Bayes-ball simulation of BNs, where knowledge of all
such ancestors’ states is required. This section is divided into two parts.
The first part presents a novel notion of contextual assignment that allows
for exploiting CSIs. It provides insight into the computation of $\mu$ using
partial assignments of requisite variables. We will show that CSIs allow for
breaking the main problem of computing $\mu$ into several sub-problems that
can be solved independently. The second part presents the sampling algorithm
and justifies it using the notion introduced in the first part.

####  5.2.1 Notion of Contextual Assignment

Recall from Section 3.2 that variables $\mathbf{X}$, $\mathbf{Z}_{\star}$,
$\mathbf{E}_{\star}$, $\mathbf{E}_{\smwhitestar}$ are requisite for computing
the query $\mu$ and the requisite network $\mathcal{B}_{\star}$ is formed by
these variables. We will consider partial assignments of these variables,
which will be used to compute $\mu$. Let us start by defining these
assignments.

######  Definition 14.

Let $\mathbf{Z}_{\dagger}\subseteq\mathbf{Z}_{\star}$ and
$\mathbf{e}_{\dagger}\subseteq\mathbf{e}_{\star}$. Denote
$\mathbf{Z}_{\star}\setminus\mathbf{Z}_{\dagger}$ by $\mathbf{Z}_{\ddagger}$,
and $\mathbf{e}_{\star}\setminus\mathbf{e}_{\dagger}$ by
$\mathbf{e}_{\ddagger}$. A partial assignment $\mathbf{x}$,
$\mathbf{z}_{\dagger}$, $\mathbf{Z}_{\ddagger}$, $\mathbf{e}_{\dagger}$,
$\mathbf{e}_{\ddagger}$ will be called contextual assignment if due to CSIs in
$P$,

$\prod_{u_{i}\in\mathbf{x}\cup\mathbf{z}_{\dagger}\cup\mathbf{e}_{\dagger}}P(u_{i}\mid\mathbf{pa}(U_{i}))=\prod_{u_{i}\in\mathbf{x}\cup\mathbf{z}_{\dagger}\cup\mathbf{e}_{\dagger}}P(u_{i}\mid\mathbf{ppa}(U_{i}))$

where $\mathbf{ppa}(U_{i})$ is a set of partially assigned parents of $U_{i}$,
that is,
$\mathbf{Ppa}(U_{i})=\mathbf{Pa}(U_{i})\setminus\mathbf{Z}_{\ddagger}$.

Here, we summarise some important RVs or their assignments:

$\mathbf{X}$ | Query variables
---|---
$\mathbf{Z}_{\star}$ | Unobserved requisite variables apart from query variables
$\mathbf{e}_{\star}$ | Diagnostic evidence
$\mathbf{e}_{\smwhitestar}$ | Predictive evidence
$\mathbf{z}_{\dagger}$ | Assigned subset of $\mathbf{Z}_{\star}$ in a contextual assignment
$\mathbf{Z}_{\ddagger}$ | Subset of $\mathbf{Z}_{\star}$ not assigned in a contextual assignment
$\mathbf{e}_{\dagger}$ | Subset of $\mathbf{e}_{\star}$ in a contextual assignment
$\mathbf{e}_{\ddagger}$ | Subset of $\mathbf{e}_{\star}$ not in a contextual assignment

######  Example 16.

Consider the network of Figure 1(a), and assume that our diagnostic evidence
is $\\{F=1,G=0,H=1\\}$, predictive evidence is $\\{D=1\\}$, and query is
$\\{E=0\\}$. From the CPD’s structure, we have: $P(E=0\mid A=1,B,C)=P(E=0\mid
A=1)$; consequently, a contextual assignment is
$\mathbf{x}=\\{E=0\\},\mathbf{z}_{\dagger}=\\{A=1\\},\mathbf{e}_{\dagger}=\\{\\},\mathbf{Z}_{\ddagger}=\\{B,C\\},\mathbf{e}_{\ddagger}=\\{F=1,G=0,H=1\\}$.
We also have: $P(E=0\mid A=0,B=1,C)=P(E=0\mid A=0,B=1)$; consequently, another
such assignment is
$\mathbf{x}=\\{E=0\\},\mathbf{z}_{\dagger}=\\{A=0,B=1\\},\mathbf{e}_{\dagger}=\\{H=1\\},\mathbf{Z}_{\ddagger}=\\{C\\},\mathbf{e}_{\ddagger}=\\{F=1,G=0\\}$.

We aim to treat the evidence $\mathbf{e}_{\ddagger}$ independently, thus, we
define it first.

######  Definition 15.

The diagnostic evidence $\mathbf{e}_{\ddagger}$ in a contextual assignment
$\mathbf{x}$, $\mathbf{z}_{\dagger}$, $\mathbf{Z}_{\ddagger}$,
$\mathbf{e}_{\dagger}$, $\mathbf{e}_{\ddagger}$ will be called residual
evidence.

However, contextual assignments do not immediately allow us to treat the
residual evidence independently. We need the assignments to be safe.

######  Definition 16.

Let $e\in\mathbf{e}_{\star}$ be a diagnostic evidence, and let $S$ be an
unobserved ancestor of $E$ in the graph structure in $\mathcal{B}_{\star}$,
where $\mathcal{B}_{\star}$ is the sub-network formed by the requisite
variables. Let $S\rightarrow\cdots\ B_{i}\ \cdots\rightarrow E$ be a causal
trail such that either no $B_{i}$ is observed or there is no $B_{i}$. Let
$\mathbf{S}$ be the set of all such $S$. Then the variables $\mathbf{S}$ will
be called basis of $e$. Let
$\mathbf{\dot{e}}_{\star}\subseteq\mathbf{e}_{\star}$, and let
$\mathbf{\dot{S}}_{\star}$ be the set of all such $S$ for all
$e\in\mathbf{\dot{e}}_{\star}$. Then $\mathbf{\dot{S}}_{\star}$ will be called
basis of $\mathbf{\dot{e}}_{\star}$.

Reconsider Example 16; the basis of $\\{F=1\\}$ is $\\{B\\}$.

######  Definition 17.

Let $\mathbf{x}$, $\mathbf{z}_{\dagger}$, $\mathbf{Z}_{\ddagger}$,
$\mathbf{e}_{\dagger}$, $\mathbf{e}_{\ddagger}$ be a contextual assignment,
and let $\mathbf{S}_{\ddagger}$ be the basis of the residual evidence
$\mathbf{e}_{\ddagger}$. If
$\mathbf{S}_{\ddagger}\subseteq\mathbf{Z}_{\ddagger}$ then the contextual
assignment will be called safe.

######  Example 17.

Reconsider Example 16; the first example of contextual assignment is safe, but
the second is not since the basis $B$ of $\mathbf{e}_{\ddagger}$ is assigned
in $\mathbf{z}_{\dagger}$. We can make the second safe like this:
$\mathbf{x}=\\{E=0\\},\mathbf{z}_{\dagger}=\\{A=0,B=1\\},\mathbf{e}_{\dagger}=\\{F=1,H=1\\},\mathbf{Z}_{\ddagger}=\\{C\\},\mathbf{e}_{\ddagger}=\\{G=0\\}$.
See Figure 3.

Before showing that the residual evidence can now be treated independently, we
first define a random variable called weight.

######  Definition 18.

Let $e\in\mathbf{e}_{\star}$ be a diagnostic evidence, and let $W_{e}$ be a
random variable defined as follows:

$W_{e}=P(e\mid\mathbf{Pa}(E)).$

The variable $W_{e}$ will be called weight of $e$. The weight of a subset
$\mathbf{\dot{e}}_{\star}\subseteq\mathbf{e}_{\star}$ is defined as follows:

$W_{\mathbf{\dot{e}}_{\star}}=\prod_{u_{i}\in\mathbf{\dot{e}}_{\star}}P(u_{i}\mid\mathbf{Pa}(U_{i})).$

Now we can show the following result:

######  Theorem 5.

Let $\mathbf{\dot{e}}_{\star}\subseteq\mathbf{e}_{\star}$, and let
$\mathbf{\dot{S}}_{{\star}}$ be the basis of $\mathbf{\dot{e}}_{\star}$. Then
the expectation of weight $W_{\mathbf{\dot{e}}_{\star}}$ relative to the
distribution $Q_{\star}$ as defined in Equation 4 can be written as:

$\displaystyle\mathbb{E}_{Q_{\star}}[W_{\mathbf{\dot{e}}_{\star}}]=\sum_{\mathbf{\dot{s}}_{\star}}\prod_{u_{i}\in\mathbf{\dot{e}}_{\star}\cup\mathbf{\dot{s}}_{\star}}P(u_{i}\mid\mathbf{pa}(U_{i})).$

Hence, apart from unobserved variables $\mathbf{\dot{S}}_{{\star}}$, the
computation of $\mathbb{E}_{Q_{\star}}[W_{\mathbf{\dot{e}}_{\star}}]$ does not
depend on other unobserved variables. Now we are ready to show our main
result:

######  Theorem 6.

Let $\Psi$ be a set of all possible safe contextual assignments in the
distribution $P$. Then the query $\mu$ to $P$ can be computed as follows:

$\displaystyle\frac{\sum\limits_{\psi\in\Psi}\bigl{(}\prod\limits_{u_{i}\in\mathbf{x}[\psi]\cup\mathbf{z}_{\dagger}[\psi]\cup\mathbf{e}_{\dagger}[\psi]}P(u_{i}\mid\mathbf{ppa}(U_{i}))f(\mathbf{x}[\psi])R[\psi]\bigr{)}}{\sum\limits_{\psi\in\Psi}\bigl{(}\prod\limits_{u_{i}\in\mathbf{x}[\psi]\cup\mathbf{z}_{\dagger}[\psi]\cup\mathbf{e}_{\dagger}[\psi]}P(u_{i}\mid\mathbf{ppa}(U_{i}))R[\psi])\bigr{)}}$
(6)

where $R[\psi]$ denotes
$\mathbb{E}_{Q_{\star}}[W_{\mathbf{e}_{\ddagger}[\psi]}]$.

We draw some important conclusions: i) $\mu$ can be exactly computed by
performing the summation over all safe contextual assignments; notably,
variables in $\mathbf{Z}_{\dagger}$ vary, and so do variables in
$\mathbf{E}_{\dagger}$; ii) For all $\psi\in\Psi$, the computation of
$\mathbb{E}_{Q_{\star}}[W_{\mathbf{e}_{\ddagger}[\psi]}]$ does not depend on
the context $\mathbf{x[\psi]},\mathbf{z}_{\dagger}[\psi]$ since no basis of
$\mathbf{e}_{\ddagger}[\psi]$ is assigned in the context (by Theorem 5).
Hence, $\mathbb{E}_{Q_{\star}}[W_{\mathbf{e}_{\ddagger}[\psi]}]$ can be
computed independently. However, the context decides which evidence should be
in the subset $\mathbf{e}_{\ddagger}[\psi]$. That is why we can not cancel
$\mathbb{E}_{Q_{\star}}[W_{\mathbf{e}_{\ddagger}[\psi]}]$ from the numerator
and denominator.

Figure 3: Two safe contextual assignments to RVs of BN of Figure 1(a): (a) in
the context ${A=1}$, where edges $C\rightarrow E$ and $B\rightarrow E$ are
redundant since $E\perp B,C\mid A=1$; (b) in the context ${A=0,B=1}$, where
the edge $C\rightarrow E$ is redundant since $E\perp C\mid A=0,B=1$. To
identify such assignments, intuitively, we should apply the Bayes-ball
algorithm after removing these edges. Portions of graphs that the algorithm
visits, starting with visiting the variable $E$ from its child, are
highlighted. Notice that variables
$\mathbf{X},\mathbf{Z}_{\dagger},\mathbf{E}_{\dagger}$ lie in the highlighted
portion.

####  5.2.2 Context-Specific Likelihood Weighting

First, we present an algorithm that simulates a DC($\mathcal{B}$) program
$\mathbb{P}$ and generates safe contextual assignments. Then we discuss how to
estimate the expectations independently before estimating $\mu$.

##### Simulation of DC($\mathcal{B}$) Programs

We start by asking a question. Suppose we modify the first and the fourth rule
of Bayes-ball simulation, discussed in Section 3.2, as follows:

  * •

In the first rule, when the visit of an unobserved variable is from its child,
everything remains the same except that only some parents are visited, not
all.

  * •

Similarly, in the fourth rule, when the visit of an observed variable is from
its parent, everything remains the same except that only some parents are
visited.

Which variables will be assigned, and which will be weighted using the
modified simulation rules? Intuitively, only a subset of variables in
$\mathbf{Z}_{\star}$ should be assigned, and only a subset of variables in
$\mathbf{E}_{\star}$ should be weighted. But then how to assign/weigh a
variable knowing the state of only some of its parent. We can do that when
structures are present within CPDs of $\mathcal{B}$, and these structures are
explicitly represented using clauses in a DC($\mathcal{B}$) program
$\mathbb{P}$. Recall that the proof procedure, discussed in Section 5.1, can
sample random variables without sampling some of their ancestors. Hence, the
key idea is to visit only some parents (if possible due to structures);
consequently, those unobserved parents that are not visited might not be
needed to be sampled.

To realize that, we need to adapt the Bayes-ball simulation such that it works
on $\mathbb{P}$. However, there is a problem: $\mathbb{P}$ is a set of
clauses, and no explicit graph is associated with it on which the Bayes-ball
can be applied. Fortunately, we can infer direct influence relationships using
the dependency set of $\mathbb{P}$, which is automatically constructed, as
discussed in Section 4.2. The adapted simulation for DC($\mathcal{B}$)
programs is defined procedurally in Algorithm 2. The algorithm visits
variables from their parents and calls the top-down proof procedure (Algorithm
3) to visit variables from their children. Like Bayes-ball, these algorithms
also mark variables on top and bottom to avoid repeating the same action.

Algorithm 2 Simulation of DC($\mathcal{B}$) Programs

procedure Simulate-ground-DC($\mathbf{x},\mathbf{e}$)

  * •

Simulates a DC($\mathcal{B}$) program $\mathbb{P}$ based on inputs: i)
$\mathbf{x}$: a query; ii) $\mathbf{e}$: evidence.

  * •

Let $dep(\mathbb{P})$ be the dependency set of $\mathbb{P}$.

  * •

The procedure maintains global data structures: i) $\mathtt{Asg}$, a table
that records assignments of variables ($\mathbf{x}\cup\mathbf{z}_{\dagger}$);
ii) $\mathtt{Forward}$, a set of variables whose children to be visited from
parent; iii) $\mathtt{Top}$, a set of variables marked on top; iv)
$\mathtt{Bottom}$, a set of variables marked on bottom.

  * •

Output: i) $f(\mathbf{x})$ that can be either $0$ or $1$; ii) $\mathtt{W}$: a
table of weights of diagnostic evidence ($\mathbf{e}_{\dagger}$).

  1. 1.

Empty $\mathtt{Asg,W,Top,Bottom,Forward}$.

  2. 2.

If prove-marked-ground($\mathbf{x}$) is $\mathtt{yes}$ then $f(\mathbf{x}):=1$
else $f(\mathbf{x}):=0$.

  3. 3.

While $\mathtt{Forward}$ is not empty:

    1. (a)

Remove $\mathtt{A}$ from $\mathtt{Forward}$ and add $\mathtt{A}$ to
$\mathtt{Bottom}$.

    2. (b)

For all $\mathtt{A_{0}}$ such that
$dep(\mathbb{P})\models\mathtt{pa(A_{0},A)}$:

      1. i.

If $\mathtt{A_{0}}$ is observed with value $\mathtt{v}$ in $\mathbf{e}$ and
$\mathtt{A_{0}\notin Top}$:

        1. A.

Choose $\mathtt{A_{0}\sim D\leftarrow A_{1},\dots,A_{n}}\in\mathbb{P}$ such
that prove-marked-ground($\mathtt{A_{1},\dots,A_{n}}$) is $\mathtt{yes}$. Add
$\mathtt{A_{0}}$ to $\mathtt{Top}$.

        2. B.

Let $\mathtt{p}$ be the likelihood at $\mathtt{v}$ according to distribution
$\mathtt{D}$. Record $\mathtt{W[A_{0}]:=p}$.

      2. ii.

If $\mathtt{A_{0}}$ is not observed in $\mathbf{e}$ and $\mathtt{A_{0}\notin
Bottom}$: add $\mathtt{A_{0}}$ to $\mathtt{Forward}$.

  4. 4.

Return $[f(\mathbf{x}),\mathtt{W}]$.

Algorithm 3 DC($\mathcal{B}$) Proof Procedure Marked

procedure prove-marked-ground($\mathtt{G}$)

  * •

Proves a conjunction of ground atoms $\mathtt{G}$, consequently, visits
variables from child.

  * •

Accesses $\mathbb{P}$, $\mathtt{Top,Bottom,Forward,Asg}$, and $\mathbf{e}$ as
defined in Algorithm 2.

  * •

Returns $\mathtt{yes}$ if there is a choice that makes $\mathtt{G}$ empty;
otherwise the procedure fails.

  1. 1.

While $\mathtt{G}$ is not empty:

    1. (a)

Select the first atom $\mathtt{A}$ from $\mathtt{G}$.

    2. (b)

If $\mathtt{A}$ is of the form $\mathtt{t\cong v}$:

      1. i.

If $\mathtt{t}$ is observed in $\mathbf{e}$ and its observed value is
$\mathtt{v}$: remove $\mathtt{A}$ from $\mathtt{G}$.

      2. ii.

Else if $\mathtt{t\in Top}$:

        1. A.

If $\mathtt{Asg[t]==v}$: remove $\mathtt{A}$ from $\mathtt{G}$.

      3. iii.

Else:

        1. A.

Add $\mathtt{t}$ to $\mathtt{Top}$.

        2. B.

Choose $\mathtt{t\sim D\leftarrow B_{1},\dots,B_{n}}\in\mathbb{P}$ with
$\mathtt{t}$ in the head.

        3. C.

Set $\mathtt{G:=B_{1},\dots,B_{n},sample(t,D),G}$.

    3. (c)

Else If $\mathtt{A}$ is of the form $\mathtt{sample(t,D)}$:

      1. i.

Sample a value $\mathtt{v}$ from $\mathtt{D}$, record $\mathtt{Asg[t]:=v}$,
and remove $\mathtt{A}$ from $\mathtt{G}$.

      2. ii.

If $\mathtt{t\notin Bottom}$: add $\mathtt{t}$ to $\mathtt{Forward}$

  2. 2.

Return $\mathtt{yes}$.

Algorithm 4 Generation of residual evidence’s weights for DC($\mathcal{B}$)
Programs

procedure Weight-Res-Ground($\mathtt{Res}$)

  * •

Generates residual evidence’s weights based on input: i) $\mathtt{Res}$, a
list of residual evidence. This procedure accesses $\mathbb{P}$ of Algorithm
2.

  * •

Output: i) $\mathtt{W_{1}}$, a table of residual evidence’s weights.

  1. 1.

For all random variables $\mathtt{A}_{0}$ in $\mathtt{Res}$.

    1. (a)

Let $\mathtt{v}$ be the value observed for $\mathtt{A}_{0}$ in $\mathtt{Res}$.

      1. i.

Choose $\mathtt{A_{0}\sim D\leftarrow A_{1},\dots,A_{n}}\in\mathbb{P}$ such
that prove-marked-ground($\mathtt{A_{1},\dots,A_{n}}$) is $\mathtt{yes}$.

      2. ii.

Let $\mathtt{p}$ be the likelihood of $\mathtt{v}$ according to distribution
$\mathtt{D}$. Record $\mathtt{W_{1}[A_{0}]:=p}$.

  2. 2.

Return $\mathtt{W_{1}}$.

Since the simulation of $\mathbb{P}$ follows the same four rules of Bayes-ball
simulation except that only some parents are visited in the first and fourth
rule, we show that

######  Lemma 7.

Let $\mathbf{E_{\dagger}}$ be a set of observed variables weighed and let
$\mathbf{Z_{\dagger}}$ be a set of unobserved variables, apart from query
variables, assigned in a simulation of $\mathbb{P}$, then,

$\mathbf{Z_{\dagger}}\subseteq\mathbf{Z_{\star}}\text{ and
}\mathbf{E_{\dagger}}\subseteq\mathbf{E_{\star}}.$

The query variables $\mathbf{X}$ are always assigned since the simulation
starts with visiting these variables as if visits are from one of their
children. To simplify notation, from now on we use $\mathbf{Z}_{\dagger}$ to
denote the subset of variables in $\mathbf{Z}_{\star}$ that are assigned,
$\mathbf{E}_{\dagger}$ to denote the subset of variables in
$\mathbf{E}_{\star}$ that are weighted in the simulation of $\mathbb{P}$.
$\mathbf{Z}_{\ddagger}$ to denote
$\mathbf{Z}_{\star}\setminus\mathbf{Z}_{\dagger}$, and $\mathbf{E}_{\ddagger}$
to denote $\mathbf{E}_{\star}\setminus\mathbf{E}_{\dagger}$ We show that the
simulation performs safe contextual assignments to requisite variables.

######  Theorem 8.

The partial assignment $\mathbf{x}$, $\mathbf{z}_{\dagger}$,
$\mathbf{Z}_{\ddagger}$, $\mathbf{e}_{\dagger}$, $\mathbf{e}_{\ddagger}$
generated in a simulation of $\mathbb{P}$ is a safe contextual assignment.

The proof of Theorem 8 relies on the following Lemma.

######  Lemma 9.

Let $\mathbb{P}$ be a DC($\mathcal{B}$) program specifying a distribution $P$.
Let $\mathbf{B},\mathbf{C}$ be disjoint sets of parents of a variable $A$. In
the simulation of $\mathbb{P}$, if $A$ is sampled/weighted, given an
assignment $\mathbf{c}$, and without assigning $\mathbf{B}$, then,

$P(A\mid\mathbf{c},\mathbf{B})=P(A\mid\mathbf{c}).$

Hence, just like the standard LW, we sample from a factor $Q_{\dagger}$ of the
proposal distribution $Q_{\star}$, which is given by,

$\displaystyle
Q_{\dagger}=\prod_{u_{i}\in\mathbf{x}\cup\mathbf{z}_{\dagger}\cup\mathbf{e}_{\dagger}}P(u_{i}\mid\mathbf{ppa}(U_{i}))$

where $P(u_{i}\mid\mathbf{ppa}(U_{i}))=1$ if $u_{i}\in\mathbf{e}_{\dagger}$.
It is precisely this factor that Algorithm 2 considers for the simulation of
$\mathbb{P}$. Starting by first setting $\mathbf{E}_{\smwhitestar}$,
$\mathbf{E}_{\ddagger}$ their observed values, it assigns
$\mathbf{X}\cup\mathbf{Z}_{\dagger}$ and weighs $\mathbf{e}_{\dagger}$ in the
topological ordering. In this process, it records partial weights
$\mathbf{w}_{\mathbf{e}_{\dagger}}$, such that:
$\prod_{x_{i}\in\mathbf{e}_{\dagger}}w_{x_{i}}=w_{\mathbf{e}_{\dagger}}$ and
$w_{x_{i}}\in\mathbf{w}_{\mathbf{e}_{\dagger}}$. Given $M$ partially weighted
samples
$\mathcal{D}_{\dagger}=\langle\mathbf{x}[1],\mathbf{w}_{\mathbf{e}_{\dagger}[1]}\rangle,\dots,\langle\mathbf{x}[M],\mathbf{w}_{\mathbf{e}_{\dagger}[M]}\rangle$
from $Q_{\dagger}$, we could estimate $\mu$ using Theorem 6 as follows:

$\displaystyle\overline{\mu}=\frac{\sum_{m=1}^{M}f(\mathbf{x}[m])\times
w_{\mathbf{e_{\dagger}}[m]}\times\mathbb{E}_{Q_{\star}}[W_{\mathbf{e}_{\ddagger}[m]}]}{\sum_{m=1}^{M}w_{\mathbf{e_{\dagger}}[m]}\times\mathbb{E}_{Q_{\star}}[W_{\mathbf{e}_{\ddagger}[m]}]}$
(7)

However, we still can not estimate it since we still do not have expectations
$\mathbb{E}_{Q_{\star}}[W_{\mathbf{e}_{\ddagger}[m]}]$. Fortunately, there are
ways to estimate them from partial weights in $\mathcal{D}_{\dagger}$. We
discuss one such way next.

##### Estimating the Expected Weight of Residuals

We start with the notion of sampling mean. Let $\mathcal{W}_{\star}=\langle
w_{e_{1}}[1],\dots,w_{e_{m}}[1]\rangle,\dots,\langle
w_{e_{1}}[n],\dots,w_{e_{m}}[n]\rangle$ be a data set of $n$ observations of
weights of $m$ diagnostic evidence drawn using the standard LW. How can we
estimate the expectation $\mathbb{E}_{Q_{\star}}[W_{e_{i}}]$ from
$\mathcal{W}_{\star}$? The standard approach is to use the sampling mean:
$\overline{W}_{e_{i}}=\frac{1}{n}\sum_{r=1}^{n}w_{e_{i}}[r]$. In general,
$\mathbb{E}_{Q_{\star}}[W_{e_{i}}\dots W_{e_{j}}]$ can be estimated using the
estimator: $\overline{W_{e_{i}}\dots
W}_{e_{j}}=\frac{1}{n}\sum_{r=1}^{n}w_{e_{i}}[r]\dots w_{e_{j}}[r]$. Since LW
draws are independent and identical distributed (i.i.d.), it is easy to show
that the estimator is unbiased.

However, some entries, i.e., weights of residual evidence, are missing in the
data set $\mathcal{W}_{\dagger}$ obtained using CS-LW. The trick is to fill
the missing entries by drawing samples of the missing weights once we obtain
$\mathcal{W}_{\dagger}$. More precisely, missing weights $\langle
W_{e_{i}},\dots,W_{e_{j}}\rangle$ in $r^{\text{th}}$ row of
$\mathcal{W}_{\dagger}$ are filled in with a joint state $\langle
w_{e_{i}}[r],\dots,w_{e_{j}}[r]\rangle$ of the weights. To draw the joint
state, we use Algorithm 4 and call weight-res-ground($[e_{i},\dots,e_{j}]$) to
visit observed variables $\langle E_{i},\dots,E_{j}\rangle$ from parent. Once
all missing entries are filled in, we can estimate
$\mathbb{E}_{Q_{\star}}[W_{e_{i}}\dots W_{e_{j}}]$ using the estimator
$\overline{W_{e_{i}}\dots W}_{e_{j}}$ as just discussed. Once we estimate all
required expectations, it is straightforward to estimate $\mu$ using Equation
7.

##### Interpretation

At this point, we can gain some insight into the role of CSIs in sampling.
They allow us to estimate the expectation
$\mathbb{E}_{Q_{\star}}[W_{\mathbf{e}_{\ddagger}}]$ separately. We estimate it
from all samples obtained at the end of the sampling process, thereby reducing
the contribution $W_{\mathbf{e}_{\ddagger}}$ makes to the variance of our main
estimator $\overline{\mu}$. The residual evidence $\mathbf{e}_{\ddagger}$
would be large if much CSIs are present in the distribution; consequently, we
would obtain a much better estimate of $\mu$ using significantly fewer
samples. Moreover, drawing a single sample would be faster since only a subset
of requisite variables is visited. Hence, in addition to CIs, we exploit CSIs
and improve LW further. We observe all these speculated improvements in our
experiments.

##  6 Inference in First-Order DC# Programs

Algorithm 5 Simulation of DC# Programs

procedure Simulate-DC#($\mathbf{x},\mathbf{e}$)

  * •

Simulates a DC program $\mathbb{P}$ based on inputs: i) $\mathbf{x}$, a ground
query; ii) $\mathbf{e}$: evidence.

  * •

Let $dep(\mathbb{P})$ be the dependency set of $\mathbb{P}$.

  * •

The procedure maintains global data structures: i) $\mathtt{Asg}$, a table
that records partial assignments of unobserved variables; ii)
$\mathtt{Forward}$, a set of variables whose children to be visited from
parent; iii) $\mathtt{Top}$, a set of variables marked on top; iv)
$\mathtt{Bottom}$, a set of variables marked on bottom; v) $\mathtt{Dst}$, a
table that records variables’ distributions.

  * •

Output: i) $f(\mathbf{x})$ that can be either $0$ or $1$; ii) $\mathtt{W}$: a
table of weights of diagnostic evidence ($\mathbf{e}_{\dagger}$).

  1. 1.

Empty $\mathtt{Asg,W,Top,Bottom,Dst,Forward}$. Let $\mathcal{CR}$ be combining
rules used for $\mathbb{P}$.

  2. 2.

If prove-marked($\mathbf{x}$) fails then $f(\mathbf{x}):=0$ else
$f(\mathbf{x}):=1$

  3. 3.

While $\mathtt{Forward}$ is not empty:

    1. (a)

Remove $\mathtt{A}$ from $\mathtt{Forward}$ and add $\mathtt{A}$ to
$\mathtt{Bottom}$

    2. (b)

For all $\mathtt{A_{0}}$ such that
$dep(\mathbb{P})\models\mathtt{pa(A_{0},A)}$:

      1. i.

If $\mathtt{A_{0}}$ is observed to be $\mathtt{v}$ in $\mathbf{e}$ and
$\mathtt{A_{0}\notin Top}$:

        1. A.

Add $\mathtt{A_{0}}$ to $\mathtt{Top}$.

        2. B.

For all (renamed) clause $\mathtt{B_{0}\sim D\leftarrow
B_{1},\dots,B_{m}}\in\mathbb{P}$ such that mgu $\sigma$ unifies
$\mathtt{B_{0}}$ and $\mathtt{A_{0}}$: call prove-
marked($(\mathtt{B_{1},\dots,B_{m},add\\_dst(B_{0},D))\sigma}$)

        3. C.

Let $[\mathtt{D_{1},\dots,D_{l}}]$ be distributions for $\mathtt{A_{0}}$
recorded in table $\mathtt{Dst}$, and let $\mathtt{p}$ be the likelihood at
$\mathtt{v}$ according to $\mathcal{CR}([\mathtt{D_{1},\dots,D_{l}}])$. Record
$\mathtt{W[A_{0}]:=p}$.

      2. ii.

If $\mathtt{A_{0}}$ is not observed in $\mathbf{e}$ and $\mathtt{A_{0}\notin
Bottom}$: add $\mathtt{A_{0}}$ to $\mathtt{Forward}$

  4. 4.

Return $[f(\mathbf{x}),\mathtt{W}]$

This section extends CS-LW to first-order DC# programs where clauses need not
be mutually exclusive. The extended algorithm is called first-order context-
specific likelihood weighting (FO-CS-LW).

Using tools of logic such as unification and substitution, it is easy to
simulate first-order programs without completely grounding them first. The
simulation process defined in Algorithm 5 does that. It uses dependency sets
of programs to visit RVs from parents and calls Algorithm 7 to visit RVs from
children. The RV sets of programs are used to identify RVs defined by
programs. There are two important features of the top-down proof procedure
with logical variables defined in Algorithm 7, which are worth highlighting.

Firstly, it computes answer substitutions of a query $\mathtt{\leftarrow
A_{1},\dots,A_{m}}$, that is, the substitutions of the refutations of the
query restricted to the variables in the query. To realize that, instead of
the query, the initial goal $\mathtt{G_{0}}$ is of the form:

$\mathtt{yes(V_{1},\dots,V_{k})\leftarrow A_{1},\dots,A_{m}}$

where $\mathtt{V_{1},\dots,V_{k}}$ are the logical variables that appear in
the query. This allows the procedure to return the answer
$\mathtt{\\{V_{1}/t_{1},\dots,V_{k}/t_{k}\\}}$ when the body of goal
$\mathtt{G_{i}}$ is empty after applying the resolution rules. This is just
like the proof procedure for definite programs with logical variables (?).

Secondly and more importantly, the procedure searches and collects all
distributions defined for a RV in a global variable $\mathtt{Dst}$ before
sampling values of the RV from the combined distribution. This is as per the
semantics of DC# programs, and in this way, the algorithm also exploits ICIs.

The generation of residual evidence’s weights is defined in Algorithm 7.

Algorithm 6 DC# Proof Procedure

procedure prove-marked($\mathtt{Q}$)

  * •

Proves a conjunction of atoms $\mathtt{Q}$ with variables
$\mathtt{V_{1},\dots,V_{k}}$.

  * •

Accesses $\mathbb{P}$, $\mathtt{Asg,Top,Bottom,Dst,Forward}$, $\mathbf{e}$,
and $\mathcal{CR}$ as defined in Algorithm 5.

  * •

Returns substitutions of variables $\mathtt{V_{1},\dots,V_{k}}$ if refutation
exists; otherwise fails.

  * •

Let $rv(\mathbb{P})$ be an RV set of $\mathbb{P}$.

  1. 1.

Set $\mathtt{G}$ to a clause $\mathtt{yes(V_{1},\dots,V_{k})\leftarrow Q}$

  2. 2.

While the body of $\mathtt{G}$ is not empty:

    1. (a)

Suppose $\mathtt{G}$ is $\mathtt{yes(t_{1},\dots,t_{k})\leftarrow
A_{1},\dots,A_{n}}$. Select $\mathtt{A_{1}}$

    2. (b)

If $\mathtt{A_{1}}$ is an atom of the form $\mathtt{X\cong V}$:

      1. i.

Choose a grounding substitution $\sigma_{1}$ such that
$rv(\mathbb{P})\models\mathtt{X\sigma_{1}}$

      2. ii.

If $\mathtt{X\sigma_{1}}$ is observed in $\mathbf{e}$: let $\mathtt{v}$ be the
observed value.

      3. iii.

Else if $\mathtt{X\sigma_{1}\in Top}$: let $\mathtt{v}$ be
$\mathtt{Asg[X\sigma_{1}]}$.

      4. iv.

Else:

        1. A.

For all (renamed) clause $\mathtt{B_{0}\sim D\leftarrow
B_{1},\dots,B_{m}}\in\mathbb{P}$ such that mgu $\sigma_{3}$ unifies
$\mathtt{B_{0}}$ and $\mathtt{X\sigma_{1}}$: call prove-
marked($(\mathtt{B_{1},\dots,B_{m},add\\_dst(B_{0},D))\sigma_{3}}$)

        2. B.

Let $\mathtt{M}=[\mathtt{D_{1},\dots,D_{l}}]$ be distributions for
$\mathtt{X\sigma_{1}}$ recorded in table $\mathtt{Dst}$. Let $\mathtt{v}$ be
value sampled from $\mathcal{CR}(\mathtt{M})$. Record
$\mathtt{Asg[X\sigma_{1}]:=v}$.

        3. C.

Add $\mathtt{X\sigma_{1}}$ to $\mathtt{Top}$. If $\mathtt{X\sigma_{1}\notin
Bottom}$ then add $\mathtt{X\sigma_{1}}$ to $\mathtt{Forward}$

      5. v.

If mgu $\sigma_{2}$ unify $\mathtt{X\sigma_{1}\cong v}$ and $\mathtt{X\cong
V}$: set $\mathtt{G:=((yes(t_{1},\dots,t_{k})\leftarrow
A_{2},\dots,A_{n})\sigma_{1})\sigma_{2}}$

    3. (c)

Else if $\mathtt{A_{1}}$ is of the form $\mathtt{add\\_dst(X,D)}$: //
$\mathtt{A_{1}}$ will always be ground here

      1. i.

Record $\mathtt{Dst[X]:=D}$ and set
$\mathtt{G:=yes(t_{1},\dots,t_{k})\leftarrow A_{2},\dots,A_{n}}$

    4. (d)

Else if $\mathtt{A_{1}}$ is of the form $\mathtt{V_{1}\diamond V_{2}}$ and
evaluates to true: $\mathtt{G:=yes(t_{1},\dots,t_{k})\leftarrow
A_{2},\dots,A_{n}}$

  3. 3.

Return $\mathtt{\\{V_{1}/t_{1},\dots,V_{k}/t_{k}\\}}$ when $\mathtt{G}$ is
$\mathtt{yes(t_{1},\dots,t_{k})\leftarrow}$

Algorithm 7 Generation of residual evidence’s weights for DC# Programs

procedure Weight-Residuals($\mathtt{Res}$)

  * •

Generates residual evidence’s weights based on input: i) $\mathtt{Res}$, a
list of residual evidence. This procedure accesses $\mathbb{P}$ and
$\mathcal{CR}$ of Algorithm 5.

  * •

Output: i) $\mathtt{W_{1}}$, a table of residual evidence’s weights.

  1. 1.

For all random variable $\mathtt{A}_{0}$ in $\mathtt{Res}$.

    1. (a)

Let $\mathtt{v}$ be the value observed for $\mathtt{A}_{0}$ in $\mathtt{Res}$.

      1. i.

For all (renamed) clause $\mathtt{B_{0}\sim D\leftarrow
B_{1},\dots,B_{m}}\in\mathbb{P}$ such that mgu $\sigma$ unifies
$\mathtt{B_{0}}$ and $\mathtt{A_{0}}$: call prove-
marked($(\mathtt{B_{1},\dots,B_{m},add\\_dst(B_{0},D))\sigma}$)

      2. ii.

Let $[\mathtt{D_{1},\dots,D_{l}}]$ be distributions for $\mathtt{A_{0}}$
recorded in table $\mathtt{Dst}$, and let $\mathtt{p}$ be the likelihood at
$\mathtt{v}$ according to $\mathcal{CR}([\mathtt{D_{1},\dots,D_{l}}])$. Record
$\mathtt{W_{1}[A_{0}]:=p}$.

  2. 2.

Return $\mathtt{W_{1}}$.

##### Dealing with Continuous RVs

Till now, we have not talked about inference in programs with continuous RVs.
Nevertheless, the notions discussed so far are sufficient to explain inference
in such programs. Likelihood weighting naturally extends to continuous domains
(?). We just need rules to resolve comparison atoms of the form
$\mathtt{V_{1}\diamond V_{2}}$ that appear in the body of clauses. These rules
are already present in the proof procedure.

To ensure that FO-CS-LW correctly estimates the probabilities, we just need to
ensure that Lemma 9 also holds for the DC# programs’ simulation.

######  Theorem 10.

Lemma 9 is also true for simulation of DC# programs.

##  7 Empirical Evaluation

In this section, we empirically evaluate our inference algorithms and answer
several research questions.

###  7.1 How do the sampling speed and the accuracy of estimates obtained
using CS-LW compare with the standard LW in the presence of CSIs?

To answer it, we need BNs with structures present within CPDs. Such BNs,
however, are not readily available since the structure while designing
inference algorithms is generally overlooked. We identified two BNs from the
Bayesian network repository (?), which have many structures within CPDs: i)
Alarm, a monitoring system for patients with 37 variables; ii) Andes, an
intelligent tutoring system with 223 variables.

LW CS-LW BN N MAE $\pm$ Std. Time MAE $\pm$ Std. Time Alarm 100 0.2105 $\pm$
0.1372 0.09 0.0721 $\pm$ 0.0983 0.06 1000 0.0766 $\pm$ 0.0608 0.86 0.0240
$\pm$ 0.0182 0.53 10000 0.0282 $\pm$ 0.0181 8.64 0.0091 $\pm$ 0.0069 5.53
100000 0.0086 $\pm$ 0.0067 89.93 0.0034 $\pm$ 0.0027 57.64 Andes 100 0.0821
$\pm$ 0.0477 1.07 0.0619 $\pm$ 0.0453 0.22 1000 0.0257 $\pm$ 0.0184 10.62
0.0163 $\pm$ 0.0139 2.20 10000 0.0087 $\pm$ 0.0069 106.55 0.0058 $\pm$ 0.0042
22.62 100000 0.0025 $\pm$ 0.0015 1074.93 0.0020 $\pm$ 0.0016 233.72

Table 1: The mean absolute error (MAE), the standard deviation of the error
(Std.), and the average execution time (in seconds) versus the number of
samples (N). For each case, LW and CS-LW were executed 30 times.

We used the standard decision tree learning algorithm to detect structures and
overfitted it on tabular-CPDs to get tree-CPDs, which was then converted into
clauses. Let us denote the program with these clauses by $\mathbb{P}_{tree}$.
CS-LW is implemented in the Prolog programming language, thus to compare the
sampling speed of LW with CS-LW, we need a similar implementation of LW.
Fortunately, we can use the same implementation of CS-LW for obtaining LW
estimates. Recall that if we do not make structures explicit in clauses and
represent each entry in tabular-CPDs with clauses, then CS-LW boils down to
LW. Let $\mathbb{P}_{table}$ denotes the program where each rule in it
corresponds to an entry in tabular-CPDs. Table 1 shows the comparison of
estimates obtained using $\mathbb{P}_{tree}$ (CS-LW) and $\mathbb{P}_{table}$
(LW). Note that CS-LW automatically discards non-requisite variables for
sampling. So, we chose the query and evidence such that almost all variables
in BNs were requisite for the conditional query.

As expected, we observe that less time is required by CS-LW to generate the
same number of samples. This is because it visits only the subset of requisite
variables in each simulation. Andes has more structures compared to Alarm.
Thus, the sampling speed of CS-LW is much faster compared to LW in Andes.
Additionally, we observe that the estimate, with the same number of samples,
obtained by CS-LW is much better than LW. This is significant. It is worth
mentioning that approaches based on collapsed sampling obtain better estimates
than LW with the same number of samples, but then the speed of drawing samples
significantly decreases (?). In CS-LW, the speed increases when structures are
present. This is possible because CS-LW exploits CSIs.

Hence, we get the answer to our first question: When many structures are
present, and when they are made explicit in clauses, then CS-LW will draw
samples faster compared to LW. Additionally, estimates will be better with the
same number of samples.

###  7.2 How does FO-CS-LW perform as the domain size increases?

The exact inference algorithms that PLP systems generally use for inference do
not scale with domain sizes of logical variables in the program. Large domain
sizes result in a huge ground program on which exact inference becomes
intractable even for PLPs supporting only Boolean RVs. Thus, it is interesting
to investigate how FO-CS-LW, an approximate inference algorithm, performs on
such PLPs.

For this purpose, we compared FO-CS-LW with the inference algorithm used in
ProbLog, one of the most popular PLP systems. This algorithm first grounds
first-order programs and then performs exact inference to exploit structures
of clauses in the programs. We used a ProbLog program shown in Figure 4 for
this experiment. Note that in ProbLog, when multiple distributions are
specified for an RV, they are combined using noisy OR, and when no
distribution is specified, the RV is set to false. So, using this combining
rule, the ProbLog program of Figure 4 can be expressed as a DC# program. The
domain size of each logical variable in the program is two since there are two
clients, two accounts, and two loans. In such cases, instead of specifying the
domain size of each logical variable separately, we will simply say that the
domain size is two. Notice that relationships among clients, accounts, and
loans are also probabilistic, so the number of RVs explicated by the program
becomes huge as the domain size increases. More precisely, there are
$3n^{2}+6n$ RVs when domain size is $n$. We also compared the performance of
FO-CS-LW when applied directly to equivalent first-order programs versus when
it was applied to the grounded programs. Indeed, when the requisite network is
huge, FO-CS-LW should perform well if first-order programs are first grounded.
This is the case when the probability of query
$Q_{1}=P$($\mathtt{high\\_savings(a1)\cong t}$ $\mid$
$\mathtt{home\\_loan(l1)\cong f}$, $\mathtt{debt(c1)\cong t}$,
$\mathtt{has\\_loan(c1,l1)\cong f}$) is estimated, as illustrated in Figure 5.
However, when the requisite network is small, FO-CS-LW should perform well if
applied directly to first-order programs. This is the case when the query
($Q_{2}$) is to compute $P(\mathtt{debt(c1)\cong t})$ given all other RVs (all
RVs of type $\mathtt{has\\_loan(C,L)}$ were set to $\mathtt{f}$ (“false”), all
RVs of type $\mathtt{high\\_savings(A)}$ were set to $\mathtt{f}$, and rest
RVs were set to $\mathtt{t}$ (“true”). Furthermore, ProbLog could not compute
probabilities beyond a certain domain size on a machine with $132$ GB main
memory, whereas FO-CS-LW quickly scaled to a domain size of 50.

$\displaystyle\mathtt{client(c1).\quad client(c2).\quad\dots}$ $\displaystyle\mathtt{account(a1).\quad account(a2).\quad\dots}$ $\displaystyle\mathtt{loan(l1).\quad loan(l2).\quad\dots}$ $\displaystyle\mathtt{0.7::home\\_loan(L)\mathop{:\\!\\!-}loan(L).}$ $\displaystyle\mathtt{0.3::high\\_savings(A)\mathop{:\\!\\!-}account(A).}$ $\displaystyle\mathtt{0.01::has\\_account(C,A)\mathop{:\\!\\!-}client(C),account(A).}$ $\displaystyle\mathtt{0.02::account\\_loan(A,L)\mathop{:\\!\\!-}account(A),loan(L).}$ $\displaystyle\mathtt{0.9::has\\_loan(C,L)\mathop{:\\!\\!-}has\\_account(C,A),account\\_loan(A,L).}$ $\displaystyle\mathtt{0.001::has\\_loan(C,L)\mathop{:\\!\\!-}client(C),loan(L).}$ $\displaystyle\mathtt{0.9::debt(C)\mathop{:\\!\\!-}has\\_loan(C,L),home\\_loan(L).}$ $\displaystyle\mathtt{0.6::debt(C)\mathop{:\\!\\!-}has\\_loan(C,L),\backslash\\!+\\!home\\_loan(L).}$ $\displaystyle\mathtt{0.3::debt(C)\mathop{:\\!\\!-}has\\_account(C,A),\backslash\\!+\\!high\\_savings(A).}$ $\displaystyle\mathtt{0.01::debt(C)\mathop{:\\!\\!-}client(C).}$ |  $\displaystyle\mathtt{client(c1)\sim val(t).\quad client(c2)\sim val(t).\quad\dots}$ $\displaystyle\mathtt{account(a1)\sim val(t).\quad account(a2)\sim val(t).\quad\dots}$ $\displaystyle\mathtt{loan(l1)\sim val(t).\quad loan(l2)\sim val(t).\quad\dots}$ $\displaystyle\mathtt{home\\_loan(L)\sim bernoulli(0.7)\leftarrow loan(L)\cong t.}$ $\displaystyle\mathtt{high\\_savings(A)\sim bernoulli(0.3)\leftarrow account(A)\cong t.}$ $\displaystyle\mathtt{has\\_account(C,A)\sim bernoulli(0.01)\leftarrow client(C)\cong t,account(A)\cong t.}$ $\displaystyle\mathtt{account\\_loan(A,L)\sim bernoulli(0.02)\leftarrow account(A)\cong t,loan(L)\cong t.}$ $\displaystyle\mathtt{has\\_loan(C,L)\sim bernoulli(0.9)\leftarrow has\\_account(C,A)\cong t,account\\_loan(A,L)\cong t.}$ $\displaystyle\mathtt{has\\_loan(C,L)\sim bernoulli(0.001)\leftarrow client(C)\cong t,loan(L)\cong t.}$ $\displaystyle\mathtt{debt(C)\sim bernoulli(0.9)\leftarrow has\\_loan(C,L)\cong t,home\\_loan(L)\cong t.}$ $\displaystyle\mathtt{debt(C)\sim bernoulli(0.6)\leftarrow has\\_loan(C,L)\cong t,home\\_loan(L)\cong f.}$ $\displaystyle\mathtt{debt(C)\sim bernoulli(0.3)\leftarrow has\\_account(C,A)\cong t,high\\_savings(A)\cong f.}$ $\displaystyle\mathtt{debt(C)\sim bernoulli(0.01)\leftarrow client(C)\cong t.}$
---|---
Figure 4: (Left) A ProbLog program specifying a probability distribution over
relationships and attributes of clients, accounts, and loans. (Right) The
equivalent DC# program. Figure 5: The first two graphs are for query $Q_{1}$,
and the last two graphs are for query $Q_{2}$, mentioned in Section 7.2. (a)
Comparison of exact probabilities of $Q_{1}$ computed by ProbLog, and
probabilities estimated by FO-CS-LW when applied to the first-order and the
grounded program. (b) The average time for processing $Q_{1}$ versus the
domain size. (c) Comparison of probabilities of query $Q_{2}$ for the three
cases. (d) The average time for processing $Q_{2}$ versus the domain size. To
estimate the probabilities, FO-CS-LW used $10,000$ samples. The size of $n$
indicates that $n$ clients, $n$ accounts, and $n$ loans are present in the
program. The shaded region denotes the standard deviation from the mean
probability estimated by FO-CS-LW when executed $30$ times for each $n$. The
execution time includes the grounding time when FO-CS-LW is applied to
grounded programs.

One might expect that FO-CS-LW would perform poorly as domain size increases,
and more samples would be required to get a reasonable estimate of
probabilities. Figure 5 suggests the opposite. Using the same number of
samples, the standard deviation from the mean does not increase as domain size
increases. This is because FO-CS-LW exploits symmetries that arise due to
noisy OR. Notice that exact probabilities do not change much as domain size
increases because unique parameters do not increase even though the domain
size increases and the number of parameters increases.

We conclude that FO-CS-LW scales with the domain size and can be useful on
problems where the ProbLog inference algorithm fails.

###  7.3 How does FO-CS-LW compare to the state-of-the-art inference
algorithms for hybrid relational probabilistic models?

Figure 6: The first two graphs are for query $Q_{3}$, and the last two graphs
are for query $Q_{4}$, mentioned in Section 7.3. (a) Comparison of estimates
obtained using FO-CS-LW and Old-DC for query $Q_{3}$. (b) Average time taken
by FO-CS-LW and Old-DC for $Q_{3}$. (c) Comparison of estimates for query
$Q_{4}$. (d) Average time taken for $Q_{4}$. $10,000$ samples were used for
each of the two algorithms. The shaded region denotes the standard deviation
from the mean probability estimated by algorithms when executed $100$ times
for each case. Old-DC suffered arithmetic underflow as observed data
increased.

Those exact inference algorithms that exploit CSIs are not readily applicable
to hybrid relational probabilistic models. There are not many open-source
implementations of inference algorithms for such models444The publicly
available code for BLPs is based on SICStus Prolog 3, the version that SICStus
no longer supports. So, it is difficult to run the code.. The exploitation of
first-order CSIs and symmetries arising due to aggregations in such models is
challenging, and to the best of our knowledge, no algorithm can exploit them
in such models. To some extent, the likelihood weighting-based inference
algorithm developed for the old version of DC can exploit them (?). However,
it does not filter out irrelevant evidence before inference, which is crucial
in the case of relational databases. So, in this experiment, we aim to
investigate how much FO-CS-LW improves upon old-DC’s inference algorithm.

For this purpose, we used a real-world relational data generated by processing
the financial database from the PKDD’99 Discovery Challenge. This data set is
about services that a bank offers to its clients, such as loans, accounts, and
credit cards. It contains information of four types of entities: $5,358$
clients, $4,490$ accounts, $680$ loans and $77$ districts. Ten attributes are
of the continuous type, and three are of the discrete type. The data set
contains four relations: $\mathtt{hasAccount/2}$ that links clients to
accounts; $\mathtt{hasLoan/2}$ that links accounts to loans;
$\mathtt{clientDistrict/2}$ that links clients to districts; and finally
$\mathtt{clientLoan/2}$ that links clients to loans.

We learned a model in the form of distributional clauses as described in (?)
from the financial data set. The learned model, which was a program, specified
a probability distribution over all attributes of all instances of the
entities in the data set. Since the program was learned just as described in
(?), relationships among entities could not be probabilistic. Furthermore,
clauses in the program were mutually exclusive, and aggregation atoms and
statistical model atoms were used in the bodies of the clauses. Negations were
allowed in the bodies to deal with missing values or missing relationships.
Details about these advanced constructs are present in Appendix B. A snippet
of the learned program is shown in Figure 7.

$\displaystyle\%Entities$ $\displaystyle\mathtt{account(a\\_10001)\sim
val(true).}$ $\displaystyle\mathtt{loan(l\\_7034)\sim val(true).}$
$\displaystyle\mathtt{client(c\\_12303)\sim val(true).}$
$\displaystyle\mathtt{district(d\\_24)\sim val(true).}$
$\displaystyle\mathtt{\dots}$ $\displaystyle\%Relations$
$\displaystyle\mathtt{clientLoan(c\\_12303,l\\_7034)\sim val(true).}$
$\displaystyle\mathtt{hasLoan(a\\_10001,l\\_7034)\sim val(true).}$
$\displaystyle\mathtt{hasAccount(c\\_12303,a\\_10001)\sim val(true).}$
$\displaystyle\mathtt{clientDistrict(c\\_12303,d\\_24)\sim val(true).}$
$\displaystyle\mathtt{\dots}$ $\displaystyle\%Model$
$\displaystyle\mathtt{loanAmount(L)\sim
gaussian(151080.0,12853887266.5)\leftarrow loan(L)\cong true.}$
$\displaystyle\mathtt{\dots}$ $\displaystyle\mathtt{stdMonthInc(A)\sim
gaussian(M,36225870.62)\leftarrow account(A)\cong true,avgSumOfW(A)\cong
X,avgNrWith(A)\cong Y,avg(Z1,(hasLoan(A,L)\cong true,}$
$\displaystyle\qquad\mathtt{loanAmount(L)\cong Z1),Z),freq(A)\cong
m,linear([X,Y,Z],[0.34,-516.12,0.004,12797.18],M).}$
---
Figure 7: A snippet of the program learned from the financial data set. The
aggregation atom $\mathtt{avg(\\_,\\_,\\_)}$ in the body of the last clause
collects all loans’ amounts that a client has into a list and unifies
$\mathtt{Z}$ with the average of the list. The statistical model atom
$\mathtt{linear(\\_,\\_,\\_)}$ implements a linear function $\mathtt{M\ is\
0.34\times X-516.12\times Y+0.004\times Z+12797.18}$. Predicates like
$\mathtt{loanAmount/1,stdMonthInc/1,\dots,}$ represent the attributes of
entities.

Next, we created multiple subsets of the financial data set with varying
numbers of accounts. These subsets were created by considering
$\mathtt{account}$ to be the central entity. All information about clients,
loans, and districts related to an account appeared in the same subset. All
subsets had an account $\mathtt{a\\_10001}$ that was linked with a loan
$\mathtt{l\\_7034}$. Two queries to the learned program were considered: i)
$Q_{3}=P$($\mathtt{stdMonthInc(a\\_10001)\cong X,X>22000.0}$) given the rest
subsets of data, ii) $Q_{4}=P$($\mathtt{loanAmount(l\\_7034)\cong
X,X>20000.0}$) given the rest subsets of data. Figure 6 shows the comparison
of estimates obtained for queries $Q_{3}$ and $Q_{4}$. The old-DC suffered
arithmetic underflow as observed data increased, whereas FO-CS-LW scaled quite
well. An important observation is that the execution time of FO-CS-LW does not
increase by adding more data. This is because real-world data is often not
highly relational, e.g., clients generally have one or two accounts, not ten
accounts. This is the case here. By adding more data, we are just adding data
irrelevant to account $\mathtt{a\\_10}$. FO-CS-LW that exploits CIs can detect
that, but the old-DC inference engine can not.

Thus, when a significant amount of independencies are present in hybrid
relational probabilistic models, FO-CS-LW outperforms the state-of-the-art
inference algorithm of Old-DC.

##  8 Related Work

We describe relationships of the DC# framework introduced here with previous
works in terms of representation and inference.

###  8.1 Relation to Representation Languages

Several relational representation languages based on aggregation functions and
combining rules have been introduced in the past. Examples include
probabilistic relational models (?, PRMs), directed acyclic probabilistic
entity-relationship models (?, DAPER), probabilistic relational language (?,
PRL), Bayesian logic programs (?, BLPs), and first-order conditional influence
language (?, FOCIL). These languages consist of two components: a qualitative
component representing the relational structure of the domain (either using
graphs or definite clauses) and a quantitative component specifying
conditional probability distributions (CPDs) in the tabular form. So, they do
not qualitatively represent the structures present within the CPDs.

A tree or a rule-based representation lets us represent the structures
qualitatively (?, ?, ?). That is why, probabilistic logic programming (PLP)
has received much attention. Over the past three decades, many PLP languages
have been proposed: PHA (?), Prism (?), LPADs (?), ProbLog (?), ICL (?), CP-
Logic (?). However, only a few of them support both discrete and continuous
RVs: HProbLog (?), DC (?, ?), Extended-Prism (?), Hybrid-cplint (?), (?).
Nonetheless, the hybrid PLPs that have been studied in the past do not support
combining rules, which is a core component of PLPs. BLPs do support combining
rules, but then they do not qualitatively represent the structures. The syntax
of DC# is the same as the syntax of DC introduced by (?), but the semantics is
different as DC# supports combining rules. The semantics of DC# is based on
BLPs, so one can view DC# programs as BLPs qualitatively representing
structures. Furthermore, a huge fragment of Problog programs, one of the most
popular PLPs, is expressible as DC# programs. Annotated disjunctions and
directed cycles are not supported in DC# currently.

DC# is a probabilistic programming language (PPL); thus, we should also
describe how DC# relates to various other PPLs that generally extends
imperative programming with probability distributions such as Infer.NET (?),
BLOG (?), Stan (?), etc. DC# relates to these languages in the manner similar
to how logic programming relates to imperative programming. One must use if-
then conditions in these languages to express the structures and for loops to
express aggregations/combining rules. Using statistical model atoms in the
body of DCs, one can describe complex probabilistic models written in these
languages. However, DC# currently does not support writing open-universe
models that some PPLs, such as BLOG, support. On the other hand, it is unclear
how to write DC programs with negations in these PPLs, which is important when
dealing with missing data.

###  8.2 Relation to Inference Algorithms

Resolving representation issues does not quickly imply that crucial issues
inherent to inference are also resolved. The prime focus of past works on
relational representation languages, for example, those discussed at the
beginning of the previous section, has been the development of syntax and
semantics so that these languages succinctly represent first-order
probabilistic models. For inference, most of them construct ground BNs and
rely on inference algorithms for BNs. Thus, they do not exploit symmetrical
parameters that arise due to grounding the first-order models. Indeed they do
not exploit structures present within CPDs of ground BNs since they do not
even qualitatively represent them.

The case of the related PPLs is quite surprising. A remarkable feature of PPLs
is that the structures can be represented using if-then conditions in
programs. However, equivalent BNs are constructed during inference, and
algorithms for BNs are used; thus, CSIs implied by the structures are ignored.
For example, Stan, the most popular PPLs that is also commercially used, does
that. Interestingly, BLOG (?) does exploit CSIs, but a different class of
CSIs, CSIs that arise in open-universe models due to the addition and
subtraction of some RVs from the model when some other RVs take certain
values. It does not exploit those that are implied by if-then conditions even
in closed-universe models/programs. The exploitation of such CSIs and
symmetrical parameters that appear after unrolling (similar to grounding in
relational models) for loops even in closed-universe PPLs are not well
studied.

Leaving expressive languages aside, the exploitation of CSIs implied by
structures within CPDs of ground BNs is itself a difficult problem that has
puzzled researchers for decades. Research in this direction has mainly been
focused on exact inference (?, ?). Nowadays, it is common to use knowledge
compilation-based exact inference for this purpose (?, ?, ?); however, this
approach does not apply to hybrid models. The problem of exploiting CSIs in
hybrid models is non-trivial and is poorly studied. Recently, it has attracted
some attention (?). However, proposed approaches are also exact and rely on
complicated weighted model integration (?), which do not scale. CS-LW that we
propose for BNs is simple, scalable, and applies to hybrid BNs.

FO-CS-LW that extends CS-LW to first-order DC# programs also exploits
symmetries in such programs. So, it makes sense to relate FO-CS-LW with the
literature of lifted inference algorithms that aim to exploit symmetries in
first-order models. Broadly these algorithms can be divided into two
categories. Firstly, those that exploit symmetries but do not exploit CSIs.
Belonging to this category, there are exact (?, ?, ?, ?, ?) and approximate
algorithms (?, ?, ?). Belonging to the second category are those that also
exploit CSIs. These algorithms are generally exact and do not easily apply to
hybrid models (?, ?). Recently, an exact inference algorithm belonging to the
second category was applied to hybrid models (?). However, this algorithm
inherits the problem of weighted model integration, i.e., scalability. It is
well known that exact lifted inference has two major limitations: i) only a
small class of models is liftable (?, ?); ii) the inference is hard when
binary relations are observed (?). FO-CS-LW belongs to the second category of
algorithms, which is approximate thus does not have these limitations. It
applies to DC# language in which a larger class of models can be written,
which is remarkable.

##  9 Future Work

Our paper intends to introduce an interesting probabilistic programming
framework that can be further developed in the future. Several features can be
added to this framework, which are discussed next.

The semantics of DC# can be extended to support open-universe models. The
syntax already supports them, which was shown at the beginning of Section 4.2.
One can borrow ideas from BLOG for this purpose (?). However, extending FO-CS-
LW to the language supporting open-universe models will require solving a
complex problem: how to detect requisite networks in such models while
sampling? To detect them in closed-universe models, RV and dependency sets are
automatically constructed by static analysis of programs as discussed in this
paper; however, it is difficult to construct such sets for open-universe
models as it might require dynamic analysis.

Our algorithm does not support inference in DC# programs specifying mixtures
of discrete and continuous distributions. This is the case when some clauses
state that an RV is distributed according to continuous distributions, while
others state that the same RV is distributed according to discrete
distributions. More precisely, suppose a program contains the following two
clauses:

$\displaystyle\mathtt{credit\\_score(C)\sim gaussian(700,10.9)\leftarrow
has\\_loan(C,L)\cong true.}$ $\displaystyle\mathtt{credit\\_score(C)\sim
discrete([0.9:600,0.1:650])\leftarrow has\\_loan(C,L)\cong false.}$

It is not clear whether the client’s credit score is of discrete type or
continuous type. Likelihood weighting (LW) based algorithms do not estimate
correct probabilities in such a case. To resolve this issue, (?) proposed
lexicographic LW. A context-specific variant of the lexicographic LW is needed
for such programs. This has been left for the future.

As shown in Example 7, the $\mathtt{val(.)}$ functor in DC# provides an
elegant way of describing deterministic dependencies (constraints) among RVs
in probabilistic models (?). It is, however, well known that sampling
algorithms, in general, perform poorly when a significant amount of
determinism is present in models. So, an important and interesting avenue for
future work is to combine constraint propagation with FO-CS-LW.

Finally, we aim to open up a new direction towards improved sampling
algorithms that exploit CSIs. Like LW, we believe MCMC algorithms can also be
extended along the same line.

##  10 Conclusion

We have introduced a hybrid PLP framework called DC#. It supports combining
rules required to describe relational models succinctly.

We have emphasized the exploitation of both CIs and CSIs for efficient
inference. After realizing that a sampling algorithm that can properly do that
is not well studied, we studied the role of CSIs in sampling. Subsequently, we
introduced a notion of contextual assignment to show that CSIs allow for
breaking the main problem of estimating conditional probability queries into
several small problems that can be estimated independently. Based on this
notion, we presented CS-LW that exploits CSIs implied by structures present
within CPDs of BNs. We empirically showed that when a significant amount of
structures are present, CS-LW generates samples faster than the standard LW
and provides a better estimate of the query with much fewer samples.

Since CS-LW is based on theorem proving, we easily extended it with
unification and substitution of logical variables for inference in first-order
DC# programs. The resulting first-order inference algorithm, called FO-CS-LW,
naturally exploits symmetries or ICIs that arise due to combining rules in
programs.

Empirical results showed that FO-CS-LW scales with the domain size and
outperforms the inference algorithm of the state-of-the-art hybrid PLP.

Acknowledgments

This work has received funding from the European Research Council (ERC) under
the European Union’s Horizon 2020 research and innovation programme (grant
agreement No [694980] SYNTH: Synthesising Inductive Data Models).

## References

  * Ahmadi, et al. Ahmadi, B., Kersting, K., Mladenov, M., & Natarajan, S. (2013).  Exploiting symmetries for scaling loopy belief propagation and relational training.  Machine Learning, 92, 91–132.
  * Alberti, et al. Alberti, M., Bellodi, E., Cota, G., Riguzzi, F., & Zese, R. (2017).  cplint on swish: Probabilistic logical inference with a web browser.  Intelligenza Artificiale, 11(1), 47–64.
  * Beame, et al. Beame, P., Van den Broeck, G., Gribkoff, E., & Suciu, D. (2015).  Symmetric weighted first-order model counting.  In Proceedings of the 34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pp. 313–328.
  * Belle, Passerini, & Van Den Broeck Belle, V., Passerini, A., & Van Den Broeck, G. (2015).  Probabilistic inference in hybrid domains by weighted model integration.  In Proceedings of the 24th International Conference on Artificial Intelligence, IJCAI’15, p. 2770–2776.
  * Boutilier, et al. Boutilier, C., Friedman, N., Goldszmidt, M., & Koller, D. (1996).  Context-specific independence in bayesian networks.  In Proceedings of the Twelfth international conference on Uncertainty in artificial intelligence, pp. 115–123. Morgan Kaufmann Publishers Inc.
  * Chavira & Darwiche Chavira, M., & Darwiche, A. (2008).  On probabilistic inference by weighted model counting.  Artificial Intelligence, 172(6-7), 772–799.
  * Chen, et al. Chen, Y., Yang, Y., Natarajan, S., & Ruozzi, N. (2020).  Lifted hybrid variational inference.  In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pp. 4237–4244.
  * Choi, Braz, & Bui Choi, J., Braz, R. d. S., & Bui, H. H. (2011).  Efficient methods for lifted inference with aggregate factors.  In Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, AAAI’11, p. 1030–1036. AAAI Press.
  * Corander, et al. Corander, J., Hyttinen, A., Kontinen, J., Pensar, J., & Väänänen, J. (2019).  A logical approach to context-specific independence.  Annals of Pure and Applied Logic, 170(9), 975–992.
  * Darwiche & Marquis Darwiche, A., & Marquis, P. (2002).  A knowledge compilation map.  Journal of Artificial Intelligence Research, 17, 229–264.
  * De Raedt, et al. De Raedt, L., Kersting, K., Natarajan, S., & Poole, D. (2016).  Statistical relational artificial intelligence: Logic, probability, and computation.  Synthesis Lectures on Artificial Intelligence and Machine Learning, 10(2), 1–189.
  * De Raedt & Kimmig De Raedt, L., & Kimmig, A. (2015).  Probabilistic (logic) programming concepts.  Machine Learning, 100(1), 5–47.
  * De Raedt, Kimmig, & Toivonen De Raedt, L., Kimmig, A., & Toivonen, H. (2007).  Problog: A probabilistic prolog and its application in link discovery.  In Proceedings of the 20th International Joint Conference on Artifical Intelligence, IJCAI’07, p. 2468–2473.
  * De Salvo Braz, Amir, & Roth De Salvo Braz, R., Amir, E., & Roth, D. (2006).  Mpe and partial inversion in lifted probabilistic variable elimination.  In Proceedings of the 21st National Conference on Artificial Intelligence - Volume 2, AAAI’06, p. 1123–1130.
  * Elidan Elidan, G. (2001).  Bayesian Network Repository..  https://www.cse.huji.ac.il/ galel/Repository/.
  * Feldstein & Belle Feldstein, J., & Belle, V. (2021).  Lifted reasoning meets weighted model integration.  In 37th Conference on Uncertainty in Artificial Intelligence.
  * Fierens, et al. Fierens, D., Van den Broeck, G., Renkens, J., Shterionov, D., Gutmann, B., Thon, I., Janssens, G., & De Raedt, L. (2015).  Inference and learning in probabilistic logic programs using weighted boolean formulas.  Theory and Practice of Logic Programming, 15(3), 358–401.
  * Friedman, et al. Friedman, N., Getoor, L., Koller, D., & Pfeffer, A. (1999).  Learning probabilistic relational models.  In Proceedings of the 16th International Joint Conference on Artificial Intelligence - Volume 2, IJCAI’99, p. 1300–1307.
  * Friedman & Van Den Broeck Friedman, T., & Van Den Broeck, G. (2018).  Approximate knowledge compilation by online collapsed importance sampling.  In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS’18, p. 8035–8045.
  * Getoor, et al. Getoor, L., Friedman, N., Koller, D., Pfeffer, A., & Taskar, B. (2007).  Probabilistic relational models.  Introduction to statistical relational learning, 8.
  * Getoor & Grant Getoor, L., & Grant, J. (2006).  Prl: A probabilistic relational language.  Machine Learning, 62(1), 7–31.
  * Getoor & Taskar Getoor, L., & Taskar, B. (2007).  Lifted first-order probabilistic inference.  In Statistical Relational Learning.
  * Gogate & Domingos Gogate, V., & Domingos, P. M. (2011).  Probabilistic theorem proving.  Communications of the ACM, 59, 107 – 115.
  * Gutmann, Jaeger, & De Raedt Gutmann, B., Jaeger, M., & De Raedt, L. (2010).  Extending problog with continuous distributions.  In International Conference on Inductive Logic Programming, Vol. 6489 of Lecture Notes in Computer Science, pp. 76–91. Springer.
  * Gutmann, et al. Gutmann, B., Thon, I., Kimmig, A., Bruynooghe, M., & De Raedt, L. (2011).  The magic of logical inference in probabilistic programming.  Theory and Practice of Logic Programming, 11(4-5), 663–680.
  * Heckerman, Meek, & Koller Heckerman, D., Meek, C., & Koller, D. (2004).  Probabilistic models for relational data.  Tech. rep., Technical Report MSR-TR-2004-30, Microsoft Research.
  * Islam, Ramakrishnan, & Ramakrishnan Islam, M. A., Ramakrishnan, C., & Ramakrishnan, I. (2012).  Inference in probabilistic logic programs with continuous random variables.  Theory and Practice of Logic Programming, 12(4-5), 505–523.