Integrating Case-Based and Model-based Reasoning: A symbiotic system

Phyllis Koton MIT Laboratory for Computer Science Clinical Decision Making Group 545 Technology Square, Room 371 Cambridge, MA 02139

Abstract

Associational knowledge is frequently used in expert systems because that is how experts often express their knowledge, and because it is efficient. Model-based systems, on the other hand, are robust and provide a more detailed knowledge of the problem domain, but they are relatively inefficient. Expert systems that combine both types of knowledge, using associational knowledge for speed, and reserving the ability to reason from a model when necessary, would be highly desireable. This paper describes a system that uses both associational and model-based reasoning to solve problems in its domain. The techniques described are generalizable to other domains.

The work reported here has been supported (in part) by National Institutes of Health grants R01 LM 04493 from the National Library of Medicine and R01 HL 33041 from the National Heart, Lung, and Blood Institute.

1 Introduction

Model-based reasoning is often promoted for knowledge-based systems because of its robustness, but models are inefficient compared to the associational knowledge typically used in expert systems. Case-based reasoning techniques [5] can be used to improve the performance of model-based systems, because the act of retrieving a similar case and using its solution is clearly associational: features of a problem are associated with a solution to that problem. However, case-based reasoning techniques have not been widely used to enhance knowledge-based systems. Also, case-based reasoning systems suffer from lack of a model. There is no justification (other than coincidence) for believing that transferring a solution from a previous case to a new case will produce a valid solution. The combination of case-based reasoning techniques with model-based reasoning could result in substantially improved expert systems.

2 Overview of CASEY

I have developed a program, CASEY, which integrates case-based and model-based reasoning. The model-based component employs a causal model of the cardiovascular system developed for the Heart Failure program [7], an expert system for managing patients with heart disease. The case-based reasoning component uses a self-organizing memory system [4] to store descriptions of all patients the program has seen, and generalizations derived from similarities between the patients. The patient description is comprised of features. These include both input data, such as signs and symptoms, test results, history and current therapy information, and solution data, such as the causal explanation for the patient, the diagnosis, therapy recommendation and outcome information.

CASEY produces a causal explanation^{1}, a diagnosis, and therapy suggestions for a new patient using a five-step process.

• Retrieval. CASEY finds a case similar to the new patient in its case memory.

• Justification. CASEY evaluates the significance of any differences between the new case and the retrieved case. During this phase the match can be invalidated if there are significant differences.

• Adaptation. If none of the differences invalidate the match, CASEY adapts the solution from the retrieved case to fit the new case. If a match is ruled out, or if no similar previous case is found, CASEY uses the Heart Failure program to produce a solution for the case de novo.

• Storage. The new case and its solution are stored in CASEY’s memory for use in future problem solving.^{2}

• Feature evaluation. The features which were causally important in the solution of this problem are noted in the memory.

Retrieving, adapting, and storing cases are standard procedures of a case-based reasoner. Because the match between a new problem and a previously solved problem usually is only partial, there may be differences between the two cases that preclude using even a modified version of a retrieved solution for a new problem. The justification step ensures that a retrieved solution can be supported by the data in the new problem. Evaluating the features of the new problem to determine which were important to the solution helps the program make better matches in the future, because it allows the program to distinguish between random features and important ones.

1the relationship between physiological states in the model and observable features of the patient.

2The user has the option of rejecting CASEY’s solution, in which case Heart Failure program is used to produce a causal explanation, which will be stored in memory.

CASEY differs from previous case-based reasoning systems because it uses information from its model to effect these steps. During retrieval, causal knowledge is used to select important features of the new case for matching. During justification, model-based reasoning is used to judge the significance of differences between the new and previous cases. In repairing a retrieved solution, the model determines what changes should be made in the retrieved solution so that it fits the present case. Feature evaluation uses the causal explanation of the new case to determine its important features.

3 Matching and retrieval

