Case-Based Reasoning

Case-based reasoning is one of the fastest growing areas in the field of knowledge-based systems and this book, authored by a leader in the field, is the first comprehensive text on the subject. Case-based reasoning systems are systems that store information about situations in their memory. As new problems arise, similar situations are searched out to help solve these problems. Problems are understood and inferences are made by finding the closest cases in memory, comparing and contrasting the problem with those cases, making inferences based on those comparisons, and asking questions when inferences can't be made.

This book presents the state of the art in case-based reasoning. The author synthesizes and analyzes a broad range of approaches, with special emphasis on applying case-based reasoning to complex real-world problem-solving tasks such as medical diagnosis, design, conflict resolution, and planning. The author's approach combines cognitive science and engineering, and is based on analysis of both expert and common-sense tasks. Guidelines for building case-based expert systems are provided, such as how to represent knowledge in cases, how to index cases for accessibility, how to implement retrieval processes for efficiency, and how to adapt old solutions to fit new situations.

This book is an excellent text for courses and tutorials on case-based reasoning. It is also a useful resource for computer professionals and cognitive scientists interested in learning more about this fast-growing field.

Case-Based Reasoning

by Janet Kolodner

Preface

Part I Background

1 What is Case-Based Reasoning?

1.1 Introduction

1.2 What Is a Case?

1.3 Major CBR Issues: Composition and Specificity

1.4 Processes and Issues

1.4.1 Case Retrieval

1.4.2 Proposing a Ballpark Solution

1.4.3 Adaptation

1.4.4 Evaluative Reasoning: Justification and Criticism

1.4.5 Evaluative Testing

1.4.6 Memory Update

1.5 Applicability of Case-Based Reasoning

1.5.1 Range of Applicability and Real-World Usefulness

1.5.2 Advantages and Disadvantages of CBR

1.6 Cognitive Model, or Methodology for Building Expert Systems?

1.6.1 Case-Based Reasoning and People

1.6.2 Building a Case-Based Reasoner

1.7 A Note to Readers

1.8 Summary


2 Case Studies of Several Case-Based Reasoners

2.1 CHEF

2.2 CASEY

2.3 JULIA

2.4 HYPO

2.5 PROTOS

2.6 CLAVIER

2.7 Retrieval-Only Aiding and Advisory Systems

2.7.1 A Hypothetical Architect's Assistant

2.7.2 A Hypothetical Mediator's Assistant

2.7.3. Some Real Aiding Systems

2.8 Summary


3 Reasoning Using Cases

3.1 Case-Based Inference

3.2 CBR and Problem Solving

3.2.1 CBR for Planning

3.2.2 CBR for Design

3.2.3 CBR for Explanation and Diagnosis

3.3 Interpretive CBR

3.3.1 Justification and Adversarial Reasoning

3.3.2 Classification and Interpretation

3.3.3 Interpretive CBR and Problem Solving: Projection

3.4 Case-Based and Other Reasoning Methods

3.4.1 Case-Based and Rule-Based Reasoning

3.4.2 Case-Based and Model-Based Reasoning

3.5 Summary


4 The Cognitive Model

4.1 A Short Intellectual History

4.2 Dynamic Memory

4.2.1 Reminding

4.2.2 MOPs

4.2.3 TOPs

4.2.4 Indexing

4.2.5 Reminding Revisited

4.3 Beyond Intentional Situations: Dynamic Memory and Model-Based Reasoning

4.4 Some Running Cognitive Models

4.4.1 CYRUS: A Model of Reconstructive Memory

4.4.2 CELIA: A case-Based Approach to the Passage from Novice to Expert

4.5 Summary of Claims

4.5.1 The Structure and Organization of Knowledge

4.5.2 Primary Processes

4.5.3 Dynamic Memory and Learning

4.5.4 The Structure and Role of General Knowledge

4.6 Evidence of Case-Based Reasoning in People and Its Implications

Part II The Case Library: Representing and Indexing Cases

5 Representing Cases

5.1 Components Parts of Cases

5.1.1 The Content of Problem Representations

5.1.2 The Content of Solutions

5.1.3 The Content of Case Outcomes

5.2 The Issue of Case Presentation

5.3 Case Studies

5.3.1 MEDIATOR: Highly Structured Representations, Broad But Not Deep

