 |
This paper appeared in the Proceedings of the 1992 Conference of the Cognitive Science Society.
Roy M. Turner
Department of Computer Science
University of New Hampshire
Durham, NH 03824
rmt@unh.edu
Diagnostic reasoning underlies many intelligent activities, including (but not limited to) situation assessment/context recognition, natural language understanding, scene recognition, interpretation of scientific observations, and, of course, medical diagnosis and other forms of fault-finding. In this paper, we present a memory-directed, schema-based approach to diagnostic reasoning. Features of the problem are used to ``evoke'' one or more possible diagnoses, stored as schemas. Schemas contain information about their ``manifestations'' that be used to confirm or deny the diagnosis and, in some applications, information that can be used to take action based on the diagnosis. Potential advantages of the approach include cognitive plausibility, rule exception handling via (generalized) case-based reasoning, applicability to multiple domains, extensibility from experience, and a natural way to organize knowledge about what to do after a diagnosis is made.
Diagnosis is central to much of intelligence. We can view all of the following as instances of the process of diagnosing features present in a reasoner's input: assessing its current situation (context recognition); understanding natural language; interpreting scientific observations by determining which theories they fit; and, of course, diagnosing medical problems and other kinds of faults.
We are interested in developing a computer-based model of diagnostic reasoning that supports our work in situation assessment and context-sensitive reactive reasoning in the autonomous underwater vehicle (AUV) domain, as part of the Orca project [Turner & Stevenson, 1991]. Such an approach would take features of the current problem-solving environment as input (derived ultimately from sensors or from information from other agents) and produce as output an assessment of the current problem-solving situation. This assessment would then provide the reasoner with the information necessary to assure that its behavior is appropriate for the context.
To be useful in a variety of real-world applications, a computer-based approach to diagnostic reasoning should have several properties. It should be general, that is, not tailored to one particular domain such as medical diagnosis. It should facilitate knowledge acquisition, both initially and throughout the problem solver's lifetime. This includes facilitating learning from the reasoner's own experience. Since complete knowledge is impossible to obtain in almost any domain, the reasoner should be able not only to handle usual situations, but also exceptions that follow no known rules. Finally, we should keep in mind that diagnostic reasoning is often only a means to an end. Consequently, a diagnostic reasoner should facilitate additional reasoning based on its diagnoses, for example, by allowing treatment information (for medical systems) or context-specific actions (for, e.g., reactive planners) to be associated with its representation of the diagnosis (a disease or context).
We are developing an approach to diagnostic reasoning that is based on the view of diagnosis as a memory-directed task; consequently, our approach is called MD, for Memory-based Diagnosis. This does not mean that memory is the sole mechanism underlying diagnosis in our approach; indeed, we have argued elsewhere (Turner, 1989a; 1989b) for a view of diagnosis as a planning task. Instead, we view the overall process as being guided by the organization of knowledge in the reasoner's memory.
It should be stressed that this is not completed work; rather, we build on some early work done in the domain of medical diagnosis during the medic project (Turner, 1989a; 1989b; 1989c), and current work is ongoing in the area of situation assessment and context-specific reactive reasoning for AUVs. We believe that this approach shows promise not only for our domain but for diagnostic reasoning in general.
Diagnosis is fundamentally an abductive reasoning task [Reggia et al., 1985]: from a set of features of a problem or situation (``symptoms''), hypothesize a cause (``diagnosis'') based on knowledge linking causes to effects and effects to likely causes. The kind of reasoning done by diagnosticians (e.g., physicians) to implement this abductive inference is hypotheticodeductive reasoning: hypothesize a diagnosis, then test predictions made should that hypothesis be true.
Though most researchers agree on this much, differences of opinion arise with respect to a reasonable computational model of diagnosis. The prevalent model is backward chaining rule-based reasoning [Buchanan & Shortliffe, 1984]. Chandrasekaran mdx describe diagnosis as classification: the process of assigning a problem to a particular location in a taxonomy of problems. Reggia and colleagues reggia85a, in perhaps the most formal treatment, view diagnosis as abduction, in particular parsimonious set covering. As mentioned above, the author has elsewhere argued for a view of the act of diagnosis as a planning task, view that attempts to tease out how diagnosis is done rather than what it is . The mechanism described in this paper is one part of the latter approach.
Most successful approaches to diagnosis have been rule-based, for example mycin [Buchanan & Shortliffe, 1984] and its descendants. Such systems, however, seem to miss an essential flavor of the hypotheticodeductive reasoning style as seen in humans, in which the reasoner is essentially ``reminded'' of possible diagnoses based on features in the problem.2 Humans seem to be able to relate symptoms to diagnoses with relatively little cognitive effort, and with an accuracy that increases with the human's experience. This characteristic would be highly desirable in a computer-based diagnostic reasoner as well. To capture this aspect of diagnostic reasoning in a computer model would seem to require a memory of diagnoses, linked together (organized) to facilitate retrieval of diagnoses at appropriate times.
One system that begins to address this is internist-1/caduceus [Miller et al., 1982,Pople, Jr., 1982] (hereafter referred to as INTERNIST), a diagnostic reasoner in the domain of internal medicine. This system directly approaches diagnosis as an abductive task. Symptoms are stored with information about what diseases they evoke--that is, that they should bring to mind for an expert diagnostician. Unfortunately, INTERNIST's knowledge is relatively unstructured and the program has no facility to restructure its knowledge based on experience, nor does it provide a means of easily associating additional knowledge (e.g., treatments) with diagnoses. Another system, mdx [Chandrasekaran et al., 1979] organizes diagnoses in a hierarchy that is traversed (by using rules) to find more specific diseases. However, the links between diseases in mdx's memory are static, and contain little or no information to help focus the reasoner's attention on one disease over another. Two other systems, casey [Koton, 1988] and medic (Turner, 1989a; 1989b; 1989c), respectively a case-based reasoner (e.g., [Kolodner et al., 1985]) and a schema-based reasoner (a generalization of a case-based reasoner), are more similar to the approach presented here. The kind of memory used by these programs allows a degree of interconnectedness not present in mdx, while at the same time providing mechanisms to allow updating from experience. However, though both of these systems use a content-addressable, flexible memory, they both also rely solely on mechanisms external to the memory to decide the appropriateness of evoked diagnoses.
What is desirable is an approach that can use the flexible, content-addressable memory style of casey or medic, augmented with information such as INTERNIST has to provide a measure of likelihood of the diagnoses the reasoner is reminded of by the memory. Such a scheme would provide the reasoner with a metric, potentially updatable from experience, to allow it to effectively direct the diagnostic process.
Memory-based Diagnosis (MD) is based on using a content-addressable memory of schemas representing diagnoses to perform the hypothesis generation phase of hypotheticodeductive reasoning. The memory structures are organized to facilitate retrieval based on cues in the diagnostic problem, and they contain information useful in the context of the diagnoses they represent.
Before proceeding to describe the MD approach, a brief word on terminology is in order. Our terminology is a melange of terms borrowed from INTERNIST, the memory and case-based reasoning literature, and psychological research on the process of diagnosis. ``Symptom'' and ``manifestation'' will be used synonymously to mean a feature of a given situation. A ``diagnosis'' is a conclusion of a fault or disease causing the problem or a characterization of the current situation. A symptom's ``evoking strength'' [Miller et al., 1982] for a diagnosis is a measure of how strongly its presence indicates the presence of that diagnosis. A diagnosis' ``manifestation strength'' for a symptom is a measure of how strongly the symptom is expected, given the diagnosis. The two terms ``diagnostic task'' [Miller et al., 1982] and ``logical competitor set'' (LCS) [Feltovich et al., 1984] are used synonymously to mean a set of diseases that are in competition to explain the same subset of manifestations; a reasoner seeks to ``solve'' an LCS by finding the best diagnosis from among its members.
In the MD approach, information about known diagnoses are represented as schematic memory structures. Elsewhere, we have referred to similar memory structures as contextual schemas (c-schemas) (Turner, 1989a; 1989b); we will continue to use that terminology here, though the reader should be aware that we are extending our prior definition of c-schema slightly to accommodate diagnoses such as diseases. Figure 1 shows two example c-schemas.
|
Note that c-schemas contain additional information apart from the manifestation list (list of those manifestations that are expected). The actual contents vary depending on domain, but, in general, c-schemas can contain any information useful in the context of the diagnosis. In the case of a disease, this might be treatment information. In the case of situation assessment for an autonomous vehicle, this might include context-specific ways to handle unanticipated events, to order goals, to set parameters, or to select action, as discussed elsewhere (Turner, 1989c; 1990). The point is that by making the diagnosis, the information needed to deal with the diagnosis is immediately at hand.
The overall MD process can be described as follows:
C-schemas are organized in a memory to facilitate their retrieval as well as their modification from future experience. The memory used in medic is modeled after the cyrus memory program [Kolodner, 1984], which is essentially a set of highly-interconnected discrimination nets. Such memories have been used with good results in case-based reasoners (CBR) and a schema-based reasoner (medic) to find needed cases and schemas based on features of the current problem-solving environment. They are often referred to as ``MOP memories'', since the primary memory structures are memory organization packets (MOPs). MOPs are schemas that encode information about a class of episodes (in cyrus); their primary function, as their name suggests, is to organize more specialized MOPs, which organize more specialized ones, etc., until the level of individual episodes (``cases'', in the CBR literature) is reached. C-schemas are a kind of MOP; consequently, they serve as organizing points in the memory, with more general c-schemas indexing ones that are more specialized. We use the term ``case'' for the individual episodes in memory: cases of diseases that have been seen, situations that have been encountered, and so forth.
We should point out that our approach does not exclude case-based reasoning--far from it. MD, which is a kind of schema-based reasoning, can be validly viewed as generalized CBR: that is, CBR that uses generalized cases instead of or in addition to ``real'' cases of problem solving. We have argued elsewhere [Turner, 1989a] for the utility of this view.
C-schemas are linked together by indices, each of which is a feature type/value pair. The feature types present in a c-schema's indices correspond to types of features expected to be present in the diagnosis represented by the c-schema. For example, a medical reasoner's c-schemas might contain such feature types as: symptoms, patient characteristics, medical history, etc. The ``value'' half of an index is an indication of how the indexed c-schema differs from its parent. For example, a c-schema representing ``lung disease'' will index one representing ``sarcoid'', a common lung problem in inner-city hospitals in some regions of the country. Some feature type/value pairs we might expect as indices from ``lung disease'' to ``sarcoid'' would be: ``patient home/Atlanta'', ``patient race/black'', etc. Values are chosen that are different from values of the corresponding feature type in the parent c-schema; these are considered predictive differences by Kolodner; we can also think of them as evocative differences, since their presence evokes the indexed c-schema--that is, it ``brings to mind'' the diagnosis it contains. Figure 2 shows a portion of a hypothetical c-schema memory.
Traversal of a MOP memory entails first comparing features of the current problem to the features predicted by some subset of its top-level memory structures, then selecting potential indices based on salient (evocative) differences.4 These potential indices are then compared to the c-schema's actual indices to produce a set of one or more c-schemas. Traversal continues in this manner using these structures until no further c-schemas are found. The c-schemas (and/or possibly episodes) found are, in our approach, the set of most specific possible diagnoses for the problem.
One difference in the MD approach from typical MOP memory applications is that we are interested in how strongly the current situation evokes a given diagnosis: this provides one measure of how well the diagnosis fits the problem, in the same manner as in INTERNIST. To provide for this, we augment the indices of c-schemas with an evoking strength, a measure of how strongly the reasoner should be reminded of a c-schema, given its parent c-schema and the current situation. An important property of MOP memories is that they can be updated from experience, and, as new episodes are added, the memory reorganizes its indices appropriately as well as updates the generalized information in its MOPs. In our scheme, the evoking strengths would also be updated when new information is added. This would theoretically allow the reasoner's ``remindings'' of possible diagnoses to become more accurate as it gains experience.
Of course, how strongly a diagnosis is evoked by a particular set of features in the problem description is not solely a function of the indices from the c-schema's parent. The strength with which the parent is evoked is also important. In addition, a c-schema can be reached through possibly many paths in a MOP memory, including multiple indices from the same parent; these different paths should contribute to the overall assessment of evoking strength. While we have not yet worked out the details of the combination function for evoking strengths, we can offer some initial observations. First, a c-schema should pass evoking strength to its children in proportion to how strongly it is evoked, yet we would not want simple multiplication of probability-like numbers, since this would result in a progressive decrease in evoking strength the deeper memory is traversed--the counter-intuitive situation of c-schemas that are better and better matches being less and less evoked! Second, when a c-schema is indexed more than once by a c-schema, or by more than one c-schema, its evoking strength should be a function of the evoking strengths of all the ways it is indexed, since these represent potentially different ways the c-schema matches the current situation. However, care will have to be taken to ensure that, as can happen in a MOP memory, the c-schema is not reached by two or more paths that are essentially the same, just permutations on the order in which features were examined.
The traversal process just described can determine a set of c-schemas comprising the potential diagnoses in one of at least two ways. As described above, memory traversal will create a set of all c-schemas encountered that the traversal process was not able to find children of, given the current problem features. The obvious drawback of this scheme is that the size of the set may grow quite large, and it may contain c-schemas that have very little to do with the actual problem (i.e., they were found solely due to slight resemblances). This means that the reasoner will have more hypotheses to select from, but will have to do more work to determine which hypothesis or small set of hypotheses is actually the correct diagnosis. A second approach would be to use information during memory traversal to narrow the search for hypotheses. The evoking strengths could be used during memory search to prune the search, in the manner of either beam search or a best-first search method. In this case, when considering memory traversal from some c-schema in memory, only the best n children might be considered next, where ``best'' is determined by evoking strength. With appropriate care, the memory could return either a single likely diagnosis or a set of likely diagnoses for the reasoner to consider.
These methods of finding a set of potential diagnoses are not mutually exclusive. It may be that different techniques are appropriate in different situations. For example, when in a hurry, the latter technique may be used, potentially sacrificing completeness for speed. In addition, it may be that if a reasoner is able to learn from its experiences, it can change the mechanism it uses. When a novice, a reasoner may painstakingly elucidate all possible diagnoses and carefully examine each one. With more experience, the reasoner's memory may become well-tuned, both in terms of its organization and the accuracy of its evoking strengths. In this case, the reasoner may use the latter strategy and immediately ``home in'' on the best diagnosis.
One exciting extension of the idea of representing diagnoses as c-schemas is the possibility of using a c-schema to represent a group of diagnoses that often occur together or that are often considered as a group during diagnosis. The former case should drastically improve the reasoner's ability to quickly diagnose a situation in which several different diagnoses are present, especially since the presence of one diagnosis often masks the presence of another (see, e.g., Sticklen sticklen:thesis). The latter case essentially means storing logical competitor sets as c-schemas; since LCS formation can be difficult, this, too, can improve the reasoner's performance, as suggested by Feltovich feltovich84.
In this paper, we have briefly sketched memory-based diagnosis, an approach for using a dynamic conceptual memory to aid the process of diagnostic reasoning. There are several potential benefits of memory-based diagnosis. MD allows a reasoner to be ``reminded'' of appropriate diagnoses based on features in the problem being solved in such a way that the reasoner has an initial estimate of the accuracy of the diagnoses. Since the memory is of a type that can reorganize with experience, there is the possibility that as the reasoner gains experience, its memory will return better hypotheses more quickly. MD also allows the reasoner to store frequently-occurring logical competitor sets and clusters of diagnoses, both of which can improve diagnostic ability. Since additional information can reside in the memory structures, retrieving a diagnosis automatically retrieves knowledge about how to act on the diagnosis (e.g., treatment for a disease, appropriate behavior for a kind of situation, etc.). As the memory organizes diagnoses hierarchically and allows case-based reasoning, situations which do not follow usual rules can be stored and retrieved easily. And, finally, to the extent that the underlying memory is cognitively plausible (e.g., [Kolodner, 1984]), so is MD; indeed, there is some psychological evidence supporting the schematic representation of context [Chi et al., 1982] and LCSs [Feltovich et al., 1984] in expert problem solvers.
As we have said, this work is just beginning. Earlier work in the medic project was encouraging, and we are currently investigating the approach in the domain of AUV control as part of the Orca project. We believe that memory-based diagnosis is a promising approach to diagnostic reasoning, a kind of reasoning that underlies much behavior we consider intelligent.
This document was generated using the LaTeX2HTML translator Version 98.1p1 release (March 2nd, 1998)
Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -split 0 tr.tex.
The translation was initiated by Roy M. Turner on 2000-04-18
