Induction of Relational Productions in the Presence of Background Information

1. INTRODUCTION

The long-range goal of this work is the develop­ ment of an operational, general purpose mathe­ matical theory of inductive learning whose imple­ mentation would be capable of emulating the behavior of empirical programs written for spe­ cialized tasks. This paper describes a generali­ zation theory for the induction of relational productions in the presence of "background infor­ mation", i.e., a separat~ body of facts potentially relevant to the generalization process. With only minor interface variations, a SNOBOL4 computer implementation of this theory exhibits behavior in four distinct intelligence paradigms:

1. Letter sequence completion (e.g., ABMCDM ... );
2. Selection of best visual analogies in IQ test questions;
3. Learning operators ("rules") from before-and­ after situation pairs and counterexample pairs;
4. Learning operators from observation of situa­
5. tion sequences.

Problems in the first paradigm have been solved repeatedly by programs specially written for this task. For example, Williams (1972) developed a program with behavior covering this and similar completion problems, and Waterman (1975) presents a short program for this task, expressed in condi­ tion/action productions. See also Egan and Greeno (1974). Evans (1968) developed a very capable program for .visual analogies. Hayes-Roth (1976) has developed a program for learning "rules" from before-and-after examples. The empirical program of Hedrick (1976) solves problems in the letter sequence and before-and-after pairs paradigms.

Steven A. Vere

Department of Information Engineering University of Illinois at Chicago Circle Chicago, Illinois 60680

Soloway (1976) is developing a program for learn­ ing the rules of baseball from situation sequences. Nevertheless, it is difficult to find a fundamental theoretical principal common to all theseprograms . However, it will be seen that relational produc­ tion induction does provide a common theoretical core for all four paradigms.

The relational production is a formal model for describing change in discrete relational systems (Vere 1976, 1977a). It is an amalgamation of two familiar concepts : string productions (Post 1943) and STRIPS operators (Fikes et al., 1972). Readers are cautioned not to confuse this model with the linearly ordered condition/action productions studied by Waterman and others . A major advantage of the relational production formulation over related AI "production" systems is that the appli­ cability and effect of these productions can be described mathematically using analytic tools from theorem proving literature. This permits the for­ mal proof of key results.

The relational production model will be informally reviewed in section 2. Section 3 develops the theory of relational production generalization, based on earlier work in concept induction, and discusses the role of background information. Sec­ tion 4 discusses the application of relational production induction to each of the four paradigms together with an example run on the computer implementation.

2. REVIEW OF RELATIONAL PRODUCTIONS

A relational production is a relation revision mechanism, analogous to string productions. String productions specify possible revisions of a string of symbols; relational productions specify possible revisions of a conjunction of literals. In this paper, a literal will be taken to be an ordered list of terms, and a term will be a constant or a variable.

For the purposes of this paper, a relational pro­ duct ion has the form a-+ 8, where a and 8 are con­ junctions of literals. The substrate which a set of productions may revise is called a situation, which is also a conjunction of literals.

To illustrate the structure and application of relational productions, consider a "blocksworld" consisting of a number of cubic blocks of uniform size . Figure 2.1 shows schematically a blocks­

world situation in which there are three blocks.

We will use three types of literals to describe this world:

1. (on .X .Y) means block X rests directly on top of block Y;
2. (ontable .X} means block X rests directly on the table;
3. (clear .X) means the top of block X is clear, i.e., no block rests on X.

The convention is that variables are identified by a period prefix. Otherwise, strings ofletters and digit~ are constants.

Using these literal types, a description of the situation of Figure 2.1 is: (clear a)

(ontable a)

(on c b)

(ontable b)

(clear c)

The following relational production specifies the unstacking of a block: (clear .X) (clear .X) (on .X .Y)-(ontable .X}