Most case-based reasoners use a similarity metric to gauge the similarity of two problems, and to choose the best match for the current problem. Similarity metrics use a combination of the number of features in common and the relative importance of those features. In many case-based reasoning systems, the relative importance of features for matching is predetermined by the system designer (for example, [12], [2], [1]). Another approach is to determine the important features based on a program’s experience of what was important in solving similar problems.

CASEY matches a new case against cases in its memory using every feature in the patient description. Using knowledge acquired from previous cases, CASEY then determines which features of the new case are important, and gives these features greater weight for matching. Important features are defined as those that played a role in the causal explanation of previous similar cases. Importance weight is determined by an algorithm that considers the total number of times a feature has occurred, the number of times a feature has occurred in a causal explanation, and the total number of cases the program has seen. The effect of this algorithm is to give greatest weight to important features that have appeared in many previous cases. However, when only a few previous similar cases are available for comparison, it prevents features that have not appeared very often from being dismissed from consideration.

CASEY will often retrieve more than one case that matches the new patient. If this occurs, it examines the retrieved case with the highest importance weight first. If this match is ruled out and there is another retrieved case with a close score (currently, within 10% of the highest ranking case) that case is examined. This continues either until a match is justified or there are no remaining high-scoring matches.

Figure 1 shows a sample patient presented to CASEY, Oprah. The retrieved case for Oprah, a patient named Mary, is shown in Figure 2.^{3} The features marked with an asterisk in Mary’s description are those that were used in the solution to her case. Oprah has some, but not all, of the features that were important in the case of Mary. The two cases also share some features that were not used in the solution of Mary’s case. CASEY matched Oprah to Mary using the similarities between the two cases. It now calculates the differences between

3The patient descriptions in these illustrations have been simplified to conserve space by excluding features with normal values. A patient description typically consists of about 40 features.

(DEFPATIENT "Oprah"
HISTORY
(AGE . 77)
(SEX FEMALE)
(DYSPNEA ON-EXERTION)
(CHEST-PAIN ANGINAL)
(ANGINAL UNSTABLE)
VITAL-SIGNS
(BLOOD-PRESSURE 147 89)
(HEART-RATE . 84)
(RESP . 14)
(TEMP . 98.6)
PHYSICAL-EXAM
        (APPEARANCE NO-APPARENT-DISTRESS)
(PULSE SLOW-RISE)
(AUSCULTATION MURMUR S2)
(MURMUR SYSTOLIC-EJECTION-MURMUR)
(S2 SOFT-A2)
(APEX-IMPULSE SUSTAINED)
LABORATORY-FINDINGS
(EKG LVH NORMAL-SINUS)
(CXR CARDIOMEGALY)
(CARDIOMEGALY LV))

Figure 1: Description of patient Oprah.

(DEFPATIENT "Mary''
HISTORY
(AGE . 67)
(SEX FEMALE)
(DYSPNEA ON-EXERTION*)
(CHEST-PAIN ANGINAL)
(ANGINAL UNSTABLE* EXPERIENCING*)
VITAL-SIGNS
(BLOOD-PRESSURE 148 90)
(HEART-RATE . 99)
(RESP . 14)
(TEMP . 98.7)
PHYSICAL-EXAM
(APPEARANCE DIAPHORETIC* ANXIOUS*)
(PULSE NORMAL)
(AUSCULTATION MURMUR S2)
(MURMUR SYSTOLIC-EJECTION-MURMUR*)
(S2 SINGLE*)
(APEX-IMPULSE SUSTAINED*)
LABORATORY-FINDINGS
(EKG NORMAL-SINUS LV-STRAIN*)
(CXR CARDIOMEGALY)
(CARDIOMEGALY GENERALIZED*))

Figure 2: Description of patient Mary.

