Representation and Induction of Infinite Concepts and Recursive Action Sequences

1. Introduction

Program synthesis by induction as opposed to program synthesis by deduction from input-output specifications becomes a matter of increasing interest in AI and Computer Science. In this field much work has dealt with the synthesis of LISP pro­ grams from examples of computations /3/, /4/' /5/.

We are interested on the one hand in the development of a general formalism not de­ pending on a specific programming lan· guage and on the other hand in the induc­ tion of certain infinite concepts and re­ cursive action sequences extending in this way our earlier work on concept learning /6/, /7/. By infinite concepts we mean classes of strings and other stuctures having some intrinsic periodi­ city (In Pattern Recognition only feature vectors of fixed dimensionality have been considered so far). Our method is based on the so called algebraic semantics and recursive program schemes /1/, /2/ and it is intended to provide a general frame­ work for the abovementioned representation and induction problems. The induction principle we introduce in this paper is a more general version of SUMMERS' main syn­ thesis theorem /5/. Our main aim is to apply it to the representation and induc­ tion of recursive action sequences from examples of observed behaviour. This is also of importance for problem solving and hierarchical planning.

Section 2 starts with a brief survey on the basic definitions together with exam­ ples taken from the recursive operation of clearing a block and preparing in this way the more detailed discussion of the CLEAR-operator in section 5. In section 3 the induction principle is stated and then applied to two basic examples in section 4 and 5 demonstrating the general method. The consideration of synthesized programs as recursive program schemes (RPS) allows us to introduce a new prin­ ciple of generalization not investigated in AI until now.

2. Basic definitions

Term algebras, trees, rewriting rules,

trogram schemes n the following we use the notations and definitions of /1/. Let Vk = {v 1 , ··· ,vk)' and V = U Vk be sets of variables and F kS1

a set of primitive function symbols with arity or rank {fe-F has arity~{f)).

F contains a distinguished symbol ~ representing the ·undefined·. Then let M{F,V) be the set of finite well-formed terms on FuV. Terms are inductively de­ fined by

Definition 2.1.

1} v E V, x 0 e F 0 is a term {F 0 =constants)

1. If t 1 , ··· ,tnE M{F,V) are terms then f(t 1 , ··· ,tn)· with fE F, ~{f) = n is a term.

Terms can be represented as trees.

Example 2.1. The term g{r{v 1 ), v 2 , h{f{v 1 ), g{r{f{v 1 )), v 2 , ..n. )) ) with f, g, r, h E F, f {f) = 1, f{g) = 3, fj {h) = 2 is the tree

(For the interpretation as a partially de­ fined program for clearing a block see ex­ ample 2.4.)

Definition 2.2.

On M(F,V) a partial order< is defined, intuitively: t~ t' if t' can be generated from t by substitution of ..n. by terms #.D.. at some positions in t · ..D.. is the least element of-<.

Every directed subset A' M( F, V) has an upper limit Sup(A) which is a finite or infinite tree. This allows one to extend M F V to the Moo F V of infinite trees w ic we wi esignate y as oppose to finite trees t).

In addition to the primitive function sym­ bols f€ F we consider a set ~={� 1 , ··· ,GJ of function variables with a rity 9 (Gi) = = ki ~~~~~r~~~;m;~~er on play the role of

Let MIXl(F v lf,v) be the term algebra ex­ tended by ID·

Definition 2.3.

A recursive prosram scheme (RPS) is a pair < ~ , t > consisting of a system of equations

t. € M( F u ~, V k ) ·

and a term t e: M(F v f, Vk), Gi E f,

l. i t plays the role of the "main program", which is composed of the "subprograms" Gi mutually "calling each other" by means of r: ·

Exam~le 2.2.

(For the interpretation as a program of clearing a block see ex. 2.4) A system ~ can be "solved" using the fol­ lowing rewriting rule by which function variables in the ti s can be iteratively eliminated.

Definition 2.4. (rewriting rule) By this definition we allow in a tree t subtrees beginning with function vari~ abies G E ~ to be substituted by other trees Q(G} (which appropriate correspon­ dences . in the variables).

Formally: A tree t is transformed into another tree B(t) inductively defined by

1. §(x) = x if x e F 0 v V

A

2) ~<f<t 1 , ··· ,tk>> = f(e(t 1 ), ··· ,Gctk>>

In 3) the r.h.s. means that in the tree Q(G) the variable v 1 is to be replaced by Q(ti), 1 ~ 1 ~ k. (Note that ~(ti) = ti if ti contains no function variables.) Instead of ~(t) we will also write

