Multiple Predicate Learning

1 Introduction

Recently, there has been an increased interest in ILP [Muggleton, 1992; De Raedt, 1992], resulting in a num­ ber of inductive systems employing first order logic as the representation formalism, e.g. MIS [Shapiro, 1983], FOIL [Quinlan, 1990], CIGOL [Muggleton and Buntine, 1988], CLINT [De Raedt 1992], GOLEM [Muggleton and Feng, 1990], LINUS fLavrae et al., 1991], FORTE [Richards and Mooney, 1991], AUDREY [Wogulis, 1991], and MOBAL [Kietz and Wrobel, 1992]. The problem ad­ dressed by all of these systems can be formulated as fol­ lows (cf. [Muggleton, 1992]): given is a background the­ ory B containing definitions of predicates in normal or definite clause logic and a set of positive and negative ex­ amples (true and false ground facts) E = PUN; the aim is to find a hypothesis H such that Vp E P : B U H ~ p and Vn E N : B U H ~ n, i.e. the background theory to­ gether with the hypothesis entails all positive and none of the negative examples.

In this paper, we investigate the complications that arise when the example set contains examples for mul­ tiple predicates. We study the problem in the empirical setting, i.e. under the following assumptions: the whole example set is given initially, no oracle can be consulted, and the initial theory contains no definitions for the pred­ icates to be learned.

The ILP literature has largely ignored this problem. Indeed, the empirical systems (such as FOIL, GOLEM, LINUS) are typically designed for single predicate learn­ ing. To learn multiple predicates, a knowledgeable teacher has to supply different learning sets such that all predicates can be learned, which is - as we will show - a non-trivial task. The extensional systems GOLEM and FOIL, however, can solve some multiple predicate learning tasks. For other tasks they may encounter a number of difficulties as shown in Section 3.

·Thia research ia part of the ESPRIT III project no. 6020 on Inductive Logic Programming. Luc ia funded by the Bel­ gian National Fund for Scientific Research, Nada and Saio are funded by the Slovenian Miniatry of Science and Technol­ ogy, and Nada's stay in Leuven was funded by the Belgian State-Policy-Office Grant Al/03/05.

The incremental systems (MOBAL, CIGOL, CLINT, MIS) can often cope with multiple predicates but fo­ cus the learning procedure on the most recently received example (MOBAL, CLINT, MIS) or generate questions to the user to reduce the search space (MIS, CIGOL, CLINT). These settings simplify the problem to a large degree. In the first case, the order of learning the predi­ cates (and treating the examples) is given, which is - as we will show - one of the main problems. In the second case, the oracle reduces (or even eliminates) the chance of learning incorrect (or overly general) clauses, which is - as we will show - the other main problem.

Finally, theory revisors such as FORTE and AUDREY are able to learn multiple predicates. However, AU­ DREY and FORTE leave a number of unsolved prob­ lems: the result of learning depends on the order of pro­ ceiBing the examples, AUDREY does not handle recur­ sive predicates, and both systems prefer an initial ap­ proximate domain theory.

Despite this state of the art, one could believe that learning multiple predicates is easy and that only slight changes to systems such as FOIL and GOLEM are re­ quired to learn multiple predicates. We show that this belief is essentially false. We also outline an alternative approach, the MPL algorithm, based on FOIL. It effec­ tively learns some predicate definitions beyond the scope of the other empiricaliLP systems.

In Section 2, we formalize the problem. In Section 3, we discu88 the difficulties with existing approaches when learning multiple predicates. In Section 4, we outline the MPL algorithm; in Section 5, we report on some prelim­ inary experiments and finally, in Section 6, we conclude.

2 Learning multiple predicates

