Uncertainty Management in a Distributed Knowledge Based System

1. Introduction

In several applications, a knowledge based system (KBS) may use many knowledge sources which may have different r epresentations. When the knowledge base is small, a single inference engine may work satisfactorily. However, if multiple knowledge sources are used in an expert system, the above architecture may be inappropriate . It may be necessary to associ­ ate a separate engine with each chunk of knowledge. This leads to the idea of a distributed control mechan­ ism in which each chunk of knowledge associated wilh its inference engine represents a Knowledge Source (KS). A KBS using distributed problem solving (DPS) techniques to organize knowledge is called a distri­ buted KBS.

In our research, the paradigm of DPS is used for object recognition [Kha84, KhJB4]. The claim of our work is that the paradigm of DPS is well suited to object recognition using multiple KSs. Various KSs communicate with each other in a team-like fashion . KSs mutually influence each other in the process of disambiguation of their results. A final decision based on the mean value of their Confidence Factor Values (CFVs) and the degree of organi zation in the CFVs is made .

In the process of uncertainty management we also give disbelief a considerable importance. In works like MYCIN [Sho76] a certainty factor is com­ puted by subtracting disbelief value from belief value for a hypothesis and is used in later calculations. This implies that it emphasizes the net ditierence between supporting and opposing bodies of evidence. This net ditierence may mislead by hiding much necessary information. We believe that an opposing evidence for an a! ternative reinforces supporting evi­ dence for other alternatives and vice versa.

This paper addresses the following problems briefly: (i) modifying the belief value or the disbelief value of an individual expert for an alternative based on the disbelief values or belief values, respectively, of the same expert for other alternatives in the process of competition between hypotheses, (ii) computing the CFV of each expert for each alternative based on the modified belief value and the modified disbelief value of the alternative, (iii) updating the CFV of an expert

RameshJain

Dept . of Electrical Engineering and Computer Science University of Michigan, Ann Arbor, Ml 48109

for an alternative based on the CFVs of other experts for the same alternative, a process called cooperation and (iv) combining the CFVs of all the experts to give a final value for each alternative and deciding the best alternative based on the associated CFV. The detail s of our approach are given in [KhJB5].

2. Previous Work

Past research in the field of belief revision has yielded various approaches for modifying and combin­ ing belief values [DoLBO]. AI systems, especially expert systems, adopt numerical methods for reasoning about uncertainty. Most of the approaches developed to combine and propagate certainty measures are based on subjective Bayesian techniques [DHN76 SBF79). Since a plethora of statistical data is r equired in Bayes' theorem, subjective probabilities are used instead of these data in expert systems . Thi s leads to inconsistencies and inaccuracies [Sho76, SBF79 ShB75] . Shafer [Sha76] distinguishes between aleatory probability or theory of chance and epistemic probabil­ ity or theory of belief. Shortlitie [Sho76] used belief functions for combining certainty measures. [GLFB1] applied Dempster's rule for combining disparate bodies of evidence . [Bar81] describes methods of numerical computation of evidence .

3. Competition

In a complex environment a KS may not give a reliable information. In such a situation one may use several KSs, each of which brings a ditierent perspec­ tive to the problem. None of the KSs is perfect. Thus we must combine relevant informations from all KSs Each expert determines (i)the degree of belief and (ii ) the degree of disbelief for each alternative. Since the possible alternatives stored in the KB are finite. the absence of an alternative strengthens the evidence for the presence of other alternatives . Similarly. the pres­ ence of an alternative strengthens the evidence for the absence of other alternatives . The match between the input and KB model leads to belief and disbelief values between 0 and 1. In order to determine the modified degree of belief for an alternative, an expert uses two pieces of evidence: (i) the degree of belief and (ii) the degrees of disbelief of other alternatives.

[Sha76] suggests the use of Bernoulli's rule of combination for combining two bodies of supporting evidence. If E 1 and E 2 are the belief values of two pieces of supporting evidence, then the combined­ belief value Ec is given by the function

However, this function cannot be used as it is because if either E 1 or E 2 is 1, the combined value is always 1 regardless of the other value, and the result is commutative. Thus if a KS is confident, the other is ignored. Another problem underlying the use of the expression (1) is that each piece of supporting evidence is given the same degree of reliance. This problem can be solved by assigning a relative weight w(< 1) to the second source. Then

Since in most applications, the disbelief of other alternatives plays a role which is less significant than the belief value of an alternative itself, the modified form (2) of Bernoulli's rule of combination can be applied to update the belief value . We believe that it is always safe to be conservative (rather than to overes­ timate) while relying on a secondary piece of evidence in the process of increasing the value of the evidence for the presence or absence of an alternative . There­ fore we choose the minimum of disbelief values of all the other a1ternatives in (2) for E 2 giving us a modified belief value (MBV). We determine a MDV of each alternative in a similar fashion.

4. Cooperative Competition

When the opinions of various experts about the same alternative change each other and each expert consequently modifies its own opinion about that alternative, the process is regarded as cooperation.

4.1. Confidence Factor Value

The experts modify the belief and disbelief values of the alternative in the process of competition. The Conndence Factor Value (CFV) of an expert for an alternative is found as follows:

4.2. Cooperation

During the process of cooperation, the CFVs of an alternative obtained by the experts intl.uence each other.

Values of the CFVs were modified using the follow­ ing two mechanisms of cooperation.

