10 May 2021 Non-ground Abductive Logic Programming with Probabilistic
Integrity Constraints–References

# Non-ground Abductive Logic Programming with Probabilistic Integrity
Constraints

Elena Bellodi  Marco Gavanelli  Riccardo Zese  Evelina Lamma
Department of Engineering - University of Ferrara  Fabrizio Riguzzi
Department of Mathematics and Computer Science - University of Ferrara

(2021)

###### Abstract

Uncertain information is being taken into account in an increasing number of
application fields. In the meantime, abduction has been proved a powerful tool
for handling hypothetical reasoning and incomplete knowledge. Probabilistic
logical models are a suitable framework to handle uncertain information, and
in the last decade many probabilistic logical languages have been proposed, as
well as inference and learning systems for them. In the realm of Abductive
Logic Programming (ALP), a variety of proof procedures have been defined as
well. In this paper, we consider a richer logic language, coping with
probabilistic abduction with variables. In particular, we consider an ALP
program enriched with integrity constraints à la IFF, possibly annotated with
a probability value. We first present the overall abductive language, and its
semantics according to the Distribution Semantics. We then introduce a proof
procedure, obtained by extending one previously presented, and prove its
soundness and completeness. This paper is under consideration for acceptance
in TPLP.

###### doi:

S1471068401001193

###### keywords:

Abduction, Integrity Constraints, Distribution Semantics, Probabilistic IFF

##  1 Introduction

Reasoning in uncertain domains is a common task for humans, and the human
brain also has the capability to explore different scenarios by considering a
variety of possible hypotheses, in order to take a decision. The ability of
the human brain, and human expertise in specific domains, meant that humans
were not replaceable by a machine in their reasoning tasks, so far.
Nonetheless, in the last decade, the huge increase of available data and
knowledge in many domains (e.g., in medicine, science, physics, etc.), often
in a form that can be processed automatically, strongly pushes towards forms
of automatic reasoning able to cope with uncertainty, probabilities and
hypotheses, also in order to have reasoning systems facing humans, and to
achieve a more reproducible (and verifiable) behaviour. This is definitively a
strong commitment for a trustworthy Artificial Intelligence. Logic Programming
(LP) is a powerful class of languages to be a candidate for this purpose. The
language itself is human-readable, and knowledge expressed in this class of
languages can be validated by humans. Standard LP syntax, and LP-based
reasoning is the base for a variety of more expressive languages, and proof
procedures. In particular, Probabilistic Logic Programming (PLP) [De Raedt and
Kersting (2008)] languages are simple yet powerful enough to represent
different scenarios [Azzolini et al. (2019), Nguembang Fadja and Riguzzi
(2017)]. Several of these languages are based on the distribution semantics
[Sato (1995)], such as PRISM [Sato (1995)], LPAD [Vennekens et al. (2004)],
and ProbLog [De Raedt et al. (2007)].

In the meantime, Abductive Logic Programming (ALP) [Kakas et al. (1998)] has
been proven very effective for hypothetical reasoning and for formalizing a
variety of domains and applications, ranging from diagnosis to societies of
agents and accountable protocols for multi-agent systems, commitments and
normative systems, web service choreographies. ALP is based on a declarative
(model-theoretic) semantics and equipped with an operational semantics in
terms of a proof-procedure. The IFF proof-procedure was proposed by IFF to
support abductive reasoning also in presence of non-ground abducible literals.

In this paper we consider a richer logic language, coping with probabilistic
abduction with variables. In particular, we consider an ALP program featuring
also Integrity Constraints similar to those offered by IFF, extended by the
possibility of annotating them with a probability value, that makes it
possible to handle uncertainty of real world domains. Probabilistic integrity
constraints were defined by RigBelZesAlbLam20-ML-IJ: programs containing such
constraints are called Probabilistic Constraint Logic Theories (PCLTs) and may
be learned directly from data by means of PASCAL (“ProbAbiliStic inductive
ConstrAint Logic”), a system that learns both their structure and parameters
from interpretations. However, a system able to reason about these integrity
constraints is still missing. Consider the following example.

######  Example 1 (label=exa:running)

Several years ago, a murder in Italy captured the attention of the population:
a woman was murdered, and the main indicted person was her husband. The
collected evidence included the following facts: the woman was killed in the
house where she lived with her husband (house1); a pillow stained with the
blood of the victim was found in another house (house2) some hundreds of km
away; the husband had the keys of this second house.
We can represent the facts listed above in the following knowledge base:

⬇

has_keys(husband,house1).

has_keys(husband,house2).

The goal is to find the murderer $M$, i.e., the person who entered both houses
and killed the victim:

⬇

$G={\texttt{{enter}(M,house1)}},{\texttt{{killed}(M,woman)}},{\texttt{{enter}(M,house2)}}.$

Predicates killedand enterare not known in the knowledge base, and they must
be hypothesized: in ALP they are considered abducibles (in this paper,
abducibles are in italic). Notice that this problem requires non-ground
abduction, since the murderer $M$ is unknown, and it is not even possible to
list all the possible murderers.

The relationship between having the keys and entering a house can be stated
through an integrity constraint

${\texttt{{enter}(P,H)}}\rightarrow has\\_keys(P,H).$ ($ic_{1}$)

saying that if a person P enters a house H, (s)he must have the keys.

However, the information encoded in $ic_{1}$ is not 100% sure: a person could
also enter the house without having the keys, e.g., by breaking a window or
picking the lock of the door. The encoding would be more faithful to reality
if a probability was associated to $ic_{1}$. The probability that $ic_{1}$
does not hold would be quite low, since entering with the keys is much easier
than with unlawful methods, in which the intruder could be noticed and
arrested.

Most previous works proposing probabilistic abductive logic programming have
considered only abduction of ground atoms [Poole (1993), Arvanitis et al.
(2006), Inoue et al. (2009), Kate and Mooney (2009), Raghavan (2011), Turliuc
et al. (2013), Rotella and Ferilli (2013)]. To the best of our knowledge, only
DBLP:series/lncs/Christiansen08 focused on probabilistic non-ground abduction,
and this clearly extends the expressiveness of the language, as well as the
answer capabilities of the proof-procedure: as a matter of fact, non-ground
abduction can provide answers in which not all parts of the answer are
completely defined, and in which possible hypotheses, for some given evidence,
are assumed without complete knowledge. This more closely resembles the
capabilities of the human brain, that is able to hypothesize the existence of
some action, force or individual causing an effect even without complete
knowledge of whom, or which force is responsible. On the other hand, the
proof-procedure by DBLP:series/lncs/Christiansen08 considers only a limited
form of negation and assigns probabilities only to abducibles. In our work,
instead, we extend ALP to give the possibility to probabilistically annotate
integrity constraints to enrich the standard semantics. This leads to a
probabilistic ALP reasoning system that clearly improves on existing systems
such as the one by Christiansen, since annotating ICs also allows one to
obtain the same effect of adding probabilities to abducibles. Moreover,
machine learning systems already exist that learn probabilistic integrity
constraints from data in the same form proposed in this paper, such as the
aforementioned PASCAL, however, no abductive logic programming reasoning
system existed before to exploit the learned constraints: in this paper we
fill this gap.

The paper is organized as follows. Sect. 2 introduces information about the
IFF semantics necessary for understanding Sect. 3 and 4 that discuss language,
syntax, and semantics of the proposed probabilistic non-ground abduction
proof-procedure, called ${\mbox{IFF}}^{\mathit{Prob}}$. Sect. 5 proves
soundness and completeness of ${\mbox{IFF}}^{\mathit{Prob}}$, while Sect. 6
describes its implementation and Sect. 7 discusses some real world application
examples. Sect. 8 shows preliminary scalability tests. Sect. 9 presents
related work and Sect. 10 concludes the paper.

##  2 Background

####  IFF Declarative Semantics.

A IFF [Fung and Kowalski (1997)] program is a triple
${\langle{\textbf{KB}},{\textbf{IC}},{\mathcal{A}}\rangle}$. ${\mathcal{A}}$
is a set of _abducible predicates_ , or simply abducibles. An abducible is a
predicate about which it is possible to make assumptions, such as about its
truth. An abducible atom is an atom built on an abducible predicate. In this
work, abduced literals can contain variables, that are implicitly
existentially quantified. KB is a set of logic programming clauses of the form

$h\leftarrow b_{1},\dots,b_{m}$

where $m\geq 0$, and each $b_{i}$ with $1\leq i\leq m$ is a literal (i.e., an
atom or its negation), while $h$ is an atom that cannot be built on a
predicate in ${\mathcal{A}}$. $h$ is called _head_ , while $b_{1},\dots,b_{m}$
is called the _body_ of the clause.

