A Comparison of Analytic and Experimental Goal Regression for Machine Learning

I. Introduction

Goal regression was first used in AI by Waldinger [ W ALD 7 7] as a technique for detecting and analyzing goal interactions during planning. Given a goal state G and an operator 0 P, a goal regression product is a description of a sub-goal state S, such that 0 P applied to S achieves G. The goal regression product corresponds to Dijkstra's notion of weakest pre-condition [ D IJK 7 5]. According to Dijkstra, wp(OP,G) is the weakest constraint on a stateS which guarantees that the application of OP to S yields a state satisfying G.***

Recent research in machine learning demonstrates the use of goal regression to improve concept acquisition. In particular, this research focusses on techniques for learn­ ing problem solving heuristics. Given an operator se­ quence for . a problem solution, goal regression serves to back-propagate constraints through the sequence to form heuristics for the individual operators. This technique in­ volves formal reasoning with operator semantics and will be called analytic goal regression.

This paper is a critical review of the research on an­ alytic goal regression and suggests a change in direction. Section 2 briefly reviews this research. Section 3 discusses the applicability conditions for successful application of an­ alytic goal regression to machine learning. These condi­ tions appear to restrict the use of analytic goal regression to a relatively small class of problem domains. Section 4 introduces experimental goal regression as an alternative to the analytic technique. Experimental goal regression uses induction from examples to approximate the "cor­ rect" result. This removes the constraining applicability conditions and permits goal regression in a wide class of problem domains. Section 5 compares analytic and exper­ imental goal regression.

· Support for this research was provided by the Army Research Office, under grant number ARO DAAG29-84-K-0060.

** Partial support for this research was provided by Hughes AI Research Center, Calabasas, CA.

*** In computer programs OP is a sequence of program statements.

II. Review of Research

Utgoff [UTG083] demonstrates the use of goal regres­ sion to adjust the bias inherent in the concept hierarchy trees used in LEX [MITC78]. Partial state descriptions are regressed through a solution path to form a composite con­ straint on initial states in the path. Motivating this work is the observation that the state description vocabulary should be rich enough to describe composite constraints. Typically, this vocabulary is a priori domain knowledge. The significance of Utgoff's use of goal regression is that the vocabulary can be dynamically enriched during the learning process.

Porter and Kibler [PORT84A] use an empirical vari­ ant of goal regression to improve the rate of learning prob­ lem solving heuristics. Their method of episodic learning discovers useful operator sequences [KIBL83B]. The learn­ ing is incremental and heuristics which recommend oper­ ators applied near the goal state are learned first. These heuristics are regressed through the episode to learn addi­ tional heuristic rules. The significance of this use of goal regression is that the rate of episodic learning can be dra­ matically improved by broadcasting the refinement of one heuristic through an episode to enable the refinement of other heuristics.

Minton [MINT84] demonstrates the power and po­ tential of goal regression by showing effective learning from a single training instance. With a technique called con­ straint based generalization, state descriptions are gener­ alized by deducing why the training instance is classified as positive. The technique is applied to learning general­ ized state descriptions for forced wins in two-person games. Given a chain of actions resulting in a forced win, goal regression is used to back-propagate the important descrip­ tors of the forced win state. The goal regression product is a description of the set of states for which the chain of actions achieves the forced win. The significance of this use of goal regression is that (a limited form of) "one­ shot" learning is possible by reasoning with explicit goal descriptions.

Ill. Applicability Conditions for Analytic Goal Regression This section defines two applicability conditions for effective use of analytic goal regression.

A. Invertible Operators

The first applicability condition requires that the do­ main operators be invertible. Given a STRIPS-like declar­ ative operator definition, inverses are easily computed by reversing the roles of the delete-list and add-list. However, procedural representations are more flexible and powerful for defining operator transformations [HEWI72, McDE72]. Unfortunately, analytically inverting a procedurally de­ fined operator appears impossible in general. A similar problem occurs if the goal description is defined procedu­ rally.

