Performance Evaluation of the Inference Structure in Expert System

PERFORMANCE EVALUATION OF THE INFERENCE STRUCTURE IN EXPERT SYSTEM

Yang Tao He Zhijun Yu Ruizhao Artificial Intelligence Laboratory Department of Computer Science and Engineering Zhejiang University, Hangzhou, P.R. China

ABSTRACT

There are a variety of factors that affect the performance of an expert system. This paper presents an evaluating method focusing on the complexity, costs and efficiency of inference structure in a rule I knowledge-source based expert system. The performance measuring factors proposed here, when fedback to knowledge engineers, can help them gain a quantitative understanding of reasoning performance of knowledge acquired at the (early) stages of the development life cycle, and enable them to make a numeric comparison and a choice among several structures, or have some refinements. This paper also presents some application examples of this evaluating method and describes an evaluating facility

based on it.

I INTRODUCTION

In the last decade, expert systems and tools for building them have been being developed at a surprisingly rapid rate [Waterman, 1985]. This. makes evaluation of expert system more and more important in . its development process. As pointed out in [Gaschnig, et al., 1983], evaluations pervade the expert system building process and are crucial for improving system design and performance, but the existing techniques for evaluating these systems are few and primitive. Certainly many evaluating methods used in other software systems [Shneiderman, 1980] could be applied to expert systems, but an expert system is unique in the sense that it is a knowledge-based system containing human expertise, and has many distinguishing features such as heuristic searching, reasoning, high level representation , etc .. Therefore, expert system should have its own evaluating techniques.

Gaschnig and others in their paper have presented many general evaluating c~iteria concerning on what, how, and when the evaluation should be .Performed. Our approach , on the other hand, emphasizes the performance of inference structure which means complexity, costs or efficiency in the context of this paper, i.e, the degree of difficulty, effort, or the reasonable time for a system with such an inference structure to attain certain goals. As was proposed in [Newe 11, 1982], there does exist a distinct computer system level, the knowledge level, lying immediately above the program level. Accordingly, our point is · that this evaluation is performed at the knowledge level whereas the others for common software systems are performed at the program level.

J. McDermott, et al.[NcDermott, et al., 1978] have first made an approach and presented several exciting results on the efficiency of certain production system implementations focusing on impacts of conflict set finding strategies. The evaluating method presented here is towards the inference structure itself, as the reasoning network constituted by the intrinsic relati.onships of knowledge has a great influence on the performance of expert system.

The application significance of this evaluating method has been shown in the sense that it helps knowledge engineers

(1) obtain a quantitative measure of inference performance of acquired knowledge. Example 1, f~r instance, gives the evaluating result of an e~pert system.

(2) make a numeric comparison of performance among several structures <normally with the same function in problem solving). For instance, Example 2 analyzes the impacts of a generalization strategy on the inference performance, and Example 3 compares two mechanisms for pattern consistency checking.

(3)choose, refine or reorganize the inference structure without the destruction of the function to enhance the performance of the system, and speed up the reasoning. For instance, Example 2 indicates the effectiveness of this generalization strategy for knowledge refinement, and Example 3 shows that a mechanism for pattern-consistency checking can be improved further .

The development of this model is motivated by our work on expert system development environment [He, 19861, as knowledge acquisition may be performed after or before the selection of supported system building tools. Also in KMIX [Yang, et al., 1986], it is possible to modify the control strategy statically or dynamically. That is why we need to make an estimation on inference structure itself, and have a prior probabilistic perspective of performance in control strategy applied. This will enable us to have an approximate preview of performance at early stages in the development life cycle. ·

II THE NETWORK MODEL OF INFERENCE STRUCTURE

The first stage of our evaluating method · is to abstract the Inference structure from a collection of knowledge piece embodied within an expert system . The following network model of inference structure is adapted from the theory of Petri Network [Peterson, 1981].

An inference structure, R, is defined as a four-tuple, R=<S, T, I, O>, where S=(s,, sa, ... , Stt) is a finite set of states : T=(t,, ta, ... ,t..,) is a finite set of inference transitions, Sll T=9': I is an :'!'input mappipg function defined as I:S-->2 or T-->2 : 0 is an output mappipg funftion defined as O:S-->2T or T-->~ . 2 , 2T are the power sets of S, T respectively.

The semantics of S and T are that S Is the abstract specification of static properties of knowledge; T , on the other hand, their intrinsic Inference relationships. If each state s~in I<t~ > satisfies the property predicate P~·<s&>, then each state s1 In O<t.-> satisfies the property predicate Q~<s 1 ).

