The integration of abduction and induction has lead to a variety of non-monotonic ILP systems. XHAIL is one of these systems, in which abduction is used to compute hypotheses that subsume Kernel Sets. On the other hand, Peircebayes is a recently proposed logic-based probabilistic programming approach that combines abduction with parameter learning to learn distributions of most likely explanations. In this paper, we propose an approach for integrating probabilistic inference with ILP. The basic idea is to rede ne the inductive task of XHAIL as a statistical abduction, and to use Peircebayes to learn probability distribution of hypotheses. An initial evaluation of the proposed algorithm is given using synthetic data.
Inductive Logic Programming (ILP) is concerned with learning logic programs that, together with a background knowledge, explain given examples (or data). One of the greatest bene ts of ILP, with respect to other not logic-based machine learning, is that the learned programs are very easy to interpret in natural language. A disadvantage is, however, that it does not handle noise and uncertainty in the observations very well. On the other hand, machine learning methods that relay on Bayesian statistics are better in coping with uncertainty. Their objective is to nd parameters of statistical models that maximize the likelihood of the data. Inference on these models can be very e cient when applied to large data sets, but coming up with a correct probabilistic model, which is able to capture the conditional dependencies of the data may turn up to be a di cult task. Combining logic-based learning (or logic-based inference in general) and Bayesian statistics may result in symbolic models that can cope with uncertainty, bene ting from both higher accuracy and easy interpretation.
In [
Abduction has also been shown to be useful in inductive learning. The XHAIL
approach [
This paper explores a way of combining probabilistic inference with ILP in order to learn not only structured hypothesis but also probabilisitic distributions over the clauses that form such hypothesis. The method consists of re-de ning the inductive step of the XHAIL algorithm with a statical abduction computation. The Kernel Set, derived from the language bias of a given learning task, is rede ned as a special type of annotated literal program, in which each literal is associated with a unique probabilistic parameter. Such a re-written Kernel is then taken as the input statistical abductive program of Peircebayes. It is used as generative story for the computation of literals in the hypothesis that are (logically) relevant to the given data, and statistically for the learning of probability distributions over these literals. The outcome is the learning of probabilistic distributions over clauses that form inductive solutions. Preliminary evaluation over synthetic data show some promising results.
The paper is organised as follows. First, we cover some background on XHAIL and Peircebayes. In Section 3, we illustrate our new PROBXHAIL algorithm with an example. In Section 4, we de ne the semantics of the Annotated Literal Programs, a new kind of probabilistic logic program, which are output by PROBXHAIL. We conclude with a brief evaluation and nal remarks. 2
In this section, we brie y introduce XHAIL and Peircebayes, the two building blocks of our proposed approach.
XHAIL is an ILP algorithm that combines induction and abduction in several ways. It uses an abductive-deductive procedure to compute a Kernel Set, a set of (normal) clauses that represent a most-speci c hypothesis that cover the given data. Then, it performs induction on the Kernel Set to compute a most general hypothesis that subsumes the Kernel Set, whilst preserving the same coverage. This step is re-expressed as an abductive task in which each explanation represents a single hypothesis that subsumes the Kernel Set and does not contradict any example. This inductive procedure is of particular interest for this paper. We show how to replace this step with statical abduction in order to perform Probabilistic ILP. In what follows we present the abductive representation used by XHAIL for computing inductive solutions and the statistical abduction for computing a probability distribution on abducibles. In Section 3 we describe how our approach combines these two techniques. Consider a set of C = f1 : : : kg clauses of the form c c1; : : : ; cmc . The associated abductive logic programming reformulation of such a set is the program obtained by replacing every clause c f ci gim=c1 by the following set of clauses: { c use(c; 0); try(c; 1; vars( c1)); : : : ; try(c; mc; vars( cmc )), where vars( ) represents the list of variables in the literal . { for every body literal in f cgim=c1 the following two clauses are included: i try(c; i; vars( ci )) not use(c; i): try(c; i; vars( ci )) ci ; use(c; i): In the above reformulation, the ground literals use(c; i) and not use(c; i) constitute the set of abducibles.
Example 1. Let us assume K to be the most speci c Kernel Set computed by
XHAIL for a given set E of examples. The inductive generalisation step of XHAIL
constructs the associated abductive task < ; A; E >, where and A are
dened as follows1:
Traditionally, abduction is the task of infering a set of ground atoms, called
an explanation, that together with a given background theory entails a speci c
observation given by a conjunction of (ground) facts. This concept can be
generalized to probabilistic abduction by introducing probability distributions over
the truth values of each (ground) abducible and over the observations. This
probabilistic perspective provides a method of quantitatively estimating the quality
of the abductive solutions. Introducing probability in abduction essentially
rede nes the notion of abductive solutions as no longer the minimal but the most
preferred (possibly non minimal) assumptions, based on their probability, needed
to explain a speci c distribution of observations (e.g., [
Peircebayes is an algorithm that attempts to perform inference in a speci c probabilistic model for statistical abduction. In it, each abducible is associated with an independent categorical variable (referred to as parameter) with a userspeci ed Dirichlet prior (referred to as hyperparameter). The inference task is to compute the probability distribution of the parameters given the observations. 1 Note that in the actual implementation of the XHAIL algorithm, the abductive program also uses type matching for the bias and to ensure safe rules.
K = a b:
b:
= >><8 tary(0u; s1e)(0; 0b);;utsrey((00;;11)):: 9>>= A = 8< uussee((00;; 01)):: 9= >>: tbry(0u;s1e)(1; 0n):ot use(0; 1): >;> : use(1; 0): ; In probabilistic terms the observations can be seen as a vector f of N data points, where fn = 1 denotes that the n-th observation is included in the model. The novelty is that the draw of the values for the parameters is related to the \generative story" of the model expressed as an abductive task.d
In Peircebayes the inference task is to determine a distribution of most
likely explanations, i.e. to infer P ( jf ; ). Since the prior distribution is
conveniently chosen to be a Dirichlet distribution, the prior conjugate of the
categorical distribution, this task is equivalent to nding posterior values of . The
posterior expectation of can be computed via uncollapsed Gibbs Sampling
along P (xj ; f ) and P ( jx; ). Sampling from P ( jx; ) involves sampling from
a Dirichlet distribution (since the posterior of a categorical distribution with a
Dirichlet prior is also a Dirichlet distribution). Sampling from P (xj ; f ) can be
done by sampling paths in BDDs that describe the category of abducibles in the
abductive solutions of each observation. The reader is referred to [
This section describes the PROBXHAIL algorithm. For simplicity, we illustrate its
workings with a running example with propositional atoms. The program takes
as input a set of (partial) interpretations (see [
Example 2. PROBXHAIL could consist of the following input. The example set over 100000 observations could consist of hfa; bg; fgi repeated 62958 times, hfag; fbgi repeated 2727 times, hfbg; fagi repeated 27109 times and hfg; fa; bgi repeated 7206 times. Assume a mode bias that consists of modeh(a), modeb(b), modeh(b), determination(a,b) and prohibits repetition of clauses.
The output of PROBXHAIL is a probabilistic logic program, a normal logic program augmented with statistical parameters. Such a program has non-deterministic semantics: it de nes a distribution over deterministic normal logic programs and, hence, over partial interpretations of the program. For this reason, the number of occurrences of each example is relevant: the example set represents an empirical distribution of partial interpretations and the goal of PROBXHAIL is to produce a probabilistic logic program that de nes the same probability distribution over the examples. We describe the semantics of the probabilistic logic programming language in Section 4.
Overall, the algorithm consists of two phases: structure learning and parameter learning. During the structure learning phase, a deterministic normal logic program is constructed using the bias. During the parameter learning phase, the parameters for a set of Bernoulli random variables is learned, one for every literal. The parameters are such that the probability distribution of partial interpretations de ned by the program is as close as possible to the probability distribution implied by the examples.
More speci cally, the structural learning phase of the algorithm is currently purely bias-driven. During this step, the most speci c logic program that agrees with the bias is constructed. The bias is similar to the one de ned in other ILP systems and includes mode and determination declarations. In addition, it speci es the number of times a clause can be repeated (this is relevant in the probabilistic logic program, unlike in deterministic programs where clause repetitions are redundant). With propositional programs, this procedure involves constructing a clause for every head literal and then adding every body literal that agrees with the determinations.
This procedure can be generalized to normal logic programs with variable
terms (as shown in [
In the next step, parameter learning is performed. This is done by performing XHAILs inductive task transformation on the theory generated from the structural learning step and then performing Peircebayes statistical abduction with the generated background and the use ground atoms as abducibles and the input examples as observations. This produces an unbiased estimate of the parameters of the probabilistic logic program.
Example 3. Structural learning for Example 2 yields fa b: b:g. We construct the following Peircebayes task with observations O from Example 2 and background B and abducibles A, given in Example 1. The output of the PROBXHAIL algorithm is a probabilistic program in which every literal is associated with a Bernoulli trial parameter: It can be shown that the learned parameters minimize the posterior expected value of the root mean square error function of . 4
In this section, we de ne Annotated Literal Programs (the output of PROBXHAIL ). In these programs, every literal is associated with a probabilistic Bernoulli parameter. Annotated literal programs de ne a probability distribution on normal logic programs. Informally, we can de ne this probability distribution by the method we use to sample: every clause is considered independently and is included with the probability of its head literal. Only a subset of the body literals is retained in the clause. Each body literal is considered independently and included in the clause with its associated probability. Annotated literal programs are based on answer sets semantics: the probability of a query being successful is the sum of the probability of all normal logic programs that bravely entail it (i.e. the query is true in at least one of its answer sets).
Example 4. The probability distribution on logic programs described by the program in Example 3 is shown in the table below. The probability of query ?-a. is the sum of the probability of the normal logic programs that entail it. In this example, T1, T4 and T5 have answer sets which satisfy the query. Thus, the probability of the program is p(T1) + p(T4) + p(T5) = 0:6567804. Logic Program Answer Set fa b: b:g fa b:g fa:b:g
; fb:g fa:b:g fa:g ; Note that sampling from the probabilistic logic program involves a series of Bernoulli trials. During parameter learning in PROBXHAIL we can apply a Bayesian prior on the distributions in order to de ne a probabilistic bias. Currently only a symmetric Beta prior is used (as Peircebayes supports Dirichlet Priors on abducibles); however, the applications of a user-de ned prior is an open question.
It can be shown via a translation procedure [
We run an experiment in order to measure parameter learning error. We sample normal logic programs multiple times from a given probabilistic logic program and then compute their full interpretations. We use the resulting interpretations as input for PROBXHAIL and attempt to reconstruct the original probabilistic logic program used for the sampling. We then measure the runtime of learning and the root mean square error in the parameters learned versus the original parameters. For instance, the observations in Example 2 were generated from the following probabilistic program: Results show that the root mean square error of parameter learning in Example 3 decreases below 0.001 in 3 iterations of uncollapsed Gibbs sampling. Experiments with larger synthetic datasets suggest that the number of iterations necessary for convergence increases with the number of literals.
Overall, PROBXHAIL is prone to issues with its high-dimensional parametric search space. For example, the number of di erent possible observations increases exponentially with the number of clauses. Moreover, increasing the number of parameters requires an increased number of samples and Peircebayes iterations for convergence. As a consequence of this, maintaining the number of literals as low as possible is important. This implies that a structural learning procedure is necessary that minimizes the size of the probabilistic logic program.