Case-Based Reasoning

Example CBR (page 3)

CBR can mean adapting old situations to meet new demands, using old cases to explain new situations, using old cases to critique new solutions, or reasoning from precedents to interpret a new situation (law) or create equitable solutions to a new problem (mediators).

Tough one-what would it not be useful for?(workshop contents)

Basically anything that uses memories of past experiences can use CBR

• diagnosis (medicine, mechanics, etc) (pg. 84)
• planning (CHEF) (pg. 77)
• design (KRITIK) (pg. 80)
• mediation
• law (pg. 88)
• common sense
• learning
• taking a test from a particular instructor

Premises:

• reference to old cases is advantageous to dealing with situations that recur
• descriptions of problems are often incomplete (one needs to correctly understand and interpret the problem)
• no case is "the same" - need to adapt old ones to the new situation
• learning occurs as a natural consequence of reasoning
• feedback and analysis of feedback facilitate learning

1. the experience it has had
2. its ability to understand new situations in terms of old experiences
3. its adeptness at adaptation
4. its adeptness at evaluation and repair
5. its ability to integrate new experiences into its memory appropriately

The ability to understand a new problem in terms of old experiences has two parts:

recalling old experiences and

interpreting the new situation in terms of the recalled experience

Recalling an old experience is called the indexing problem.

Adaptation is the process of fixing up an old situation to meet the demands of the new one.