As in the usual ILP setting, cf. [Muggleton, 1992; De Raedt, 1992], a theory is a set of normal or definite clauses (cf. [Lloyd, 1987]), ezample· are ground facts, po/Jitive examples are true in the intended interpretation and negative examples are false. The example set E is the union of positive and negative examples E = PUN. As we are learning multiple predicates, E contains ex­ amples form target predicates Pt 1 ··· ,J>m. We also divide E, P and N into m subsets Ep., Pp, and Np, according to these predicates. The predicates whose definitions are given initially in the background theory B are denoted as qt, ... , qz (Pi 'I q; ).

Definition 1 A hypothesis Hp i/J a /Jet of normal clatue/J for a predicate p.

Definition 2 An m-hypothesis H i/J a /Jet of normal clatue/J for m different predicate/J Pt 1 ····Pm· An m­ hypothe/Ju H i/J thtu the union of m hypothe/Je/J Hp, for i = 1, ... , m, H = Uf,;tHP··

Definition 3 An m-hypothe/Ji/J H cover/J an ezample e given a theory T iff T U H F e.

Definition 4 Given theory T, m-hypothe/Ji/J Hand ez­ ample /JetE, cover/J(T, H, E) = {e E E I TU H Fe}.

Definition 5 m-hypothe/Ji/J H i/J (globally) complete given ezample/J E and theory T iff cover/J(T, H, P) = P. Definition 6 m-hypothe/Ji/J H i/J (globally) con/Ji/Jtent given ezample/J E and theory T iff cover/J(T, H, N) = 0.

Assuming the hypothesis language of normal clauses, multiple predicate learning is defined as follows:

• Given:
• a set of training examples E for m different predicates Pt 1 ··· ,pm, and
• background theory B, containing predicate def­ initions for qt, ... , qz
• Find: an m-hypothesis H which is globally complete and consistent with regard to E and B.

The multiple predicate learning task is denoted by a triple mpl(B, H, E). It is illustrated in Example 1. A single predicate learning task is a special case of the above problem specification where m = 1. For a predi­ cate Pi, this task is denoted by 8pl(B, Hp., Ep.).

Notice that learning multiple predicates from exam­ ples is an important problem. One significant applica­ tion is in knowledge discovery, where one faces different phenomena and needs to relate them to each other. An­ other interesting application is logic program synthesis.

Example 1 We illustrate the problem of multiple predi­ cate learning on a relatively simple task where the back­ ground theory B is extensional and contains a complete set of facts for the background predicates parent, female and male. Completeness means that all positive and neg­ ative examples of the predicates are available to the sys­ tem (negative examples are generated under the CWA). The aim is to learn father, mother and ancestor from the complete set of examples for these predicates, under the usual interpretation of father, mother and ancestor. A complete and consistent 3-hypothesis H is:

ancestor(X,Y) +- parent(X,Y) ancestor(X,Y) +- parent(X,Z) 1\ ancestor(Z,Y) father(X,Y) +- parerit(X,Y) 1\ male(X) mother(X,Y) +- parent(X,Y) 1\ female(X)

The background theory B contains:

To elaborate our ideas in more detail, some additional terminology needs to be established. We make a distinc­ tion between local and global properties. Global proper­ ties of hypotheses and clauses are defined in the context of the entire example set E and the m-hypothesis H, whereas local properties are defined using Ep, and Hp,:

Definition 7 Hypothe/Ji/J Hp, i/J locally con~i/Jtent iff cover/J(T, Hp,, Np.) 0; and locally complete iff cover/J(T, Hp,, Pp.) = Pp,.

Definition 8 Clau/Je c E Hp, i/J globally incorrect iff cover/J(T, H, N) 'I 0 and cover/J(T, H - {c}, N) C cover/J(T, H, N).

Definition 9 Clau/Je c E Hp, i/J globally irrelevant iff cover/J(T, H, P) = covers(T, H- {c}, P).

A clause c is incorrect if it is responsible, either directly or indirectly, for negative examples being covered by the hypothesis H. In the special case where c is incorrect and covers(T, H - {c}, N) = 0, we have that c alone is responsible for the inconsistency of the hypothesis. A clause is irrelevant if it does not contribute to positive examples being covered.

3 State-of-the-art

The application of empirical single predicate learners to a multiple predicate learning task encounters a number of problems. First, we argue that one should be cautious when applying extensional predicate learners for multi­ ple predicate learning. Second, we show that when using a single predicate learner to learn multiple predicates, the result depends very much on the order of learning the predicates.

3.1 Extensionality

Let us first discuss the way extensional systems, such as GOLEM and FOIL, handle multiple predicate learning problems. To solve a multiple predicate learning prob­ lem mpl(B, H, E), they first transform the background theory B into a ground h.-easy model M of the back­ ground theory B. Such a model contains a set of true ground facts derivable from B by a depth-bounded in­ terpreter. To learn the predicates P\, they then repeat­ edly call their inductive learning procedures on the sin­ gle predicate learning tasks spl(M UP, H,., E,.). The resulting m-hypothesis isH = H, 1 U ... U H,_.

The approach works well provided that the example set E is complete, i.e. when E contains all possible posi­ tive and negative examples for the predicates Pi· For ex­ ample, the problem specified in Example 1 can be solved by GOLEM using a complete example set. However, when the example set is incomplete, which is the usual setting in inductive learning, a number of serious prob­ lems may occur. The reason for these problems is the use of an extensional notion of coverage:

Definition 10 An m-hypothesu H eztensiona.lly covers an eza.mple e with respect to a. ground model M iff there u a. cla.u6e c E H a.nd a. substitution () such tha.t hea.d( c )0 = e a.nd body(c)9 C M.

The notions of extensional completeness and consis­ tency are derived in a straightforward manner from this definition. To distinguish the extensional notions from the ones introduced earlier, we will refer to the non­ extensional ones as intensiona.l.

Using extensional coverage can lead to problems be­ cause an example may be covered intensionally, but not extensionally and vice versa (see Example 2 for an il­ lustration and [De Raedt et a.l., 1993] for more details). Two main problems arise because of this. First, an ex­ tensional system may find a hypothesis that is extension­ ally globally complete and consistent, but not intension­ ally (see Example 2). Second, the system may be unable to find an intensionally globally complete and consistent hypothesis when there is one. Both problems disappear when care is taken that the already induced clauses are added to the theory. When working intensionally, this can easily be realized. When working extensionally, this is computationally much more expensive, as the whole model may have to be regenerated (in the case of normal program clauses).

Example 2 Reconsider the theory of Example 1, and suppose the aim is to induce the concepts male_ancestor (m-a) and female_ancestor (f-a) from father and mother and a complete example set. FOIL 2.1 induced the hy­ pothesis below. This definition is complete and con­ sistent from an extensional point of view (in the given database, both parents are always specified). From an intensional point of view, however, the definition is use­ less as it cannot be used to derive conclusions from a theory containing father and mother only.

3.2 Order dependency

When adopting the above conclusion, the straightfor­ ward way to solve the multiple predicate learning prob­ lem mpl(B, H, E) using a single predicate learner works as follows. Multiple predicate learning starts with a 0hypothesis, i.e. H = 0. In each step of multiple pred­ icate learning, the current A:-hypothesis (A: < m) Hcu,. = H, 1 U ... U H,. needs to be refined. At each step of target theory construction, the next predicate SJ:+t E {p11 ... ,p,.} (where s1:+1 ::fi s; for all j ~ A:) is selected and a new hypothesis H,H 1 is constructed by solving the single predicate learning task spl(T, H,.+ 1 , E,.i)· where E,.+ 1 is the training set for predicate s1:+1 and T is the theory BUHC11or· The background knowledge to be considered in single predicate learning is not only B, but B together with the m-hypothesis Hcu,. learned so far. We now show that this idea encounters some problems.

The main problem is to determine the next predicate to be learned. This is a serious problem because pro­ cessing the predicates in a non-optimal order may sig­ nificantly affect the learning results: no solution may be found or the induced hypothesis may be very complex.

The reason for the impact of the order of learning the predicates on the learning results is the use of a back­ ground theory. This theory determines the difficulty of the learning task. Given all relevant predicates in the background theory, the single predicate learning task is easy. On the other hand, if the available predicates are less relevant or irrelevant, the learning task becomes hard or unsolvable. For instance, learning the predicate grandfather in terms of male, female and grandparent is easy; using male, female and parent is harder, and using only male and female the problem is unsolvable.

The situation is more complicated than indicated above. All ILP (and other inductive) learners employ an explicit or implicit bias, which effectively restricts the space of considered hypotheses. Such a bias is neces­ sary because the space of possible predicate definitions is the language£ of definite or normal clause logic. Even for a fixed number of predicates of arity 2 or larger, the number of different clauses is infinite. Since no system can search forever, bias is needed to make the search space finite and to consider the most interesting clauses first. As examples of such bias, consider GOLEM's ij­ determinacy (explicit declarative bias) and FOIL's en­ coding length restriction (implicit procedural bias). Bias makes the search space manageable, but can prevent the learner from finding the desired predicate definitions.

When trying to learn multiple predicates using a sin­ gle predicate learner, bias and ordering effects are both to be taken into account. For certain orderings of learn­ ing the predicates, the learning task as a whole may be solvable, whereas for others, it may not. Clearly, in the worst case, which arises when there would exist only one order of learning the predicates that leads to a solution, all possible orderings of learning the predicates are to be considered (formulated more precisely, an ordering is a sequence of the learning tasks spl(T, H,,, E,.) where T = B U Hcur for the current k-hypothesis Hcu,. and there is precisely one task for each predicate Pi)· This is clearly computationally very expensive. Even when the worst case does not arise, using a non-optimal order may have negative effects on the results, in the sense that the induced hypotheses may be unnecessarily complex and thereby also less reliable and accurate. To illustrate our point, consider GOLEM on the task of Example 1. GOLEM requires that both mother and father are learned before ancestor, because the recursive clause for ancestor using parent is not determinate.

Using a single predicate learner to solve a multiple predicate learning task is even more problematic than sketched above. Many of the problems are due to learn­ ing at the local instead of at the globa.llevel:

3.2.1 Overgeneralization

When an overly general clause c is learned for a pred­ icate Pi and Pi has to be used in a clause for a predicate P;, overgeneralization may prevent the learner from find­ ing globally consistent clauses for P;. The reason is that the decision to add clause c to the theory is made at a loca.llevel, based on the examples for Pi only. When using this predicate later, there are also global effects. One effect may be that P; falls off the learnability cliff [Wrobel, 1988] (all clauses for P; may be overly general, or may not satisfy the bias restrictions). As an example, consider again GOLEM on the task of Example 1, with the order of learning father, mother and ancestor. As­ sume that - due to too few negative examples for father -the learned definition for father is overly general (e.g., father(X,Y) +- parent(X,Y)). In this case the definition of ancestor is not determinate again. The example implies that overgeneralization of one predicate can prevent the learner from finding the definitions of other predicates. It is hard to see how global effects can be taken into account by single predicate learners, which make local decisions.

3.2.2 Mutually recursive predicates

Mutually recursive predicates 1 complicate the learning process because the learning of one (mutually recursive) predicate should be interleaved with the learning of the other ones. To learn multiple mutually recursive predi­ cates, one should - in the worst case - not only consider all orderings of the (single predicate) learning tasks, but all sequences (i.e. single predicate learning tasks may have to be considered more than once).

4 Towards multiple predicate learning

The above analysis motivates a different approach, which discovers a good order of learning the predicates; inter­ leaves the learning of the different predicates; recovers from overgeneralization; and takes into account global effects. We now present such an approach.

4.1 Refinement operators

In ILP, the search space is determined by the particular hypothesis language £ used; £ contains the clauses al­ lowed in the hypotheses. The search space can then be structured using the notion of a refinement operator ( cf. [Shapiro, 1983]).

Definition 11 Given a. language£ a.nd a. cla.u.se c, a. re­ finement operator p i.s a. mapping from £ to 2.c .such that for a.ll c E £ : p(c) u the 1et of mo1t general ·pecia.liza.­ tioM of c in£.

1 Although mutually recursive predicates are not fre­ quently needed, mutual recursion cannot always be removed (without introducing additional new predicates).

The notion of specialization most often used in ILP is 8subsumption as introduced by [Plotkin, 1970]. In most ILP systems, refinement of a clause of the form Head +­ Body is performed by applying a substitution on the clause or by adding a literal to the Body [Shapiro, 1983].

In the multiple predicate learning algorithm MPL (outlined in Section 4.2), instead of refining clauses of the form Head +- Body, the idea is to refine clauses c of the form +- Body where the head of the clause is empty. A refinement operator can then perform two syn­ tactic operations on a clause (see also [De Raedt and Bruynooghe, 1993]):

• Bod11 refinement operator PB conjunctively adds to Body a literal Lit with a predicate q, occurring in B ( i = 1, ... , 1) or a predicate Pi from the set of target predicates ( i = 1, ... , m).
• Head refinement operator PH replaces the empty head by a literal with a predicate name Pi from the set of target predicates (i = 1, ... , m).

All body refinements form a set ps(Body) ={Body A Lit I Lit can be formed for a predicate q, (i = 1, ... ,1) or Pi (i = 1, ... , m)}. All ·head refinements performed on +-Body form a set PH(Body) = {Head+- Body I literal Head can be formed for a predicate Pi ( i = 1, ... , m )}. Head refinements, performed on ps(Body), form a set PHs(Body) . Clauses constructed using a B, H or H B refinement operator will be called B-refinement, H­ refinement or H B-refinement, respectively.

Our algorithm uses the head and body refinement op­ erators to construct the clause to be added to the cur­ rent hypothesis. Instead of refining a clause with a fixed predicate name in the head, the refinement operator gen­ erates clauses for different predicates.

4.2 The MPL algorithm

Here we outline a basic algorithm, named MPL (Multiple Predicate Learner), that incorporates the above ideas and that has proven capable of solving some multiple predicate learning tasks falling outside the scope of most of the other ILP systems.

The MPL system basically performs a hill-climbing search on m--hypotheses. In this part of the search, it keeps track of two hypotheses, Hcu,. and Hncct · Hcu,. contains the current m--hypothesis, i.e. the best hypoth­ esis encountered so far. Hnect is constructed from Hcu,. in three steps :

First, clauses responsible for covering negative exam­ ples (globally incorrect clauses) are deleted. In case of different possibilities, preference is given to locally in­ consistent clauses, and those clauses covering the most negative examples. Positive examples exclusively cov­ ered by retracted clauses are (again) added to the cur­ rent example set. Incorrect deleted clauses are marked. The marks are used to avoid adding the same clause(s) later (cf. procedure Findbest).

Second, clauses that are no longer required to cover positive examples (globally irrelevant clauses)

are deleted. Clauses that previously covered posi­ tive examples may become irrelevant because of retrac­ tions/additions of other clauses.

Third, the algorithm repeatedly adds locally consis­ tent clauses to Hnczt until a clause is added that is lo­ cally consistent but not globally or Hnczt is a solution to the multiple predicate learning task. Adding a clause that is not globally consistent leads to an inconsistency, which may be removed in the next cycle through the outer while loop.

If the 111--hypothesis Hnczt generated in this way is bet­ ter than Hcur (for a definition of better see Section 4.3), Hnczt is assigned to Hcur and the process is repeated.

The motivation for performing a greedy hill-climbing search is that it is far too expensive to investigate all alternatives. Furthermore, doing a complete search of the space of the alternatives cannot guarantee solutions as the search for clauses (cf. Findbest, which is similar to FOIL) is also heuristic.

MPL(B,E)

Ecur := E; Hnczt := 0; better := true while not(Hnezt glob. comp. and cons.) and better do Hcur := Hnczti while Hnczt glob. incons. do delete from Hnczt a glob. incons. clause c add to Ecur all positive examples covered by c and not covered by Hnezt delete from Hnczt all globally irrelevant clauses while Hnczt glob. cons. and not glob. comp. do Cbut := call Findbest(B, Hnezt, Ecur) add Cbut to Hnczt remove from Ecur all pos. ex. covered by Hnu:t better := Hnezt is better than Hcur if Hnczt glob. complete and consistent then delete from Hnezt all glob. irrelevant clauses output Hnezt else output Hcur Findbe8t{ B ,H ,E) Beam:={ true} while improvement possible do select best Body from Beam BRefinements := PB(Body) for all Bo E BRefinements do Evaluate Bo, i.e. val(Bo):=max{val(c) IcE PH(Bo)}

Beam:=b best bodies on Beam U BRefinements return best unmarked clause on Beam

The search for locally consistent clauses ( cf. Find­ best) is based on the ideas in FOIL [Quinlan, 1990) and mFOIL [Dzeroski, 1991). At each step of the search, the algorithm keeps track of the b best bodies of clauses. It repeatedly selects the current best body from the Beam, and computes all B-refinements. The quality of a Bo is then taken as the maximum value of the evaluation func­ tion val ( cf. Section 4.3) applied to the H -refinements of Bo. In this way, the predicate for which a clause is being learned is not fixed as in FOIL but rather selected dynamically. This allows to find the most interesting clauses first . The search continues as long as the bodies on Beam may still be improved. One further difference with FOIL should be mentioned. The MPL algorithm marks the incorrect clauses it retracts. The algorithm takes care that marked clauses are never again added to current hypothesis. In this way, MPL avoids loops.

Notice that MPL can also start from an initial, ap­ proximate hypothesis for the predicates to be learned. The only required change is to initialize Hcur to this initial hypothesis.

4.3 Heuristics

The MPL sketched in Section 4.2 employs two heuristics: a heuristic to decide whether one 111--hypothesis is better than another one, and a heuristic evaluation function that computes the quality (interestingness) of a clause.

Definition 12 Given a clawe c for a predicate Pi, the current ezample 1et Ecur, the background theory B and the current hypothe1u H cur,

where PI {re8p. p 1 ) u the number of po8itive ezample1 covered at the local (re1p. global) level, and t, (re1p. t 1 } the number of ezample8 covered at the local (re1p . global) level. Clau8e c1 i8 better than clau1e c~ if val(ci) ~ val( c:~). Tie8 are re1olved by ·electing the clawe that contain· the lead number of literal· involving p1 , .·. ,Pm.

The evaluation function val is a weighted sum of the lo­ cal (clause) and global (hypothesis) accuracy, estimated by the Laplace estimate also used in the ILP system mFOIL [Dzeroski, 1991). The tie-break procedure re­ flects a desire to have as few dependencies as possible, thereby reducing the probability of later revisions.

Finally, our algorithm also compares the quality of two 111--hypotheses.

Definition 13 An m-hypothe1u H1 u better than H~ if H1 globally cover· more po8itive ezample1 than H~ or H1 cover· the 1ame number of po1itive ezample1 a1 H~ but leu negative ezample1.

The algorithm uses a depth-bounded interpreter for test­ ing coverage.

5 Experimental results

Using a prototype implementation of the MPL algorithm in PROLOG, two experiments were performed on the domain of learning family relations. In order to sim­ plify the evaluation of the results and the comparison with FOIL, during all runs with the system, the system was not using the beam-search strategy but rather hill­ climbing (the beam width b was 1). Furthermore, the depth bound for testing coverage was 6, the refinement operator being used was essentially the same as in Quin­ lan's FOIL, and the weights were w1 = 0.8 and w~ = 0.2.

Experiment 1 aimed at learning the definitions of an­ cestor, father and mother from the knowledge base con­ taining male, female and parent specified in Example 1, and from a complete set of positive and negative exam­ ples. The system learned the following clauses in the specified order

(1) ancestor(X,Y) - parent(X,Y) (2) father(X,Y) - parent(X,Y) A male(X) (3) mother(X,Y) - parent(X,Y) A female(X) (4) ancestor(X,Y)- parent(X,Z) A ancestor(Z,Y)

To check the ability of the MPL algorithm to recover from overgeneralization, we also ran MPL starting from clauses 5, 6 and 7. This theory could have been in­ duced using other evaluation criteria in MPL. Indeed af­ ter learning clause 5, ancestor and parent are synonyms and only our tie-break method prefers clause 2 over 6 and clause 3 over 7.

(5) ancestor(X,Y) - parent(X,Y)

(6) father(X,Y) - ancestor(X,Y) A male(X)

(7) mother(X,Y) - ancestor(X,Y) A female(X)

(8) ancestor(X,Y) - parent(X,Z) 1\ parent(Z,Y)

MPL then discovered that clause 8 was the most inter­ esting one to add next, yielding the current hypothesis H composed of 5, 6, 7 and 8: At that moment, the sys­ tem discovered that the hypothesis is no longer globally consistent and it decided to remove (and mark) clauses 6 and 7 from H. After this clauses 2, 3 and 4 were in­ duced, making clause 8 redundant. Therefore clause 8 was removed, yielding the desired target theory.

Experiment 2 aimed at learning male...ancestor (m-a) and female...ancestor (f-a) from father and mother. All the facts and examples about father, mother, m-a and f-a were derived from the background theory in Example 1. MPL learned (notice that clause 14 is correct):

(9) f-a(X,Y) - mother(X,Y)

(10) m-a(X,Y)- father(X,Y)

(11) f-a(X,Y) - mother(X,Z) A f-a(Z,Y)

(12) m-a(X,Y) - father(X,Z) 1\ f-a(Z,Y)

(13) m-a(X,Y)- father(X,Z) A m-a(Z,Y)

(14) f-a(X,Y) - f-a(X,Z) A m-a(Z,Y)

6 Conclusions

We analyzed the problem of empirically learning multi­ ple predicates from examples. We identified the main problems: consideration of clauses only at a local level, extensional notion of coverage, determining the order of learning the predicates, bias, overgeneralization and mutual recursion. We also proposed an alternative ap­ proach MPL based on FOIL. Preliminary experiments show that MPL is able to solve some multiple predicate learning problems beyond the scope of other empirical ILP systems.

Acknowledgements

The authors are grateful to Hilde Ade, Francesco Bergadano, Peter Flach, Stephen Muggleton, and Gun­ ther Sablon for discussions and/ or comments. Special thanks to Maurice Bruynooghe for his support.