Detecting Ambiguity: An Example in Knowledge Evaluation

Introduction.

Expert systems have depended upon the knowledge base of the collaborating expert for soundness and richness . However, as knowledge bases grow and try to remain current in a changing world, incremental knowledge needs to be added, and one does not have the filter of usage over time that makes an expert's knowledge so generally reliable. One is led to considering means of aiding the expert as he evaluates new information and attempts to update the knowledge base .with this information. Many different types of aids will be useful; we suggest a useful approach and give a specific example within this approach.

There bas been some realization of the importance of aiding knowledge acquisition . TEIRESIAS (see [Davis, 1982]) not only provided convenience tools for rule input but helped with rule inlefirity by use of "rule models." Michalski and Chilauski lMichalski and Chilauski, 1980] investigated inductive learning as a means of automating knowledge acquisition. Recently, Suwa, Scott, and Shortliffe [Suwa, Scott, and Shortliffe, 1982] have directly addressed the problems of verifying "completeness and consistency" in the context of the ONCOCIN system Also see this last paper for a good summary of the need for and present status of knowledge acquisition aids.

Our ge~eral concern is also with the quality of the knowledge m a knowledge base. Our immediate oo~cern is t? aid th_e expe_rt with feedback regarding umntended mteracllons With other rules in a rule­ based system when a new rule is added. In this paper we assume rea~oning with certainty. Extending the approach considered here to weighted evidence reasoning is an obvious next step.

This work is supported in part by the Air Force Office of Scientific Research under grant AFOSR-Bl-0221.

many ambiguous meaningful input vectors (any union of mea ningful vectors of different classes). If we could obtain the minimally ambiguous {min-ambiguous) vectors, we need only display these to the expert; a now-ambiguous ex-atomic meaningful vector will be caught.

We model the inference system here by an "and-or" graph. (See Figure 1.) An input node is a single attribute-value pair. An attribute may have seve ral values. To represent this we partition the nodes into sectio1lS, each section denoting one attribute. Therefore, an input vector can list only one node per section. A pseudovector is any collection of input nodes, perhaps several per attribute. We assume that we can process pseudovectors; the classification of a pseudovector is all classes inferred by activating all nodes of the pseudovector. A rule is depic t e d by a dark node with conjoined input (cut by a curved arc) and one or more outputs. Output nodes are labelled C1, etc.

For simplicity, we limit ourselves to two classes. A Oi.-vector is an input vector of class Ci, for i=1,2. A 12-node (read "one- two node") is an input node in both a C1-vector and a C2-vector. V 12 is the set of all 12-nodes. We eliminate most superposition ambiguous vectors by demanding that the ambiguous vector be composed of V 12 nodes. (This is overly restrictive; we deal with some of this later, and must forego othe r possibilities here.) Figure 2 shows a min­ ambiguous vector from V 12 that is (probably) faulty. Figure 3 shows that min-ambiguous vectors from V 2 nee d not be faulty. Vector <abc> is a C1-vector andla C2-vector, which is probably intended. We simply have <a b >EC1, <c d>EC1, <a c>EC2 and <b d>EC2.

Finding unintended ambiguities.

Our concern is to locate unintended classifications for meaningful input vectors. Besides possibly using unusual input "vectors" (pseudovectors) for input, we need only to augment our inference system to execute "backfl.ooding" in order to use the procedure discussed here. By backftood from Ci we mean to follow all backchaining paths and mark every Ci-vector input node by "i". This is amenable to parallel computation .

We consider the interaction between classes C1 and C2. One would check interactions between every pair of classes in turn . Of course, the backtlooding need be done only once per class rathe r than being repeated for every pair of classes.

We proceed as follows:

Step 1. Backtlood from node Cl. Mark with a "1" all input nodes reached by backtlooding. These are called C1-nodes.

Step 2 . Backtlood from node C2. Mark with a "2" all input nodes reached by backfl.ooding. These are C2-nodes. The 12-nodes are now determined and printed for reviewing by the expert. lt then may be clear by inspection that no meaningful input vector is a subset of the set V 12 of 12-nodes; one could input V 12 as a vector (or pseudovector) to doublecheck that no class is ide ntified with this (pseudo)vector. (See Step 3.)

Step 3. lf v 12 is not obviously void of meaningful input vectors , then input V 12 as a {pseudo)vector. There are three possible outcomes.

• (a) V 12 is neither a C1-vector or a C2-vector.

