A Study of Empirical Learning for an Involved Problem

1. Introduction

Although concepts and evaluation functions can be learned from examples using various methods, existing techniques are often inadequate for harder problems. If the domain is uncertain or the environment is dynamic [Langley, 1987], a simple induction algorithm may have difficulty. In many cases we may be forced to elaborate old methods, combine them, or develop new ones.

To complicate matters, there are several approaches to choose from. To learn uncertain con­ cepts, we might consider a modification of ID3 [Quin­ lan, 1986] or some statistical technique [Draper & Smith, 1981]. Or, because concept learning involves the parameterization of descriptions, we might base our method on traditional optimization [Gill et al., 1981]; one such approach uses genetic algorithms [Hol­ land, 1975]. or course, some methods are known to be especially suited for particular situations; e.g., genetic algorithms can be applied to badly behaved problems having strong nonlinearities. However, many problems and methods are largely unexplored.

The situations considered in this paper include probabilistic concepts, dynamic environments, and noisy and biased data. In an attempt to help develop methods for such cases, we explore a problem that taxes current systems. The problem involves a representation of the fifteen puzzle that can be managed by elaborations of several methods.

The next section defines a general problem of which the fifteen puzzle is a special case. The analysis suggests certain methods. Section 3 describes the methods and discusses their strengths before we evalu­ ate and compare them in Section 4. Finally, Section 5 summarizes implications for empirical learning.

2. The Problem

This section analyzes a representation of the fifteen puzzle, whose solution may be viewed as a special case of concept learning. In this and other problems, the data may be biased, which complicates learning.

2.1. Generalized Concepts

Our basic problem is learning a concept or evaluation function from examples. By definition, a concept is a rule that describes a class of instances. If we represent an instance as a tuple of attributes, a con­ cept will have an associated instance space whose dimensionality is the total number of attributes. As shown in Figure 1 (a), an "ali-or-none" concept is a binary-valued function over instance space. This diagram shows two attributes; in general a concept is a function over whatever attributes are used to express it. If we allow a concept to be probabilistic (Fig.lb ), the function becomes graded: it has values between 0 (certain class exclusion) and 1 (certain class member­ ship). Here we interpret and learn the graded values as probabilities. Hence a concept is a binary or proba­ bilistic funetion over inatanee spaee.

Viewing a concept as a function helps to draw parallels among learning methods and the representa­ tions they use. As one example, consider an evaluation function H for a state-space problem such as the fifteen puzzle. If x is k- tuple of attributes ( x 1 , x 2 , ... xi) representing a state, then H(x) could represent the probability of finding the goal (quickly, optimally, etc.) if the aolution path goea through x [Rendell, 1983]. But because H(x) has the form of a probabilis­ tic concept, it could also be interpreted as the concept "good state to develop."

Typically, a concept is expressed as a logic expression or decision tree involving the attributes [Mitchell, 1978; Quinlan, 1986], sometimes with anno­ tated probabilities [Breiman et al., 1984; Rendell, 1983], although other expressions are possible. In con­ trast, an evaluation function H is often defined as a linear combination of attributes b 1 x 1 + b 2 x 2 + .... + bkxk = b.x, where the bi are weights to be learned [Samuel, 1963]. However, these preferred forms are not mandatory.

To reiterate: When expressed in terms of attri­ butes, concepts and evaluation functions are both func­ tions over their instance space. Only the details vary. The terms eoneept and evaluation function are some­ times synonymous.

2.2. Noisy and Biased Data

The data for empirical learning are often binary, to represent definite knowledge about class member­ ship [Mitchell, 1978]; but data can also be graded, to indicate probable categorization [Draper & Smith, 1981]. For example, we could annotate a value of 0.8 to a patient's state to express a belief that he has some disease. Probabilistic data can also be uncertain (e.g., 0.8 ± 0.1), or even biaaed (e.g., 0.8 is an overestimate). Biased data arise if the sampling is not random, which is undesirable in statistics [Draper & Smith, 1981], but not always in machine learning [Winston, 1984].

