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