Predicting The Length Of Solutions To Problems

Introduction

This paper is concerned with a class of problems whose solutions are in a sense linear. Several formalisms have been used to describe such problems [1,2,3,4,7,9], but the central ideal can be simplified and summarised as follows. The universe is a network consisting of a set S·{s.} of objects connected by a set E of edges. 1 A problem is the task of finding a path from one object si to another object sj. A solution con­ sists then of a sequence of objects

such that an edge connects each object to the next. The above will be called a solution of length .!!. because the path from si to sj contains

si= s 0, si, .·· , s~_ 1 ,s~ = sj n edges.

Several systems have been developed for dis­ covering solutions to these problems. They have one feature in common with most algorithms in artificial intelligence, namely: at any stage in the search for a solution, a choice must be made among several possible next actions. This choice is known to be crucial, for if it is made felici­ tously a solution may be ·found quickly, whereas a great deal of time may otherwise be spent fruit­ lessly. Many successful systems incorporate re­ latively complex mechanisms to make this choice [5,10,14] but these mechanisms often seem to be bound inexorably each to its own system, and thus

cannot be transferred to new systems.

This situation was relieved by analysis [7,8] indicating that the ability to make a good choice comes down to (in our simple formalism) the ability to predict the lengths of solutions to problems before they are solved. This is a particularly useful approach because the length of a solution to a problem does not depend on the way that the· solution was found, and so the choice-making function can be divorced from the algorithm proper. In particular it is possible

J.R. Quinlan

Basser Department of Computer Science University of Sydney, Australia

to study the prediction task in isolation, so long as the implications of the eventual re­ union of all the components are borne in mind.

The following section develops a general pre­ diction scheme that could be adapted to any system for handling this type of problem. This is followed by an examination of its performance on a substantial number of problems.

A General Scheme

The underlying structure of the scheme is straightforward. Suppose we have a set of prob­ lems ~hose solution length is known, and an un­ solved problem whose solution length we wish to estimate. The approach taken is to predict that the unsolved problem will have the same solution length as the 'most similar' solved problem. To determine the most similar solved problem, we will map all the problems into points in some space and find the point closest to the unsolved problem. The main part of the scheme is concerned with setting up the mapping in such a way that points in the space which are close together do tend to have similar solution lengths. Note that the con­ verse is not true: we do not require that all points with similar solution lengths lie close together. For instance, the points with a given solution length may form several distinct clusters throughout the space.

A few preliminary remarks must be made. A problem may have many solutions of various lengths, so 'the' length will be taken to be the shortest. Alternatively a problem may have no solution, in which case we take the length to be a large number. Finally, while a solution length is clearly an integer, we will allow an estimate to be a real number such as 3.7, which may be inter­ preted as 'closer to 4 than to 3'.

The first step will be to look at the dif­ ferences between a pair of objects. we are after some means of describing the changes that must be wrought on the first to make it identical to the second. Clearly this description will depend on the nature of the objects and cannot be defined in general terms. We thus postulate the exist­ ence of a difference function

which, given a pair of objects, produces a vector of q non-negative real numbers. Section 3 des­ cribes two such functions that may serve as illus­ trations.

Now 6 maps a pair of objects into Rq, and a problem consists of finding a path between a pair of objects so and so, say. It might seem that 6 ~ ) alone will suffice to map problems into a suitable space. However, recall that we will need to find the closest point to an unsolved problem, so we will need to use distance in the space. The various components of 6 ( s 0 , s 0) might measure quite ~ ) different things, with the result that using 6 alone might render distances in the space meaning­ less. Consider the analogy of mapping people into R 2 by taking their height in feet and their weight in pounds. Suppose we have two individuals who map to <3.5,150.0> and <6.0,160.0>. A third individual <5.9,154.0> would then be closer to the former than the latter! To ensure that distances are meaningful, then, our mapping must have the property that the coordinates of a point are

measured in the same units.

Since the length of a problem's solution will also clearly depend on the edges E connect­ ing objects, it would seem desi·rable to bring them into the mapping somehow. Now each edge e connects two objects s and s , say. We can form X y a picture 6(s ,s ) of the difference between the X y objects connected by edge e. If we could form such a picture for each edge and average them, the

