Using Experience in Learning and Problem Solving by Phyllis Koton 5.B, Massachusetts Institute of Technology (1980) §.M., Massachusetts Institute of Technology (1983) Submitted to the Department of Electrical Engineering and Computer Science in Partial Pulfillment of the Requirements for the Degrce of Doctor of Philosophy at the Massachusetis Institute of Technology May, 1988 © Massachusetts Institute of Technology 1988 Signature of Author Depastfnent of Electrical Engineering anc Computer Science May 5, 1988 Certified by_ ~~ Peter Szolovits Associate Professor, Electrical Engineering and Computer Science _Ahesis Supervisor Accepted by__= ru — Arthor C, Smith Chairman, Departmental Committee on Graduate Students a eg uy ery LB ra nies ARCHIVES: L.Using Experience in Learning and Problem Solving by Phyllis Koton Submitted to the Department of Electrical Engineering and Computer Science ‘on May 7, 1988 in partial fulfillment of the requirements for the degree of Doctor of Philosophy Abstract The problem-solving performance of most people improves with experience. The performance of most expert systems does not. People solve unfamiliar problems slowly, but recognize and quickly solve problems that are similar to those they have solved before. People also vemember probiems that they have solved, thereby improving their performance on similar problems in the future. The thesis describes a system, CASEY, that uses case-based reasoning to recall and remember problems it has seen before, and uses a causal model of its domain to justify re-using previous solutions and to solve unfamiliar problems. CASEY overcomes some of the major weaknesses of case-based reasoning through its use of a causal model of the domain. First, the model identi. fies the important features for matching, and this is done individually for each case. Second, CASEY can prove that a retrieved solution is applicable to the new case by analyzing its differences from the new case in the context of the model. CASEY overcomes the speed limitation of model-based reasoning by remembering a previous similar case and making small changes to its solution. It overcomes the inability of associational reasoning to deal with unanticipated problems by retognizing when it has not seen a similar problem before, and using model-based reasoning in those circumstances. The techniques developed for CASEY are shown to result in solutions identical to those derived by a model-based expert system for the same domain, but with an increase of several orders of magnitude in efficiency. Furthermore, the methods used by the system are domain-independent and should be applicable in other domains with models of a similar form. Thesis Supervisor: Peter Szolovits Title: Associate Professor, Electrical Engineering and Computer Science 2Acknowledgements I would like to thank the following people who helped make this thesis possible: My thesis supervisor, Peter Szolovits, for seven years of support and good advice, .couraging me to keep going when I was ready to give up, and for giving me the intellectual freedom to let my ideas develop and grow. Ramesh Patil, who as teacher, reader, and friend, taught me about artificial intelligence, medicine, engineering, and life in general. William Long, whose knowledge, good nature, and patience inspired me, and whose Heart Failure program is a challenging and impressive body of work that I was extremely fortunate to have as a resource for my own research. Patrick Winston, who did exactly what he promised, and whose comments during my thesis defense made it quite a pleasant experience. Janet Kolodner, to whom I owe an immense intellectual debt, for reading this thesis although under no official obligation to do so, and for supporting me in so many ways. Robert Jayes, who provided the test cases for my program. ‘The members of the Clinical Decision Making Group, past and present, especially Tom Russ, Elisha Sacks, Mike Wellman, Alex Yeh, Robert Granville, and Isaac Kehane, for many years of camaraderie, peer review, and good ideas, and Nomi Harris for making our office such a fun place. Paul Resnick, for some very illuminating discussions. My friends David Goddeau and Kent Pitman for all-around good advice since the time we were undergraduates. ‘And of course, my family: my daughter Jaclyn, my husband Ben (a merci-less editor), and my parents, without whose love, support, time, and sacrifices I could never have finished this thesis. ‘The work reported herein has been supported in part by National Institutes of Health grants RO1 LM 04493 from the National Library of Medicine and RO1 HL 33041 from the National Heart, Lung, and Blood Institute.Contents 1 Introduction Ll Background»... 02.00.20. 000% eee eee 1.2 Associational vs. model-based reasoning ............ 1.3. Using past problem-solving experience... 2... 0-455 14 The domain of medical decision making. ......... 1.5 Asimple example... ........-.. bees 2 Design and operation 2.1 Overview of the memory system... [Link] 2 ee ee 2.2 Overview of the Heart Failure Program... ..........- 2.3 Overview of CASEY . 0.0... eee eee eee 24 Matching and Retrieval... 0.2... 2.4.1 Determining the relative importance of features. 24,2 Choosing the Best Match ............ 25 Justification... ......2..0005 cece eee 2.6 Adapting the solution. .............- 2.6.1 Explanation Repair Strategies . . .27 2.6.2 Diagnosis and therapy repair Storage and feature evaluation. .......... Implementation 31 3.2 3.3 34 35 3.6 Interface with the Heart Failure program Implementation of the memory nodes ...... « 3.2.1 Generalizations .. . 3.2.2 Cases... 0... eee eee cere Complexity of the memory scheme ....... Constructing a similarity metric... . . Implementation of the justifier........... Implementation of the repair strategies . . . Results 4l 42 A detailed example .........-0.0-05 Analysis of CASEY’s performance... .... . « Discussion 5A 5.2 5.3 54 55 5.6 Strengths of the method ....... 00.20. Limitations ©... 1... eee eee eee Learning... 0... eee eee eee 5.3.1 Learning by generalization ......... 5.3.2. Improving on the Heart Failure program .......« Indexing 20.0. Defaults and exceptions»... ....-.0 05 Relation to formal theories of diagnosis... . . . 56 37 59 59 61 64 66 68 69 70 7 825.7 58 5.9 5.10 CBR vs. generate-and-test ©... 0... eee ee 102 Generality of the Method... ... cece eee eee 104 5.8.1 Requirements... ...-...000-0005 se 104 5.8.2 Other aspects of generalization ............- 105 5.8.3 Application to more complex models .......-. 106 Future Work... 0. eee 109 Conclusions... 2...) eee 118Chapter 1 IntroductionThe problem-solving performance of most. people improves with experience. The performance of most expert systems does not. People solve unfamiliar problems slowly, but recognize and quickly solve problems that are similar to those they have solved before. People remember problems that they have solved, thereby improving their performance on similar problems in the future, People also learn from their mistakes. Research in artificial intelligence has resulted in techniques that exhibit some of these capabilities. Associational reasoning solves common problems quickly. Model-based reasoning’ can be used to solve unfamiliar problems, but it does so slowly. Memory-based rea- soning [22] techniques can be used to remember previously solved problems and to learn from experience. However, no current system demonstrates all three capabilities. A seasoning system that (1) used associational reasoning for efficiency, (2) used model-based reasoning for robustness, and (3) learned from experience, could combine the advantages of each technique while com- plementing their individual limitations. Such a method would represent a substantial enhancement of current technology. This thesis presents the the- ory, implementation, ard evaluation of such a system, CASEY. 1.1 Background Much of the recent research in artificial intelligence has been directed towards the development of high-performance, domain-specific problem solving sys- tems, called expert systems or knowledge-based systems. Such systems can be ‘by which I mean reasoning from a causal model of some domain.classified according to the type of reasoning used by the program.? The vast majority of current expert systems rely on associational reasoning (associating data with solutions via heuristics, empirical associations, or “rules of thumb”). ‘The alternative approach, which solves problems by reasoning about a model of the behavior of objects in the domain, is known as model-based reasoning? Each approach has its advantages and disadvantages, but neither approach allows expert systems to learn from experience. Although work in machine learning has developed techniques that allow computer programs to learn, bar- ring few exceptions (e.g., AQ11 [31]) these techniques have not been applied to expert systems. Furthermore, this work has concentrated on the development of rule sets through training examples, after which learning ceases. People seem to use both associational and mode!-based reasoning. For fax miliar problems, we use associational reasoning, taking advantage of the speed of this approach. When confronted with unfamiliar or difficult problems, peo- ple can refer to a more detailed knowledge base, much like the type used by model-based systems. The human ability to exploit both types of reasoning requires us to (1) recognize a new problem as being of a type we have en- countered previously, and to (2) constantly update our knowledge; that is, to learn from experience. Current knowledge-based systems rely on knowledge painstakingly compiled from human experts, a process that is time-consuming This dichotomy had previously been identified as “shallow vs. deep” knowledge. How- ‘ever, the difference is in the inethod of reasoning, since the distinction between deep and shallow knowledge is relative [25], and deep knowledge can be employed with techniques traditionally considered shallow (18). Also known as “reasoning from first principles” [9]. 10and labor-intensive. When faced with the same problem twice in succession, they work just as hard to solve the problem the second time. The development of a technique that integrates associational and model-based reasoning with the ability to learn from experience could result in improved system perfor- mance. 1.2 Associational vs. model-based reasoning Associational reasoning reduces long chains of inferences in the underlying “deep” knowledge to shorter, often uncertain, links between data and solu- tions. This approach has the advantage of efficiency, because the alterna- tive of following all of the intermediate links and choosing among alternate paths in the problem space can be slow and is often unnecessary. However, programs using associational reasoning have their limitations. Because such programs solve problems by matching the current situation against a set of predetermined situations, the knowledge base must anticipate situations that may arise. If the program is presented with an unanticipated, peripheral, or difficult problem, it may be unable to solve it [8] or worse, appear to solve it but yield a solution that is incorrect [24]. Also, associational knowledge typi- cally must contain maay implicit assumptions. For a complicated domain, it might be infeasible or impossible to explicitly enumerate the exact conditions under which the knowledge is applicable. Such systems, therefore, cannot ensure that their knowledge will be applied correctly. Models provide a different kind of knowledge for reasoning in many do- mains. Knowledge about the domain that might be excluded from an associ- uational reasoning system is often explicitly represented in the model. Models are typically combined with a general reasoning method, such as simulation or search, affording the model-based system more flexibility than an associa- tional system for the same domain [9], [24], [44]. However, the more explicit, knowledge and more general problem solving method creates longer inference chains. For this reason, model-based systems are slower, more complicated, and less widely employed than associational systems. Also, if the relationships in the model are uncertain, long inference chains may generate too much un- certainty to draw conclusions. Associational reasoning allows the relationships to be summarized at a manageable level of uncertainty. ‘There have been a few previous attempts to combine associational rea- soning with model-based reasoning. ABEL [34], a program for diagnosing acid-base and electrolyte disturbances, maintained a description of a patient’s illness at five levels of detail. ‘The least-detailed level represented associational knowledge and the more-detailed levels were used for model-based reasoning. However, rather than choosing when to solve a problem using associational rea- soning and when to use model-based reasoning, ABEL always reasoned about the patient at every level of detail. GORDIUS [45] combined associational reasoning and reasoning from a causal model for hypothesis generation in the geology domain. It also was incapable of deciding when to use each type of knowledge. It always used its associational rules to generate hypotheses, and always used its causal model to test proposed hypotheses. 121.3 Using past problem-solving experience The ability to identify similar problems, recall previous problems, and store newly-solved problems could enhance a knowledge-based system’e performance in several ways. Common problems could be solved more efficiently because the system could recognize that it already knew how to solve ther and apply previously derived solutions. By remembering problems after it solved them, the system could continually increase the collection of problems that it knows how to solve. The system could also modify its knowledge by allowing the user to override the program’s solution, and remembering the solution that the user preferred. There have been several machine learning techniques developed that allow identification and recall of similar problems, for example case-based reason- ing [23], memory-based reasoning [47], and derivational analogy [7]. These paradigms all rely on a memory of previously solved cases. Case-based reason- ing and derivational analogy have the same basic framework when presented with a new problem. The programs recall a previous solution, adapt it to the current problem, and remember the new problem and its solution. Memory- based reasoning is used to remember a similar previous problem, but does no adaptation. These paradigms are fundamentally associational: they asso- ciate features of a problem with a previously-derived solution to that problem. However, neither case-based reasoning nor memory-based reasoning have been used with a strong causal model, and so their adaptations of previous solutions are basically ad hoc, Derivational analogy goes to the other extreme: it is so careful about justifying its use of each step in a previous solution that it loses 13the efficiency advantage of associational reasoning. Winston's work on anal- ogy [50, 51, 52] uses the causal explanation of a previous situation to produce a solution for a new problem. However, this work does not address the issues of remembering, determining the applicability of, and choosing among previous similar problems. Case-based reasoning was the most applicable to CASEY’s goals of com- bining associational reasoning, model-based reasoning, and learning from ex- perience. By their ability to match the features of a new problem against a memory of previously-solved problem, case-based reasoning systems achieve the efficiency of associational reasoning. If no previous case is recalled, it could serve as a signal that the problem is unfamiliar to the program and that model- based reasoning should be used. By their ability to remember new problems and their solutions, case-based reasoning systems continually increase their collection of easily solved problems. Most importantly, as several similar cases are solved, most programs that use case-based reasoning (e.g., citeKolo, [46], {48]) make and remember generalizations about the problems that they have solved and the solutions to these problems. These generalizations represent new associational knowledge which links the common features of a group of problems with a solution to that type of problem. Until now, case-based reasoning has been applied only to domains without a strong causal model (e.g., SHRINK [21] in psychiatry, MEDIATOR [46] in dispute mediation, PERSUADER [48] in labor negotiations, JUDGE [5] and HYPO (4] in legal reasoning, PLEXUS [2] in real-world planning, SWALE [16] in newspaper story explanation). The lack of an explicit causal model gives case-based reasoning programs a problem commonly seen in other associational “4reasoning systems: they cannot ensure that their knowledge will be applied correctly. There is one underlying reason for this: without an explicit causal model, case-based reasoning programs depend exclusively on coincidence in selecting similar previous problems* and in making generalizations. A second problem, also seen in associational reasoning systems, is that when an adequate match is not found, case-based reasoners are unable to fall back on model- based reasoning and must still use the best match available to atrive at a solution. A consequence of these two limitations is that a retrieved solution sometimes leads a case-based reasoner down the wrong path. A previous case-based reasoning program which did use a causal model was CHEF {13}, a planning program in the domain of cooking. CHEF’s causal model was extremely simple. Moreover, its causal reasoning consisted solely of chaining rules backward from an observed failure to a cause. This approach could not scale up to a reasonably sized domain. Furthermore, his causal model was not used to derive a solution de novo, Integrating associational, model-based, and case-based reasoning results in a program which has the strengths of each approach while compensating for their weaknesses. ‘The model-based reasoning component solves compli cated and unfamilar problems, and releases the case-based component from its dependefice on coincidence. The case-based reasoning component uses as- sociational knowledge to recognize problems that the system already knows how to solve, and allows the constant creation of new associational knowledge by the program. The combination is synergistic. ‘memory-based reasoning programs also have this drawback. 151.4 The domain of medical decision making Asa complex real-world domain, medical decision making is particularly well- suited as a testbed for combining associational reasoning, model-based reason- ing, and learning techniques. Medical decision making involves an experiential component as well as reasoning from causal models. Physicians start with a large basic and clinical science knowledge base. Then, the accumulation of cases seen over a physician’s career improves his day-to-day problem-solving ability. Making generalizations about previous patients lets a physician make predictions about future similar patients; remembering how an unusual past case was resolved can be helpful the next time a similar case is seen. How- ever, when a good physician confronts an unfamiliar problem he refers to his knowledge of pathophysiology ~ his model. Medical reasoning is more challenging than some other diagnosis domains that typically deal with “single faults” and have an underlying model that is small and well-characterized (e.g. digital circuit diagnosis). ‘The models used in the medical domain are often large and complex. They are incomplete and therefore uncertain. Medical problems can include multiple interacting diseases with partially overlapping symptoms, which are problematic for many diagnosis programs. For these reasons, the ideas developed for CASEY were tested in the do- main of managing patients with heart failure. The techniques do not depend on any specific domain information and therefore should be applicable to other domains with similarly designed models. 161.5 A simple example The input to CASEY is a description of a patient. CASEY produces its solutions using a memory of cases that it has already solved and a causal model of the cardiovascular system. CASEY’s output is a causal explanation of the patient’s symptoms. The causal explanation relates items in the patients description to states in the model. This section gives a simple example of CASEY’s operation. A new patient, Uri, is presented to the program. Uri is a 67-year-old male with dyspnea (shortness of breath) on exertion and a history of anginal chest pain. His blood pressure is 135/80, his heart rate is 87, his respiration rate is 14, and his temperature is 98.4. His chest x-ray reveals aortic valve calcification. The rest of his physical examination is normal. The best match CASEY finds for Uri is a patient named Sarah. She was a 72-year-old woman with a history of angina, complaining of unstable anginal chest pain. Her blood pressure was 138/81, her heart rate was 76, her respi- ration rate was 14, and her temperature was 98.4. The rest of her physical examination was normal. ‘The causal explanation for Sarah’s findings retrieved from the memory is shown in Figure 1.1.5 It indicates that her chest pain was caused by a fixed coronary obstruction. She was suffering from both exertional angina (which “in this and all subsequent causal explanation diagrams, items in upper case indicate states in the model of the cardiovascular system. Items in bold face are diagnosis states Ttems in lower case are inputs to the program. An arrow from item A to item B indicates that A causes B. A lack of connection between items indicates that they are not causally related WyFIXED CORONARY OBSTRUCTION + REGIONAL FLOW DEFICIT ———p UNSTABLE ANGINA t t EXERTIONAL ANGINA unstable anginal chest pain + tory of an al chest pain Figure 1.1: Causal explanation for Sarah. explained her history of angina), and unstable angina (which explained her unstable anginal chest pain). CASEY’s next task is to determine whether the solution for Sarah can be adapted to fit Uri. The differences between the patients, shown in Table 1.5, might make the solution unsuitable. One of Sarah’s symptoms that was used as evidence in the solution (unstable angina) is absent from Uri’s case. Similarly, Uri exhibits symptoms that are absent from Sarah’s case and which must be explained. Using information in its causal model and a set of principles for reasoning about causal explanations, CASEY makes the following judgements about the differences between Sarah and Uri: 1. No state in the model of the cardiovascular system uses the sex or age of the patient in any way, so these differences are insignificant. 2. Dyspnea is a significant symptom. CASEY knows this because the model contains the information that when a patient has dyspnea on exertion, 18Feature: Sarah Uri Sex female male Age 2 87 Dyspnea none on exertion Chest pain unstable angina none Blood pressure 138/81 135/80 Heart rate 76 87 Chest x-ray normal aottic-valve calcification Table 1.1: Differences between Sarah and Uri. it can be explained by the model 70% of the time. 3. Uri does not have any evidence for unstable angina. This part of the diagnosis does not fit Uri. 4. The difference between the two patient’s blood pressures is insignificant. 5. Uri’s heart rate is slightly high, while Sarah’s is normal. However, a slightly high heart rate does not strongly suggest any disease, so it can be ignored. 6. Aortic valve calcification has only one cause: aortic valve disease. Aortic valve disease must be part of the solution for Uri. CASEY can repair Sarah’s solution to fit Uri by 1. adding dyspnea on exertion as an unexplained feature, 2. removing the diagnosis of unstable angina, 19AORTIC VALVE DISEASE FIXED CORONARY dyspnea on exertion, | OBSTRUCTION aortic valve calcification REGIONAL FLOW DEFICIT t EXERTIONAL ANGINA + history of anginal chest pain Figure 1.2: Causal explanation for Uri. 3. adding the diagnosis aortic valve disease to account for the aortic valve calcification. ‘The results of these repairs are shown in Figure 1.2 This is identical to the causal explanation for Uri produced by the Heart Failure program. CASEY’s explanation, however, is derived without running that program, but by adapt- ing the solution of the past case. This method is significantly more efficient. 20Chapter 2 Design and operation2.1 Overview of the memory system CASEY remembers cases it has seen by storing them in a self-organizing mem- ory system [17]. A self-organizing memory system records and organizes ex- periences or cases. The memory system also creates generalizations, which are structures that hold knowledge describing a group of similar cases! A generalization is created from the similarities between the cases that it orga- nizes. Individual cases that are stored in a particular generalization structure are indexed by the features that distinguish them from the other cases in the same generalization structure. As a new case is integrated into a generaliza- tion, it “collides” with the cases in the generalization that share its differences. This is termed reminding [42]. Two cases are said to be similar if they are integrated into the same generalization and share a set of differences with the generalization. The implementation of the memory structure is based on the memory de- scribed by Kolodner 17]. Following Kolodner’s scheme, the memory structure is represented as a discrimination net in which each node is either an indi- vidual case or a generalization structure (called a GEN). Each pointer to a subnode is labeled (indexed) by a feature of the subnode that differentiates it “TA note om terminology: Kolodner [17] used the terms Memory Organization Packet (MOPs), features, and norms to describe the structures in a self-organizing memory. The same structures can be thought of aa frames, slots, and typical values; or concepts, roles, to holding general (ie. prototypical) information (that which is true of a typical episode organized by this and prototypes. A MOP is a specialization of a frame that, in addi MOP), also contains a hierarchical structure that indexes all the episodes organized by this MOP. Kolodner later [19] began referring to MOPs as “generalized episodes.” 22from the parent node. Indexing requires two levels (see Figure 2.1). The first level indicates the category of the index (e.g., syncope/near-syncope). The second level indicates the values that the feature takes on in the subnodes (eg., syncope/near-syncope on- exertion; syncope/near-syncope at-rest). The set of indices defines a set of paths through the memory structure. At each point in the path, one of three conditions obtains. If exactly one case is stored at this point, the stored case and the new case are compared, their similarities placed in a new generalization, and they are indexed beneath the generalization by their differences from each other. Also, the stored case is returned (the program is “reminded” of it). If there is a generalization at the point, the new case is indexed in the existing generalization. If there is no further information that distinguishes the new case from the other cases stored in the GEN, the common features of the GEN are returned.” If no other case is stored at this point, the new case is simply installed there, and the common features of the GEN directly above this point are returned. 2.2 Overview of the Heart Failure Program CASEY is designed around an existing model-based expert system (the Heart Failure program [30]) that diagnoses and suggests therapy for patients with heart failure. The building blocks of the Heart Failure model are measures, measure values, and states. Measures correspond to observable features, such as heart rate, or laboratory results. Measure values are the input values of In medicine, this would be an instance of a case being a “classic presentation” of some diseaseGEN *FEATURE-GEN* NODES: 46 FEATURES (auscultation 52) (angina unstable) (Geox mate) DIFFS —acute-mi _syncope/near-syncon GEN 808 NODES: 23, FEATURES (cardiomegaly ty) (apex-impulse sustained) (s2 single) (characteristic-murmur (pulse slow-rise) (chest-pain anginal) (dyspnea on-exertion) CAUSAL limited-cardiec-output _general-flow-deficit ‘exertional angina fixed-high-outflow-resistance slow-sjection aortic-stenosis. ) DIFFS. known diagnoses heart-rate auscultation .. Figure 2.1: A fragment of the memory structure. 4(defnode mitral-stenosis goal diagnosis causes (primary (.003 (if (female sex) .01 .001)) P+ (mitral-valve-disease :prob .1) D- (mitral-valve-replacement)) measure ((characteristic-murmur (prob ms .5)) (murmur (prob diastolic-rumble .5)) (nistory-findings (prob hemoptysis .1)) (cxr (prob kerley-b-lines .2)) (EKG (prob (or first-degree-block wenckebach) .1)) (si (prob loud .75)) (auscultation (prob 1v-s3 (p- 1.0))) (auscultation (prob opening-snap .7)) (valvular-diseaso (prob MS 1.0)))) Figure 2.2: Information about mitral stenosis. the measures, for example, “68” for the patient’s heart rate, and are entered by the user. The combination of a measure and a measure value is referred to as a finding. States can represent three types of information: specific qualita- tive assessments. of physiological parameters, for example HIGH LEFT ATRIAL PRESSURE; the presence of diseases (“diagnosis” states), for example PERI- CARDITIS; and therapies given to the patient, for example NITROGLYCERIN. Some states are distinguished as “goal states”. These are states that can be treated. The Heart Failure program's information about the state MITRAL STENOSIS is-shown in Figure 2.2.° The model recognizes two kinds of relation- ships. It can indicate that one state causes another with a given probability. It can also indicate that a state is associated with a particular finding with ates that thi jgoal diagnosis 1 diagnosis state, P+ indicates an uncertain cause; De indicates a definite correction. The measure slots indicate the probability with which a patient with mitral stenosis will have the given finding. 25a given probability. There are over 400 findings and about 140 states defined in the model. The model is represented as a causal inference network. States in the model are shown as nodes. They are connected by links indicating the direction of causality, whether the influence is positive or negative, and probabilities associated with the link. ‘The Heart Failure program takes as its input a list of findings that describe the patient. A patient description typically consists of about 40 findings. The description for a new patient presented to the system, Larry, is shown in Figure 2.3. From the input, the Heart Failure program produces a solution consisting of a causal explanation, a diagnosis, and therapy suggestions for the patient. The causal explanation describes the relationship between physiolog- ical states in the model and observable features of the patient. The diagnosis and the therapy suggestions are derived from states in the causal explanation. ‘The causal explanation consists of a set of findings, states, and directed links (Figure 2.4). A link between two states, or a state and a finding, indi- cates that one causes the other. Only abnormal findings are explained, but the program may not explain all abnormal findings. If a diagnosis state is established in the causal explanation, the name of the state is added to the patient's diagnosis. If a goal state is established, the therapy associated with that state is added to the list of therapy suggestions for the patient. ‘The prototypical concept of a causal model in artificial intelligence is one that contains descriptions of a set of primitive objects and a set of operations that exist in some domain. In order to derive the overall behavior of the system, programs which use this kind of model (e.g, (12), [24], {49}, [13], [45], ete.) compute the effects of applying the operations to the objects until some end- 26(DEFPATIENT “Larry” HISTORY (age. 65) (sex male) (dyspnea on-exertion) (orthopnea absent) (chest-pain anginal) (anginal vithin-hours unstable) (syncope/Near-syncope on-exertion) (palpitations none) (nausea/Vomiting absent) (cough absent) (diaphoresis absent) (hemoptysis absent) (fatigue absent) (therapies none) VITAL~SIGNS (blood-pressure 138 80) (heart-rate . 90) (arrhythmia~monitoring normal) (resp . 20) (temp . 98.4) PHYSICAL-EXAM (appearance nad) (mental-status conscious) Gugular-pulse normal) (pulse slow-rise) (apox-impulse normal) (parasternal-impulse normal) - (chest clear-to-auscultation-and-percussion) (abdomen normal-oxam) (extremities normal-exam) LABORATORY-FINDINGS (ekg 1vh normal-sinus) (car calcification) (calcification mitral aortic-valve)) Figure 2.3: Patient description for Larry 27pin arm prams 107 ow rena renson expe (22) 2+ ws sentcmmacroon\ esto ~—— i 1 orn $2248 aaron ernopae 208) Ine $2 enzo ne 10 “rps on aerton (05) nar wyocanous onvarn nuh (208) Acme acta spe (2919) sugedeaonrveaeg 59m 28 (0019) eer Cardiomyopathy Session 1 @ 8/26/87 16: int ata Notes Cog 63 cat, Sem race SS nae nena ee A a ey unpre pein mena case SST ihe le See cee a em ted wenn ra [Connand: System Set Time Save Toad are Jbeck've Ltep Top Level tn Ltsp Pane 1. ood Patient Refresh Run Cosey Eval Evidence| Failure ane Rich rite paleo Sailure A causal explanation produced by the Heart Failure Program. 28state or goal is achieved. This computation often takes the form of a simulation or search. The trace from initial state to end-state of the effects of operations on the objects in the system is called a causal explanation of the observed end- state. When the effects of applying an operation cannot be determined (as when computing the combined effects of two opposing influences of unknown magnitudes) such systems usually create multiple “possible worlds,” one for each uncertain conclusion. For simple systems this method can be useful. For some other domains, and in particular the cardiovascular domain in which the Heart Failure program operates, the cost of simulation is prohibitive due to the presence of approximately 270 feedback loops in the portion of the domain that the model covers. Furthermore, the cost of maintaining multiple possible worlds is also high in this particular domain. Much of the data needed for simulation can only be obtained invasively;* so it is not usually available. This results in en explosion of possible worlds [29]. The Heart Failure program therefore uses a different approach. When the information about states, their causes, and their effects is loaded into the Heart Failure program, the program precomputes the trace of the system under various conditions. The diagnos- tic task, then, is to work backwards from features in the patient description through the trace of potential causes and effects, to find the states which ulti- mately causéd the symptoms. The paths from ultimate (or primary) cause to observed features is the causal explanation. The causal explanation is derived through a complicated process which involves causal, probabilistic, and heuristic reasoning. The Heart Failure pro- that is, by inserting measurement devices into or otherwise invading the patient's body. 29gram propagates evidence backward from the findings to the states that cause them. Some findings have definite causes; those states are established imme- diately. For each remaining unexplained finding, the system examines every pathway through the model from every diagnosis that could cause the find- ing. The process of producing an explanation is complicated by the presence of the 270 feedback loops in the model. It is further complicated because the links between findings and the states that cause them are frequently uncertain, so several possible explanations for the patient’s findings must be considered simultaneously. The system allows for multiple diseases, and attempts to find a set of diagnoses that “cover” the findings. Each of these covering sets is evaluated and the most probable is selected. The Heart Failure program was designed to deal with complex clinical situ- ations. Its model has evolved painstakingly over several person-years of effort. Like other model-based programs, it is capable of solving difficult and unusual cases. However, like other model-based programs, its reasoning is extremely expensive computationally. For this reason, the Heart Failure program was an excellent testbed for enhancement through the use of experience. 2.3 Overview of CASEY CASEY attempts to produce the same causal explanation, diagnosis, and ther- apy suggestions for a new patient (the case that CASEY is currently trying to solve) as the Heart Failure program. It does so by integrating model-based reasoning, associational reasoning and case-based reasoning, in a five-step pro- cess: 30© Retrieval. CASEY finds a case similar to the new patient in its case memory. This is called the retrieved case. © Justification. CASEY evaluates the significance of any differences be- tween the new case and the retrieved case using information in the Heart Failure model. Ii significant differences are found, the match is invali- dated. If all differences between the new case and the retrieved case are judged insignificant or if the solution can be repaired to account for them, the match is said to be justified. The precedent case is a retrieved case that has been justified and from which solution transfer will occur. ‘The precedent solution is the solution associated with the precedent case. ‘¢ Adaptation. If none of the differences invalidate the match, CASEY adapts a copy of the precedent solution (called the transferred solution) to fit the new case, If all matches are 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.* © Feature evaluation. Those features that were causally important in the solution of this problem are noted in the memory. ‘The model-based reasoning component of CASEY employs the model of the cardiovascular system developed for the Heart Failure program. Other "The user has the option of rejecting CASEY's solution, in which case Heart Failure progtam is used to produce a causal explanation, which is then stored in memory. 31programs which integrate associational reasoning with causal models (e.g CHEF and GORDIUS) use their causal model to simulate a proposed solution. The complexity of the Heart Failure program's model precludes simulation. CASEY therefore analyzes its proposed solution with respect to the causal model, by examining the relationships between evidence in the new case and states in the model. Associational reasoning is used in CASEY through the association of de- scriptions of new patients with previously derived solutions for similar patients. This type of association is created with each new patient by the case-based rea- soning component (see below). New associational knowledge is also constantly being created through generalizations. ‘The case-based reasoning component uses a self-organizing memory system [17] to store descriptions of every patient the program has seen, and generaliza- tions derived from similarities between the patients. The patient description is comprised of features, such as signs and symptoms, test results, history and current therapy information, and solution data, such as the causal expla- nation for the patient, the diagnosis, therapy recommendation and outcome information. Retrieving, adapting, and storing cases are standard procedures of a case- based reasofier. CASEY differs from previous case-based reasoning systems because it incorporates reasoning from its causal model in each of these steps. © Most case-based reasoning systems use a fixed and often a priori ranking that indicates which features of a new case are important for matching against cases in the memory (e.g., [5), [13], [46]). It is not always possible 32to determine in advance which features are going to be important, and furthermore, the important features may vary from case to case. CASEY therefore matches a new case against cases in its memory using every feature in the patient description. Using knowledge of which features were important in determining the causal explanation of previous cases, CASEY then determines the important features of the new case, and gives these features greater weight for matching. During justification, model-based reasoning is used to judge the signif- icance of differences between the new and previous cases. 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 pre- clude using even a modified version of a retrieved solution for a new problem. The justification step proves that a retrieved solution can be supported by the features of the new problem. © Feature evaluation uses the causal explanation of the new case to de- termine its important features. These are then recorded as part of the ccase’s representation in memory. Determining which features of the new problem were important to the solution helps the program make bet- ter matches in the future, because it allows the program to distinguish between extraneous and important features. CASEY demonstrates that combining a memory of past cases with reason- ing from a causal model can have significant advantages over either method used alone. 33* CASEY combines the efficiency of associational reasoning with the im- proved problem-solving ability of model-based reasoning. It can recog- nize when a case is routine and when it is not. It efficiently solves routine cases by making small local changes to an existing solution. CASEY can recognize that it does not know how to solve a particular problem. When this occurs, it can solve the case by using the Heart Failure program. ‘¢ CASEY’s performance improves with experience. It learns to solve more problems efficiently as it is given more problems to solve, because it remembers what it has done in the past. It can improve its knowledge by being corrected. ¢ CASEY can acquire new knowledge automatically by making generaliza- tions about problems that it has solved. It automatically acquires new associational knowledge by making generalizations about each new case presented to it. ‘© CASEY’s model-based reasoning component is enhanced by the abil- ity of the case-based component to learn new associations and compile detailed reasoning structures into simple associations between features and solutions. This results in both improved performance speed and in improved accuracy of the program as new information is added. CASEY’s case-based component is improved by the use of a causal model will be helpful for a because the model can prove that a retrieved soluti new case. Also, the model can be used to identify important features for matching. This results in the elimination of a major limitation of previ- 34ous case-based reasoning system, the need to fix the important features for mate! 352.4 Matching and Retrieval 2.4.1 Determining the relative importance of features When presented with a new problem, CASEY searches its memory for a similar case. It compares a new case against cases in its memory using all the features in the patient description. However, all features are not equally important in matching a new case to a previous case. Furthermore, the important, features for matching may vary from case to case. For example, the cardiac rhythm might be important and the heart rate unimportant for one case, whereas for another case, the opposite may be true. Therefore, unlike previous case-based reasoning programs, that use a fixed, and often a priori, measure of impor- tance, CASEY’s similarity metric allows the important features for matching to be determined for each retrieved case individually. CASEY performs this determination using information in the Heart Failure model. CASEY then compares the important features of the retrieved case with the features of the new case to determine similarity. Thus, although CASEY retrieves cases from memory on the basis of all features, it matches cases based on features known to be important. For CASEY, important features are defined as those that played a role in the causal explanation of previous similar cases.® eA a case-based reasoning program for the domain of law. However, CASEY’s causal model ilar reluctance to fix a set of important features for matching ie seen in HYPO (4), allows it to easily identify the important aspects of each precedent case. HYPO has no such model, and therefore must retrieve every precedent that partially matches the new case. Tt then ranks the precedents according to the number of dimensions (4) in common, and ‘examines them in that order. 36CASEY’s justifier does not requize that the new case be identical to a pre- vious case in order to use the latter's solution. In real-world domains, several different pieces of evidence may have equivalent implications. For example, LV strain on EXG and LV enlargement on chest x-ray are both evidence for the same state, LV HYPERTROPHY, even though they represent different fea- tures in a patient description. CASEY can repair a causal explanation that includes the state LV HYPERTROPHY to fit a new patient whose description includes evidence of LV HYPERTROPHY, say from an EKG, even if the evidence in the previous case came from a different source, such as a chest x-ray. For matching, therefore, it is sufficient to have features in both cases that are ev- idence for the same states in the model. CASEY generalizes features in the new case to refer to the states for which they are evidence.” These generalized features are called evidence-states, because they are states for which there is evidence in the patient. Later, at the time of storage, features of the new case that were used in that patient's causal explanation are generalized to refer to the states which they supported generalized causal features. For example, LV HYPERTROPHY ON EKG supporting the state Ly HYPERTROPHY becomes EVIDENCE-OF LV HYPERTROPHY. “7 Thus, CASEY incorporates a form of explanation-based generalization [33], (11), be- cause CASEY-generalizes the evidence to the level that retains the same causality. This is discussed further in section 2.7. The difference between evidence-states and generalized causal features is exactly that evidence-states are states which might be in the causal explanation, whereas generalized causal features refer to states that are in the patient’s causal explanation. 372.4.2 Choosing the Best Match An input case may have similarities with many previous cases. Most case- based reasoning systems use some sort of similarity metric to determine how similar two cases are, and to choose the “best” match from among the similar cases. A good similarity metric gives a high value for cases that are similar and a low value for cases that are dissimilar. CASEY typically recalls between. one and four cases similar to a new case, and places them in a list ordered according to a novel similarity metric. The score for each retrieved case is calculated using the evidence-states of the new case, the generalized causal features of the retrieved case, and the total number of features that the new case and the retrieved case have in common. CASEY’s task is to produce a causal explanation that links evidence and states in the model by finding previous cases that are similar to the new one and would thus have a causal explanation similar to the new case’s causal explanation. The relationship between the evidence-states of the new case and the generalized causal features of the retrieved case is thus vital to identifying good match. The generalized causal features of a past case essentially tell the matcher: “Here are the states for which I need evidence in order to generate this causal explanation.” The evidence-states of a new case essentially tells the matcher, “These are the states for which I can provide evidence.” A retrieved case that finds evidence for many of its generalized causal features in the new case will be a better precedent than a retrieved case in which few generalized causal features are matched by evidence-states in the new case. CASEY’s similarity metric thus orders matches according to the cardinality 38ralized causal features, of the intersection of the evidence-states and the g minus the number of generalized causal variables that are not matched by evidence-states. The purpose of the latter adjustment is to avoid matching relatively simple cases with large, complicated cases whose explanations cover the simple case but also have many extra states that will have to be removed (Figure 2.5). When two retrieved cases have the same score, the number of features in common is used to break the tie. The reason for this choice is that although the Heart Failure program ignores most normal values, there are many cases in which normal values are important in establishing or ruling out a diagnosis. Similarity metrics that match cases on the basis of generalizations of causally- related features are superior in case-retrieval to those that match cases on the basis of the causally-related features themselves. ‘Typically, many different fea- tures can provide evidence to support the existence of the same state, so many different combinations of features can give rise to the same causal explanation. A system that requires the same causally-related features for matching can- not retrieve a case whose causal explanation would be identical except for the particular features used as evidence for the states in the causal explanation. ® There is no point in considering the number of evidence-states which go unmatched by generalized causal features. This is because each feature in the patient description generates anywhere from zero to more than 10 evidence-states, so the number of unmatched evidence- states is unrelated to the quality of the match (except when no evidence-states are matched at all; this is detected separately). An interesting possibility would be to calculate how many of the new case's features had been covered by a generalized causal feature which matched some evidence-state in the set generated by that feature. This is left for future work. 39FIXED CORONARY OBSTRUCTION 4 REGIONAL FLOW DEFICIT | UNSTABLE ANGINA | ‘unstable anginal chest pain ‘New case FIXED CORONARY OBSTRUCTION 1 MYOCARDIAL REGIONAL FLOW DEFICIT ____ INFARCTION | | UNSTABLE ANGINA ____»_within-Hours anginal | N, chest pain unstable anginal chest pain MYOCARDIAL ISCHEMIA Lo MI ‘CURRENT hg: old infarct anterior ischemia Retrieved case igure 2.5: A match with many superfluous states. 40‘soft a2, AORTIC STENOSIS ‘single 82 AORTIC STENOSIS | | systolic FIXED HIGH OUTFLOW murmur FIXED HIGH OUTFLOW ‘gjection RESISTANCE ofes RESISTANCE ~ | | ‘SLOW EJECTION ‘SLOW EJECTION | | pulse has slow rise apex impulse = — Figure 2.6: A good match with no features in common. For example, Figure 2.6 shows the causal explanations for two patients who have no causally-related features in common. The two explanations, however, are identical, and therefore these cases represent good match. The purpose of a matcher is to retrieve cases whose causal explanations will be useful for the new case. Generalizing the causally-related features increases a matcher’s chances of finding relevant past cases, and this is the approach used in CASEY. CASEY first examines the retrieved case with the highest rank. If this match is ruled out (see section 2.5) and there is another retrieved case with a close score (currently, within 10% of the highest score), that case is examined. This continues either until a match is accepted or there are no remaining 41high-scoring matches. If the features of a new case are not evidence for any states that have been used to explain the findings of previous patients, CASEY can recognize that it does not know how to solve the case. This is analogous to a physician encountering a patient with a constellation of symptoms the physician has not seen before. Just as the physician would then consult his pathophysiology books, CASEY solves such a problem by invoking the Heart Failure program to find a solution for the new patient. 422.5 Justification A key question that physicians as well as other problem solvers must answer is whether different constellations of findings still support the same solution. Likewise, CASEY determines whether different features in the patient descrip- tion can still support the same solution by examining the relationship between evidence and physiological states in the Heart Failure model. The module in CASEY that performs this evaluation is called the justifier because it must justify using a retrieved case as a precedent for the new case, The justifier relies on a set of domain-independent heuristics for reasoning about evidence, termed evidence principles. The evidence principles reason about such con- cepts as alternate lines of evidence for states, additional supporting evidence for states, and inconsistent evidence. The first evidence principle is used to determine whether a state in the retrieved causal explanation is ruled out by evidence in the new case, the next four determine whether the difference in question is insignificant or repairable, and the last three handle features that, have special values. 1. Rule out. A state must be eliminated from the transferred solution if there is some feature in the new case that is incompatible with that state. Incompatibility is defined as zero probability of a feature coexisting with some state in the retrieved solution. For example, a heart rate of 40 beats per minute is incompatible with the state HIGH HEART RATE. Ruling out a state does not necessarily mean that the match is ruled out (see below). 432. Other evidence is used when a feature present in the retrieved case is missing in the new case. This principle tries to determine if there is another feature of the new case that supports the same state that the missing feature supported. For example, if the feature opening-snap supported the state MITRAL- STENOSIS in the retrieved case, but was absent in the new case, CASEY would consult the causal model to find other findings that could be ev- idence for MITRAL STENOSIS, such as loud S1 or diastolic rumble. CASEY would then search for these other findings among the features in the description of the new case (see Figure 2.7). ao ee | aed —_ pe ee — — Figure 2.7: Using the evidence principle other evidence. 3. Unrelated oldcase feature is used when a feature is present only in the retrieved case. If the feature was not used in the causal explanation, its absence has no effect on any states in the explanation, so it can be ignored. 444, Supports ezisting state is used when a feature is present in the new case but not in the retrieved case. This principle determines whether it is possible to attribute the feature to some state in the retrieved causal explanation. For example, if the feature ejection-click, which is evidence for the states PULMONIC STENOSIS and AORTIC STENOSIS, appeared only in the new patient, CASEY would check for the presence of either of these two states in the retrieved causal explanation. If one or more of these states were present, CASEY would attribute the new feature to that state (see Figure 2.8). | | “ — —_ Figure 2.8: Using the evidence principle supports ezisting state. 5. Unrelated newcase feature is also used when a feature is present only in the new case, This principle identifies a feature that is abnormal, but does not provide evidence for any existing state and is not strongly suggestive of a new state. Such a feature is added it to the explanation as an “unexplained feature.” 45specificity experier For example, the feature single $2 is abnormal, so it cannot be ig- nored. It is evidence for the states FIXED-HIGH-OUTFLOW-RESISTANCE and COPD-OR-CHRONIC-BRONCHITIS. But single S2 alone does not strongly suggest either of these states, so if neither of them are already present in the causal explanation, it is added to the causal explan: as an unexplained feature. 6. Normal. Normal values are not explained by the Heart Failure program, so a normal value in the new case is not explained. (Note that if a model did reason using normal values, this rule could be changed). 7. No information. If there is no information given about a feature in one of the cases and it is known to have a normal value in the other case, then it is also assumed to have a normal value in the former case. 8. Same qualitative region. CASEY evaluates differences between features with numerical values by translating them into physiologically equivalent ranges. For example, a blood pressure of 180/100 becomes “high blood pressure.” Features whose values fall into the same range are judged not to be significantly different. Information in the Heart Failure model is used to determine physiologically equivalent ranges. ToTThe information that CASEY uses to determine the advisability of ignoring a particular feature is called the specificity of the finding by the Heart, Failure program. It indicates the percentage of time the finding is explained by the model. The same number is called the “import” of a finding in the Internist-1/QMR [32] system. CASEY can also determine ly by examining the role the feature played in similar past cases, 46.The use of the evidence principles is not guaranteed to result in the same solution as the Heart Failure program. This is because they do not reason about the relative likelihoods of findings. This is discussed in more detail in section 5.2. However, any solution they do produce is guaranteed to be a valid possible explanation for the patient's symptom complex. ‘The changes that CASEY proposes to the retrieved solution are small and local to the difference being considered, and therefore they are computationally inexpensive. However, CASEY evaluates each change in the context of the entire solution. This prevents it from being oblivious to unwanted interactions that might be created by its changes. CASEY rejects a match either if a significant difference cannot be explained or if all the diagnosis states in the retrieved solution are ruled out. If all differences between the new case and the retrieved care are insignificant or repairable, then solutions are transferred from the precedent to the current case. 472.6 Adapting the solution CASEY uses repair strategies to adapt a previous solution to a new case. There are three types of repair strategies corresponding to the three parts of the solution: causal explanation, diagnosis, and therapy. 2.6.1 Explanation Repair Strategies Associated with each type of repairable difference detected by the evidence principles is an explanation repair strategy which modifies the precedent causal explanation to fit the new case. Repair strategies modify the transferred causal explanation by adding or removing nodes and links. CASEY makes seven types of repairs: 1. Remove state. This strategy can be invoked in two circumstances: either the state is known to be false, or all of the evidence that previously supported the state has been removed (the removed evidence could be either features missing in the new patient, or states ruled out during justification). In the first case, this strategy is invoked by the rule out evidence principle. In the second case, when all the evidence for a state is missing in the new case, or if the only cause of a state has been removed from the transferred causal explanation, CASEY removes that state from the explanation. CASEY also determines whether states caused by this state must now be removed. 2. Remove evidence. This repair strategy is invoked by the principles other evidence and unrelated oldcase feature. When a piece of evidence that 48was used in the retrieved case is absent in the new case, this removes the feature and any links to it. . Add evidence. This repair strategy is invoked by the principles other evidence and supports ezisting state. It adds a piece of evidence to the causal explanation, and links it to those states for which it is evidence. . Substitute evidence is invoked by the same qualitative value principle. When two numerical values have the same qualitative value, this repair strategy replaces the old value with the new value as evidence for some state. ). Add state. The only time CASEY adds a state to the causal explanation is when the feature it is attempting to explain has only one cause. This repair strategy is invoked by the principle supports existing state, because the fact that a feature has only one cause is discovered while CASEY is searching for existing states that cause this feature. When the evidence has only one possible cause, that state is added to the causal explanation. CASEY then tries to link it to existing states and features in the causal explanation (using add link). . Add link is invoked by the add state repair strategy, and is used to add a causal link between two states. . Add measure is invoked by unrelated newease feature. ‘This adds an abnormal feature which CASEY cannot link to the causal explanation. 49FIXED CORONARY OBSTRUCTION + REGIONAL FLOW DEFICIT ——— UNSTABLE ANGINA t 4 EXERTIONAL ANGINA unstable anginal chest pain + history of anginal chest pain Figure 2.9: Causal explanation with associated diagnosis of fixed coro- nary obstruction, unstable angina, and exertional angina. After explanation repair has been completed, CASEY can perform diagno- sis and therapy repair. 2.6.2 Diagnosis and therapy repair Because the diagnosis and therapy suggestions are deduced from a patient’s causal explanation, diagnosis and therapy repair take place after causal ex- planation repair. The diagnosis for a patient is simply a list of the diagnosis states in the patient’s causal explanation. For example, the causal explana- tion in Figure 2.9 indicates a diagnosis of fixed coronary obstruction, unstable angina, and exertional angina. Diagnosis repair strategies add and remove diseases from the transferred diagnosis. If 2 diagnosis state was removed from the transferred causal explanation during explanation repair, the correspond- ing diagnosis is removed from the patient's diagnosis list. If a diagnosis state 50was added to the causal explanation, that diagnosis is added to the patient’s diagnosis list. Therapy suggestions are derived from the goal states of the patient’s causal explanation. They are indicated in the Heart Failure model as states whose presence decreases the effects of state they directly affect. For example, the causal explanation in figure 2.9 produces only one therapy suggestion, coronary artery bypass graft, which is associated with the state fixed coronary obstruc- tion. The therapy repair strategies add a therapy suggestion if a treatable state is added to the causal explanation. They remove a therapy suggestion if the state that was asscociated with that therapy suggestion is removed from the causal explanation. 512.7 Storage and feature evaluation CASEY stores each case it solves and its solution in its case memory for use in future problem-solving. New cases are stored in the memory indexed both by the input features that describe the case and the solutions (the causal explanation, diagnosis, and therapy suggestions) that were derived for the case. This is true whether the solution was produced by CASEY or by the Heart Failure program. ‘There are three structures in CASEY that are used to store generaliza- tions: the FEATURE-GEN, the CAUSAL-GEN, and the THERAPY-GEN. In the FEATURE-GEN, cases are retrieved and stored by the features that describe them. Cases are stored in the FEATURE-GEN at the time a new case is pre- sented to the system. In the CAUSAL-GEN, cases are retrieved using their evidence-states. They are stored in the CAUSAL-GEN using their generalized causal features after the causal explanation for the case has been determined. In the THERAPY-GEN, cases are retrieved and stored according to the therapy recommended for the patient. An individual case is indexed in memory by the all features that describe it. In previous work on case-based reasoning, major effort was expended on selecting those features of the case which were to be used as indices for storing and retrieving the case. CASEY indexes a case by erery feature that describes it. This approach has two advantages: 1. One can not always determine the usefulness of a feature in advance. My scheme allows useful features to be determined by experience. For each case it solves, CASEY increases the importance weight of the features 52that were important in reaching the solution. Because random features should occur only rarely, less useful features fall into the background. 2. The indexing mechanism is very simple, because it always indexes a case by every feature, and does not have to decide which ones are significant or predictive. CASEY makes generalizations about the cases it has solved by finding sim- ilarities between the new case and cases already in its memory [17]. This is known as similarity-based generalization [27]. Generalizing the patient descrip- tions allows CASEY to make predictions about patients who share features [19] by recognizing co-occurrences. In the FEATURE-GEN, CASEY generalizes all the features in the patient description, not just the causally-related features. Some features that describe a patient are not used for analysis by the Heart Failure model, and therefore will never be considered important, Some of these features may be related to (and therefore can predict) states in the model. For example, no state in the Heart Failure model uses the information on how a murmur changes with valsalva as evidence, ulthough there is a known causal relation for why a systolic murmur associated with the disease IHSS increases upon valsalva maneuver. Normal values for findings are another example. The Heart Failure program ignores most normal findings, even though they can be used to rule out many states. By using similarity-based generalization to learn new associations between features and solutions, CASEY can aug- ment the knowledge in the Heart Failure system. At the same time, making generalizations about groups of similar patients reduces the effect of noise (ran- dom, unimportant features in the patient description) on the performance of 53the program. This is because spurious features are likely to occur randomly, whereas important features will tend to recur with some regularity in cases presented to the program [28]. CASEY also generalizes the new case by creating a description of it using only its observable states (i.e. ignoring the specific evidence for those states, and ignoring internal states with no direct evidence). These are the gener- alized causal features introduced in section 2.4. The new case is indexed in the CAUSAL-GEN by its generalized causal features, This is an improvement over simply using the input features as indices for storage because it puts the emphasis on the states in the patient’s causal explanation rather than on the specific evidence for those states. Since CASEY will accept any evidence for a state as a substitute for any other piece of evidence for that state, it makes sense to allow it to remember and match cases on the basis of classes of evidence. Separating the generalized causal features and giving them priority in matching has the effect of determining the importance of features by expe- rience. This is reasonable because the usefulness of a feature cannot always be determined in advance. This also allows the problem solver to adapt to changes in the types of problems it is presented over time. Giving extra weight to causally-related features is reasonable because causality often indicates which features are important in the case for matching (51), [43]. Re-evaluating the importance of features is of value if the types of problems presented to the program can change over time. For example, a program designed like CASEY for the domain of general medicine might reasonably be expected to form a generalization that represents a new cluster of simultaneous 54occurrence of lymphadenopathy, fever, malaise, and immunosuppression in young men (i.e. AIDS), based on its exerience, if it were presented with several such cases. 55Chapter 3 ImplementationFigure 3.1 shows a block diagram of the program. The memory structure con- tains three organizing structures for the cases, the FEATURE-GEN, the CAUSAL- GEN, and the THERAPY-GEN, described in section 2.1. The memory organizer selects the indices from the input cases, organizes the indices to reflect their relative frequencies and importance, integrates cases into the memory struc- tures, creates new generalized episodes, and modifies and refines the knowledge stored in the memory structure. The justifier produces justifications using in- formation from the Heart Failure model, as described in section 2.5, and the adapter modifies past solutions, as described in section 2.6. 3.1 Interface with the Heart Failure program CASEY is invoked via and takes its input from the Heart Failure program’s input screen. The input is translated into C/ SEY’s internal representation in order to search the case memory. If the search is not successful and the Heart Failure program must be run for the patient, the data is still available in the Heart Failure program's representation fiom the input screen. CASEY uses the Heart Failure program’s representation for causal explanations, and can display its results using the Heart Failure program’s graph-drawing utilities. CASEY also has routines that let it examine the Heart Failure model. a7MEMORY feature-gen ORGANIZER — MEMORY STRUCTURE similarity metric ADAPTER SJUSTIFIER Heart Failure Program Figure 3.1: Module diagram of CASEY 583.2 Implementation of the memory nodes 3.2.1. Generalizations GENS are data structures used to hold generalizations created by the program. Each GEN holds information about the two or more cases indexed by this GEN. The features list stores the features present in the description of at least 2/3 of the cases in this GEN.' Each element of the features list is a 3- tuple consisting of the name of the feature, the value of the feature, and the number of cases indexed in this GEN that share this feature. The diffs list holds the indices that are used to differentiate among the cases indexed in this GEN, The causal list holds a list of states that are common to the causal explanation of all the patients indexed in this GEN. Finally, the node-count records how many cases are indexed in this GEN. An example of a GEN created by CASEY is shown in Figure 3.2. This GEN organizes cases that included the feature syncope/near-syncope on exertion. CASEY saw 23 patients with this feature. The patients had other features in common, including anginal chest pain, dyspnea on exertion, and sustained apex impulse (normal values are not shown in the figure). Patients organized by this GEN all shared the causal explanation fragment listed under the heading “causal” in the figure. This generalization represents a substantial number of the cases solved by CASEY. fraction of cases that a feature in the features list represents is determined by the system designer. 59GEN 686 NODES: 23 FEATURES (cardiomegaly Wv) (apex-impulse sustained) (52 single) (characteristic-murmur as) (pulse slow-rise) (chest-pain anginal) (dyspnea on-exertion) ‘CAUSAL limited-cardiac-output —_general-flow-deficit exertional angina fixed-high-outflow-resistance slow-ejection aortic-stenosis DIFFS known diagnoses heart-rate auscultation ... Figure 3.2: A typical generalization structure (GEN)3.2.2 Cases The CASE data structure holds information about the individual cases pre- sented to the program, Each CASE holds the following information: 1 10. . A unique number that identifies this case (the node- ‘The name of the patient. . The date and time the case was entered. . The description of the patient. This is represented as a list of fea- ture/value pairs. . The causal explanation derived for this patient. This is represented as a list of nodes and links. ‘The generalized causal features for the case. (Before a causal explanation has been derived for the case, this slot holds the evidence-states for the patient. . The patient's diagnosis, . Any therapy suggestions made for this patient. ). The source of the solution for this patient (either the Heart Failure pro- gram or another case). If this patient's causal explanation was trans- ferred from another case, the precedent case and any substitutions made in adapting the precedent solution to the current case are recorded. Any follow-up information available for this patient. 61SESSION-AT: DATA: CAUSAL-EXPLANATION: [Link] age 62, sex female, dyspnea on-exertion, orthopnea absent, chest-pain anginal, anginal unstable, syncope/near-syncope none, palpitations none, cough absent, diaphoresis absent, hemoptysis absent, nausea/vomiting absent, fatigue absent, therapies none, heart-rate 86, resp 14, temp 98.3, mean-arterial-pressure 103, appearance anxious, mental-status conscious, jugular-pulse normal, pulse slow-rise, parasternal-impulse normal, auscultation murmur, murmur systolic-ejection-murmur, auscultation 62, 62 soft-a2, apex-impulse laterally-displaced, exr cardiomegaly, cardiomegaly lv, cxr calcification, mitral calcification, aortic-valve calcification, ekg sinus-rhythm, ekg lv-strain, arrhythmia-monitoring sinus-rhythm extremities normal-exam, abdomen normal-exam, chest clear-to-auscultation-and-percussion limited-cardiac-output, slow-ejection, unstable-angina general-flow-deficit, Iv-systolic-function, cardiac-dilatation, iv-systolic-function-chronic, lv-hypertrophy, Iv-press-chronic fixed-high-outflow-resistance, aortic-stenosis, anxiety, aortic-valve-disease, mitral-valve-disease, (dyspnea on-exertion), (unstable anginal chest pain), (appearance anxious), (arterial-pressure 103), (heart-rate 86), (pulse slow rise), (52 soft-a2), (ekg Iv-strain), (cardiomegaly |v), (calcification mitral), (calcification aortic-valve), (apex-impulse laterally-displaced), Figure 3.3: An example of the CASE data structure. 62GEN-CAUSALS: DIAGNOSIS: THERAPY: TRANSFERRED-FROM: OUTCOME: (present aortic-valve-disease), (present mitral-valve-disease), (present cardiac-dilatation), {pizsent !v-hypertrophy), (present fixed-high-outflow-resistance), (present slow-ejection), (present anxiety), (present unstable-angina), (present limited-cardiac-output) unstable-angina, aortic-stenosis, aortic-valve-disease, mitral-valve-disease (aortic-valve-replacement aortic-valve-diseaze) node-64 (same-qualitative-region (mean-arterial-pressure:103 ‘mean-arterial-pressure:104) rule: (high blood-pressure)) (definite-cause (calcification mitral) mitral-valve-disease) (new-state mitral-valve-disease) (definite-cause (calcification aortic-valve) aortic-valve-disease) (new-state aortic-valve-disease) (causes aortic-valve-disease aortic-stenosis) (other-evidence (pulse slow-rise) slow-ejection) (other-evidence (s2 soft-a2) fixed-high-outflow-resistance) (cther-evidence (apex-impulse laterally-dieplaced) cardiac-dilatation) (other-evidence (cardiomegaly Iv) cardiac-dilatation) (supports-existing-state (cardiomegaly Iv) lv-hypertrophy) (no-evidence high-sympathetic-stimulation) ail Figure 3.4: More of the Case data structure. 63‘An example of the CASE data structure is shown in Figures 3.3 and 3.4 The patient name, date, and time together serve to uniquely identify the session with the patient. The follow-up information? is useful for making predictions about patients similar to this one. For example, if the patient did not respond to the therapy recommended by the program, this information could be used by the physician when considering the therapy for a future patient. 3.3. Complexity of the memory scheme ‘As more cases are added to the memory, concerns might be raised about the size of the case memory and the increase in retrieval time. The memory re- trieval scheme used by CASEY never examines all the nodes in the memory. It only follows those paths specified by features in the new patient’s description. The time to follow a path in memory is proportional ts the depth of the search tree, which in turn is dependent on (at most) the number of features in the longest patient description. It is independent of the number of cases stored in the memory. A small experiment was performed to determine how retrieval time changed as the number of cases in the memory increased. Four GENs were built us- ing increasing numbers of cases. Then the time to retrieve matches for two cases was measured, one from the FEATURE-GEN and one from the CAUSAL- GEN. The results, given in Table 3.1, indicate that the time (in seconds) to thown in the example. 64Number of cases in memory 10 20 30 44 Table 3.1: Results of a timing experiment. retrieve a case from memory was indeed almost constant as the number of cases increased. The growth in size of the case memory is highly dependent on the nature of the cases stored in it. If the program were presented with one thousand iden- tical cases, the case memory would consist of exactly one GEN whose features would be the features in their description, with no diffs and thus no individual cases stored in the memory. If the memory were presented with one thousand cases that had no features in common, it would consist of a single GEN whose features list was empty, and a diffs list that held every feature in each of the cases’ description. At the end of each diff would be a single case. In ordi- nary use, the nature of the cases presented to the system will most likely fall between these two extremes. When the memory is in its early stages of use, there are many features that it has never encountered before. A new feature is entered as a diff in the top-level GEN and increases the breadth of the memory structure. Subsequent cases that have this feature in their description will create generalizations below the diff, and thus increase the depth of the memory structure. When CASEY is presented with a case whose features are identical to the features of a GEN, there is no way to distinguish the case from the GEN and thus there is no need to remember the case, since it is already completely 65described by the generalization. As more and more cases are seen by the program, GENs representing common types of problems seen by the program are formed and refined. The cases from which those GENs were derived are no longer accessible. When a case is no longer distirguishable by any feature from a generalization, it is discarded. The only cases that are explicitly stored are exceptions to these “prototypical” problem types. (Cases that are not stored because they are identical to a generalization are still used to increment the importance weights in the memory. This ensures that CASEY keeps its importance weights current.) Creating generalizations reduces the depth of the tree because a case is indexed into the memory structure beneath a GEN only by those features that are different from the features in the generalization. After the memory has seen a variety of cases, therefore, it grows more slowly, and may even compact itself. 3.4 Constructing a similarity metric ‘Two similarity metrics were implemented for CASEY, although only one is used. One used a combination of usage counts and causal importance of fea- tures, the other, presented in section 2.4.2, used generalized causal features. To implément the first metric, each index is given two slots for maintaining usage information. The first slot, usecount, is incremented each time the fea- ture is seen in a case. The second, priority, is incremented every time a feature is found to be used in a causal explanation. The ratio priority/usecount basi- cally determines the importance ordering of the indices, although it is adjusted for frequency (see below). If the ratic is low compared to that of other indices, 66it indicates that a feature is common without being causally important so its usefulness is low. This scheme allows rare but causally important features to be considered more useful than simple frequency would indicate (since they are rare, their usecount is low, so their ratio is high). The weighting scheme is somewhat more sophisticated than a simple ratio. For example, a feature whose ratio = 1 but whose usecount = 100 is considered more important than a feature whose ratio and usecount are both 1. Similarly, the system ranks a feature whose ratio = 0 and whose usecount = 100 lower than one whose ratio 0 but whose usecount is only 3. The result of this similarity metric is that important features are recognized, while spurious features are downplayed. Although I had originally intended to use the above metric, an analysis of the best match for several cases determined that generalized causal features were most important in determining the best match for a case (the metric is described in section 2.4.2). ‘This is because a decision was made to always attempt to reproduce the Heart Failure program's solution (rather than allow- ing CASEY to potentially find a better solution). Generalized causal features group features that are evidence for the same state, so using generalized casual features groups cases that have evidence for the same states. Therefore the second metric is the one that is used in the current implementation. The first metric would be more useful than the second if the Heart Failure program were allowed to be overridden. In that case, CASEY would be cal- culating new “evoking strengths” of features for diagnoses, whereas currently CASEY keeps the Heart Failure program’s probability weights. 673.5 Implementation of the justifier Before the system can attempt to justify a match between two cases, it must first identify the differences between them, and then decide which ones are significant. Identifying any differences is simple, because the memory organizer indexes the two cases by their differences in the GEN that is created when the similar case is found. CASEY can identify the following types of differences: features missing in the new case, extra features in the new case, and features that have different values. The justifier then evaluates each difference using the evidence principles. Whenever a difference is judged insignificant or a repair can be made to account for the difference, the justification for the change is recorded in a list of justifications. Some features of the new case may remain unexplained after this step. The justifier examines all the causes in the Heart Failure model for each unexplained feature. If the feature has a definite cause, or only one cause, that cause is added to the causal explanation. Otherwise, the feature remains unexplained. Next, the justifier tries to find support for states in the causal explanation that have no support, either because all the evidence for the state is missing in the new case, or because the cause of that state was removed. Again, if the state has a definite cause, or only one cause, that cause ig added to the causal explanation. The justifier also examines the causal explanation for any evidence that can be used to support the state. If no support for the state is found, it is removed from the causal explanation. Finally, the justifier checks for the two failure states. If all diagnosis states have been removed from the causal explanation, or if some feature in the new case remains unexplained, the match fails. Otherwise, the match is accepted 68and the list of justifications is returned. 3.6 Implementation of the repair strategies ‘The implementation of the explanation repair strategies is quite simple: each evidence principle generates a list containing the objects in the old causal ex- planation that must be changed or added, and a tag indicating the change that must be made to the explanation. For example, (add (anginal experiencing) unstable-angina) or (substitute mean-arterial-pressure 102 103). The repair strategies are called according to the change that must be made, and the causal explanation is incrementally medified. This process is not very expensive because all changes to the causal explanation are local to the state named in the input string. The repair strategies are independent of the partic- ular implementation of the domain model. In order to use these on a different model, only the lowest-level routines (the ones that actually add states and links to the explanation) need be changed. Diagnoses and therapy suggestions are both determined by the presence of distinguished states in the causal explanation. Thus, diagnosis and ther- apy repairs are both linked to the explanation repair strategies add-state and remove-state. As described in section 2.6.2, when a diagnosis state is added or removed, a diagnosis repair strategy modifies the diagnosis appropriately. When a treatable state is added or removed, a therapy repair strategy adds or removes a therapy suggestion . 69Chapter 4 Results4.1 A detailed example ‘A new patient, Natalie, is presented to the system. She is a 62-year- old female complaining of dyspnea on exertion and unstable anginal chest pain. She appears anxious, Her blood pressure is 146/81 and her heart rate is 86 beats per minute. Auscultation reveals soft A2 and a systolic ejection murmur. She has a laterally displaced apex impulse. Her EKG shows LV strain, and her chest x-ray shows LV cardiomegaly and mitral and aortic valve calcification. The rest of her examination is normal, The exact input presented to CASEY is shown in Figure 4.1. renewcommand11.5 As a prelude to retrieval, CASEY generalizes all features in Natalie’s description to determine the states for which there is evidence in this patient. These are Natalie’s evidence-states. Fer example, the feature “LV cardiomegaly” is evidence for the states LV HYPERTROPHY and CARDIAC DILATATION. According to the model, Natalie has evidence for 66 states. In order to find a previous case similaz to Natalie, CASEY searches the CAUSAL-GEN for cases that have the evidence-states in their causal explanation. It also searches for patients similar to Natalie in the FEATURE-GEN. This is the retrieval step. CASEY retrieves two cases that are similar to Natalie, Cal and Margaret. CASEY uses its similarity metric to rank the retieved cases. As shown in Table 4.1, all of Cal’s seven generalized causal features are covered by Natalie's evidence-states. One of Margaret's eight generalized causal feavures, “evidence of high sympathetic stimulation,” is not covered by Natalie's evidence-states. In terms of number of generalized causal features in common, these two cases rank equally. The number of total features in common is used to break the tie. Cal and Natalie n(defpatient Natalie” (age . 62) (sex female) (dyspnea on-exertion) (orthopnea absent) (chest-pain anginal) (anginal unstable) (syncope/near-syncope none) (palpitations none) (nausea/vomiting absent) (cough absent) (diaphoresis absent) (hemoptysis absent) (fatigue absent) (therapies none) (blood-pressure 146 81) (heart-rate . 86) . (arrhythmia-monitoring normal) (resp . 14) (temp . 98.3) (appearance anxious) (mental-status conscious) (Gugular-pulse normal) (pulse slow-rise) (auscultation 62 murmur) (52 soft-a2) (murmur eystolic-ejecticn-murmur) (apex-impulee laterally-displaced) (parasternal-impulse normal) (chest clear-to-auscultation-and-percussion) (abdomen normal-exam) (extremities normal-exam) (ekg lv-strain normal-sinus) (car calcification cardiomegaly) (calcification mitral aortic-valve) (cardiomegaly Iv)) Figure 4.1: Patient data for Natalie 2Generalized Causal Features Evidence States Cal Margaret Natalie ral valve disease yes aortic valve disease = yes unstable angina unstable angina yes slow ejection slow ejection yes limited cardiac output limited cardiac output —_yes LV hypertrophy LV hypertrophy yes fixed high outflow resist. fixed high outflow resist. yes, _ cardiac dilatation yes = anxiety yes high sympathetic stim. _no i total: 7/8 Table 4.1: Match analysis of Cal and Margaret for Natalie have 28 features in common, whereas Margaret and Natalie have 27 features in common. Therefore the match with Cal ranks higher than the match with Margaret, and CASEY first tries to justify the match with Cal. Cal’s causal explanation is shown in Figure 4.2. In the justification phase, CASEY determines that Cal’s explanation can be modified to account for all of Natalie's findings except for the laterally displaced apex impulse. This finding is not accounted for by any state in Cal’s explanation and it has no easily determined cause (as does Natalie’s finding of anxious appearance, which has only one cause, anxiety). The justification thus fails, and CASEY next considers Margaret as a precedent. Margaret’s causal explanation is shown in Figure 4.3. The differences be- tween patients Natalie and Margaret, which CASEY must explain by justifying the match, are shown in Table 4.2. CASEY makes the following inferences about the differences between pa- 3symcope/neat syncope on ¢ LIMITED CARDIAC OUTPUT AORTIC VALVE DISEASE __,. sot valve califation exertion | MITRAL VALVE DISEASE single 32 AORTIC STENOSIS ntl cletfeaton GENERAL FLOW DEFICIT FIXED HGH OUTFLOW ___, HIGH LV PRESS CHRONIC | RESISTANCE | UNSTABLE ANGINA SLOW EJECTION LW HYPERTROPHY mean arterial pressure: 103 unstable anginal chest pain sastaned spe impulse Ww eardlomegaly ote: strain - Figure 4.2: Causal explanation for Cal. 4dyspnea on exertion cexpeencing anion chest pa \ ANXIETY GH SYMPATHETIC. STIMULATION apheresis mean aterial preseure: 104 LUMITED CARDIAC OUTPUT singe st aortic stENosis sa acon amar Gcenenat FLow oericiT sc wa oursLow Hictay PRESS cHROKIC —_, Low wv s¥STOUIC | [RESISTANCE | FUNCTION CHRONIC UNSTABLE ANGINA stow execrion Ww uvrenrrons Low w srstoute 4 4 4 FUNCTION state anginal het pst setae pe imple eh aa ‘CARDIAC DILATATION appears amsous | Causal explanation for Margaret. 5Feature name Value for Natalie Value for Margaret ag 62 67 temperature 98.3 98.7 heart rate 86 90 blood pressure 146/81 148/unknown apex impulse laterally-displaced sustained parasternal impulse normal unknown pulse slow-rise normal 32 soft A2 single chest x-ray mitral and aortic none calcification IV cardiomegaly generalized cardiomegaly angina unstable unstable experiencing appearance anxious anxious diaphoretic Table 4.2: Differences between patients Natalie and Margaret. tients Natalie and Margaret: © No rule in the Heart Failure model uses age as evidence, so Margaret's age is judged to be insignificant by the rule unrelated oldcase feature, and Natalie's age is judged to be insignificant by the rule unrelated newcase feature, Both patients’ heart-rates are in the same qualitative region (moderately high heart rate) so the difference is considered insignificant. ¢ Both temperatures are in the “normal” qualitative region so the differ- ence is considered insignificant. Both patient's blood pressures are in the “high” qualitative region so the difference is insignificant. 76© Margaret's finding of sustained apex impulse supports the state SLOW EJECTION. Natalie does not have a sustained apex impulse, but she does have a slow rise pulse. This is other evidence for the state SLOW EJECTION. © Natalie's finding of a laterally-displaced apex-impulse supports the ex- isting state CARDIAC DILATATION. ¢ Natalie's parasternal impulse is normal and does not have to be ex- plained. Single $2 and soft A2 both support the existing state FIXED HIGH OUT- FLOW RESISTANCE. © LV cardiomegaly in Natalie is evidence for the same states that gen- eralized cardiomegaly supports in Margaret’s causal explanation. LV cardiomegaly also supports the existing state LV HYPERTROPHY, so a link must be added between the finding and the state. Mitral valve calcification and aortic valve calcification on chest x-ray are both definite evidence for the states MITRAL VALVE DISEASE and AORTIC VALVE DISEASE, so theses states are added to the causal explanaiton. @ Natalie does not have the finding “experiencing unstable angina,” but, she has other evidence, namely “unstable anginal chest pain,” to support the state UNSTABLE ANGINA, © Natalie's finding of “appears anxious” supports the existing state ANXI- ETY. There is no longer any evidence for the state HIGH SYMPATHETIC 1STIMULATION 50 it is removed. Alll the differences between Margaret and Natalie are insignificant or repairable, so the match is said to be justified. In order to adapt the explanation transferred from Margaret to fit the data for Natalie, the following repair strategies are invoked by the justifier: (substitute-evidence mean-arterial-pressure 103 104) (remove-evidence unstable-angina experiencing) (add-state (mitral-valve-disease)) (add-evidence (calcification mitral) mitral-valve-disease) (add-state (aortic-valve-disease)) (add-evidence (calcification aortic-valve) aortic-valve-disease) (add-1ink aortic-valve-d: ase aortic stenosis) (remove-evidence (apex-impulse sustained) slow-ejection) (add-evidence (pulse slow-rise) slow-ejection)) (add-evidence (s2 soft-a2) fixed-high-outflow-resistance) (remove-evidence (s2 single) fixed-high-outflow-resistance) (add-evidence (apex-impulse laterally-displaced) cardiac-dilatation) (remove-evidence (cardiomegaly generalized) cardiac-dilatation) (add-evidence (cardiomegaly lv) 1v-hypertrophy) (add-evidence (cardiomegaly lv) cardiac-dilatation) (remove-evidence diaphoresis high-sympathetic-stimulation) The changes that must be made to Margaret's causal explanation to fit the details of Natalie's description are shown in graphically in Figure 4.4. The 8Ayspnea on exertion LIMITED CARDIAC OUTPUT | ‘AORTIC STENOSIS a | ‘AORTIC VALVE DISEASE __,. sorte valve cacfeaton FE Dresser” 4 cever ow oer reo wich ourriow 2 Hiciiy PRESS cHRowc —_, Low wy svsrou Pain | RESISTANCE | FUNCTION CHRONIC awnery UNSTABLE ANGINA stow execrion Lv avPERTROPHY tow wy sysrouc 1 — FUNCTION sea eh tea [petit as low se) & tinea] cARoiAC DLATATION 2/3 of the patients with the feature had IHSS) it would use the infor- mation in the GEN for prediction. CASEY would predict that patients with a of a program. A memoized procedure maintains a ...table in which values of previous calls are stored using as keys the arguments that produced the values. When the memoized procedure is asked to compute a value, it first checks the table to see if the value is already there and, if so, just returns that value. Otherwise, it computes the value in the ordinary way and stores this in the table.” {1} 89