Case-Based Reasoning Research Paper

1. Case-Based Reasoning As Cognitive Model

Initial research on CBR was motivated by observations of how humans remember, reason, and learn from experiences. People who encounter surprising events are often reminded of similar past events and use these remindings to help them understand and respond to the new situations (Schank 1982). For example, a doctor whose patient has an unusual reaction to a medicine might be reminded of a previous patient who had similar reaction. Remembering the treatment used for the prior patient suggests a candidate treatment for the new patient; remembering the outcome of the previous treatment helps to predict the new outcome and warns of potential pitfalls to avoid.

Psychological studies provide evidence supporting human use of CBR for a wide range of problem-solving tasks such as learning programming, performing mathematical problem solving, explaining anomalous events, and decision-making (see Leake 1998) for examples of this work). Another use of CBR is for classification or interpretation. For example, in legal reasoning in the American legal system, prior cases are the basis for legal judgments: lawyers build arguments about how to interpret rules of law by comparing and contrasting precedent cases to the current situation (see Ashley and Rissland (1988) and Legal Reasoning Models).

Research on CBR as a cognitive model studies the knowledge and processes that underlie human CBR, addressing topics such as memory organization, similarity assessment, and analogical mapping (Kolodner 1993, Leake 1998). Computational models developed in this work illuminate functional constraints on reasoning processes and provide testable hypotheses about human reasoning for psychological investigation.

2. Steps In Case-Based Problem-Solving

Computer CBR systems have been developed for numerous tasks including planning (Hammond 1989, Veloso 1994), design (Pu and Maher 1997), and explanation (Schank et al. 1994). Regardless of the specific reasoning task, any CBR system retrieves relevant prior cases, adapts their lessons to fit the new situation, evaluates and applies the result, and retains the results of processing as new cases to guide future reasoning. Thus, computer models of CBR must account for four main processing steps: retrieval, adaptation, evaluation application, and storage.

2.1 Retrieval

In order to facilitate retrieval of relevant cases, stored cases are organized by indices characterizing circumstances in which the cases are likely to be relevant. For example, in a medical CBR system to suggest treatments for illnesses, treatment cases could be indexed by the diseases they treat and the characteristics of patients (e.g., age) that tend to determine whether a given treatment is appropriate. Given a new problem to solve, a case-based reasoner first performs situation assessment to analyze the input problem and describe it in terms of the indices used to organize cases. Retrieval algorithms use the description to retrieve the cases in memory expected to be most relevant. For example, nearest-neighbor retrieval algorithms select the most similar prior cases according to a metric that weights features by their relative importances. Alternatively, case libraries may be organized into discrimination networks to enable retrievals based on only a small number of feature comparisons. After candidate cases have been retrieved, a finer-grained similarity assessment process is often used to identify the best candidates and to determine differences requiring adaptation

2.2 Adaptation

The case adaptation step revises the lessons of the retrieved case (or revises and combines the lessons of multiple retrieved cases) to generate an appropriate new solution. For example, a doctor might have to adopt a prior treatment by reducing the dosage if the prior patient was an adult and the current patient is a child, or might combine elements of prior treatments to address multiple complaints. Computer CBR systems often use rule-based reasoning to determine how to transform prior solutions. In interpretive CBR, the case-based reasoner does not modify the retrieved case, but instead develops justifications for why the prior interpretation applies (or does not apply) to the new situation.

2.3 Evaluation Application

Tentative results of case adaptation are evaluated to assess the appropriateness of the new solution and to determine whether additional changes are needed, possibly resulting in a cycle of repeated adaptation and evaluation. Once a solution is judged acceptable, it is applied to the real problem. If the solution fails, it may be repaired, reevaluated, and reapplied.

2.4 Storage

Each processing episode of a CBR system, whether resulting in success or failure, is stored to guide future reasoning. Cases containing successful solutions suggest solutions for similar future problems, while cases storing failures provide warnings of problems to avoid and information on how to avoid them. The storage step packages information about the problem, solution and its results in a new case. It also assigns indices for the case and places it in the case library (also called the ‘case base’) for future use.

3. Research Issues

3.1 Retrieval And Similarity Assessment

