Avoiding Pitfalls When Learning Recursive Theories

1 Introduction

A growing cohort of systems now learn first-order the­ ories to explain observations. Early examples, MIS [Shapiro, 1983] and MARVIN [Sammut and Banerji, 1986], have been joined by CIGOL [Muggleton and Buntine, 1988], FOIL (Quinlan, 1990, 1991], GOLEM (Muggleton and Feng, 1990], FOCL [Pazzani, Brunk and Silverstein, 1991; Pazzani and Kibler, 1992], ILE [Rouveirol, 1991] and others. The reason for looking beyond familiar propositional formalisms is their limited expressiveness - observations are not always capable of being represented as attribute values and theories sometimes cannot be captured as decision trees or DNF expressions.

Most first-order learning systems construct Horn clause theories. This subset of first-order logic is rich enough to include variablization, limited quantification, and recursion, yet restricted enough to be computable (hence its use as the basis for the well-known program­ ming language Pro log) . Learned theories expressed as collections of Horn clauses are therefore executable pro­ grams, explaining why this sub-field of machine learning is also known as inductive logic programming.

Any theory that contains recursive clauses runs the risk of non-termination due to infinite recursion. There is no general method for detecting such flawed recursive theories, since deciding whether a Horn clause program will terminate is an analog of the halting problem and thus undecidable. However, this paper describes a heuristic method that can vet recursive theories while they are being developed, thereby avoiding some prob­ lematic recursion. The method guarantees that, for a ground query, the clauses defining a single relation will never invoke themselves so as to cause infinite recursion.

*This research was made possible by a grant from the Aus­ tralian Research Council (principal investigator J.R. Quin­ lan) and assisted by a research agreement with Digital Equip­ ment Corporation.

The idea starts with the discovery of orderings on sets of constants that are then extended to orderings of the recursive literals in clauses. The approach, which has been implemented in the new version of FOIL, should also be applicable to any system that learns from ground examples by a process of specialization.

In the following sections we introduce the learning task and give a brief description of FOIL. We then show how sets of constants can be ordered and how this ordering can be used to discover orderings of pairs of variables in a clause, leading to a method for ordering recursive literals in a set of clauses. The paper concludes with empirical results that support the utility of the approach.

2 The Learning Task

Input consists of a collection of relations. Each relation is specified by two sets of tuples of constants: those that belong in the relation ( EB tuples) and those that do not (e )' where the latter are often taken to be the comple­ ment of the former by the closed-world assumption. The constants may be grouped into (possibly overlapping) types or may belong to a single universal type. A relation R of arity k, represented by k-tuples of constants, may also be regarded as a literal R(V1 , V2, ... , VA:) with k arguments.

The learning task is to use the extensional definition of the relations provided by the tuples to generate an intensional definition of a designated target relation in terms of itself and other relations.

We will use the small example of Figure 1 as a contin­ uing illustration. There are two relations:

The tuples shown for these relations are the EB tuples from the tree in the Figure, the e tuples being the complementary sets. For instance, { 0, 1, 2) is in the relation subtree because the tree at node 0 has the subtrees at nodes 1 and 2; {a, 2) is in leaf-of because a is a leaf of the tree at node 2. If the target relation is leaf-of, the learning task would be to find a definition 1 such as leaf-of( A, B) +- subtree(B, A, C), ·subtree( A, D, E)

leaf-of( A, B) +- subtree(B, C, A), ·subtree( A, D, E)

leaf-of( A, B) +- subtree(B, C, D), leaf-of( A, C)

leaf-of( A, B) +- subtree(B, C, D), leaf-of( A, D)

3 FOIL

FOIL learns function-free definitions of this kind. A com­ plete description ofthe system is given in [Quinlan, 1990, 1991], but the following simplified version is sufficient for our purposes.

FOIL grows a definition one clause at a time until all ® tuples in the target relation have been covered by at least one clause. Each clause commences with the same left­ ~and side and t~: right-hand side is successively special­ iZed by the add1tlon of literals until the clause covers no e tuples. Clause development is guided by a training set o~ tu;Ples of consta~ts, each tuple representing a possible bmdmg of the vanables in the incomplete clause that satisfies all literals on the right-hand side. The initial training set for each clause consists of the uncovered ® tupl~ of t~e target relation together with all e tuples. Addmg a hteral to the right-hand side can cause some tuples to be excluded and/or all remaining tuples to be extended by the introduction of new variables.

. 1 Som~ literals in this definition are negated; many system­ s, mcluding FOIL, permit this small extension to the Horn clause formalism.

