Page images
PDF
EPUB

ORGANISM-1 is pseudomonas aeruginosa RULE 37)

USER: HOW 1.3

TEIRESLAS: (i.e. HOW was it established that the aerobicity of ORGANISM-1 is facultative?)

The following were used:

(3.1) RULE Z7 indicated there is strongly suggestive evidence (.8) that the aerobicity of ORGANISM-1 is facultative

(3.2) RULE 27 indicated there is weakly suggestive evidence (2) that the merobicity of ORGANISM-1 is anaerobic

Since this gave a cumulative CF of (.8) for facultative, and (-2) for anaerobic, it has been established that the aerobicity of ORGANISM-1 is facultative.

USER: WHY DIDN'T YOU CONSIDER STREPTOCOCCUS AS A POSSIBILITY FOR ORGANISM-1?

TEIRESIAS: The following rule could have been used to determine that the identity of ORGANISM-I was streptococcus: RULE 33

But clause 2 ("the morphology of the organism is coccus") was already known to be false for ORGANISM-1, so the rule was never tried.

Discussion

A few short comments aimed at knowledge engineering are in order.

English is the language most natural and comfortable for our experts and users, and was therefore the language cho sen for interactive consultation, explanation, and external representatioa of the rules (the internal format is INTERLISP). This situation is not peculiar to doctors; in most areas of application of intelligent agents I believe that English (i.e., natural language) will be the language, of choice. Programming an English language processor and front-end to such systems is not a scary enterprise because:

(a) the domain is specialized, so that possible interpretations are constrained.

(b) specialist-lalk is replete with standard jargon and stereotyped ways of expressing knowledge and queries-just right for text templates, simple grammars and other simple processing schemes.

Results

No clinical evaluation of MYCIN is currently being done. In a preliminary evaluation, dove outside of the clinical setting, a panel of expert judges was asked to rate MYCIN'S performance along a number of dimensions (e.g., infecting organism identification, organism significance). In 90 percent of the cases submitted to the judges, a majority of the judges said that the program's decisions were the-same-as or as-good-as the decisions they would have made.

Esplanation

MYCIN can expose its line of reasoning by offering explanations of various kinds. "Why" and "How" questions can be asked by the user during the consultation. "Why" is the user's way of inquiring, “Why do you want to know that?" "How" is his way of asking, "How did you conclude that...?" In a post-consultation, he can similarly inquire about how the diagnostic conclusions were reached, and inquire about the reasons why certain other conclusions were ruled out. Examples of the MYCIN-TEIRESIAS explanation capabilities follow:

MYCIN: Is the patient's illness with
ORGANISM-1 a hospital-acquired infection?
USER: WHY
TEIRESIAS: (i.e., WHY is it important to
determine whether or not the infection with
ORGANISM-1 was acquired while the patient
was hospitalized?)

(1.0) This will aid in determining the
category of ORGANISM-1.

It has already been established that

(1.1) the gram stain of ORGANISM-1 is
gramneg, and
(1.2) the morphology of ORGANISM-1 is rod,
and
(1.3) the aerobicity of ORGANISM-1 is
facultative

Therefore, if

(1.4) the infection with ORGANISM-1 was not acquired while the patient was hospitalized

then

there is strongly suggestive evidence (8) that the category of ORGANISM-1 is enterobacteriaceae

Also: there is weakly suggestive evidence (.1) that the identity of

(c) the ambiguity of interpretation resulting from simple schemes can be dealt with easily by feeding back interpretations for confirmation. If this is done with a pleasant "I didn't quite understand you..." tone, it is not imitating to the user.

English may be exactly the wrong language for representation and interaction in some domains. It would be awk. ward, to say the least, to represent DENDRAL's chemical structures and knowledge of mass spectrometry in English, or to interact about these with a user.

Simple explanation schemes have been a part of the Al scene for a number of years and are not hard to implement. Really good models of what explanation is as a transaction between user and agent, with programs to implement these models, will be the subject (I predict) of much future research in AI.

Without the explanation capability, I assert, user acceptance of MYCIN would have been nil, and there would have been a greatly diminished effectiveness and contribution of our experts.

MYCIN was the first of our programs that forced us to deal with what we had always understood: that experts' knowledge is uncertain and that our inference engines had to be made to reason with this uncertainty. It is less impor. tant that the inexact reasoning scheme be formal, rigorous, and uniform than it is for the scheme to be natural to and easily understandable by the experts and users.