Feature name Value for Mary  Value for Oprah
age 67 77
anginal  unstable* experiencing* unstable
blood-pressure 148/90  147/89
heart-rate 99 84
temp 98.7  98.6
appearance  diaphoretic* anxious*  nad
pulse  normal  slow-rise
s2  single*  soft-a2
ekg  lv-strain*  lvh
cardiomegaly generalized*  lv

Figure 3: Differences between patients Mary and Oprah.

the two cases (shown in Figure 3) and passes this information to the justifier, along with the solution retrieved from Mary’s case.

4 Justification

Two cases might have many similar features yet have one critical difference that invalidates the match. The critical question is whether different values of features in the problem description still support the same solution. In CASEY’s domain, this manifests itself as whether different patient symptoms still support the same causal explanation.^{4} CASEY therefore uses a set of evidence principles to evaluate differences between the new case and a retrieved case relative to its model. These principles allow CASEY to reason the relationship between evidence and physiological states in the Heart Failure model. They rely on such concepts as alternate lines of evidence for states, additional supporting evidence for states, and inconsistent evidence. The module in CASEY that performs this evaluation is called the justifier.

A difference is insignificant if it does not affect the retrieved causal explanation. For example, the difference between Mary’s and Oprah’s temperature is insignificant because both temperatures are normal. A difference is said to be repairable if the features of the new case can be fit to the retrieved causal explanation. Consider, for example, the fragment of Mary’s causal explanation shown in Figure 4. The feature ekg: lv strain is evidence supporting the state LV HYPERTROPHY. Oprah does not have lv strain on her EKG. CASEY looks in the model for other features that are evidence of LV HYPERTROPHY, and determines whether Oprah has any of those features. In fact, Oprah has two such findings: ekg: lvh and lv cardiomegaly. Therefore, CASEY can justify keeping this state in Oprah’s causal explanation. If all differences between the new case and the retrieved case are insignificant or repairable, then the transfer of solutions from the precedent to the current case proceeds.

In case-based reasoning systems without models, the problem solver finds the best match, transfers its solution to the new case, and hopes for the best. Sometimes a retrieved case leads the problem solver down the wrong path. Evaluating differences by use of a model improves the likelihood that the retrieved solution applies to the new case. When CASEY

4The differences can also affect the diagnosis and therapy, however these follow from the causal explanation.

Figure 4: A fragment of Mary’s causal explanation.

justifies the match between the old case and the new case, it demonstrates that although there are differences between the cases, the model still supports the retrieved solution.

5 Adaptation

Modifications to the solution are necessary for partial matches between cases Repair strategies are invoked by the justifier when it discovers a repairable difference between the new case and the retrieved case. Repair strategies adapt a previous solution (consisting of causal explanation, diagnosis, and therapy) to a new case. Causal explanation repair strategies add or remove nodes and links to a copy of the retrieved causal explanation. Diagnosis repairs add or remove diseases from the transferred diagnosis. Therapy repairs add or remove therapy suggestions. All three types of repair strategies are implemented in a similar manner. For the example of Mary and Oprah given in the previous section, the justifier would invoke causal repair strategies to remove the evidence ekg: lv strain from the state LV HYPERTROPHY, and add the evidence ekg: lvh and lv cardiomegaly to the list of evidence supporting that state. Repaired solutions do not have to be tested (as is required in, e.g., [2], [11]) because the validation of the solution by the model has already taken place in the justification phase.

6 Storage

The combination of case-based and model-based reasoning has significant advantages for remembering previous cases. New cases are stored in the memory indexed both by the input features that describe the case and the solutions that were derived for the case (the causal explanation, diagnosis, and therapy suggestions). CASEY also generalizes (using similaritybased generalization) the input features and the causal explanations of the retrieved and new cases. Generalizing the patient descriptions allows CASEY to make predictions about patients who share these features [5]. CASEY generalizes all the features in the patient description, not just the causally-related features. The Heart Failure model is incomplete, so it is possible that the other features are related to (and therefore can predict) some cause not represented in the model. The sex of the patient is an example: no state in the causal model uses the sex of the patient as evidence, yet there are causal relationships between gender and heart disease. The use of case-basd reasoning therefore allows CASEY to improve on the performance of the Heart Failure system by learning new associations between features and solutions.

