Authors: Joeseph Gartner, Terrance Swift, Allen Tien
Medical information systems have become an active area of software development in the United States, with a market of over 10 billion dollars per year. Typically, these systems have as their goals either to cut the costs of medical treatment or to ensure that treatments are performed in a standard, well-documented manner. Traditional medical information systems address well- known problems such billing or shift-scheduling; or problems related to work ow management such as simple monitoring of treatment plans. However, important areas of medical practice, such as patient assessment (diagnosis) have not often been addressed by medical information systems, partly because the process of medical reasoning is dificult to automate. The purpose of the Diagnostica system developed by Medicine Rules, Inc (Stony Brook, NY) is twofold. As a research system, it explores how the process of psychiatric assessment can be represented by extensions of classical logic. More importantly, as a commercially available product Diagnostica seeks to aid psychiatrists, psychologists and psychiatric social workers in diagnosing patients in an eficient and systematic manner.
Beyond economic considerations, accurate diagnoses are critical to public health, but can be dificult to make. For instance a confused, elderly patient could suffer either from a Major Depressive Disorder or from Alzheimer's Dementia. In the former case, the patient may be treatable with medication; in the latter case the patient is not. Similarly, itmay be dificult to determine whether a child has Attention Deficit Disorder (treated by medication) or an Adjustment Disorder (treated by therapy). Diagnostic procedures about psychiatric disorders have been codified by the American Psychiatric Association in the fourth edition of its reference book Diagnostic and Statistical Manual of Mental Disorders, or DSM-IV , which is widely used in the United States. These procedures specify various criteria that a patient must satisfy in order to meet a diagnosis for a mental disorder. As an example, one of the criteria for Asperger's Disorder, a Childhood Pervasive Development Disorder, is shown in Figure 1. This criterion re ects the polythetic nature of psychiatric diagnoses. There need be no essential characteristic or criterion of a diagnosis. For instance, the failure to develop peer relationships can, under different circumstances, indicate schizophrenia, autism, and many other disorders. Instead, multiple prototypes with varying features are used to group together a wide range of disparate phenomena by analogy. The need to represent multiple prototypes leads to criteria like that in Figure 1, but also to occasional dificulty and even ambiguity in distinguishing between the 618 DSM-IV diagnoses, as in the cases mentioned above. Because of these complications, while most American psychiatrists use DSM-IV, few use it to its full advantage. Studies have shown that clinical psychiatrists err in using DSM-IV by not considering all possible diagnoses, while research psychiatrists err by not excluding diagnoses quickly enough.
impairment in social interaction, as manifested by at least two of the following
1. marked impairment in the use of multiple nonverbal behaviors such as eye-to-eye gaze, facial expression, body postures, and gestures to regulate social interaction;
2. failure to develop peer relationships appropriate to developmental level
3. a lack of spontaneous seeking to share enjoyment, interest,m or achievements with other people (e.g. by a lack of showing, bringing, o r pointing out objects of interest to other people).
4. lack of social or emotional reciprocity
As indicated by the above criterion, DSM-IV diagnostic rules have a clear formulation that lends itself to formulation as a logic program, thus a patient meets criteria for a diagnosis if the body of the diagnosis, expressed as a logical rule, is satisfied. However, DSM-IV makes certain demands on knowledge representation formats that cannot easily be programmed in Prolog. We discuss the demands made by DSM-IV, then discuss how DSM-IV can be represented as a logic program, and finally how the resulting logic program can be implemented using the XSB system and is incorporated into Diagnostica.
The Nature of Knowledge in DSM-IV From the perspective of knowledge representation, several factors distinguish the process of psychiatric assessment.
1. Under-specification: DSM-IV sometimes does not provide a means to distinguish between two closely related diagnoses, but occasionally leaves the final diagnosis up to the judgment ofa physician. DSM-IV's method for doing this is through mutually-dependent exclusion rules, as can be seen from a criterion for Asperger's Disorder is:
Other Pervasive Development Disorders, such as Autism or Childhood Development Disorder contain similar exclusion rules, so that choosing among the three disorders may be indeter- minate according to a strict interpretation of the DSM-IV rules | each diagnosis is true if and only if the others are false. This under-specification re ects not only the practical clinical problem of distinguishing Asperger's Disorder from, say, Autism, but also the fact that researchers continue to debate the validity of Asperger's Disorder as a distinct diagnosis altogether (see e.g. [5, 8]).
2. Incomplete Knowledge: If there are no indications that a patient has an uncommon symptom or case history, certain criteria may be ruled out by default. For instance, the diagnosis of Dissociative Fugue disorder depends on determining that the patient has no medical condition that could also account for the observed symptoms, a determination that may be dificult, if not impossible, to make with absolute certainty. Similarly, many diagnoses depend on a history of the patient that may be impossible to obtain, or may be unreliable from patients or their signifcant others. For instance,
In these cases, the diagnosis made need to be made on less than perfect information, and there is a need to distinguish information that is assumed false because there is no evidence to support it from information that is explicitly known to be false.
3. Hypothetical Reasoning: Diagnoses sometimes rely on hypothetical reasoning by the physician. An instance of this is Adjustment Disorder, which has the criterion
Once the stressor (or its consequences) has terminated, the symptoms to not persist for more than an additional 6 months.
Taken literally, this criterion implies that a physician cannot diagnose a patient as undergoing Adjustment Disorder, while the patient is undergoing it.
4. Temporal Reasoning DSM-IV often requires very sophisticated temporal reasoning to repre- sent the duration and occurrence of various symptoms. Criteria often have temporal condi- tions such as ... the disturbance does not occur exclusively during the course of a delirium. Furthermore, temporal reasoning also may be used to determine whether a patient is di- agnosed with single or multiple disorders. For instance, if a patient is both depressed and anxious, he will be treated for anxiety only if the symptoms of an anxiety disorder preceded those of the depression - otherwise the anxiety is taken to be a symptom of the depression itself.
Representing DSM-IV as a Logic Program The first three of these factors have been ad- dressed, while an adequate logic programming representation for time in DSM-IV is still to be determined. We discuss these factors in turn.
1.Under Specification As a first pass the exclusion rules of DSM-IV are represented using default negation. Thus the exclusion rule mentioned above, can be represented schematically in Prolog pseudo-syntax as:
'Aspergers Disorder':- (various conditions), not pervasive development disorder.
If a patient satisfies all non-exclusion criteria for two diagnoses that are mutually exclusive in DSM-IV, the corresponding logic program becomes non-stratified. The current approach for DSM-IV is to evaluate mutually exclusive diagnostic rules under the Well-Founded Semantics . Thus, if a patient fulfills all (non exclusion) criteria for a set of mutually exclusive diagnoses, the physician will be told that the actual diagnosis is unknown, but will be given the set of (partially satisfied) mutually exclusive diagnoses.
2. Incomplete Information It is well-known from knowledge representation literature that infor- mation that is assumed false because there is no evidence to support it can be represented by default negation; while information that is explicitly known to be false can be represented by explicit negation. Explicit negation can be added to the well-founded semantics with- out increasing its computational complexity under the well-founded semantics with explicit negation (see e.g. ).
3. Speculative Information More speculative information, such as that needed to conclude an Adjustment Disorder can be represented using abduction. In these cases the beliefs that the physician makes are recorded explicitly as an abductive context upon which the diagnoses depends.
Implementing DSM-IV in the Diagnostica System From the preceding considerations about knowledge representation in DSM-IV, it is clear that DSM-IV requires the ability not only to evaluate non-stratified programs over the well-founded semantics with explicit negation, but the ability toperform abduction over such programs. Fortunately, recent work in logic programming addresses how toevaluate such programs. The XSB System  eficiently evaluates the well-founded semantics at an engine level; using a program transformation, explicit negation can be evaluated with a well-founded engine as discussed in ; finally abduction over well-founded programs with ex- plicit and default negation can be performed minor modifications to XSB using the Abdual method . Indeed, development of the Abdual method was spurred partly by the need for well-founded abduction to model DSM-IV.
Figure 2: Using Diagnostica for Attention Deficit Disorder
Figure 2 shows part of the user interface of Diagnostica 1.0 (see http://www.medicinerules.com for more on Diagnostica). A physician can mark a crite- rion as true or explicitly false in the middle box on the right (criteria that are not marked are treated as default false). As these symptoms are entered, various diagnoses become true, potentially true, or precluded in the box on top right. At the same time, the tree-like structure of DSM-IV is represented in the left box. In other screens of Diagnostica 1.0, abduction is used to allow physicians to perform hypothetical reasoning. Given a state of knowledge about a patient, the physician can ask what criteria are needed to make a particular diagnosis about a patient. This hypothetical reasoning also allows a physician to determine criteria that may differentiate between two similar diagnoses. Diagnostica 1.0, does not perform abduction through the negative exclusion rules, and thus does not perform abduction over the entire well-founded semantics. However, it is the intention that future versions of Diagnostica will have this capability, based on the evaluation methods mentioned above.
Summary Non-stratified programs are sometimes considered to be of little use for practical problems. However, translation of DSM-IV diagnostic rules into logical rules shows that sets of closely related diagnoses may form non-stratified recursive components. As mentioned above, if a patient satisfies all non-exclusive criteria for more than one diagnoses, so that these diagnoses are undefined under the well-founded semantics, no determination is made of which diagnosis is correct. Alternate approaches could, of course, be taken. One particularly promising approach under current investigation is to recode the exclusion rules to allow the physician to add optional preferences when non-exclusion criteria are met for a set of potentially mutually exclusive diagnoses. Using these preference rules a physician may prefer one diagnosis over another (e.g. preferring Autism to Asperger's Disorder) or even disable the mutual exclusion to allowmultiple diagnoses (e.g. allowing
1. The need not only to model these aspects of DSM-IV, but to use them in a commercial product has helped spur the development ofthe Abdual evaluation method which is just beginning to be fully integrated with Diagnostica; further work in adding user-defined preferences and temporal reasoning in Diagnostica should lead to the practical validation of further knowledge representation techniques and perhaps also to advances in implementation techniques for non-monotonic reasoning.
 J. Alferes, C. Damfiasio, and L. M. Pereira. A logic programming system
for non-monotonic reasoning. Journal of Automated Reasoning, 14(1):93-147, 1995.
 J. Alferes, L. M. Pereira, and T. Swift. Well-founded abduction via tabling dual programs. In International Conference on Logic Programming, 1999. To Appear.
This current work is undertaken with Carlos Viegas Damfiasio and Luis Moniz Pereira
 Diagnostic and Statistical Manual of Mental Disorders. American Psychiatric Association, Washington,DC, 4th edition, 1994. Prepared by the Task Force on DSM-IV and other commit- tees and work groups of the American Psychiatric Association.
 J. Freire, P. Rao, K. Sagonas, T. Swift, and D. S. Warren. XSB: A system for eficiently computing the well-founded semantics. In International Conference on Logic Programming and Non-Monotonic Reasoning, pages 430-440. Springer-Verlag, 1997.
 M. Prior, R. Eisenmajer, S. Leekam, L. Wing, J. Gould, B. Ong, and D. Dowe. Are there subgroups within the autistic spectrum? a cluster analysis of a group of children with autistic spectrum disorders. Can J Psychiatry, 43(6):589-595, August 1998.
 T. Swift. Tabling for non-monotonic programming. Annals of Mathematics and Artificial Intelligence, 25(3-4), 1999.
 A. van Gelder, K. Ross, and J. Schlipf. Unfounded sets and well-founded semantics for general logic programs. JACM, 38(3):620-650, 1991.
 F. Volkmar, A. Klin, and D. Pauls. Nosological and genetic aspects of asperger syndrome. J Child Psychol Psychiatry, 39(6):893-902, September 1998.
Joeseph Gartner, Medicine Rules Inc, 25 East Loop Rd, Stony Broon, NY 11794
Terrance Swift, Department of Computer Science, SUNY at Stony Brook, Stony Brook, NY
Allen Tien, Medical Decision Logic Inc 7921 Ruxway Rd, Baltimore MD 21204-3515