All of these points can be summarized by saying that MYCIN and its TEIRESIAS adjunct are experiments in the design of a see-through system, whose representations and processes are almost transparendy clear to the domain specialist. “Almost" here is equivalent to "with a few minutes of introductory description." The various pieces of MYCIN-the backward chaining, the English transactions, the explanations, etc.-are each simple in concept and realization. But there are great virtues to simplicity in system design: and viewed as a total intelligent agent system, MYCIN TEIRESIAS is one of the best engineered.

SUIX: signal understanding

Historical note

SU/X is a system design that was tested in an application whose details are classified. Because of this, the ensuing discussion will appear considerably less coocrete and tangible than the preceding case studies. This system design was done by H. P. Nii and me, and was strongly influenced by the CMU Hearsay II system design (Lesser and Erman, 1977).

with full explanation of the support for each. There are two types of input data: the primary signal (to be understood): and auxiliary symbolic data (to supply context for the understanding). The primary signals are spectra, represented

descriptions of the spectral lines. The various spectra cover the physical space with some spatial overlap.

Representations

The rules given by the expert about objects, their behav. ior, and the interpretation of signal data from them are all represented in the situation action form. The situations" coastitute invoking conditions and the "actions" are processes that modify the current hypotheses, post unresolved issues, recompute evaluations, etc. The expert's knowledge of how to do analysis in the task is also represented in rule form. These strategy rules replace the normal executive program.

The situation-hypothesis is represented as a node-link praph, tree-like in that it has distinct "levels," each represeating a degree of abstraction (or aggregation) that is natural to the expert in his understanding of the domain. A node represents an hypothesis: a link to that node represents support for that hypothesis (as in HEARSAY II, "support from above" or "support from below"). "Lower" levels are concerned with the specifics of the signal data. "Higher" levels represent symbolic abstractions.

Sketch al method

The situation-hypothesis is formed incrementally. As the situation unfolds over time, the triggering of rules modifies or discards existing hypotheses, adds new ones, or changes support values. The situation-hypothesis is a common workspace ("blackboard," in HEARSA Y jargon) for all the rules.

la general, the incremental steps toward a more complete and refined situation-hypothesis can be viewed as a sequence of local generate-and-test activities. Some of the rules are plausible move generators, generating either nodes or links. Other rules are evaluators, testing and modifying node descriptions.

