A Domain-Independent Production-Rule System for Consultation Programs

Introduction

1 he focus of mucn current work in artificial Intelligence is the development of computer programs that aid scientists with complex reasonin9 tasks. Recent work has s11q9ested that one key to the creation of intelligent systems Is the Incorporation of lar~1e amounts of task­ specific knowledge. Howrwer, building such "knowledge­ based" prowoms from scratch con be a very time­ consumlnq task. We hove found that the bosic framework of the MYCIN prowom [D) could bo generalized sufficiently to mnke possible the substitution of knowledge bases from other domains. Tho result of l11is generalization is EMYCIN', a system for dovelopinq rule-based consultation programs. Tho aim of this work Is to make knowledqe-bosed systems technolo~IY more accessible to investigators in many fields .

2 Description of EMYCIN

EMYCIN Is used to construct o consultation program, by which we mean a prowam which offers its user advice on some problem within Its domain of expertise, much as a IHtmnn consultant does. 1 he program elicits Information relevant to the case by nsking tho user ques tions during lito co11rse of the consultation. The prowam then applies its knowledge to tho facts of the case and Informs the tlsor of Its conclusions. Tho user Is free to ask the program questions about Its rcasonin9 In order to better understand or validate the advice given.

2.1 Knowledge Organization

Knowledue In EMYCIN is represented In terms of production rules operatino on associative (attrlbute­ ob joel -value) triples . To represent the uncertainty of dot11 or competlnn hypotheses, attached to each triple Is a certainly fclclor (Cf'), a number between -1 and 1 ln<ilco tlnn tho stren~1th of the belief In thilt fact [8].

lle11sonlng Is performed usin9 domain knowledge encoded 11s prod11cllon rules. Each rul e has a premise, which is a conjunction of predicates over triples in the knowledne base. If the premise is true, the conc lusion in tho acl/on port of the rule Is drown. If the premise Is known with less than certainty, tho strength of the conclusion Is modified accordingly (see [8)). Flnuro 1 shows a typical rule from the domain of structural analysis (described In Section 3) .

· "Essential MYCIN", I.e. MYCIN stripped of its domain knowle<ino . This work was supported in port by the NSF wont MCS 7 7-02712 ond tho Advanced Research Projec ts 1\gency, contract MDI\ 003-77-C-0322.

Rule 68

• If: 1) The material composing the sub-structure is one of the metals,
• The analysis error (in percent) that 1s tolerable 1s less than 5,
• The non-dimensional stress of the sub­ structure is greater than .5, and
• The number of cycles the loading is to be
• applied is greater than 19000

Then: It is definite (1.9) that fatigue is one of the stress behaviour phenomena in the sub-structure

PREMISE: ($A NO

(SAME CNTXT COMPOSITION (LISTOF METALS))

(LESSP* (VALl CNlKT FRROR) 5)

(�R~ATERP* (VALl CNlKl NO-SlRESS) .5 )

(GREATERP· (VALl CN IKT CYCLES) 10000))

ACTION: (CONCLUDE CNTXl SS-STRESS FATIGUl TALLY 1.0)

Figure 1

En~1lish and Internal Lisp forms of a SACON rule .

2 .2 Application of Rules -- the Rule Interpreter