Generalizing the explanations produces partial explanations that explain the features that the new case and retrieved case have in common. This allows CASEY to produce a partial solution for a similar problem in the future even in the absence of enough information to explain the whole problem.

7 Feature evaluation

The use of a model is essential to CASEY’s feature evaluation step. After producing the causal explanation for a new case, CASEY determines the important features of the new case (those features which were used as evidence in the causal explanation) and increments the weights of these features in the case memory. For example, after the case of Oprah is solved, the features ekg: lvh and lv cardiomegaly are given extra weight in the memory because the model says that these features will be useful in identifying future patients with LV HYPERTROPHY, i.e. these features predict that part of the solution. Determining the importance of features by experience is reasonable because the usefulness of a feature cannot always be determined in advance. This also allows the problem solver to adapt to changes over time in the types of problems is is presnted. Giving extra weight to causallyrelated features is reasonable because because causality often indicates which features are important in the case for matching [14], [10].

8 Related work

CHEF [2] combines case-based reasoning with a simple causal model. It uses causal knowledge to explain plan failures in the limited domain of cooking. Therefore CHEF’s causal reasoning can consist solely of chaining rules backward from an observed failure to a cause. This would not scale up to a reasonably sized domain. Recent work by Resnick and Davis [9] uses combines a memory of past cases with explanation-based generalization to produce a generalized description of a hardware fault, but their technique requires an exact match between the new problem and the old problem.

Other systems have combined reasoning from a model and associational reasoning. ABEL [8] maintained a description of the patient at five levels of detail. It did not have a learning component. The Generate, Test and Debug method [11] always uses its causal model to test proposed hypotheses, and always generates them using associational rules. CASEY decides when to use associational or causal knowledge. It determines whether the new case is sufficiently similar to ones it has already solved to use the associationally-derived solution. If not, it resorts to model-based reasoning.

Other case-based reasoning programs have used a model to determine important features, for example, PERSUADER [13] and MEDIATOR [12]. However, in these systems the knowledge from the model was implicitly represented in the selection of features; they did not use an explicit model. IVY [3], like CASEY, uses information of what was important to its reasoning task to select important features of the problem for storage. IVY, however, simplifies the selection problem by using heuristics to dispense with most of the features presented to the program.

9 Discussion and conclusions

CASEY integrates model-based and case-based reasoning techniques in a program which is efficient, can learn from its experiences, and solves commonly-seen problems quickly, while maintaining the ability to reason using a detailed knowledge of the domain when necessary. The model-based component is enhanced by the ability of the case-based component to learn new associations and compile detailed reasoning structures into simple associations between features and solutions. The case-based component is improved by the use of a model because the model can demonstrate that a retrieved solution will be helpful for a new case, and the model can be used to identify important features for matching.

Since determination of important features is based on information in the model, it is reasonable to ask why the Heart Failure model is not simply “compiled” to produce all this information in the form of associational rules relating important symptoms and physiological states. In fact, that is exactly what CASEY is doing, but it is compiling the knowledge incrementally, associating features of problems with solutions for the cases it has seen. Also, the Heart Failure program’s model provides the relative importance of features only for single diagnoses. To compile all of the Heart Failure program’s knowledge taking into account multiple diagnoses would be computationally intractable. Because CASEY also makes generalizations about patients who have multiple diagnoses, it can create associational knowledge relating features to solutions involving multiple diseases.

In certain domains, including CASEY’s domain of medical reasoning, users require the most likely explanation of the evidence, not merely any explanation of the evidence. It is true that for a small number of cases, CASEY could introduce biases in the importance weights of features, for obvious reasons. If CASEY was given a large number of randomly selected cases, it would overcome the biases in its importance weights that were due to the small sample size of patients that it has reasoned about. Kolodner [6] has demonstrated that using a parallel inplementation, the retrieval time is independent of the number of cases in the memory. Thus, if given enough patients, CASEY could have the same accuracy as the probabilities in the Heart Failure program, while still providing the performance advantages of associational reasoning.

