CABOT: An Adaptive Approach to Case-Based Search

1 Introduction

Many case-based reasoning (CBR) systems are designed to solve new problems by adapting solutions to similar, previously solved, problems. The proposed solution to a new problem can be inappropriate for a variety of rea­ sons: 1) the system lacks a similar past case, 2) the "wrong" case was retrieved , or 3) the retrieved case was not adapted properly to the new problem. Most case­ based and instance-based systems are designed to handle just one or two of these errors. However, it is rare for a CBR system to handle all three.

It is important to distinguish between errors with dif­ fering causes because they require different solutions. It may be possible to compensate for an error in the re­ trieval mechanism by adding more information or alter­ ing the adaptation mechanism, but the resulting sys­ tem might do more work or save more information than would otherwise be necessary. For example, the CHEF system [Hammond, 1986] may expend effort adapting a retrieved case when a different case could be adapted with less effort. Compensating for an error, rather than dealing with its causes, may also hamper future perfor­ mance.

"Supported by a grant from Digital Equipment Corp.

tsupported by a grant from GTE Laboratories Inc.

tsupported by grants from the Air Force Office of Sponsored Research under contract AFOSR-90-0359; the National Science Foundation, contract IRI-890841 ; and GTE Labora­ tories Incorporated.

The work presented in this paper is based upon two hypotheses. The first is that it is useful for a case- or instance-based system to distinguish among errors due to a lack of information, a faulty retrieval mechanism, and a faulty adaptation mechanism. The second hy­ pothesis is that a problem-solving system can profitably use feedback from its environment to distinguish among the three types of errors. Once this distinction can be made, it is assumed that error correction can be done us­ ing a standard machine learning technique for supervised learning.

These hypotheses have been tested in CABOT, a hy­ brid case-based reasoning/ machine learning system that both reasons from cases and uses an inductive learning algorithm to adjust its retrieval and adaptation mecha­ nisms. CABOT has been tested against a non-learning system, two case-based systems with fixed retrieval and adaptation mechanisms, and two inductive learning sys­ tems. Results from these tests suggest that existing case­ based and instance-based systems could save fewer cases without reducing their current levels of performance.

2 Case-Based Reasoning

Although case-based reasoning systems vary signifi­ cantly, those that are used for problem-solving share a common approach. When a new problem is encountered , the system first retrieves one or more cases that are sim­ ilar to the new problem. Typically no case matches the new problem exactly, so the system must adapt one of the retrieved solutions to the new problem. Finally, the system may add the new problem and its solution to the case base, and it may adjust its indices.

Instance-based learning algorithms also share this ap­ proach to problem-solving, although they are sometimes considered distinct from case-based systems. When a new problem is encountered, one or more similar in­ stances are retrieved. If their classifications differ , the differences must be resolved to provide a classification for the new instance. Finally, the system may add a new instance to its instance base. The primary differences between case-based systems and instance-based learning algorithms are the tasks to which they are applied, and the complexity of the information that they store; cases are typically more complex than instances.

The simplest approach to error-correction is to save all information, whether or not an error was made. The

1. Retrieve the stored problem state most like the current problem state, according to the Retrieval metric.
2. Select from the available successor states the one most like the retrieved successor, according to the Selection metric.
3. Implement the selected action.
4. Receive feedback from the Oracle about which successor was best.
5. If CABOT did not select the best successor, perform error-correction:
6. (a) Try to adjust the Retrieval metric. If successful, go to 1.
7. (b) Try to adjust the Selection metric. If successful, go to 1.
8. (c) Add the current problem state and the best successor to the case base. Go to 1.

Figure 1: CABOT's problem-solving cycle.

GINA program [De Jong & Schultz, 1988] for playing OTHELLO adopts this approach, saving every board that it sees. One might expect GIN A eventually to become swamped with cases. Instead, the number of unique boards encountered by GINA in its play with opponents eventually stabilized at a small fraction of the number of possible boards.

Aha & Kibler (1989) have experimented with a family of instance filtering algorithms. The Prozimity algorithm saves all instances, while the NTGrowth algorithm dis­ cards instances that would be classified correctly or that appear to be noisy (i.e ., their classifications conflict with the rest of the data). In their tests on noisy data, the two algorithms were roughly equal; thus, equal performance was gained from fewer instances.