In some problems, not all the data are available before some decision must be made that utilizes the results of analyzing the first batch. In such dynamic learning, how might the results of one run affect the gathering of future data? A physician might have compiled some data for diagnosis. If these data sup­ port disease A, then the physician's subsequent tests may be biased toward observations that will confirm it. The consequences of such a bias may often be good, but sometimes detrimental. If the correct diagnosis is disease B, time may be wasted, or worse, the proper evidence may never be found.

This problem can also arise in domains such as the fifteen puzzle. Because this punle has about 1013 states, most problems cannot be solved breadth-first (to give unbiased data). In contrast, a good evaluation function solves many problems, but produces biased data: States assessed favorably tend to predominate. Data can become increasingly biased as the evaluation function improves in successive iterations. New data are incommensurable with early data, and if used directly, can give erroneous results [Rendell, 1981].

2.8. Representative Problem Charaeteristies

The issues explored here involve biased and unc­ ertain data, uncertain concepts, and dynamic learning. All these arise in the fifteen puzzle when an evaluation function is used for best-first search. In experiments, several attributes were defined, all relative to the goal. The most important is the total city-block distance of tiles from their goal positions [Doran & Michie, 1966]. The other attributes are various impediments, such as the tiles in a row being correct, except out of order [Rendell, 1981]. This high-level representation presumes considerable knowledge, and compresses the 1013 states into about 10 4 or 10 5 descriptions, depend­ ing on the exact choice of attributes.

Although this compression is great, it is not the main benefit of the representation. The main benefit is to tame the evaluation function H. H maps states into probabilities, which estimate the likelihood that a state will appear on a shortest-solution path. This probabil­ ity H varies with the attributes xi monotonieallv. For example, the smaller the city-block distance, the more likely the state will be useful. Although attributes may interact somewhat, the monotonic relationship allows us to assume a linear combination: H(x) = b 1 x 1 + b 2 x 2 + .... + bkxk = b.x, and we need only learn the weights bi.

H can also be viewed as a class membership func­ tion, where the class is probabilistic (cf. ·Fig.1b). His comparable to other concepts that begin with favorable representations. In a favorable representation the attributes are matched to the problem so that, over their instance space, concepts exhibit few disjuncts or peaks [Holte & Porter, 1988; Rendell, 1988]. If our linear model b. x is appropriate, then H has just one peak-where each xi has its extreme value.

Associated with H is its weight apaee, over which is defined some objective function [Gill et al., 1981]. Our objective is task performance. Figure 2 shows that a performance function over a weight space defined by our attributes tends to be smooth, and may have a single optimum. The ordinate shows the aver­ age number of nodes developed before a solution was found, for a large set of arbitrarily difficult puzzles. Weight space is hypothesis space, the continuous ana­ log of a discrete version space [Mitchell, 1978]. In ver­ sion space, hypotheses are correct or incorrect. In weight space the hypotheses have degrees of correct­ ness, shown in Figure 2 with the best at the central position of each graph. Such optima are surprisingly difficult to find, even for simpler spaces.

Although our representation gives typical membership and objective functions, this problem is harder than some because it requires dynamic learning. This produces biased data, which are already uncer­ tain. The data come from search trees; each node becomes a training example. An example is positive if and only if it appears on a solution path. Although failures to solve give only negative examples, incom­ plete search trees are useful for training when com­ bined with successful searches. Depending on the learning method, several searches may compose a sin­ gle iteration. An iteration is a set of searches to gather many data, followed by the computation of an improved evaluation function H to guide new searches. Because H favors useful states, iterated learning requires "unbiasing" procedures [Rendell, 1983].

3. A Selection of Learning Methods

The weights of an evaluation function or the parame­ ters of any concept description can be learned in many different ways. However, there are two basic approaches. One learns the function over instance space (Fig. 1 ); the other works with hypothesis space (Fig. 2). Methods that use instance space directly include curve fitting and decision tree induction. Methods that work in hypothesis space include candi­ date elimination and optimization techniques. We first outline, then evaluate three instance space methods, two hypothesis space methods, and one combination method (see Table I).

(1) Direet eurve fitting. If attributes have real, integer, or binary scales, we can use statistical regres­ sion [Draper & Smith, 1981], which fits the best hyper­ plane H(x) = b1 x1 + b2JC:! + .... + bkxk by minimizing the least squared-error for different choices of weights bi. Abstractly, this is like searching weight space (Fig.2) to minimize the objective function-here the squared-error. Operationally, however, regression is algorithmic- no search is necessary, because the tech­ nique inverts matrices to solve minimization equations directly. Hence the method is very fast.