CASEY’s most serious limitation is that it assumes that there is very limited interaction between entities in the underlying model. For example, it has no concept of two states jointly causing a third. This weakness is due to the fact that no such interactions are represented in the Heart Failure model. This limits the generality of CASEY’s reasoning techniques to other systems which also make this assumption. CASEY’s evidence principles currently are being extended to handle more complex interactions.

Even if CASEY cannot solve a new problem completely because it lacks sufficient input information, it can often give a partial solution, as was seen in Section 6. Similarly, when CASEY is given a problem at the boundary of its expertise, it can produce a partial soultion for features that are handled by its model, and leave the remaining features unexplained. Therefore, techniques such as are used in CASEY might be useful in integrating several models for different domain. Each model might use those features which it could explain, leaving the other features for other models. This is a topic for future work.

Acknowledgements

Robert Jayes, MD kindly provided the example cases. William Long’s Heart Failure program provided an excellent resource for this work. Peter Szolovits, Ramesh Patil, and William Long gave much helpful advice in supervising this research.

References

[1] William M. Bain. A case-based reasoning system for subjective assessment. In Proceedings of the National Conference on Artificial Intelligence, pages 523–527. American Association for Artificial Intelligence, 1986.

[2] Kristian Hammond. Case-based Planning: An Integrated Theory of Planning, Learning and Memory. PhD thesis, Yale University, 1986.

[3] Larry Hunter. Indexing with knowledge goals: How to put knowing what you know to use. In Proceedings of the Fourth International Workshop in Machine Learning, 1987.

[4] Janet L. Kolodner. Maintaining organization in a dymanic long-term memory. Cognitive Science, 7:243–280, 1983.

[5] Janet L. Kolodner. Experiential processes in natural problem solving. Technical Report GIT-ICS-85/22, School of Information and Computer Science, Georgia Institute of Technology, 1985.

[6] Janet L. Kolodner. Retrieving events from a case memory: A parallel implementation. Unpublished manuscript, 1988.

[7] W. J. Long, S. Naimi, M. G. Criscitiello, and R. Jayes. Using a physiological model for prediction of therapy effects in heart disease. In Proc. of the Computers in Cardiology Conf. IEEE, October 1986.

[8] Ramesh S. Patil. Causal representation of patient illness for electrolyte and acid-base diagnosis. TR 267, Massachusetts Institute of Technology, Laboratory for Computer Science, 545 Technology Square, Cambridge, MA, 02139, October 1981.

[9] Paul Resnick and Randall Davis. Improving performance of model-based reasoning by learning from experience. Submitted to AAAI88, March 1988.

[10] Roger C. Schank, G. C. Collins, and Larry Hunter. Transcending inductive category formation in learning. Behavioral and Brain Sciences, 9:639–686, 1986.

[11] Reid Simmons and Randall Davis. Generate, test, and debug: Combining associational rules and causal models. In Proceedings of the Tenth International Joint Conference on Artificial Intelligence, pages 1071–1078, 1987.

[12] Robert L. Simpson. A computer model of case-based reasoning in problem solving: An investigation in the domain of dispute mediation. Technical Report GIT-ICS-85/18, Georgia Institute of Technology, 1985.

[13] E. P. Sycara. Resolving adversarial conflicts: An approach integrating case-based and analytic methods. Technical Report GIT-ICS-87/26, Georgia Institute of Technology, 1987.

[14] Patrick H. Winston. Learning new principles from precedents and exercises: The details. AIM 632, Massachusetts Institute of Technology, Artificial Intelligence Laboratory, 545 Technology Square, Cambridge, MA, 02139, 1981.