An inference structure can be depicted via a graph: a circle represents a state, and a bar represents an inference transition.

An inference structure satisfies the

following properties:

(1> \( i, J (#<ti, I <s; »=#(si, O<ti > > > V i,j (#(ti, O<s1 »=#<sj, I<tt>>> where #(x,y> is the number of element x in y, y is a bag allowing the multiple appearance of an element.

<2> \(I < I<ti>U' A O<t,HIIJ >

2 J < I <ss >~II A O<s; >=11 >

3 J < I <ss >=II A O<st HIIJ >

1. There exists no inference cycle, i.e., for any partial inference path si., tJ, Si~ tsa. · . . si,. ts,. si,.,. , where t;. 1 s in O<st. > fork =1, ... ,n and Sire Is in O<t;~t-1 > for k" 2, .. .,n+1 , Si 1 · si .. ,·

Property 1 validates the correctness of function I and 0; Property 2 warrants the initiallty and termlnallty of reasoning; Property 3 excludes the self-reference of inference transitions. This constraint is used to prevent reasoning loops and is further discussed in Section IV. The latter two statements in Property 2 can be derived directly from Property 3 <the proof is omitted here>.

In the rest of this section, we illustrate an inference structure Rc abstracted from rules 6; 6, 7, 8 and 23, and the related parameters specified in [Van Melle, Chapter 3], which is part of the inference structure in CLOT [Buchanan&Shortliffe, 1984]. The transition is named in accordance with the rule, so is the state to the parameter.

Rc = ( S, T, I , 0 > S = (clindef, family, sigbleed, onset, bldtype) T = (t5, t6, t7, t8, t23) I<clindef> = (t6, t6, t7, t8) O(cl indef> = I! I<family> = B O<family> = (t5) l(sigbleed> = (t23 ) O<slgbleed>=<t6,t6,.t7,t8) I<onset) = 8' O<onset> = ( t6) I < b 1 d type> = g O(bldtype> =(t7,t8,t23) I<tS> = (family, sigbleed) 0(t5) = (clindef) l(t6) = (sigbleed, onset) 0(t6> = (clindef) I <t7> = (sigbleed, ·bldtype) 0(t7> = <clindef) l(t8> = (sigbleed, bldtype) O<t8) = (clindef) I<t23) = (bldtype) O<t23) = (sigbleed)

Figure 1 shows the graphical representation of inference structure Rc.

Ill ESTIMATIONS OF THE PERFORMANCE MEASURING FACTORS

The next stage of our method is to derive the z-transform performance function of the inference structure abstracted.

Generally, the control strategies which can be applied to inference structure are basically data-driven, goal-directed, and Opportunistic searching. During their applications, the efforts of testing, matching, activating, acting, switching, etc. of inference transitions have the greatest influence on the speed of reasoning. Thus in our approach, each transition t in T is designated a performance factor p which is a measure of complexity, costa, or efficiency, whose value and semantics are determined depending on the detail situation confronted and required. Then the performance factor of a partial inference path, &£., tj, ·i. t1. ... a.:,. ti,. s.-.... , is defined as the sum of the performance factor of all transitions in this path, i.e., ~P;,.. As the number of partial inference paths routed with a specific performance factor p may be various from one reasoning ·time to another, N<p> stands for its mean value.

Let

where f<z> is defined as the z­ transform performance function of inference structure which involves the classical z-transform of feedback control theory [Katsuhiko, 1970].

G = {X I xeS ( O(X)·g A l(X)~~ ))

Let r(y,x> denote the partial inference relation between x andy, i.e. y 6 O<x> and x & l(y),

The derivation of performance function the f(Z) z-transform is due to the propagation of the so-called performance accumulator A. The computational process is described as follows.

• <1> For each inference ~ransition t in T, designate n.<ti)= ztto t,:, where P, is the performance factor of ti ; designate performance accumulator A<s>=1 to every states in G; initialize a list called OPEN to be G.
• For any element x in OPEN, if A<x> is known, then x is replaced as I<x> added into OPEN after the application of propagating rules 1 and 3; if A<x> is unknown, but A<r<x,y>> is known for all y in O<x>, then apply propagating rules 2 and 4 to compute A<x>, where the statement 'A<x> is known' means that A<x> has been obtained.
• <3> Repeat step <2> until I<x>=e and A<x> is known for all x in OPEN.

<4> f<z>= L A(X) Uopf*

Property 2 of R stated in Section II holds the condition of G·H and OPEN·e in <4>. Property 3, however, warrants the terminality of computational loop mentioned in <2> and (3).

The propagating rules used above are listed as follows:

Propagating rule 1:

if x is in S and A<x> is known , then

for all y in I<x>, let

A(r(x,y)) = (1-(1-1/b)b )~A(X)

where b= I I <x> I

if x is in T, and for all y in O<x>,

Propagating rule 2: A<r<y,x>> is known, then let

A<x> = ~ A<r<y,x))tt JC<x> '16 OtiC

if x is in T and A<x> is known, then

Propagating rule 3: for all yin I<x>, let

A<r<x,y>> · A<x>

Propagating rule 4: if x is in S, and for all y in O(x)

A<r<y,x>> is known, then let

A<x> = E A<r<y,x)) ~·()!II)

