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:

• read and understand specialized CBR literature,
• use existing CBR systems
• implement simple CBR algorithms.

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:

• Case-Based Reasoning and Cognition - basic concepts, models of memory, remindings, cases versus rules.
• Introduction to Case-Based Reasoning - case studies in case-based reasoning systems, general model of case-based reasoning process.
• Instance-Based Learning - measuring similarity, basic instance-based learning algorithms, learning compact concept descriptions.
• Exemplar-Based Learning – Protos System: integration of flat case memory and background knowledge.
• Hierarchical Case Memory and Case-Based Reasoning. JUDGE: a case-based legal reasoner, CHEF: a case-based planer, DMAP: a case-based parser, CASEY: a case-based diagnostician.
• Concluding discussions - integration of CBR with other paradigms, open problems, case and intelligence.

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].
 
 

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

Retain.
 
 

Required reading

[Aamodt]

Additional readings:

Chapters 4, 8 of [Kolodner]
 
 

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:

[Agre]

Additional readings:

[Barsalou].
 
 

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:

[Agre]

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:

[Agre]

Additional readings:

[Salzberg]
 
 

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

Required reading:

[Agre]

[Salzberg], [Domingos]
 
 

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:

[Agre],[Porter]

Additional readings:

[Bareiss]
 
 

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:

[Hammond].
 
 

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]
 

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:

• background knowledge in knowledge representation formalisms and main problem-solving methods;
• background knowledge in search and matching techniques
• some practical skills in AI programming (Prolog or Lisp).