« PreviousContinue »
The knowledge engineer
Generation-and-test: Omnipresent in our experiments is the
'classical" generation-and-test framework that has been the hallmark of Al programs for two decades. This is not a coasequence of a doctrinaire attitude on our part about heuristic search, but rather of the usefulness and sufficiency of the concept.
The knowledge engineer is that second party just discussed. She works intensively with an expert to acquire domain-specific knowledge and organize it for use by a program. Simultaneously she is matching the tools of the Al workbench to the task at hand-program organizations, methods of symbolic inference, techniques for the structuring of symbolic information, and the like. If the tool fits, or nearly fits, she uses it. If not, necessity mothers Al invention, and a new tool gets created. She builds the early versions of the intelligent agent, guided always by her intent that the program eventually achieve expert levels of per. formance in the task. She refines or reconceptualizes the system as the increasing amount of acquired knowledge causes the Al tool to "break" or slow down intolerably. She also refines the human interface to the intelligent agent with several aims: to make the system appear "comfortabie" to the human user in his linguistic transactions with it; to make the system's inference processes understandable to the user, and to make the assistance controllable by the user when, in the context of a real problem, he has an insight that previously was not elicited and therefore not incorpo rated.
la the next section, I wish to explore (in summary form) some case studies of the knowledge engineer's art.
Situation Action Rules: We have chosea to represent the
knowledge of experts in this form. Making no doctrinaire claims for the universal applicability of this representation, we nogetheless point to the demonstrated utility of the rule-based representation. From this representation flow rather directly many of the characteristics of our programs: for example, ease of modification of the knowledge, ease of explanation. The essence of our approach is that a rule nust capture a "chunk" of domain knowl edge that is meaningful, in and of itself, to the domain specialist. Thus our rules bear only a historical relationship to the production rules used by Newell and Simon (1972) which we view as "machine-language programming" of a recognize act machine.
The Domain-Specific Knowledge: It plays a critical role in
organizing and constraining search. The theme is that in the knowledge is the power. The interesting action arises from the knowledge base, not the inference engine. We use knowledge in rule form (discussed above), in the form of inferentially-rich models based on theory, and in the form of tableaus of symbolic data and relatioaships (i.e., frame-like structures). System processes are made to conform to natural and convenient representations of the do main-specific knowledge.
CASES FROM THE KNOWLEDGE ENGINEER'S
Flexibility to modify the knowledge base: If the so-called
"grain size" of the knowledge representation is chosen properly (i.e., small enough to be comprehensible but large enough to be neaningful to the domain specialist), then the rule-based approach allows great flexibility for adding, removing, or changing knowledge in the system.
I will draw material for this section from the work of my group at Stanford. Much exciting work in knowledge engineering is going on elsewhere. Since my intent is not to survey literature but to illustrate themes, at the risk of appearing parochial I have used as case studies the work I know best.
My collaborators (Professors Lederberg and Buchanan) and I began a series of projects, initially the development of the DENDRAL program, in 1965. We had dual motives: first, to study scientific problem solving and discovery, par. dicularly the processes scientists do use or should use in inferring hypotheses and theories from empirical evidence; and second, to conduct this study in such a way that our experimental programs would one day be of use to working scientists, providing intelligent assistance on important and difficult problems. By 1970, we and our co-workers had pained enough experience that we felt comfortable in laying out a program of research encompassing work on theory formation, knowledge utilization, knowledge acquisition, explanation, and knowledge engineering techniques. Although there were some surprises along the way, the general lines of the research are proceeding as cavisioned.
Line-of-reasoning: A central organizing principle in the de
sign of knowledge-based intelligeat agents is the maintenance of a linc-of-reasoning that is comprehensible to the domain specialist. This principle is, of course, not a logical necessity, but seems to us to be an engineering principle of major importance.
Multiple Sources of Knowledge: The formation and maio
tenance (support) of the line-of-reasoning usually require the integration of many disparate sources of knowledge. The representational and inferential problems in achieving a smooth and effective integration are formidable engineering problems.
Explanation: The ability to explain the line of reasoning in
a language convenient to the user is necessary for application and for system development (e.g., for debugging and for extending the knowledge base). Once again, this is an engineering principle, but very important. What con
As a road map to these case studies, it is useful to keep in mind certain major themes:
stitutes. " explanation" is not a simple concept, and considerable thought needs to be given, in each case, to the structuring of explanations.
Rules of this form are natural and expressive to mass spectrometrists.
Sketch a method
Begun in 1965, this collaborative project with the Stanford Mass Spectrometry Laboratory has become one of the longest-lived continuous efforts in the history of Al (a fact that in no small way has contributed to its success). The basic framework of generation-and-test and rule-based representation has proved rugged and extendable. For us the DENDRAL system has been a fountain of ideas, many of which have found their way, highly metamorphosed, into our other projects. For example, our long-standing commitment to rule-based representations arose out of our (successful) attempt to head of the imminent ossification of DENDRAL caused by the rapid accumulation of new knowledge in the system around 1967.
DENDRAL's inference procedure is a heuristic search that takes place in three stages, without feedback: plangenerate-test.
"Generate" (a program called CONGEN) is a generation process for plausible structures. Its foundation is a combinatorial algorithm (with mathematically proven properties of completeness and non-redundant generation) that can pro duce all the topologically legal candidate structures. Coostraints supplied by the user or by the Plan" process prune and steer the generation to produce the plausible set (i.e., those satisfying the constraints) and not the enormous legal set.
**Test" refines the evaluation of plausibility, discarding less worthy candidates and raak ordering the remainder for examination by the user. "Test" first produces a "predicted set of instrument data for each plausible candidate, using the rules described. It then evaluates the worth of each candidate by comparing its predicted data with the actual input data. The evaluation is based on heuristic criteria of goodness-of-fit. Thus, "test" selects the "best" explanations of the data.
“Plan" produces direct (i.e., not chained) inference about likely substructure in the molecule from patterns in the data that are indicative of the presence of the substructure. (Pat. terds in the data trigger the left-hand-sides of substructure rules). Though composed of many atoms whose intercooDections are given, the substructure can be manipulated as atom-like by "generate." Aggregating many units eatering into a combinatorial process into fewer higher-level units reduces the size of the combinatorial search space. "Plan" sets up the search space so as to be relevant to the input dana. "Generate is the inference tactician; "Plan" is the inference strategist. There is a separate **Plan" package for each type of instrument data, but each package passes substructures (subgraphs) to "Generale." Thus, there is a uniform interface between "Plan" and "Generate." User-supplied constraints enter this interface, directly or from userassist packages, in the form of substructures.
Sources of knowledge
The various sources of knowledge used by the DENDRAL system are:
Valences (legal connections of soms); stable and unstable configurations of atoms; rules for mass spectrometry fragmentations; rules for NMR shifts; experts' rules for planning and evaluation; user-supplied constraints (contextual).
Actioa: Fragmentation of the
particular configuration (Breaking links)
DENDRAL's structure elucidation abilities are, paradoxically, both very general and very narrow. In general, DENDRAL handles all molecules, cyclic and tree-like. In pure structure elucidation under coastraints (without instrument data), CONGEN is unrivaled by human performance. In structure elucidation with instrumeat data, DENDRAL'S performance rivals expert human performance only for a small number of molecular families for which the program has been given specialist's knowledge, namely the families of interest to our chemist collaborators. I will spare this computer science audience the list of names of these families. Within these areas of knowledge-intensive specialization, DENDRAL's performance is usually not only much faster but also more accurate than expert human performance.
The statement just made summarizes thousands of runs of DENDRAL on problems of interest to our experts, their colleagues, and their students. The results obtained, along with the knowledge that had to be given to DENDRAL to obtain them, are published in major journals of chemistry. To date, 25 papers have been published there, under a series title "Applications of Artificial Intelligence for Chemical Inference: (specific subject)" (see for example, the Buchanan, Smith, et al., 1976, reference).
The DENDRAL system is in everyday use by Stanford chemists, their collaborators at other universities and collaborating or otherwise interested chemists in industry. Users outside Stanford access the system over commercial computer communications network. The problems they are solving are often difficult and novel. The British government is currently supporting work at Edinburgh aimed at transferring DENDRAL to industrial user communities in the UK.
Representation and extensibility. The representation cho sen for the molecules, constraints, and rules of instrument data interpretation is sufficiently close to that used by chest ists in thinking about structure elucidation that the knowl edge base has been extended smoothly and easily, mostly by chemists themselves in receat years. Only one major reprogramming effort took place in the last 9 years when a new generator was created to deal with cyclic structures.
Representation and the Integration of multiple sources of knowledge. The generally difficult problem of integrating various sources of knowledge has been made easy in DENDRAL by careful engineering of the representations of ob jects, constraints, and rules. We insisted on a common las guage of compatibility of the representations with each other and with the inference processes: the language of molecular structure expressed as graphs. This leads to a straightforward procedure for adding a new source of knowledge, say, for example, the knowledge associated with a new type of instrument data. The procedure is this: write rules that de scribe the effect of the physical processes of the instrument 00 molecules using the situation action form with polec.
ular graphs on both sides; any special inference process using these rules must pass its results to the generator only (!) in the common graph language.
It is today widely believed in Al that the use of many diverse sources of knowledge in problem solving and data interpretation has a strong effect on quality of performance. How strong is, of course, domain-dependent, but the impact of bringing just one additional source of knowledge to bear on a problem can be startling. In one difficult (but not un usually difficult) mass spectrum analysis problem, the propram using its mass spectrometry knowledge alone would have generated an impossibly large set of plausible candidates (over 1.25 million!). Our engineering response to this was to add another source of data and knowledge, proton NMR. The addition on a simple interpretive theory of this NMR data, from which the program could infer a few additional constraints, reduced the set of plausible candidates to one, the right structure! This was not an isolated result but showed up dozens of times in subsequent analyses.
DENDRAL and data. DENDRAL'S robust models (topological, chemical, instrumental) permit a strategy of finding solutions by generating hypothetical "correct answers" and choosing among these with critical tests. This strategy is opposite to that of piecing together the implications of each data point to form a hypothesis. We call DENDRAL'S strategy largely model-driven, and the other data-driven. The consequence of having enough knowledge to do modeldriven analysis is a large reduction in the amount of data that must be examined since data is being used mostly for verification of possible answers. Ia a typical DENDRAL mass spectrum analysis, usually no more than about 25 data points out of a typical total of 250 points are processed. This important point about data reduction and focus-of-attention has been discussed before by Gregory (1968) and by the vision and speech research groups, but is not widely understood.
Conclusioa. DENDRAL was an early herald of Al's shift to the knowledge-based paradigm. It demonstrated the point of the primacy of domain-specific knowledge in achieving expert levels of performance. Ils development brought to the surface important problems of knowledge representation, acquisition, and use. It showed that, by and large, the Al tools of the first decade were sufficient to cope with the demands of a complex scientific problem-solving task, or were readily extended to handle unforeseen difficulties. It demonstrated that Al's conceptual and programming tools were capable of producing programs of applications interest, albeit in narrow specialties. Such a demonstration of competence and sufficiency was important for the credibility of the Al field at a critical juncture in its history.
META-DENDRAL: inferring rules of mass spectrometry
The META-DENDRAL program is a case study in automatic acquisition of domain knowledge. It arose out of our
•The ralysie du syetic aming with formula C20H4N.
META-DENDRAL, like DENDRAL, uses the generacion-and-lest framework. The process is organized in three stages: Reinterpret the data and summarize evidence (INTSUM); generate plausible candidates for rules (RULEGEN); test and refine the set of plausible rules (RULE. MOD).
INTSUM: gives every data point is every spectrum an interpretation as a possible, (highly specific) fragmentation. It then summarizes statistically the "weight of evidence" for fragmentations and for atomic configurations that cause these fragmentations. Thus, the job of INTSUM is to translate data to DENDRAL subgraphs and boad-breaks, and to summarize the evidence accordingly.
RULEGEN: conducts a beuristic search of the space of all rules that are legal under the DENDRAL rule syntax and the user-supplied constraints. It searches for plausible rules, i.e., those for which positive evidence exists. A search path is pruded when there is no evidence for rules of the class just generated. The search tree begins with the (single) most general rule (loosely put, "anything" fragments from "aaything'') and proceeds level-by-level toward more detailed specifications of the "anything." The heuristic stopping criterion measures whether a rule being generated has become too specific, in particular whether it is applicable to too few molecules of the input set. Similarly there is a criterion for deciding whether an emerging rule is too general. Thus, the output of RULEGEN is a set of candidate rules for which there is positive evidence.
RULEMOD: tests the candidate rule set using more com
plex criteria, including the presence of negative evidence. It removes redundancies in the candidate rule set; merges rules that are supported by the same evidence; tries further specialization of candidates to remove negative evidence; and tries further generalization that preserves positive evidence.
META-DENDRAL produces rule sets that rival in quality those produced by our collaborating experts. In some tests, META-DENDRAL re-created rule sets that we had previ. ously acquired from our experts during the DENDRAL project. In a more stringent test involving members of a family of complex ringed molecules for which the mass spectral theory had not been completely worked out by chemists, META-DENDRAL discovered rule sets for each subfamily. The rules were judged by experts to be excellent and a paper describing them was recently published in a major chemical journal (Buchanan, Smith, et al, 1976).
In a test of the generality of the approach, a version of the META-DENDRAL program is currently being applied to the discovery of rules for the analysis of nuclear magnetic resonance data.
MYCIN and TEIRESIAS: Medical diagnosis
MYCIN originated in the Ph.D. thesis of E. Shortliffe (now Shortliffe, M.D. as well), in collaboration with the Infectious Disease group at the Stanford Medical School (Shordliffe, 1976). TEIRESLAS, the Ph.D. thesis work of R. Davis, arose from issues and problems indicated by the MYCIN project but generalized by Davis beyond the bounds of medical diagnosis applications (Davis, 1976). Other MYCIN-related theses are in progress.
The MYCIN performance task is diagnosis of blood infections and meningitis infections and the recommendation of drug treatment. MYCIN conducts a consultation (in English) with a physician-user about a patient case, constructing lines-of-reasoning leading to the diagnosis and treatment plan.
The TEIRESIAS knowledge acquisition task can be described as follows:
In the context of a particular consultation, confront the expert with a diagnosis with which he does not agree. Lead him systematically back through the line-of-reasoning that produced the diagnosis to the point at which he indicates the analysis went awry. Interact with the expert to modify offending rules or to acquire new rules. Rerun the consultation to test the solution and gain the expert's concurrence.
THEN: There is suggestive evidence (.4) that the former should be done before the latter.
MYCIN employs a generation-and-test procedure of a familiar sort. The generation of steps in the line-of-reasoning is accomplished by backward chaining of the rules. An IF. side clause is either immediately true or false (as determined by pacient or test data entered by the physician in the consultatioa); or is to be decided by subpoeling. Thus, "test" is interleaved with a generation" and serves to prune out incorrect lines of-reasoning.
Each rule supplied by an expert has associated with it a degree of certainty" representing the expert's confidence in the validity of the rule (a number from 1 to 10). MYCIN uses a particular ad-hoc but simple model of inexact reasoning to cumulate the degrees of certainty of the rules used in an inference chain (Shortline and Buchanan, 1975).
It follows that there way be a number of somewhat true" lines-of-reasoning some indicating one diagnosis, some in
INFECTION-1 is CYSTITIS (Item 1) PSEUDOMONAS-CEPACIA (ORGANISM-5) (Item 2) CITROBACTER-DIVERSUS (ORGANISM-4] (Item 3) E.COLI (ORGANISM-3] INFECTION-2 is UPPER-RESPIRATORY. INFECTION (Item 4) LISTERIA (ORGANISM-2] INFECTION-3 is BACTEREMIA (Item 3) ENTEROCOCCUS (ORGANISM-1) (REC-1) My preferred therapy recommendation is as follows: la order to cover for Items (1 2 3 4 5): Give the following in combination: 1) KANAMYCIN Dose: 750 mg (7.5 mg/kg) 912h IM (or IV)
for 28 days Comments: Modify dose in regal failure 2) PENICILLIN Dose: 2,500,000 units (25000 units/kg)
44h IV for 28 days