Effective case retrieval depends on appropriate retrieval algorithms, well-organized case bases, and indices that are useful for the current task. In case-based problem solving, cases are indexed by information about the problems they solve. For example, a case-based planning system may index plan cases by the goals they achieve and constraints they satisfy. Indices should be predictive of the relevance of cases and should involve features of problems that are likely to be known to the reasoner; both abstract and concrete features may be useful. A crucial research issue in CBR is developing appropriate indexing vocabularies for particular reasoning tasks. In order to retrieve useful cases for novel situations, methods are also needed for reformulating or transforming indices to widen search when no directly relevant cases are available. There is also considerable interest in replacing traditional measures of similarity with similarity criteria that directly reflect pragmatic needs by predicting which prior cases will be easiest to adapt to fit the new situation (e.g., Smyth and Keane 1998). Research on retrieval algorithms investigates methods for achieving rapid retrievals from large case bases (e.g., by exploiting parallel algorithms).

3.2 Case Adaptation

Developing case adaptation rules is often difficult because of knowledge acquisition problems: the needed knowledge may not be available or may be difficult to codify. Consequently, improving case adaptation methods is a fundamental challenge for CBR. Research areas include applying machine learning techniques to automatically generate case adaptation rules; applying CBR to a CBR system’s internal processing, to adapt cases based on prior adaptation experiences rather than rules; using a derivational analogy process to account for new circumstances by replaying a prior solution-generation process, rather than revising a prior solution (Veloso 1994); and applying artificial intelligence methods such as constraint-based reasoning to guide the adaptation process. It is important to note that sufficiently powerful case adaptation can enable cases to be used in very novel ways; research on flexible retrieval and adaptation processes has given rise to CBR models of creative problem solving.

3.3 Case-Base Maintenance

As CBR systems receive long-term use, keeping the case base accurate becomes an important problem. Likewise, as cases are accumulated, it may be necessary to reorganize or update the case base in order to improve its coverage of important problems and to avoid slow retrievals. This has led to considerable interest in methods for improving case quality and retrieval efficiency by strategic deletion, revision, and addition of cases to a case base. Because cases are increasingly generated by multiple distributed sources (e.g., different offices of an organization), additional issues concern how to update and access distributed case information.

3.4 Integration With Other Methods

CBR systems may be integrated with other systems and approaches—both artificial intelligence systems and other systems—to leverage off the strengths of each. For example, case-based and rule-based reasoning may be integrated with each other, with cases used to guide interpretation of rules or to suggest targets for rule-based reasoning. CBR may also be used for speedup learning, with initial rule-based problem solving building up a case library that can then be used instead of rules, bypassing costly reasoning from scratch, or to avoid errors by storing exceptions to rules. Conversely, rule-based reasoning may be useful to augment the case library and extend the range of problems that a CBR system can solve.

4. CBR Technology

Applications of CBR include both autonomous and interactive systems. As observed by Kolodner (1993), human users are often adept at evaluating the relevance of prior cases and applying their lessons, but may lack the experience needed to acquire a sufficient set of cases. On the other hand, case adaptation and evaluation are difficult for CBR systems, but practical methods exist for accessing large case libraries. These complementary strengths have led to increasing focus on case-based ‘retrieve and propose’ systems that support human reasoners by providing them with relevant prior cases to aid their decision making (cf. Decision Support Systems). For example, case-based ‘help desk’ systems are used widely to aid telephone support personnel who diagnose customer problems, and commercial CBR ‘shells’, are available to facilitate the development of such applications (Watson 1997). As novel problems and solutions are added to the case base during use, the system builds a sharable corporate memory, of cases, aiding corporate knowledge management.

CBR is also increasingly applied to electronic commerce. For example, case-based support systems are used during on-line purchases of computers, to help buyers configure their systems by presenting similar past configurations as a starting point for them to modify. This helps users find a good match to their needs, even if they do not know all the important features of the product they are ordering.

In addition, the CBR cognitive model and CBR principles are guiding the design of educational systems by, for example, suggesting when useful learning is most likely to occur and how to retrieve examples to support that learning. Likewise, CBR is being applied to accessing hypermedia and on-line repositories of information—providing indexing vocabularies and example-based query interfaces—and is being used to focus information retrieval, in order to extract task relevant information from large-scale information sources. Another active research area, textual CBR, develops methods for facilitating knowledge acquisition by automatically capturing and indexing cases in textual form. Leake (1996) and Lenz et al. (1998) present projects illustrating these applications areas.

5. Relationship To Other Artificial Intelligence Methods