If our class membership values were probabilities, normal regression techniques [Draper & Smith, 1981]

would apply. However, in our experiments (and in many machine learning applications) the data are binary. Fortunately, binary data can be managed by analogous techniques, one of which is probit analysis [Finney, 1971].

(2) Probability regions and diserete evaluation. In machine learning the best known empirical tech­ nique may be induction of decision trees or partitioning of instance space [Quinlan, 1986]. For graded con­ cepts, the instance space is divided into regions of simi­ lar probability [Breimah et al., 1984]. If we have learned a concept, these regions classify instances into their probable class; if we have learned an evaluation function, the regions classify instances into their prob­ able utility [Rendell, 1983].

For our fifteen puzzle problem, one pass of a par­ titioning algorithm is insufficient. Because of the difficulty of this puzzle, early data must come from easier problems, and later data from intelligent search (causing sample bias). Hence, the partitioning algo­ rithm becomes just one operation in a scheme to form and revise regions and their probability estimates [Ren­ dell, 1983]. Mter the initial partitioning, later passes use the biased data and three other operations: unbias­ ing, probability updating, and region refinement. Unbiasing begins by comparing averaged data within existing regions, which already provide an unbiased estimate of the probabilities. These unbiased estimates are now compared with the biased data, pairwise for each region, to extract a relationship. The relationship allows an operation to be applied to the biased proba­ bilities to convert them to unbiased estimates. Now the new probability estimates are averaged with the old to provide probability updating. The newly unbiased data are also used for a different operation: region refinement, which further subdivides the exist­ ing partition.

(3) Fitting probability regions for smoothed evaluation. Although the regions output by an induction algorithm allow refined classification, the discrete nature of this approach may be insufficient. As we see in Section 4, search performance may be poor if the discrete probability regions do not discriminate well enough. To address this problem, we could use the probability regions as data in atatistical regression to find the best smoothed function H(x) = blxl + b2x2 + .... + bkxk.

Instead of this complicated process of inducing regions, then fitting them, why not simply fit the origi­ nal data? The answer is that the computational resources required to unbias are too great if we retain all the data. In contrast, if we iteratively repeat the operations of data gathering, unbiasing, partitioning, then regression, then our primary information struc­ ture is the compressed regions. Regions are easier to update.

(4) Optimization using response surfaee fitting. Unlike the previous three methods which work in instance space (Fig. 1 ), optimization methods search hypothesis space to minimize (maximize) the objective function JL· Because the weights in Figure 2 have real values, and because JL is smooth and appears to have only one peak, a hill-climbing method is suitable [Gill et al, 1981). A hill-climbing technique selects weight vectors b by moving in the direction of improving JL (b). One technique suitable for noisy domains is response surface fitting with a diminishing grid. In this method we select points b at corners and mid­ points of a hypercube in weight space, then gather data (JL values) to fit a quadratic (a parabola). The optimum predicted by the parabola allows us to gather more refined data, as we gradually hone in on the optimum JL by repeatedly shrinking the grid. Starting with a large grid detects broad tendencies; shrinking the grid improves accuracy.

Despite the quality of this method, a serious problem in our case is that most values of JL cannot be found ! This is because most choices of b give such poor performance that typical problems cannot be solved within reasonable time. To offset this problem, initial runs used easier problems.

(6) Optimization using a genetie algorithm. Genetic algorithms are designed to optimize an objec­ tive function JL called the fitness [Holland, 1975). Given a population, hypotheses b are selected stochast­ ically for breeding, with probabilities proportionate to JL(b ). Hypotheses are usually represented as bit vec­ tors called genotypes. Binary operations such as cross­ over are applied to pairs of genotypes; unary opera­ tions such as mutation are applied to single genotypes. The operations produce a new generation of hypotheses. Because they implement parallel search, genetic algorithms can manage badly behaved objec­ tive functions.

For this reason, a genetic algorithm seems unnecessarily powerful for the problem illustrated in Figure 2. Massively parallel search is not required and it may be costly. We still have the problem of com­ puting JL for mediocre choices of b, though once again we can do some preliminary search.