Both CYRUS [Kolodner, 1983] and PROTOS (Bareiss & Porter, 1987] dynamically adjust the structure of their case bases, and hence their retrieval mechanisms. CYRUS tries to maintain an appropriate organization of cases based upon an internal metric, expressed in terms of the number of adherents and exceptions to a given memory organization packet (MOP). In contrast, PRO­ TOS is given feedback by a benevolent teacher. The teacher provides the correct answer and may explain the relevance of individual features. The teacher also ap­ proves or rejects changes that PROTOS proposes, which prevents PROTOS from making serious mistakes. This feedback also enables PROTOS to prune its case-base by merging cases.

EACH (Salzberg, 1988] also stores exemplars (general­ ized, representative instances) to perform classification. When EACH encounters a new instance, the distance to each stored exemplar is measured. The closest exem­ plar determines the classification that EACH predicts. EACH generalizes and specializes its exemplars in re­ sponse to classification successes and failures. In addi­ tion, EACH uses a weighted distance function, similar to CABOT's, which is adjusted after every classification error. Thus EACH tunes its retrieval mechanism in re­ sponse to limited feedback from its environment.

CHEF [Hammond, 1986] adjusts its adaptation mech­ anism and also its retrieval mechanism by changing the way cases are indexed. CHEF receives very detailed feed­ back from a simulator, which it can analyze to identify the reason that an adapted case fails to meet its goals. After it repairs the adapted case, CHEF constructs demons that prevent it from making similar adaptation mistakes in the future. CHEF also indexes the repaired case according to the failures that the case avoids, as well as the goals the case satisfies.

Adding a case, adjusting the retrieval mechanism, and adjusting the adaptation mechanism are all ways of cop­ ing with failure. Few of the systems above make clear distinctions among causes of failure, and therefore it is rarely clear which mechanism should be adjusted.

Most systems that can adjust their retrieval or adapta­ tion strategies depend upon detailed feedback from the problem-solving environment. Requiring detailed feed­ back limits the environments in which those systems can operate. In contrast, CYRUS optimizes an internal met­ ric that does not use feedback from the environment. However, the inability to use feedback prevents a system from adjusting to the environment in which it operates. Therefore, an important research question is how a sys­ tem can adjust both its retrieval and adaptation mecha­ nisms using only limited feedback from the environment. The following sections present a system that addresses this question.

3 CABOT

The CABOT program was developed to investigate the problem of using limited feedback from a problem­ solving environment to distinguish different types of er­ rors in case-based reasoning. CABOT is designed for state-space search, where states are represented as fea­ ture vectors and problem-solving consists of repeatedly selecting and then executing one of a set of actions. Fig­ ure 1 outlines CABOT's problem-solving cycle. Cases consist of pairs of states ( s;, S:), where S: (the child) is -+ the desired successor to Sp (the parent).

State-space search is performed by starting at an ini­ tial state and repeatedly selecting successor states until a goal state is reached. The object of CABOT's reason­ ing is solely to determine, at each state in the search, the best successor state. CABOT does this by performing a restricted form of adaptation called selection: when a case is retrieved, it is used to select one from a set of successor states. By improving the quality of deci­ sions at each step in the search, CABOT improves its problem-solving performance.

The feedback available to CABOT is qualitative. A domain-dependent Oracle identifies the best successor state, but it does not explain its reasoning, nor does it score or order the rest of the available successors. CABOT's task is to use this limited feedback to improve its problem-solving performance. When CABOT's selec­ tion differs from that of the Oracle, its decision is con­ sidered a failure that it must correct. CABOT first tries to adjust its retrieval metric. If the retrieval metric can­ not or should not be changed, CABOT tries to adjust its selection metric. Changes to the retrieval and selec­ tion metrics are both subject to an assured consistency condition that only allows changes if the two metrics remain consistent with each other. CABOT checks for assured consistency by testing any changes on a random sample of problems that it has previously encountered; if a change to one of the metrics decreases accuracy, the change is discarded. If neither metric can be changed, CABOT adds a new case.

The next three sections discuss each step in detail.

3.1 Retrieval

Retrieval consists of identifying the case R = (14,, Ji;) --+ --+ whose Rp is closest to the current problem state Sp. Distance is determined by a weighted distance function dR --+ {the retrieval metric) whose weight vector W R can be adjusted during error correction. No similarity threshold is used; retrieval always returns a case.