Tlw control structure is a goal-direct ed bockwurd­ c hainln ~l of rules. 1\t any given time, EMYCIN is workin[l toward establishing the value of some attribute. To this end, the system retrieves thn (precotllpUt ed) list of rul es whose conclusions bear on this [IOal. Tile rul e in finure 1, for example, would be retri eved in the attempt to determine the stress of a substructure. If, in the course of evaluatinq tho premise of one of these rul es, some other piece of information is necclod which Is not yet known, EMYCIN sets up a subgool to find out tlwt information; this In turn causes other rules to be tried. Questions or0 nskecl clurinn the consultation when the ru les filii to deduce the necessary Information. If the user cannot supply the requested Information, It remains unknown, and rules that require It will simply fail. Thus, the rules unwind to produce a succession of goofs and It Is the attempt to achieve each goal thot drives the consultation (EMYCIN also permits a limited use of antecedent rules, triggered when the program receives new data or makes a conclusion).

2.3 Usefulness of the rule representation

fls has been described in earlier reports of the MYCIN prow om [ 4 ], many of the system's Important features are fncllitnted by the use of rules as the primary representation of knowled(re . Since each rule is intended to be a sln(Jie "chunk" of Information, the knowledge base is inherently modular, making it relatively easy to update. lndivlcluol rules can be added, deleted or modified without clrnsticnlly affecting the overall performance of the system. The rules ore o convenient unit for explanation purpos f's. 1 he system's nbility to "rend" its own rules Is used f'XIenslvely by the explanation program (below) and other routines which assist the user in manipulating the rule bose.

2.4 Explanation Capability

EMYCIN's expl,1nalion program allows the user to lnterrooote the system's knowledge, either to find out about inferences made In the particular case at hand or to examine the static knowledge base in general. During the consultation, in response to certain user commands, EMYCIN can offer explanations of the current, past and likely future lines of reosonin\1 (WHY a question was asked, or HOW o conclusion is reached). A more general form of explnnntion Is ovallobln via the Q/1 Module, which Is nutomnticoily invoked after the consultation has ended, ond con also be entered during the consultation to answer quos lions outside the scope of the special WHY /HOW commands . The QA Module accepts simple English­ lnnqunqe questions dealing with any conclusion drawn durin(~ tho consultation, or about the domain in general. Tho questions oro parsed by pattern matching and kr!yword lookup, usinq o dictionnry which is outomaticolly cunslruclnd from tho phr11ses used In defining the vnrious objects nnd attributes of the domain. The Qfl module has hf!nn d<':><.:ribed in we at de toil elsewhere [ 7].

"lho explonolion program Is also o helpful hi(lh-ievel debuquin(l old for the system developer. Without having to resort to Lisp-level manipulations, she con examine any inferences that were made, find out why others failed, and thereby correct errors or omissions In the knowled(le base.

2.5 Knowledge Acquisition

fl suhstonlial port of the Initial effort Involved In croolln~r an EMYCIN system Is spent In the acquisition phose, viz. constructing tho knowledge base of the rules ond the object-attribute structures upon which they operate. Thus we hove devoted much effort to providing proornmmotlc assistance for this task.

EMYCIN supplies o hloh-ievel clatabase editor for the doto structures in the system. The data must be entered In Its Lisp format (understanding English rules Is far too difficult, espociolly In o new domain where the vocabulary ha:m' t even boon Identified and organized for the prowam's usc). but the editor handles all the bookkeeping involvod In munoglng the rule bose and performs various clwr.ks to colch o number of common user errors .

To portiolly brid(te the (lOP between precise Lisp Input ond !reo-form En(JIIsh text, there is on intermediate "terse" rule format. This format is o simplified fllqol - like language which uses the attributes ond their val;tes as operands; the operators correspond to EMYCIN predicates. E.g. SACON's Rule 68 shown in Figure 1 above could be written Instead as:

If Composit1on : (LISTOF METALS) and Error < 5 and Nd-stress > .5 and Cycles > 19990 Then Ss-stress = fatigue

Figure 2 . Stylized English format for rule input .

The terse rule format Is also avniioble on output , f or users who prefer It to the more verbose En[tlish translations.

fls each rule is entered, It is checked for synt11 c ti c vnlidity, to cntch spelling errors and other simple errors. Other dolo structures ore al :;o updated, such as the one tellln(J the rule Interpreter which rules conclude about which attributes.

2.6 Other support features

EMYCIN has facilities for maintaining o library of sample cases. These can be used for testing a complete syst em or for debug(rin(t o growing one . When a library consultation is rerun, the system's questions are answered by supplyin(J the response, if any, (;iven when the case wos first run . Mony such cases moy be oulomolicolly rerun In background mode, with the system comparing the "results" with those of earlier runs . Tills makes II cosy to check the performance of a new set of rules on "standard" cases .

EMYCIN's existin(J human-enuineering features relieve the system builder of many of tile tedious cosmeti c concerns of producin9 a humon-useoble prowom. Most of these center around the consuilntion Interaction where the system requests data from the user; they Include a terminal Input facility with such f eatures as spelling correction ond Tonox-styie completion on oilmode from o list of possible answers, ond o simple help facility.

3 Applications

Several consultation systems hove been written In EMYCIN. The MYCIN program (which could be vi ewed as the ori(Jinal implementation of EMYCIN) provides advice on the diagnosis of ond therapy for patients with Infectious diseases. There ore currently some 460 rules In the MYC IN rule set, makin9 conclusions about 86 of the 236 attributes (the remoinill(l attributes ore simply input dolo). Results of formal evaluations of MYCIN's competence In tho domnlns of bacteremia (bacterial Infections In the blood) ond menin(Jitis Indicate that MYCIN's performance In these oreos has begun to approach that of medical specialists [ 1 0).

The PUFF system (6) performs Interpretation of measurements from the pulmonary function laboratory. The do to from over 100 cases were used to create some 60 production rules diagnosing the presence of pulmonary disease. These rules oro used to create o complete report incluclin~l the Input measurements, historical information, oncl the measurement interpretation.

The IIEADMED program (5) is on application of EMYCIN

to c lini c al ps ychophormacolo~IY· llw system diagnoses a ron\le of psychiatric disorders and con recommend drug treatment if Indicated. Tho system contains 275 rules at present, one of which Is shown In figure 3.

• If : I) lhe diagnosis for ~1hich therapy is being recommended is major-depressive-disorder,
• 2 ) The intensity of this patient's psychiatric disturbance is one of: moderate, mild,
• The current mental state of the patient is psychotic, ond
• There is no recent prior episode of psychiatric disturbance

Then: There is strongly suw1cstive evidence ( .8) that the class or category of treatments is antipsychotic

Figure 3 . A sample IIEI\DMED rulo .

As o stronger test of dornilin independence, EMYCIN was npplied to the complctP.iy non-meclical domain of s truc tural analysis. Si\CON (Structural Analysis Con:;ultotlon) [ ?] provid·~s advice to a structurnl engineer rcqnrclincJ tho usc of a lnrqe structural analysis program ca lled MARC . The MARC pruqrom uses finite-element nn<1 iys is techniques to simullltc the mechanical behavior of ob j ec t s. The ~1onl of the Si\CON program is to recommend on analysis s tra tcgy to guidP tiHJ MAHC user in the choice of specific input dato, numerical methods and material propPrtics. 1 he system contnins some 160 rules and 50 nttriiJutrs, half of which arc concluded by the rules .

4 flange of Apr lie ability -- Limitations

Althouqh we do not have a precise characterization of domni11s whi ch nrc most suitable for an EMYCIN application, our l"Xpf'ricnce provides some general uuidelines. We found thnt many of the simpler sy:; tems did not even make 11 sc o f the inexoct Inference mechani sm provided by Cfs . It is possible that more efficient representations exist for tlw prec ise knowledge existing In such domnins . However, it s till seems appropriate to build a rcilsoning prowam from EMYCIN os a first test of the inference rules written by an exp0r t . While mony of the system's complicated leotures, such os certainty factors, muy 90 unused in the simpler sys ll"IIIS, tltoso f0atures do not substantially burden a proqrnm which does not use their extra generality.

It is not alwuys cosy to octur,lly formulate the domain knowle d~IC Into production rules , even in the domains that have been successfully implemented so far . Our desire to keep the rule formAt simple is occasionally at odds with the need to encode ·the many aspects of scientific decision-making. For cx£lmple, the process of therapy s ciPc tlon in MYCIN proved more amenable to o generate nnd test algorithm [3]. The backward-choinin~l of rt,tles by the deductive system Is olso often a stumbling block for c~ xperts who nre new to the system; however, they soon leorn to structure their knowled~1e appropriately. In fact, some experts have felt that encoding their knowledge Into rules hos helped them formalize their own view of the domain, leading to qreater consistency in thoir decisions.

The representation of foct s as associative triples with CF 's may not be natural or adequate for many domains . However, the triples have proved o flexible enough data s truc ture in our lnves tiootions thus for. The specific cont rol s tructure In EMYCIN, viz., ~1oal-directed backward c hAininn of rules, 111i[!ht be considered much morA rest ric live .

Certainly other control struc tur es and reprcsentotlons ore possible. We rccognile that EMYCIN is not ns (JCnerol as some other efforts, e.g. KRL [ 1 ] , nor Is It lntonded to be : there may weil bo advontoges In restrictlnq the user's options. At least during the initial formulation of the knowledge of a domain, the simple framework of a single, easily understood control structure allows the expert to focus on the knowledge In the rules themselves, and not oet sidetracked by a bewildering array of control choices.

5 Conclusion

Currently the system builder still requires o fair knowledge of Lisp and the workinos of EMYCIN Itself . Our work olms ot Improving the facilities for acquiring and debuoglng rules, as these are tlw most time-consuming portion of creating a new consultation system. Our aim Is to hove a truly convenient "workshop" for knowlcd \JC­ based system exploration, In which a knowledge engineer can relatively quickly create o functional consultation pronram in a new domain, try out a new set of rulos, or simply discover whether o rule-based system Is reasonable for the task.

Acknowledgements

The author wishes to acknowledge the contribution of Carli Scott, who programmed much of the QA Module and continues to assist In tho development of new features In EMYCIN. Thanks to Carll ond also to Bruce Buchanan for their helpful advice on this paper.