result would be a vector

where di is the average value of the ith component of the difference between pairs of objects con­ nected by an edge. Intuitively, d is a picture of the difference created by moving along a 'typical'

edge. Each component of 6 is non-negative, so di will be non-negative. Moreover, di will be zero only if the ith component of the difference between all pairs of objects connected by edges is zero (in which event the ith component of the difference function could well be scrapped) . But for most problems of interest S and E are very large or even infinite, so d cannot be computed as above. Here we make use of the fact that the scheme is to be embedded in a problem-solving system. It is most unlikely that a problem­ solver would be set up to tackle a single problem in some universe; even if it were, it would solve some subproblems in the course of its search for a solution. We can assume, then, that a number of problems with identical or very similar S and E have been solved. The vector d can be approxi­ mated by averaging 6(s ,s ) not over all edges e, X y but over those edges used in solutions to the previous problems.

Again, a problem is solved when a path is found from object so to object So. If ~ )

~ ) q then ~ is the kth component of the difference that will arise as we move from si to sj. Again, ~ is the corresponding component of the differ­ ence that arises in moving along a typical edge. The ratio ~~~ is then the number of typical edges that we would expect to move along in getting from si to sj. If we form

then ~ is a crude estimate, derived from the kth component of the difference function, of the length of the solution to the problem. Each com­ ponent of ~ is clearly measured in the same units, so mapping problems to their ~ descriptions in Rq will result in meaningful distances in the space.

At first glance, it seems that we have changed the task of predicting the length of solu­ tions into a classical pattern recognition problem [6] in which the ~·s are the description vectors and the classes are the solution lengths. This unfortunately is not so. Since the picture of a problem is incomplete, it is quite possible to envisage two problems with the same picture but different solution lengths. Secondly, we have allowed the prediction function to take real values so the number of classes would become infini te. As a matter of peripheral interest, when the first set of data from the next section was set up as a pattern recognition problem using a clustering algorithm [13], the results were poor.

Still, the approach taken is a variant of a familiar pattern recognition technique. Each z is clearly a point in q-space, so we imagine a set {p . } of prototype points embedded in this -1. space. Each prototype point ~i has associated with it a frequency fi and a class sum ci, both of which are integers. As usual we operate in two modes, classifying and training. For classi­ fication we are given to description z of a problem; we find the prototype point ~i nearest to z and predict the solution length as the ratio ci/fi . In training we have a description of a problem with known solution length n. If there already exists a prototype point ~i that is very close to~· i.e., l~i- ~~~some E, we modify it by

(ii) changing its frequency and class sum;

f. becomes f .+l and c . becomes c .+n. 1. 1. 1. 1. If no prototype point is very close to ~· we enter the latter as a new prototype point p .=z, -J - setting fj to 1 and cj to n.

One matter remains to be dealt with. If the predictor is to be useful ·in practice it cannot be allowed to acquire prototype points without limit. There must be some mechanism for reducing their number so that the performance of the pre­ dictor is degraded as little as possible. This implies that some means of generalizing a subset of the prototype points is required, in the vein of Samuel's generalization of checker positions [11]. A simple process is defined that reduces by one the number of prototype points.

Basically, it looks for two neighbouring points with similar class sum/frequency ratios and re­ places them by an average point.

We say two prototype points ~i and ~j are adjacent if the distance between them is less than the distance from either to any other prototype point. We consider merging them to form a single prototype point ~k' with

Now this merge has associated with it a cost in the form of a change in class sum/frequency ratios that can be expressed as

which reduces to

The procedure then consists of examining each pair of adjacent points and merging that pair for which the above cost is minimal. Each application of the procedure reduces the number of prototype points by one. Section 3 reports on the degrada­ tion of prediction performance as the number of prototype points is reduced.