if in t Gi is to be replaced by tj. Example: se~ example 2.3

Definition 2.5

Let~ be a RPS as in def. 2.3. For 1~i~n and l = 0, 1, 2, ··· we define a sequence Gp) by

using the substitution rule of def. 2.4. This sequence is called KLEENE-sequence. It can be shown that Gp>-< GF+ 1 ), l = = 0,1, ··· and that S~p GP)=DfT(! ,Gi), 1 ~ i ~ n is the fixpoint solution (least solution) of l:

Example 2.3.

using the rewriting rule of def. 2.4. with Q(t) = G(l+ 1 )(v 1 ,v 2 ), Q(G) = G(l)(v1,v2).

Note that this KLEENE-sequence is genera­ ted by the following procedure which we will use for induction(8section 3):

There is a tree tr = G 1 = g{r{v 1 ), v 2 , h(f(v 1 ),..n.)) and a fixed node min tr (labelled by .n.) and G{ 1 + 1 ) is construc­ ted b} substituting G{l) [t/~J = = G{l (f{v 1 ), v 2 ) at node m ( 1 = 2,3, ··· ). G(l) [t/~J means that the , vector of vari­ ables~= (v 1 ,v 2 ) of G(l) has !o be re­ placed by: the vector of trees t = = {f{v 1 ), v 2 ).

Interpretation and valuation Until now we have considered syntactical structures only. By an interpretation I we assign to every function symbol f with arity i a function on some domain

(D x D x ··· x o )I. {We have to take v1 v2 vi into account sorted functions and vari· ables v 1 , ··· ,vi).

.< is interpreted by :: I, ..Cl.. by .L (the "un­ defined·). An interpretation assigns to each RPS a program. By a valuation ¥ we assign to each variable v. a value rom Jdomain {Dj)I. An interpretation together with a valuation assigns to a RPS a value (the result of the computation by~~

Examfle 2.4. (see fig. 1 and example 2.2.) Let , F£ F be the truth values ·true· and "false· 0 respectively and in example 2.2. g be the McCARTHY-conditional

( <F denotes interpretation) Let v 1 be a variable denoting definite objects x (blocks), r(x} the predicate CT{x) = cleartop (x), f{x) the logical function Lu(ON{u,x)) ("that block u lying on block x·), v 2 a state variable s and h(x,s) 4:= put (x,s) ("put x in state son the table" getting the new states'= put (x,s)). Then

�{v 1 ,v 2 )~ CLEAR (x,s)

is the (recursive) CLEAR-operator· In the case of fi~. 1 we have 2 CLEAR (x,s) = put {f{x), put (f (x},

g(CT{f 2 (x)),s, ··· ) ··· )

= put (f{x), put {f 2 {x},s))

since g (CT{f 2 {x)), s, . ··· ) = s

3. Principle of induction

Our main aim is to construct {recursive) programs from examples of computations. The induction principle is a generaliza­ tion of the synthesis theorem of SUMMERS /5/. {The convergence properties areal­ ready established by our use of the KLEENE-sequence, def. 2.5., for induction.) In the first stage we build from a finite set of examples a finite tree ~ either by a learning algorithm or by a combination of alternatives similar to /5/. Then we try to interpret i as an element of a KLEENE-sequence of some RPS which has to be induced. Formally: If there exists a tree tr · M(F~~,V}, a fixed node min tr, a vector t =.(t 1 , ··· ,t ) of trees tiE M(Fu ~. V} {1 = 1, ··· ,R) and a se­ quence

then we consider ~ as~the l·th element of a KLEENE-sequence. t(t/v] means that the vector v of variables of t has to be re­ placed by the vector rand tr{t/m) means that m is the root nod~ of subtree t in tr. (In general the t(lJ 's are defined only for some specific values of the vis and the domain has to be extended by the induction process.) The method can be generalized to the case where several nodes mk in tr have to be replaced by

·macro-functions· (see section 5). Having established t as t(l·} and 1· being suf­ ficiently high we extrapolate the sequen­ ce for all l and get the simplest hypo­ thesis (i. e. RPS) which has ~ as the

l·th element of its KLEENE-sequence. 1· can be regarded as a measure of the reli­ ability of the hypothesis. In sections 4 and 5 we demonstrate the method by two basic examples.

4. Induction of recursive Boolean expressions

We consider the following classification problem on the set{a 1 a 2 ··· akl k=1,2 ··· J of binary strings {aj £ {0,1) for 1~j; k): all strings with ai = 1 for i = 1, ··· ,k belong to the class T ("true·) and all other strings (i. e. containing at least one aj = O) belong to the class F {"faa~~ From a finite training sample of strings the algorithm has to infer the classifi­ cation function for strings of arbitrary length. Our set of primitive functions g, x, r, s e F (flee section 2) is defined as follows ·

Definition 4.1. g is the McCARTHY conditional as in ex. 2.4.

s(k) = k + 1 k = o, 1, 2, ···

x(i), r(j) are tests to be performed on strings, s is the successor function, T, F€ F 0 are the truth values for tests as in ex. 2.4. Suppose we have a training sample of all strings up to length k = 2, strings consisting only of symbols 1 being classi­ fied as T, strings containing at least one 0 as f. Then by a slight modification of an algorithm for automatically construc­ ting decision trees from training s~mples of feature vectors /6/, /7/ the following initial tree ~ can be built

This tree classifies (by definitions 4.1.) the strings 1 and 11 as T, ~11 other strings with length ~ 2 as F and strings with length> 2 asA.

According to section 3 we have to search for a tree tr which appears as a subtree of itself (at a fixed node m) r~cursively with appropriate substitutions t/V of va­ riables. (That is we use a matching pro­ cedure with appropriate replacement of variables.)

Observing the "periodicity" of the appear­ ance of the symbols r and x respectively in ~ at the same position in subtrees be­ ginning with g we define

with G( 1 )(s(1)) = G( 1 )(2) = g(x(s(1)),

g(r(s 2 (1)),..n, i'), F)

That is we have for 0 ~ 1 ~ 1·, 1· = 2 a KLEENE.sequence

which is partially defined for 1 "S ti ~ 111! - (1 - 1) (1 = 1,2; 1· = 2) and undefined for other values of n. In the sense of section 3 we have (fo~ n = 1,2) tr = g(x(n), g(r(s(n)), c, T), f) .. and t = t = s(n). c is an arbitrary tree labelling 1 the node m mentioned in section 3. Now we want to get the simplest hypothesis for continuation of the KLEENE-sequence. The simplest hypothesis is to extrapolate G(l) for all 1 and fpr all n

(i. e. extending the domain) using the successor function s(n) on the natural nu"mbers.This way we get the recursive program

G(1) accepts (classifies) all strings ~ containing only 1's as T arr-others as r and our starting tree 1 is the second element of its KLEENE-sequence. (With other words: 2:: accepts for n = 1 a log,. ical conjunction of arbitrary length. For n> 1 the first n - 1 elements of a string are ignored.) Note that the reliability of the hypothesis is low because we have used examples up to 1· = 2 only.

Now we introduce a new principle of gene­ ralization. We abstract from the interpre­ tation of the function symbols G, g, x, r, T, F used so far (see def. 4.1.) and con­ sider r as a pure syntactical structure (i. e. RPS). If we interpret_g, x~ r as in def. 4.1. but T by F and F by T thenX accepts all strings consisting only of 1~ as F and all others as T. If we addition­ ally interpret x by"'x (negation of x) then ~ accepts all strings containing at least one 1, i. e. a logical disjunction of arbitrary length. With another inter­ pretation of x, r, we could makei. accept all graphs consisting of a directed chain (fig. 2a) and with still another inter­ pretation all directed circuits (fig 2b). This means that L read as a RPS accepts families of structures which can be con­ sidered as being equivalent in this sense. This could be used to avoid the full in­ duction process for a new problem for which one has a starting tree~. Before performing the induction one could try to find a structural isomorphism of ~ with an element of a KLEENE-sequence of an al­ ready existing RPS (solution of an old problem) being at the same time a syntac­ tical solution of the new problem too. ~that this procedure may also be re­ garded as some kind of analogical reason­ ing in which functions (or relations) would be replaced by other functions (relations).

5. Learning action sequences

Now we consider a more complicated exam­ ple in which several nodes mk in the tree tr (see section 3) have to be replaced by "macrofunctions". We return to the problem of clearing a block x (fig. 1) which we have dealt with in examples 2.2. - 2.4. The variables and primitive functions are as in ex. 2.4. Suppose we have the follo­ wing three examples of observed behaviour (training instances):

CT(x) ~ s (·if clartop (x) then nothing is to be done·)

CT(f(x))_. h(f(x}, s) (·if the block f(x} lying on x is clear then put f(x} on the table in state s·)

Combining these alternatives by means of the function g to a initial tree ~ leads to

From the first position in each subtree beginning with g we get the sequence CT(x}, CT(f(x}}, CT(f 2 (x))

and define

With this definition we get from the se­ cond position in the subtrees beginning with g the sequence

s, h(F(1,x}, s}, h(F(1,x), h(F(2,x}, s)). The simplest hypothesis is to continue by h(F{1,x), h{F{2,x), h{F(3,x), s))}, ···

i. e. by using the successor function s(n) for extrapolation. With a function

the above sequence can be written as

H(n,x,s) =of H'(1,n,x,s}; H(O,x,s) =of s

(5.4}

A and the tree t (5.1) as

The simplest hypothesis is again to ex· trapolate by means of the successor func­ tion. Using the induction methods intro­ duced in section 3 and 4 we get this way a KLEENE-sequence G'(l) and the fixpoint solution

Pro~osition 5.1.

G'{ )(O,x,s) reproduces the tree i (5.1)

Proof: By def. 2.5. of the KLEENE-se­ quence and use of (5.2) - (5.4). G'(O,x,s) clears a block x from an arbi­ trary number of blocks (fig. 1). Finally we compare the representation G' (5.6) of the CLEAR-operator with the re­ presentation G introduced in examples 2.2. and 2.4. which is the minimal one (but not easy to learn). The equvalence of both representations is established by the following

Proposition 5.2.

There exists a syntactic transformation which transforms G' into G.

Proof: By proving that each element G,(l) of the KLEENE-sequence of G' can be trans-

formed into the corresponding element G(l) of G using the reduction rules

repeatedly. These rules could be made clear from the semantics in ex. 2.4. c~ means that the l.h.s. of the rule can be replaced by the r.h.s.)

6. Conclusion

A framework for representation and in­ duction of infinite concepts and action sequences has been represented. It was applied to examples taken from typical AI domains, demonstrating the general con­ struction algorithm. The induction prin­ ciple was formulated with the help of the KLEENE-sequence. Equivalently the concept of a tree grammar could have been applied, i. e. our induction problem is equivalent to the problem of identification of a tree grammar. In our examples we have dealt with the construction of single loops only, multiple (nested) loops can be treated by a more step procedure in a similar manner. The use of program sche­ mes (RPS) instead of programs allows one to treat classes of functions simultan­ eously. This can be used to avoid the full solution of new problems if there exists already program schemes isomorphic to the111.

In future work we will investigate broad­ er classes of functions playing an impor­ tant rols in AI research especially in picture recognition and planntng.