"Case-Based Reasoning"

"Case-Based Reasoning" (Andrew Broad)

(This paper was submitted as a CS3411 (Advanced Knowledge-Based Systems) essay in January 1997, and appears on this web page in a slightly edited form.


This paper presents an overview of Case-Based Reasoning (CBR). A CBR system attempts to solve a new problem by making an analogy to an old one and adapting its solution to the current situation. It stores previously experienced situations in its memory as cases, which the system is reminded of when it encounters a similar situation. I like to think of cases specifically as problem solving episodes.

At the heart of the essay, I present a framework for CBR. I look at how to represent cases and index them for later retrieval, and at the major steps in CBR (Aamodt and Plaza [1]): retrieving similar cases from memory, selecting the one that best matches the current situation, adapting that case's solution to fit the current situation and storing this episode as a case in memory.


As well as a methodology for building intelligent knowledge based systems, CBR is a plausible model of human cognition (Section 1.6 of Kolodner [4], Chapter 1 of Riesbeck and Schank [8]). We naturally do CBR all the time! Rather than solving problems from first principles, we draw on experience. This enables us to solve problems more easily and to become more competent.

I believe that CBR offers a crisp revelation of the essence of human intelligence. Successful thinking is a matter of retrieving the right information at the right time. We understand something precisely when we are able to explain it in terms of what we already know! (Section 4.2 of Kolodner [4]).


CBR seems to be advantageous for domains which don't have a well-defined theory but do have a great abundance of data in the form of cases (such as law). Some domains (such as medicine) are inherently case-based.

Programs have been written to use CBR for planning (CHEF invents new recipes by adapting old ones), design (JULIA plans meals by posting and propagating constraints) and diagnosis (CASEY diagnoses heart failure). These systems and many others are discussed at length in Chapter 2 of Kolodner [4].


A case as stored in memory consists of a problem and its solution. It will also need to hold the chain of operators that were used to solve the problem if derivational adaptation is to be used (more on which later).

An individual case corresponds to a specific problem solving episode. It is an instance of a generalised episode, together with other similar cases (Kolodner et al. [5]). Generalised episodes are to cases as classes are to objects; they form an inheritance hierarchy. Generalised episodes are also known as Memory Organisation Packets (Section 19.3 of Rich and Knight [7]; Chapter 2 of Riesbeck and Schank [8]; Section 4.2.2 of Kolodner [4]). They are effectively scripts with links - particularly generalisation links, specialisation links, and instance links to point to individual cases.

For example, each time I take the train from Warrington to Manchester is a case in my memory. Because I do it so often, it has become ossified as a generalised episode, which is what comes to mind to help me solve this problem every day, rather than any specific instance of the journey. From now on, when I use the word 'case' it subsumes the notion of generalised episodes.

This representation of cases is called the dynamic memory model (Aamodt and Plaza [1]; Section 4.2 of Kolodner [4]; Chapter 2 of Riesbeck and Schank [8]). It is dynamic in the sense that it changes with experience.


The idea of indexing is central to the representation, storage and retrieval of cases. Each case is tagged with a set of indexes which serve to guide the search process for retrieving cases appropriate to the current problem situation. Indexing avoids a linear search through the entire case library, which can often contain thousands of cases!

Indexes are features of a case which distinguish it from the norms of its supercase ('Supercase' and 'subcase' are my words for the cases at the end of generalisation and specialisation links respectively). A case is worth retaining just when there is some difference from the others - I don't remember every single train journey but I do remember the one where I was delayed for three hours because a lorry crashed into a bridge!

Indexing is a crucial part of CBR because it determines under what circumstances a case will be retrieved (Section 1.2 of Kolodner [4]). It is important to be able to retrieve just those cases which are appropriate to solving the current problem, an ability which is probably the barometer of intelligence.

A good index is one which is distinct but not unique, so that a small set of cases will be retrieved (Chapter 2 of Riesbeck and Schank [8]). The more specialised a case is, the larger its set of indexes will be (including those it inherits from its ancestors in the hierarchy of cases). Again, this constrains cases so that the reasoner will be reminded by the current situation of a sensible number of cases.


The first thing a case-based reasoner does when faced with a situation is to pick out some features to index into the case library, where the stored cases reside.

It then trundles around the case library using these features to guide it, following links to get to cases which have some indexes in common with the current situation. It is said to be reminded of each case it collides with; those are the cases it retrieves.

It ranks the retrieved cases by a similarity metric (Golding and Rosenbloom [3]) and selects the best case (or cases).

The similarity metric compares a case to the current problem situation with regard to various features. The importance of each feature is represented as a multiplicative weight. It would be nice if the system could learn its own weights and even better if it could learn its own similarity metrics and indexes!


The solution inside the best case is what is known in the trade as a ballpark solution (Section 1.4.2 of Kolodner [4]). To compensate for retrieval's partial matching, the solution must be adapted to fit the current case.

For example, suppose CHEF is required to invent a recipe for beef and broccoli and the best case it retrieves is a recipe for chicken and peas (this example is used both in Section 2.1 of Kolodner [4] and Chapter 2 of Riesbeck and Schank [8]). It has to adapt the old recipe by replacing chicken with beef, and peas with broccoli. It then further modifies the recipe using object critics (Section 2.1 of Kolodner [4]), which are special-purpose rules such as inserting a step to chop the broccoli into chunks.

Derivational adaptation (Chapter 2 of Riesbeck and Schank [8]) involves not just modifying the solution itself but rerunning the chain of operators that generated the solution, making appropriate changes. Because derivational adaptation requires fewer ad hoc rules (object critics), it is good for adapting cases which were generated by the CBR system itself, and is more domain-independent. Derivational analogy is discussed quite independently of CBR in Section 17.8 of Rich and Knight [7].


Once the system has solved a problem, it gains experience by storing the problem, along with its solution (and possibly the derivation of that solution) as a case in memory. It must index this case so that it will be retrieved under appropriate circumstances in the future!

In the light of this experience, it may also re-index the existing cases in the library. It can automatically augment the case hierarchy by creating a generalisation when many cases have similar indexes. For example, if I had many severely delayed train journeys, I would add a new generalised episode as a supercase of those particular journeys and a subcase of train journey.

Where do cases come from in the first place? The system could start by solving problems from first principles using rules until it has enough experience to use the case-based approach, or initial cases could simply be entered by hand (Section 19.4 of Rich and Knight [7]).


A good case-based reasoner needs to evaluate the adapted solution to see if it really works. If it doesn't, the system needs to explain the failure and repair the solution (Chapter 2 of Riesbeck and Schank [8]).

On running the new beef and broccoli recipe through its simulator, CHEF discovers that the broccoli goes soggy because the beef sweats. It repairs the solution so that they will be cooked separately.

Not only does the system store the repaired case, it also stores the one that didn't work along a failure link so that it will be retrieved as a warning to the reasoner in the future (Section 2.1 of Kolodner [4]). The first thing CHEF does is to anticipate failures by looking for failed cases and adding the feature that predicts that failure to its goals, e.g. "the vegetable must remain crisp". Both the repaired case and the failed case will have been indexed by that feature.


Traditional expert systems are brittle because they can't learn from experience and they collapse dramatically when faced with problems beyond their plateau of expertise (Brown [2]). A CBR system can deal with such situations by acquiring new cases (it may have to ask a human expert).

CBR greatly alleviates the knowledge acquisition bottleneck, partly because learning occurs as a natural by-product of problem solving (Aamodt and Plaza [1]) and partly because it is easier to get human experts to tell you cases rather than all their compiled knowledge! This is particularly true for complex, nasty domains where it is impossible to completely specify all the rules, but there are always cases (Chapter 2 of Riesbeck and Schank [8]).

CBR is more efficient than RBR for large domains because it avoids expensive recomputation, and searches the space of what has happened rather than the intractable space of what could happen (Brown [2]).

There is evidence in Section 3.4.1 of Kolodner [4] that case-based systems are also faster to develop than rule-based systems and require less maintenance.

However, I want to emphasise that CBR is there to enhance RBR, not necessarily to replace it! Rules are very good for capturing broad trends but, in the real world, there are often exceptions to the rule. Cases fill in these exceptions (Golding and Rosenbloom [3]).


Aamodt and Plaza [1] mention the category and exemplar model as an alternative to the dynamic memory model. This model uses much shallower case hierarchies (corresponding to a view that natural concepts should be defined extensionally). Cases are either positive or negative exemplars of a rule, which are taken into account before the rule is applied, in order to avoid mistakes (Golding and Rosenbloom [3]).

Brown's thesis [2] condemns indexing because it requires the case library to be structured in a way that is too domain-specific, and proposes to replace indexing with a retrieval process that is more flexible yet still efficient.

Using a massively parallel computer with a processor for each case would allow cases to be rapidly retrieved (Winston [9]), but Brown [2] argues that this is neither necessary nor sufficient. What's important is to avoid exhaustive search, although some parallelism would offer a valuable speed-up!


CBR is widely regarded as being restricted to intra-domain analogies, whereas the field of analogical reasoning allows inter-domain analogies. This is more difficult because cases need to be represented and compared at a more abstract level, as the following stories from Brown [2] illustrate:

"Helen went shoplifting. She concealed the clothes to avoid getting caught, but as she left the store, the electronic tags triggered the alarm system."

"Fred had always worried about being killed, so he was always meticulous in checking for traffic whenever he crossed a road. Unfortunately, he never thought to check where he was stepping and one day he fell down an open manhole."

To see the analogy between these two cases requires looking beyond surface features to the abstract principle that to prevent an unwanted occurrence, it is not enough to attend to one possible cause of it!


CBR is a field of great promise, but there are problems which nobody has solved yet. Retrieval and adaptation are not that easy!

Ian Pratt [6] criticises CBR in that it is difficult to evaluate the inferences it makes because the meanings of data structures are unclear. This raises the old debate between the 'neats' and the 'scruffies', but it is good to be able to quickly generate plausible answers as long as you validate them!

CBR is a very exciting young prospect, which I'm interested in doing for my postgraduate research. I believe it has a major role to play in making computers more intelligent than mankind sometime next century! This will be achieved by combining the power of human memory with the amazing speed and unerring accuracy of computers.

On the other hand, we must bear in mind that what is good for humans isn't necessarily suitable for computers! As humans, we rely on CBR all the time but computers often don't need it. I don't wish to advocate CBR where not appropriate!

CBR already has its own research group in this department and, in my opinion, ought to have a taught course devoted to it!


[1] Aamodt A. and Plaza E. (1994). Case-Based Reasoning: Foundational Issues, Methodological Variations, and System Approaches. Pages 39-59 in AICom - Artificial Intelligence Communications 7(1), March 1994. On the Internet, http://www.iiia.csic.es/People/enric/AICom.html (last modified 1st December 1997).

[2] Brown M.G. (1993). A memory model for case retrieval by activation passing. Ph.D. thesis, Department of Computer Science, University of Manchester, technical report UMCS-94-2-1. On the Internet, ftp://ftp.cs.man.ac.uk/pub/TR/UMCS-94-2-1.ps.Z (last modified 17th June 1995).

[3] Golding A.R. and Rosenbloom P.S. (1993). Improving rule-based systems through case-based reasoning. Pages 759-764 in Buchanan B.G. and Wilkins D.C., editors. Readings in Knowledge Acquisition and Learning: Automating the Construction and Improvement of Expert Systems. Morgan Kaufmann Publishers, Inc., San Mateo, CA. ISBN 1-55860-163-5.

[4] Kolodner J.L. (1993). Case-Based Reasoning. Morgan Kaufmann Publishers, Inc., San Mateo, CA. ISBN 1-55860-237-2.

[5] Kolodner J., Simpson R. and Sycara-Cyranski K. (1985). A process model of case-based reasoning in problem solving. Pages 284-290 in Proceedings of the Ninth International Joint Conference on Artificial Intelligence (IJCAI-85), Los Angeles, CA, 18th-23rd August 1985. Volume 1.

[6] Pratt I. (1994). Artificial Intelligence. Macmillan, London. ISBN 0-333-59755-9.

[7] Rich E. and Knight K. (1991). Artificial Intelligence, Second Edition. McGraw-Hill, New York. ISBN 0-07-100894-2.

[8] Riesbeck C.K. and Schank R.C., editors. (1989). Inside Case-Based Reasoning. Lawrence Erlbaum Associates, Hillsdale, NJ. ISBN 0-89859-767-6.

[9] Winston P.H. (1992). Artificial Intelligence, Third Edition. Addison-Wesley, Reading, MA. ISBN 0-201-53377-4.

Back to Case-Based Reasoning
Email me
Hosted by www.Geocities.ws