Early in this section we postulated a func­ tion 6 for producing a vector description of the changes that would have to be made to one object in order to make it identical to a second. This function eventually yielded a description z of a problem in q-space. The scheme proceeded under the assumption that two problems with points lying near each other will tend to have solutions of similar length. In other words, we required 6 to provide a meaningful description so that this spatial property comes about. Now for some problem areas with built-in spatial connotations (such as transportation problems) it is not diffi­ cult to formulate such a 6. But what about the rest? The next section examines two universes, one finite and one infinite. In each case it is possible to develop a simple 6 so that the pre­ diction scheme gives useful results. Hopefully these successes indicate a general applicability

of the scheme.

Testing the Scheme

In the first universe objects are binary trees, a representation recognized as being both common and general (7]. The universe is infinite, so objects and ed9es cannot be stated explicitly. Edge information is given by rewriting rules, each of the form s 1 := sr where s 1 and sr are objects. The meaning of such a rule is as follow~ if si is an object containing an instance of s 1 then si can be rewritten as the object sj formed by replacing the instance of s 1 with a corres­ ponding instance of sr. For example, consider the object (a+b)+c and the rule x+y :s y+x. The object is an instance of x+y, and so can be re­ written as the corresponding instance of y+x, namely c+(a+b). But a+b is also an instance of x+y, so the original object could also be re­ written by this rule as (b+a)+c. An edge connects si to sj if and only if si can be rewritten as sj. Since S is infinite, each rewriting rule normally defines an infinite number of edges.

Two sets of problems were established. The first (set A) contained 152 problems relating to the manipulation of algebraic expressions involv­ ing + and -. The number of rewriting rules varied from 6 to 23, solution lengths from 1 to 6. The second (set S) of 139 problems was concerned with establishing the equivalence of programs using a formal language to describe flowcharts [12]. The number of rules ranged from 26 to 40, solution lenqths from 1 to 5. Sample problems and solutions for sets A and S appear in [9,10]. A number of problems from both sets have been presented to human problem-solvers who found them non-trivial.

A moderate amount of experimentation was needed to find a suitable 6 (largely because the early attempts were too sophisticated) · It was decided to use only syntactic information, i.e., to disregard entirely the meanings of objects represented as trees. Further it was decided to ignore the difference between operators and operands. Six operations for manipulating binary trees were formulated, as

;t: move a symbol up and to the right

' move a symbol up and to the left

~ move a symbol down and to the right

i1 move a symbol down and to the left

· add a new symbol somewhere in the tree

• 9 delete a symbol somewhere in tree.

Any changes to a binary tree can be described using these operations. The function 6 produces a vector of 6 elements, one for each of the operations. The kth element of 6(s. ,s.) is l. . J simply the number of times that the kth operation above was used in changing si to sj. The unique­ ness of the vector was ensured by a number of arbitrary restrictions, such as only using the operations e and 9 when the move operations by themselves were inadequate. For example, con­ sider the two objects

which we denote by s 1 and s 2 respectively. To change s 1 to s 2 we must

