Prototypes and Production Rules: An Approach to Knowledge Representation for Hypothesis Formation

Introduction

Much of A rtificlal Intelligence research has focused on determining the appropriate knowledge representations to use In order to achieve high performance from knowledge-based systems. The principal A rtificlal Intelligence theme being explored In this present research · Is that there are many advantages to a system that uses both frame-like structures and production rules to perform problem-solving tasks In knowledge-Intensive domains.

In order to test this theme, a knowledge representation was designed using a combination of frames and production rules. The frames are called Prototypes because they represent stereotypical situations which can be used as a basis for comparison to the actual situation given by the data."" The domain chosen was that of pulmonary physiology. The task was to Interpret a set of pulmonary function test results, producing a set of interpretation statements and a diagnosis of pulmonary disease In the patient. A system called CENTAUR has been written to perform this task using prototypes that characterize the typical features of each pulmonary disease. Each feature Is called a Component of the prototype. A s!Ociated "'ith each component are production rules used to infer a value for the component. These production rules are a form of procedural attachment with a constrained, stylized syntax that makes them easier to examine than general procedures. This constrained syntax leads to other advantages, such a~ ease of acquisition and modifiability as discussed In [2]. The prototypes focus the search for new information by guiding the invocation of the production rules and eliciting the mo~t relevant Information from the user. These prototypes are linked together In a network in which the links specify the rel:~tionships between the prototypes.

This research developed out of the MYCIN project [5), which uses a knowledge base of production rules to perform infP.ctious disease consultations. Initially, a MYCIN-Iike

· This work was supported by the Advanced Research' Projects Agency under contract MDA 903-77-C-0322. Computer facilities were provtded by the SUM EX-AIM facility at St:~nford University under NIH grant RR-00785. The author Is sponsored by the Xerox Corporation under the direction of the Xerox Palo Alto Research Center.

·· The term prototype has been given the same meaning by other re~earchers, for example In KRL [I], a prototype is a special kind of unit representing a hypothetical Individual that Is the typical member of a class.

production rule system called PUFF [4] was written to perform pulmonary function test interpretations. Problems with the production rule formalism In PUFF and similar rule-based systems, such as a need to focus the search for new information and the desire to represent characteristic patterns of disease, motivated the creation of a prototype-directed system.

2 The CENTAUR System

CENTAUR produces an Interpretation of data and a pulmonary diagnosis based on a set of pulmonary function test results. The Inputs to the system are the pulmonary function te~t results and a set of patient data including the patient's name, sex, age, and a. referral diagnosis. The output consists of both a set of interpretation statements that serve to explain or comment on the pulmonary function test results and a final diagnosis of pulmonary disease in the patient.

CENTAUR usb a hypothesis-directed approach to problem solving where the possible hypotheses are represented by the prototypes. The goal of the system Is to confirm some of the prototypes as matching the data In an actual case. The final set of confirmed prototypes is the system's solution for classifying the data In that case. The prototypes represent the various pulmonary diseases, their degrees and subtypes, with the result that the set of confirmed prototypes represents the diagnosis of pulmonary disease in the patient.

In the example below, the prototype representing a pulmonary function consultation itself, the PULMONARY­ DISEASE prototype, has been selected as the Initial Current Prototype, the system's best hypothesis about how to classify the data In the case. The Initial data Is requested and the user responses (preceded by a double asterisk **) are recorded. Data entered in the system suggests or "triggers" disease prototypes. The triggered prototypes are placed on a Hypothesis List and ordered according to how closely they match the data. The system attempts to fill in values for the components of the current prototype, which may ca.use rules to be Invoked; or, If no rules are associated with the component, the system will ask the user for the value. When all of the prototype components have values, a decision Is made by the system as to whether the given data values match those expected for the prototype. A not her prototype Is then selected as the Current Prototype, and the process repeats. The system moves through the prototype network confirming or disproving indicated disease prototypes. Matching data and prototypes continues until each piece of data has been accounted for by some confirmed prototype or until the system has concluded that It cannot account for any more of the data.

3 CENTAUR Example

The following Is an example of an interpretation of a set of pulmonary function test results for one pulmonary patient. Comments are in italics.

·CENTAURt 14-Jan-79 13:54:87

--------PATIENT-7--------

1) Patient's identifying number: ** 7446

Z) roforral diagnosis: tt ASTHMA

[Trigger for OAD and CM 900]

3) FEV1/FVC ratio: ** 40

