An Interactive System to Learn Functional Logic Programs

1 Introduction

Inductive Logic Programming (ILP) is the field of Ma­ chine Learning concerned with the task of learning logic programs from positive and negative examples in the form of ground literals [Muggleton, 1991; Muggleton, 1992; Rouveirol, 1992; Bergadano et al., 1993] . The ob­ tained results have shown some major problems.

Systems tend to be slow and do not always termi­ nate successfully, even when a solution program ex­ ists. A natural approach consists in restricting the hy­ pothesis space by means of strong constraints of var­ ious kinds includin~ rule models [Kietz and Wrobel, 1991], predicate sets [Bergadano, 1991], mode [Kirschen­ baum and Sterling, 1991; Muggleton and Feng, 1990; Shapiro, 1983] and type [Morik, 1991; Raedt, 1991; Shapiro, 1983] of the variables, and integrity constraints [Raedt and Bruynooghe, 1992] .

FILP follows the same idea, and restricts the inductive hypotheses to logic programs that are functional, in the sense that every n-ary predicate P can be associated to a functional relation as follows:

• m of P's arguments are labeled as input,
• the other n-m arguments are labeled as output,
• for every given sequence of input values, there is one and only one sequence of output values that makes the predicate true .

The above properties must be determined by the user and are assumed also for the examples that are not seen. This is necessary because some examples may be missing and will be queried later .

These requirements do not affect the expressive power ,

Daniele Gunetti

University of Torino corso Svizzera 185 10149 Torino, Italy

e-mail: gunetti@di.unito.it

as any computable function can be represented by a functional logic program and, on the other hand, make the learning task a lot easier, because many clauses that would otherwise need to be generated and checked against the examples are now disallowed a priori, and the order of the literals within a clause antecedent is somehow constrained by the need of computing an out­ put value before it can be used as input in another literal.

Only few systems [Kietz.and Wrobel, 1991; Morik, 1991 ; Raedt and Bruynooghe, 1991] are able to learn programs with more than one clause consequent . The reason for this lies in the extensional interpretation of all predicates occurring in clause antecedents, including recursive calls. As a consequence, systems may be unable to learn a pro­ gram, even when an allowed inductive hypothesis ~hat is consistent with the examples exists. Even worse, 1t may happen that a program is learned that computes wrong outputs even for the given examples. We solve this prob­ lem by querying the user for relevant examples that may be missing, depending on the hypothesis space that has been defined. As a result of this, every learned program behaves as required on the given examples and such a program is always found if it exists. The queries that are asked to the user are of the type of the existential queries of CLINT [Raedt and Bruynooghe, 1991], be­ cause they contain unbound variables. However, these variables are labeled as output, and, as a consequence, there is always one and only one answer to every such query.

Therefore, functionality is the central idea that allows us to face what we have individuated as two major problems in ILP: (1) restricting further and in an explicit _way the set of allowed inductive hypotheses and (2) bemg able to learn multiple predicates, in our case by means of in­ put/output queries that make the extensional informa­ tion sufficient. In the following we will call the predicates that we need to learn the inductive predicates, while the others will be either built-in or defined by the user .

FILP does not need a complete extensional specifica­ tion of the predicates to be learned, up to a certain ex­ ample complexity, as it happens, e.g., with FOIL [Quin­ lan, 1990] . Such a specification can be even more time­ consuming and error-prone for the user than actually writing the desired program. By contrast , a very limited number of initial examples is required by FILP, and a few additional input values are presented to the user, and the corresponding outputs are requested. However, not all of these input/output examples are always nec­ essary, in the sense that it may happen that, even for a subset of them, there is only one allowed program that is consistent (i.e., the solution is determined) . We believe that this problem cannot be remedied unless we give up the extensional interpretation of predicates. But, in that case, the order the clauses are generated with becomes relevant, and backtracking may be required.

2 The Learning Procedure

In this section we present the FILP system and prove some formal properties about it. As in most other ILP learning systems clauses are learned one at a time, inde­ pendently of the ones that were learned previously. Since FILP learns functional relations, it really only needs positive examples. Negative examples are implicitly as­ sumed to be all the ones having the same input values as the positive examples but different outputs.

2.1 A functional mode for variables

