1. Aims:

The course is aiming to provide the students with the background knowledge in the field of case-based reasoning - a new paradigm for combining problem-solving and learning. The different aspects of case-based reasoning process will be illustrated by the examples of CBR systems that use past experience to solve problems in different problem domains.

2. Objectives:

On completion of the course students should be able to:

3. Learning Strategies:

Guided reading. Hands-on experiments with computer models.

4. Overall Duration and Format:

One semester (15 weeks) course with 2 hours seminars and 2 hours lab work.

5. Instructor: Dr. Gennady Agre - Institute of Information Technologies - BAS

6. Literature:

[Agre] G. Agre, Z. Markov and D. Dochev. Introduction to Machine Learning, TEPUS JEP1497, SOFTECH, Sofia (in Bulgarian – Forthcoming).

[Bareiss] Ray Bareiss. Exemplar-Based Knowledge Acquisition: A Unified Approach to Concept Representation, Classification, and Learning. Academic Press, Inc., 1989.

[Barsalou] L. Barsalou and C. Hale. Components of Conceptual Representation: From Feature Lists to Recursive Frames. In: I. Van Mechelen, J. Hampton, R. Michalski and P. Theuns (Eds.). Categories and Concepts: Theoretical Views and Inductive Data Analysis}, Academic Press Ltd, 97-144, 1993.

[Golding and Rosenbloom] Golding A.R., Rosenbloom, P.S. Improving rule-based systems through case-based reasoning. Proceedings of the National Conference on Artificial Intelligence, Anaheim, MIT Press (1991) 22--27.

[Hammond] Kristian Hammond. Explaining and Repairing Plans That Fail. Artificial Intelligence 45 (1990), pp. 173-228.

[Kolodner] Janet Kolodner. Case-Based Reasoning. Morgan Kaufmann Publ., San Mateo, 1993.

[Salzberg] S. L. Salzberg. Learning with Nested Generalized Exemplars. Kluwer Academic Publishers, Norwell, MA, 1990.

[Mayer] Richard Mayer. Thinking, problem solving, cognition. Second edition. H. Freeman and Co., New-York, 1992.

[Porter] Bruce Porter, R. Bareiss, R. Holte. Concept Learning and Heuristic Classification in Weak-Theory Domains. Artificial Intelligence, 45, 1990, 229-263.

[Riesbeck and Schank] Christopher Reisbeck, Roger Schank. Inside Case-Based Reasoning. Lawrence Erlbaum Ass. Hillsdale, New Jersey, 1989.

[Schank and Abelson] R. Schank and R. Abelson. Scripts, Plans, Goal, and Understanding. In D.A. Watterman and F. Hayes-Roth (Eds.), Pattern-directed Inference Systems, pp. 415-430, Academic Press, NewYork, 1977.

[Weiss] Sh. Weiss and C. Kulikowsi.Computer Systems That Learn, Morgan Kaufmann Publishers, San Mateo, California, 1991.

7. Course Outline:

The course is divided into the following sections:

8. Main Topics:

Case-Based Reasoning and Cognition


Topic 1. Models of Memory. Semantic and Episodic Memory. Conceptual Memory and Scripts.

Reminding. Cases versus Rules.

Required reading:

Chapters 2-3 of [Mayer], chapters 1 [Schank and Abelson].

Introduction to Case-Based Reasoning


Topic 2. Main types of Case-based reasoning methods . The CBR Cycle– 4R: Retrive, Reuse, Revise and


Required reading


Additional readings:

Chapters 4, 8 of [Kolodner]

Instance-Based Learning


Topic 3. Flat Organization of Case Memory. Measuring similarity. Similarity metrics. Similarity and

family resemblance. Statistical approaches to evaluation of similarity. Processing missing values.

Required reading:


Additional readings:


Topic 4. Nearest Neighbor and k-Nearest Neighbor methods. Choice of optimal k - leave-one-out

crossvalidation method. Bayes classification. "Naive" Bayes classifier.

Required reading:


Additional readings:

Chapter 3 of [Weiss].

Topic 5. Methods for weighting attributes. Weighting cases. Measuring and using typicality. Case

weighting by evaluation of classification behaviour.

Required reading:


Additional readings:


Topic 6. Learning compact category description, prototypically-based learning, learning generalised exemplars.

Required reading:


[Salzberg], [Domingos]

Exemplar-Based Learning


Topic 7. Using background knowledge for classification. Protos system - task definition and basic

concepts. Using Knowledge-based matching for evaluation of similarity. Using and learning

matching knowledge. Using and learning indexing knowledge. Evaluation of Protos.

Required reading:


Additional readings:


Hierarchical Case Memory and Case-Based Reasoning


Topic 8. Hierarchical organisation of memory – shared feature networks, discrimination networks, memory

organisation packages.

Required reading:

Chapter 8 of [Colodner]

Topic 9. Case adaptation - types of adaptation and adaptation techniques. Explanation and Repear.

Required reading:

Chapter 2 of [Riesbeck and Schank]

Additional readings:

Chapter 11, 12 of [Kolodner]

Topic 10. JUDGE: A Case-Based Legal Reasoner. A Model of Sentencing Process. Sentences Formation.

Modification Phase. Explaining Rules.

Required reading:

Chapter 5 of [Riesbeck and Schank]

Additional readings:

Chapter 6 of [Riesbeck and Schank]

Topic 11. A Model of Cased-Based Planning. Building an Initial Plan. Debugging Failed Plan. Storing

Plans for Later Use. Learning from Planning.

Required reading:

Chapter 6 of [Riesbeck and Schank]

Additional readings:


Topic 12. CHEF: A Case-Based Planer. Knowledge Model. Representation of Domain Knowledge.

Representation of Control Knowledge. Indexes. The Problem Solving Process. The Learning

Process. Evaluation of CHEF.

Required reading:

Chapter 6 of [Riesbeck and Schank]

Additional reading:

[Hammond], chapter 7 of [Riesbeck and Schank]

Concluding discussions- Integration with other paradigms


Topic 13. Integration with model-based reasoning: CASEY - A Case-Based Diagnostician. Problem

Addressed. The Knowledge Model Knowledge Types. The Problem Solving Process. Reasoning

and learning.

Required reading:

Chapter 2, 5 of [Kolodner]

Topic 14. Improving Rule-Based Systems through Case-Base Reasoning. Indexing, Proposing Analogies

and Conflict Resolution. Integrating CBR and Neural networks.

Required reading:

[Golding and Rosenbloom]

Topic 15. Open problem in CBR. Case and Intelligence.

Required reading:

Chapter 16 of [Kolodner], chapter 12 of [Reisbeck and Schank]

9. Assessment:

Based on answering questions and solving illustrative problems.

10. Prerequisites:

The course is aimed at computer science students at postgraduate level (M.Sc.).

The following is required: