SEEK2: A Generalized Approach to Automatic Knowledge Base Refinement

1. Metaknowledge in Knowledge Base Refinement

It is clear from the examples in section II.B that a refinement system requires metaknowledge of both the syntax and semantics of the "object" system's language, i.e.. the representation language of the domain knowledge base. For example, Gen, Mfmc, SpecA, and SpecB presuppose a working knowledge of what it is for a rule or a rule-component to be satisfied. Other researchers have shown ways in which metaknowledge can aid in the general knowledge acquisition process [6] and in enhancing an expert system's performance [7]. In this section we describe a metalanguage designed specifically for the refinement task. Using this metalanguage one can define knowledge engineering concepts and heuristics, such as Gen(rule}, as well as domain specific metaknowledge - e.g., the fact that case findings x and y are incompatible - in terms of a set of primitive concepts and operations.

One motivation for a metalanguage was alluded to in section III.B, where we mentioned that SEEK's knowledge base of heuristics and statistics was inaccessible to the user of the system. The ability to easily access and modify this knowledge base is quite desirable for designing and experimenting with refinement concepts. For example, some of the current statistics for SEEK2 are not likely to be as useful with respect to an expert system that employs a scoring scheme for combining confidence factors. Useful variants of these statistics could be defined within the same metalanguage that we have developed for SEEK2.

In general, even within one expert system framework. different styles of knowledge bases are possible; it is likely therefore that different styles of refinement will be needed. For example, some knowledge bases employ a taxonomic ordering of hypotheses. Such an ordering provides knowledge that could be used, together with appropriate control heuristics, to formulate a more efficient version of SEEK2's automatic pilot algorithm. A knowledge base refinement metalanguage will allow for the representation of such control heuristics (see figure IV-1). A refinement metalanguage will allow the expert or knowledge engineer to represent the knowledge that a certain component in a rule should not be altered under any circumstances, or that if a change to component x is made, component y must be changed as well , or that additions to any rule with conclusion C should be drawn from a specified list of components, etc. It will also allow for the definition of special-purpose statistics that may be of use in suggesting plausible rule refinements, e.g., the frequency of occurrence of a certain combination of findings in a specified subset of cases.

2. Defining Statistics in SEEK2's Metalanguage

SEEK2's statistical concepts can be specified in a set­ theoretic metalanguage that employs only a small number of refinement primitives together with some appropriate notions from simple set theory, arithmetic, and logic. Using these primitives it is possible to experiment with variations on SEEK2's statistics and define domain specific statistics as well.

A set-theoretic definition of concepts such as Gen{rule} (see section Il.B) requires refinement pnm1t1ves of the following sorts. Some primitive variables are needed to provide the system or a user with the ability to "access" various "objects" in the domain knowledge base and the data base of cases. For example, rule is a variable whose range is the set of rules in the domain knowledge base, case is a variable whose range is the set of cases in the data base of cases, and d x is a variable whose range is the set of possible final diagnostic conclusions in the knowledge base. In addition some primitive functions are needed to allow one to refer to selected parts or aspects of a rule or a case, e.g. , RuleCF{ rule) is a function whose value is the confidence factor associated with rule, PDX{case) is a function whose value is the expert's conclusion in case ("PDX" stands for "Physician's Diagnosis"), and COX{ case) is a function whose value is the conclusion reached for the current knowledge base in case ("CDX" stands for "Computer's Diagnosis"). As an example of the way in which these primitives can be used, note that using the notions of PDX(case) and CDX(case) one may define a misdiagnosed case as any case for which PDX(case) ~ CDX(case).

Certain special sets of objects are of importance in the knowledge base refinement process. and it is therefore useful to have primitives that refer to them, e.g., Rules-For{dx} is a function whose value is the set of rules that have dx as their conclusion. Finally various primitives that in some way involve semantic properties of rules, or the performance characteristics of the knowledge base as a whole are useful, e.g., Satisfied{rule-component, case} is a predicate that is true iff rule-component is satisfied by the findings in case, and false otherwise, and ModeiCF{dx, case} is a function whose value is the system's confidence factor accorded to d x in case.

SEEK2's refinement knowledge base was designed using the metalanguage we have just outlined [8). Implementation was achieved by incorporating the aforementioned primitives as procedures and functions, and then coding (by hand) high­ level set-theoretic definitions as efficient procedural forms employing these primitives. Currently we are experimenting with a system in which the primitives described above (and others) are available to the user and can be combined to form expressions designating sets, variables, and functions of interest to the user.

V DISCUSSION

SEEK2 currently has ten statistical concepts and nine heuristics for generating refinements. Working in automatic pilot mode on a Rheumatology knowledge base of approximately 140 rules with 5 final diagnostic categories, and using a data base of 121 cases, SEEK2 was able to increase the overall performance of the system from a value of 73% (88 / 121) to a value of 98% (119/ 121). It used approximately 18 minutes of Vax-785 cpu time. The total number of experiments tried was 106. out of which 8 were accepted.···

In evaluating the usefulness of SEEK2's automatic pilot capability it is important to keep in mind that · the expert is still the final judge. Despite the assured gain in performance with respect to the given data base of cases, and the reasonable expectation of performance enhancement with respect to new cases, the expert may agree with only a subset of the total number of refinements suggested by SEEK2···· . The measure of SEEK2's usefulness is not, however, simply how many of its experiments the expert accepts; even rejected experiments have value: they point out areas of the knowledge base that need to be examined if enhanced performance is to be achieved.

Validity and consistency are important goals in developing expert systems. Yet the design of these systems is often lacking in a coherent formal approach for achieving these goals. The approach to knowledge base refinement described here can lead to a more solid foundation for designing and validating expert system knowledge bases.

VI ACKNOWLEDGMENTS

We would like to thank Casimir Kulikowski for his helpful suggestions concerning this work, and Kevin Kern for programming assistance.

···The system has not yet been tested on alternative knowledge bases.

****The incorporation of domain-specific metaknowledge in SEEK2 might enable the system itself to sometimes reject a refinement that in some way violates the expert's understanding of the domain, even though it may improve performance.