For functional logic programs we need to specify a func­ tional mode for every variable of every literal used in the learning task, in order to employ and learn only func­ tional relations . For example sum(in,in,out) would be a legal way to use sum, but sum(out,out,in) would not, because it does not represent a function. For this reason, FILP asks the user to provide a functional mode for all predicates, and then uses it for constraining the allowed clauses as follows: a literal L can occur in a clause an­ tecedent f3 1\ L 1\ -y only if all of its input variables occur in {3, or are input variables in the head. Moreover, as a result must always be produced, the output variables of the head must occur somewhere in the body.

For example, suppose we have to learn a concept c with a mode for variables c(in,in,out), using predicates a, b, d with a mode for variables a(in,out), b(in,out), d(in,in,in,out) . Then the clause c(X,Y,Z) :- a(X,W), b(Y,K), d(X,W,K,Z) is a legal one because every input variable is defined before of being used, and the output variable of c is at last instantiated.

2.2 A general extensional top-down method

This subsection contains a basic version of FILP, without queries for adding the missing information, and an ex­ ample of its use, in order to describe the approach and to prepare the discussion of the problems stemming from it and the extension that is needed. This basic algorithmic scheme is similar to the ones of ML-SMART [Bergadano and Giordana, 1988] and FOIL [Quinlan, 1990], but uses the notion of a predicate set and requires the function­ ality constraints, and, therefore, does not need any neg­ ative example. It also accepts more than one inductive predicate, although the extension presented later is nec­ essary for making this feature work in general. In the following a and -y represent generic conjunctions of lit­ erals.

The main loop · in the algorithm tries to cover every positive example of every predicate P. This is done by repeatedly generating clauses of the form "P(X) :- a", and then removing the covered examples. Clause gener­ ation is performed as follows:

a- true while covered( a) :f; 0 do if consistent( a) then return(P(X) :- a) else choose a predicate Q and its arguments Args such that the functionality constraint is satisfied if no such Q is found then backtrack a -a 1\ Q(Args)

where covered(a) and consistent(a) are defined below:

Definition 1: We say that the clause P(X,Y) :- a(X,Y) extensionally covers P( a,b) iff a( a,Y) extensionally computes Y = b, where extensional computation is de­ fined as follows :

• a = Q(a,Y) with functional mode Q(in,out). Then Q(a,Y) extensionally computes Y = b iff Q(a,b) is derivable from the definition of Q or is a given example of Q.
• a= -y(X,T), Q(T,Y) with functional mode -y(in,out) and Q(in,out) . Then -y(a,T), Q(T,Y) extensionally computes Y = b iff -y(a,T) extensionally computes T = e and Q( e, b) is derivable from the definition of Q or is a given example of Q.

In the algorithm, an example P(a,b) belor:6s to covered(a) iff a(a,Y) extensionally computes Y=b, :md consistent( a) is true iff, for no such example, a( &.,Y) ex­ tensionally computes Y=c and c:j;b. ·

Suppose, for instance, that we have to learn the logic program for reverse. Let examples(reverse) be:

reverse(O,O), reverse([a],[a]), reve1'se([c],[c]), reverse([ a,b],[b ,a]), reverse([b,c ],[c,b]), reverse([a,b,c] ,[c,b,a]).

Suppose we also know that reverse depends on the following set of predicates, with their usual definition supplied (except for reverse, of course):

null, head, tail, assign, append, reverse.

This is an important information, but obviously still very far away from the actual program that we want to learn: we need to associate variables to these pred­ icates, and divide the obtained literals among the un­ known number of clauses that will be necessary. The or­ der of the literals is partially constrained by their mode:

null(out), null(out), head(in,out), tai/(in,out), assign(in,out), append(in,in,out), reverse(in,out).

The algorithm starts to generate the first clause - the antecedent a is initially empty. We need to choose the first literal Q(Args) to be added to a. As we have left the heuristics unspecified, we will choose it so as to make the discussion short. Variables are taken from the clause head, or from a finite set of additional typed variables.

Let o:=null(Y). A given example is covered, but we cannot accept the clause reverse(X,Y) :- null(Y) as it is, because it computes wrong outputs for some given input values, e.g. reverse((a],O), so more literals need to be added.

Let o:=null(Y) 1\ head(X,H); in this case no positive examples are covered. Clause generation fails and we backtrack to the last literal choice.

Let o:=null(Y) 1\ nuli(X); the first example is covered and no wrong outputs can be computed. A clause is gen­ erated and the covered example reverse(O,O) is removed from examples( reverse).

We proceed to the generation of another clause; o: is empty again. Suppose we have already generated o:=head(X,H) 1\ taii(X,T); all the remaining examples are covered, but again we have to specialize because o: could compute wrong outputs.

Let o: = head(X,H) 1\ tai/(X,T) 1\ reverse(T,W); this clause again extensionally covers all remaining ex­ amples. For instance, for the last example we have that head((a,b,c],a) and tai/((a,b,c],(b,c]) are true, and reverse((b,c],(c,b]) is a given example. However, the output variable Y is not instantiated and the procedure needs to be continued.

Suppose we add the literal assign((H],Y). The so ob­ tained clause covers reverse((a],(a]) and reverse((c],(c]), but for reverse((a,b,c],Y) it computes Y=(a), which is not consistent with the data. Further specialization would fail to correct this problem and we need to back­ track, obtaining, e.g.,

which covers all remaining examples and does not com­ pute wrong outputs. The final solution turns out to be:

2.3 Partial justification of extensionality

Extensional methods are able to learn clauses individu­ ally, without worrying about their behavior in the con­ text of the final program. This is an advantage in terms of efficiency, because once a clause is generated, it will be kept, and there is no need for backtracking of this type. This independence of the clauses is made possi­ ble by the extensional interpretation of recursion and of the other sub-predicates: when a predicate Q occurs in a clause antecedent o:, it is evaluated as true when the arguments match one of the positive examples. For in­ stance, the clause

extensionally covers the example reverse((a],(a]) because head((a],a) and tai/((a],O) are true, and reverse(O,O) is also a given example. The previously generated logical definitions of Q are not used. The method leads to a fun­ damental property of extensional methods, which will be proved below.

Definition 2: A program P is compiete w.r.t. the ex­ amples E iff (V Q(i,o) E E) P 1- Q(i,o). A program Pis consistent w.r.t. the examples E iff (,ll Q(i,o) E E) P 1Q(i,o') and o:f;o'.

In other words, a complete program computes all de­ sired outputs, and a consistent program does not com­ pute wrong outputs.

Lemma 1: Suppose the extensional top-down method given above outputs a logic program P, that always ter­ minates for the given examples.

Let Q(X,Y) :- o:(X,Y) be any clause of P, then

(VQ(a,b) E Examples(Q)) o:(a,Y) ext. computes Y=b -+ P 1- Q(a,b).

Proof (by contradiction)

Suppose that (1) (VQ(a,b) E Examples(Q)) o:(a,Y) ext. computes Y=b but (2) P If Q(a,b) . Let o: = (3(X,Z) 1\ R(Z,W) 1\ r(W,Y), where R(Z,W) is the first literal such that:

- R is an inductive predicate (in particular, R could be Q),

-there is an example R(r,s) such that f3(a,r) 1\ R(r,s) 1\ r(s,b) is extensionally true.

-for any such rands, P If R(r,s).

There must be a literal R(Z,W) in o: with these prop­ erties, because of the assumptions (1) and (2) . But the example R(r,s) must be extensionally covered, since the algorithm has successfully terminated. Therefore, the same argument can be repeated for R(r,s), with a never ending chain of valid deductions. This contradicts the assumption that the program output by the system ter­ minates on all given examples. ·

Theorem 1: If the given extensional top-down method terminates successfully, then it outputs a complete pro­ gram P.

Proof

(Ve E examples) P extensionally covers e, since the algo­ rithm terminated successfully. By Lemma 1, then, P 1e, i.e. P is complete. ·

The above proof is also valid for systems such as FOIL, and is a partial justification of the extensional evaluation of the generated clauses. However, other desirable prop­ erties, similar to the one given by Theorem 1, are not true. First, even if a complete and consistent program P exists in the hypothesis space, we are not guaranteed that it will be found. Second, the algorithm may out­ put a program which is inconsistent with respect to the given examples. This is due to the fact that some ex­ amples may be missing, while extensionality somehow assumes them to be present. This is true also for functional programs, because even if the single clauses of P satisfy the functionality constraints, different values may be computed by different clauses. A detailed dis­ cussion of these problems with examples may be found in [Bergadano, 1993].

2.4 Completing examples before learning

There is no reason why all examples smaller than some fixed complexity bound should have to be given by the user. After all, the whole motivation of induction is that some information is missing. The important points are that (1) if a program P consistent with the given exam­ ples exists, then it must be found and (2) the induced program P must not compute wrong outputs on the in­ puts of given examples. The basic extensional method described in the previous section (and other systems, such as FOIL) guarantees neither, unless some specially determined examples are given in the inductive relations . To overcome this problem, FILP queries the user for some of the missing examples, as done with the "eager" strategy in MIS. For every legal clause ( = permitted by the constraints) of the type

P(X,Y) :- A(X,W), Q(X,W,Z), a.

where Q has mode Q(in,in,out), and for every example P(a,b), we do the following:

• extensionally compute A(a,W), obtaining a value W = c;
• ask the user for the value Z computed by Q(a,c,Z);
• add this example to examples(Q).

Adding one example may cause the request of others. Suppose, for instance, that an example A(a,d) is added for A. Then, the above procedure might add an example for Q, e.g. the one matching Q(a,d,Z). As a consequence, the procedure must be repeated for every clause, again and again, until no more examples are added for the in­ ductive predicates.

Both for making the above procedure terminate and for guaranteeing the termination of learned programs, we require that any recursive call within a generated clause matches the following pattern:

where Q(X,Y) is known to define a well ordering be­ tween Y and X (Y <X) . It is possible to show that, if every recursive clause in P satisfies the above constraint, then the procedure terminates.

As an instance, suppose that we want to learn a sort program. Consider the following clause:

sort(X,Y) :- tail(X,T), sort(T,W) .

It satisfies the constraint on recursive calls because, when tail(X,T) is true, then T is a shorter list than X and this is a well order relation. Consider the exam­ ple sort([3,2,1],[1,2,3]). By using the clause, the user is queried for the value of sort([2,1],W), and this is added to examples(sort). This new example causes the rep­ etition of the procedure, and the user is queried for sort([1],W), and at the next step for sort(O,W).

Not all possible examples have been added, only the ones that were useful for that clause, given the initial example in examples( sort) . If this is done for all the clauses that are possible a priori, i.e. that satisfy the given constraints, then the problems mentioned in the previous subsection are solved. When speaking of FILP, we will assume in the following that the above comple­ tion procedure has been executed as a first step.

Lemma 2: Suppose the examples given to an exten­ sional learning system are completed with the above given procedure. Suppose also that some program P be­ longs to the hypothesis space and Q(a,b)Eexamples(Q) after the completion.

If P f- Q (a, b) then the first clause in P resolved against Q( a, b) extensionally covers Q( a,b).

Proof (by contradiction)

Suppose that (1) P f- Q(a,b), where Q(X,Y) :- a(X, Y) is the first clause used in the proof, but (2) Q( a,b) is not extensionally covered by this clause.

Let a(X, Y) = {J(X,Z) 1\ R(Z,W) 1\ 'Y(W, Y) . Suppose that P f- {J(a,r) 1\ 'Y(s,b) and P f- R(r,s), but R(r,s) ¢ examples(R). There must be one literal R(Z,W) having this property, because of assumptions (1) and (2), and let R(Z,W) be the first such literal. The user must have been queried for R(r,W), because {J(a,r) is extensionally covered. Since R(r,s) ¢ examples(R), the answer must have been W=w-:j;s . But then no clause could extension­ ally cover R(r,s), or it would be inconsistent, while P f­ R(r,s). We could now repeat the same argument for R. This would produce a non-terminating chain of resolu­ tion steps, and a finished proof ofQ(a,b) would never be obtained, contradicting the initial hypothesis that P f­ Q(a,b). ·

Theorem 2: If a complete and consistent program P exists, then FILP will terminate successfully.

Proof (by contradiction)

If FILP does not terminate with a solution, there must be an example Q(a,b) that it cannot cover. Since P is complete, P f- Q(a,b). Take the first clause Q(X,Y) :-a resolved against Q(a,b). By Lemma 2, a(a,Y) ex­ tensionally computes Y=b. But this clause would have been expanded by FILP and found to cover the example. Moreover, consistent(a) is true, because P is consistent and by the contrapositive of Lemma 1, and therefore the clause would have been generated and the example would have been covered. ·

Theorem 3: If FILP terminates successfully, then it outputs a consistent program P.

Proof

If P is not consistent, then there must be some example Q(a,b), such that P f- Q(a,c) and b-:j;c. But, by Lemma 2, some clause Q :-a of P will extensionally cover Q(a,c) . But, in that case, consistent(a) would have been false and FILP would not have generated that clause. ·

By virtue of Theorem 1, this program will also be com­ plete.

3 Results

FILP is written in C-prolog (interpreted) and runs on a SUN SPARCstation 1. Table 1 contains results about some standard logic programs learned by FILP. Times required to learn the programs are in seconds.

The second column of the table contains the set of examples initially given to FILP. Observe that, apart from member and subset, one initial carefully chosen ex­ ample is sufficient to learn the corresponding program. Member and subset require a minimum of two examples because they do not represent functional relations, and must be turned into functions by adding a boolean ar­ gument which is true if the corresponding relation holds and false otherwise. In general, it is possible to prove that one initial example is sufficient to learn all the clauses necessary to derive it. This means that it is possi­ ble to learn a program starting with the minimum set of examples such that the program itself and the negation of those examples represent a minimally unsatisfiable set of clauses. Then, it is obviously better to chose exam­ ples as simple as possible, in order to limit the number of queries the user will have to answer.

The third column shows the final number of examples used by FILP in the learning process, the initial ones plus those queried to the user. For example, starting from the given example, the set of examples of union is completed by querying the user for union([b],[a,c],?) and for union(O,[a,c],?) .

Note that FILP is also able to learn more concepts at the same time . For example it has learned quicksort together with its major subprogram partition, starting with only one example of quicksort and, at the begin­ ning, without examples of partition. The time required for the entire task was about the sum of the times re­ quired .to learn independently quicksort and partition.

We must remark that FILP does not learn concepts separately, as it would be done by other systems such as FOIL and GOLEM [Muggleton and Feng, 1990]. We tell the system that quicksort could depend on partition, and FILP queries the user for the missing examples of partition. Then these examples are used to learn partition itself.

FILP can also work with the extensional definition of a concept. So, it is possible to learn quicksort without learning partition, and only relying on its extensional definition (the given or queried examples) . On the other hand it can learn more than two concepts together . We could also give no intensional definition for append, but only some examples, and have FILP learn also append together with quicksort and partition. Finally, the last program in the table is a version of quicksort not em­ ploying the append predicate.

As an example, below are the learned programs for partition and quicksort without append; it should be noted that FILP works with "flattened" clauses [Rou­ veirol, 1993], where functions are transformed into pred­ icates.

4 Conclusion

We have described four major characteristics of FILP. First of all, since FILP knows it is learning a func­ tion, it needs only positive examples of the program to be learned. This makes the task of the user easier, because he or she has to think only in terms of "what the program must compute" and not in terms of "what the program must not compute" . Nonetheless, for ev­ ery given positive example Q(a,b), all the corresponding negative examples {Q(a,k)lk:f:b} are implicitly known and can be used by FILP. Moreover, strong function­ ality constraints limit the number of legal clauses and consequently increase the efficiency of the system.

Second, FILP requires a very limited number of exam­ ples and, partially, this is still due to the knowledge of FILP about functions . For example, quicksort is learned with only six positive examples (plus seven examples for partition, if we want to learn that , too), while GOLEM employs fifteen positive examples (plus an unspecified number of negative examples) to learn quicksort alone. Simpler programs require a smaller number of examples to be learned. The only system, up to our knowledge, able to learn logic programs with a smaller number of ex­ amples than FILP is LOPSTER [Lapointe and Matwin, 1992] . Usually LOPSTER works with only two exam­ ples, but one of the two is in fact required to corre­ spond to the non-recursive clause of the desired program. Moreover LOPSTER is a restricted learning system and it is, for example, unable to learn quicksort .

Third, FILP queries the user for the missing examples. This means that the user must not provide all the needed examples to learn a program at the beginning. He or she can forget some examples, and FILP will ask for them. Observe that FILP queries the user only for the examples it really needs, so it will not waste time trying to cover useless examples. A similar technique is used in Shapiro's MIS . However MIS is an incremental sys­ tem, and newly added examples may require some pre­ viously generated clause to be retracted. This happens both with the contradiction backtracing algorithm and when refining clauses with the eager strategy [Shapiro, 1983] . In other systems [Muggleton and Feng, 1990; Quinlan, 1990] the user must provide all the examples at one time, and usually a superset of the examples needed is given, resulting in a lot of time wasted in covering useless examples . Experience with FILP has shown that the best way to use it is to start with just few significant examples (most of the time one is enough), and the sys­ tem will query for the missing ones needed to perform the learning task.

Finally, FILP learns complete and consistent pro­ grams, and this means first of all that programs learned by FILP have not unexpected behavior (that is, they do not cover negative examples) as it is the case for other extensional methods (such as FOIL) which do not com­ plete the given examples.

Experiments and results obtained with FILP have shown how, limiting our attention to functional logic programs, it is possible to acquire efficiency (with al­ most no loss in generality) by exploiting constrains on functionality and implicit negative examples. We believe that this possibility is not limited to extensional meth­ ods, but could be useful for every ILP learning system.

Acknowledgments: This work was in part supported by BRA ESPRIT III Project 6020 on Inductive Logic Programming.