(6) Combining partitioning and parallelism. Our final method is a combination of partitioning in instance space and parallel search in hypothesis space.

This method uses a modified genetic algorithm to govern multiple partitioning [Rendell, 1985). The "genotype" is compressed and variable-it is a set of probability regions (Fig. 1 b). Each of these structures produces a different evaluation function H, which is then given some puzzles to produce data of two types: detailed data for updating probabilities and refining regions, and overall data for measuring performance JL· This allows the selection of individual regions for k­ sexual crossover.

4. Comparative Results

Table I summarizes representative results of many experiments for each of the six methods described in the previous section. To assess these methods we use the number of nodes developed JL· Because other com­ putation is negligible, JL is a good measure of both the learning time and the quality of the resulting evalua­ tion function. (Another measure, the length of the solution, was found to track J.L·) On a VAX 780, 1000 nodes take about lh minute CPU time. The average values of JL shown in the table were obtained by solving 100 puzzles, giving a standard error of about 11 (or 3%). Although some related work appeared in [Ren­ dell, 1983) and [Rendell, 1985), most of these results are new. All experiments used the same four attributes of Figure 2.

(1) Direet eurve fitting. To fit the best ~yperplane H(x) = b1 x1 + b2 x2 + .... + bk xk to the bmary data from search trees, probit analysis [Finney, 1971) was used. Because the technique is algorithmic, it is fast. However, the quality (nodes developed) is 534- 53% worse than optimal, and this is after favorable interpretation of the results. To begin the experiment, puzzles nine moves from the goal were given (greater difficulty requires too much computation). The result­ ing data gave a non-zero weight only for the city­ block distance x 1 , because easy puzzles can hardly have the impediments described by the other attributes x2, x 3 , and x.. To continue the experiment, the resulting evaluation function was used to solve harder puzzles and find impediment weights. These weights ( b2, b 3 , and b.), now approximated the correct ones, but because of the biasing effect of the city-block distance already in H, the new value of b 1 was in error by 1200%. Further experiment gave similarly biased and unpredictable values, although if we take the value of b 1 from the first iteration and the values of b2, b 3 , and b· from the second, we obtain the performance shown.