Using the above illustration, the training set for the ~rst clause is as shown in Figure 2(a). If subtree(B, C, D) 1s added as the first literal on the right-hand side of the clause, the training set changes as shown in Figure 2(b) . The n_umber of tuples is reduced and each remaining tuple 1s expanded to take account of new variables C and D . The element (a, 0, 1, 2) shows a possible binding ~~a, B=O, C=1, D=2 that satisfies the right-hand side; 1t 1s marked ® since (a, 0) belongs in the target relation leaf-of

When recursive literals are candidates for addition to the right-hand side of a clause, we need to ensure that they cannot cause infinite recursion on ground queries. For instance, if R(A, B) is a symmetric relation pseudodefinitions such as '

must be avoided. The original version of FOIL discovered possible orderings of the constants as described below that in turn allowed the establishm~nt of a partial order~ ing of the. variables in a ~l~use . Literal R(W1 , W2 , . . . , W~:) was cons1dered for add1t10n to a clause with left-hand side R(Vt, V2, ... , V~:) only if Wi < Vi for at least one argument Vi . This is sufficient to prevent problems when there is a single recursive literal in a single clause, but not when there are two or more of either. For example, a recurrence relation of the form

leads to infinite recursion, yet each recursive literal sat­ isfies the ordering requirement above.

We now amend the sufficiency requirement to allow for an arbitrary collection of clauses for the target literal , each of which may contain any number of recursive literals. We want to ensure that a ground query of the target literal R cannot cause the clauses defining R to invoke themselves without termination. This still does not cover infinite recursion arising from the situation in which clauses for a relation R invoke clauses for a relation S which in turn invoke clauses for R.

4 Ordering a Set of Constants

Constants belonging to some common types such as the integers have a well-known natural order. Since the method described here depends on an ordering of con­ stants in all types, including symbolic types , we require a general algorithm for discovering a plausible ordering of the constants belonging to each type. To simplify the presentation we will assume that all constants belong to a single universal type; if there are several types, the procedure is repeated for each in turn.