In words, this specifies that if a block X is clear and rests on blockY, then the situation may change into one in which X rests on the table and Y is clear. We emphasize that a production is not the same as a predicate calculus implica­ tion, since the literals on the left of the pro­ duction are deleted from the situation. This will be described precisely below.

Of course, a production may not be applicable in a given situation. For example, an unstacking operation cannot occur if no block rests on another. Let a represent a situation and 8 a con­ ventional substitution of the kind used in deduc­ tive theorem proving, and having the form {t1/v1, ... , tr/vr}, where each ti is a term and each vi is a variable. Then production a+ 13 is applicable to situation a iff a 8 <;a. In this relation, the conjunctions a and a are regarded as sets of literals. Thus the unstacking produc­ tion above is applicable to the situation of Figure 2.1 since

To specify the new situation after a production has revised a situation, we will use additional set operators:

Here U and n denote set union and intersection, respectively, and the overbar denotes set comple­ ment. 8 is any substitution which satisfies the applicability relation. In the absence of paren­ theses, intersection takes precedence over union in expressions.

Continuing the example above, if the unstacking production is applied to the situation of Figure 2.1, the new situation is determined as follows:

Thus the production serves to unstack a block. Similar productions can be formulated to transfer a block from one stack to another and to stack blocks. By continuing to apply productions, a situation can be revised repeatedly. The nota­ tion a £> a· will denote that production p trans­ forms situation a into situation a'.

Beyond artificial intelligence applications, rela­ tional productions are also capable of modelling the semantics of computer programs, including list processing and structured data (Vere 1976).

The Context Form for Relational Productions

The antecedent a and consequent 13 of a production may contain common literals. Let y=anl3. This set of common literals y will be called the context of the production. Consideration of the applica­ bility relation a8 <;a and next situation relation a'= ana8 u 138 shows that adding or deleting lit­ erals in the context affects applicability of a production, but not the transformation caused by that production. The context form of a production a + 13 is

For example, the context form of the blocksworld

unstacking production (clear .X) (clear . X)

3. GENERALIZATION OF RELATIONAL PRODUCTIONS

This section develops an analytic, operational theory for the generalization of relational pro­ ductions. First, "generalization" is defined for productions; second, properties of generalizations are reviewed; third, a method for generalizing productions is developed based on an earlier method for generalizing simple conjunctions of literals; fourth, a method is presented for aug­ menting the context of productions with relevant background information using the concept of associ­ ation chains; fifth, the concept of deterministic productions is introduced and defined in terms of association chains.

3.1 Definition and Theorem for Generalization of Relational Productions