LEX-II [MITC83] partially circumvents this problem by providing the learning element with operator inverses. Both the domain operators and their inverses are repre­ sented procedurally. As Utgoff discovered [UTG083], the chief shortcoming of this approach is the inability to rea­ son with some operator definitions. For example, consider the substitution operator in symbolic integration which re­ places a sub-expression of an integral with a variable. In LEX, this operator is defined as:

where poly{f(x)) stands for a polynomial in x. The prob­ lem discovered by Utgoff is that analytic goal regression with this operator definition fails. The critical constraint that whatever matches f' be the derivative of whatever matches f is not explicit in this operator representation. This constraint is embedded in an opaque representation of the operator. Procedural representations can conceal es­ sential operator constraints and prevent the analytic com­ putation of goal regression products.

B. Relative Closure of Representation Language

The second applicability condition for analytic goal regression requires that the representation language ade­ quately express goal regression products. As we demon­ strate, analytic goal regression can produce state descrip­ tions which are unrepresentable in the language used for forward reasoning. In particular this constraint is not sat­ isfied by merely assuming that one has a STRIPS-like rep­ resentation.

There is no problem with computing a goal regression product if the goal and the operator are fully instantiated. However, regressing expressions through partially instantiated operator definitions can be troublesome [NILS80, pp 288-292]. Consider the operator unstack(x,y) defined with the following STRIPS rule:

Pre and Delete conditions: handempty, clear(x), on(x, y) Add conditions: holding(x), clear(y)

The regression of the partial state description clear( C) (for some constant C) yields the disjunction (y = C) V clear( C). External disjunction is often precluded from concept de­ scription languages [MICH83] but co=only occurs in an­ alytic goal regression products.

While a disjunctive clause might be split into sepa­ rate clauses, thereby eliminating the disjunction, negated clauses can also be troublesome. For example, the re­ gression of clear(C) through unstack(x,B) yields ·(x = C) 1\ clear( C). These examples demonstrate that the con­ cept description languages must support disjunction and negation if analytic goal regression is used.

The problem of representation language closure arises in Minton's research [MINT84]. As described in section 2, Minton applies goal regression to learn forced move board positions in two person games. In particular, consider Minton's example in the game gomoku. Gomoku is similar to tic-tac-toe except the board is a 19x19 grid and the object is to get 5 X's or O's in a row. An open four­ position for X is four X's in a row with an adjacent blank position. An open three-position for X is three X's in a row with two blank positions on one side and one blank position on the other.

We believe that the description language cannot rep­ resent all goal regression products in this domain. The de­ scription language for board positions is a conjunct of pred­ icates. Minton computes the goal regression product of an open four-position as an open three-position. Assuming the natural gomoku move operator definition:

the open three-position is only a subset of the correctly computed goal regression product. An open four can also result from applying the move operator to a

position. Therefore, the correct goal regression product is a disjunctive clause which is outside the expressive power of the description language. This problem might be ad­ dressed by extending the description language to include terms which correspond to disjunctive expressions in the original language. But, discovering appropriate shifts in representation language may be more difficult than the problem being addressed.

We believe that these applicability conditions restrict the use of analytic goal regression to a relatively uninter­ esting set of problem domains. In addition to these neces­ sary limitations, there is an additional pragmatic concern.

The technique forms totally precise rules which may not capture the data at hand. Analytic goal regression could be used in the total absence of experience and might be called learning by reasoning or "no-shot" learning.

The next section proposes an alternative which ap­ proximates the results of analytic goal regression but relies on experience, rather than reasoning.

IV. Experimental Goal Regression

Experimental goal regression is an alternative to an­ alytic goal regression in which the applicable conditions are eliminated. The technique yields an approximation of the result of analytic goal regression. This approximation is incrementally refined using standard machine learning techniques.

Experimental goal regression uses induction to ap­ proximate a goal regression product. Consider states s1, s2, ... , s,. in the domain search space which are mapped by operator OP into a state satisfying the goal G. Experi­ mental goal regression applies standard induction tech­ niques to s1, s2, ... , s,. to form a partial description of the regression of G through OP.

