Recently much work in Machine Learning has concentrated on representation languages able to combine aspects of logic and probability, leading to the birth of a whole eld called Statistical Relational Learning. In this paper we present a technique for parameter learning targeted to a family of formalisms where uncertainty is represented using Logic Programming techniques - the so-called Probabilistic Logic Programs such as ICL, PRISM, ProbLog and LPAD. Since their equivalent Bayesian networks contain hidden variables, an EM algorithm is adopted. In order to speed the computation, expectations are computed directly on the Binary Decision Diagrams that are built for inference. The resulting system, called EMBLEM for \EM over Bdds for probabilistic Logic programs E cient Mining", has been applied to a number of datasets and showed good performances both in terms of speed and memory usage.
Machine Learning has seen the development of the eld of Statistical Relational Learning (SRL) where logical-statistical languages are used in order to e ectively learn in complex domains involving relations and uncertainty. They have been successfully applied in social networks analysis, entity recognition, collective classi cation and information extraction, to name a few.
Similarly, a large number of works in Logic Programming have attempted
to combine logic and probability, among which the distribution semantics [
In this paper we present the EMBLEM system for \EM over Bdds for
probabilistic Logic programs E cient Mining" [
Since there are transformations with linear complexity that can convert a
program in a language under the distribution semantics into the others [
The paper is organized as follows. Section 2 presents LPADs and Section 3 describes EMBLEM. Section 4 discusses related works. Section 5 shows the results of the experiments performed and Section 6 concludes the paper. 2
Formally a Logic Program with Annotated Disjunctions [
An atomic choice is a triple (Ci; j ; k) where Ci 2 T , j is a substitution that grounds Ci and k 2 f1; : : : ; nig. (Ci; j ; k) means that, for the ground clause Ci j , the head hik was chosen. In practice Ci j corresponds to a random variable Xij and an atomic choice (Ci; j ; k) to an assignment Xij = k. A set of atomic choices is consistent if (C; ; i) 2 ; (C; ; j) 2 ) i = j, i.e., only one head is selected for a ground clause. A composite choice is a consistent set of atomic choices. The probability P ( ) of a composite choice is the product of the probabilities of the individual atomic choices, i.e. P ( ) = Q(Ci; j;k)2 ik.
A selection is a composite choice that, for each clause Ci j in ground(T ), contains an atomic choice (Ci; j ; k). We denote the set of all selections of a program T by ST . A selection identi es a normal logic program w de ned as w = f(hik body(Ci)) j j(Ci; j ; k) 2 g. w is called a world of T . Since selections are composite choices we can assign a probability to possible worlds: P (w ) = P ( ) = Q(Ci; j;k)2 ik.
We consider only sound LPADs, in which every possible world has a total well-founded model. In the following we write w j= Q to mean that the query Q is true in the well-founded model of the program w .
The probability of a query Q according to an LPAD T is given by P (Q) =
X 2E(Q)
P ( ) (1) where we de ne E(Q) as f 2 ST ; w j= Qg, the set of selections corresponding to worlds where the query is true.
To reduce the computational cost of answering queries in our experiments, random variables can be directly associated to clauses rather than to their ground instantiations: atomic choices then take the form (Ci; k), meaning that head hik is selected from program clause Ci, i.e., that Xi = k.
Example 1. The following LPAD T encodes a very simple model of the development of an epidemic or pandemic:
C1 = epidemic : 0:6; pandemic : 0:3 : f lu(X); cold: C2 = cold : 0:7: C3 = f lu(david):
C4 = f lu(robert): Clause C1 has two groundings, C1 1 with 1 = fX=davidg and C1 2 with 2 = fX=robertg, so there are two random variables X11 and X12; C2 has only one grounding that is associated to the variable X21. X11 and X12 have three values since C1 has three head atoms (epidemic, pandemic, null); similarly X21 has two values since C2 has two head atoms (cold, null).
The worlds in which a query is true can be represented using a Multivalued
Decision Diagram (MDD) [
X11 X12 X21 2
3 1 1 kkkkkkk1kkkkkk 3 1 1 TTTTTTT2TTTTTT
2 (a) MDD.
0
Y V T R O L 0
It is often unfeasible to nd all the worlds where the query is true so inference algorithms nd instead explanations for it, i.e. composite choices such that the query is true in all the worlds whose selections are a superset of them. Explanations however, di erently from possible worlds, are not necessarily mutually exclusive with respect to each other, but exploiting the fact that MDDs split paths on the basis of the values of a variable and the branches are mutually disjoint so a dynamic programming algorithm can be applied for computing the probability.
Most packages for the manipulation of decision diagrams are however restricted to work on Binary Decision Diagrams, i.e., decision diagrams where all the variables are Boolean. A node n in a BDD has two children: the 1-child, indicated with child1(n), and the 0-child, indicated with child0(n). The 0-branch, the one going to the 0-child, is drawn with a dashed line.
To work on MDDs with a BDD package we must represent multivalued
variables by means of binary variables. For a multivalued variable Xij ,
corresponding to ground clause Ci j , having ni values, we use ni 1 Boolean variables
Xij1; : : : ; Xijni 1 and we represent the equation Xij = k for k = 1; : : : ni 1
by means of the conjunction Xij1 ^ Xij2 ^ : : : ^ Xijk 1 ^ Xijk, and the
equation Xij = ni by means of the conjunction Xij1 ^ Xij2 ^ : : : ^ Xijni 1. Figure
1(b) shows the reduced BDD corresponding to the MDD in Figure 1(a). BDDs
can be used for computing the probability of queries by associating to each
Boolean variable Xijk a parameter ik that represents P (Xijk = 1). If we
dene g(i) = fjj j is a substitution grounding Cig then P (Xijk = 1) = ik for all
j 2 g(i). The parameters are obtained from those of multivalued variables in
this way:
i1 =
EMBLEM applies the algorithm for performing EM over BDDs, proposed in
[
Then EMBLEM enters the EM cycle, in which the steps of expectation and maximization are repeated until the log-likelihood of the examples reaches a local maximum. The necessity of exploiting EM depends on the fact that, to determine the parameters ik, the number of times that a head hik has been chosen is required. The information about which selection was used in the derivation of a goal is unknown, so the random variables are hidden and we compute expected counts. For a single example Q: { Expectation: computes E[cik0jQ] and E[cik1jQ] for all rules Ci and k = 1; : : : ; ni 1, where cikx is the number of times a variable Xijk takes value x for x 2 f0; 1g, with j in g(i). E[cikxjQ] is given by Pj2g(i) P (Xijk = xjQ): { Maximization: computes ik for all rules Ci and k = 1; : : : ; ni 1. ik =
E[cik1jQ] E[cik0jQ] + E[cik1jQ] (2) If we have more than one example the contributions of each example simply sum up when computing E[cijx].
P (Xijk = xjQ) is given by P (Xijk = xjQ) = P (Xijk=x;Q) with
P (Q) P (Xijk = x; Q) = X P (Q; Xijk = x; ) where P (Xijk = 1j ) = 1 if (Ci; j; k) 2 for k = 1; : : : ; ni 1 and 0 otherwise.
Since there is a one to one correspondence between the possible worlds where Q is true and the paths to a 1 leaf in a Binary Decision Tree (a MDT with binary variables), where is a path, and if corresponds to , then P (Xijk = xj )=P (Xijk = xj ). R(Q) is the set of paths in the BDD for query Q that lead to a 1 leaf, d is an edge of and (d) is the probability associated to the edge: if d is the 1-branch from a node associated to a variable Xijk, then (d) = ik, if d is the 0-branch from a node associated to a variable Xijk, then (d) = 1 ik.
Now consider a BDT in which only the merge rule is applied, fusing together
identical sub-diagrams. The resulting diagram, that we call Complete Binary
Decision Diagram (CBDD), is such that every path contains a node for every
level. For a CBDD, P (Xijk = x; Q) can be further expanded as
where (Xijk = x) 2 means that contains an x-edge from a node associated
to Xijk. We can then write
where N (Q) is the set of nodes of the CBDD, v(n) is the variable associated to
node n, Rn(Q) is the set containing the paths from the root to n and Rn(Q; x)
is the set of paths from n to the 1 leaf through its x-child.
where ikx is ik if x=1 and (1 ik) if x=0. F (n) is the forward probability [
The expression F (n)B(childx(n)) ikx represents the sum of the probabilities of all the paths passing through the x-edge of node n and is indicated with ex(n). Thus For the case of a BDD, i.e., a diagram obtained by applying also the deletion rule, Formula 3 is no longer valid since also paths where there is no node associated to Xijk can contribute to P (Xijk = x; Q). These paths might have been obtained from a BDD having a node m associated to variable Xijk that is a descendant of node n along the 0-branch and whose outgoing edges both point to child0(n). The correction of formula (3) to take into account this aspect is applied in the Expectation step.
EMBLEM's main procedure consists of a cycle in which the procedures Expectation and Maximization are repeatedly called. Procedure Expectation returns the log likelihood of the data that is used in the stopping criterion: EMBLEM stops when the di erence between the log likelihood of the current iteration and the one of the previous iteration drops below a threshold or when this di erence is below a fraction of the current log likelihood.
Procedure Expectation takes as input a list of BDDs, one for each example, and computes the expectations for each one, i.e. P (Xijk = x; Q) for all variables Xijk in the BDD and values x 2 f0; 1g. In the procedure we use x(i; k) to indicate Pj2g(i) P (Xijk = x; Q). Expectation rst calls GetForward and GetBackward that compute the forward, the backward probability of nodes and x(i; k) for non-deleted paths only. Then it updates x(i; k) to take into account deleted paths. The expectations are updated in this way: for all rules i and for k = 1 to ni 1, E[cikx] = E[cikx] + x(i; k)=P (Q).
Procedure Maximization computes the parameters values for the next EM iteration, as speci ed in (2).
Procedure GetForward traverses the diagram one level at a time starting from the root level, where F(root)=1, and for each node n it computes its contribution to the forward probabilities of its children. Then the forward probabilities of both children are updated in this way: F (childx(node)) = F (childx(node)) + F (node) ikx.
Function GetBackward computes the backward probability of nodes by traversing recursively the tree from the leaves to the root. When the calls of GetBackward for both children of a node n return, we have all the information that is needed to compute the ex values and the value of x(i; k) for non-deleted paths. An array & is used here to store the contributions of the deleted paths by starting from the root level and accumulating &(l) for the various levels l.
A fully detailed description of EMBLEM together with an example of its
execution can be found in [
Our work has close connection with various other works. [
Approaches for learning probabilistic logic programs can be classi ed into
three categories: those that employ constraint techniques (such as [
Among the approaches that use EM, [
Among the works that use a gradient descent technique, LeProbLog [
Alchemy [
EMBLEM has been tested over three real world datasets: IMDB1, UW-CSE2 [
To compare our results with LeProbLog we exploited the translation of
LPADs into ProbLog proposed in [
For the probabilistic logic programming systems (EMBLEM, RIB, CEM and
LeProbLog) we consider various options. The rst consists in choosing between
1 http://alchemy.cs.washington.edu/data/imdb
2 http://alchemy.cs.washington.edu/data/uw-cse
3 http://alchemy.cs.washington.edu/data/cora
4 http://www.dcc.fc.up.pt/~vsc/Yap
associating a distinct random variable to each grounding of a probabilistic clause
or a single random variable to a non-ground probabilistic clause expressing
whether the clause is used or not. The latter case makes the problem easier. The
second option is concerned with imposing a limit on the depth of derivations
as done in [
IMDB regards movies, actors, directors and movie genres and it is divided
into ve mega-examples. We performed training on four mega-examples and
testing on the remaining one. Then we drew a Precision-Recall curve and computed
the Area Under the Curve (AUCPR) using the method reported in [
For predicting sameperson=2 we used the same LPAD of [
The queries that LeProbLog takes as input are obtained by annotating with
1.0 each positive example for sameperson=2 and with 0.0 each negative
example for sameperson=2. We ran LeProbLog for a maximum of 100 iterations or
until the di erence in Mean Squared Error (MSE) between two iterations got
smaller than 10 5; this setting was used in all the following experiments as well.
For Alchemy we always used the preconditioned rescaled conjugate gradient
discriminative algorithm [
A second LPAD has been created to evaluate the performance of the algorithms when some atoms are unseen: sameperson_pos(X,Y):p:- movie(M,X),movie(M,Y). sameperson_pos(X,Y):p:- actor(X),actor(Y),
workedunder(X,Z),workedunder(Y,Z). sameperson_pos(X,Y):p:- director(X),director(Y),genre(X,Z), genre(Y,Z). sameperson_neg(X,Y):p:- movie(M,X),movie(M,Y). sameperson_neg(X,Y):p:- actor(X),actor(Y),
workedunder(X,Z),workedunder(Y,Z). sameperson_neg(X,Y):p:- director(X),director(Y),genre(X,Z), genre(Y,Z). sameperson(X,Y):p:- \+ sameperson_pos(X,Y), sameperson_neg(X,Y). sameperson(X,Y):p:- \+ sameperson_pos(X,Y),\+ sameperson_neg(X,Y). sameperson(X,Y):p:- sameperson_pos(X,Y), sameperson_neg(X,Y). sameperson(X,Y):p:- sameperson_pos(X,Y), \+ sameperson_neg(X,Y). The sameperson_pos/2 and sameperson_neg/2 predicates are unseen in the data. Settings are the same as the ones for the previous LPAD. In this experiment Alchemy was run with the withEM option that turns on EM learning.
Table 1 shows the AUCPR averaged over the ve folds for EMBLEM, RIB, LeProbLog, CEM and Alchemy. Results for the two LPADs are shown respectively in the IMDB-SP and IMDBu-SP rows. Table 2 shows the learning times in hours.
For predicting samemovie=2 we used the LPAD: samemovie(X,Y):p:- movie(X,M),movie(Y,M),actor(M). samemovie(X,Y):p:- movie(X,M),movie(Y,M),director(M). samemovie(X,Y):p:- movie(X,A),movie(Y,B),actor(A),director(B), workedunder(A,B). samemovie(X,Y):p:- movie(X,A),movie(Y,B),director(A),director(B), genre(A,G),genre(B,G).
To test the behaviour when unseen predicates are present, we transformed the program for samemovie=2 as we did for sameperson=2, thus introducing the unseen predicates samemovie pos=2 and samemovie neg=2. We ran EMBLEM on them with no depth bound, one variable for each instantiation of the rules and one random restart. With regard to LeProbLog and Alchemy, we ran them with the same settings as IMDB-SP and IMDBu-SP, by replacing sameperson with samemovie.
Table 1 shows, in the IMDB-SM and IMDBu-SM rows, the average AUCPR for EMBLEM, LeProblog and Alchemy. For RIB and CEM we obtained a lack of memory error (indicated with \me"); Table 2 shows the learning times in hours.
The Cora database contains citations to computer science research papers. For each citation we know the title, authors, venue and the words that appear in them. The task is to determine which citations are referring to the same paper, by predicting the predicate samebib(cit1,cit2).
From the MLN proposed in [
haswordauthor(C,word_a).
The dots stand for the rules for all the possible words. The Cora dataset comprises ve mega-examples each containing facts for the four predicates samebib=2, samevenue=2, sametitle=2 and sameauthor=2, which have been set as target predicates. We used as negative examples those contained in the Alchemy dataset. We ran EMBLEM on this LPAD with no depth bound, a single variable for each instantiation of the rules and a number of restarts chosen to match the execution time of EMBLEM with that of the fastest other algorithm.
The second LPAD adds to the previous one four transitive rules of the form samebib(A,B):p :- samebib(A,C),samebib(C,B). for every target predicate, for a total of 563 rules. In this case we had to run EMBLEM with a depth bound equal to two and a single variable for each non-ground rule; the number of restarts was one. As for LeProbLog, we separately learned the four predicates because learning the whole theory at once would give a lack of memory error. We annotated with 1.0 each positive example for samebib=2, sameauthor=2, sametitle=2, samevenue=2 and with 0.0 the negative examples for the same predicates. As for Alchemy we learned weights with the four predicates as the non-evidence predicates. Table 1 shows in the Cora and CoraT (Cora transitive) rows the average AUCPR obtained by training on four mega-examples and testing on the remaining one. CEM and Alchemy on CoraT gave a lack of memory error while RIB was not applicable because it was not possible to split the input examples into smaller independent interpretations as required by RIB.
The UW-CSE dataset contains information about the Computer Science department of the University of Washington through 22 di erent predicates, such as yearsInProgram/2, advisedBy/2, taughtBy/3 and is split into ve mega-examples. The goal here is to predict the advisedBy/2 predicate, namely the fact that a person is advised by another person: this was our target predicate. The negative examples have been generated by considering all couple of persons (a,b) where a and b appear in an advisedby/2 fact in the data and by adding a negative example advisedby(a,b) if it is not in the data.
The theory used was obtained from the MLN of [
The annotated queries that LeProbLog takes as input have been created by annotating with 1.0 each positive example for advisedby=2 and with 0.0 the negative examples. As for Alchemy, we learned weights with advisedby/2 as the only non-evidence predicate. Table 1 shows the AUCPR averaged over the ve mega-examples for all the algorithms.
Table 3 shows the p-value of a paired two-tailed t-test at the 5% signi cance level of the di erence in AUCPR between EMBLEM and RIB/LeProbLog/CEM/ Alchemy (signi cant di erences in bold).
From the results we can observe that over IMDB EMBLEM has comparable performances with CEM for IMDB-SP, with similar execution time. On IMDBuSP it has better performances than all other systems, with a learning time equal to the fastest other algorithm. On IMDB-SM it reaches the highest area value in less time (only one restart is needed). On IMDBu-SM it still reaches the highest area with one restart but with a longer execution time. Over Cora it has comparable performances with the best other system CEM but in a signi cantly lower time and over CoraT is one of the few systems to be able to complete learning, with better performances in terms of area and time. Over UW-CSE it has signi cant better performances with respect to all the algorithms.
Memory errors, that we encountered with some systems over certain datasets, have to be ascribed to the memory needs of the systems; for instance, some of them are not able to manage the LPAD for CoraT because its transitive rules generate large BDDs. 6
We have proposed a technique which applies an EM algorithm for learning the parameters of Logic Programs with Annotated Disjunctions. It can be applied to all languages that are based on the distribution semantics and exploits the BDDs that are built during inference to e ciently compute the expectations for hidden variables.
We executed the algorithm over the real datasets IMDB, UW-CSE and Cora, and evaluated its performances - together with those of four other probabilistic systems - through the AUCPR and AUCROC. These results show that EMBLEM uses less memory than RIB, CEM and Alchemy, allowing it to solve larger problems, as one can see from Table ?? where, for some datasets, not all the mentioned algorithms are able to terminate. Moreover its speed allows to perform a high number of restarts making it escape local maxima and achieve higher AUCPR.
EMBLEM is available in the cplint package in the source tree of Yap Prolog and information on its use can be found at http://sites.google.com/a/ unife.it/ml/emblem.
In the future we plan to extend EMBLEM for learning the structure of LPADs by combining the standard Expectation Maximization algorithm, which optimizes parameters, with structure search for model selection.