Go to Step 4.

• (b) V 12 is in one class but not the other .

Go to Step 5.

• {c) V 12 is both a C1-vector and a C2-vector. Go to Step 6.

Step 4 . There is n·o ambiguity between classes C1 and C2.

Step 5. Suppose V 12 is classified. C1 but not C2. V 12 could contain a ~1-~ector which IS par~ ?f a C2-vec""tor not contained w1thm V 1 ; thus the_ rrumrnal C1-vectors within V 12 should be iso1ated so th1s can be checked. This canoe done either by the Critical Set algorithm (see below} or by explicit testing. Space limitation prevents further details . The symmetric case of V 12 classified C2 but not Cl is processed similarly.

Step 6. Since both classes C1 and C2 are reached by V 12 . we need to check for meaningful ambiguous vec(ors within V 12 . If V 12 is small then o':e reasonable way is to input directly the atorruc meaningful vectors within V 12 , checking that they each are uniquely classified. Ir some are not, one can directly print out the inference steps of the ambiguous rule or seek min-ambiguous subvectors. This can be done bottom-up from sin~leton nodes or top-down via the Critical Set algorithm (see below}. The advantage of finding min-ambiguous subvectors is to ease the inspection of the inference steps since one knows the critical input nodes yielding the ambiguity. Finally, if too many meaningful subvectors of V 12 exist to process them directly the Critical Set algorithm may be used .

This ends the procedure description.

We briefly outline the Critical Set algorithm purpose and form and then give a small example.

Space prohibits a full presentation of the Critical Set algorithm, which is presented in [Loveland, 1982). The algorithm is a divide-and-conquer algorithm to solve the following problem. We are given a universe U whose power set is the domain of a monotonic set function f, f binary valued, with f(¢)=0, f(U}=1 and SeT => f(S) ~ f(T}. With f so defined, there exist critical sets B such that f(B}=l but for every proper subset S of B, f(S}=O. Thus, B is a "minimal 1-set" under f. In Step 5 we use this algorithm where the universe U is the set of 12-nodes and f is defined as f(S}=l if S as a pseudovector yields class C1, f(S}=O if S yields no class at all. In Step 6, the universe is the same and f(S)= 1 if S as a pseudovector yields classes C1 and C2, f(S)=O if S is not ambiguously classified. Note that if there are no inhibitor rules then f is monotonic in both cases since the superposition property holds.

The algorithm finds some one critical set, element by element. To find an element it splits successive sets in two until a singleton set is reached, whereupon the isolated element is added to the critical set. To split a pseudovector, divide the values of one attribute in half, add a different half to each set s 1 and s 2 and add all other nodes (from other attributes) to both S 1 and S 2 . To split a legal vector (one node per attribute) simply split the nodes evenly between s 1 and Sz·

The algorithm is very efficient (in a suitable sense} in finding some critical set, but finding many critical sets can occasionally lead to high computational cost. For a full discussion see [Loveland, 1982].

We conclude with a very brief illustration regarding the process of finding unintended ambiguities.

Suppose a,b,c,d,e are attribute-value pairs with {only} a and b representing different values for the same attribute. Suppose vectors <a c d>ECl , <b c>EC2, and <c d e>EC2 are the only meaningful vectors. Then V 12 = !c,dl, learned from backtlooding. <c d> is not of e1tller class. <a c d e> is an ambiguous vector since it is in both classes, for good reason as it is a superset of two distinct and differently classed vectors . It is both meaningful and a min-ambiguous vector. <a b c d > is an ambiguous pseudovector, but not a vector since a and b have the same attribute.

Suppose in addition that <b c d>EC1 is created in error by a new rule . Then V 12 = !b,c,d!. and <b c d> is min-ambiguous as can be found by the Critical Set algorithm applied at Step 6. The algorithm gives a suggested sequence of input pseudovectors to be submitted by the expert (or perhaps automatically} to determine the min-ambiguous vector. The algorithm would have one evaluate input vectors <b c>, <d> , <b d> and <c d> {and we know the <b c d> classification as Step 6 was reached) . Here the expert on his own might have tried <b c> first, then <c d > , and <b d>. and, getting the expected results, realized the same conclusion slightly more efficiently. We stress that we do not want to oversell the Critical Set algorithm; it is the general approach we emphasize. Most important, we stress the value of testing procedures to catch violations of key properties of dynamic inference systems.