W2A-039 Case-based reasoning-0.txt
Complexity of Adaptation in Real-World Case-Based Reasoning Systems

1 Introduction

Case-Based Reasoning (CBR) is a reasoning method that uses experiential knowledge, in the form of cases, to solve problems. When faced with a new problem a CBR system will retrieve a case that is similar, and, if necessary, adapt it to provide the desired solution. Its current popularity as a problem solving paradigm is representative of the shift that has occurred in automated problem solving research; researchers are beginning to move from simple, "toy" domains to complex, real world domains. With this move has come a recognition of the many inadequacies of traditional problem solving approaches, and assumptions previously deemed reasonable have proved invalid in complex, dynamic real world domains. Case-based reasoning methods have proved useful in dealing with many of these problems and have had considerable initial success in real world problem solving endeavours.

Researchers have organised problem solving into three main classes. In order of increasing complexity, these are: simple, routine, and innovative. Simple problem solving activities are characterised by domains whose simplicity facilitate solution generation in a fairly straightforward fashion; there is a relatively direct inference path from problem specification to problem solution. With routine problem solving, domains are more complex and often incomplete, problem specifications are conceptually quite distant from their solutions, and additional computational expense is incurred due to conflicts between dependent domain objects. The most difficult activity, innovative problem solving, is identified by patchy domain models, intricate solution paths through the problem-space, and a considerable amount of backtracking due to interaction problems.

The aim of this paper is to characterise the relationship between case-based reasoning and problem solving tasks of differing complexity. This relationship is discussed in detail in the next sections. Sections three, four and five solidify this discussion by introducing three real CBR systems concerned with simple, routine, and innovative problem solving.
2 Problem Solving Complexity and CBR
Our perspective on problem solving is concerned with search-based problem solving techniques. Such problem solvers search a space of "world models" or "problem states" (the problem-space) to find one in which all the problem goals have been achieved (the goal state). Search proceeds through the problem-space by the application of state-transforming operators. The task of the problem solver is then to find some sequence of operators that transform the initial state into the goal state. The complexity and cost of automated problem solving is well studied and there are many ways that it can be estimated. The classic measure is the amount of search which has to be carried out in developing a solution to a problem.

Essentially, there are two search related problems associated with conventional problem solving methods. The first, which we term the operator chaining problem, is basically the problem of searching forward through the problem-space to find the appropriate sequence (chain) of operators with which to solve the target problem. Relieving this problem has been (and still is) the objective of much research and has resulted in a range of relatively successful techniques (e.g. heuristic search, hierarchical planning, least commitment strategy, goal regression etc.). Further computational complexity arises from the operator conflict problem. As a planner interacts with its domain it receives a stream of conjunctive goals. Were these goals independent of one another the cost of problem solving would be linear with the number of goals. The reality is somewhat different. Operator conflicts can result in unfavourable interactions between goals. Under such conditions the problem solver must backtrack over earlier work in order to plan a new solution which avoids these interactions. If somehow the problem solver could learn specific sequences of actions that overcome interaction problems in certain situations, the cost per goal could be reduced in the long run.

Case-based reasoning methods attempt to address both of these problems. By constraining the problem-space search, it reduces the operator chaining problem; the retrieval of a similar case constitutes a considerable 'jump' into the problem space thereby eliminating many potential routes from the search. Furthermore, CBR is potentially a more efficient constraint method than conventional approaches (e.g. heuristic evaluation etc.) whose scope is more local, pertaining to individual problem space states rather than whole areas. Backtracking due to bad interactions may also be avoided, thereby relieving the operator conflict problem. Effectively, cases can be viewed as 'canned' solutions where operator conflicts have been resolved in certain well defined situations As long as the retrieved case is sufficiently similar to the target relatively few conflicts should arise due to modifications made during adaptation.

An Overview of CBR

In CBR, problem solving knowledge is characterised as a set of episodes each representing the solution to a specific problem situation. A new problem (the target) is solved by retrieving a similar episode (base case) from memory, and its solution is then modified to conform with the target situation. Cases are represented by features and relationships and case retrieval depends on matching these case representations. It can be seen from the following description of the stages in CBR that the retrieval stages is a two stage process:-

Representation:: Cases are represented by features and operators (relationships). The features may be surface or abstract features and typically the more predictive features will be selected for indexing.

Base Filtering: A small number of candidate episodes which are considered contextually similar to the target situation are selected from the case base. The case base will often be organised as a discrimination network (D-net) to facilitate this.

Case Selection / Mapping: This second stage will select a case from this candidate set based on a more detailed comparison of the cases. A mapping between the base and target cases may also be produced at this stage.

Adaptation: Once the best case from the case base has been selected it must be adapted to fit the problem in hand. In the simplest situations, for instance diagnosis, this adaptation may be trivial and the base case may apply without modification. Adaptation may be very complex in more difficult problem domains, e.g. non routine design.