Much artificial intelligence research focuses on methods for generating new solutions from scratch by chaining together general rules. CBR is an interesting alternative for a number of reasons, including: (a) simplifying knowledge acquisition (experts often find it difficult to provide rules for their actions but can easily provide examples, and CBR systems can be fielded with small case libraries and learn additional cases during use); (b) providing natural explanations of decisions (by accounting for decisions in terms of actual previous examples, rather than in terms of rules that users may not understand or trust); (c) increasing problem-solving efficiency by reusing the results of prior reasoning; and (d) facilitating system development in domains that are hard to codify in terms of general rules (e.g., because the rules would have too many exceptions). In CBR, traditional rule acquisition issues are replaced by issues of capturing and representing reasoning episodes, selecting similarity and indexing criteria, and capturing case adaptation knowledge.

The learning done by CBR systems strikes a middle ground between knowledge-poor and knowledge-rich learning approaches. Unlike knowledge-poor inductive learning methods, CBR exploits domain knowledge (e.g., many CBR systems use explanations to guide indexing and adaptation). Unlike knowledge rich methods, such as explanation-based generalization, CBR can still be in the absence of a rule-based domain theory.

In its emphasis on building up knowledge by learning, CBR research is in the same spirit as research on neural networks. However, CBR contrasts in storing and reasoning from examples rather than storing only learned generalizations. Also, CBR performs ‘lazy learning.’ Rather than immediately generalizing training instances and discarding the examples, as in, for example, explanation-based and neural network learning, CBR stores cases with minimal processing and processes them further only if and when adaptation is needed to solve new problems. In addition, unlike neural networks, case-based reasoning systems can change Behavior immediately in response to new examples: a single correct example of dealing with a situation, and no further training, is all that is needed for the system to process that situation correctly in the future.

6. Conclusion

A case-based problem solver solves new problems by retrieving stored problem cases and adapting their lessons to fit new circumstances; it learns by storing new episodes for future use. This process can provide robust reasoning and learning even in domains that are hard to codify in rule-based form. CBR research has provided computational cognitive models of human information processing, artificial intelligence techniques, and information technology for a wide range of task domains.

The CBR cognitive model is discussed in Kolodner (1993) and Leake (1998). A volume edited by Leake (1996) surveys the field with chapters on issues and applications in tasks such as decision aiding, knowledge navigation, design, diagnosis, and education; Kolodner (1993) provides an in-depth examination of key issues; and a volume edited by Riesbeck and Schank (1989) includes chapters on important early CBR research projects and ‘micro-versions’, of the computer programs those projects developed. The process of developing CBR applications is described by Watson (1997). A volume edited by Lenz et al. (1998) presents chapters on CBR technology for tasks including supporting electronic commerce and textual CBR.

Bibliography:

1. Ashley K D, Rissland E 1988 A case-based approach to modelling legal expertise. IEEE Expert 3(3): 70–7
2. Hammond, K J 1989 Case-based Planning: Viewing Planning as a Memory Task. Academic Press, Boston, MA
3. Kolodner, J 1993 Case-based Reasoning. Kaufmann, San Mateo, CA
4. Leake D B (ed.) 1996 Case-based Reasoning: Experiences, Lessons, and Future Directions. AAAI Press, Menlo Park, CA
5. Leake D 1998 Cognition as Case-based Reasoning. In: Bechtel W, Graham G (eds.) A Companion to Cognitive Science. Blackwell, Oxford, UK, pp. 465–76
6. Lenz M, Bartsch-Sporl B, Burkhard H D, Wess S (eds.) 1998 Case-based Reasoning Technology: From Foundations to Applications. Springer, Berlin
7. Pu P, Maher M L (eds.) 1997 Issues and Applications of Case-based Reasoning in Design. Erlbaum, Mahwah, NJ
8. Riesbeck C K, Schank R C 1989 Inside Case-based Reasoning. Erlbaum, Hillsade, NJ
9. Schank, R C 1982 Dynamic Memory: A Theory of Reminding and Learning in Computers and People. Cambridge University Press, Cambridge, UK
10. Schank R C, Riesbeck C K, Kass A (eds.) 1994 Inside Case- based Explanation. Erlbaum, Hillsdale, NJ
11. Smyth, B, Keane, M T 1998 Adaptation-guided retrieval: Questioning the similarity assumption in reasoning. Artificial Intelligence 102(2): 249–93
12. Veloso M M 1994 Planning and Learning by Analogical Reasoning. Springer, Berlin
13. Watson, I 1997 Applying Case-based Reasoning: Techniques for Enterprise Systems. Kaufmann, San Francisco, CA