IC is a set of implications, called Integrity Constraints (ICs). Each
${ic}\in{\textbf{IC}}$ has the form

$b_{1},\dots,b_{n}\rightarrow H_{1}\vee\dots\vee H_{k}$

where $b_{1},\dots,b_{n}$ is a conjunction of atoms called $Body$ of the IC
$ic$, while the disjunction $H_{1}\vee\dots\vee H_{k}$ is called the $Head$.
Each $H_{i}$ with $1\leq i\leq k$ is a conjunction of literals
$h_{1},\dots,h_{l}$.

A goal $G$ is a conjunction of literals of the form $g_{1},\dots,g_{m}$ with
$m\geq 1$.

To define the abductive semantics, we need to recall some definitions. An IC,
clause or abducible is _ground_ if it does not contain variables. A
_substitution_ $\theta$ is an assignment of variables to terms:
$\theta=\\{V_{1}/t_{1},\ldots,V_{n}/t_{n}\\}$. The application of a
substitution $\theta=\\{V_{1}/t_{1},\ldots,V_{n}/t_{n}\\}$ to an IC ${ic}$,
indicated with ${ic}\theta$, is the replacement of each variable $V_{i}$
appearing in ${ic}$ and in $\theta$ with $t_{i}$. ${ic}\theta$ is called an
_instance_ of ${ic}$. $\theta$ is _grounding_ for ${ic}$ if ${ic}\theta$ is
ground. The same applies to clauses and abducibles as well.

The IFF abductive semantics defines an abductive answer to a goal $G$ as a
pair $(\Delta,\theta)$, where $\Delta$ is a set of abducible atoms and
$\theta$ is a substitution for the variables contained in $G$, such that

$\begin{split}{\textbf{KB}}\cup\Delta&\models{\textbf{IC}}\>\>\>\qquad\text{and}\\\
{\textbf{KB}}\cup\Delta&\models G\theta\end{split}$ (1)

where $\models$ is entailment according to the 3-valued completion semantics
[Kunen (1987)], i.e., we require that every 3-valued models of the completion
[Clark (1978)] of ${\textbf{KB}}\cup\Delta$ is also a 3-valued model of IC. In
such a case, we write $ALP\models^{\Delta}G$. Variables in $G$ are free, the
remaining variables in $\Delta$ are existentially quantified, while variables
in KB and IC are implicitly universally quantified with scope the entire
implication.

RigBelZesAlbLam20-ML-IJ introduce (although not in the context of ALP) the
concept of Probabilistic Integrity Constraint (PIC)

$p_{i}\ ::\ Body\rightarrow Head$ (2)

where $p_{i}$ is a probability $\in[0,1]$.

##  3 ${\mbox{IFF}}^{\mathit{Prob}}$ Syntax and Declarative Semantics

${\mbox{IFF}}^{\mathit{Prob}}$ programs define a probability distribution over
IFF programs inspired by the distribution semantics proposed in the field of
Probabilistic Logic Programming [Sato (1995)]. A
${\mbox{IFF}}^{\mathit{Prob}}$ program, similarly to IFF, is a triple
$ALP_{p}=\langle{\textbf{KB}},{\textbf{IC}},{\mathcal{A}}\rangle$, however, in
this case, the set IC is defined as
${{\textbf{IC}}^{p}}\cup{{\textbf{IC}}^{np}}$, where ${{\textbf{IC}}^{p}}$ is
a set of PICs as in Eq. 2 while ${{\textbf{IC}}^{np}}$ is a set of (non-
probabilistic) ICs as in the IFF.

It is worth noting that associating probabilities to ICs makes
${\mbox{IFF}}^{\mathit{Prob}}$ more general than other frameworks
[Christiansen (2008)] in which probabilities are attached to abducibles, since
the fact that abducible a has probability $p$ can be simply expressed by the
PIC

$(1-p)::{\texttt{{a}}}\rightarrow\mathit{false}.$

A ${\mbox{IFF}}^{\mathit{Prob}}$ program
$T={\langle{\textbf{KB}},{\textbf{IC}},{\mathcal{A}}\rangle}$ defines a
probability distribution over IFF programs called _worlds_ where the
constraints set includes each ${ic}\in{{\textbf{IC}}^{np}}$, and some
instances of any ${ic}\in{{\textbf{IC}}^{p}}$ included with probability
$p_{i}$.

An _atomic choice_ is a triple $({ic}_{i},\theta_{j},k)$ where ${ic}_{i}$ is
the $i$-th PIC, $\theta_{j}$ is a substitution for the variables in
${ic}_{i}$, and $k\in\\{0,1\\}$ indicates whether ${ic}_{i}\theta_{j}$ is
chosen to be included in a world ($k$ = 1) or not ($k$ = 0). A _composite
choice_ ${{E}}$ is a consistent set of atomic choices, where _consistent_
means that ${{E}}$ does not contain two atomic choices
$({ic}_{i},\theta_{j},k),({ic}_{i},\theta_{j},m)$ with $k\neq m$, i.e.,
$({ic}_{i},\theta_{j},k)\in{{E}},({ic}_{i},\theta_{j},m)\in{{E}}\Rightarrow
k=m$ (only one decision for each instance of each PIC).

The probability of a composite choice ${{E}}$ is

$P({{E}})=\prod_{({ic}_{i},\theta_{j},1)\in{{E}}}p_{i}\prod_{({ic}_{i},\theta_{j},0)\in{{E}}}(1-p_{i})$

where $p_{i}$ is the probability associated with PIC ${ic}_{i}$.

A _selection_ $\sigma$ is a _total_ composite choice, i.e., it contains an
atomic choice for every instance up to renaming of every PIC of the
${\mbox{IFF}}^{\mathit{Prob}}$ program. Given a selection $\sigma$, the world
${\mathcal{W}}_{\sigma}$ is defined as
${\mathcal{W}}_{\sigma}=\\{{ic}_{i}\theta_{j}|({ic}_{i},\theta_{j},1)\in\sigma\\}$.
Let us indicate with $\mathcal{S}_{T}$ the set of all selections and with
${{\mathcal{W}}_{T}}$ the set of all worlds. The probability of a world
${\mathcal{W}}_{\sigma}$ is $P({\mathcal{W}}_{\sigma})=P(\sigma)$.
$P({\mathcal{W}}_{\sigma})$ is a probability distribution over worlds, i.e.,
$\sum_{{\mathcal{W}}\in{{\mathcal{W}}_{T}}}P({\mathcal{W}})=1$.

Given a world $\mathcal{W}$, the conditional probability that a goal $G$ is
satisfied in the world is defined as $P(G|{\mathcal{W}})=1$ if
$\exists\Delta\langle{\textbf{KB}},{\mathcal{W}},{\mathcal{A}}\rangle\models^{\Delta}G$
and 0 otherwise. Given a goal $G$, its probability $P(G)$ can be defined by
marginalizing the joint probability of the goal and the worlds:

$\displaystyle P(G)$ $\displaystyle=$
$\displaystyle\sum_{{\mathcal{W}}\in{{\mathcal{W}}_{T}}}P(G,{\mathcal{W}})=\sum_{{\mathcal{W}}\in{{\mathcal{W}}_{T}}}P(G|{\mathcal{W}})P({\mathcal{W}})=\sum_{{\mathcal{W}}\in{{\mathcal{W}}_{T}}:{\mathcal{W}}\models
G}P({\mathcal{W}})$

Therefore, the probability of a goal $G$ can be computed by summing the
probability of the worlds where the goal is true.

Given a goal $G$ to solve, an _explanation_ is a composite choice ${{E}}$ for
$G$ such that $G$ is entailed by every world of $\omega_{{E}}$, where
$\omega_{{E}}=\\{{\mathcal{W}}_{\sigma}|\sigma\in\mathcal{S}_{T},\sigma\supseteq{{E}}\\}$
is the set of worlds compatible with ${{E}}$.