The co·putational propagating rules the probabilistic following shows model of the are derived under consideration. The the deduction process of rule 1.

Supposing that the transitions which can deduce the state x are t, , t&····· tb, i.e. I<x> =<til 1<=i<=b}, then the average probability that ti is used for the derivation of x is

where q is the mean probability of successful activation of a transition, which is approximated as 1/b. In the above statement, the first item denotes that ti is selected first, and the other items denote t is selected after the unsuccessful activations of others in . I<x>. Thus the propagating factor usedbin the rule1 is ~eighted as 1-(11/b) ·

The final evaluating stage compute performance measuring of inference structure R. result of the above computation is to factors Let the be

where N<k> ~ 0 and N(i) = 0 Then let for i>k.

BF = £<1>

DF = f I ( 1 ) If ( 1 )

where f'(1) is the differentiation of f<z> with z=l.

NDF = k

Here breadth factor BF is a measure of total searching breadth to achieve the final goal while reasoning; depth facto~ DF is a measure of the mean performance factor of partial inference path routed while reasoning; NDF, then, is the maximum of the performance factors amongst such paths.

Other measuring factors are derived directly from the four-tuple of inference structure R, i.e., ITI , the total number of inference transitions in R ; lSI, the total number of states in R; IFI, where F = ( x I xeS <I<x>=W A O(x)*g)}.

As an example of the this evaluating method, performance function of in Section I I is application of the z-transform Rc illustrated

thus

ITI = 5 lSI = 5 IFI = 3

BF = 5.47 DF = 1.5 NDF = 2

IV SCOPE AND EXAMPLES OF THE APPLICATION

In this evaluating model, BF is correlated with the effort of reasoning horizontally in matching, selection, confliction resolution, switching, etc., which is the most important factor affecting the reasoning speed of system. The greater BF is , the more effort is needed. DF and NDF, on the other hand, are measure of the vertically-accumulated effort in checking, matching, activation and action etc .. ITI and lSI are often associated with the size of storage. IFI involves the number of primitive data which need to be acquired.

Commonly, it is easily found in most of the knowledge-based expert systems the track of reasoning network often constituted via a set of rules or knowledge ·sources . It is therefore tractable to abstract inference structure from them. Property 3 of an inference structure stated in Section II seems to be a major limitation of the application which excludes the self­ referencing inference transitions In the system. When such a system like NYCIN is confronted, the additional mechanism is needed to avoid reasoning loops, so is the propagation process stated in Section III to prevent the computing loops. The similar problem has also been explored in [He&Yu, 1986], and the solution can be the marking method discussed in [Buchanan&Shortliffe, 1984] or others. Another problem arises in determining the performance factor of transitions and the size of · state, which requires the abstraction is performed under a fixed standard. One of the further direction of this approach is to explore the volume factor of inference structure, which has been investigated as f'(l) in our work, but its application significance remains to be clarified.

