We present the Credal-FOIL system for structure learning of probabilistic logic programs under the credal semantics. The credal semantics is a generalisation of the distribution semantics based on the answer set semantics. Our learning approach takes a set of examples that are atoms with target lower and upper bounds probabilities and a background knowledge that can have negative loops. We de ne accuracy in this setting and learn a set of normal rules without loops that maximises this notion of accuracy. We showcase the system on two proof-of-concept examples.
Probabilistic Logic Programming is a eld that has its roots in the nineties. It
augments the eld of Logic Programming to allow probabilistic inference using
logical rules. While there exist many formulations, a major approach is based on
the Distribution Semantics [
The credal semantics [
Rule learning is a well studied subject in logic programming and is often
called inductive logic programming [
In this paper we introduce Credal-FOIL, a framework and algorithm for
learning the structure of probabilistic logic programs under the credal semantics.
In Credal-FOIL the learned hypothesis is a non-probabilistic set of normal rules
with no negative loops and the logic program in the background knowledge is
expressed as a non strati ed answer set program. Examples in our Credal-FOIL
learning task are single atoms with an associated target lower and upper bound
probability. To the best of our knowledge no attempt had been proposed yet
for structure learning under the credal semantics. Our system de nes a notion
of coverage over our examples and learns incrementally a hypothesis that
maximises a notion of accuracy. We showcase our system using two proof of concept
examples: the rst example shows that in the speci c case when the background
knowledge is strati ed the learning task coincides with the ProbFOIL [
The rest of the paper is composed as follows: Section 2 presents the background necessary for reading this paper, Section 3 presents our learning task and our methodology to solve it. We apply our system to two examples in Section 4 and talk about related works in Section 5. Finally we discuss our work and next steps in Section 6 and conclude in Section 7. 2
This section introduces notions of logic programming [
In a logic program, a term is either a constant a; b; c:: or a variable X; Y; Z::, an atom is of the form p(t1; :::; tn) where p is a predicate of arity n and t1; :::; tn are terms (n can be 0). A literal is an atom p or a negated atom not p (negation as failure), a normal rule is of the form A :- B1; :::; Bn where A is an atom (called the head of the rule) and B1; :::; Bn are literals (called the body of the rule). A rule with an empty body is called a fact. A ground literal is a literal with no variable, a ground rule contains only ground literals. A normal logic program is a set of normal rules. The Herbrand universe of a program is the set of all the ground terms appearing in the program. The Herbrand Base HBP of a program P is the set of all the ground atoms that can be formed from the predicates in P and the ground terms in the Herbrand universe. A substitution is a mapping from variables to terms. The grounding of a program P is the set of all ground rules r where r is in P and is a mapping from variables to ground terms in the Herbrand universe. We call an interpretation of P any subset of HBP .
We can now introduce the answer set semantics. Given a program P and an interpretation I, the reduct P I is the program made from the grounding of P in the following way: remove all rules that has in the body the negation of an atom in I and then delete all negative literals from the body of the remaining rules. The reduct P I is a ground de nite program and thus has a single minimal model. I is an answer set of P if it is the minimal model of P I . We denote the set of answer sets of P as AS(P ). A strati ed program P is a program that can be divided in the form P = P1 [ P2 [ ::: [ Pm where Pi and Pj are disjoint for all i 6= j such that if an atom occurs positively in Pi then it appears in the head of a rule in Pj with j i and if an atom appears negatively in Pi then it appears in the head of a rule in Pj with j < i. It is known that a strati ed program admits one single answer set if any, and that unstrati ed programs can admit more than one. As a program may have multiple answer sets, the entailment of an atom can be of two types: brave and cautious. An atom p is cautiously entailed by P if p is in all the answers sets of P and bravely entailed by P if p is in at least one answer set of P. For an interpretation I and conjunctive formula F , we denote I j= F if F is entailed (true) in I. The notion of brave and cautious entailment is extended to conjunctive formulas. 2.2
The credal semantics is a generalisation of the Distribution semantics [
The syntax we consider in this paper for probabilistic logic programs is as
follows: a PLP is a pair < P; P F > where P is a logic program and P F is a
set of independent ground probabilistic facts. A probabilistic fact is of the form
:: p (using the Problog notation [
We denote HBP the Herbrand Base HBP augmented with the atoms in the probabilistic facts. When referring to interpretations of P in the context of a PLP < P; P F >, we mean subsets of HBP . Probabilities are de ned over interpretations of P using probability measures P r: for an interpretation I var1 (X) , not walk (X) , s u n s h i n e (X) , not wind (X) .
var1 (X) , not run (X) . var1 (X) , run (X) , t i r e d (X) .
var1 (X) , walk (X) , not warm(X) .
HBP and a probability measure P r over 2HBP , P r(I) denotes the probability
associated to I by P r. We surcharge the notation and de ne the probability of
a conjuctive formula F as P r(F ) = PI22HBP ;Ij=F P r(I) for a given probability
measure P r over 2HBP . A PLP is consistent if there is at least one answer set
for each total choice, meaning that 8C 2 2P F ; AS(P [ P FC ) 6= ;. We give the
de nition from Cozman and Maua [
In other words, we accept all probability measures that only give non-zero
probability to elements of fAS(P [ P FC )jC total choiceg such that for each total
choice, the sum of the probability of the corresponding answer sets equals the
probability of the total choice. Now, the probability of a conjunctive formula F
can be di erent depending on the probability model considered. However there
exists a minimum value [
An algorithm is given in [
We give an example of probabilistic logic program in Figure 1. It de nes 4 probabilistic facts with their corresponding probabilities, which yield 24 = 16 total choices. There will be a negative loop in P [ P FC for all the total choices C where sunshine is true and wind is false at the same time (that is with probability 0:4 0:8 = 0:32), so run(d1) appears in one out of two answer sets for these total choices. Otherwise run is always false. That makes for: P r(run(d1)) = 0 and P r(run(d1)) = 0:32. While the atom sick(d1) is not in a negative loop, it depends on run(d1) or walk(d1) and so will have di erent lower and upper bound probabilities: P r(sick(d1)) = 0:15 and P r(sick(d1)) = 0:27. 3
The rst di culty of learning a probabilistic program under the credal semantics
is that we aim to learn a set of probability distributions instead of a single one.
We use as targets the lower and upper bound probabilities of example atoms.
Our approach builds on ProbFOIL [
The hypothesis we learn here is a set of rules with no negative loops. In
practice, these examples are di erent groundings of the same predicate (the
target predicate) and the rules in the hypothesis all have the same head. We
extend ProbFOIL [
Each example can be interpreted in the following way: they provide information about the proportion of the worlds (total choices) in which the atom ei should be true or false, the probability of each total choice being given by the DS. In this context, we interpret the probabilities as percentages and when talking about proportions of the worlds, we mean taking into account the probabilities of each world. For example when writing \in 0:5 of the worlds", we do not mean in exactly half of them but in a certain amount such that their probabilities sum to 0:5. Now as in our setting one total choice can lead to multiple answer sets, we not only have atoms being true or false but also the notion of brave and cautious inference for each total choice. Each example provides targets for these di erent inference types. Informally, (ei; pi; pi) can be interpreted as meaning that ei should be cautiously entailed (cautiously true) in pi (in percentage) of the worlds, bravely entailed (bravely true) in (pi pi) of the worlds and not entailed (false) in (1 pi) of the worlds. We call respectively these quantities the \True/Positive" (ti = pi), \Brave" (bi = pi pi) and \False/Negative" (fi = 1 pi) parts of example (ei; pi; pi). This is illustrated in Figure 2. We can then de ne the Positive, Brave and Negative parts of the dataset as: 1 pi
p i
0 ei
Not entailed Cautiously entailed
Bravely entailed Set of total choices
To rate an hypothesis, we use the notions of ROC analysis (True Positive, False Positive, True Negative, False Negative) to which we introduce two new categories: True Brave (TB) and False Brave (FB). These are aimed at de ning the coverage over the brave part of the dataset. It is important to note that each example participates at the same time to the Positive, Brave and Negative parts of the dataset. Given the PLP B [ H =< P [ H; P F > composed of background B =< P; P F > together with an hypothesis H and an example (ei; pi; pi), let qi = P rB[H (ei) and qi = P rB[H (ei) the predicted lower probability and predicted upper probability for atom ei. The aforementioned quantities are de ned on each example (ei; pi; pi) as follows: { true positive tpi = min(pi; qi) { true negative tni = min(1 pi; 1 qi) { true brave tbi = max(0; min(pi; qi) { false positive f pi = max(0; qi pi) { false negative f ni = max(0; pi qi) { false brave left f bli = max(0; min(pi; qi) qi) { false brave right f bri = max(0; qi max(qi; pi)) max(pi; qi))
These quantities are illustrated in Figure 3. If qi < pi (ex. 1,2 and 5 of Figure 3), that means that in qi of the worlds, we rightfully predict that ei is cautiously entailed so tpi = qi. However if qi > pi (ex. 3,4 and 6 of Figure 3), we predict that ei is cautiously entailed in qi of the worlds, which is \too many". Thus tpi = pi and f pi = qi pi, meaning that we predict that in f pi worlds ei is tpi 0.1 tpi 0.1 0.1 0.1 tpi 0.1 0.1 cautiously entailed when it should not be. The argument is of the same nature for tni and f ni depending on pi and qi. Now the true brave part of the example is the intersection of the two segments [pi; pi] and [qi; qi]. There are two \ways of obtaining" some false brave: the segment [qi; qi] over ows [pi; pi] to the left or to the right. When it over ows to the left then qi < pi (assume qi > pi, ex. 2 and 5 of Figure 3), then we predict that in f bli = pi qi of the worlds ei is bravely entailed when it should be cautiously entailed. Symmetrically, when [qi; qi] over ows to the right, qi > pi (assume qi < pi, ex. 3 and 5 of Figure 3), we predict that in f bri = qi pi of the worlds ei is bravely entailed when it should no be entailed. Informally, false brave left can be seen as \we predict bravely entailed when it should be cautiously entailed" and false brave right as \we predict bravely entailed when it should not be entailed". The same arguments hold when the segments [pi; pi] and [qi; qi] do not intersect (ex. 1 and 4 of Figure 3). We compute these quantities over the entire dataset by summing them over each individual example:
The false brave (FB) quantity is the sum of the false brave left (FBL) and the false brave right (FBR). These allow us to de ne the following loss functions: T P = T N =
F N = F BL =
X tpi i=1::n X tni i=1::n X f ni i=1::n X f bli
They are a modi cation of the usual heuristics from ROC analysis used in
inductive logic programming [
Our algorithm (Figure 4) is a version of the coverage algorithm and is similar
to that of ProbFOIL+'s [
This pruning checks for which i the rules h b1; ::; bi maximises this localscore. As such, multiple (or none or all) literals might be removed from the body. The re nement process is shown in Algorithm 2: from a rule with empty body, we iteratively re ne it until either it does not increase the TP or TB part of the dataset or does not have any FP or FBR (line 2). The rst step to the re nement loop consists of nding the set of all possible literals that can be added at the end of the rule r (line 3). Next we reject some possible re nements (line 4) to compensate for the fact that we do not discard covered examples as a normal FOIL algorithm would. In our case, we cannot discard the examples as a rule might only cover a part of that example. This implies that when learning a second rule, we need to make sure it is not going to cover exactly the same part of the examples as the rst one. The reject function checks each possible re nement (literal) by appending it to the body of the rule r and checking if adding this latter to the hypothesis changes the computed probabilities. If the probabilities stay the same, that means that this potential rule would not be useful, thus the re nement is rejected. Finally, the re nement process selects the best literal in the set of retained re nements (lines 7-8) and appends it to the current rule. This process is repeated until the stopping criteria is met.
In practice, the re nement process of Algorithm 2 is included within a beam search to allow for a better search through the hypothesis space. We keep the rules that had the best maximum localscore until none can be re ned further, at which point we return the one with the maximum potential localscore. 4
We demonstrate our system Credal-FOIL on two examples of probabilistic
program reconstruction and then give some implementation details about our
experiments. The rst is the sur ng example from De Raedt et Thon [
FBR({r})) == 0): 3 refinements = refinement(SM , r) %Set of all possible
literals that can be added to c based on SM 4 refinements = reject(H, r, refinements) %We reject some refinements 5 Let (h b1, .., bi) be r % i 0 6 Let N be the cardinality of refinements 7 l = argmaxk2[1;N] localscore(H, h b1,..,bi,refinements[k]) 8 r = h b1,..,bi,refinements[l] 9 return r modeh(pred1(Var)) (mode head) and modeb(pred2(Var)) (mode body) respectively de ne that \pred1(X)" can be in the head of a rule and that \pred2(X)" and \not pred2(X)" can be in the body of a rule. In our examples, we only use predicates of arity one. Of course with our learning setting, there can only be one mode head declaration.
In the following examples, an added atom var1(X) appears in the programs. It is automatically added by our learning system for practical reasons but does not in uence the probabilities. We explain why we do so in section 4.3. var1 (X) , not pop (X) , windok (X ) .
var1 (X) , not pop (X) , s u n s h i n e (X ) . The sur ng example has three probabilistic facts per example: pop(ti), windok(ti) and sunshine(ti) which each have a probability. The full program is given in Figure 5. The mode bias allows only for sur ng in the head and for pop, windok and sunshine (and their negation by failure) in the body. We generated 50 di erent examples by grounding each set of three probabilistic facts 50 times and attributing to each grounding a random probability. We then computed the probability of sur ng(ti) (where i = 1::50) using the full program to obtain a set of examples of the form: e(sur ng(t1); 0.84; 0.84) (which correspond to probabilities 0.03, 0.67 and 0.6 to pop(t1), windok(t1) and sunshine(t1) respectively). We can note here that as the PLP is strati ed, the target upper and lower probabilities are the same. Using the value m = 5 for the m-estimatetb, the program terminated after 3 iterations of the outer-loop with the following rules: sur ng(X) :- var1(X), not pop(X), windok(X). sur ng(X) :- var1(X), sunshine(X), not pop(X): sur ng(X) :- var1(X).
The third rule was rejected by Credal-FOIL as it lowered the overall accuracy. This example aims to show that our system works in the case of point probabilities and is not only tailored for unstratifed background knowledge. 4.2
We now consider the program in Figure 1 and use as target predicate sick. The mode declaration allows for tired, run, walk and warm (and their negation by failure) in the body. We proceed in the same way as with the sur ng example to compute (using the full program) the examples of the form: e(sick(t1); 0.15; 0.27). For learning, we delete from the program the two rules with sick in the head. The logic program part of the background knowledge thus contains the two rules with run and walk in the head, forming a negative loop. We attempt to reconstruct the original program using 50 examples (sick(ti) for i = 1::50). Using the value m = 5 for the m-estimatetb, after three outer-loop iterations we obtain the following rules: sick(X) :- var1(X), not warm(X), not run(X). sick(X) :- var1(X), run(X), tired(X).
sick(X) :- var1(X):
The third rule is of course discarded by the algorithm as it lowers the
accuracy. As not run(X) and walk(X) are logically equivalent in this PLP,
CredalFOIL is capable here to recover the two missing rules.
We give here some additional information about our experimental setting. Our
system does not use knowledge compilation to compute the probability values
but instead simply computes the answer sets for each total choice using CLINGO
[
In fact, the sickness learning only needed two examples to nd the original rules while sur ng needed ve examples at minimum. The factor that explains this di erence is probably that m-estimatetb had access to more information (TB, FBR) in the sickness case.
CLINGO uses GRINGO to ground programs. Thus rules need to be safe, meaning amongst other things that negative literals cannot appear alone in the body of rules. To avoid this problem altogether, we automatically add to the body of rules the atom var1(X) and add ground facts var1(ti) (i = 1::50) in the program. 5
Structure learning is not new in probabilistic logic programming and comes from
the eld of inductive logic programming. We took inspiration from ProbFOIL
[
While (to the best of our knowledge) our work is the rst attempt at structure
learning under the credal semantics, previous work has been done in learning
using semantics that are based on the answer set semantics. PrASP [
We discuss in this section our work and future steps. We will rst comment on practical sides of our approach. We would like to point out that di erent parts of our system are based on empirical choices. The rst is the choice of m-estimatetb in the local score: it has shown to perform better than the other candidates for unstrati ed PLPs. Also, the construction of our heuristic functions aimed to follow the original goals of each loss function in ROC analysis, but one might decide to use entirely new metrics based on the new categories we de ned. Finally, our way to formulate our TB and FB quantities can be debatable. Consider the case where, for an example ei, we have pi = 0:5, pi = 0:7, qi = 0:1 and qi = 0:3. Our system would consider that f bli = 0:2 and f ni = 0:4 but one can argue it to be unfair as pi pi = qi qi, which means that we predict the example to be bravely entailed in the right amount of worlds. We could instead compute the quantities using the following formulas: tbi = min(pi pi; qi
qi) f bli = 0 f bri = qi qi tbi (5)
X (ei;pi;pi)2E We can see it as favoring the intervals [pi; pi] and [qi; qi] to be of the same lengths instead of intersecting. Empirically this formulation did not make much of a di erence in our tests.
We made the choice of maximising our notion of accuracy which is intuitive, but a case could be made to instead formulate the learning task using a regression loss of the form ( nd H such as):
H = argminH jP rB[H (ei) pij + jP rB[H (ei) pij (6)
This would require the de nition of a speci c heuristic function as it is not equivalent to maximising accuracy because of speci c cases illustrated by examples 1 and 4 in Figure 3.
While we ful lled our goal of proving the feasibility of learning under the
credal semantics, expanding it in a concrete context will be complex. The main
di culty comes from our de nition of examples: we required the target lower
and upper bound probabilities. We do not have at the time a protocol to extract
them from statistical data. While arti cial intelligence has used semantics based
on intervals (Dempster-Shafer Belief Functions [
In this paper we presented the system Credal-FOIL aimed at learning the structure of a probabilistic logic program interpreted under the credal semantics. Credal-FOIL is capable of learning a set of normal rules with a single head using an unstrati ed background knowledge. From the set of examples and an hypothesis, we introduce heuristic functions that are inspired by ROC analysis. We make a proof-of-concept using two examples of program reconstruction using possibly non-strati ed background knowledge. Future work will focus on learning weights and negative loops as well as considering alternative learning tasks.