2.2 A CBR Perspective on Complexity Earlier we introduced the notion of a number of types of problem solving: simple, routine, and innovative. In fact, we can view these as a continuum of problem solving tasks (Figure 1) organised in terms of computational complexity. As illustrated, the relative contribution of the operator chaining and operator conflict problems varies across this continuum. Due to the simplicity of their domains, simple problem solving tasks incur the bulk of their cost from the operator chaining problem; the lack of domain complexity leads to few conflicts so little time is spent backtracking. At the other end of the continuum, the complexity of the domains of innovative problem solving tasks results in the operator conflict problem being very prominent (and expensive to resolve), with proportionately less time spent on the operator chaining problem.
<%> Figure 1
<!--%-->
The basic tenet of CBR is that, rather than solve a problem from first principles, it may be easier to retrieve a similar problem and transform the solution to that problem. In Figure 2 we attempt to illustrate these trade-offs graphically. SP' represents the specification for a new problem and SL' is the solution to that problem. FP' represents the search process that establishes this solution from first principles - the task we wish to avoid. A CBR solution is worthwhile if the retrieval task R, and the adaptation task A are simpler than FP'.

In the later sections of this paper we will examine three CBR systems that differ in the complexity of the transformation task A:-

Substitution Adaptation:: This is the simplest type of adaptation and merely involved substituting some of the parameters in the solution.

Transformational Adaptation:: This adaptation is more complex and will involve structural changes to the solution.

Generative Adaptation:: This is the most complex adaptation and is not perfectly represented by the diagram. The adaptation process involves a rework of the reasoning process FP in the context of the new problem situation represented by SP'.

From a case-based reasoning perspective there is a relationship between the complexity of the problem solving task and the complexity of the CBR adaptation process. CBR systems concerned with simple problem solving tasks will typically require simple, substitutional adaptation; the retrieved case will typically be very close to the target and consequently will require only very basic substitutive adaptation, with little or no chance of bad interactions occurring. With routine problem solving tasks, the retrieved case, while being similar to the target, will probably require substantial modification possibly changing some structural elements of the retrieved solution (transformational adaptation), and innovative problem solving tasks extensive modifications are necessary during adaptation so interactions are unavoidable and difficult to resolve. To accommodate this adaptation complexity it is generally necessary to augment cases with detailed knowledge such as the reasoning trace structures of Carbonell's Derivational Analogy.

3 Rachman: Substitutional Adaptation

Simple problem solving tasks are characterised by well-defined domain models, and a relatively direct inference path from problem specification to problem solution. Case-based reasoning methods are particularly well suited to such tasks as there is often a rich set of cases to draw upon during problem solving. The retrieved case is typically very similar to the target problem and consequently the adaptation problem is relatively uncomplicated; in general modifying the attributes of solution elements will suffice without the need to change the overall solution structure.

3.1 A Brief Overview of Rachman Figure 3 shows two example cases from a case-based system called Rachman that can predict the selling value of a house given some details about it. The system contains a large case base of houses and their selling prices and, given a house description, it will retrieve a case or a set of cases describing similar houses and their selling prices. These prices can be adjusted depending on differences between the target and base cases to estimate the price of the target house. This system is comparatively straightforward but is equivalent to a host of potential CBR applications, for example loan risk assessment and help-desk assistants. The complexity of this problem is greatly reduced by having a well populated case base, so that good matches can be found and the required adaptation is not difficult.

The cases are divided into two sets of features, the index features and the internal features. The index features are the most strongly predictive features and form the basis for the D-Net (Figure 4). The main problem with the D-Net approach is that it forces a strict ordering of the index features, in this example the cases might be organised first under location, then number of bedrooms, etc. However, different users may have different priorities; some, for instance, might consider the number of bedrooms to be more important than location. In addition, it will not be possible to retrieve matches for cases that have missing features as the retrieval process will not be able to search below the level of that feature in the network.

These problems are largely solved by introducing redundancy into the D-Net. This means that the network supports alternative orderings on the index features (see Figure 4). The extent to which redundancy can be introduced into the network is limited because the size of the network grows in proportion to the number of orderings supported. Retrieval in Rachman returns clusters of cases and the cases are ranked according to their frequency of occurrence in these clusters.

3.2 Substitutional Adaptation in Rachman It is assumed with this system that the case base is well populated so that near or exact matches can be found. This means that the adaptation is comparatively straightforward using substitution specialists that adjust the price based on differences between the base and target cases. For instance a substitution specialist may add or remove the value of having a conservatory. The important point is that the effect of this adjustment is quite local and does not cause complex interactions.

D&/ej&\a Vu: Transformational Adaptation

In a CBR system for routine problem solving, retrieved cases, while being comparatively similar to the target, will probably require substantial structural modification. Consequently a limited opportunity exists for bad interactions to occur. Carbonell (Carbonell, 1983) characterises such problem solvers as belonging to the realm of Tranformational Analogy. Essentially, the adaptation stage can be considered as a solution transformation problem. Finding the appropriate transformation is itself a problem-solving process, but in a different problem space. The states of this transformation-space (T-space) are problem solutions, as opposed to solution states. The transformation-space operators (T-operators) are atomic solution transformation operators (e.g., Substitute Solution Step, Delete Solution Step, Insert Solution Step, Reorder Solution Steps). And the job of adaptation is to find the appropriate sequence of T-operators which will transform the retrieved solution into the desired target solution (See Figure 5).
