This paper introduces a method for algorithmic reduction of the search space of an ILP task, omitting the need for explicit language bias. It relies on bottom-up propositionalisation of examples and background knowledge. A proof of concept has been developed for observational learning of strati ed normal logic programs.
Machine learning can be de ned as automatic program improvement in certain
tasks through experience [
Most ILP tasks take as input a tuple: positive examples, negative examples,
background knowledge and language bias. Language bias serves to restrict the
search space, as it de nes which predicates can appear in the hypotheses, in
addition to any constraints that may apply. Speci cation of language bias
arguably requires prior knowledge of the form the hypothesis should be in, which
may not always be available. On the other hand, the size of an unconstrained
search space makes an unguided traversal intractable. One way to reduce the
search space is by propositionalisation. Propositionalisation techniques aim to
transform the task from a relational to an attribute-value form, which makes it
easier to learn, but possibly loses some information [
This work aims at restricting the search by nding clues of relevance that are inherent in the examples and background knowledge, utilising a combination of incremental propositionalisation and extended set operations, omitting the need for language bias. Our contribution is two-fold: a de nition of bottom-up propositionalisation for rst-order logic programs, and an algorithmic mechanism for generating ILP-hypotheses that uses these propositional features. A brief background is presented in the next section. We describe the workings of our approach in section 3, along with an illustrative example. A discussion of related work is presented in section 4.
Before delving into learning with bottom-up propositionalisation, it is useful to rst formally de ne an ILP task and present an overview of how ILP learners typically work.
De nition 1. Let L be a language and let T be the learning task of our approach, where T=hM; B; E+; E i, de ned in L, where: M Mode declarations, where LM is the language restricted by M . B Background knowledge, a logic program.
E+ Positive examples, a set of ground atoms of the same predicate. E Negative examples, also a set of ground atoms of the same predicate as E+
The hypotheses space of an ILP problem has a lattice structure, with partial ordering based on hypothesis generality and subsumption. (We say that H H0 , H j= H0). Existing systems vary on how they traverse this search space; with a top-down approach, overly general hypothesis are re ned until they are consistent with negative examples, and branches that do not cover some of the positives are pruned. With a bottom-up, only clauses that do not cover any negatives are generalised, until a solution to the task is found.
We take a di erent approach towards nding a solution, which does not traverse the hypotheses space one-step at a time. Propositional features are constructed bottom-up, and then a subset of these is selected -depending on their coverage of examples- to nd a solution. Since all examples are considered at each step, it allows for learning normal logic programs. 3
Given a set of examples, it is intuitive to try to de ne them by discerning which characteristics they have in common, which separate them from the instances that are known not to belong to that concept. How can we identify these characteristics in ILP tasks? This is the basis upon which this work is held.
Propositionalisation is done bottom-up in the sense that instead of starting out with templates of the features and checking which of them are satis ed, we generalise the existing atoms. The atoms that are generalised are the ones in the model of the background program and are relevant to some given example, with respect to how that example maps to the target hypothesis head. We present a few de nitions before explaining the approach step by step.
The entire details of the work and reasoning behind some design decisions,
along with proofs on correctness and minimality are in [
We extend set operations to account for generality ordering between atoms, by checking subsumption. Below are the de nitions for these extended operations: De nition 2 (\ ). Let A,B be sets of (possibly ground) atoms and a be one such atom, a 2 A \ B if f either a 2 A ^ (a 2 B _ 9a0 2 B a 2 B ^ (a 2 A _ 9a0 2 A s:t: a j= a0) s:t: a j= a0) If we assume that sets A and B do not contain predicates in multiple levels of generality in the same set, keeping only the most speci c form, then A \ B will contain only the predicates common to both sets, in the most general form. De nition 3 (n ). Let A,B be sets of (possibly ground) atoms and a be one such atom, a 2 A n B if f a 2 A ^ (a 62 B^ 6 9a0 2 B s:t: a j= a0) De nition 4 (Target atom). Let T=hB; E+; E i, a target atom is an unground atom such that target = lgg(e1; : : : ; en) 8e 2 E+.
Example 1. Let E+ = fp(a); p(b); p(c)::g then target= p(X) The target atom represents the head of the main clause in the hypothesis; using least-general-generalisation helps identify constants, and eliminates negative examples that are not subsumed by the target atom.
De nition 5 (M(e)). Let e be an example, M(e) is a mapping of terms in e to head (universally quanti ed) variables, more formally: M(e) = fti 7! Vi where Vi 7! ti 2 ^ target = eg M(e) can be seen as the inverse of the substitution in target = e. Instead of matching each variable with a term, we match each term with the variable's symbol, to be used in generalising atoms later.
Example 2. Let target be p(X, Y), e1 = p(a,b), and e2 = p(c,c), then M(e1) = fa 7! X; b 7! Y g and M(e2) = fc 7! fX; Y gg De nition 6 (Links(term)). Let t be a constant term, B some logic program, links(t) is a set of all atoms in the model of B that contain the term t, more formally: links(t) = fp(t1; : : : ; tn)jp(t1; : : : ; tn) 2 model(B) ^ t = ti for some i 1 i ng For each example, we construct sets of relevant atoms entailed by the background program. To know which atoms are relevant to each example, we link the atoms based on the terms that occur in both of them.
Example 3. Let B = fq(a):s(b):r(a; b):s(a):g then links(a) = fq(a); r(a; b); s(a)g De nition 7 (Generalise(a, M(e))). Let a be a ground atom, M(e) is a mapping as de ned in de nition 5, Generalise(a, M(e)) is a set of unground atoms where terms are replaced by their mapping in M(e), and terms not in M(e) are replaced with a new skolem variable.
Generalisation of an atom is an ungrounding process that is a direct substitution of the ground term to the variable symbol it maps to in M(e). The same atom can be generalised to di erent features depending on the mapping it uses, which in turn depends on the example used. 3.2
Our work takes on a more algorithmic approach to solving an ILP problem, the basic steps of Bottom-up Propositionalisation ILP are outlined below: Algorithm 1: BPILP: Bottom-up Propositionalisation ILP
Input: B: Background Program, E+: Positive Examples and E : Negative Examples
Output: HMin: Minimal hypothesis 1 M model(B) 2 T arget lgg(e1; e2; : : : en) 8ei 2 E+ 3 foreach e in E+and E do 4 M(e) term to variable mapping wrt T arget 5 Links(e) all atoms in M with at least one term in e 6 F eats(e) Generalise(a, M(e)) 8a 2 Links(e) 7 body+ T (F eats(ei+)) 8ei+ 2 E+ 8 body ff jf 2 S(F eats(ej )) n S(F eats(ei+))
^ 6 9V 2 args(f ) s:t: is skolem(V ) 8ei+ 2 E+ 8ej 2 E g 9 H fT arget:- b1+; : : : ; bn+; not b1 ; : : : ; not bm:jbi+ 2 body+ ^ bj 2 body g 10 if H is a solution then 11 HMin reduce(H) 12 else 13 14 15 return HMin expand skolem variables in body+ (by repeating steps 3, 4 and 5) or add auxiliary predicate de nitions until a solution is found
HMin reduce(H)
First, we get the unique model of the background program by feeding it to an ASP solver3. We then nd the target atom which will represent the head of main clause of the hypothesis, by nding the lgg of positive examples. Afterwards a set is constructed for each given example in the ILP task, containing the links for all terms in that example. These sets are then generalised relative to the 3 We assume B is a strati ed normal logic program, with no occurrence of the target predicate example and the target hypothesis head (using the mapping as de ned in def 5), only the most speci c generalisations are kept as features.
The importance of bottom up propositionalisation lies in the reduction of propositional features to work with; if we have t variables in the clause head, an n-ary predicate can be generalised in (t + 1)n ways (since each argument can take any one of the head variables or a new skolem). By simply generalising our links, we obviate the need to construct all of these feature templates and check for their satisfaction. BPILP produces a way that is able to compare the generalisations between the example feature sets in order to easily nd the features that discriminate positive from negative examples.
We test the resulting hypothesis, if it satis es the problem we reduce it by removing redundant literals based on their coverage. Otherwise, we repeat the linking and generalising step for the features in body+ which contain skolem variables, such that propositionalisation is incremental. This is currently constrained by setting a nite length for the depth of skolem variable expansion.
If the previous step does not result in satisfying features, the algorithm adds a new predicate, not in L. This invented predicate can be de ned by multiple clauses, each containing complementary features, or by a negative feature with a skolem variable.
Example 4. A demonstration of BPILP on a full task, where:
T = hB = fq(X) : w(X); not t(X): t(a): t(b): t(c): w(c): w(d):g; E+ = fp(a): p(b):g; E = fp(c): p(d):gi 1. Get model 2. Find target
4. M(e) 5. Generalise Links 6. Saturated Hypothesis 7. Reduce Hypothesis 4
M = fq(d): t(a): t(b): t(c):
w(c): w(d):g
T arget = lgg(p(a); p(b)) = p(X) e1 ft(a):g fa 7! Xg ft(X):g
e2 ft(b):g e3
e4 ft(c): w(c):g
fq(d): w(d):g fb 7! Xg fc 7! Xg fd 7! Xg ft(X):g ft(X): w(X):g fq(X): w(X):g p(X) : t(X); not w(X); not q(X): p(X) : not w(X): We introduced an algorithmic approach to tackle ILP tasks without the need for explicit language bias to restrict the search space, by powering bottom-up propositionalisation.
There is some work into trying to learn the language bias, McCreath and
Sharma[
Some ILP learning frameworks do not require language bias in their task
de nition, such as FOIL[
The latter framework, MIL, boasts suitability for recursive de nitions and predicate invention. It works by augmenting the background program with a meta-interpreter, which abduces higher order de nite clauses, known as meta rules. However, it requires a total ordering over the predicate and object symbol sets to guarantee termination. Moreover, the current implementation constrains the language to a subset of H22, which may compromise intuitive formulation of the problem. It does not learn normal logic hypotheses.
Propositionalisation is done in our work in a bottom-up manner to make it
more tractable, hence not all propositional templates (top-down) are considered,
as in the widely-known LINUS [
Franca et. al.[
We have introduced a novel approach to solving observational ILP tasks in which
language bias is omitted in favour of algorithmic bias, by utilising
incremental, bottom-up propositionalisation. It supports predicate invention to facilitate
learning in some cases. It is able to learn normal logic program hypotheses for
problems with strati ed background programs, and has proved to work well on
common problems, such as the Eastbound Trains [
This work was funded by a postgraduate scholarship awarded by King Saud University.