We also define the set of worlds identified by a set of explanations
${{\mathcal{E}}}$ as
$\omega_{{\mathcal{E}}}=\bigcup_{{{E}}\in{{\mathcal{E}}}}\omega_{{E}}$. A set
of explanations ${{\mathcal{E}}}$ is _covering_ with respect to $G$ if every
world ${\mathcal{W}}\in{{\mathcal{W}}_{T}}$ in which $G$ is entailed is such
that ${\mathcal{W}}\in\omega_{{\mathcal{E}}}$. Two explanations ${{E}}_{1}$
and ${{E}}_{2}$ are _incompatible_ if their union is inconsistent, i.e., given
a PIC $ic$ and a substitution $\theta$, the explanations
${{E}}_{1}=\\{({ic},\theta,1)\\}$ and ${{E}}_{2}=\\{({ic},\theta,0)\\}$ are
incompatible. A set ${\mathcal{E}}$ is pairwise incompatible if for all
${{E}}_{1}\in{{\mathcal{E}}}$, ${{E}}_{2}\in{{\mathcal{E}}}$,
${{E}}_{1}\neq{{E}}_{2}$ implies ${{E}}_{1}$ and ${{E}}_{2}$ are incompatible.
The probability of a pairwise incompatible set of explanations ${\mathcal{E}}$
is defined as $P({{\mathcal{E}}})=\sum_{{{E}}\in{{\mathcal{E}}}}P({{E}})$.

######  Definition 1 (Probabilistic Abductive Answer)

Given an $ALP_{p}$, $(\Delta,\theta)$ is a probabilistic abductive answer for
a goal $G$ in the explanation ${{E}}$ if

$\begin{array}[]{rrcl}&{\textbf{KB}}\cup\Delta&\models&G\theta\\\
&{\textbf{KB}}\cup\Delta&\models&{{\textbf{IC}}^{np}}\\\
\forall(ic_{i},\theta_{j},1)\in{{E}},&{\textbf{KB}}\cup\Delta&\models&ic_{i}\theta_{j}\\\
\end{array}$

In such a case, we write $ALP_{p}\models^{\Delta}_{{E}}G$.

######  Example 2 (continues=exa:running)

We are now able to refine the previous example by associating a probability to
the IC saying that if a person P enters a house H, (s)he must have the keys:
such statement is uncertain, because it might be the case that an unauthorized
person is able to enter a house also without having the keys, although with a
lower probability, say 0.3:

$0.7::{\texttt{{enter}(P,H)}}\rightarrow has\\_keys(P,H).$ ($ic_{1}^{\prime}$)

##  4 ${\mbox{IFF}}^{\mathit{Prob}}$ Operational Semantics

####  IFF Operational Semantics.

Before defining the ${\mbox{IFF}}^{\mathit{Prob}}$ operational semantics, we
recap the IFF operational semantics [Fung and Kowalski (1997)].

The following is the subset of IFF transitions that are relevant for this
work, in a proof-theory style notation. In the following list, a is an
abducible atom, while $p$ and $q$ represent atoms of either abducible or
defined predicates, and $N$ is a set of arguments.

  * •

propagation
$\qquad\frac{{\texttt{{a}}}(N)\qquad{\texttt{{a}}}(N^{\prime}),B\rightarrow
H}{N=N^{\prime},B\rightarrow H}$

  * •

unfolding

$\displaystyle\frac{p(N)\qquad p(N^{\prime})\leftarrow B}{N=N^{\prime},B}$
$\displaystyle\frac{p(N)\rightarrow
H\qquad\begin{array}[]{l}p(N^{\prime})\leftarrow B^{\prime}\\\
p(N^{\prime\prime})\leftarrow B^{\prime\prime}\\\ \dots\\\ p(N^{k})\leftarrow
B^{k}\\\ \end{array}}{\begin{array}[]{l}N=N^{\prime},B^{\prime}\rightarrow
H\\\ N=N^{\prime\prime},B^{\prime\prime}\rightarrow H\\\ \dots\\\
N=N^{k},B^{k}\rightarrow H\\\ \end{array}}$

  * •

case analysis

$\displaystyle\frac{(N=N^{\prime},B)\rightarrow
H}{(N=N^{\prime}),\quad(B\rightarrow H)}$
$\displaystyle\qquad\frac{(N=N^{\prime},B)\rightarrow H}{N\neq N^{\prime}}$

  * •

equality rewriting

$\displaystyle\frac{[\exists E][\forall A]A=E}{\theta=\\{A/E\\}}$
$\displaystyle\frac{[\exists E][\forall A]A\neq E}{\mathit{false}}$
$\displaystyle\frac{[\exists E_{1}][\exists
E_{2}]E_{1}=E_{2}}{\theta=\\{E_{1}/E_{2}\\}}$
$\displaystyle\frac{X=t\qquad\mbox{$t$ does not contain
$X$}}{\theta=\\{X/t\\}}$ $\displaystyle\frac{X=t\qquad\mbox{$t$ contains
$X$}}{\mathit{false}}$ $\displaystyle\frac{X\neq t\qquad\mbox{$t$ contains
$X$}}{true}$
$\displaystyle\frac{p(t_{1},\dots,t_{n})=p(s_{1},\dots,s_{n})}{t_{1}=s1,\dots,t_{n}=s_{n}}$
$\displaystyle\frac{p(t_{1},\dots,t_{n})\neq p(s_{1},\dots,s_{n})}{t_{1}\neq
s1\lor\dots\lor t_{n}\neq s_{n}}$
$\displaystyle\frac{p(t_{1},\dots,t_{n})=q(s_{1},\dots,s_{m})\mbox{ where
}p\neq q\lor n\neq m}{\mathit{false}}$
$\displaystyle\frac{p(t_{1},\dots,t_{n})\neq q(s_{1},\dots,s_{m})\mbox{ where
}p\neq q\lor n\neq m}{true}$

where the substitution $\theta$ is added to the child node. In case two
variables with different quantifiers are unified, the new variable is
existentially quantified.

  * •

logical simplifications

$\frac{true\rightarrow A}{A}$ (3)

$\begin{array}[]{ccccc}\frac{\mathit{false}\rightarrow
A}{true}&\frac{true\land A}{A}&\frac{\mathit{false}\land
A}{\mathit{false}}&\frac{true\lor A}{true}&\frac{\mathit{false}\lor
A}{A}\end{array}$

  * •

factoring

$\begin{array}[]{cc}\frac{{\texttt{{a}}}(X)\quad{\texttt{{a}}}(Y)}{X=Y}&\frac{{\texttt{{a}}}(X)\quad{\texttt{{a}}}(Y)}{X\neq
Y}\end{array}$

####  ${\mbox{IFF}}^{\mathit{Prob}}$operational semantics.

We provide an extended version of the IFF operational semantics capable to
deal with probabilistic integrity constraints. We decorate each probabilistic
integrity constraint $ic$ with its original version and a substitution,
initially empty, $\theta_{\emptyset}$:

$ic^{ic\theta_{\emptyset}}$

The main transition that needs to be updated is the logical equivalence
$\frac{\mbox{true}\rightarrow A}{A}$ (Eq 3). Such a rule continues to exist
for non-probabilistic ICs, while for probabilistic ones it is replaced by the
following two rules:

$\displaystyle\frac{\left(p::true\rightarrow
A\right)^{ic_{i}\theta_{j}}\qquad{{E}}\qquad(ic_{i},\theta_{j},0)\not\in{{E}}}{A,\qquad{{E}}\cup\\{(ic_{i},\theta_{j},1)\\}}$
(4) $\displaystyle\frac{\left(p::true\rightarrow
A\right)^{ic_{i}\theta_{j}}\qquad{{E}}\qquad(ic_{i},\theta_{j},0)\not\in{{E}}}{{{E}}\cup\\{(ic_{i},\theta_{j},0)\\})}$
(5)

Intuitively, when the body of a PIC is proven true, its consequences are not
propagated in all possible explanations, but, instead, two alternative
explanations are generated: one in which the PIC is assumed to hold and its
consequences are propagated, while in the other the PIC is not assumed to hold
and the consequence $A$ is not derived.

The other transitions are unmodified, except for the decoration explained
earlier, e.g., Probabilistic Propagation becomes

$\frac{a(X)\qquad\left(p::a(Y),B\rightarrow
H\right)^{ic\theta}}{\left(p::X=Y,B\rightarrow H\right)^{ic\theta}}$

######  Definition 2 (Successful derivation)

Each node of a derivation has the form

$\langle R,\Delta,PSIC,{{E}},\theta\rangle$

where the goal still to be proven is partitioned into the set $R$ (Resolvent)
of non-abducible literals and the set $\Delta$ of abducible ones, $PSIC$ is a
set of (probabilistic and non-probabilistic) ICs that must hold, ${{E}}$ is
the current explanation, and $\theta$ is the current substitution.

A derivation is successful for a goal $G$ in an
$ALP={\langle{\textbf{KB}},{\textbf{IC}},{\mathcal{A}}\rangle}$ with
explanation ${E}$ if it starts from a node

$\langle G,\emptyset,IC,\emptyset,\emptyset\rangle$