5.3.2 CASEY: Concentrating on Situation Description and Solution, Proposition-Based Representations

5.3.3 CHEF: Representing a Solution Plan

5.3.4 JULIA and KRITIK: Representing Design Cases, Concentrating on the Solution

5.3.5 HYPO's Representations: Concentrating on Situation Description

5.3.6 Formlike Representations

5.4 Advanced Issues

5.4.1 Grain Size of Cases: Monolithic Cases or Distributed Cases?

5.4.2 Evolving Problem Descriptions

5.4.3 Boundaries of Cases: Representing Cases in Continuous Environments

5.5 Summary


6 Indexing Vocabulary

6.1 Qualities of Good Indexes

6.1.1 Predictive Features

6.1.2 Abstractness of Indexes

6.1.3 Concreteness of Indexes

6.1.4 Usefulness of Indexes

6.2 Choosing Vocabulary

6.2.1 Determining Coverage

6.2.2 Methodologies for Choosing Index Vocabulary

6.2.3 The Functional Methodology for Choosing Indexing Vocabulary

6.3 Toward a Generally Applicable Indexing Vocabulary

6.4 The Universal Index Frame: A Vocabulary for Intentional Situations

6.4.1 Specifying Content

6.4.2 Specifying Context

6.5 Generally Applicable Indexing Schemes: Lessons Illustrated by the UIF

6.5.1 Indexes Correspond to Interpretations of Situations

6.5.2 Capturing Relationships Among Components of an Episode

6.5.3 The Specificity of Indexes

6.5.4 Surface Features and Abstract Features in Indexing and Reminding

6.5.5 Modularity and Redundancy in an Indexing Scheme

6.5.6 Describing Cases and Indexing Cases: The Differences

6.6 Beyond the Universal Index Frame

6.7 Summary


7 Methods for Index Selection

7.1 Choosing Indexes by Hand

7.2 Choosing Indexes by Machine

7.3 Choosing Indexes Based on a Checklist

7.3.1 Difference-Based Indexing
7.4 Difference-Based Indexing

7.5 Combining Difference-Based and Checklist-Based Methods

7.6 Explanation-Based Indexing

7.6.1 Creating an Explanation

7.6.2 Selecting Observable Features

7.6.3 Generalization

7.6.4 Dealing with Solution-Creation Goals

7.6.5 Some Examples

7.7 Combining Explanation-Based, Checklist-Based, and Difference-Based Methods

7.8 Choosing an Automated Indexing Method

7.9 Summary

Part III Retrieving Cases from the Case Library

8 Organizational Structures and Retrieval Algorithms

8.1 A Note About Matching

8.2 A Set of Cases

8.3 Flat Memory, Serial Search

8.4 Hierarchical Organizations of Cases: Shared Feature Networks

8.5 Discrimination Networks

8.6 A Major Disadvantage

8.7 Redundant Discrimination Networks

8.8 Flat Library, Parallel Search

8.9 Hierarchical Memory, Parallel Search

8.10 Discussion

8.10.1 A Note on Parallelism

8.10.2 Advantages of Hierarchical Organizations

8.10.3 Integrating Search and Match Functions

8.11 Summary


9 Matching and Ranking Cases

9.1 Some Definitions

9.1.1 Dimensions, Descriptors, and Features

9.1.2 Choosing What to Match

9.1.3 Matching and Ranking

9.1.4 Global and Local Matching Criteria: Taking Context into Account in Matching

9.1.5 Absolute and Relative Matching and Ranking

9.1.6 Input to Matching and Ranking Functions

9.2 The Building Blocks of Matching and Ranking Process

9.2.1 Finding Correspondences

9.2.2 Computing Degree of Similarity of Corresponding Features

9.2.3 Weighting Dimensions of a Representation: Assigning Importance Values

9.3 Putting It All together

9.3.1 Matching and Ranking Using a Numeric Function: Nearest-Neighbor Matching

9.3.2 Adding Exclusion to the Ranking Procedure

9.3.3 The Need to Take Context into Account in Ranking

9.3.4 Making Ranking Dynamic Through Multiple Assignments of Importance

9.3.5 Using Preferences to Implement a Relative Ranking Scheme

9.4 Summary


10 Indexing and Retrieval