3.2 Selection

It is rare for the retrieved successor state to exactly match any of the available successors of the current prob­ lem state. However, the exact pair of states is less im­ portant than their relationship; the pair of states en­ codes a transformation of the problem that presumably reduces the distance to a goal. Selection consists of iden­ tifying the successor state whose transformation of the current problem is most similar to the transformation represented by the retrieved. case.

The transformation of the problem from one state to another is represented by the difference between their ---+ --+ - feature vectors. The vector ARc = Rp - Rc represents the change in feature values that should ideally occur between the current problem state and the selected suc­ cessor state. The change that actually occurs between --+ the current problem state and each successor state Sc is ----+ --+ --+ represented as ASc = Sp - Sc. These relationships are illustrated in Figure 2.

Selection consists of identifying the successor state ----+ ---+ whose ASc is closest to ARc. Distance is determined by a weighted, signed distance function ds (the selection --+ metric), whose weight vector Ws can be adjusted during error correction. ds is defined as follows:

Ties are broken arbitrarily. No similarity threshold ts used; selection always selects a successor state.

3.3 Error Correction

After CABOT selects a successor state and carries out the associated action, it asks the Oracle to identify the desired action. If the Oracle agrees with CABOT's choice, no error correction is performed. Otherwise, CABOT considers its choice to be wrong and tries to correct itself. Error correction consists of the following:

1. CABOT checks to see if it retrieved the wrong case. It does so by conducting retrieval again with the added constraint that the retrieved case must cause it to select the desired successor state. The resulting --+- case N = (Np, Nc) is called a near miss. If no such case is found, CABOT proceeds to step 2.

If a near miss is found, CABOT tries to adjust the weighted Euclidean distance function dR so that the near miss state is closer than the retrieved state to the current problem state. The desired distance re­ lationship is:

This relationship may be expressed in terms of the --+ retrieval weight vector WR:

--+ CABOT adjusts WR by applying the absolute correction rule [Nilsson, 1965] to Equation 1.

Finally, CABOT verifies that the retrieval and selec­ tion metrics remain consistent, as discussed earlier. If they do, error correction terminates. Otherwise, the adjustments to the retrieval weight vector are discarded, and CABOT proceeds to step 2.

1. CABOT assumes that it retrieved the right case, but that the selection metric is wrong. It tries to adjust the selection weight vector, in a manner similar to that used for the retrieval weight vector. Adjust­ ment is based upon the desired relationship:

--+ --t Sec is the successor state chosen by CABOT. Sed is the desired successor state.

CABOT verifies that the retrieval and selection metrics remain consistent, as discussed earlier. If they do, error correction terminates. Otherwise, the adjustments to the selection weight vector are dis­ carded, and CABOT proceeds to step 3.

1. CABOT assumes that its error was due to missing information, and adds a new case. The new case consists of the current problem state and the desired successor state.

Weights used in the retrieval and selection metrics ----+ ---> (W R and Ws) are initially set to 1.0 and are adjusted by the error correction process. CABOT attempts to adjust its retrieval metric (step 1) before attempting to adjust its selection metric (step 2) because retrieval determines the cases that are used in selection. This ordering is de­ signed to make the retrieval metric converge before the selection metric.

4 An Experimental Domain: OTHELLO

CABOT has been been tested on OTHELLO, a two-player board game. Players alternate moves, and there are usu­ ally 60 moves in a game. Although the rules of OTHELLO are simple, the search space contains approximately 10 50 nodes, and the strategies can be quite complex. OTH­ ELLO was selected as a domain for CABOT because of its large search space, because it has been used as a domain by researchers in artificial intelligence [Rosen­ bloom, 1982; Lee & Mahajan, 1988; De Jong & Schultz, 1988], and because of the availability of immediate feed­ back after every move. Problem-solving in OTHELLO con­ sists of deciding which move to make next; on each cycle, CABOT selects a move, makes it, receives feedback, and possibly performs error correction.

The OTHELLO Oracle makes decisions by conducting a minimax search, using alpha-beta pruning, to a depth of 3-ply and then evaluating search states with a polyno­ mial evaluation function. The Oracle shifts to exhaustive search for the last 8 moves of the game.

Raw board positions are often considered too specific a representation for OTHELLO game states, so it is common to represent them with vectors of more abstract features. A feature is a numeric function that measures some im­ portant characteristic of a board position. CABOT and its opponents use a set of features common to OTHELLO­ playing programs: mobility, potential mobility, corner squares, X squares, etc. [Rosenbloom, 1982] Hereafter, "board" will be used to denote this feature vector, rather than the actual raw board configuration. The OTHELLO Oracle uses a larger and more comprehensive set of fea­ tures than is used by CABOT.

4.1 LATCBR: A Pure Case-Based Opponent

One of CABOT's opponents is a case-based reasoning system that uses a very simple version of a claim-lattice [Rissland & Ashley, 1987] to determine the best move. This opponent, called LATCBR, orders the cases into a lattice in which the cases closest to the root are those with maximal subsets of features exactly matching the current problem state. LATCBR contains no built-in indices to prune this set, nor does it have any way of judging which of the nodes at a given level are best for the player. It therefore treats all nodes occurring closest to the root as equal, and discards the rest. The cases contained in these nodes are all considered retrieved.

The claim-lattice was designed for comparing and con­ trasting competing alternatives. It does not offer a straightforward mechanism for selecting a single alter­ native, nor is there any a priori reason for selecting one alternative as best. The approach adopted for LATCBR is to adapt each case to the current situation by iden­ tifying the move that it matches most closely, and then make the choice that is recommended by the majority of the cases, with ties broken randomly. The degree of match between a case and a given move is determined by the number of features on which they exactly match.

LATCBR does not attempt to correct either its re­ trieval function or its adaptation function when it makes a mistake. When the Oracle disagrees with its chosen move, LATCBR adds a new case.

4.2 PIL: A Pure Inductive Learning Opponent

The PIL opponent uses an inductive learning algorithm to improve a heuristic evaluation function h over search states. PIL selects the succe~sor to the current problem state for which his greatest; ties are broken arbitrarily.

After each selection, PIL asks the Oracle to identify the desired successor. If the desired successor differs from PIL's selection, PIL considers its choice to be wrong and tries to correct h. It does so by adjusting h so that the desired successor state is rated more highly than all other successor states.

PIL's evaluation function h is a weighted sum of fea---+ ture values. Weights in the weight vector W p r L are initially set to 1.0. Qualitative feedback can be used correct the weights, as shown below:

PIL adjusts the weight vector by applying the absolute correction rule [Nilsson, 1965] to Equation 2.

5 Experiments and Results

Four experiments were run to determine the relative ef­ fectiveness of the pure case-based (LATCBR), adaptive case-based (CABOT), and pure inductive learning (PIL) move selection strategies. The experiments were de­ signed to examine three characteristics of each strategy:

• Effectiveness: How effective was it for playing OTHELLO? Effectiveness was measured by the win/loss ratio, and by the average discs taken per game.
• Decision Accuracy: How often did it agree with the Oracle's choice?
• Growth of Case Base: For the case-based sys­ tems, how quickly did the case base grow?

Each tournament began with empty case bases and unweighted linear threshold units (i.e., all weights set to 1.0). At the beginning of each game, one player was randomly selected to make the first move. Each player was permitted to learn from both its own moves and its opponent's moves throughout the tournament. By train­ ing on both sets of moves, a learning program receives balanced training because it can train on better game states than it might achieve on its own.

Games were played until either 100 games had been played, or until the Oracle's best game had been en­ countered. The latter stopping condition is important for case-based competitors. If a case- or instance-based game-playing program is permitted to observe an oppo­ nent that follows a fixed strategy, it will eventually mem­ orize that opponent's best game. Once the opponent's best game is memorized, the case-based program cannot lose more than 50% of the subsequent games. When both opponents are case-based and both are learning from a fixed Oracle, they will eventually begin playing a single game repeatedly. All of the tournaments reported below were ended if this condition occurred. The results from the four tournaments are summarized in Tables 1 and 2.

Table 1 shows the number of games won, lost and tied by each player during the four tournaments. It demon­ strates that CABOT's performance is superior to that of the pure case-based system (LATCBR) and the pure inductive learning system (PIL) in playing OTHELLO. It also shows that the performance of PIL is superior to the performance of LATCBR. This result is unexpected because the training data are not linearly separable. We expected PIL to perform more poorly, and are unable to explain why it did not. The performance of CABOT