and terminates in a node

$\langle\emptyset,\Delta,PSIC,{{E}},\theta\rangle$

where no transition is applicable. If such a derivation exists, we write

$ALP\vdash_{{{E}}}^{\Delta}G\theta$

######  Definition 3 (Computed Probability of a goal)

Let ${{\mathcal{E}}}=\\{{{E}}|ALP\vdash_{{{E}}}^{\Delta}G\\}$ be the
_covering_ pairwise incompatible set of explanations for the goal $G$, the
computed probability of $G$ is
$P(G)=P({{\mathcal{E}}})=\sum_{{{E}}\in{{\mathcal{E}}}}P({{E}})$.

##  5 Soundness and Completeness

######  Theorem 1 (Soundness)

If there exists a successful derivation $ALP\vdash^{\Delta}_{{E}}G\theta$,
then $ALP\models^{\Delta}_{{E}}G\theta$.

######  Proof 5.2.

Note that, with respect to the original IFF transitions, the new transitions
of ${\mbox{IFF}}^{\mathit{Prob}}$ only change the explanations, while all
remaining elements of each node of the proof tree remain as in IFF. In
particular, all non-probabilistic integrity constraints are handled as in IFF,
that is sound [Fung and Kowalski (1997)], so for each successful derivation
$ALP\vdash^{\Delta}_{{E}}G$, $KB\cup\Delta\models{{\textbf{IC}}^{np}}$ holds.

The only modification is probabilistic logical equivalence (Eq 4 and Eq 5), in
which a new branch is added: while in the original IFF proof-procedure, when
the condition of an IC is satisfied, the consequence is always added to the
node, for probabilistic ICs two mutually-exclusive branches are added to the
proof-tree.

In one branch, Eq 4 is applied and adds the atomic choice $(ic,\theta,1)$ to
${{E}}$. Note that no transition removes elements from ${E}$. In such a
branch, the consequent of $ic\theta$ is added to the resolvent and all the
following computation treats $ic\theta$ as a non-probabilistic integrity
constraint in IFF; this proves that for each $({ic},\theta,1)$ that is added
to ${{E}}$, $KB\cup\Delta\models ic\theta$.

In the other branch, Eq 5 is applied and the atomic choice $(ic,\theta,0)$ is
added to ${{E}}$. Notice that no transition can add an atomic choice
$(ic,\theta,k)$ to ${{E}}$ if $(ic,\theta,0)$ was already in ${{E}}$ (the set
${{E}}$ is always consistent). This proves that $(ic,\theta,1)$ will not be
added in the following part of the derivation to ${{E}}$.

######  Theorem 5.3 (Completeness).

If $ALP\models^{\Delta}_{{{E}}}G\theta$ then there exists a successful
derivation $ALP\vdash^{\Delta^{\prime}}_{{{E}}^{\prime}}G\theta$, where
$\Delta^{\prime}\subseteq\Delta$ and
$\forall(ic_{i},\theta_{j},1)\in{{E}}^{\prime}$,
$(ic_{i},\theta_{j},1)\in{{E}}$.

######  Proof 5.4.

Suppose that $ALP\models^{\Delta}_{{{E}}_{*}}G$, i.e., there is a
probabilistic abductive answer for a goal $G$, in an explanation ${{E}}_{*}$.
We leverage on the completeness theorem of the IFF proof-procedure [Fung and
Kowalski (1997)], crafting an IFF program in such a way that a
${\mbox{IFF}}^{\mathit{Prob}}$ derivation can be built with simple
replacements of transitions from the IFF derivation.

Let $IC({{E}}^{+}_{*})=\\{ic_{i}\theta_{j}|(ic_{i},\theta_{j},1)\in E_{*}\\}$;
consider the (non-probabilistic)

$ALP_{\not{p}}={\langle{\textbf{KB}},{(IC({{E}}^{+}_{*})\cup{\top({{\textbf{IC}}^{p}}\setminus
IC({{E}}^{+}_{*}))})|_{\not{p}}}\cup{{\textbf{IC}}^{np}},{\mathcal{A}}\rangle}$

where ${X|_{\not{p}}}=\\{ic|p::ic\in X\\}$ strips the probability annotation
from a set of probabilistic ICs $X$ and ${\top(X)}=\\{Body\rightarrow
true|Body\rightarrow Head\in X\\}$ replaces the $Head$ of a set of ICs with
$true$; clearly the last operation produces implications that are tautologies,
and are useless from a logical viewpoint, but that help us build the
${\mbox{IFF}}^{\mathit{Prob}}$ derivation.

From the completeness theorem of the IFF [Fung and Kowalski (1997)], we have
that there exists an IFF derivation $ALP_{\not{p}}\vdash^{\Delta^{\prime}}G$
where $\Delta^{\prime}\subseteq\Delta$. We build a successful
${\mbox{IFF}}^{\mathit{Prob}}$ derivation that mimics the IFF derivation,
where Eq 4 is applied to ICs in $IC({{E}}^{+}_{*})$, and in which Eq 5 is
applied to ICs in its complement, ${{\textbf{IC}}^{p}}\setminus
IC({{E}}^{+}_{*})$.

In the IFF derivation, the logical equivalence Eq 3 is possibly applied to
${{\top({{\textbf{IC}}^{p}}\setminus IC({{E}}^{+}_{*}))}|_{\not{p}}}$; we
substitute each application with the application of Eq 5. Such applications
have no other consequences beside adding elements $(ic_{i},\theta_{j},0)$ to
the ${E}$ set, where ${ic}_{i}\theta_{j}\in{{\textbf{IC}}^{p}}\setminus
IC({{E}}^{+}_{*})$.

Since ${\mbox{IFF}}^{\mathit{Prob}}$ may also have to apply propagation,
unfolding and case analysis to the ICs in ${{\textbf{IC}}^{p}}\setminus
IC({{E}}^{+}_{*})$, adding the set ${{\top({{\textbf{IC}}^{p}}\setminus
IC({{E}}^{+}_{*}))}|_{\not{p}}}$ to the integrity constraints of the IFF
program ensures that also the IFF derivation applies such transitions when
necessary.

In the IFF derivation, the logical equivalence $\frac{true\rightarrow A}{A}$
is (possibly) applied to ICs in ${IC({{E}}^{+}_{*})|_{\not{p}}}$. We
substitute each application of Eq 3 with the application of Eq 4. Note that Eq
4 is applicable, because the set ${{E}}$ is empty in the initial node, and the
only transition that adds atomic choices of the type $(ic_{i},\theta_{j},0)$
to ${E}$ is Eq 5, that adds only elements of ${{\textbf{IC}}^{p}}\setminus
IC({{E}}^{+}_{*})$. Clearly the result in the resolvent is the same as for the
original IFF derivation, since both Eq 3 and Eq 4 add the consequence $A$ of
the implication to the resolvent. By construction, the set of atomic choices
$(ic_{i},\theta_{j},1)$ added in this way to ${E}$ is always a subset of
$IC({{E}}^{+}_{*})$.

##  6 Implementation

###  6.1 Recap: CHR implementation of the $\mathcal{S}\mbox{CIFF}$ proof-
procedure

We implemented ${\mbox{IFF}}^{\mathit{Prob}}$ leveraging on the implementation
of the $\mathcal{S}\mbox{CIFF}$ proof-procedure. $\mathcal{S}\mbox{CIFF}$
[Alberti et al. (2008)] is an extension of the IFF proof procedure [Fung and
Kowalski (1997)] that also features constraints (à la Constraint Logic
Programming (CLP)) and universally quantified abducibles. In this work, we
extend to the probabilistic case only the IFF sub-language and leave for
future work the probabilistic extension of the other parts of
$\mathcal{S}\mbox{CIFF}$.

The $\mathcal{S}\mbox{CIFF}$ proof-procedure was implemented [Alberti et al.
(2013)] in Constraint Handling Rules (CHR) [Frühwirth (2020)]. CHR is a
rewriting system originally developed to implement new CLP constraint solvers,
and then employed also as a language for a wide variety of applications. A set
of atoms are declared as CHR constraints; according to the CLP operational
semantics, when a CHR constraint is selected (e.g., during SLD-resolution), it
is moved to a constraint store. CHR rules transform the constraint store,
hopefully simplifying it. There exist two main types of CHR rules: propagation
and simplification rules.

A Propagation  rule has the form

$c_{1},c_{2},\dots,c_{n}\Rightarrow Guard|Body$