(Prototype OAD is triggered by the value 40 for tht FEV/IFIIC ratio. The Certainty Measure (CM) indicates on a numtrical scale the defree of ctrtainty with ruhich the prototypt is indicated by the data.

1. FVC/FVC-predicted: ** 81
2. TLC observed/predicted: ** 139

[Trigger for NORMAL and CM 500] (The questioninf ccmtinrus and other prototypes art trlggtrtd by the data values.

HoreSpecific Prototypes chosen: NORMAL OAD (Although there are five possible, more specific diseast prototypts for the PULMONARY-DISEASE prototype, only the truo that were triggered by the initial data art selected as possibilities to p~trsur. Thrse prototypes arefilled in with the data values that are already known in the case.

!Surprise Value! 261 for RV in NORMAL, CH: 788 !Surprise Value! 139 for TLC in NORMAL, CH: 488

(Any data values that art not consistent with the values expected for that dtuase prototype are noted as Surprise Values, and the CM for that prototype is lowered. Two of the data valuts that are ncrt consistent rulth the NORMAL pulmonary function prototype are s horun hert.)

Hypothesis list: (OAO 990) (NORMAL ·699) (The Hypothesis List of triggered prototypes is then ordered according to the CM of the prototypes and a neru Cumnt Prototype, OAD, Is chosen.)

Components of OAD to trace: FZ5 D~RV/TLC (In order to instantiate the OAD prototype, two more components must have values. These are then asked of the user if there are no rules that can be uud to deduce their values. The OAD prototype is confirmed as matching the data in this case. Control information associated with the prototypt specifies that the Degree of OAD should be determined next, follorued by the Subtype of OAD.)

Confirmed: ASTHMA SEVERE·OAD OAD

(Eventually SEI'ERE-OAD and ASTHMA are also confirmed. Data values that can be accounted for by one of the confirmed prototypes are marktd. If thert are data values rtmainlng that cannot be a.ccounttd for by tht confirmed prototypts, the system wtll attempt to determine if there are multiple distasts in the patient. Refinement Rrtles associated ruith the confirmed prototypes art rxrcuttd to further refine the diagnosis and conclti.Sicons which are then printed.)

Conclusions:

Smoking probably exacerbates the severity or the patient's airway obstruction. Good response to bronchodilators is consistent with an asthmatic condition.

Pulmonary Function Diagnosis: Severe Obstructive Airways Disease. Asthmatic type.

4 Prototypes and Components

Following frame terminology, each prototype contains SLOTS of information associated with it. One of these is the slot COMPONENTS that lists the substantive characteristics of the prototype. Each component may, In turn, have slots of intormatlon associated with it. In the OA D prototype In Figure i . l, there are components for many of the pulmonary function tests that are useful In characterizing a patient with OAD. For example, the TOTAL LUNG CAPACITY of a patient with OA D is typically higher than that · of a person with normal pulmonary function. Thus there Is a component, TOTAL LUNG CAPACITY, with a range of PLAUSIBLE VALUES that are characteristic of a person with OA D.

Some control information is represented explicitly in slots associated with the prototype. These slots contain a set of one or more clauses that express some action to be taken by the system In order to instantiate the prototype (CONTROL slot), upon confirmation of the prototype (Jf.CONFIRMED slot), in the event that a prototype is disproved (IF·DISPROVED slot), and in a clean-up stage after the system processing has been completed (ACTION slot).

PROTOTYPE

Obstructive Airways Disease

GENERAL SLOTS

--Bookkeeping Information

• --Pointers to other

prototypes

(link prototype)

--English phrases

CONTROL SLOTS

Control

If-Confirmed

If-Disproved

Action

COMPONENTS

Plausible Values

Default Value

Possible Error Values

Rules

Importance of value

to this prototype Author: Aikins Date: 27-0CT -78 Source: Dr. Fallat Pointers: (degree MILD-OAD) .. . (subtype ASTHMA) .. . Hypothesis: "There Is an interpretation of OAD."

Deduce degree of OAD

Deduce subtype of OAD

If-Confirmed: Action:

Deduce OA D findings

Print OA D findings

TOTAL LUNG CAPACITY

Plausible Values: > 100

Importance: i

REVERSIBILITY

Rules: 19, 21, 22 ·. 25 Importance: I

FIG U R E.4 .1 A sample prototype with possible slots on the left and values for OAD on the right.

4.1 rroduction Rules

The CENTAUR knowledge base also includes sets of l ll'oductlon rules. Many of the production rules are classified as NFERENCE RULES, rules used to infer information in the domain. They refer to values for components in their premise clauses and make conclusions about values of components in their action clauses. An example of one of the Inference Rules Is given In Figure 1.2. The RULES slot associated with a component contains a list of all Inference Rules that make a conclusion about that component. These may be applied when a value is needed for the component.

• If: 1) A The mmf/mmf-pred fs less than 28, and
• A The mmf/mmf-pred is less than 15, and B The fvc/fvc-pred is less than 88

B The fvc/fvc-pred is greater than 88, or

• Then: 1) There is evidence that the degree of OAD is severe, and
• One of tho OAD findings is: Low mid-expiratory flow is consistent with severe airway obstruction.

FIG UR E.4.2 A Sample Production Rule--English Version

5 Control Structure

The control Information used by CENTAUR Is contained either in slots associated with the individual prototypes or in a simple Interpreter. Control strategies specific to an Individual prototype are represented In slots associated with that prototype, with more general system control being expressed In the

Interpreter.

The control structure can be broken Into three stages: a hypothesis-formation stage in which data values are acquired and an attempt Is made to match prototypes to data, resulting In a list of confirmed prototypes; a refinement stage In which a set of REFINEMENT RULES are applied to the list of confirmed prototypes to "debug" this list and further refine the recommendations that will be made; and a final "clean-up" stage In which, for example, findings associated with the prototype are printed.

G Advantages of the Prototype-Directed Approach

The use of this approach for the pulmonary function Interpretation task, as compared to the purely rule-based approach used in PUFf, results In two categories of ad vantages: those dealing with the knowledge base representation Itself and those dealing with the system's reasoning and performance. Advantages In knowledge representation occur partly because some knowledge previously rr.prescnted In rules Is now represented more clearly In prototypes. For example, the prototypes explicitly represent control Information formerly rl'presented In the PUFF Inference rules. In the PUFF system, there are rules whose purpose It is to guide computation by controlling the invocation of other rules. This feature can be very confusing to the medical experts since they do not know which rules are those intended to represent descriptive medical expertise and which rules are those serving a necessary computational function. New knowledge is also being represented in prototypes; for example, plausible ranges of values for each of the pulmonary function tests for each disease can be listed, as well as the relative Importance of each measurement In a particular disease prototype. Advantages in system reasoning and performance, that is, the questions that are asked and the order in which

Information is acquired, include the following:

(A) ·Consultation flow more closely follows physician's rea.sonlng. The process of medical problem solving has been discussed by many researchers (e.g., [3]) and it is widely felt that a sequence of suggesting hypotheses, acqui ring further information, and then revising the hypotheses, as is used in CENTAUR, Is, in fact , the problem-solving process used by most physicians. Thus CENTAUR offers Increased conceptual clarity, in that !he user can understand what the program Is doing, and this factor leads to other advantages, for example, the system can offer the user a more intelligible explanation of its performance during the consultation.

(B) Questions ire a.sked in a reasonable order. In a rule­ based system such as PUFF, questions are asked of the user as rules are Invoked containing clauses referring to Information not yet known. The expert can control the order In which the questions are asked only by writing rules to enforce some order. As has been discussed, this procedure results in a potentially confusing rule base where some rules guide computation. In the prototype-directed system, the expert can specify the order In which information Is acquired for each prototype In the control slot.

(C) Only relevant questions are uked. Another advantage of CENTAUR over PUFF is that only those hypotheses suggested by the initial data are explored. For example, If the Total Lung Capacity (TLC) for the patient is 70, then CENTAUR would begin exploring the possibility of Restrictive Lung Disease (R LD) because a low TLC would trigger the R LD prototype. (A low TLC Is consistent with a hypothesis of R LD; a high TLC Is consistent with OA D.) In the PUFF program, the rlrst disease tried is always OA D, so the PUFF program would begin asking questions dealing with OAD. These questions would seem Irrelevant considering the data, and, Indeed, if there were no data to indicate OAD, such questions would not be asked by CENTAUR.

7 Summary

CENTAUR was designed In response to problems that occurred while using a purely rule-based system. By changing the knowledge representation to Include prototypes as well as production rules, new knowledge was represented. Further, knowledge that had been represented rather awkwardly In rules was represented more clearly In prototypes. The production rules were retained as a stylized form of p[ocedural attachment that could be easily examined or modified. By altering the control structure so that a best-fit matching process of prototypes to data produced a current best hypothesis to guide further search, a more focused consultation resulted w.hlch more closely followed the way physicians reason. Control knowledge was explicitly labeled and made prototype-specific so that control of the consultation was adapted to the current best hypothesis. In summary, the prototype-directed system achieved better reasoning and performance than the rule-based system. In addition, although representing knowledge In production rules alone did not seem adequate for this task, the ability to represent knowledge In prototypes as well did provide

the needed rlextbtllty.