See (page 244 (217) Maintaining Organization in a Dynamic Long-Term Memory")

Case-based reasoning achieves most of its learning in two ways:

• through the accumulation of new cases
• through the assignment of indexes

In general

• a case represents specific knowledge tied to a context. It records knowledge at an operational level.
• cases can come in many different shapes and sizes, covering large or small time slices, associating solutions with problems, outcomes with situations, or both
• a case records experiences that are different from what is expected. Not all differences are important to record. Cases worthy of recording teach a useful lesson. ("Normal" experiences are generalized into schemas...relationship between cases and schemas is seen in the next section)
• useful lessons are those that have the potential to help a reasoner achieve a goal or set of goals more easily in the future

A case is a contextualized piece of knowledge representing an experience that teaches a lesson fundamental to achieving the goals of the reasoner.

Thus there are two parts to a case:

• the lesson(s) it teaches (the cases content)
• the context in which it can teach its lesson(s) (indexes)

The Cognitive Model

Models of human memory

History

• schemas (Bartlett 1932)
• scripts (Schank 1977)
• Dynamic Memory (Schank 1982)

Though cases provide a starting point for solving a problem, general knowledge in case-based systems provide guidance in adapting old solutions to fit new situations, choosing indexes, matching cases to each other, and evaluating the goodness of derived solutions.

MOPs

Memory Organization Packets (pg 110)

• hold general knowledge
• organize, in a complex hierarchy, specific experiences of that general knowledge

• MOPs package scenes, by referring to their sequence as part of the MOPs descriptive information. (pg 110)
• They index instances that provide expectations about setting, characters, and sequence of scenes - the kinds of information that MOPs hold.
• Scenes index scripts and instances that provide expectations about how the scene will unravel in different circumstances. (pg 111, 112)
• Scripts are specializations of scenes, and scenes are components of MOPs. Scripts index cases that specialize them, that is, that provide expectations about variations in the script.
• Cases can be specializations of MOPs or scenes - they are the instances that show the specifics that vary from what is expected in a significant way

Like MOPs, E-MOPs have two functions, the organization is through individual episodes using a web of indexes. Specifically, E-MOPs organize similar episodes according to their differences and keeps track of their similarities.

E-MOPs further developed the theory of MOPs by proposing that E-MOPs and cases are arranged together in specialization/generalization hierarchies. Thus, traversal of an index in an E-MOP can lead to encountering an event or specialized E-MOP.(page 249 of paper)

Two important aspects:

• *generalized information characterizing its episodes
• *treelike structures that index its episodes by differences

memory organization

TOPs

Thematic Organization Packets

Provide a means of categorizing situations by the intentions of participants rather than by the details of the activities of situations.

More knowledge of goals and plans...

(goal description, condition) pair

They capture the similarities between situations across different domains.

(page 112)

Representing Case

* What component parts does a case have? (pg. 146)

Problem/situation description: the state of the world at the time the case was happening and, if appropriate, what problem needed solving at that time

Solution: the stated or derived solution to the problem specified in the problem description, or the reaction to its situation

Outcome: the resulting state of the world when the solution was carried out

* What kinds of knowledge does a case need to encode

1. The content of Problem Representation (page 148)

   Three major components of the problem representation:

   1. Goals to be achieved in solving the problem
   2. Constraints on those goals
   3. Features of the problem situation and relationships between its parts
      1. include in the problem description all descriptive information that was explicitly taken into account in achieving the case's goals
      2. include in the problem description the kinds of descriptive information that are normally used to describe cases of this sort
   4. The content of Solutions (page 154)
      • The solution itself
      • The set of reasoning steps used to solve the problem
      • The set of justifications for decisions that were made in solving the problem
      • Acceptable solutions that were not chosen (and reasons and justifications that go with them)
      • Unacceptable solutions that were rules out (and reasons and justifications that go with them)
      • Expectations of what will result upon deployment of the solution
   5. The content of Case Outcomes (page 158)
      • The outcome itself
      • Whether or not the outcome fulfilled or violated expectations
      • Whether the outcome was a success or failure
      • Explanation of the expectation violation and/or failure
      • Repair strategy
      • What could have been done to avoid the problem
      • Pointer to the next attempt at a solution (result of applying repair)

   * What formalisms and methodologies are appropriate for representing a case?

   "The important thing has been to get the knowledge in some format in a way that works rather than designating one or another format as the appropriate one for representing cases." (page 160) neat or scruffy?

   Also, user-interface issues...

   * How can we recognize the boundaries of cases, and how can they be devided into chunks of the right size? (page 182, 188)

   Indexing

   How do TOPs, MOPs, E-MOPs, scenes, and scripts organize events so that those that can provide the best expectations can easily be made available to reasoning processes? ... indexing

   Cases are indexed by combinations of features that predict their applicability in an anomalous situation

   Important points:

   1. features to be used as indexes must be chosen carefully if the most useful cases are to be recalled from the case library
   2. the features of a case that are useful as indexes often go beyond the surface features of the case
   3. choice of good indices may require an interpretation or elaboration process during which the interesting functional features of a situation are derived
   Issues on choosing indexes:
   • What kinds of goals do reasoners have that a case might contribute to fulfilling?
   • How should we label or index cases so that we can recognize their applicability in the future?
   • What guidelines are available for this process?
   • How can the computer automate the process?
   • What vocabulary should we use to describe and index cases?
     • How do we choose domain-related vocabulary items?
     • What abstract descriptors hold across domains?
   In general, there are two kinds of indexing that are useful
   • Differences allow us to retrieve cases that specialize the norms

   • Anomolies provide expectations for understanding or acting in similar anomalous situations.

   Guidelines: (paper page 254) (book page 197)

   • Indexes should be predictive
   • Predictions that can be made should be useful ones, that is, they should address the purposes the case will be used for
   • Indexes should be abstract enough to make a case useful in a variety of future situations (pg. 199)
   • Indexes should be concrete enough to be easily recognizable in future situations
   Index Selection Methods (pg. 247)

   blame assignment, credit assignment computationally complex (if not intractable)

   Need heuristics...

   Technique 1) choose as indexes features that tend to predict solutions or outcomes

   System builder tells the system which kinds of features it should use for indexing. Each case is indexed by the features found on the checklist.

   The best checklists are lists of features known to be predictive

   Technique 2) concentrate on extracting differences between the new case and other cases in the case library

   Usually these two are combined...

   Third kind: select indexes using explanations of why a solution worked or didn't work

   Choosing Indexes By Hand (pg. 249)

   • Determine what the case could be useful for by designating its points with respect to the set of tasks the reasoner is being asked to carry out
   • Determine under what circumstances its points would be useful for each of these tasks
   • Translate the circumstances into the vocabulary of the reasoner
   • Massage the circumstances to make them recognizable and as generally applicable as possible
   Choosing Indexes By Machine (pg. 257)
   • Choosing Indexes On a Checklist (pg. 259, 263)
   • Difference-Based Indexing (pg. 267)
   • Combining Difference-Based and Checklist
   • Explanation-Based Indexing (pg. 270)
   • Combining all three

   Organizational Structures and Retrieval Algorithms

   Remembering is the process of retrieving a case or set of cases from memory. In general, it consists of two substeps: (pg 18)

   *Recall previous cases

   The goal of this step is to retrieve "good" cases that can support reasoning that comes in the next steps. Good cases are those that have the potential to make relevant predictions about the new case. Retrieval is done by using features of the new case as indexes into the case library. Cases labeled by subsets of those features that can be derived from those features are recalled.

   *Select the best subset

   This step selects the most promising case or cases to reason with from those generated in step 1. The purpose of this step is to reduce the set of relevant cases to a few most-on-point candidates worthy of intensive consideration. Sometimes it is appropriate to choose one best case; sometimes a small set is needed

   Case retrieval, no matter the method, requires a combination of search and matching... then, perhaps situation assessment.

   Organizational structures are searched to find potentially matching cases, and each is judged for its potential usefulness. This judgement is done by matching functions. In some schemes, search and matching are sequential, in others, they are interleaved.

   Some schemas: (page 291)

   • Flat memory, serial search (optionally augmented by shallow indexing or
   • partitioning)
   • Shared feature networks, breath-first graph search
   • Prioritized discrimination networks, depth-first graph search
   • Redundant discrimination networks, breath-first graph search
   • Flat memory, parallel search
   • Hierarchical memory, parallel search
   More considerations:
   • Adaptation (matching rarely exact)
   • Justification and Criticism
   • Case Repair
   • Memory Update

   Advantages of Case-Based Reasoning (page 25)

   Case-based reasoning allows the reasoner to propose solutions to problems quickly, avoiding the time necessary to derive those answers from scratch

   Case-based reasoning allows a reasoner to propose solutions in domains that are not completely understood by the reasoner

   Case-based reasoning gives a reasoner a means of evaluating solutions when no algorithmic method is available for evaluation

   Cases are useful in interpreting open-ended and ill-formed concepts

   Remembering previous experiences is particularly useful in warning of the potential for problems that have occurred in the past, alerting a reasoner to take actions to avoid repeating past mistakes

   Cases help a reasoner to focus its reasoning on important parts of a problem by pointing out what features of a problem are the important ones

   and disadvantages

   A case-based reasoner might be tempted to use old cases blindly, relying on previous experience without validating it in the new situation

   A case-based reasoner might allow cases to bias it too much in solving a new problem

   Often people, especially novices, are not reminded of the most appropriate sets of cases when they are reasoning