A Task-Independent Experience-Gathering Scheme for a Problem Solver

Introduction

It is not at all clear how a problem-solver should improve its performance as it solves, or fails to solve, the problems presented to it. It is clear, however, that such improvement is neces­ sary if problem-solvers are ever to compete suc­ cessfully with human beings. Moreover, the im­ provement cannot be restricted to rote learning of results; what is needed is some equivalent of a human being's ability to detect analogies betwee~ problems. This paper outlines one scheme that has been implemented and tested fairly extensively. Although details are given for a particular problem-solving system, the general philosophy is applicable to most depth-first problem-solvers.

A problem, in this context, is a triple con­ sisting of a state, a goal and a set of opeTators. A state is some object: a well-formed formula, a pattern or somesuch. A goal describes some hypo­ thetical state or set of states. Each operator maps some set of states into another set. A solution to a problem is a sequence of operators that maps the given state into another state that matches the goal. For example, a state could be an algebraic expression, a goal another algebraic expression, and the operators rules for changing expressions into equivalent expressions. A solu­ tion would then be a schoolboy-type demonstration that the state and goal expressions are equiv­ alent. This definition of problems and solutions clearly includes heuristic search problems.l

Figure 1 shows a partial outline of a depth­ first method for finding solutions to such prob­ lems. For any (sub)problem (s,g,R) a set A of operators is selected, one or more of which may hopefully lead to a solution. Each of the oper­ ators is ·tried until one leads to a solution or the set is exhausted. Many essential mechanisms have been omitted from this skeleton, principally how the set of operators is selected, what new problem is tried when an operator is chosen, and what happens when a subproblem is solved. These vary from system to system, and, while they are critical to the performance of any system, the experience-gathering scheme is independent of their form.

Given a problem (state a,goal g,operators R) proceed as follows:

1. If s matches the description g, report suc­ cess on this problem. Otherwise, select a subset A of R; these are the operators to be tried.
2. If A is empty, report failure on this problem. Otherwise, choose an operator x in A and delete x from A.
3. Attempt a new problem based on the current problem and operator x. If failure is reported on this new problem return to step 2.

Figure 1. Skeleton of depth-first problem-solver.

Such a problem-solving schema could make use of 'experience' in a number of ways. ,The two ob­ vious ones are to guide the selection of the set A of operators to try, and to choose which oper­ ator x in A to try next. The selection of the set A, however, is typically performed by some algo­ rithm which is not sufficiently flexible to allow modification by experience.l,3 The scheme given here is based on the second alternative. Each operator x in A will be assigned a weight, deter­ mined from past experience, which represents an estimate of how likely it is that trying x will lead to a solution of the problem (s,g,R). When choosing an operator from A, the one with the highest weight will be tried first.

The first question is, where is this weight to come from? We would like to have weights asso­ ciated with operators in the context of problems. In any interesting task environment, the operator and problem spaces are large, if not infinite; it is clearly impractical to associate a weight with every possible operator-problem pair. The way out adopted here is to categorize operator-problem pairs, and associate a weight with each class. The weight assigned above to x will then be the weight associated with the class into which the pair (x,(s,g,R)) falls. Whenever a problem is solved, the table of weights associated with the classes will be adjusted in an attempt to correct any mistakes in the order operators were tried.

The critical factor here is the classific­ ation of the pair (x, (s,g,R)), One reasonable approach would be to look at how easy it would be to apply x to s (i.e., to get the state into the domain of the operator), and how much the use of x would advance s towards g. Suppose we had a measure Q(y,z) of the 'similarity' of state y to goal z, and that this measure took on one of n possible values. Then the approach would classify (x, (s,g, R)) by examining Q(s, 'x should be applicable ') and Q(x(s),g)*. In fact, the simplest such categorization is used; two operator-problem pairs fall into the same class iff each of the above similarities is the same for both pairs.

The next section is an amplification of the above for the Fortran Deductive System (FDS).3,4,5 For this system it is possible to develop a task­ independent similarity measure, and thus a task­ independent classification s~heme.

A More Detailed Look

At this point it becomes necessary to discuss some details of FDS so that a more complete treat­ ment of the experience-gathering scheme for this system can be given.

States are represented as trees with a symbol at each node, where a symbol is a binary or unary connective, free variable or constant. Each pos­ sible node position on such a tree is numbered as follows: the root of the tree is numbered 0, and the right and left successors of node n are num­ bered 2n+l, 2n+2 respectively. Figure 2 shows two states with the number of each node in parentheses beside the symbol**·

Goals ar e represented as strings of condit­ ions , each of which is of t he form 'node n should be the symbol q' or 'the subtree whose root is node n should be identical to the subtree whose root is node m'. Each of the above is called a condition on node n.

*s may not be in the domain of x. In this case an estimate of x(s) is used.

**For the examples given in this section, the not­ ation of elementary algebra will be used.