Productio Pl is a generalization of productionp2, denoted p1 ::; p2, iff for all situations cr and cr', (cr £~ cr') implies (cr £~ O'). In other words, if p 1 is a generalization of p2, the p1 can cause any transformation caused by P2· and possibly others as well.

Relational Production Generalization Theorem (Vere 1977b). If Pl- ( [ydal + 81) and P2 = C [y2Ja2 + 82) are two relational productions' and ve (Xl en 81 e = !3 and a 2e n 826 = !3, then p1 $ p2 iff there exists a substitution 6a such that Y!6a~Y2, a16a = a2, and and 816a = 82.

3.2 Properties of Generalizations

In this section we briefly review some of the properties of generalizations.

Strict Generalizations. If production Pl is an alphabetic variant of production p 2 , then it fol­ lows immediately from the generalizationdefinition for productions that p1 $ p2. If p1 $ P2 and p1 is not an alphabetic variant of P2· then p1 is a strict generalization of p2, denoted Pl <p2.

Common Generalizations . If p1 $ p2 and p 1 :s: p 3 it is natural to say that p 1 is a common generaliza­ tion of P2 and P3· It is also useful to talk of the common generalization of more than two productions.

Maximal Common Generalizations. Loosely speaking, a maximal common generalization is one which con­ tains all the common features of the productions of which it is a generalization. More precisely, a production p 1 is a maximal common generalization of productions p2 and p3 iff:

1. Pl 5 P2 and Pl 5 p3 (i.e . , it is a common
2. generalization.)
3. nop1' exists suchthatp1<P1'· Pl'$p2, and P1' ~p 3 (i.e., it is maximal.)

As an example, consider the four productions

P4 $ Pl and P4 $ P2. However, P4 is not a maximal common generalization of Pl and P2 because P3 is also a common generalization and P4 < P3· In fact, P3 is a maximal common generalization (meg).

3.3 Computing Maximal Common Generalizations of Productions

In previous work on the generalization of simple conjunctions (Vere 1975), A$ B iff A6~B, and a procedure is presented for computing the meg of two conjunctions. As shown below, in relational production generalization a production may be regarded as an ordered 1 ist of three conjunctions: the context y, the antecedent a, and the conse­ quent 8. Given two productions Pl and P2· their meg's are obtained by computing the meg's of each of their three components. However, generaliza­ tion of the antecedent and consequent are special cases. To see why, consider three productions Pl = {[y!lal + 81}, P2 = { [y2Ja2 + 82}, and P3 = { [Y3]<X3 + 83}. It follows immediately from the theorem and definitions of sections 3.1 and 3.2 that if P3 is an meg of Pl and P2, then Y36a ~ Yl, y36b~Y2, a36a=al, a36b=a2, 836a=81, and 836b = 82 for some substitutions 6a and eb. Thus the contexts Yl and Y2 need not have the same num­ ber of literals, but a1 and a2, and 81 and 82 respectively must have the same number. Conse­ quently a3 must not only be an meg of a1 and a2, but it must also have exactly the same number of literals. The same is true for 83.

The meg of the .antecedents is (at mky .X), and the meg of the consequents is (at mky .Y). However, for both antecedent and consequent these generali­ zations have fewer literals than the antecedent and consequent of P2· Hence no meg of Pl and P2 exists.

In summary, to find the meg of two productions Pl and P2· compute the meg's of their respective com­ ponents. However, if a3 or 83 has fewer literals than the corresponding components of Pl or P2· no meg exists.

The method for two productions is the basis for generalizing n productions, where n> 2. In Vere (1977b) an iterative, bottom-up approach is dis­ cussed. If a conjunctive generalization can be assumed, a "linear" method is faster: given productions Pl· P2· ... , Pn compute mcg(pn,mcg(Pn-1·( ... mcg(p2,Pl) ... ).

3.4 Background Information

In the concept learning paradigm of earlier work, instances of a concept are each described by a con­ junction of literals and these conjunctions are generalized to form an abstraction of the concept. In many cases, both in concept induction and pro­ duction induction, there is a body of information potentially pertinent to the generalization and yet not specifically associated with any particular instance. For simplicity, the following discussion treats only concept induction examples.

Consider the problem of learning poker hands from examples. The two "full house" hands 4 S, 2 H, 4 D, 4 C, 2 C and 10 H, 10 D, J S, J C, J H could be described by the following conjunctions of literals: (card 4 S) (card 2 H) (card 4 D) (card 4 C) (card 2 C) and (card 10 H)(card 10 D)(card J S) (card J C)(card J H). From these we could obtain the generalization: (card .Xl .Yl)(card .Xl .Y2) (card .X2 .Y3)(card .X2 .Y4)(card .X2 .Y5). No information is required beyond that present in the descriptions of the instances. However, to learn the concept of "straight" from the following two hands: 3 H, 4 D, 5 H, 6 D, 7 C and 10 H, J S, Q D, K D, A C requires additional backgroundinfor­ mation on the relative ranking of the cards, e.g., that Queen is just higher than Jack and so on. We use the term background information to refer to a body of facts potentially relevant to a class of generalization problems, but not actually part of the description of any particular instance. It then seems natural to refer to the descriptions of the instances as the foreground information. Here background information might take the form: (next 2 3)(next 3 4) ... (next K A). The problem is to mechanically augment the literals of each instance in the foreground with "relevant" back­ ground literals before generalizing. For example, we would want to add the background literals (next 3 4)(next 4 5)(next 5 6)(next 6 7) to the description of the first "straight" hand shown above. For the second "straight" hand, a differ­ ent subset of background literals are relevant if we are to obtain the generalization: (card .XA .YA) (card .XB .YB)(card .XC .YC)(card .XD .YD) (card .XE .YE)(next . XA .XB)(next .XB .XC) (next .XC .XD) (next .XD .XE). To describe how relevant background literals are selected requires the concepts of associations and association chains.

Two literals L1 and L2 have an association Ai jCL1,L2) iff the ith term of L1 is identical to the jth term of L2. An association chain is a sequence of associations: Ai1,i2(Ll,L2) Ai 3,i4(L2,L3) ··· Ain,in+lCLn-l,Ln) where for even r: ir f ir+l. For example, if L1 = (next 2 3), L2 = (next 3 4), L3 = (next 4 5), and L4 = (odd 3) then A3 2CL1,L2) A3 2CL2,L3) sat­ isfies the definition of'an association chain, but A3 2CL1,L2) A2 2CL2,L4) does not. These two cases ar~ illustrated in Figure 3.1, which shows that an association chain can be viewed as a threading together of literals such that the thread enters through one term and leaves through another.

We are interested in forming association chains in which ·the first and last literals in the chain are foreground literals and the rest are backbround literals. Background literals in such chains will be deemed relevant to the foreground instance to which they are linked. For production induction, these background literals will be added to the con­ text of the production, and generalization will proceed as described earlier in this section.

Let Yf denote the original production context, and Yb denote the relevant background literals. Then the complete context is y = Yb UYf · The examples of section 4 will illustrate this context augmentation.

In practice, a limit must be placed on the length of the association chains which are considered, lest yb become too large. This prevents the com­ putation times from becoming excessive, at the cost of ignoring information potentially relevant to the generalization process . None of the examples of this paper require association chains of more than four literals.

3.5 Deterministic Productions

A relational production whose context has been augmented with background information, [yb,Yf]a+B, is defined to be deterministic iff all variables in B are either:

1. also present in a or Yf, or
2. are linked by association chains through Yb back into a or Yf·

For example, the production

[ ] (at robot . X)---+ (at robot . Y)

i s nondeterministic, since the variable .Y of the consequent does not appear in the antecedent or context. Given a particular present situation to which this production is applicable, .Y is a free variable, and so the new situation obtained by applying the production is not uniquely deter­ mined. However, the following production is deterministic:

[(next .N9 . NlO), null] (string . Nl3 . Nll : Nl2 . N9)--+ (string .Nll .Nl2 .N9 .NlO)

Here Yb = (next .N9 .NlO) and Yf =null. The vari­ ables .Nll, .Nl2, and .N9 all appear in the ante­ cedent. The variable .NlO participates in an association chain through the background context into the antecedent via .N9.

In summary, this definition approximately captures the intuitive idea that if a "deterministic" pro­ duction is applied to a situation, the new situa­ tion should be uniquely determined.

4. APPLICATION OF PRODUCTION INDUCTION WITH BACKGROUND INFORMATION TO FOUR INTELLIGENCE PARADIGMS

This section illustrates the application of pro­ duction induction with background information to four intelligence paradigms : letter sequence com­ pletion, visual analogies, operator induction from before-and-after pairs, and operator induction from a situation sequence. In each paradigm an example is presented which was run on the computer implementation of the theory previously described. This program is designated Thoth-pb, one of a series of induction programs which have been developed. (In Egyptian mythology, Thoth is the god of knowledge and learning.) Thoth-pb consists of about 1,600 executable SNOBOL4 statements.

4.1 Application to the Letter Sequences Paradigm

In the letter sequences paradigm, a sequence of letters is presented, such as ABMCDMEFMG, and the problem is to predict the next letter in the sequence. For this paradigm, the background information is the ordering of the letters of the alphabet: (next A B)(next B C) ... (next Y Z). In common with Waterman (1975), we assume the sequence has a fixed "period" i, i.e., any letter in the sequence is a function of the previous i symbols. This assumption is not valid for sequences such as ABBCCCDDDD .... Suppose we assume the period is 2 (actually it is 3). We could then construct the following set of productions:

Augmenting the context with background literals using a maximum chain length of four gives:

Generalizing these productions gives:

[(next .Nl .N2) ,null] (string .N5 .N6)-+(string .N3 .N4)

which is nondeterministic, as previously defined. Thus the period cannot be 2. Thoth-pb initially assumes the period is 1, constructing the productions:

It then augments these productions with background literals and generalizes. If the result is not deterministic, it increases i by one and tries again, and so on, until either a deterministic generalization is found, or the period i becomes so large that two productions cannot be con­ structed. (Thoth-pb requires at least two produc­ tions to generalize.) For this example, for i = 3, the program computed the following deterministic generalization: ·

The total execution time was 11 seconds. To pre­ dict the next letter, we can match the left side of the pro~uction to the right end of ABMCDMEFMG using the substitution 8 = {E/ .N3,F/ .N4,G/ .Nl,H/ .N2} The next letter is thus H, since .N2 follows .Nl in the production. Thoth-pb only computes the generalization, without actually using it to prediet the next letter; this is a simple clerical task. Thoth-pb has successfully solved all 15 problems in Simon and Kotovsky (1963) .

4.2 Application to Visual Analogies

It seems significant that the same production induction process can be used in a problem class which, to the present time, has been regarded as distinct: the familiar visual analogy problems studied by Evans (1968). One such problem is shown in Figure 4.1. Using the analytic concepts of this paper, it is possible to give a formal representation and solution for such problems.

To begin, each scene must be translated into a conjunction of literals. This translation is a significant problem in itself, but not an induc­ tion problem. For example, scene B is translated into the coniunction: (ISA P3 TRIANGLE) (ISA P5 DOT)CISA P4 SQUARE)(ABOVE P3 P4)(IN P5 P4). The end result of this translation, here performed manually, is a set of eight conjunctions sA, sB, sc, s1, ... , s5. From these Thoth-pb constructs the following six relational productions: SA -+ SB and sc -+ si 1 $ i S 5. The maximal common general­ izations are computed for each of the following five pairs of productions:

gi = mcg(sA -+ SB, sc -+ si) 1 $ i $ 5. Scene ib is the "best" answer iff gi < gib for all i -; ib. This example does not require background information, although more complex analogies may require back­ ground information for selection of the best answer.

For g1 and g3, Thoth-pb ization exists; g2, g4, reported that no general­ and g 5 are shown below.

Applying the generalization theorem of section 3 the program observes that g2 < g4 and g5 < g4. Con­ sequently scene 4 is chosen as best answer. Total execution time was 11 seconds.

4.3 Application to the Before-and-After Pairs Paradigm

In the before-and-after pairs paradigm, pairs of situations are presented which describe a system both before and after an action has occurred. More than one action may be exemplified. Option­ ally, "nonpairs" may also be presented, in which the transformation between the two situations was not caused by one of the actions.

Each before-and-after pair (ab,aa) may be viewed as a single relational production ab + aa . The new situation equation from section 2, a· = an ae u 88, shows that this production exactly accomplishes the transformation from the first situation to the second. Consequently, a set of such pairs may be treated as a set of productions, which may then be augmented with background infor­ mation and generalized as in section 3. General­ ized productions which are "inconsistent" (Vere 1975) with counterexample productions are auto­ matically discarded.

As an example, consider Figure 4.2 in which the arrows indicate legal and illegal white pawn moves in chess. The background information for this problem consists of the relative positions of the squares on a chess board, here labelled sl through s64, plus information on the squares which form the bottom row for white and for black. This information totals 128 literals. Literals such as (E Sl S2), i.e., east of Sl is S2, specify the horizontal position of the squares. Literals such as (S Sl S9), i.e., south of Sl is S9, specify the vertical position of the squares. Literals such as (WBR S57) and (BBR Sl), i.e., S57 is in the white bottom row and Sl is in the black bottom row, specify the bottom rows for white and black. The position of the pawn before and after a move is foreground information. For example, the move from square S49 to S33 is represented by the situ­ ation pair: (WP S49), (WP S33) . Here the ''WP" literals indicate the position of a white pawn. Nonpairs are represented in the same way. This problem consists of seven pairs and seven "nonpairs". Thoth-pb computed the following generalizations in 100 seconds:

the White Pawn's Move in Chess

The first production describes the standard "one square north" move by a white pawn. The second production describes a "two squares north" move, which is possible only when the pawn is in its initial position, located one square above the white bottom row.

If Thoth-pb is given only the seven legal move pairs, without counterexamples, it overgeneralizes, obtaining the following conjunctive generalizations:

Both productions cover all seven before-and-after pairs, but they are nondeterministic, as defined in section 3.5. By requesting Thoth-pb to ignore nondeterministic generalizations, we can obtain (in 84 seconds) the two correct, disjunctive generalizations seen above without providing any counterexamples.

4.4 Application to the Situation Sequence Paradigm

The situation sequence paradigm is closely related to the before-and-after pairs paradigm. A sequence of situations is presented, describing successive "snapshots" of a discrete system undergoing change. The problem is to find a minimal set of produc­ tions, one of which is capable of causing the transformation between any pair of adjacent situa­ tions in the sequence.

Figure 4.3 shows a sequence of six situations in the familiar Tower of Hanoi puzzle. Each scene will be represented using "on" and "clear" literals, as in section 2. The elements involved are the three discs A, B, C and the three pegs Pl, P2, P3. For example, the second scene is repre­ sented by the following conjunctions: (clear C) (on C Pl)(clear A)(on A B)(on B P2)(clear P3) . The background information for this problem con­ sists of literals giving the relative sizes of the elements: (L B A)(L C A)(L C B)(L Pl A)(L Pl B)

(L Pl C)(L P2 A)(L P2 B)(L P2 C)(L P3 A)(L P3 B) (L P3 C). Here (LX Y) may be interpreted as "X is larger than Y". For example, the literal (L P2 A) may be interpreted as "the base of P2 is larger than A".

From the six conjunctions describing the scenes, Thoth-pb constructs five productions from the adjacent pairs of descriptions, and then augments the context of each pro~uction with relevant back­ ground information. For example, from the first two descriptions is constructed the production:

The following conjunctive generalization of the five productions was obtained in 36 seconds:

This generalization corresponds closely to our intuitive idea of the Tower of Hanoi operator, except for the last three literals of the fore­ ground context, which reflect an idiosyncrasy of this sequence: in every case when a move occurred, there happened to be an .N8 clear, an .N6 on an .N7 and an . . N4 on an .N5. Note that none of these variables have associations to the production antecedent or consequent. Such "noise" literals could be screened out by checking this property. Alternatively, we could show an additional sequence involving just one disc to break the idiosyncrasy.

5. CONCLUSION

Relational production induction has been shown to be a common process in four distinct intelligence paradigms, which suggests that it may be a basic principal of inductive inference. The examples of section 4 all require only modest computation times, and are far from being upper bounds on the difficulty of problems solvable by these methods. In induction, as in problem solving and computa­ tion in general, the style of representation of information influences the form and difficulty of solutions. This paper has assumed error free data: "noisy" data presents a topic for future work. The background information concept could be generalized by allowing the literals to be dynamically inferred, instead of requiring them to be stored explicitly.