It should be noted that although this method is motivated for rule or knowledge-source based reasoning network, Example 3 below, however, is to evaluate two pattern-consistency checkers, which indicates that the inference structure is a kind of the cognitive modeling of human reasoning. The application scope of this method is therefore extended further.

The following examples show the application significance of this method. The performance factor of each transition is assigned as 1, :)(;function A. Example 1 : evaluating a geological expert system GPE

GPE is a geological prospecting system developed at Zhejiang University [He, et al., 1985) with a similar structure to PROSPECTOR. The results of evaluation are listed as follows:

ITI = 86 lSI = 120 IFI = 49 BF = 59.09 DF = 5.70 MDF = 8

B. Example 2 : comparing two kinds of inference structures

Here we apply a kind of generalization strategies used in knowledge learning and refinement [Michalski, et al. 19841 to inference structure Raa , which results in structure R~as depicted in Figure 2. we , only consider BF and DF which have the greatest impacts on the reasoning speed.

BF,.,. = 2n (1- <1-1 /2n )atl.) DF"" = 1

BFz,. = 3/2·n <I- <1-1 /n) > DF,.b = 2

Generally speaking, BF has more impact on the reasoning speed than DF. As the searching breadth of R.~ is about 25X less than that of R2· If this generalization in s: , s~ , ... ,s~ is repeated, it will be diminished by about 43X, 57X, 68X, with respect to this evaluating model. Considering the finally-generalized structure is a full binary tree like inference structure with n=2M~,IFI=2$, then for this structure, BF=<3/4>··2~ , and for RaA, BF=<I-<1-2-""~" >·2 ..... The former is about 1- e/(e-1)·(3/4>"' less than the latter, where e=2.7183.

C. Example 3 refining a patternconsistency checker

In the implementation of OPS5's high performance pattern matching mechanism Rete, it is necessary to make sure that the bound variables in patterns after matching are consistent with the same value. As stated in [Forgy, 19821, Rete uses a linear checker which is depicted in Figure 3<a> via an inference structure with four pattern variables. We think it was adopted because of its convenience in the implementation. The refinement proposed in [Zhang, et al., 1986) is to use binary checking method which is depicted in Figure 3(b) with four pattern variables. The former structure is called Rf, and the latter, Rz. When the number of pattern variables are n, the evaluating results are listed as follows.

For Rf

ITI = 2<n-l) BF :!: 0. 32n· lSI = 2n DF :!: 0.33n IFI = n MDF '"' n

For Rz

ITI = 2(n-l) lSI = 2n IFI = n BF :!: o.63n·log~n DF ~ 0.50·log&n MDF :!: logan +1

BF, DF, and MDF of Rz are only about log.n/n percent as many as those of Rf without the increase of ITI, lSI and IFI. We believe that it is more efficient to use such a refined structure for pattern consistency checking if rules are not allowed to be modified or added dynamically at running time .

V AN EVALUATING FACILITY

EVAL is an evaluating facility that gives the estimation results of evaluation for inference structure during the development of knowledge­ based expert system in terms of the evaluating method described above. EVAL is an interactive system developed at Zhejiang University, and serves as a peripheral device for ·KMIX. KMIX is a general-purpose knowledge base system < i.e . , a tool> which integrates and uniformly specifies the domain and control knowledge. As every knowledge entity in KMIX is specified as a state machine with constraints, it can be divided into a collection of substates, then knowledge sources constitute the inference relationships between those states. EVAL accepts a collection of knowledge entities, and abstracts an inference structure from them, then calculates its performance measure factors.

ACKNOWLEDGMENTS

We thank Wang Shenkang, Gao Ji, Cao Xuejun, Zhangwei, Wang Weining, Tong Xuejun, Zhang Lei, and Tongming at the Artificial Intelligence Laboratory of Zhejiang University, and Hang Jiangchao at the Academic Sinica, for commenting early drafts and providing valuable discussions.