10.1 Situation Assessment: Choosing Indexes for Retrieval

10.1.1 Before Search: Context Setting Using a Checklist

10.1.2 During Search: Incremental Context Refinement

10.2 Implementing Indexes

10.3 Achieving Efficiency, Accuracy, and Flexibility

10.4 Summary

Part IV Using Cases

11 Adaptation Methods and Strategies

11.1 Substitution

11.1.1 Reinstantiation

11.1.2 Parameter Adjustment

11.1.3 Local Search

11.1.4 Query Memory

11.1.5 Specialized Search

11.1.6 Case-Based Substitution

11.1.7 Memory Organization Requirements for Substitution Methods

11.2 Transformation

11.2.1 Commonsense Transformation

11.2.2 Model-Guided Repair

11.3 Special-Purpose Adaptation and Repair Heuristics

11.4 Derivational Replay

11.5 Summary


12 Controlling Adaptation

12.1 Identifying hat Needs to Be Fixed

12.1.1 Using Differences Between Problem Specifications

12.1.2 Using a Checklist

12.1.3 Using Inconsistencies Between the Old Solution and Stated Goals

12.1.4 Using Solution Projections

12.1.5 Carrying Out a Solution and Analyzing Feedback

12.1.6 Using Adaptation History: Compensatory Adaptation

12.2 Choosing an Adaptation Strategy

12.2.1 Choosing What Gets Adapted

12.2.2 Finding an Appropriate Adaptation or Repair Strategy

12.2.3 Choosing Between Several Adaptation Methods

12.3 Choosing What Gets Adapted and the Method of Adaptation in Tandem

12.3.1 Case-Based Adaptation

12.3.2 Using Execution-Time Feedback

12.3.3 Using Critics to Control Adaptation

12.4 Flow of Control

12.5 Summary


13 Using Cases for Interpretation and Evaluation

13.1 Exemplar-based Classification

13.2 Case-Based Interpretation

13.2.1 Analyzing and Retrieving Cases: Dimensions, Indexing, and the Case Analysis Record

13.2.2 Positioning and Selecting Cases: The Claim Lattice

13.2.3 Generating and Testing Arguments

13.3 Critiquing Solutions: Case-Based Projection

13.4 Summary


14 Using Cases: Some Additional Issues

14.1 Using Reasoning Goals to Guide Case-Based processes

14.2 Anticipating Potential Problems and Opportunities for Enhancement

14.3 Deriving Subgoals

14.4 Types of Reasoning Goals and Tasks

14.5 Goal Scheduling

14.6 Integrating the Goal Scheduler With the Case-Based Reasoner

14.7 When to use a Goal Scheduler

14.8 A Neglected Complexity: Merging Pieces of Several Solutions

14.9 Summary

Part V Pulling It All Together

15 Building a Case-Based Reasoner

15.1 First things First: When Should a Case-Based Reasoner Be Used?

15.2 Which Tasks and Subtasks Should the Case-Based Reasoner Support?

15.2.1 Analysis of the Task Domain

15.2.2 Generic Case-Based Reasoning Tasks

15.2.3 Functions Cases Can Profitably Fulfill

15.3 What Degree of Automation Should Be Used?

15.3.1 Consideration 1: Required Creativity

15.3.2 Consideration 2: Complexity of Evaluating Solutions and Effecting Repairs

15.3.3 Consideration 3: Need to Consider Aesthetics, Values, and/or User Preferences

15.3.4 Consideration 4: Locus of Complexity

15.4 Building and Maintaining the Case Library

15.4.1 Collecting Cases: Which Ones?

15.4.2 Achieving Coverage and Reliability

15.5 Maintaining the Case Library

15.5.1 Collecting Cases: How?

15.5.2 Collecting Cases: What Constitutes a Case?

15.6 Case Presentation and Human-Computer Interaction

15.7 Summary


16 Conclusions, Opportunities, Challenges

16.1 Case-Based Reasoning and Learning

16.2 Conclusions

16.3 Challenges and Opportunities

16.3.1 Knowledge Engineering Issues

16.3.2 Scaleup: The Major Technological Issue

16.3.3 Fundamental Issues and Enhanced Capabilities

16.4 The Future


Appendix: A Case Library of Case-Based Reasoning Systems

Bibliography

Index