against the Oracle is not surprising. However, it is in­ teresting to note that it took CABOT just 26 games to discover the Oracle's best game. After that point , the two opponents began playing the same game repeatedly, each losing exactly 50% of the games.

OTHELLO players are rated both on how often they win and on the magnitude of the score. Table 2 reports the average number of discs won by each player in each tournament. The figures confirm that the hybrid sys­ tem is better at selecting moves than either of its pure opponents.

Figure 3 shows the decision accuracy of CABOT and LATCBR. Decision accuracy is the percentage of time that a player's chosen move is judged to be the best by the Oracle. This graph shows a running average of decision accuracy through 25 games, and confirms that CABOT's performance is better than LATCBR's be­ cause its decisions tend to be more accurate. The train­ ing data for both systems are identical, so the only fac­ tor that can account for this difference is CABOT's im­ proved retrieval and adaptation strategies. The improve­ ment in CABOT's retrieval and adaptation strategies oc­ curs quickly, usually within the first game or two. In con­ trast, LATCBR is initially error-prone but its accuracy continues to improve as its case base grows. Figure 3 shows that the difference between the two accuracies de­ creases as the number of games increases. This confirms the intuition that having enough cases is asymptotically as good as having a smaller number of cases with better retrieval and adaptation strategies.

Superior performance is one result of adjusting re­ trieval and adaptation strategies. Another result is the difference in the growth of the case base. Figure 4 shows this growth during the CABOT vs LATCBR tourna­ ment. The CABOT case base tends to be about half the size of the LATCBR case base. Neither case base shows any sign of stabilizing. Continued growth may be due to the small number of games that have been played. The search space for OTHELLO is large (about 10 50 legal boards), so it may be unrealistic to expect either case base to stabilize within 24 games.

Results vary from tournament to tournament, because of the effects of learning, and because the Oracle makes random choices when it has two or more equally good moves. We have observed variation in the specific num­ bers of games won and lost by each move selection strat­ egy. However, the relative performance of each strategy is consistent. CABOT is superior both to LATCBR and PIL, and PIL is superior to LATCBR.

We have also tested CABOT against opponents that use other inductive learning techniques to guide move se­ lection. One of these opponents used the ID3 algorithm for building decision trees [Quinlan, 1986) . One problem with using ID3 for this task is that the OTHELLO boards are described by numeric features, whereas ID3 is in­ tended for symbolic attributes. We experimented with several methods of converting numeric data to symbolic attributes, including Quinlan's method (1986), Vapnik's method (1982), and our own manual method. None of these methods for creating symbolic attributes was both computationally feasible and more effective than the weighted sum evaluation function of the PIL system.

6 Conclusions

CABOT was developed to investigate the hypothesis that case-based reasoning systems would benefit from the ability to dynamically adjust their retrieval and adaptation mechanisms. CABOT reasons from cases for the purpose of guiding state-space search. State-space search is different than traditional CBR tasks because the problem-solver's task is to repeatedly identify the successor state to explore next . As a result, CABOT performs a restricted form of adaptation, in which the retrieved case is used to select one of a set of known alternatives.

One of the assumptions of this work is that feedback from the environment is necessary for making proper ad­ justments to retrieval and selection mechanisms. The feedback provided to CABOT and its opponents consists of the best move as identified by the Oracle. However, no information is provided that might suggest why one move was better than another. This feedback is quite weak when compared with the detailed information available to systems like CHEF [Hammond, 1986) and PROTOS [Bareiss & Porter, 1987).

The empirical results reported in this paper confirm several hypotheses. First, they demonstrate that the ability to tune retrieval and selection mechanisms leads to both a smaller case base and better performance. They suggest that traditional CBR systems may be sav­ ing more cases than they really need. Second, they demonstrate that detailed feedback from the environ­ ment, while useful, is not always necessary to make these adjustments. Sometimes it is enough just to know the desired result. Finally, the performance of CABOT when played against pure inductive and pure case-based learn­ ing opponents illustrates that a hybrid architecture can overcome the weaknesses of opponents of each type.

Acknowledgements

Support for this work was provided by the Office of Naval Research through a University Research Initiative Pro­ gram, under contracts N00014-86-K-0764 and N0001487-K-0238. Comments by David Aha and Bernard Sil­ ver were especially valuable. We thank Jeff Clouse for providing the Oracle program.