An Explanation-based Approach to Generalizing Number

I

AN EXPLANATION-BASED APPROACH TO GENERALIZING NUMBER *

Jude W. Shavlik 1 Gerald F. DeJong

Coordinatrd Scirncr Laboratory Uni\·rrsity of Illinois Urbana, IL 61801 USA

details. However. extensive augmentation of the explanation can be often required to produce the appropriate concept.

Many important concepts require generalizing number. For example. physical laws such as momentum and energy conservation apply to arbitrary numbers of objects. building blocks-world towers requires an arbitrary number of repeated stacking actions. and setting a table involves an arbitrary number of guests. This paper presents an explanation-based approach to the problem of ··generalizing toN ...

U AN APPROACH

Observations of repeated application of a rule or operator may indicate that generalizing the number of rules in the explanation may be appropriate. However. alone this is insufficient. To be conducive to number generalization there must be a certain recursive structural pattern. That is. each application must achieve preconditions for the next. For example. consider stacking blocks. The same sort of repositioning of blocks occurs repeatedly. each building on the last. We adopt the vocabulary ·or predicate calculus to investigate this notion of structural recursion. The desired form of structural recursion is manifested as repeated application of an inference rule in such a manner that a portion of each consequent is used to satisfy some of the antecedents of the next application. Figure 1 illustrate.s the concept of repeated rule application.

Consider inference rule 1. Notice that the consequent of this inference rule can be used to partially satisfy the antecedents of another application of the rule (via the predicate

ABSTRACT

An approach to generalizing number in explanation-based learning is presented. Generalizing number can involve generalizing such things as the number of entities involved in a concept or the number of times some action is performed. This issur has been largely ignored in previous explanation-based learning research. Instead. other research has focused on changing constants into variables and determining the genrral constraints on those variablrs. In the approach presented, gelleralization to N is triggrred by thr detection of inference rules of a specified syntactic form. When one is found, it is extended into the rule that results from an arbitrary number of repeated applications of the original rulr. If the preconditions of the extended rule are met, the rrsults of multiple applications of thr original rule are immediately drtrrmined. Thrre is no need to apply the underlying rule successively, each time checking if the preconditions for the next application are satisfied.

I INTRODUCTION

This paper addresses the important issue in explanatio'n­ based learning of generalizing number. Generalizing number can involve generalizing such things as the number of entities involved in a concept or the number of times some action is performed. This issue has been largely ignored in previous explanation-based learning research. Instead. other research has focused on changing constants into variables and determining the general constraints on those variables.

Consider the LEAP system [1]. The system is shown an example of using NOR gates to compute the boolean AND of two OR's. It discovers that the technique generalizes to computing the boolean AND of any two inverted boolean functions. However . LEAP cannot generalize this technique to allow constructing the AND of an arbitrary number of inverted boolean functions using a multi-input NOR gate. This is the case even if LEAP's initial background knowledge were to include the general version of DeMorgan's Law and the concept of multi-input NOR gates. Generalizing the number of functions requires alteration of the original example's explanation. This generalization cannot be performed using their goal regression algorithm alone.

Ellman's system [2] also illustrates the need for generalizing number. From an example of a four-bit circular shift register. his system constructs a generalized design for an arbitrary four-bit permutation register. A design for an N-bit circular shift register cannot be produced. As Ellman points out. such generalization, though desirable. cannot be done using the technique of changing constants to variables.

Many other explanation-based generalization algorithms [3-6] also cannot alter the structure of their explanations. No additional objects nor inference rules can be incorporated into the explanation. These algorithms work by changing constants in the observed example to variables with constraints. Another algorithm [7] allows for the elimination of easily-reconstructed P). as illustrated in figure 1. The antecedents ~f this rule involve three qualitatively different types of vanables. (The differences between the three types will become clear when the extended version of this rule is described.) Predicate P involves all three types of variables, while predicat~ R speci_fies a necessary relationship between the (i-l)th and uh collection of x 's.' Predicate S constrains the (i-1 )th collection of x 's and predicate T constrains the ith collection. Lastly. the ith collection of y 's are partially defined by terms in the (i-1 )th application.

· This research was partially supported by the National Science Foundation unrler grant NSF 1ST 85-11542.

1 University of Illinois Cognitive Science/ Artificial Intelligence Fellow.

Chaining together several applications of rule 1 produces rule le.

In this extended inference rule all references to the Y; .j for i >0 are eliminated and the z 9 terms remain unchanged from one application of the original rule to the next. Hence. besides the initial situation. all that needs to be !ipecified for an arbitrary number of applications of rule 1 is a sequence of X; .j terms. The predicates R. S. and T place constraints on possib!e seq~ences of x 's. In particular. the predicates Sand T constratn wh1ch terms can be members of the sequence. while predicate R specifies the relationship between successive members of the sequence.

The general form of a sequence is shown below. It consists of an ordered collection of p-ary vectors.

m SOME EXAMPLES

Two simple examples that concretely illustrate the above procedure are presented below.

A. Blocks World

Imagine an explanation-based learning system that deals with the blocks world. Assume that in the course of its operation this system has to determine the position of the top of block which is resting on a table. Also assume that in the course of doing this it produces an explanation structure that can be transformed into rule 2 below. (Figure 2 illustrates this rule.) This rule is in a form that matches rule 1. Rule 2e is the extended form of rule 2. On these rules. all terms beginning with a ? are univ~rsally quantified variables.)