where $c_{1},\dots,c_{n}$ are CHR constraints, $Guard$ and $Body$ are Prolog
goals. The meaning is that $Body$ is a logical consequence of the conjunction
$c_{1}\land\dots\land c_{n}$ provided that $Guard$ is true. Operationally,
when the set of constraints $c_{1},\dots,c_{n}$ are in the constraint store,
the guard is evaluated; in case it is true, the $Body$ is executed.

A Simplification rule has the form

$c_{1},c_{2},\dots,c_{n}\Leftrightarrow Guard|Body$

Its declarative reading is that $Body$ is equivalent to the conjunction
$c_{1}\land\dots\land c_{n}$ provided that $Guard$ is true. Operationally,
when the set of constraints $c_{1},\dots,c_{n}$ is in the store, and the guard
is true, the constraints $c_{1},\dots,c_{n}$ are removed from the store and
the $Body$ is executed.

In the $\mathcal{S}\mbox{CIFF}$ implementation, each abducible atom a(X) is
mapped to a CHR constraint abd(a(X)), and each IC $Body\rightarrow Head$ is
mapped to a CHR constraint ic(Body,Head). Each transition in the operational
semantics is mapped to a CHR rule. For example, transition propagation is
mapped to the CHR simplification rule (CHR expert readers will actually
recognize it as a simpagation rule)

$abd(A),\ ic([abd(B)|T],H)\ \Leftrightarrow\ abd(A),\ ic([A=B|T],H),$

and transition case analysis is mapped to

$ic([A=B|T],H)\ \Leftrightarrow\ A=B,\ ic(T,H)\ ;\ A\neq B$

where the semicolon is Prolog’s OR and $\neq$ is a dis-unification constraint.
Logical equivalence $\frac{true\rightarrow G}{G}$ is mapped to the
simplification rule

$ic([],Head)\Leftrightarrow Head.$ (6)

###  6.2 Implementation of ${\mbox{IFF}}^{\mathit{Prob}}$

In order to implement probabilistic reasoning, we add a new CHR constraint
that represents the current explanation:

${expl}({{E}},P)$

means that, in the current derivation branch, the explanation is ${{E}}$, and
has probability $P$. The ${{E}}$ parameter is a collection (e.g., list) of
triples $(ic_{i},\theta_{j},k)$, holding the integrity constraint $ic_{i}$,
the substitution that made its body true, $\theta_{j}$, and the integer $k$
representing a Boolean value explaining whether $ic_{i}\theta_{j}$ belongs to
${E}$ or not.

The CHR constraint representing ICs now requires additional information for
probabilistic ICs: unsurprisingly the probability $P$ needs to be added to the
parameters, and also the original version $ic_{i}$ of the integrity constraint
together with the $\theta_{j}$ substitution that binds the variables in the
body is stored. The new CHR constraint representing a probabilistic
implication is

$ic(Body,Head,ic_{i}\theta_{j},P).$

1:$ic([],Head,ic_{i}\theta_{j},P_{ic}),$ ${expl}({{E}},P_{{E}})$
$\Leftrightarrow$

