My research activity focuses on the field of Machine Learning. Two key challenges in most machine learning applications are uncertainty and complexity. The standard framework for handling uncertainty is probability, for complexity is first-order logic. Thus we would like to be able to learn and perform inference in representation languages that combine the two. This is the focus of the field of Statistical Relational Learning. My research is based on the use of the vast plethora of techniques developed in the field of Logic Programming, in which the distribution semantics [16] is one of the most prominent approaches. This semantics underlies, e.g., Probabilistic Logic Programs,Probabilistic Horn Abduction,PRISM [16], Independent Choice Logic,pD,Logic Programs with Annotated Disjunctions (LPADs) [17], ProbLog [5] and CP-logic. These languages have the same expressive power: there are linear transformations from one to the others. LPADs offer the most general syntax, so my research and experimentations has been focused on this formalism. An LPAD consists of a finite set of disjunctive clauses, where each of the disjuncts in the head of a clause is annotated with the probability of the disjunct to hold, if the body of the clause holds. LPADs are particularly suitable when reasoning about actions and effects where we have causal independence among the possible different outcomes for a given action. Various works have appeared for solving three types of problems for languages under the distribution semantics: - inference: computing the probability of a query given the model and some evidence: most algorithms find explanations for queries and compute their probability by building a Binary Decision Diagram (BDD) [5,15,10]; - learning the parameters: for instance, LeProbLog [6] uses gradient descent while LFI-ProbLog [7] uses an Expectation Maximization approach where the expectations are computed directly using BDDs; - learning the structure: in [13] a theory compression algorithm for ProbLog is presented, in [12] ground LPADs are learned using Bayesian network techniques.
A different approach from distribution semantics is represented by Markov
Logic: a Markov Logic Network (MLN) is a first-order knowledge base with a
weight attached to each clause, reflecting “how strong” it is. For this language
inference, parameter and structure learning algorithms are available as well, see
[
By means of the development of systems for solving the above problems, one would like to handle classical machine learning tasks, such as Text Classification, Entity Resolution, Link Prediction, Information Extraction, etc., in real world domains. An example of Text Classification problem is given by the WebKB dataset, containing the text of web pages from 4 universities; each page belongs to one of four classes: course, faculty, research project or student. Given words on the pages, one wish to infer the class. Entity Resolution concerns the problem of information integration from multiple sources, where the same entities can be differently described. An example is represented by the Cora dataset, containing citations of computer science publications, since citations of the same paper often appear differently.
I have considered the problem of learning the parameters and both the parameters and the structure of LPADs by developing three learning systems: section 2 presents a parameter learning algorithm based on Expectation Maximization, section 3 presents two algorithms for structure learning that exploit the first. 2
An LPAD is composed of annotated disjunctive clauses Ci of the form
hi1 : Πi1; . . . ; hini : Πini : −bi1, . . . , bimi . where hi1, . . . hini are logical atoms,
bi1, . . . , bimi are logical literals and {Πi1, . . . , Πini } are real numbers in the
interval [
An LPAD rule containing variables represents a number of “simple experiments”, one for each ground instantiation of the rule (obtained by replacing variables with constants of the domain), with the disjuncts as the possible outcomes. For each ground instantiation of a rule only one pair (h : Π) is chosen; in this way a normal non-disjunctive logic program is obtained, called possible world. A probability distribution is defined over the space of possible worlds by assuming independence among the selections made for each rule. The probability of a possible world is the product of probabilities of the individual heads chosen in each rule. The probability of a query Q according to an LPAD is given by the sum of the probabilities of the possible worlds where the query is true. Example 1. The following LPAD T encodes the result of tossing a coin depending on the fact that it is biased or not:
C1 = heads(Coin) : 0.5; tails(Coin) : 0.5 : −toss(Coin), ¬biased(Coin). C2 = heads(Coin) : 0.6; tails(Coin) : 0.4 : −toss(Coin), biased(Coin). C3 = f air(coin) : 0.9; biased(coin) : 0.1.
C4 = toss(coin) : 1. This program models the fact that a fair coin lands on heads or on tails with probability 0.5, while a biased coin with probabilities 0.6 and 0.4 respectively. The third clause says that a certain coin coin has a probability of 0.9 of being fair and of 0.1 of being biased, the fourth one that coin is certainly tossed.
Each selection of a disjunct in a ground clause of an LPAD can be represented by the equation Xij = k, where k ∈ {1, . . . , ni} indicates the head chosen, Xij is a multivalued random variable where i and j indicate the clause and the grounding. A function f (X), built on a set of multivalued variables and taking Boolean values, can be represented by a Multivalued Decision Diagram (MDD), a rooted graph that has one level for each variable. Each node has one child for each possible value of the associated variable. The leaves store either 0 or 1, the possible values of f (X). Given values for all the variables X, a MDD can be used for computing the value of f (X) by traversing the graph starting from the root and returning the value associated to the leaf that is reached. An example of such function is: f (X) = {X11 = 1 ∨ X21 = 2 ∧ X31 = 1 ∨ X22 = 3 ∧ X31 = 1}. A MDD can be used to represent the set of selections over rules, and will have a path to a 1-leaf for each possible world where a query Q is true. It is often unfeasible to find all the worlds where the query is true so inference algorithms find instead explanations for the query, i.e. set of selections such that the query is true in all the worlds whose selection is a superset of them. Since MDDs split paths on the basis of the values of a variable, the branches are mutually disjoint so that a dynamic programming algorithm can be applied for computing the probability of a query by a summation. Usually one works on MDDs with a Binary Decision Diagram package, so one has to represent multivalued variables by means of Boolean variables.
The problem I faced is how to efficiently perform “parameter learning”, i.e.,
using training data for learning correct probabilities Πik. The technique applied
exploits the EM (Expectation Maximization) algorithm over BDDs proposed in
[
EMBLEM takes as input a set of interpretations (sets of ground facts), each describing a portion of the domain of interest, and a theory (LPAD). The user has to indicate which, among all predicates, are target predicates: the facts for these predicates will form the queries for which a SLD-proof is computed; from these proofs a BDD is built encoding the Boolean formula consisting of the disjunction of the explanations for the query.
Then EMBLEM performs an EM cycle, in which the steps of Expectation and Maximization are repeated until the log-likelihood of the examples reaches a local maximum. Expectations are computed directly over BDDs. EM is necessary to determine the parameters Πik since the number of times that head hik is chosen is required. The information about which selection was used is unknown, so the “choice” variables are latent and the number of times is a sufficient statistic.
Decision Diagrams are suitable to efficiently evaluate the expectations since the set of selections used for the derivation of the examples can be represented as the set of paths from the root to the 1-leaf.
The first system developed for LPADs’ structure learning is SLIPCASE, for
“Structure LearnIng of ProbabilistiC logic progrAmS with Em over bdds” [
I am now working on SLIPCOVER, an evolution of SLIPCASE which first searches the space of clauses and then the space of theories. SLIPCOVER performs a cycle for each predicate that can appear in the head of clauses, where a beam search in the space of clauses is performed: each clause (built according to a language bias) is tested on the examples for the predicate, its head parameters are learned with EMBLEM and the log likelihood of the data is used as its score. Then the clause is inserted into one of two lists of promising clauses: a list of target clauses, those for predicates we want to predict, and a list of background clauses, those for the other predicates. Then a greedy search in the space of theories is performed, in which each target clause is added to the current theory and the score is computed. If the score is greater than the current best the clause is kept in the theory, otherwise it is discarded. Finally parameter learning with EMBLEM is run on the target theory plus the clauses for background predicates.
The two systems can learn general LPADs including non-ground programs. 4
We experimented EMBLEM on the real datasets IMDB, Cora, UW-CSE, WebKB, MovieLens and Mutagenesis and evaluated its performances by means of the Area under the PR curve and under the ROC curve, in comparison with five logic-probabilistic learning systems. It achieves higher areas in all cases except two and uses less memory, allowing it to solve larger problems often in less time.
We tested SLIPCASE on the real datasets HIV, UW-CSE and WebKB, and
evaluated its performances - in comparison with [
We have tested the second structure learning algorithm on HIV, UW-CSE,
WebKB, Movielens, Mutagenesis and Hepatitis and evaluated it - in comparison
with SLIPCASE, [