Rewriting rules take the form y :=z , where y and z are states. A rewriting rule informs the system that any instance of y can be mapped into the corresponding instance of z . Each rewriting rule defines an infinite number of operators of the form 'use rule number m to rewrite the subtree whose root is node n' for any non-negative n . The above operator will be written O[m, n].

The domain of an operator O[i,j] can be des­ cribed by a goal G[i, j ] as illustrated in figure 3. First, a rewriting rule (number i, say) is

Rewriting rule number i

Goal G[i,2] node 2 should be the symbol '-', node 6 should be the symbol '+', subtree whose root is node 13 should be identical to subtree whose root is node 5.

Operator O[i,2] rewrites the first state of figure 2 to the state

given, then the goal which is satisfied by a state iff that state lies in the domain of O[i,2]. The first states in figure 2 satisfies G[i,2]; the state O[i,2](s) into which O[i,2] maps sis shown.

Let s be a state, g a goal. A condition (on a node m) in g is satisfied by s if

i. s satisfies all conditions in g on nodes from which node m is descended, and

ii . s has the property required by the condition.

For example, consider the second state of figure 2 and the goal G[i,2] of figure 3. The first con­ dition is satisfied, since there are no conditions on antecedents of node 2 and the symbol at node 2 is '-'. The second condition is not satisfied, for although i above is true, node 6 is not the symbol '+'. Finally, the third condition is not satisfied, even though the subtree whose root is node 13 is identical to the substate whose root is node 5. Requirement i above is not met, since the second condition is not satisfied and node 13 is a descendant of node 6.

The definition of states, goals and operators in this section is more restrictive than the cor­ responding concepts presented in the introduction; within this limited framework we can define a r easonable function Q(s, g) to measure the similar­ ity of state s to goal g. Actually, the word 'measure ' is too strong; all that is needed for the purpose of classification is to know whether Q(a, b) and Q(c, d) are equal, i.e., whether the two s tates are equally similar to their respective goals. Such an indicator is much easier to devel­ op than a true measure.

if We could say that Q(a,b) and Q{c, d) are equal

• i . goals b and d have the same number of con­ ditions, and
• ii . the number of conditions of b satisfied by a is the same as the number of conditions of d satisfied by c.

This does not fit the description of similarity given in the introduction, since there is an in­ finite number of possible values of Q(s,g). Due t o the way FDS is set up, however, goals with more than five conditions are rare. Taking account of this, requirement i is relaxed to allow goals with similar numbers of conditions to be lumped to­ gether, and ii is changed to specify roughly equal proportions of conditions satisfied. Let x be the number of conditions in g, n the number of these satisfied by s , and y the ratio n/x. Values 1 through 20 are assigned to Q(s,g) as shown in table 1. Note that these values are to be used

only to establish equal similarity; if Q(a, b) is greater than Q{c, d) it does not follow that a is more similar to b than c is to d.

Suppose now that the 20X20 classes of operator-problem pairs are numbered 1 through 400. Two pairs are to fall in the same class iff their states are equally similar to the goals of apply­ ing the operators, and the resulting states are equally similar to the problem goals. Putting this another way, the operator-problem pair (O [i , j ], (s ,g,R)) falls in class

20X(Q(s , G[i , j ])-l)+Q(O[i , j ] {s), g)

where, if s does not satisfy G[i, j ], O[i, j ] (s) is a synthetic state which looks like the result of using O[i , j ] to rewrite some state. If O[i , j ] were selected to solve the problem (s, g, R), the weight assigned to O[i , j ] would be the weight associated with the above class. FDS goes one step further; it uses this weight as a base for determining a final weight, but the discussion of this process lies beyond the scope of this paper.

The experience-gathering, then, consists of adjusting the table T of weights associated with the classes. When a problem is solved, each step of the solution is exami ned to s ee whether any operators were tried before the 'correct' one (the one in the solution). If this is the case, the weights associated with the classes of the incor­ rect operators are decreased, while the weight as­ sociated with the class of the correct operator is increased. The adjustment formulae appear in 5.

Two comments ought to be made here. First, the classification rule uses only the similarity measure defined above. This, in turn, is defined in terms of properties shared by all states and goals in FDS. Thus the classification mechanism is task-independent, in the sense that it is de­ fined for any problem which can be presented to FDS. Since FDS is a general-purpose system, this feature was a critical factor in the design of the scheme.

The second comment is really a query: given that the classification is defined for .an arbit­ rary problem, is it appropriate? Saying that two operators in the context of a problem fall in the same class is asserting that, in this scheme, they are equally likely to lead to a solution. This is a strong statement. If the classification has no connection with reality, adjusting weights assoc­ iated with classes is unlikely to produce anything except random behavior. On the other hand, if significant improvement results then the classif­ ication scheme may represent a useful way to cat­ egorize operators in the context of problems. The question of the appropriateness of the scheme is best answered, then, by examining some results of its use.

Results

The performance of FDS in four task environ­ ments will be summarized. Each of these cons ists of an ordered set or bZock of problems to be sol­ ved in sequence. In about half the cases the problems are theorems to be proved. A brief des­ cription of the blocks is given below; a complete definition appears in 5,6. Some of the problems have been presented to human beings, who f i nd them non-trivial. 3