The assumption underlying the search for an ordering is that some pairs of arguments of some relations must be ordered - this would seem to be a prerequisite for the development of well-behaved recursive theories. For each relation R(V1 , V2 , ... , V~:), every pair of arguments V. , Vj ( i # j) is examined to see whether it is possible that V. < Vj . If the relation is specified by n EB k-tuples of constants, there are pairs of constants a,J:i, a.,i , x = 1. . n corresponding to the pairs of arguments V. , Vj . If the relation establishes that V. < Vj, then it must follow that a.,i < a.,i for each x = l..n. This is feasible if and only if the transitive closure of these n inequalities does not contain any cycles, i.e. there is no way to establish that any constant is less than itself. If the closure is cycle-free, we postulate that either V. < Vj or V. > Vj , since both are equally plausible and we cannot distinguish between them.

Returning to Figure 1, we see that a potential inequal­ ity exists between all pairs of arguments of each relation. For example, the first pair of arguments of subtree would give the inequalities

whose transitive closure adds just 0 < a . Since this is cycle-free, it is plausible that subtree( A , B, C) establish­ es A < B .

Two partial orderings established by different argu­ ment pairs from the same or different relations are consis­ tent if the transitive closure of all associated inequalities contains no cycles. From the example above, the first and third arguments of subtree give the inequalities

and the transitive closure of these and the previous inequalities is still cycle-free. Thus there is an ordering of the constants that would allow subtree( A, B, C) to est ablish A < B and A < C.

When all orderings of argument pairs have been in­ vestigated, the next step is to find an ordering of the constants that is consistent with as many of them as pos­ sible. FOIL searches for a maximal consistent subset of the argument pairs and extracts from it a total ordering on the constants. The corresponding transitive closure of the inequalities between pairs of constants allows us to determine, for any constant a, the number of constants b such that a < b; the constants are then ranked on this number , with ties resolved arbitrarily. In our example, a maximal consistent set is

There is only one ordering of the constants consistent with the transitive closure of these inequalities, namely

Note also that the polarity of this ordering is arbitrary - we might just as well write b < a < ... since we cannot distinguish between ascending and descending order.

5 Ordering Recursive Literals

The ordering of constants in each type now allows us to establish inequalities on the variables in a partly­ developed clause and eventually an ordering on the recursive literals themselves.

Consider an incomplete clause whose left-hand side is R(V1 , V2 , ... , V~:) and let the variables in the clause be V1 , V2 , ... , V, ( v ~ k) . The corresponding training set consists of m v-tuples of constants ( a.,1, a.,2, ... , a.,v }, x = l..m. For every pair of variables V. , Vj of the same type, the ordering of constants can be used to establish whether V. < Vj, i.e. whether a.,i < a.,i for all x . The training set for the incomplete clause

appears in Figure 2(b) above. With respect to the chosen order of the constants, B < C (since 0 < 1, 1 < a , 2 < c, and so on) and a similar check of the tuples reveals that B<D.

Suppose that the recursive literal R(W1 , W2 , ... , W~: ) is a candidate for addition to the right-hand side of the clause. If it is added , we must ensure that this invocation of R can never lead to R being called with the same arguments, causing an infinite recursive loop. Such problems can never arise if there is an ordering of the literals R( .. . ) such that recursive literals on the right­ hand sides of clauses are always less than the literal on the left-hand side.

To this end, we define a total ordering on literals involving the target relation R as follows . We select a permutation p1, p2, ... , pk of the variable positions 1, 2, .. , k in such literals. For each pi we choose one of the inequality relations < or > and denote this choice <>pi · Then,

It may seem strange that the inequality > is permitted as a possible <>pi, but this must be allowed because the order of the constants could be either ascending or descending.

The literal R(W1 , W2 , .. . , Wk) can be added to the right-hand side of the incomplete clause only if we can find an ordering of the literals, as above, in which this and any previous recursive literals are all less than the (unchanging) left-hand side of the clause. "Previous" here means occurring either earlier in the right-hand side of this clause, or in an earlier clause of this definition. Whether or not a suitable literal ordering exists can be established by a simple elimination process that is linear in the number of recursive literals in the definition so fa.r .

In the example, the literal leaf-of( A, D) is an ac­ ceptable addition to the clause because we can choose the permutation 2, 1 of the relation arguments with <>2 = <>1 = >. This defines an ordering of the literals that can be paraphrased as

Since we have D > B from above, leaf-of( A, D) is less tha.n leaf-of(A, B) under this ordering of the literals.

6 Examples

FOIL generated the definition of leaf-of shown in Section 2 in less than 0.1 seconds. (All times quoted in this section are for a DECstation 5000.) This small example is not sufficient of itself to convince sceptical readers that the approach works, so we present results on a variety of more challenging tasks.

6.1 Ackermann's function

This is a more demanding test of handling recursive def­ initions due to the complexity of the recursion involved. Ackermann's function of two non-negative arguments is

Following the usual procedure of converting functions to function-free predicates, we substituted a three­ argument predicate Ack(A, B, C) for the two-argument function F(m, n); Ack(A, B, C) is true if C = F(A, B) . All values of the function up to 20 were given to FOIL, with e tuples coming from the closed-world assumption - this gave 51 E17 and 9,210 e tuples. The relation succ(A, B), meaning B = A+ 1, was also defined for values of B up to 20. The clauses found by FOIL in 95 seconds mirror the definition above:

The literal ordering found for this example was

(the third disjunct never being required) . The first recursive literal in the last clause satisfies the latter disjunct while the second recursive literal satisfies the former disjunct . This example shows that control of recursion can require a sophisticated ordering on the recursive literals.

6.2 List processing examples

Several studies involving small list-processing tasks have been reported in the inductive programming literature. Three of the more difficult are:

• Discovering the quicksort procedure

There are six relations:

sort(U, S)

partition(V, U, L, H)

components(£ , H, T)

append (A, B, C)

null(L)

elt(V)

sorting list U gives list S partitioning list U on value V gives

sublist L (values ~ V),

sub list H (values > V)

list L has head H and tail T

appending list A to list B gives list C

L is the empty list

Vis a number

Following Muggleton, the examples provided for the sort relation cover all lists of length up to three containing non-repeated numbers in {0, 1, 2}. There are 16 such lists, giving 16 E17 and 240 e tuples. The other relations are defined over this same vocabu­ lary.

• Finding how to append one list to another Examples covered all lists of length up to three with non-repeating elements drawn from {1,2,3,4}; since the closed-world assumption would give about 270,000 e tuples, a sample of about 9K of them was provided explicitly. Other relations were com­ ponents, null, list and reverse - note that the last two of these were not required for the definition of append.
• Finding how to reverse a list

Examples were the same as for the append relation

• above.

Results with these tasks, summarised in Table 1, show that FOIL handles them relatively well.

A more detailed examination of the quicksort task serves to illustrate the approach. Constants belonged to two types, numbers and lists. No orderings of the numbers were found, since none of the relations has two arguments of type number - from FOIL's perspec­ tive, then, any ordering is satisfactory. The ordering discovered for the list type started with the empty list, followed by all lists of length one, two, and then three, in agreement with intuition. The definition found,

has a clause with two recursive literals; the induced liter­ al ordering, requiring the first argument of any recursive literals to be less than that of the left-hand side, is clearly satisfied in both cases.

6.3 Examples from arithmetic

The final examples concern arithmetic recurrence rela­ tions:

· Finding a recurrence relation for (;;;.)

The relations used in this task were

Tuples for values of N up to 5 and for the corre­ sponding values for multiply and dec were provided.

· An artificial relation

This recurrence relation was specifically designed to test the approach. The underlying function is

The relations for this task were P(A, B, C) (mean­ ing G(A, B) = C), plus(A, B, C) and dec( A, B) as above. All tuples involving integer values up to 10 were provided.

The results on these tasks are summarised in Table 2.

In the second task, the constants are just the integers 1,2, ... ,10 and FOIL discovered their natural order . The definition found was not exactly the expected one:

The first and third clauses are fine. The second is a convoluted generalisation of the B=O case that is valid only for the restricted set of tuples provided - a reminder of the ever-present risk when learning from small num­ bers of examples. The literal ordering consistent with all three recursive literals is

and again there is no need for a third disjunct. The relation in this example is symmetric, showing that the approach prevents simple pseudo-definitions such as

which, of course, would lead to infinite recursion.

7 A Note on Complexity

As the above examples illustrate, the computational cost of the approach is usually moderate. This brief section looks at worst-case rather than average complexity to see where problems might arise.

In the first phase (Section 4), the fundamental opera-­ tion is that of checking the consistency of a potential con­ stant ordering. The implementation uses an incremental transitive closure method whose worst-case cost is O(c 4 ) for c constants. (Although other approaches have lower cost, the incremental method used by FOIL allows consis­ tency to be checked as each constraint is added and has advantages when searching for the maximal consistent set of argument pair orderings.) For r relations of arity a, the number of possible ordered relation argument pairs is O(ra 2 ). If p of these are ordered, the number of possible consistent sets of orders to be checked is 0(3"). (Note that the reverse of any order found must also be considered, but that an order and its reverse are never mutually consistent) .

The second phase (Section 5) occurs during clause development. If there are t tuples and v variables, the maximum cost of checking orderings of pairs of variables is O(tv 2 ) . For a target relation of arity a, there are O((v + a - 1} 4 ) recursive literals that are potential candidates for addition to the right-hand side. If the definition to this point contains l - 1 recursive literals, the cost per literal checked is O(la 2 ).

There are thus two exponential aspects of complexity: one with the number of pairs of argument orders that yield an ordering on the constants, and one with the arity of the target relation. The latter crops up in many places in FOIL, such as when evaluating the gain of potential literals. The cost of checking the ordering requirement for a recursive literal is usually small by comparison with the gain computation, so is not significant. The potential problem with the approach lies in putative situations in which there are many possible orders between pairs of arguments, of which about half are consistent. (The depth first search for a maximal consistent set halts once it becomes apparent that no further set can be larger than the best set found so far; if all pairs of arguments are consistent, little computation is required.) This circumstance has not yet been enountered in trials with a wide selection of problems from the literature. As an alternative to the present scheme, FOIL could use some heuristic method to find a near-maximal set of consistent orderings.

The approach described here decomposes the basic problem of finding an ordering of tuples of the target relation into finding orderings on pairs of their argu­ ments. This allows us to work with smaller sets { c con­ stants rather than O{c 4 ) tuples) and to use information from other relations in addition to the target relation. Although it may be possible to construct problems for which the tuple ordering approach is the only viable one, the decomposition is computationally attractive and works well in practice.

8 Conclusion

This paper has presented an effective method for sidestepping many problematic recursive clauses while learning a first-order theory. The approach uses an ordering induced on constants of each type to develop an ordering of recursive literals so as to guarantee that a recursive literal on the right-hand side of a clause is always less than the literal on the left-hand side that caused it to be invoked.

Although the method has been implemented and test­ ed as part of the new version of FOIL, it should be able to be incorporated into any learning system that develops clauses by repeated specialisation from a collection of ground facts . FOIL uses only constant atoms but a system that uses general ground terms could order them in a similar manner, either

• (a) by treating terms as atoms, or
• (b) by mapping all ground facts into function-free form, inducing an order on the atoms, then constructing from this an order relation on ground terms.

Again, if the order of constants or terms is known, or can be determined by some other means, the prepara­ tory heuristic ordering of the constants can be omitted and the method for ordering rec·ursive literals employed directly.

The process of finding an ordering on the constants consumes little time (a maximum of 0.02 seconds for the examples described in the previous section) . Once these orders are established, checking whether one variable is either greater than or less than another variable over a training set requires only the comparison of the ranks of pairs of constants and so is also computationally undemanding.

Although the approach is sufficient to prevent infinite recursion arising from ground queries on a single relation, it does not address non-terminating recursion involving more than one relation, e.g. when relation R invokes S and S invokes R. Since FOIL builds definitions for a single relation at a time, preventing infinite recursion of this kind would require a much more complex scheme.

The new version of FOIL incorporating the approach described in this paper is available by anonymous ftp from beta.cs.su.oz.au under the file name fpub/foil4.sh