Experimental goal regression avoides the limitations of analytic goal regression discussed in the previous sec­ tion. First, the technique does not preclude procedural operator representations since OP is not inverted. Second, goals can be represented procedurally since experimen­ tal goal regression uses them only as boolean predicates on state descriptions. Third, experimental goal regres­ sion does not require the language to be complete with respect to goal regression products. Only a useful par­ tial characterization of the inverse is generated instead of a completely accurate one as in the case of analytic goal regression.

The practical success of experimental goal regression relies on an efficient construction of multiple examples of goal regression products. One approach to example gener­ ation is perturbation [KIBL83A], which relies on inherent regularity and continuity in the search space [LENA83]. Given a single example, perturbation automatically gen­ erates and classifies neighboring examples. The selection of the most promising neighbors can be guided with some knowledge of the transformation performed by the opera­ tor. Relational operator models [PORT84B] are one tech­ nique for approximating operator definitions.

V. An Example

The following example compares analytic and exper­ imental goal regression for learning search heuristics. The task is the algebraic simplification of a pair of simultaneous linear equations labelled a and b. The operator sub( a, b) replaces equation b with the result of subtracting equation a from equation b. Similarly, sub(b, a) replaces equation a with the result of subtracting equation b from equation a. For simplicity we assume that the sub operators are only applicable when the equations have equal x-coefficients. These operators can be defined as:

As with other systems for learning search heuristics [LANG83, 0HLS82], the learning element uses a static eval­ uation function for credit assignment. Since the overall problem solving goal is to simplify the equations, the func­ tion counts the number of non-zero terms in the equations.

Let us examine how analytic goal regression would learn heuristics for the sub operator. Consider the follow­ ing positive training instance for the operator sub( a, b):

Analytic goal regression produces the heuristic rule:

This goal regression product is accurate with respect to the operator definition but fails to incorporate the guid­ ance of the static evaluation function. The heuristic rule erroneously recommends sub( a, b) in the state:

The resulting state is:

The static evaluation function reveals that sub( a, b) is not effective in reducing the number of nonzero terms in the example.

Experimental goal regression induces a goal regres­ sion product from positive examples. The representation of both the sub operators and the static evaluation func­ tion are irrelevant to the success of experimental goal re­ gression. Examples of effective applications of sub( a, b) are generated (perhaps by perturbation of a given example) and classified as positive or negative by the static evalua­ tion function. Induction over the set of positive examples using the climbing hierarchy tree generalization operator yields the heuristic rule:

where nonzero and integer are typed variables.

A goal regression product, derived experimentally, in­ corporates the pragmatic preconditions for effective use of each operator. In the example above, pragmatic precondi­ tions for sub( a, b) require that both the y-coeffi.cient and the constant term in equation b be non-zero. Pragmatic preconditions are enforced by constraints external to the operator definition. Therefore, they cannot be discovered by analytic goal regression.

We believe that combinations of analytic and exper­ imental goal regression might be more promising than ei­ ther technique alone. For example, a combination of tech­ niques might mitigate the following problems:

• Analytic goal regression relies on extending the representation language to precisely describe goal regression products (section IIIB).
• Experimental goal regression relies on efficiently generating a set of state descriptions (section IV).

Using a combination of the two techniques, the goal regression product computed by analytic goal regression might be used to constrain the generation of state descrip­ tions used in experimental goal regression. An analytic goal regression product that can be approximated in the representation language can be used as a "seed" for state description generation. The combination of analytic and experimental goal regression is a topic of future research.

VI. Conclusions

Goal regression promises to be a powerful technique in learning about actions. Predominantly, analytic goal regression has been explored. Analytic goal regression is a powerful reasoning technique for "no-shot" learning. That is, learning could proceed given only the definition of the goals and operators. Unfortunately, the necessity to invert operator definitions and to stay within the representation language severely limits the applicability of analytic goal regression. Experimental goal regression is an alternative to the analytic technique which relies on proven machine learning algorithms to approximate the results of analytic goal regression. Coupled with automatic example genera­ tion, experimental goal regression is an effective machine learning technique that does not suffer from the limitations of analytic goal regression.