2: $(\quad(ic_{i},\theta_{j},\\_)\in{{E}},$

3:$\phantom{(}\quad{expl}({{E}},P_{{E}})$

4: $;\quad(ic_{i},\theta_{j},\\_)\not\in{{E}},$

5:
$\phantom{(}\quad(\quad{expl}({{E}}\cup\\{(ic_{i},\theta_{j},1)\\},P_{{E}}P_{ic}),$

6:$\phantom{(}\quad\phantom{(}\quad Head$

7:
$\phantom{(}\quad;\quad{expl}({{E}}\cup\\{(ic_{i},\theta_{j},0)\\},P_{{E}}(1-P_{ic}))$

8:$\phantom{(}\quad)$

9:$).$

Figure 1:  Implementation of the probabilistic logical equivalence rule in
CHR.

We extend the logical equivalence rule $\frac{true\rightarrow A}{A}$ according
to the new operational semantics (Figure 1). Such logical equivalence is
applied when (due to successive applications of other transitions) the body of
an integrity constraint $ic_{i}$ is proven true, for a given substitution
$\theta_{j}$ of the variables in the body. Simplification rule 6 is extended
to consider three cases in disjunction. In the first (line 2), it is imposed
that $ic_{i}\theta_{j}$ belongs to the current explanation (i.e., a
unification is imposed such that ${ic}_{i}\theta_{j}$ unifies with at least
one member of the explanation, similarly to the member predicate in standard
Prolog); in such a case, the $ic$ has already been propagated with exactly the
same substitution, so there is no need to re-propagate its consequences, nor
to change the current explanation and its probability. Otherwise (line 4), it
is imposed that $ic_{i}\theta_{j}$ does not belong to the current explanation
(i.e., a dis-unification constraint is imposed between $ic_{i}\theta_{j}$ and
all members of the explanation). In such a case, two alternative branches are
opened, i.e., one in which we consider an explanation that includes the
integrity constraint $ic_{i}\theta_{j}$ (line 5) and one in which
$ic_{i}\theta_{j}$ is considered removed (line 7).

###  6.3 Computation of the Probability of Goals

The ${\mbox{IFF}}^{\mathit{Prob}}$proof-procedure returns the covering set
${\mathcal{E}}$ of all the explanations ${expl}/2$ for a goal $G$. As seen in
Definition 3, if ${\mathcal{E}}$ is also pairwise incompatible, then
$P(G)=P({{\mathcal{E}}})$. However, a covering set of explanations
${{\mathcal{E}}}$ for a goal $G$ is not guaranteed to be pairwise
incompatible.

Thus, we associate a Boolean random variable $X_{ij}$ to each instance of PIC
${ic}_{i}\theta_{j}$. In this way, an atomic choice $({ic}_{i},\theta_{j},1)$
corresponds to $X_{ij}$ assuming value $true$. The variables
$\mathbf{X}=\\{X_{ij}|({ic}_{i},\theta_{j},k)\in{{E}},{{E}}\in{{\mathcal{E}}}\\}$
are pairwise independent and the probability that $X_{ij}$ takes value 1 is
$p_{i}$, the probability associated with the $i$-th PIC.

Given a covering set of explanations ${{\mathcal{E}}}$ for a query $G$, each
world where the query is true corresponds to an assignment of $\mathbf{X}$ for
which the following Boolean function takes value 1:

$f_{{\mathcal{E}}}(\mathbf{X})=\bigvee_{{{E}}\in{{\mathcal{E}}}}\bigwedge_{({ic}_{i},\theta_{j},1)\in{{E}}}X_{ij}\bigwedge_{({ic}_{i},\theta_{j},0)\in{{E}}}\overline{X_{ij}}$
(7)

Thus, we can compute the probability of $G$ by computing the probability that
$f_{{\mathcal{E}}}(\mathbf{X})$ takes value 1. This formula is in Disjunctive
Normal Form (DNF) but we cannot compute $P(f_{{\mathcal{E}}}(\mathbf{X}))$ by
summing the probability of each individual explanation because the different
explanations may not be mutually disjoint. To solve the problem, we can apply
knowledge compilation to the propositional formula
$f_{{\mathcal{E}}}(\mathbf{X})$ [Darwiche and Marquis (2002)] in order to
translate it into a target language that allows the computation of the
probability in polynomial time. A target language that was found to give good
performances is the one of Boolean Decision Diagrams.

A BDD for a function of Boolean variables is a rooted graph that has one level
for each Boolean variable. A node $n$ in a BDD has two children: one
corresponding to the 1 value of the variable associated with $n$, indicated
with $child_{1}(n)$, and one corresponding to the 0 value of the variable,
indicated with $child_{0}(n)$. The leaves store either 0 or 1. Given values
for all the variables, a BDD can be used to compute the value of the formula
by traversing the graph starting from the root, following the edges
corresponding to the variables values and returning the value associated to
the leaf that is reached. For instance, Figure 2 shows a BDD for the function
$f(\mathbf{X})=(X_{11}\wedge X_{21})\vee(X_{12}\wedge X_{21}).$

|
---|---
$\textstyle{X_{11}}$$\textstyle{n_{1}}$$\textstyle{X_{12}}$$\textstyle{n_{2}}$$\textstyle{X_{21}}$$\textstyle{n_{3}}$$\textstyle{1}$$\textstyle{0}$
Figure 2: BDD for function $f(\mathbf{X})$.

1:function Prob($node$, $pMap$)

2: Input: a BDD node $node$ and a (node,prob) map $pMap$

3: Output: the probability of the formula associated to $node$

4: if $node$ is a terminal then

5: return $value(node)$$\triangleright$ $value(node)$ is 0 or 1

6: else if $node$ is in $pMap$ then

7: return $pMap[node]$ $\triangleright$ The probability of $node$

8: else

9: let $X$ be $v(node)$ $\triangleright$ $v(node)$ is the variable associated
to $node$

10: $P_{1}\leftarrow$Prob($child_{1}(node)$)

11: $P_{0}\leftarrow$Prob($child_{0}(node)$)

12: add $(node,P(X)\cdot P_{1}+(1-P(X))\cdot P_{0})$ to $pMap$

13: return $P(X)\cdot P_{1}+(1-P(X))\cdot P_{0}$

14: end if

15:end function

Figure 3: Function that computes the probability of a BDD.

A BDD performs a Shannon expansion of the Boolean formula
$f_{{\mathcal{E}}}(\mathbf{X})$, so that if $X$ is the variable associated to
the root level of a BDD, the formula $f_{{\mathcal{E}}}(\mathbf{X})$ can be
represented as $f_{{\mathcal{E}}}(\mathbf{X})=X\wedge
f_{{\mathcal{E}}}^{X}(\mathbf{X})\vee\overline{X}\wedge
f_{{\mathcal{E}}}^{\overline{X}}(\mathbf{X})$ where
$f_{{\mathcal{E}}}^{X}(\mathbf{X})$ (respectively,
$f_{{\mathcal{E}}}^{\overline{X}}(\mathbf{X})$) is the formula obtained by
$f_{{\mathcal{E}}}(\mathbf{X})$ by setting $X$ to 1 (resp., 0). Now the two
disjuncts are mutually exclusive and the probability of
$f_{{\mathcal{E}}}(\mathbf{X})$ can be computed as
$P(f_{{\mathcal{E}}}(\mathbf{X}))=P(X)P(f_{{\mathcal{E}}}^{X}(\mathbf{X}))+(1-P(X))P(f_{{\mathcal{E}}}^{\overline{X}}(\mathbf{X}))$.
Figure 3 shows the function Prob that implements the dynamic programming
algorithm of [De Raedt et al. (2007)] for computing the probability of a
formula encoded as a BDD.

##  7 Application examples

We can now show how probabilities are computed in the running example; we then
show a second example taken from the literature, to show the versatility of
our approach.

######  Example 7.5 (continues=exa:running).

Here ${{\textbf{IC}}^{p}}=\\{\ref{eq:exampleMurder_IC_Prob}\\}$,
${{\textbf{IC}}^{np}}=\emptyset$ and the set of abducible predicates is
${\mathcal{A}}=\\{{\texttt{{enter}/2}},{\texttt{{killed}/2}}\\}$, since they
are not known.

Two atoms may make the body of $ic_{1}^{\prime}$ true, one stating that
husband has the keys of house1 and the other stating that he holds the keys of
house2; these will correspond to the substitutions
$\theta_{1}=\\{\texttt{P/husband},\texttt{H/house1}\\}$ and
$\theta_{2}=\\{\texttt{P/husband},\texttt{H/house2}\\}$. For each
instantiation that makes the body true, exactly one of the two transitions in
Eq. 4 and 5 is applicable. In this way, four explanations are generated in
alternative branches:
$E_{1}=\\{(\ref{eq:exampleMurder_IC_Prob},\theta_{1},1),(\ref{eq:exampleMurder_IC_Prob},\theta_{2},1)\\}$
with $P(E_{1})=0.7^{2}=0.49$,
$E_{2}=\\{(\ref{eq:exampleMurder_IC_Prob},\theta_{1},1),(\ref{eq:exampleMurder_IC_Prob},\theta_{2},0)\\}$
with $P(E_{2})=0.7\cdot(1-0.7)=0.21$,
$E_{3}=\\{(\ref{eq:exampleMurder_IC_Prob},\theta_{1},0),$
$(\ref{eq:exampleMurder_IC_Prob},\theta_{2},1)\\}$ with $P(E_{3})=(1-0.7)\cdot
0.7=0.21$ and
$E_{4}=\\{(\ref{eq:exampleMurder_IC_Prob},\texttt{\\{P/X,H/house1\\}},0)$,
$(\ref{eq:exampleMurder_IC_Prob},\texttt{\\{P/X,H/house2\\}},0)\\}$ with
$P(E_{4})=(1-0.7)^{2}=0.09$.

The sets of explanations where the goal is true are:

${{\mathcal{E}}}_{1}$

$=\\{E_{1},E_{2},E_{3}\\}$ with probability
$P({{\mathcal{E}}}_{1})=\sum_{i=1}^{3}P(E_{i})=0.91$, probabilistic abductive
answer
$\Delta=\\{{\texttt{{enter}(husband,house1)}},{\texttt{{enter}(husband,house2)}},$
${\texttt{{killed}(husband,woman)}}\\}$ and $\theta=\\{\texttt{M/husband}\\}$.
This solution (the most likely) states that the husband was the killer with a
chance of 91%. Explanation $E_{1}$ indicates that the goal is true (the
husband was the killer) if the husband had entered both houses since he had
the keys for both. The second and third explanations represent the fact that
one instantiation of the PIC is not considered, so with probability 0.3 one
can enter a house even if (s)he does not have the keys.

${{\mathcal{E}}}_{2}$

$=\\{E_{4}\\}$ with $P({{\mathcal{E}}}_{2})=P(E_{4})=(1-0.7)^{2}=0.09$; note
that both instances of $ic_{1}^{\prime}$ are relaxed $(k=0)$ so the complement
of 0.7 must be used. In this case the probabilistic abductive answer is
$(\Delta,\theta)=(\\{{\texttt{{enter}(M,house1)}},$
${\texttt{{enter}(M,house2)}},$ ${\texttt{{killed}(M,woman)}}\\},$
$\emptyset)$. This solution (much less probable) states that some unknown
person entered the two houses and committed the murder with a chance of 9%.

${\mbox{IFF}}^{\mathit{Prob}}$ provided two reasonable explanations. In
particular, the second abductive explanation, obtained through non-ground
abductive reasoning, is that some person, unknown to the knowledge base, could
have perpetrated the murder. It is interesting to know that this is exactly
the explanation suggested by the husband during the trial: he pleaded not
guilty and suggested that some other person could have entered his house,
killed the woman, and carried the pillow to the second house. Although
logically possible, such explanation was considered unlikely by the judges,
that sentenced the husband guilty. Nevertheless, as a human brain was able to
hypothesize the existence of an external person entering both houses and
killing the victim, also the ${\mbox{IFF}}^{\mathit{Prob}}$ proof-procedure
was able to produce such hypothesis. And as a human brain judged such
hypothesis unrealistic, also the proof-procedure assigned it a low
probability. Of course, this is a simplification of all the evidence collected
during the trial, that we cannot report here due to lack of space.

It is also interesting to vary the probability $q$ associated with
$ic_{1}^{\prime}$ to see when ${{\mathcal{E}}}_{2}$ becomes the most probable
explanation. Now the probabilities are: $P(E_{1})=q^{2}$,
$P(E_{2})=q\cdot(1-q)$, $P(E_{3})=q\cdot(1-q)$ and $P(E_{4})=(1-q)^{2}$. In
order to have $P(E_{1})+P(E_{2})+P(E_{3})<P(E_{4})$, it must be that
$q<1-\frac{\sqrt{2}}{2}\simeq 0.293$.

######  Example 7.6.

DBLP:series/lncs/Christiansen08 proposes an example of power supply network
diagnosis (here adapted to ${\mbox{IFF}}^{\mathit{Prob}}$ syntax); a power
plant `pp` provides electricity to a few villages `v`i through directed wires
`w`i. The network structure is described by a set of `edge/3` facts (please
refer to the figure of the network in Section 7.1 in [Christiansen (2008)]):

⬇

edge(w1, pp, n1). edge(w4, n3, v3). edge(w7, n3, v2).

edge(w2, n1, n2). edge(w5, n1, n4). edge(w8, n4, v4).

edge(w3, n2, n3). edge(w6, n2, v1). edge(w9, n4, v5).

The fact that a given point (the power plant, a node or a village) in the
network has no electricity is described in [Christiansen (2008)] by means of
the `hasnopower/1` predicate.

⬇

hasnopower(pp) $\leftarrow$ down(pp).

hasnopower(N2) $\leftarrow$ edge(W,_,N2), down(W).

hasnopower(N2) $\leftarrow$ edge(_,N1,N2), hasnopower(N1).

while the opposite situation is described by:

⬇

haspower(pp) $\leftarrow$ ${\texttt{{up}(pp)}}.$

haspower(N2) $\leftarrow$ edge(W,N1,N2), up(W), haspower(N1).

The clauses and facts mentioned above represent the KB of the
${\mbox{IFF}}^{\mathit{Prob}}$ program. In the proof-procedure by
DBLP:series/lncs/Christiansen08, probabilities are associated to abducible
atoms, and he defines the abducibles up/1 with probabilities 0.9 (every
instance of ${\texttt{{up}(}}X)$ has the same probability) and down/1 with
0.1. As noted earlier, in ${\mbox{IFF}}^{\mathit{Prob}}$ we can use PICs to
associate probabilities to single abducibles, using the complementary
probability:

⬇

$ic_{1}$ = 0.1::up(X) $\rightarrow$ false.

$ic_{2}$ = 0.9::down(X) $\rightarrow$ false.

Finally, the program in [Christiansen (2008)] also includes one IC to state
that no node may be up and down at the same time:

⬇

$ic_{3}$ = up(X) $\wedge$ down(X) $\rightarrow$ false.

Here ${{\textbf{IC}}^{p}}=\\{ic_{1},ic_{2}\\}$,
${{\textbf{IC}}^{np}}=\\{ic_{3}\\}$ and the set of abducible predicates is
${\mathcal{A}}=\\{{\texttt{{up}/1}},{\texttt{{down}/1}}\\}$.

Given the goal:

⬇

$G$ = hasnopower(v1),hasnopower(v2),hasnopower(v3),

hasnopower(v4),hasnopower(v5)

$P(G)=0.199695$ is returned as the probability that no village has
electricity, as the sum of the probability of the worlds where the goal is
true, throughout the application of function Prob of Fig. 3. In total, 1600
worlds are found, corresponding to the different combinations of failures of
wires/power plant. As also computed by DBLP:series/lncs/Christiansen08, the
two most probable worlds have both probability $0.1$ and are respectively
identified by the explanations:

$E_{1}=\\{(ic_{2},\texttt{X/pp},0)\\}$

having probability $P(E_{1})=(1-0.9)=0.1$; the complement of $0.9$ is taken as
$ic_{2}$ with substitution $\theta_{1}=\\{\texttt{X/pp}\\}$ (i.e., down(pp)
$\rightarrow$ false.) is not included ($k=0$). The probabilistic abductive
answer is $(\Delta,\theta)=(\\{{\texttt{{down}(pp)}}\\},\theta_{1})$;

$E_{2}=\\{(ic_{2},\texttt{X/w1},0)\\}$

having probability $P(E_{2})=(1-0.9)=0.1$; here $ic_{2}$ with substitution
$\theta_{2}=\\{\texttt{X/w1}\\}$ is not included. The probabilistic abductive
answer is $(\Delta,\theta)=(\\{{\texttt{{down}(w1)}}\\},\theta_{2})$.

$E_{1}$ indicates that the goal is true (no village receives power) if the
power plant is down with probability 0.1, while $E_{2}$ if the main wire (w1)
is down with probability 0.1.

##  8 Experiments

To test how our approach reacts with an increasing number of worlds, given an
integer $n\geq 1$, we considered the ALP containing the following ICs for
$1\leq i\leq n$:

⬇

0.6::$\texttt{{b}}_{i-1}$(X) $\rightarrow$ $\texttt{{p}}_{i}$(X) $\wedge$
$\texttt{{q}}_{i}$(X).

0.6::$\texttt{{p}}_{i}$(X) $\rightarrow$ $\texttt{{b}}_{i}$(X).

0.6::$\texttt{{q}}_{i}$(X) $\rightarrow$ $\texttt{{b}}_{i}$(X).

where $\texttt{{b}}_{i}\texttt{(X)}$, $\texttt{{p}}_{i}\texttt{(X)}$, and
$\texttt{{q}}_{i}\texttt{(X)}$ are abducibles for all $i$. For the test
purpose, we built 12 ALPs of increasing size containing the above ICs for $i$
varying from 1 to $n$, with $n\in\\{1,2,3,\dots,11,12\\}$.

These ALPs present a number of worlds that grows exponentially with $n$. This
is due to the fact that $\texttt{{p}}_{i+1}\texttt{(X)}$ and
$\texttt{{q}}_{i+1}\texttt{(X)}$ are needed to abduce
$\texttt{{b}}_{i}\texttt{(X)}$. $\texttt{{p}}_{i+1}\texttt{(X)}$ and
$\texttt{{q}}_{i+1}\texttt{(X)}$ can either both be true, or one true while
the other must be abduced, or both must be abduced. In turn, to abduce
$\texttt{{p}}_{i+1}\texttt{(X)}$ or $\texttt{{q}}_{i+1}\texttt{(X)}$, one must
use $\texttt{{b}}_{i+1}\texttt{(X)}$, which may be already abduced or may
possibly have to be abduced. These possible cases must be considered for all
values assumed by $i$, creating an exponential number of possible ways to
prove $\texttt{{b}}_{i}\texttt{(X)}$.

For the test, we compute the probability of the goal
$G=\texttt{{b}}_{0}\texttt{(X)}$. To compute the running time, we ran the
${\mbox{IFF}}^{\mathit{Prob}}$ proof procedure 5 times w.r.t. each ALP built
and we computed the average running time with its standard deviation. All the
tests have been performed on a Linux machine equipped with IBM© POWER9TM AC922
at 2.6(3.1)GHz, with 256 GB of RAM. We allowed a maximum of 100 GB for the
Prolog stack, necessary to hold the worlds and the information about the
choice points for the ALPs with $i\geq 11$.

Table 1: Average running time (in seconds) on 5 executions of the ${\mbox{IFF}}^{\mathit{Prob}}$ proof-procedure and the $\pm$ the standard deviation. ALP size indicates the value $n$ takes in each ALP, i.e., it defines the range $1\leq i\leq n$. OM means Out of Memory. ALP size ($n$) | N. Worlds |  Time (s) $\pm$ Std. dev.
---|---|---
1 | 5 | $0.00133\pm 0.00003$
2 | 17 | $0.00387\pm 0.00001$
3 | 53 | $0.01228\pm 0.00003$
4 | 161 | $0.04042\pm 0.00013$
5 | 485 | $0.13582\pm 0.00059$
6 | 1 457 | $0.45903\pm 0.45903$
7 | 4 373 | $1.91763\pm 0.01396$
8 | 13 121 | $6.32130\pm 0.02730$
9 | 39 365 | $21.51733\pm 0.06072$
10 | 118 097 | $73.78656\pm 0.29424$
11 | 354 293 | $333.90058\pm 0.78041$
12 | 1 062 881 | OM

Table 1 shows, for each ALP, the number of found worlds and the average
running time in seconds to compute the probability of the goal $\pm$ the
standard deviation. The value OM represents the fact that the proof-procedure
went out of the available stack due to the high number of worlds and choice
points to maintain in memory. As one can see, our approach is able to manage
very high number of worlds within 1 minute.

##  9 Related work

Some works explicitly addressed probabilistic abductive reasoning:
TurliucEtAl2013 rank explanations in terms of probabilities and investigate
the role of integrity constraints. They define a probability distribution over
the truth values of each (ground) abducible, while we set probabilities on
integrity constraints. SOLAR [Inoue et al. (2009)] is a system for abductive
inference that applies an Expectation Maximization (EM) algorithm for
evaluating hypotheses obtained from the process of hypothesis generation.
After generating all minimal explanations, the EM algorithm, working on BDDs,
is used to assign probabilities to atoms in explanations. Finally, SOLAR
computes the probability of each hypothesis to find the most probable one. EM
is also used by conf/ijcai/Raghavan11, who considers Bayesian Logic Programs
(BLPs), and by kate2009rj, who consider Markov Logic Networks (MLNs). EM is
exploited to learn the parameters associated with the model.

Differently, DBLP:journals/ai/Poole93 considers Bayesian networks but focuses
on the definition of the language instead of the combination of abductive
proof-procedures and statistical learning. Moreover, it imposes assumptions on
the type of constraints in order to simplify the procedure.

arvanitis2006abduction consider Stochastic Logic Programs (SLPs), where
abductive reasoning is done by reversing deduction, i.e., reversing the flow
of the proof-procedure. However, this may return wrong conclusions without
imposing ad hoc constraints in the program.

DBLP:conf/cilc/RotellaF13 define new types of probabilistic constraints to
guide the search of explanations that are consistent with the constraints, by
giving priority to explanations having higher probability to be true. However,
all these approaches do not allow non-ground abduction. We refer to [De Raedt
and Kersting (2008)] for a description of BLPs, MLNs, and SLPs.

Abduction is also used in machine learning. For example in [Muggleton et al.
(2015)], it is used to perform predicate invention and recursive
generalisations with respect to a meta-interpreter. In this case, however,
values for predicate variables rather than values for first order variables
are abduced. More recently, [Dai and Muggleton (2021)] proposed to use
abduction to infer constraints for learning problems but do not consider
existential variables.

DBLP:series/lncs/Christiansen08 also implements probabilistic non-ground
abduction in CHR; the main difference with our work is that in his work
probabilities are associated with abducibles, while in our work they are
associated with integrity constraints. The integrity constraints in his proof-
procedure are more limited in syntax, since they can only accommodate
abducible predicates and are in the form of denials, while in IFF they can
include all types of atoms, and are in the form of implications, with
disjunctions in the head. Due to the syntactic restrictions on integrity
constraints, only a limited form of negation is possible, while in IFF sound
negation can be applied to both abducible and defined atoms. Differently from
our solution, Christiansen adopts a best-first search scheme, in which
branches with higher probability are explored before the branches with lower
probability; while the exact probability is only known at the end of the whole
search, at each found solution a lower bound is obtained, and it gets more
precise as new solutions are found. On the other hand, a best-first search has
higher memory requirements than a depth-first search.

##  10 Conclusions

We presented a probabilistic abductive logic programming language able to
perform abductive reasoning with variables, and probabilities attached to
constraints. The need to have probabilistic integrity constraints comes from
probabilistic reasoning with many real-life applications, and such integrity
constraints may be learned from available data [Riguzzi et al. (2020)]. We
showed two examples on different domains of abductive reasoning with
probabilities in action, showing the usefulness of non-ground abduction and
that our language can also tackle problems with probabilities attached to
abducibles. Soundness and completeness of the devised proof-procedure have
been shown.

Future work concerns considering non-ground probabilities, i.e., variable
probabilities attached to integrity constraints and its CHR implementation, as
well as probabilistic clauses in the KB, and CLP constraints.

## References

  * Alberti et al. (2008) Alberti, M., Chesani, F., Gavanelli, M., Lamma, E., Mello, P., and Torroni, P. 2008\.  Verifiable agent interaction in abductive logic programming: The SCIFF framework.  ACM Trans. Comput. Log. 9, 4, 29:1–29:43.
  * Alberti et al. (2013) Alberti, M., Gavanelli, M., and Lamma, E. 2013\.  The CHR-based implementation of the SCIFF abductive system.  Fundamenta Informaticae 124, 4, 365–381.
  * Arvanitis et al. (2006) Arvanitis, A., Muggleton, S. H., Chen, J., and Watanabe, H. 2006\.  Abduction with stochastic logic programs based on a possible worlds semantics.  In Short Paper Proceedings of the 16th International Conference on Inductive Logic Programming (ILP 2006).
  * Azzolini et al. (2019) Azzolini, D., Riguzzi, F., and Lamma, E. 2019\.  Studying transaction fees in the Bitcoin blockchain with probabilistic logic programming.  Information 10, 11, 335.
  * Christiansen (2008) Christiansen, H. 2008\.  Implementing probabilistic abductive logic programming with constraint handling rules.  In Constraint Handling Rules, Current Research Topics. Lecture Notes in Computer Science, vol. 5388. Springer, 85–118.
  * Clark (1978) Clark, K. L. 1978\.  Negation as failure.  In Logic and data bases. Springer, 293–322.
  * Dai and Muggleton (2021) Dai, W.-Z. and Muggleton, S. H. 2021\.  Abductive knowledge induction from raw data.  In Proceedings of the 35th Conference on Artificial Intelligence (IJCAI 2021).
  * Darwiche and Marquis (2002) Darwiche, A. and Marquis, P. 2002\.  A knowledge compilation map.  Journal of Artificial Intelligence Research 17, 229–264.
  * De Raedt and Kersting (2008) De Raedt, L. and Kersting, K. 2008\.  Probabilistic inductive logic programming.  In Probabilistic Inductive Logic Programming - Theory and Applications. Lecture Notes in Artificial Intelligence, vol. 4911. Springer, 1–27.
  * De Raedt et al. (2007) De Raedt, L., Kimmig, A., and Toivonen, H. 2007\.  ProbLog: A probabilistic Prolog and its application in link discovery.  In 20th International Joint Conference on Artificial Intelligence (IJCAI 2007). Vol. 7. AAAI Press/IJCAI, 2462–2467.
  * Frühwirth (2020) Frühwirth, T. W. 2020\.  Justifications in constraint handling rules for logical retraction in dynamic algorithms: Theory, implementations, and complexity.  Fundamenta Informaticae 173, 4, 253–283.
  * Fung and Kowalski (1997) Fung, T. H. and Kowalski, R. A. 1997\.  The IFF proof procedure for abductive logic programming.  Journal of Logic Programming 33, 2, 151–165.
  * Inoue et al. (2009) Inoue, K., Sato, T., Ishihata, M., Kameya, Y., and Nabeshima, H. 2009\.  Evaluating abductive hypotheses using an EM algorithm on BDDs.  In 21st International Joint Conference on Artificial Intelligence (IJCAI 2009). Morgan Kaufmann Publishers Inc., 810–815.
  * Kakas et al. (1998) Kakas, A., Kowalski, R., and Toni, F. 1998\.  The role of abduction in logic programming.  In Handbook of Logic in Artificial Intelligence and Logic Programming. _Vol 5_. Oxford University Press, 235–324.
  * Kate and Mooney (2009) Kate, R. J. and Mooney, R. J. 2009\.  Probabilistic abduction using Markov logic networks.  In IJCAI-09 Workshop on Plan, Activity, and Intent Recognition (PAIR 2009).
  * Kunen (1987) Kunen, K. 1987\.  Negation in logic programming.  The Journal of Logic Programming 4, 4, 289 – 308.
  * Muggleton et al. (2015) Muggleton, S. H., Lin, D., and Tamaddoni-Nezhad, A. 2015\.  Meta-interpretive learning of higher-order dyadic datalog: predicate invention revisited.  Machine Learning 100, 1, 49–73.
  * Nguembang Fadja and Riguzzi (2017) Nguembang Fadja, A. and Riguzzi, F. 2017\.  Probabilistic logic programming in action.  In Towards Integrative Machine Learning and Knowledge Extraction. Lecture Notes in Computer Science, vol. 10344. Springer.
  * Poole (1993) Poole, D. 1993\.  Probabilistic Horn abduction and Bayesian networks.  Artificial Intelligence 64, 1, 81–129.
  * Raghavan (2011) Raghavan, S. V. 2011\.  Bayesian abductive logic programs: A probabilistic logic for abductive reasoning.  In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI-11). IJCAI/AAAI, 2840–2841.
  * Riguzzi et al. (2020) Riguzzi, F., Bellodi, E., Zese, R., Alberti, M., and Lamma, E. 2020\.  Probabilistic inductive constraint logic.  Machine Learning, 1–32.
  * Rotella and Ferilli (2013) Rotella, F. and Ferilli, S. 2013\.  Probabilistic abductive logic programming using possible worlds.  In Proceedings of the 28th Italian Conference on Computational Logic, Catania, Italy, September 25-27, 2013. CEUR Workshop Proceedings, vol. 1068. CEUR-WS.org, 131–145.
  * Sato (1995) Sato, T. 1995\.  A statistical learning method for logic programs with distribution semantics.  In Proceedings of the Twelfth International Conference on Logic Programming, (ICLP 1995). MIT Press, 715–729.
  * Turliuc et al. (2013) Turliuc, C.-R., Maimari, N., Russo, A., and Broda, K. 2013\.  On minimality and integrity constraints in probabilistic abduction.  In Logic for Programming, Artificial Intelligence, and Reasoning. Springer, 759–775.
  * Vennekens et al. (2004) Vennekens, J., Verbaeten, S., and Bruynooghe, M. 2004\.  Logic programs with annotated disjunctions.  In 24th International Conference on Logic Programming (ICLP 2004). Lecture Notes in Computer Science, vol. 3131. Springer, 431–445.

  *[LP]: Logic Programming
  *[ALP]: Abductive Logic Programming
  *[ICs]: Integrity Constraint
  *[IC]: Integrity Constraint
  *[PIC]: Probabilistic Integrity Constraint
  *[PICs]: Probabilistic Integrity Constraint
  *[CLP]: Constraint Logic Programming
  *[CHR]: Constraint Handling Rules
  *[BDD]: Boolean Decision Diagram
  *[ALPs]: Abductive Logic Programming
  *[BDDs]: Boolean Decision Diagram