A Tool for Building Second Generation Expert Systems

Xuejun Tong, Zhijun He and Ruizao Yu

Artificial Intelligence Laboratory Computer Science and Engineering Depar tment Zhejiang Univer sity, Hangzhou, P.R.China

ABSTRACTS

The demand for second generation expert systems will soon bring forward the demand for tools to build them. ZDEST-2 is built to test the authors ' ideas on what characteristics such tools should have and how to reflect them consistently within a system. New concepts such as three-level control scheme and 3-D explanation are introduced;multiple representation methods and inference engines are offered and integrated. The most distinguished charac­ teristics of ZDEST- 2 are: (1) It is a gen­ eral tool suitable for building var i ous domain oriented expert systems<ESsl. (2) The ESs built by it can fully reflect the nature of applicated domains. (3) Well­ developed environment is provided for the building and using of ESs. (4) A user friendly interface is emphasized, explana­ tions can be tailored to the elaboration needed, and, external procedure accesses are allowed. This paper gives a quite detailed description about how ZDEST-2 gains such characteristics.

I INTRODUCTION

During the past decade, ES technology has been developing rapidly, attracting a great number of resear.chers and coopera­ tions. But still, it is felt that the first generation ESs neglect the impor­ tance of simulating experts' problem­ solving trains and the importance of meet­ ing the needs of terminal users. Thus begins the research on second generation ES(SGESl. To conform to this tendency, the problem challenging tool designers is how to build tools which are able to assist the procedure of building and using SGESs. Several important characteristics a SGES will have are discussed in (1]. Now as to the tools, what are their major charac­ teristics? First of all, in order to have some background knowledge, let us examine what prior tools lack. Prior tools pay little attention to how to reflect the nature of problem domain. Many tools are derived from domain- oriented ESs, it is inevitable that they carry with them more or less features peculiar to application domain. Other tools such as HEARSAY-m (6] and AGE[7J, tend to be general aids, sacrifice efficiency to gain generality, so they are impractical to use. Prior tools lack the intention to organize separate modules into a closely related tool set to provide life long service for ESs . Domain experts try hard to find tools providing good assistance to the use of ESs, only to find those tools are not suitable for buildi ng their own ESs. So we feel, future tools should have the follow~ ing characteristics: firstly, they should have great flexibility in combining vari­ ous different inference engines; secondly, ESs built by them should fully reflect the nature of application domain, the expert 's reasoning trains and the ways expert giving explanation; thirdly,they should be able to record rich-structured bookkeeping information for knowledge in order to sup­ port the maintaining and updating of SGESs and to provide user friendly interface; and forthly, as the SGES may be a sort of distributed problem-solving system, the tools should have the potentiality to build distr i buted systems. ZDEST-2 is built to explore the potentiality of hav­ ing these characteristics withi.n a system, in order to offer SGESs life long service . It results in a fair success. It has been used to build four ESs from different domains: one for detecting blood defects (ZCLOTl; one for repairing superheterodyne transistor radios <ZRADl; one for pros­ pecting mineral resources and estimating the quantity (ZGPEl; and one for making up the best cotton composition for cotton mills ( ZCOTl.

li OVERVIEW OF ZDEST-2

According to the classification of [2], tools can be divided into several catalogs, and ZDEST-2 can be seen as a general system aid with well-developed supporting facilities. ZDEST-2 has two distinct functions. One is talking with experts interactively to extract domain knowledge and domain problem-solving procedures so as to build domain oriented ESs. This process is called ES building process. The other one is providing various supporting facilities including explanation based on 3-D truth maintenance structure and meta-knowledge based knowledge base management to assist the using and maintaining of ESs.

During ES building process, by talking with domain experts interactively, ZDEST-2 gains knowledge about the conceptual structure of the domain, and builds upon that ES components such as task, meta-ks and body-ks used by the ES to be built.

Task, meta-ks<MKS), body-ks(BKS) and inference engine are four main ES com­ ponent types, called ES items. There is a comment frame associated with each item, which records control information and bookkeeping information relevant to the item. Information in the comment frames is useful in scheduling the item or explain­ ing the item's behavior. The comment frame is filled in under the guidance of the domain expert, and so the expert has the power of deciding the actual internal form of the ES under the same three-level control architecture.

In order to gain the problem-solving efficiency and the capabili.ty of charac­ terizing application domain and to be generally applicable, we proposed the three-level control scheme.It is a general control architecture composed of planning, sketchy reasoning and concrete reasoning. It is a problem-solving architecture of ES suitable for various application domains. A blackboard acts as the general data communication area, where ES items record and look for needed data.

ZDEST-2 is currently running on VAX11/785 and Honeywell DPSS/51, using FRANZ LISP and LISP/66 respectively. Its source code is about 9000 lines long (not includ­ ing the comment lines). ESs built by it can be transferred to run on IBM PC.

III ES BUILDING PROCESS

Fig.l (the single-line arrow indicate& data flow, while the double-line arrow indicates control flow).At any time during ES building process, ZDEST-2 is always in one of the following four ES building stages: (!)conceptual structure descrip­ tion, (2) ES component description, (3) knowledge acquisition, (4) ES refinement and assembly. The semantic and syntactic examination is performed from beginning to end for the purpose of eliminating errors occurred in ES building process.

A. Conceptual Structure Description

Conceptual structure is organized around concepts and context types, indi­ cating the property inheritance between context types. Concepts stand for basic objects of the application domain, they are used to define problems, rules, goals and messages mentioned in ES. Context types describe the region within which certain concepts are applicable. Context types themselves can be regarded as con­ cepts which are applicable within certain regions, in other words, they .are higher level concepts. For any application domain, the organization of conceptual structure may not be unique, it is influenced by the way experts intend to organize ES components.

The properties of context types and concepts are recorded in the property list associated with them.Through the dialogue, expert enters the properties of each context type and concept.

Part of the conceptual structure of ZRAD is shown in Fig.2, where IF (inter­ mediate frequency>, HF (high fr.equency) and LFA <low frequency amplifier) are context types, that is, they are higher level concepts. The concepts which can be applied in LFA are TR4VC (the voltage of TR4 collector>,ITR(the input transformer), OTR (the output transformer) and so on.

B. ES Component Description

Tasks, MKSs, BKSs and inference en­ gines are ES components, they are combined to form an executable ES. The specifica­ tion of them is done by fillinq in the comment frames associated with them and acquiring relevant knowledge pieces used by them. The comment frames have slots for specifying the precondition of task execution, relation meta rules used by inference engine used rules used by KS, and between tasks, the MKS, the peculiar by KS, the domain so on (Table 1, 2).

Table 1. Comment frame of a BKS of ZCLOT

name: bcu knowledge form: production rules inference engine: goal-directed-inf context types: patient concepts included: finaldef ···· rules: rule-0, rule-7, rule-9 father ks: mcu

Table 2. Comment frame of an inf. engine

name: goal-d.1rected.-1nf

glob parameters: (cntxt ddata qua-numb)

cfcombine: cf-combine

cfadjust: nil

usedby: (bcu>

description: This is a goal-directed in­ ference engine, MYCIN like certainty measure is used.

C. Knowledge Acquisition

During the ES component description period, the related meta-knowledge and domain knowledge are acquired when mentioned. For the convenience of representation, three kinds of representa­ tion methods are offered by ZDEST-2.

l. Production Rules

Production rules can be expressed simple expression lanquage (SELl restricted natural lanquage <RNL>. in and

a. SEL-- SEL uses concepts and their values as operands, predicates as opera­ tors to express loqical ' relation between concepts and values. Lisp expressions can be inserted in any place within a SEL expression in case some operations exceed the representation power of SEL. A rule of ZRAD expressed in SEL is show as follows:

IF esc=normal 40 ma <= ctfc < 70 ma type =& (on, off} THEN errmsg=cl7t (printl "Cl7 is through")

b. RNL-- With the help of predicate description patterns, value function description patterns, acquired properties of concepts and a powerful pattern matcher, the production rules expressed in RNL can be translated without much difficulty.RNL can be extended dynamically by adding new predicate and value function description patterns.

2. Semantic Networks Semantic network representation is

also supported by ZDEST-2, a linear parti ­ tioned network representation language is provided. The implication relation is represented as a "space"[lOl, so in the logical level, the function of implication space is equivalent to that of production rule. This enables the easy transformation between them, makes it possible to allow the co-existence of knowledge represented in different methods. But until now, ZDEST-2 has merely allowed different KSs to use different knowledge representation methods, while knowledge within a particu­ lar KS is encoded in the same form.

3. Procedure Representation

ZDEST-2 also allows the knowledge to be represented in proced.ures written in FRANZ LISP, FORTRAN, PASCAL or C. External access ability is very important to large problem solving activities. By this powerful characteristic, large systems containing tasks such as data processing, table drawing and others can also be built by ZDEST-2.

D. ES Refinement and Assembly

Information and knowledge acquired during conceptual structure description, ES component description and knowledge acquisition are stored in a data file. The data file describes the static organiza­ tion of an ES loosely. Fig.3 shows the static organization of an example data file.

Because ZDEST-2 is a large tool set, it is composed of a great number of modules. For ES to achieve high perfor­ mance efficiency, all of the redundant modules and data must be discarded . After that, the newly built system is assembled and compiled into an executable ES. The question answering module and knowledge base management module accompany the ES, in order to support the possible future debugging, updating and maintaining.

Since each KS can select its pwn inference eng1ne and representation method by choice, systems built by ZDEST-2 can be regarded as a combination of a number of the ES cores(by ES core we mean the key components of an ES, that is, knowledge and inference engine), while different cores are different in representation or inference method or others. This distinguished characteristic strengthens the problem-solving capability of ESs, attains great flexibility for ZDEST-2 to build different types of ESs, and also enables the reflection of domain nature.

I

IV THREE LEVEL CONTROL ARCHITECTURE

ESs built by ZDEST-2 use three level control scheme, which consists of planning period, sketchy reasoning period and concrete reasoning period, as the problem­ solving architecture.

Planning happens on task level. Through dynamic planning, the execution sequence of tasks is dynamically ordered. During planning period, the scheduler controls the execution,suspension of tasks according to the current control informa­ tion in the blackboard and administers the interaction and message passing between tasks. This process is similar to the scheduling of control KSs and domain KSs by scheduler in blackboard control archi­ tecture[3J. In blackboard control archi­ tecture, the scheduler activates control KSs to determine the importance and neces­ sity of executing certain domain KSs, and then selects one to execute according to the current problem-solving strategy. Such architecture has eight prominent charac­ teristics, but it also has several severe disadvantages: firstly, the time used in scheduling is in proportion to the number of both control KSs and domain KSs; secondly, KSs are relatively independent, isolated components, the execution order of KSs is purely opportunistic. But in ap­ plication domain, expert's problem-solving procedure is often guided by implicit trains, the relative order of some KSs is determinable. So the ES component "task" is introduced to administer several closely related KSs cooperating to solve certain sub-problem, whose order can be determined when the task runs. The comment frames associated with tasks record a set of production rules used to describe the precondition of task execution or relation between tasks, and a set of production rules to describe the relatively fixed dependency of MKSs administered by the tasks. The function of planning period is to plan dynamically the task execution order in order to reflect the major problem solving steps taking by experts during problem solving.

Each task controls several MKSs. When a task is chosen to run, the sketchy reasoning period starts. The comment frame associated with MKS records the meta rules and meta inference engine. The 'role of MKS is to make preliminary assessment of the sub-problem based on the clues alrP.ady occurred on blackboard in order to choose the best suited lower level KSs to run. For instance, it can determine useable rules used by lower level KSs, modify the inference engines used by lower level KSs and enable the execution of lower level KSs. The idea of separating the sketchy reasoning process from the whole problem­ solving process is also initiated by the goal of pursuing the similarity of problem-solving between computer and domain experts, because many experts have the intuition of favoring one inference path while discarding others. The "intui­ tion" probably is the result of tradeoff consideration of known clues. The meta knowledge plays various roles. One of the important roles is that it can be used to modify dynamically the comment frames of lower level KSs. Because of this role, when the inference engines used by lower level KSs are so simple that the inference process is nearly determined only by meta rules, the execution of MKS enables the problem-solving process of lower level KSs to be self adaptive to the problem status. We believe the self-adaptive of inference is also an important feature of SGESs.

Concrete reasoning period is responsi­ ble for actually solving sub-problems. Since after sketchy reasoning period, everything is tailored to the specific needs, so the concrete reasoning period is quite efficient, especially when the meta knowledge used by MKS is excellent.

The distribution of problem-solving activities at different control level in different time intervals is shown as follows:

where, at time interval:

• (llChoose a task to fire, call it Tl.
• (2)0rder the MKSs administered by Tl as Tl-Hl, Tl-H2, etc.
• (3)Begin the sketchy reasoning of Tl-Hl.
• (4lChoose a BKS to run, call it Tl-Hl-Bl.
• (5)Preview the rules used by Tl-Hl-Bl.
• (6)Adjust inference engine to suit the current state of the blackboard if necessary.
• <?>Execute Tl-Hl-Bl.
• (B)Repeat (4) to (8), until the sub-problem is solved.
• (9)Begin the sketchy reasoning of Tl-H2.
• (lOlRepeat (1) to (3), choose another

task to fire, until the whole problem is solved.

It is not difficult to find out that the three-level control architecture is a qeneral, efficient problem-solvinq archi­ tecture. For example, the most often used inference enqines: qoal-directed and data-directed, can be implemented on the concrete reasoninq level; and the more complex mixed-chaininq inference enqine can be implemented on the sketchy reason­ inq level. Besides, the symptom based inference enqine[4l can be implemented on the planninq level. The three level control architecture is an amelioration to the blackboard control architecture. It is more suited to be used in practical systems. Further more, because of the introduction of comment frames, the KSs' structure is loosely orqanized.Throuqh the fill-in of comment frames, domain experts are free to choose whatever suited infer­ ence enqines to reflect the exact nature of problem solvinq.

Because the three level control archi­ tecture is a framework capable of charac­ terizinq the qeneral problem solvinq activities of application domain, and because ZDEST-2 provides qreat flexibility for experts in buildinq an actual system, so ZDEST-2 is a tool worthwhile to use for almost any domain.

V THE SUPPORTING FACILITIES OFFERED

A. Question Answerinq

The SGES must be able to qive ap­ propriate system performance explanations based on user's domain familiarity. ZDEST-2 has made qreat efforts to provide ESs with a user friendly interface. The ES built by ZDEST-2 encouraqes user to ask "HOH", "HHY" questions and to demand help from the system durinq problem-solvinq process, and also encouraqes user to use question answerinq module provided by ZDEST-2 to examine and to understand the evolution of problem-solvinq process. Durinq the planninq, sketchy reasoninq and concrete reasoninq period, the control transfer information is automatically recorded in a truth maintenance structure (THS). The THS is of 3-D structur~ indicatinq control transfer locus between tasks, MKSs and BKSs <Fiq.4). Accordinq to

user's familiarity, answered at T, M or the question can be B orientation. The locus in any horizontal plane indicates the control transfer within the same task, while the cross plane locus shows control transfer between different tasks. The T level explanation is based on the role of production rules stored in the task's comment frame, it qives the hiqhest level control transfer information. The M level explanation is based on the known clues in the blackboard and the activation record of the production rules stored in the task's comment frame, and it qives the explanation of meta rules' function, indi­ catinq the causality concluded by the sketchy reasoninq. The B level explanation is based on the activity of each rule, qivinq the detailed domain rule level explanation. Althouqh the rationale of explanation is based on rule level expla­ nation, the method used is similar to that of [41, but because the explanation could be qiven at three level, the needs of users with different backqround can be satisfied. The question types which can be answered by question answerinq module include the followinq ones:

• .trace the performance at three level.
• .at T, M or B level investigate the success or fail of rules caused by certain blackboard information .
• .interroqate the conclusions reached at M or B level.
• .investiqate how certain conclusions are reached or not reached.

Fig.4 shows the control transfer from Sl: task Tl, MKS Ml, BKS Bl to 52: task Tl, MKS Ml, BKS B2. It is control transfer within same task and MKS. PTl, PMl, PBl and PB2 point to the sub- explanation structure associated with Tl, Ml, Bl and B2 in place Sl, 52 respectively.

B. Knowledqe Base Manaqement

ZDEST-2 pays lots attention to knowledqe base manaqement in order to give user a well-developed environment of main­ taining ESs. We use meta-knowledge about the semantics of predicates and value functions and meta-knowledge about the loqical calculus to check statically the consistency between rules. A knowledge base inquiry languaqe is also provided to assist user browsinq through the knowledge base.

V1 CONCLUSIONS

From the start of ZDEST-2 project, qreat emphases have been laid on the four characteristics mentioned above. Now we can say, ZDEST-2 reflects them quite well. The three level control architecture focuses on opportunistic inference at the planning level, focuses on meta level rea­ soninq at the sketchy reasoning level and focuses on solution based inference at the concrete reasoning level. By proper combination and orqanization, almost all kinds of application domain can be properly characterized by such three level control architecture. Further more, s7stems built by ZDEST-2 can reflect the domain nature as much as .possible by allowinq expert to use particular inference enqine and par­ ticular representation method to charac­ terize the problem-solvinq methods pecu­ liar to certain portions of the domain. The maintenance of built systems is also taken cared of by ZDEST-2 since question answerinq module and knowledqe base manaqement module are provided.

Compared with tools built in last several years, a number of these tools' desiqners recoqnized the importance of providinq two or three kinds of represen­ tation lanquaqe to support different ways of representinq domain knowledqe [2,91. A number of them also recognized the useful­ ness of makinq various typical inference enqines available for expert's choice [2,81, but few of them explored the possi­ bility of inteqratinq multiple representa­ tion methods and inference enqines within an ES. Mostly because of this distinct difference, we believe ZDEST-2 is a second qeneration tool. On the other hand, tools which are qeneral enouqh to be applied to a qroup of different domains, such as HEARSAY-_, AGE, seldom provide well­ developed environment for the buildinq and maintaininq of ES toqether. ZDEST-2 can provide 3-D explanation for ESs reqardless of whatever inference enqines are used as far as the needed control transfer infor­ mation is properly recorded (this can be easily done, for the inference enqines supplied by ZDEST-2 have already had such function, if the inference enqines are supplied by domain experts, then it is necessary to embed codes to fill in con­ trol transfer information at relevant points of inference) .·

Several experiments have been made to test the abilities of ZDEST-2. Firstly, we chose EMYCIN system. The CLOT system built by EMYCINC6l, was re-built by ZDEST-2, called ZCLOT, ZCLOT acts almost exactly the same as CLOT at concrete reasoninq level. The buildinq and debuqqinq of ZCLOT takes merely about three hours. Secondly, we chose the KAS system, since KAS was derived from PROSPECTOR and we have already built an ES to prospect mineral resources, called GPE, which is similar to PROSPECTOR in structure and performance. GPE was aqain re-built by ZDEST-2, called ZGPE. ZGPE takes only one week's time to built. It uses semantic network and procedure as its major representation methods. It has 128 con­ cepts, 140 knowledqe pieces, 11 specific procedures and several context types. Usu­ ally it takes about two minutes . for ZGPE to qet a positive conclusion but less than one minute to qet a neqative result. So, it is certain that ZDEST-2 is more power­ ful than EMYCIN and KAS. Thirdly, we tried an ES for multi-factor planninq. This is an ES used to find the best composition of different kinds of cotton for cotton mills. In this system, about 22 factors of different importance convoluted make the problem-solvinq difficult. Much work is done on the planninq level and the results are satisfactory. Fourthly, we tried mixed-chaininq inference by buildinq an trouble shootinq system for radio repair. All of these systems are accomplished successfully.