Block S contains fifteen problems in an alge­ bra pertainin~ to flowchart equivalence developed by Sanderson. (The problems are taken from this thesis.) Initially there are twenty-six rules, but, a s each theorem is proved, it is r e tained as a new rewriting rule. Figure 4 shows the given rules, the theorems, and a sample proof of the first theorem. For convenience, states ar e repre­ sented in conventional bracketed notation r a t her than as trees.

Block A consists of eighteen theorems of Notation: 'S' is a unary connective, 'I' and 'Z' are constants, and all other alphabetic characters represent free variables. The bin­ ary connectives '+'and '/'have no relation to the symbols used in arithmetic.

Initial rewriting rules given

Theorems

Proof of first theorem

elementary algebra concerned with the manipulation of binary addition and subtraction. There are six rules given and, as before, each theorem proved is added to the list of rules.

Block H i s composed of twenty-five problems in lexical pattern recognition in a generalized form of that f ound in Ledley2. There are twenty rules defined throughout.

Block P is a statement of a well-known puz­ zle. A philosopher is walking in a land peopled exclusively by Goodies (who only tell the truth) and Baddies (who always say the exact opposite of the truth). Coming up to two of the residents of this land, our philosopher asks the way to the library. One mutters something unintelligible, and the other says, "He says east. He's a Baddie." Which way should the philosopher go? In the for­ mulation used there are eight rewriting rules.

For an individual problem, the performance of FDS will be measured by effi ciency , the ratio of the number of states in the solution to the number generated while searching for it. If a problem i s solved with 100% efficiency, then there is not much wrong with the ordering of operators for trial! For a block, the performance measure will be the average effi ciency on the problems in that block.

The first set of experiments is designed t o demonstrate that the scheme allows FDS to improve its performance on a given block of problems. Successive passes are made through the block, as follows. Each weight is initialized at 0.5 and the problems of the block solved in sequence with the adjustment of weights suppressed; this is cal­ led pass 0. (The average efficiency on pass 0 rep­ resents the performance of FDS with no re-ordering of selected operators.) Any problems retained as rules are then forgotten, and pass 1 is made per­ mitting the adjustment of weights. Any rules kept are again discarded, but the adjusted table of weights is retained, and pass 2 is made. The above is repeated until pass 10 is finished. Since nothing changes between passes except the table of weights, any improvement must be due to the 'experience' represented by this table.

The results of this set of experiments are summarized in table 2. Notice that, even with no

experience, the average efficiency on each block is quite high. FDS incorporates a powerful algo­ rithm for selecting operators and screening out useless ones, and the order in which it discovers operators gives some clue to the order in which they ought to be tried. The ordering, and hence the efficiency, still improves significantly on the series of passes; on pass 10, sixteen of the eighteen problems of block A are solved with 100% efficiency. Although only four tasks have been explored to this length, comparable improvements have been noted in all the dozen or so tasks pre­ sented to the system.

But the concept of experience is stronger than this. Solving problems in some area should allow the system to solve new problems better. In other words, experience should be transferable from one set of problems to another set in the same task environment. Generally, this turns out to be t he case with this scheme. Consider, for example, the last f ive problems of each of the bl ocks S , A and H; call t hem blocks S ', A' and H'. We will compa re the average efficiency with which FDS solves each of these subblocks using two dif­ fer ent t ables of weights: E, the table of pass 0, and E', that obtained during pass 1 through the bl ock after all but these problems have been sol ved. Note that these tables of weights contain no experience from any of the problems in the sub­ bl ocks . Table 3 shows that, for blocks A and H,

experience block S ' block A' block H'

E

0. 7%

E'

0.8%

27.0%

64.8%

50.1%

79.5%

Table 3. Within-task transferability

solving all but the last five problems of each s ignificantly helps the solution of these last f ive. For block S the improvement is very slight. The last five problems of block S , however, are different from the preceeding ones (they all have two S's). In this case, then, a notable improve­ ment was not to be expected. As a further test, a relatively difficult algebra problem was presented t o FDS. With no experience, the system (on an IBM 7040-7094 DCS) was unable to solve it in an hour. On the other hand, when the experience from block A was given to FDS, it found a solution in five and one half minutes.

Some incomplete experiments have been made to test whether this form of experience is transfer­ able , not from one set of problems to another wi thi n the same task, but from task to task. It has been found that this is sometimes useful, but tha t in most cases the improvement is insignific­ ant. One interesting point which has emerged from thes e experiments is that it is possible to com­ bine tables obtained from several tasks; the re­ sult i ng synthetic table leads to better per­ formance averaged across all the tasks than any of the individual tables from which it was formed.

Conclusion

On the basis of the experiments performed with the scheme, it seems fair to say that it works. This is encouraging when one considers the simpl e-mindedness of the approach. While it could only benefit from a more powerful measure of simi­ l arity , the basic idea of classifying operators in the context of problems seems to be appropriate.