In typical operation, new data is submitted for processing (say, N time-units of new data). This initiates a flurry of rule-trieserings and consequently rule-actions (called "evears"'). Some events are direct consequences of data; ocher events arise in a cascade-like fashion from the triggering of rules. Auxiliary symbolic data also cause events, usually affecting the higher levels of the hypothesis. As a consequence, support-from-above for the lower level processes is made available; and expectations of possible lower level events can be formed. Eventually all the relevant rules have their say and the system becomes quiescent, thereby triggering the input of new data to reenergize the inference activity.

The system uses the simplifying strategy of maintaining only one "best" situation-hypothesis at any moment, modifying it incrementally as required by the changing data. This

[ocr errors][merged small]

RESIAS reporting of rule invocations in the construction of a reasoning chain.

Since its knowledge base and its auxiliary symbolic data give it a model-of-the-situation that strongly constrains interpretation of the primary data stream, SUIX is relatively unperturbed by errortul or missing data. These data condicioas merely cause fluctuations in the credibility of individual hypotheses and/or the creation of the "wait-and-see" events. SUIX can be (but has not yet been) used to control sensors. Since its rules specify what types and values of evidence are necessary to establish support, and since it is constantly processing a complete hypothesis structure, it can request "critical readings from the sensors. La general, this allows an efficient use of limited sensor bandwidth and data acquisition processing capability.

Other case studies

Space does not allow more than just a brief sketch of other interesting projects that have been completed or are in progress.

AM: mathematical discovery

AM is a knowledge-based system that conjectures interesting concepts in elementary mathematics. It is a discoverer of interesting theorems to prove, not a theorem proving program. It was conceived and executed by D. Lepas for his Ph.D. thesis, and is reported by him in these proceedings.

AM's knowledge is basically of two types: rules that suggest possibly interesting new concepts from previously conjectured concepts; and rules that evaluate the mathematical "interestingness" of a conjecture. These rules attempt to capture the expertise of the professional mathematician at the task of mathematical discovery. Though Leoal is not a professional mathematician, he was able successfully to serve as his own expert in the building of this program.

AM conducts a heuristic search through the space of coocepus creatable from its rules. Its basic framework is generation-and-test. The generation is plausible move gener tion, as indicated by the rules for formation of new concepts. The test is the evaluation of "interestingness." Of particular note is the method of test-by-example that lends the flavor of scientific hypothesis testing to the enterprise of machematical discovery.

Initialized with concepts of elementary set theory, it conjectured concepts in elementary aumber theory, such as "add," "multiply" (by four distinct paths!), "primes," the unique factorization theorem, and a concept similar to primes but previously not much studied called "maximally divisible numbers."

approach is made feasible by several characteristics of the domnin. First, there is the strong continuity over time of objects and their behaviors (specifically, they do not change ndically over time, or behave radically differently over short periods). Second, a single problem (ideatity, location and velocity of a particular set of objects) persists over numerous dan gathering periods. (Compare this to speech understanding in which each sentence is spoken just once, aad each presents a new and different problem.) Finally, the system's hypothesis is typically "almost right," in part because it gets numerous opportunities to refine the solution (i.e., the numerous data gathering periods), and in part because the availability of many knowledge sources tends to over determine the solution. As a result of all of these, the curreat best hypothesis changes only slowly with time, and hence keeping oaly the currear best is a feasible approach.

of interest are the time-based events. These rule-like expressions, created by certain rules, trigger upon the passage of specified amounts of time. They implement various "wait-and-see" strategies of analysis that are useful in the domain.

Results

In the test application, using signal data generated by a simulation program because real data was not available, che program achieved expert levels of performance over a span of test problems. Some problems were difficult because there was very little primary signal to support inference. Others were dificult because too much signal induced a plethora of alternatives with much ambiguity.

A modified SUIX design is currendy being used as the basis for an application to the interpretation of x-ray crystallographic data, the CRYSALIS program mentioned later.

Discussion

The role of the auxiliary symbolic sources of data is of critical importance. They supply a symbolic model of the existing situation that is used to generate expectations of events to be observed in the data stream. This allows flow of inferences from higher levels of abstraction to lower. Such a process, so familiar to Al researchers, apparendy is almost uarecognized among signal processing engineers. In the application task, the expectation-driven analysis is essential in controlling the combinatorial processing explosion a the lower levels, exactly the explosion that forces the traditional signal processing engineers to seek out the largest possible number-cruncher for their work.

The design of appropriate explanations for the user takes an interesting twist in SUIX. The situation-hypothesis unfolds piecemeal over time, but the "appropriate" explana. dion for the user is one that focuses on individual objects over time. Thus the appropriate explanation must be synthesized from a history of all the events that led up to the current hypothesis. Contrast this with the MYCIN-TEI.

MOLGEN: planning experiments in molecular genetics

MOLGEN, a collaboration with the Stanford Genetics Department, is work in progress. MOLGEN's task is to CRYSALIS: Inferring protela structure from electron

density maps

CRYSALIS, too, is work in progress. Its task is to hypothesize the structure of a protein from a map of electron density that is derived from X-ray crystallographic data. The map is three-dimensional, and the contour information is crude and highly ambiguous. Interpretation is guided and supported by auxiliary information, of which the amino acid sequence of the protein's backbone is the most important. Deasity map interpretation is a protein chemist's art. As always, capturing this art in heuristic rules and putting it to use with an inference engine is the project's goal.

The inference engine for CRYSALIS is a modification of the SUIX system design described above. The hypothesis formation process must deal with many levels of possibly useful aggregation and abstraction. For example, the map itself can be viewed as consisting of "peaks," or "peaks and valleys," or "skeletoa." The protein model has “atoms," "amide planes," "amino acid sidechains," and even massive substructures such as “helices." Procein molecules are so complex that a systematic generation-and-lest strategy like DENDRAL's is not feasible. Incremental piec. ing together of the hypothesis using region-growing methods is necessary.

The CRYSALIS design (alias SU/P) is described in a recent paper by Nü and Feigenbaum (1977).

provide intelligent advice to a molecular geneticist on the planning of experiments involving the manipulation of DNA. The geneticist has various kinds of laboratory techniques avail for changing DNA material (cuts, joins, insertions, deletioas, and so on): techniques for determining the biological consequences of the changes; various instruments for measuring effects; various chemical methods for induce ing, facilitating, or inhibiting changes; and many other tools.

Some MOLGEN programs under development will offer planning assistance in organizing and sequencing such tools to accomplish an experimental goal. Other MOLGEN proprams will check user-provided experiment plans for feasibiliry; and its knowledge base will be a repository for the rapidly expanding kaowledge of this specialty, available by interrogation.

la MOLGEN the problem of integration of many diverse sources of knowledge is central since the essence of the experiment planning process is the successful merging of biological, genetic, chemical, topological, and instrument knowledge. IA MOLGEN the problem of representing processes is also brought into focus since the expert's knowledge of experimental strategies-proto-plans-must also be represented and put to use.

One MOLGEN program (Stefik, 1978) solves a type of analysis problem that is often difficult for laboratory scientists to solve. DNA structures can be fragmented by chemicals called restriction enzymes. These enzymes cut DNA at specific recognition sites. The fragmentation may be complece or partial. One or more eazymes may be used. The fragmeated segments of the DNA are collected and sorted out by segment length using a technique called gel electro phoresis. The analytical problem is similar to that faced by DENDRAL: given an observed fragmentation pattern, bypothesize the best structural explanation of the data. More precisely the problem is to map the enzyme recognition sites of a DNA structure from complete or partial digests",

The program uses the model-driven approach that is similar to DENDRAL's and is discussed earlier. The method is generate-and-test. A generator is initiated that is capable of generating all the site-segment maps in an exhaustive, irre dundant fashion. Various pruning rules are used to remove whole classes of conceivable candidates in light of the data. Some of the pruning rules are empirical and judgmental. Others are formal and mathematically based.

The program solves simpler problems of this type of anat ysis better than laboratory scientists. The harder problems, however, yield oaly to the broader biological knowledge known by the scientists and not yet available to the propram's reasoning processes. In a recent test case, a problem whose solution space contained approximately 150,000,000 site-fragment "maps" was solved in 27 seconds of PDP-10 time using the INTERLISP programming system.

Interestingly, the computer scientist's formal understanding of the nature of the problem, his formal representation of the knowledge used for pruning out inappropriate candidates, and the computational power available to him enabled him to suggest a few new experimeat designs to his genericist collaborators that were not previously in their repertoire.

SUMMARY OF CASE STUDIES

Some of the themes presented earlier need no recapitulation, but I wish to revisit three here: generation-and-test; situation action rules, and explanations.

Generation and test

Aircraft come in a wide variety of sizes, shapes, and functional designs and they are applied in very many ways. But almost all that fly do so because of the unifying physical principle of lift by airflow; the others are described by exception. If there is such a unifying principle for intelligent programs and human intelligence it is generation-and-lest. No wonder that this has been so thoroughly studied in Al research!

In the case studies, generation is manifested in a variety of forms and processing schemes. There are legal move generators defined formally by a generating algorithm (DENDRAL's praph generating algorithm): or by a logical rule of inference (MYCIN's backward chaining). When legal move generation is not possible or not edicient, there are plausible move generators (as in SUIX and AM). Sometimes generation is interleaved with testing (as in MYCIN, SUIX, and AM). In one case, all generation precedes testing (DENDRAL). One case (META-DENDRAL) is mixed, with some testing taking place during generation, some after.

[ocr errors]

Tease also shows pea variety. There me sinople toets (WYCIN: "Is the organism verobic?"': SUIX: “Has a spec. mal line appeared a position Puy Some tests ane complex heuristic evaluations (AM: “Is the new concepe 'interest. ing'?"; MOLGEN: "Will the reaction actually take place?"") Sometimes a complex test con involve feedback to modity the object being tested (as in META-DENDRAL).

The evidence from our case studies supports the assertion by Newell and Simon that paration-sad-test is a law of our science (Newell and Simon, 1976).

Situation action rules

Sinuation Action rules are used to represent experts' knowledge in all of the case studies. Always the situation part indicates the specific conditions under which the role is relevant. The action part can be simpla (WYCIN: comclude presence of particular organism: DENDRAL: coe clude break of particular bood). Or it can be quite complex (MOLGEN: an experigatial procedure). The overriding consideration in making design choices is that the rule form chosen be able to represent clearly and directly what the expert wishes to express about the domain. As illustrated, this may necessitate a wide variation in rule syntax and semantics.

From a study of all the projects, a regularity emerges. A salient feature of the Situation Action rule technique for represeating experts' knowledge is the modularity at the knowledge base, with the concomitant lexibility to add or change the knowledge easily as the experts' understanding of the domain changes. Here too one must be pragmatic, not doctrinaire. A technique such as this cannot represent modularity of knowledge if that modularity does not exist in the domain. The virtue of this technique is that it serves as a framework for discovering what nodularity exists in the domain. Discovery may feed back to cause reformulation of the knowledge toward preater modularity.

Finally, our case studies have shown that strategy knowl edge can be captured in rule form. la TEIRESLAS, the metarules capture knowledge of how to deploy domain knowledge; in SUIX, the strategy rules represent the experts' knowledge of how to analyze" in the domain.

Explanation

Most of the programs, and all of the more recent onus, make available an explanation capability for the user, be he end-user or system developer. Our focus on end-users in applications domains has forced attention to human engineering issues, in particular making the need for the explo nacion capability imperative.

The Intelligent Agent viewpoint seems to us to demand that the agent be able to explain its activity: else the question arises of who is in control of the agent's activity. The issue is not academic or philosophical. It is an engineering issue that has arisen ia medical and military applications of intel

Lignat pents, and will goven future acceptance of a work in applications areas. And on the philosophical lovel one might evea arrue that then is a non imperative to provide accurate explanations to end users whose intuitions about our systems an almost al.

Fially, the explanation capability is meded part of the concerned stack on the knowledge acquisition problem. Ex. planation of the reasoning process is central to the interac. dive taaster of expertise to the knowledge base, and it is our most powerful tool for the debuering of the knowledge

ACKNOWLEDGMENT

The work reported herein has received long-term support from the Defense Advanced Research Projects Agency (DAHC 15-73-C-0135). The Nacional lastines a Health (5R24 RROOS12, RR-uong has supported DENDRAL, META-DENDRAL, and the SUVEX-AIM computer facil ity on which we compute. The National Science Foundation (MCS 76-11649, DCR 74-23461) hus supported research on CRYSALIS and MOLGEN. The Bureau of Health Sciences Research and Evaluation (HS-10544) has supported research on WYCIN. I am prateful to these xeracies for their contio uing support of our work.

I wish to express my deep admiration and thanks to the faculty, stadt and students of the Heuristic Programming Project, and to our collaborators in the various worldly arts. for the creativity and dedication that has made our work exciting and fruitful.

REFERENCES

General

Peigubowa. L. A. “Artificial lavelligence Lowered: Wher is ? Wher to it

nchieved? Where is it going?," invited power. Symposium on Arificial

Intelligence. Canberne, Australia, 1974. Feigenbaum, I. A. and J. Foldman, Computers and Thought. Now York,

McGraw-Hill. IX. Goldonia, I. ad S. Papers, Artificial love lipouce, Language wed the Study

& Keowledge." Cognitive Science. Vel. 1. No. I. 19. Gregory, R. "On How to Litde Information Controla w Much Dohavior,"

Dionics Research Report No. I. Hechino localligrace Departmea. Vui

versity of Edioburn, incl. Lewear, V. L med L D. Lowa. "A Retrospective View of the HLASAY.

I Architecture." Proceedings of the sea Incarnational Arabicial Incolli renco-1977, Merschworts Landicato al Technology. Cambridge. Mense

wote. August 22-23, 1977. Vd. L Nowell, A. sed H. A. Sicon. Humen Problem Solving. Prentice-Hall. 1972 Nowell, A. ad H. A. Simon. "Computer Science u Empirical Inquiry:

Symbols d Scered," Com ACM. 19. 3. Marel, in.

DENDRAL and META-DENDRAL

Primatova. E. A., 3. G. Druchemen, and I. Laderborg. "On Generality mad

Problem Solving o Cane Soudy Uring the DENDRAL Propa," Machine Inodigones 6. Edinburgh Univ. Prow, 1971.

« PreviousContinue »