· Although not done here for reasons of clarity, the approach presented can be extended to situations where there are relations among the (i-k).J. through the ith collections.

Yposl! lon; -J;1

In rule 2e the sequence is made explicit. For all consecutive pairs of sequence elements. the first must be on the second. In addition. the function +' is introduced. This recursive function has two arguments: a sequence of numbers and a "seed" number. It maps these into a single number - the sum of all the numbers. The function derived-sequence takes a sequence and a unary function and maps them into another sequence - the one which results from applying the function to each member of the original sequence.

The extended rule can be used to find the y -position of a block supported by several other blocks when the y -positions of the underlying blocks are not directly known. All that needs to be known is the heights of each block and the y-position of the table top (or the y -position of one intervening block). In this case the extended rule is obtained from an example that involved 1111 repeated actions nor structures.

An important task for a system that generalizes number is to loosen the preconditions of a r-ule as far as possible while still maintaining the veracity of the rule. Also. as much guidance as possible should be provided so that a problem solver can most easily determine when a rule is both applicable and appropriate.

Imagine using rule 2e in a backward-chaining fashion. If a problem solver is to find the y -position of an object it needs to choose a sequence that satisfies the specified constraints. This task is simplied if the preconditions are specified in terms of sets or bags'. rather than sequences. In this case. there is no need to test each permutation of a given collection of elements. If a bag satisfies the rule's preconditions. then any sequence derived from that bag suffices. Other derivable properties, such as the cardinality of the bag or the length of the sequence. might also usefully constrain a problem solver.

One case where it is easy to specify the preconditions in baj terms occurs when there are no inter-element constraints (i.e), : predicate R in rule 1 is not used). If an inter-element predicate does appear in the preconditions. the properties of that predicate determine how loosely the preconditions can be expressed. For example. if R is an equivalence relation (that is, R is reflexive, symmetric. and transitive), then the elements must form an equivalence cl4ss, a property that is order independent.

In the above example. R is (the a transitive version of) On. In bag terms. rule 2e requires a collection of elements where. (i) except for one element (object 0 ). every element is on one and only one other element. (ii) except for possibly one element (?object, ), every element has one and only one element on it. and (iii) the sum of the heights of all elements other than object 0 plus the y -position of object 0 equals ?y, . If a bag with these properties is obtained. the necessary sequence can easily be constructed.

· A bag (or multi-set) is an unordered collection of elements in which an element can occur more than once.

B. Digital Circuit Design

The second example involves a simplified version of circuit design . Figure 3 shows two flip-flops. When the clock is pulsed. the input of a flip--flop is passed to its output. provided its select line is on. Assume that from observing the connection of two flip-flops. a learning system derives rule 3. That is. it determines

that if two flip-flops are connected together and the select line of the first is on. after the next clock pulse the current output of the first flip-flop becomes the second's output. Rule 3 is also of the form of rule I. The extended form of rule 3 is rule 3e. (Notice that all of the select lines are required to be on.) In constructing this rule. knowledge about repeated incrementing is used to define ?y, in terms of the number of flip-flops connected. The new rule can be used to build such things as a delay line and can lead to the concept of an N -bit shift register.

IV RELATED WORK

Several other approaches to generalizing number have been recently proposed. Prieditis [8) has outlined plans for a system which learns macro-operators representing sequences of repeated STRIPS-like operators. While we agree very much with the spirit of Prieditis' work. we feel that STRIPS-like operators impose unwarranted restrictions. For one thing. our use of predicate calculus allows generalization of repeated structure and repeated actions in a uniform manner. In the FERMI system [9). cyclic patterns are recognized using empirical methods and the detected repeated pattern is generalized using explanation­ based learning techniques. However. unlike the techniques presented in this paper. the rules acquired by FERMI are not guaranteed to always work. After a significant amount of work. a learned problem-solving strategy may terminate unsuccessfully. A third system. Physics 101 [10. 11). differs from the above two approaches in that the need for augmenting explanation structures is motivated by an analytic justification of an example's solution and general domain knowledge. In a sample problem. information about number. localized in a single physics formula. leads to a global restructuring of a specific solution's explanation. However. Physics 101 takes advantage of properties of mathematical calculations. To be a broad solution of the generalization to N problem. non mathematically-based domains must also be handled.

V CONCLUSION

Most research in explanation-based learning involves relaxing constraints on the entities in a situation. rather than generalizing the number of entities themselves. This paper presents an approach to generalizing to N i·n explanation-based learning. Generalization is triggered by the detection of rules of a certain syntactic form (i .e .. rule 1 ). and a technique for extending these rules is presented. The extended versions are modified so that a problem solver can efficiently apply them. This involves attempting to expression the preconditions for these rules in terms of order-independent data structures such as sets and bags. If the preconditions of the extended rule are met. the results of multiple applications of the underlying rule are immediately determined. There is no need to apply the rule successively. each time checking if the preconditions for the next application are satisfied.

A first computer implementation of the ideas presented here has been developed. The BAGGER system [12) analyzes explanation structures and attempts to construct inference rules of the form of rule I. When one is found. it is extended into the rule that results from an arbitrary number of repeated applications ·or the original rule. This system is being tested on problems from various domains. including the blocks world. digital circuit design. and mathematical problem solving.