• (i) move a down and to the left (')
• (ii) move c ~ twice, and then ,/ and lw
• (iii) move b I'
• (iv) add a symbol + to s 1
• (v) delete a symbol- to s 1 ·

The vector produced by counting the number of times each operation was used is

This 6 is completely independent of the rewriting rules available to solve a problem; there is no idea of 6(s. ,s.) providing a model of how to get l. J from si to sj. The same 6 was thus used for both sets of problems. The 'typical' edge difference d for each problem was computed from the solu­ tions to previous problems in its set.

The second universe was that of the a­ puzzle. An object consists of a 3X3 arrangement of tiles bearing the digits 1 to 8 and a blank tile. An edge exists between two objects if the second arises from the first by interchanging the blank tile with one of its neighbours. In this problem domain both S and E are finite, though large (S contains about 360,000 objects).

Three measures were used to set up 6, all of them adapted from those mentioned by Nilsson [7].

we define 6(si,sj) as (x 1 ,x 2 ,x 3 ) where x 1 = the mmlber of non-blank tiles that occupy different positions ins. and s. l. J the sum of the cell distances apart of the above different positions x 3 · going around the edge, the number of non-blank tiles that have different successors ins. and s .. 1 J

For example, if si and sj are the objects

then 6(si,sj) is (5,9,5). (Note that, unlike the first 6, this one has a substantial connection to the way a problem is solved; in fact, x 1 is a lower limit on the length of the solution.) The third set (set P) contained 186 8-puzzle problems with solution lengths ranging from 1 to 18.

The .basic measure of the predictor's perform­ ance on a problem was taken to be the absolute ~· i.e., the magnitude of the difference between the actual and predicted solution lengths. (This follows the approach to errors in heuristic functions in [8].) For a set of problems the performance measure was the average absolute error on the set. The predictor could be considered useful in so far as it outstrips the obvious ran­ dom procedure of selecting an arbitrary length !rom those actually occurring in the set. This random procedure has an expected average absolute error of

2.02 on set A (selecting a length from 1 to 6)

1.63 on set S (ditto from l to 5)

6.10 on set P (ditto from l to 18).

The first experiment was designed to test the scheme in an environment similar to that which would be encountered in practice. Each set was first shuffled so that the original order of the problems would have no bearing on the outcome. Each problem in a set was first tested, the absolute error found, and then the problem used to train the system. Each problem was thus tested with the predictor having the benefit only of experience from previous problems in the set. Three average absolute errors were computed: for the first 2/3 of the problems, for the last l/3, and for the whole set. This experiment was performed with 20 different shuffles of each set.

The results obtained appear in Table I. This shows that the performance on the whole set was better than . the random procedure in all cases, but particularly so for sets A and P. There is also a clear improvement on the last 1/3 in all sets. COnsidering the numbers of problems and shuffles, this improvement can only be ascribed to the experience obtained on previous (different) problems.

Table I

Alternating test and train: average absolute errors on 20 shuffles and mean.

The values shown for each set are for the first two-thirds of the problems, the last third, and the whole set.

The second experiment was drawn up to invest~ gate the predictor's performance on the sets of problems after training, and to see how it was affected by reduction of the number of prototype points. The prototype points developed in the first experiment were retained and each problem again presented for classification. The number of prototype points was then reduced by repeated merging and each problem again fed to the predic­ tor. This reduction process was performed several times.

The results appear in Table II. It is clear, ·first of all, that the predictor is doing very well with its full complement of prototype points. Secondly, it is possible to merge quite a large number of prototype points before the performance of the predictor is seriously degraded; even allowing only 10, the predictor still does passably. This suggests that the scheme should still be useful if a restricted amount of space was available to hold prototype points.

Table II

Degradation of retrial performance as the number of prototype points is reduced.

Conclusion

On the basis of its performance on the sets of problems in the previous section, it seems fair to say that the scheme gives useful results, even with an unsophisticated o function. It is being included as part of a problem-solver in the process of development. Still, many improvements are possible.

In Section 2 we went to some lengths to en­ sure that the various components of the ~ descrip­ tion of a problem were measured in the same units. As a result, distances were equivalent in all dimensions of the problem description space. This does not allow for the possibility that small changes in one component could be more significant than large changes in another. A more flexible definition would allow distances in different dimensions to be weighted differently. Experiments have been conducted along these lines using statistics such as the variance of di from problem to problem in a set. The result was a small but noticeable improvement.

Certain aspects of the scheme may not be appropriate if the number of training points were to run into the thousands. In particular, it may be desirable to impose some sort of ageing process on prototype points and on the solutions used to give a picture of the 'typical' edge. These measures would be designed to ~e the system more responsive to its recent history rather than its total history in some problem domain.

Finally, there still remains the nuisance of designing an appropriate 0. This may not be as annoying as it appears. For the universe of binary trees we used only structural information on objects, so the same o was appropriate for two quite different problem domains. A relatively small number of structures is used to represent objects in artificial intelligence, so a few o's may suffice to handle a large number of problem domains. The ideal system, of course, would specify a loose framework for o and allow the function itself to be induced from experience, along the lines of a feature extraction exercise. Intriguing as this sounds, it may turn out to be pinning one's hopes on a deus ~ machina.