1: Mean-Highest: In this case, the highest CFV for the alternative among the experts is found and each expert increases its CFV to t)"le mean of the highest CFV and its own CFV. The motivation behind the scheme is that even if a single expert succeeds to a high extent for an alternative, it helps all the other experts in the disambiguation process. Suppose that before updating Al=0.5 A2=0.9 A3=0. 1. After updating A1= .7 A2=0.9 A3=0.5

This method of updating has the drawback that all the CFVs are increased because of only one value, the highest. This is a very optimistic approach.

2: Increment towards a High Value and Decrement towards a Low Value: In this method the change takes place towards both the high value and the low value. An expert changes the CFV towards the next higher CFV and towards the next lower CFV obtained by other experts. For the above example, the updated values will be

This method of updating CFVs involves a kind of averaging process and is better than the above method because the change in the CFV is intl.uenced by both higher and lower values. However, the new value is the same as taking the average of adjacents except for values at the extreme positions. In other words, its own value does not contribute in determin­ ing its new value, unless it is either the lowest or the highest value. When only two experts are participat­ ing, each of them gets the same updated CFV, which is equal to the mean of the two experts' CFVs . Also, even if the difference between the CFV of an expert and that of the highe r or lower adjacent expert is very high, the change in the CFV occurs in the same way, i .e . the change is equal to the mean of the CFVs of the two experts . This may not be a very practical approach but it leads to the following approach .

4. 3 . Influence and Ego-Altruistic Cooperation

The drawbacks of the method 2 can be eliminated by changing the CFV of an expert by a degree depe'1d­ ing upon the difference between the CFV of the expert and those of the higher and lower adjacent experts The experts with extreme values change only in one direction. This process of confidence smoothing has a very important feature that the change in the CFV for an alternative obtained by the expert is both positive and negative, depending on the values of the higher adjacent and lower adjacent experts .

4.3.1. Notion of Influence

Suppose there are N equally important experts in the decision making procef's. The N experts can be placed on a straight line with respect to their CFVs. In the example below, A1, A2, and A3 are the CFVs and A1> A2> A3. Only adjacent nodes intl.uence each other A1 is intl.uenced by A2, A2 is intl.uenced by Al and A3 and A3 is infiuenced by A2. Since A2 is lower than A1 A1 gets negative influence from A2. Also, since A2 is greater than A3, A2 gets positive influence from A1 and negative influence from A3 . A3 gets positive influence from A2.

The infiuence between nodes is a function of the distanced between them. [The distance is the difference between the CFVs of the experts.] The influence increases with the increase of the distance up to a point, and then decreases with the increase of the distance . The magnitude of the influence(I) between two nodes is given by the following function.

Total influence(I) at a node is the sum of the posi­ tive intl.uence(.t;,) and negative intl.uence(In} at that node.

Thus, updated value of the node =Value of the node + Total intl.uence .

In this approach, the experts are generous to accept intl.uence when their CFVs are closer to each other; otherwise, the experts are egoistic by not changing much when their CFVs differ by a high degree . When the difference in CFVs is more, each indi­ vidual expert tends to rely more on its own confidence factor . This sort of cooperation introduced here is called ego- altruistic co- operation.

5. Decision Making

All the hypotheses with their CFVs corresponding to each expert are still competing for their selection. This section describes the decision making procedure. Our problem may be considered very similar to the problem of multicriteria decision making. We may assume that the CFVs of experts are same as the costs according to different criteria and the decision should be made considering all these costs . It can be shown [KhJ85), however, that none of the existing approaches can be applied here .

5 .1. Decision Making Based on the Mean Value and the Degree of Organization

Suppose there are three experts, exp1, exp2 and exp3, and three alternatives, a, b, c. The CFV for each alternative obtained by the experts are as follows:

exp3 a3 b3 c3

When the mean of the CFVs is taken for an alter­ native, there is a loss of information, and it is impossi­ ble to guess how much an expert is contributing. Intuitively if the disparity between the CFVs of the experts is very high, it is very hard to believe results of any of the experts. As a result, the credibility of the CFV should go down for the alternative. It is therefore suggested that the final CFV for an alternative depends on the two factors: (1) The mean value of the CFVs of all the experts for an alternative , and (2) The degree of organization (the uniformity of results) in CFVs of the experts for an alternative.

The degree of organization in the CFVs of the experts can be found by using the concept of entropy. Since the CFVs of experts for an alternative cannot be considered probability values but could be considered as fuzzy numbers, fuzzy entropy can easily be applied to finding the degree of organization among the vari­ ous experts. If J.J.o 1 , J.J.o 2 , .... 14.,. are the membership values of the members in a fuzzy subset and if we specify

then, the fuzzy entropy is

We found that the final CFV of the experts for an alternative is a linear combination of the mean-value of the CFVs of the experts and the degree of organiza­ tion in the CFVs, which is represented as follows:

FINAL CFV = a. MEAN-VALUE + {3 . DEGREE OF ORGANIZATION

a. and {3 are the co-efficients associated with the 'mean value' of the CFVs and the 'degree of organiza­ tion' in the CFVs re spectively.

6. Conclusion

We proposed a scheme of handling uncertainty in a distributed environment in which there are many KSs, each with a different expertise of problem solving This can be decomposed into 3 steps : (1) dealing with competing hypotheses (2) co-operation and (3) decision-making. We discussed our approach to these steps .