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.
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]).
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].
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.
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.
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!
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].
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]).
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.
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]).
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!
"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!
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!
[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.