(2) Probability regions and discrete evaluation. The second method is to partition instance space into regions of similar probability (of a state's appearing on a short solution). Because the technique is iterative, it requires not only initial partitioning, but also partition refinement after data unbiasing (see Section 3). The improving quality of the evaluation function over repeated iterations allows the solution of harder prob­ lems, 'which provide more representative data. This alternation of sampling and learning allows each pro­ cess to speed the other. But the evaluation is discrete:

For task performance the states are classified into discrete regions. This lack of smoothing or interpola­ tion causes poor performance: at least four times optimal quality. (The number of nodes developed could not be tested precisely, because resource limits were often exceeded.)

(3) Fitting probability regions for smoothed evaluation. This is the same as the previous method except that at the end of each iteration the probability regions are used as data to find weights bi fo~ the linear combination H(x) = b1x1 + b2x2 + .... + bkxk. After convergence in half a dozen iterations, this smoothed evaluation function gave near--optimal per­ formance of 353 (compare Fig.2 and see [Rendell, 1983)). Although H contains the only knowledge used for solving, the probability regions provide the primary information, and are more suitable for dynamic learn­ ing. One advantage of this and other instance space methods is that ever11 IJtate c:ounta. One drawback of this and most methods is that for fast learning, the difficulty of the training problems must be just at the current performance limit. This requires some user experience. Moreover, the combination of approximate techniques (e.g., unbiasing, and search that relies on previous learning) over repeated iterations can cause problems. To some extent the iterative learning seems to be self-correcting, but often performance degrades slightly or levels off. One cure is user experience; another is repeated runs. Experiments have shown that about ten runs are required for a result within 10% of optimal. A similar criticism applies to most methods, so their learning times are multiplied by ten in cololmn 5 of Table I ("Effective Cost").

(4) Optimization using response surface fitting. Rather than probabilities over instance space, optimi­ zation methods use summary measures of performance 11. over hypothesis space. Summary measures cost more to obtain: concept accuracy requires the classification of many instances; search performance requires the solution of whole problems. For each problem solved, only a single value is obtained- the number of states developed. This contrasts with the first three methods, which identify each count with a point in instance space. This design difference explains the difference in learning times: hill climbing in weight space is slower. Initially, most values of the weight vector b are so poor that problems cannot be solved. To counteract this problem, a preliminary round of curve fitting (row 1) was used to obtain approximately correct weights.

(6) Optimization using a genetic algorithm. Approximately correct weights were also given to the genetic algorithm (row 5). Genetic algorithms need a well-chosen representation. If the genotype is too short, resolution will be lost; if this bit string is too long, time will be wasted. To ensure better perfor­ mance, the graphs in Figure 2 and some preliminary runs were analyzed to choose a genotype length of six bits. Another variable is the population size. Several experiments used populations up to 200. The less than optimal performance of 388 {12% worse than optimal) for the best individual in a population of 50 is perhaps not too surprising because genetic algorithms are not designed for obtaining 100% accuracy when the objec­ tive function 11. is unimodal, but rather for approaching multiple optima in parallel when the function is badly behaved. The high cost results from so much search (hundreds of states in each of many problems) for so little (a single performance value for each solution). Another problem is that verification of an individual weight vector requires a larger sample than during learning. For each weight vector suspected to be close to optimal, many test problems must be solved, which typically costs 10,000 nodes per candidate vector.

(6) Combining partitioning and parallelism. Perhaps surprising is the sixth result. This gives the best performance (although not significantly better than row 3 because the standard error is about 11, or 3%, in all rows). The cost appears higher than for the extended partitioning method, by a factor of six. Superficially, then, it seems that extended partitioning

* Measured as number of nodes developed to solve or learn (see text) .

is better when used alone than when combined with a genetic algorithm. However, this cursory assessment is misleading. The favorable learning speed of extended partitioning in row 3 results from considerable user experience with training. In fact the learning speeds given in rows 2 through 5 are about an order of magni­ tude too low (reflected in col. 5). In contrast, the com­ bined method of_ row 6 needs little user guidance because it is much less sensitive to training problems and evaluation errors. Even with a small population of 10 or 20, this method is extremely &table. It is reli­ able and easy to use. Furthermore, this method avoids the cost of verification, because individual weight vec­ tors need not be tested. Rather, all the regions from all the individual partitions can be used as a single large data set to fit a very accurate evaluation function ((Rendell, 1985] elaborates).

6. Discussion

This study of six empirical-learning methods suggests ways to cope with domains that are simultaneously probabilistic, dynamic, noisy, and biased. One recom­ mendation is to combine types of methods. Even for our numeric domain, the standard methods of curve fitting (1) and optimization (4) were limited because of biased data (in 1) and lost information (in 4). Further­ more, a standard method of instance space partitioning or decision tree induction, despite its extension for pro­ gressive refinement after data "unbiasing" (2), was inadequate because discrete classification rules were too unrefined, even though they were probabilistic. But when partitioning (2) was combined with curve fitting (1), the learning was fast and the task performance was optimal. Incorporating a third technique improved learning behavior still more. Like method 4, the genetic algorithm (5) could use only some of the infor­ mation available in the search domain, and although this method (5) behaved relatively poorly when used alone, it stabilized method 3 and made it easier to use (cf. (Quinlan, 1988]).

Because other problems exhibit characteristics similar to the search problem we analyzed, the phenomena should generalize. Probabilistic evaluation functions are probabilistic concepts (Section 2.1 ). In many real-world domains the concept is probabilistic, the learning situation is dynamic, and the data are noisy and even biased (Section 2.2). To reiterate the phenomena we observed:

• Instance space algorithms find class membership values H as a function of attribute values x; hypothesis space algorithms optimize overall quality values p, .of entire functions H(x). Combinations of these two methods exploit both kinds of informa­ tion.
• Instance space algorithms are fast; hypothesis space algorithms are stable. Combinations may have both advantages and also be easier to use.

The varied strengths of different techniques may pro­ vide a net gain when the methods are combined [Ack­ ley, 1985]. Ultimately, systems for very general learning may owe much to a structured combination of techniques (Buchanan et al., 1978].