%-*- Mode: Latex; Default-character-style: (:SWISS :ROMAN :NORMAL) -*-
\documentstyle{article}
%\input <ELAN>MARGINS.TEX
\input margins.tex

\begin{document}

\begin{titlepage}
\begin{center}
{\large Integrating  Case-Based and  Model-based Reasoning: \\
A symbiotic system}
\end{center}
\vspace{.2in}
\begin{center}
Phyllis Koton\\
MIT Laboratory for Computer Science\\
Clinical Decision Making Group\\
545 Technology Square, Room 371\\
Cambridge, MA 02139
\end{center}
\vspace{.5in}

\begin{center}
Abstract
\end{center}
\vspace{.1in}

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.

\vspace{.1in}

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.

\end{titlepage}

\section{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
\cite{Kolod85} 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. 
 
\section{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
\cite{LNCJ86}, an expert system for managing patients with heart disease.
The case-based reasoning component uses a self-organizing memory system
\cite{Kolo} to store descriptions of all patients the program has seen, and
generalizations derived from similarities between the patients.  The patient
description is comprised of {\it 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\footnote{the relationship between
physiological states in the model and observable features of the patient.}, a
diagnosis,
and therapy suggestions for a new patient using a five-step process.   
\begin{itemize}
\item Retrieval.  CASEY finds a  case similar to the new patient  in its
case memory.  
\item 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.
\item 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 {\it de novo}.
\item Storage.  The new case and its solution are stored in CASEY's memory
for use in future problem solving.\footnote{The 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.} 
\item Feature evaluation.  The features which were causally important in the
solution of this problem are noted in the memory.
\end{itemize}

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.

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.

\section{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, \cite{Simpson},
\cite{Hammond86}, \cite{Bain}).  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 {\it 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~\ref{oprah} shows a sample patient  presented to CASEY, Oprah.
\begin{figure}
{\tt
\begin{verbatim}
(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))
\end{verbatim}
}
\caption{Description of patient Oprah.}
\label{oprah}
\end{figure}
The retrieved case for Oprah, a patient named Mary, is shown in
Figure~\ref{mary}.\footnote{The 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.}
\begin{figure}
{\tt
\begin{verbatim}
(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*))
\end{verbatim}
}
\caption{Description of patient Mary.}
\label{mary}
\end{figure}
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 {\it similarities} between the two cases.  It
now calculates the {\it differences} between the two cases (shown in
Figure~\ref{diffs}) and passes this information to the justifier, along with
the solution retrieved from Mary's case.
\begin{figure}
\begin{tabular}{lll}
Feature name  & Value for Mary & Value for Oprah \\ \hline
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
\end{tabular}
\caption{Differences between patients Mary and Oprah.}
\label{diffs}
\end{figure}

\section{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.\footnote{The
differences can also affect the diagnosis and therapy, however these follow
from the causal explanation.}   CASEY therefore uses a set of {\it 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 {\it justifier}.

A difference is {\it 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 {\it 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~\ref{frag}.
\begin{figure}
\vspace{2in}
\caption{A fragment of Mary's causal explanation.}
\label{frag}
\end{figure}
The feature {\sc 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: {\sc ekg: lvh} and {\sc 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 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.

\section{Adaptation}

Modifications to the solution are necessary for partial matches between
cases {\it 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 {\sc
ekg: lv strain} from the state LV HYPERTROPHY, and add the evidence {\sc
ekg: lvh} and {\sc lv cardiomegaly} to the list of evidence supporting that
state.  Repaired solutions do not have to be tested (as is required in, e.g.,
\cite{Hammond86}, \cite{Simmons87}) because the validation of the
solution by the model has already taken place in the justification
phase.

\section{Storage}
\label{stor}


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 similarity-based 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 \cite{Kolod85}.  CASEY generalizes
{\it 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 {\it 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.

\section{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 {\it 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 {\sc ekg: lvh} and {\sc 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 causally-related features
is reasonable because because causality often indicates which features are
important in the case for matching \cite{Winston81}, \cite{Schank86}.

\section{Related work}

CHEF \cite{Hammond86} 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
\cite{ResnickDavis} 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 \cite{Patil} maintained a description of the
patient at five levels of detail.  It did not have a learning component.  The
Generate, Test and Debug method \cite{Simmons87} always uses its causal
model to test proposed hypotheses, and always generates them using
associational rules.  CASEY {\it 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 \cite{Sycara} and MEDIATOR
\cite{Simpson}.  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  \cite{Hunter},
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.

\section{Discussion and conclusions}

CASEY {\it 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 {\it most likely} explanation of the evidence, not merely {\it
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 \cite{Kolodner88} 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~\ref{stor}.   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.


\section*{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.

\bibliographystyle{plain}
%\bibliography{bibcite:bibcite;abbrevs,bibcite:bibcite;bib}
\bibliography{abbrevs,bib,crossref}


\end{document}


