Covering vs. Divide-and-Conquer for Top-Down Induction of Logic Programs

1 Introduction

The search for an inductive hypothesis can be performed either bottom-up (i.e. from an overly specific hypothe­ sis to a more general) or top-down (i.e. from an overly general hypothesis to a more specific) . In propositional learning, two search techniques for top-down induction have been proposed: covering and divide-and-conquer. Covering, which has been used in e.g. the AQ family [Michalski,1980], constructs a hypothesis by repeatedly specializing an overly general hypothesis, on each iter­ ation selecting a disjunct that satisfies a subset of the positive examples and no negative examples, until all positive examples are satisfied by the selected disjuncts.

Divide-and-conquer, which has been used in e.g. ID3 [Quinlan,1986], constructs a hypothesis by dividing an overly general hypothesis into a set of hypotheses, which correspond to disjoint subsets of the examples. It then continues recursively with those hypotheses for which the corresponding subsets contain both positive and nega­ tive examples. The resulting hypothesis consists of all specialized hypotheses for which the corresponding sets contain positive examples only.

One of the main long term goals of inductive logic pro­ gramming is to upgrade the techniques of the proposi­ tional learning paradigm to a logic programming frame­ work. This in order to allow for the use of a more expressive formalism and to allow for the use of sub­ stantial background knowledge in the learning process. However, of the two search techniques used in proposi­ tional learning, only covering has been formalized and used extensively for top-down induction of logic pro­ grams (q;. in MIS [Shapiro,1983], FOIL [Quinlan,1990], ANA-EBL [Cohen,1991], FOCL (Pazzani et a/,1991), GREN­ DEL (Cohen,1992) and FOCL-FRONTIER (Pazzani and Brunk,1993]). This work contributes to the above long term goal by giving a formalization of divide-and­ conquer in a logic programming framework . This formal­ ization is in fact a reformulation of the al~orithm SPEC­ TRE [Bostrom and Idestam-Almquist,1994J, and can also be viewed as a generalization of the technique used in ML-SMART [Bergadano and Giordana,1988] .

In the next section, the two search techniques are for­ malized and analysed in a logic programming framework. In section three, an empirical evaluation of the two tech­ niques is presented, in which the techniques are com­ pared with respect to efficiency and to the accuracy of the resulting hypotheses. Finally, concluding remarks are given in section four . In the following, we assume the reader to be familiar with the standard terminology in logic programming [Lloyd,1987].

2 Top-Down Induction of Logic Programs

In this section, we first define the top-down induction problem in a logic programming framework. We then present two common specialization operators and show how covering and divide-and-conquer can be formal­ ized using one of these. Finally, we analyse the techniques with respect to the hypothesis spaces that are ex­ plored, the ability to produce recursive hypotheses and the amount of redundancy in the produced hypotheses.

2.1 The Top-Down Induction Problem

The top-down induction problem can be formulated as follows:

Given: a definite program 0 (overly general hypothe­ sis), a definite program B (background predicates) and two sets of ground atoms E+ and E- (positive and neg­ ative examples).

Find 1 : a definite program H, called a valid hypoth­ esis, such that MHuB ~ MouB, E+ ~ MHuB and

MHuB nE- = 0.

In this work we assume that all positive and negative examples are ground instances of the same atom T, re­ ferred to as the target predicate, and that all clauses in 0, and only those, define T. Furthermore, we assume the target predicate to be non-recursive (i.e. no instance of the target predicate is allowed in the body of a clause). It should be noted that this assumption does not pre­ vent other recursive predicates from being used in the definition of the target predicate. The reason for this assumption is discussed in section 2.6.

2.2 Specialization Operators

Literal addition is a specialization operator that has been used in several approaches for top-down induc­ tion of logic programs (e.g. [Shapiro,1983; Quinlan,l990; Pazzani et a/, 1991]). By this operator, a clause is special­ ized by adding a literal to the body, where the literal usu­ ally is restricted to be an instance of a background pred­ icate. Various restrictions are normally also put on the variables in the literals (e.g. at least one of the variables should appear elsewhere in the clause [Quinlan,l990]) . Goal reduction is another specialization operator that has been used in several approaches (e.g. [Cohen,l991; Pazzani et a/,1991]). By this operator, a clause is spe­ cialized by resolving upon a literal in the body using one of the background clauses. It should be noted that any specialization obtained by goal reduction can also be ob­ tained by literal addition (not necessarily in one step). On the other hand, it is also possible to define predicates that may introduce any literal (cf. [Cohen,1992]), which makes any clause obtainable by literal addition also ob­ tainable by goal reduction. Since goal reduction allows for more explicit control of what specializations are al­ lowed than literal addition, we have chosen the former operator when studying search techniques for top-down induction.

2.3 Covering

The covering principle can be applied in a logic pro­ gramming framework in the following way. One of the clauses in the overly general hypothesis is selected and specialized until the selected clause does not cover 2 any negative examples. This process is iterated until all pos­ itive examples are covered by the selected clauses. This technique is formalized in Figure 1, using goal reduction as a specialization operator.

1 Mp denotes the least Herbrand model of P.

INPUT: two definite programs 0 and B, and two sets of ground atoms E+ and E-: OUTPUT: a valid hypothesis H. Let H = 0. WHILE E+ # 0 DO Let C E 0 be a clause covering an element in ET WHILE C covers an element in E- DO Let C be a resolvent of C and a clause in B, such that it covers an element in ET Let H = H U { C}. Let E+ = E+ \ {e: e is covered by C}.

Example

Assume that we are given the overly general hypothesis:

reward(S,R):- suit(S),rank(R).

and the background predicates in Figure 2, together with the following sets of positive and negative examples:

E+ = { reward(spades, 7) , reward(clubs, 3)} E- = { reward(hearts,S) , reward(clubs,j)} suit(S):- red(S). suit(S):- black(S). rank(R):- num(R). rank(R):- face(R) . red(hearts). red(diarnonds). black(spades). black(clubs). num(1) .... num(10). face(j). face(q). face(k).

Since the clause in the overly general hypothesis covers negative examples, it is specialized. Choosing the first literal to resolve upon using the second clause defining suit(S) results in the following clause:

reward(S,R):- black(S),rank(R).

This clause still covers the second negative example, and is thus specialized. Choosing the second literal to resolve upon using the first clause defining rank (R) results in the following clause: ·

reward(S,R):- black(S),num(R).

2 A clause A ~ B1, ... , Bn is said to cover an atom AB w.r.t. a definite program B if and only if there is an SLD­ refutation of B U {( ~ B1, ... , Bn)B}.

Figure 1: The Covering algorithm.

This clause does not cover any negative examples and is thus added to the resulting hypothesis. Since the hy­ pothesis now covers all positive examples, the algorithm terminates. 0

The algorithm produces a valid hypothesis in a fi­ nite number of steps under the assumptions that there are a finite number of SLD-derivations of the positive and negative examples w.r.t. the overly general hypoth­ esis and background predicates and that no positive and negative example have the same sequence of in­ put clauses in their SLD-refutations. It should be noted that this property is not dependent on how the non­ deterministic choices in the algorithm are made. How­ ever, these choices are crucial for the result. Normally, a few number of clauses of high generality are pre­ ferred to a large number of specific clauses, and mak­ ing the wrong choices may result in a non-preferred, although valid, hypothesis. Since it is computation­ ally expensive to find the optimal choices, these are often approximated. In several approaches this has been done by selecting the refinement that maximizes the information gain [Quinlan,1990; Pazzani et a/,1991; Cohen,1992].

2.4 Divide-and-Conquer

The divide-and-conquer principle can be applied in a logic programming framework in the following way. Each clause in the overly general hypothesis covers a subset of the positive and negative examples. If a clause covers positive examples only, then it should be included in the resulting hypothesis, and if it covers negative examples only then it should be excluded. If a clause covers both negative and positive examples, then it corresponds to a part of the hypothesis that needs to be further di­ vided into sub-hypotheses. When taken together, these hypotheses should be equivalent to the divided hypoth­ esis. This means that a clause that covers both positive and negative examples should be split into a number of clauses, that taken together are equivalent to the clause that is split. This can be achieved by applying the trans­ formation rule unfoldinrf [Tamaki and Sato,1984] . This technique is formalized in Figure 3.

Example

Consider again the overly general hypothesis, back­ ground predicates and examples in the previous exam­ ple. Calling the divide-and-conquer algorithm with the clause in the overly general hypothesis together with the background predicates and all covered examples results in the following.

Since the clause covers both positive and negative ex­ amples, unfolding is applied. Unfolding upon suit(S) replaces the clause with the following two clauses:

The first clause covers one negative example only, while the second clause covers two positive examples and INPUT: a clause C, a definite program B and two sets of ground atoms E+ and E-: OUTPUT: a valid hypothesis H. IF E+ = 0 THEN let H = 0. IF E+ -j 0 and E- = 0 THEN let H = {C}. IF E+ -j 0 and E- -j 0 THEN Unfold upon a literal inC, giving C1, ... , Cn. Let Et and Ei, 1 ~ i ~ n, be all examples in E+ and E- respectively that are covered by C;. FOR i = 1 TO n DO Call Divide-and-Conquer with C;, B , Et and E;; giving H;. Let H = H 1 U ... U H n.

3 When unfolding upon a literal L in the body of a clause C in a definite program P, Cis replaced with the resolvents of C and each clause in P whose head unifies with L.

Figure 3: The Divide-and-Conquer algorithm.

one negative example. The algorithm is then called once with each of these clauses. The empty hypothesis is re­ turned by the first call since the first clause does not cover any positive examples. The clause used in the sec­ ond call is unfolded since it covers both positive and negative examples. Unfolding upon rank(R) replaces the clause with the following two clauses:

reward(S,R):- black(S), num(R). reward(S,R):- black(S), face(R).

The first of these clauses covers two positive and no neg­ ative examples and is therefore included in the resulting hypothesis, while the second covers one negative example only, and is therefore not included. Hence, the resulting hypothesis is:

0

Divide-and-conquer produces a valid hypothesis in a finite number of steps under the same assumptions as for covering, i.e. that there are a finite number of SLD­ derivations of the positive and negative examples and that no positive and negative example have the same se­ quence of input clauses in their SLD-refutations. As for covering, it should be noted that the non-deterministic choices (in this case of which literals to unfold upon) are crucial for the result . Again, the optimal choices can be approximated by selecting the specialization that maxi­ mizes the information ~ain, as is done in [.Bostrom and Idestam-Almquist,1994j (cf. ro3 [Quinlan,1986]) .

2.5 The Hypothesis Spaces

Let 0 be an overly general hypothesis and B be back­ ground predicates. The hypothesis space for covering is Hcov = {H : H ~ {Co X ... X Cn : Co E 0 and Ct, ... ,Cn E B, where n?: 0}}. 4 The hypothesis space for divide-and-conquer is H dac = { H : H ~ H' \ B, where H' is obtained from 0 U B by applying unfolding upon clauses that are not in B} .

Note that Hdac C Hcov, which follows from that each set of clauses obtained by unfolding can be obtained by goal reduction and that there are programs that can be produced by covering that can not be produced by divide-and-conquer. For example, consider the overly general hypothesis:

4 C x D denotes a resolvent of C and D upon a literal in the body of C.

and the background predicates:

Then the following hypothesis is in Heov, but not in H dae:

2.6 Recursive Hypotheses

As was stated in section 2.1, the target predicate is as­ sumed to be non-recursive. The reason for this is that divide-and-conquer is not applicable when specializing clauses that define recursive predicates, since decisions regarding one subset of examples may then affect other subsets of examples. For example, consider the overly general hypothesis:

odd(O). odd(s(X)):- odd(X).

together with the positive and negative examples:

Then the first clause covers negative examples only, and should therefore not be included in the resulting hy­ pothesis. However, this can not be achieved without obtaining an overly specific hypothesis, since then the positive examples would no longer be covered. Extend­ ing the definition of cover to include all examples that use a clause, and not only use it as the first clause in their refutations, does not solve the problem. Then in the example above, all examples would be covered by the first clause, and all except one by the second clause. However, since the first clause can not be removed or specialized, it means this sub-part of the problem can not be treated separately according to the divide-and­ conquer principle. One solution to this problem is to transform the overly general hypothesis into an equiva­ lent non-recursive hypothesis, as proposed in [Bostrom and Idestam-Almquist,1994]. However, although this transformation allows divide-and-conquer to be applied, it prevents recursive hypotheses from being found . It should be noted that although divide-and-conquer is not applicable torecursive predicates, it does not mean that recursive definitions can not be found by applying un­ folding and clause removal. On the contrary, a technique for achieving this is presented in [Bostrom, 1995].

Covering, on the other hand, can be easily extended to deal with recursive predicates. Instead of searching for a clause that together with background predicates covers some positive examples and no negative exam­ ples, a clause can be searched for that together with the clauses found so far and the background predicates can cover some not yet covered positive examples without covering any negative examples, and that allows for the remaining positive examples to be covered without cov­ ering any negative examples.

2.7 Redundancy

When using covering, the number of SLD-refutations of the positive examples is not necessarily the same for the resulting hypothesis as for the overly general hypothesis, i.e. the amount of redundancy may increase or decrease. On the other hand, when using divide-and-conquer, the number of SLD-refutations of the positive examples is the same for both the overly general and the resulting hypothesis. This follows from the fact that the number of SLD-refutations does not increase when unfolding is applied (proven in [Kanamori and Kawamura,1988]). In order to reduce the amount of redundancy when using divide-and-conquer, only a minor change to the algo­ rithm is needed: instead of placing a positive example in all subsets that correspond to clauses that cover the example, the example can be placed in one such subset.

3 Empirical Evaluation

In this section we empirically evaluate the performance of covering and divide-and-conquer. We first present three domains that are used in the experiments and then present the experimental results .

3.1 Domains

Two domains are taken from the UCI repository of machine learning databases and domain theories: King+Rook versus King+Pawn on a7 and Tic-Tac-Toe. The third domain considers natural language parsing using a definite clause grammar and is taken from [Bratko,1990].

The example sets in the UCI repository are repre­ sented by attribute vectors, and have to be transformed into atoms in order to be used together with the algo­ rithms. The number of examples is 3196 in the first do­ main (of which 52.2% are positive) and 958 in the second domain (of which 65.3% are positive).

Since the algorithms also require overly general hy­ potheses as input, such are constructed for the two first domains in the following way ( cf. [Cohen,1991]). A new target predicate is defined with as many arguments as the number of attributes, and for each attribute a new background predicate is defined to determine the pos­ sible values of the attribute. This technique is illus­ trated by the following overly general hypothesis and background predicate for determining win for x in the Tic-Tac-Toe domain:

win_for_x(S1,S2,S3,S4,S5,S6,S7,S8,S9):­ square(S1), square(S2), square(S3), square(S4), square(S5), square(S6), square(S7), square(S8), square(S9). square(x). square(o). square(b).

An alternative formulation of the Tic-Tac-Toe domain is used as well, where a new intermediate background predicate is introduced. In the alternative formulation, the definition ofthe predicate square(S) is changed into the following:

square(x). square(S):- o_or_b(S). o_or_b(o). o_or_b(b).

The hypothesis is that the new intermediate predicate will reduce the number of clauses in the resulting defi­ nition, and hence increase the accuracy. The reason for this is that it does not matter in the correct definition of the target predicate whether a square has the value o or b.

The set of positive examples in the third domain con­ sists of all sentences of up to seven words that can be generated by the grammar in [Bratko,1990, p 455], i.e. 565 sentences. The set of negative examples is generated by randomly selecting one word in each correct sentence and replacing it by a randomly selected word that leads to an incorrect sentence. Thus the number of negative examples is also 565. Two versions of an overly general hypothesis are used for this domain. The first version is shown below:

where the definition of the predicate s (X, Y) is the same as for sentence(X, Y), but with s substituted for sentence and with one extra clause: s(X,X). By re­ ferring to the background predicate s (X, Y) instead of sentence(X,Y), the problem with recursive overly gen­ eral hypotheses is avoided, as discussed in section 2.6.

The second version introduces intermediate predicates in the definitions of sentence(X,Y) and s(X,Y), that group words into classes in the following way:

sentence(X,Y):- determiner(X,Z), s(Z,Y). sentence(X,Y):- noun(X,Z), s(Z,Y). determiner([everyiX] ,X). determiner([aiX],X).

The hypothesis is, like for the Tic-Tac-Toe domain, that the intermediate predicates will improve the accuracy of the resulting hypotheses .

3.2 Experimental Results

The performance of covering and divide-and-conquer in the three domains is evaluated using the information gain heuristics that were mentioned in section 2. An experiment is performed with each domain, in which the entire example set is randomly split into two halves, where one half is used for training and the other for test­ ing. The number of examples in the training sets that are given as input to the algorithms are varied, representing 1%, 5%, 10%, 25% and 50% of the entire example set, where the last subset corresponds to the entire set of training examples and a greater subset always includes a smaller. The same training and test sets are used for both algorithms. Each experiment is iterated 50 times and the mean accuracy on the test examples is presented below. In addition, the amount of work performed by the two algorithms is presented, measured as the number of times it is checked whether a clause covers an example or not 5 .

In Figure 4 and Figure 5, the results from the King­ Rook versus King-Pawn domain are presented. It can be seen that divide-and-conquer produces more accu­ rate hypotheses than covering for all sizes of the train­ ing set. Furthermore, covering checks more examples than divide-and-conquer for all sizes of the training sets. When the size of the training set is 50%, the number of checks made by covering is about 3.3 times as many as the number of checks made by divide-and-conquer. The mean cpu time for divide-and-conquer at that point is 566.9 s, and for covering 2075.3 s.

5 The reason for using this measure of efficiency and not e.g. cpu seconds, is that this measure is not implementation dependent. Nevertheless, for some cases we also present the learning time measured in cpu seconds. The algorithms were implemented in SICStus Prolog 2.1 and executed on a SUN SparcStation 5.

In Figure 6 and Figure 7, the results from the DCG domain are presented. The two upper curves in Fig­ ure 6 denote the accuracy of the hypotheses produced by divide-and-conquer and covering using intermediate predicates. Interestingly, when no intermediate predi­ cates are used, covering and divide-and-conquer produce identical hypotheses, which is shown by the lowest curve. This experiment also illustrates that the amount of back­ ground knowledge can be far more important than what search technique is used.

In Figure 7, it can be seen that covering checks more examples than divide-and-conquer for all sizes of the training sets and for both overly general hypotheses. When the size of the training set is 50%, the number of checks made by covering without intermediate pred­ icates is about 30.3 times as many as the number of checks made by divide-and-conquer. The mean cpu time for divide-and-conquer at that point is 5.4 s, and for cov­ ering 127.3 s.

In Figure 8 and Figure 9, the results from the Tic-Tac­ Toe domain are presented. The curves labeled Cover­ ing(i) and Divide-and-Conquer (i) in Figure 8 represent the accuracy of the hypotheses produced by divide-and­ conquer and covering with intermediate predicates. The two other curves represent the accuracy of the programs produced by divide-and-conquer and covering without intermediate predicates. It can be seen that covering performs better than divide-and-conquer both with and without intermediate predicates.

The amount of work performed by covering is more than what is performed by divide-and-conquer for all sizes of the training sets and for both overly general hy­ potheses, as shown in Figure 9. When the size of the training set is 50%, the number of checks made by cov­ ering without intermediate predicates is about 3.7 times as many as the number of checks made by divide-and­ conquer. The mean cpu time for divide-and-conquer at that point is 14.0 s, and for covering 49.6 s.

4 Concluding Remarks

We have formalized the covering and divide-and-conquer techniques for top-down induction of logic programs. The main difference between the techniques is that cov­ ering specializes an overly general hypothesis repeatedly, while divide-and-conquer only specializes it once. This has the consequence that a large amount of the work performed at each iteration in covering might be re­ peated, while this is not the case for divide-and-conquer. This was demonstrated by the experiments, in which the amount of work performed by covering was up to 30 times the amount of work performed by divide-and­ conquer. The experiments also demonstrated that the accuracy of the resulting hypothesis can be higher when focusing on discriminating positive from negative exam­ ples, which was done by divide-and-conquer, rather than focusing on a high coverage of positive examples, which was done by covering. On the other hand, the hypoth­ esis space is larger for covering, and thus more com­ pact hypotheses may be found by this technique than by divide-and-conquer. Moreover, a major draw-back of divide-and-conquer, in contrast to covering, is that it is not applicable to learning recursive definitions.

The termination conditions for covering and divide­ and-conquer could be relaxed by slightly altering the al­ gorithms. Instead of requiring that no positive and neg­ ative examples have the same sequence of input clauses in their SLD-refutations, it is enough to require that for each positive example there is one SLD-refutation with a unique sequence of input clauses. This alterations would lead to that some valid hypotheses can be found that are not found by the algorithms in their current formu­ lations.

Instead of using goal reduction as a specialization op­ erator, literal addition could have been used in the for­ malizations and the experiments. In the covering algo­ rithm, a clause would then be specialized by adding a literal rather than resolving upon a literal in the body. In the divide-and-conquer algorithm, a clause would then be replaced by all clauses obtainable by adding a literal, rather than all resolvents upon a literal. However, as was pointed out earlier, by using goal reduction instead of literal addition, explicit control of the possible special­ izations is obtained, where the overly general hypothesis is used as a declarative bias that not only limits what predicate symbols are used, but also how they are in­ voked.

Acknowledgements

This work has been supported by the European Com­ munity ESPRIT BRA 6020 ILP (Inductive Logic Pro­ gramming). This work benefitted a lot from discussions with Peter Idestam-Almquist, who originally made the observation that the algorithm SPECTRE resembles ID3 and suggested the use of an impurity measure.