Combination and Propagation of Uncertainty with Belief Functions - A Reexamination

COMBINATION AND PROPAGATION OF UNCERTAINTY WITH BELIEF FUNCTIONS

- A REEXAMINATION -

Didier Dubois Henri Prade

Universite Paul Sabatier Laboratoire Langages et Systemes Informatiques 118 route de Narbonne, 31062 TOULOUSE CEDEX - FRANCE

ABSTRACT

The behavior of Dempster's rule of combination in typical situations is examined. Particularly, it is shown that assessing a zero value or a very small value may lead to very different results. Moreover a comparison with a possibility theory-based approach in case of con­ flicting information is provided. The general problem of representing uncertainty with one or several numbers IS addressed. Lastly, the propagation of uncertainty from a fact and "if. .. then ·.· " rule is discussed in the framework

of belief functions .

I - INTRODUCTION

The treatment of uncertain information in knowled­ ge engineering has encountered an increasing interest a­ mong AI researchers in the recent years. Roughly spea­ king, there are at least two basic problems when reaso­ ning with uncertain facts or rules ; namely the com~ma­ tion problem and the propagation problem. The combma­ tion problem refers to the aggregation of uncertain pieces of information issued from different sources dealing with the same matter. The propagation problem deals with the aggregation of the uncertainty concerning the satisfaction of the condition- part of a rule with the uncertainty of the rule itself in order to deduce the uncertainty perva­ ding the conclusion of the rule. Two theoretical frame­ works have recently emerged for discussing these pro­ blems : the Dempster-Shafer theory of evidence [ 4] and Zadeh's possibility theory ; see Prade [ 3 ] for a comparative overview. In the following we examine how Dempster's rule of combination behaves in typical situa­ tions and how the result given by this rule may depend on the assessment of the values of the basic assignment. Then the propagation problem is briefly discussed in Shafer's framework.Comparisons are made with the possibilistic ap­ proach as well as with the treatment of uncertainty in in­ ference systems such as MYCIN. The key question of the representation of the uncertainty of a fact or of a rule by more than one number is discussed throughout the whole paper.

II - COMBINATION PROBLEM

In Shafer's approach an uncertain body of evidence is represented by a so-called basic probability assignment m which is a set-function from the set n of possible ele­

mentary events to the real interval [0, 1] such that

The quantity m(A;) is supposed to represent our part of belief in the occurrence of A exactly. See Garvey et a!. (IJCAI-81, pp 319-325) for an application-oriented presen­ tation. Dempster's rule combines two probability assign­ ments m 1 and m2 pertaining to two sources of informa­ tion, and obtains a new basic probability assignment m satisfying (1), which is defined by VCjJi, C9l, m(C) = ( E m1 (A) .mz<B))j( E m1 (A) .mz(B)) (2) AnB=C AnBjfJ

Moreover this rule is associative.

1) The case of two alternatives

In the following we completely investigate the case where n only contains two known alternatives, each one being regarded as opposite to the other one, i.e. n = {a;~a}. This case is int.eresting in the scope of expert systems be­ cause it is found when general rules enable the same con­ clusion a to be derived with various levels of uncertainty, and as such, is often encountered in applications. In this case a basic probability assignment m is defined by the three numbers m(a), mha), m(rl) which have to satisfy the constraint ( 1 ). Then the degree of belief in the alter­ native a is given by Bel(a) = m(a) while the plausibility of a is computed as Pl(a)=m(a)+m( rl)= 1-Belha), from the ge­ neral formulas [ 4]

where the -overbar denotes the set-complementation. Al­ ternative a may be regarded as probable to a degree which belongs to the interval [Bel(a),Pl(a)]=[m(a),m(a)+ m(rl)] while the probability of the opposite alternat1ve1a lies in the interval [1-m(a)-m(rl), 1-m(a)]. The quantity m(rl) corresponds to the amount of ignorance. Note that in general we need two numbers, m(a) and m(rl), for ex­ pressing the uncertainty pertaining to alternative a. How­ ever if m( n )=0, the uncertainty of a is expressed by a single number, its probability ; when m(a)+m(r1)=.1 or when m(a)=O, the useful information about an alternative lies m its degree of belief or in the degree of belief attached to the opposite alternative, respectively. In that case, the plausibility function is a possibility measure in the sense of Zadeh [ 6 ].

Indeed, when the collection of subsets A of n such that m(A)>O is nested with respect to set inclusion, the belief and plausibility functions defined by (3) are respec­ tively nothing but necessity and possibility measures in Zadeh's sense, see [3]. In the case of two alternatives a and, a, we are in such a situation as soon as m(a)= 0 or mha)=O since obviously {a}cn and ba}cn.

With Beli(a)=mi(a)=si and Pl;(a)=mj(a)+mjW)=ti, where i= 1 ,2, Dempster's rule of combination yields

with d = 1-s1<1-tz)-sz<1-t1) The formulas (4) encompass 4 noticeable particular cases

i) Sj=tj . In this case we have just to combine two ordi­ naryprobability distributions since mi(ri)=O. We get m(a)=(s1.sz) /(1-s1-sz+2s1.sz) ; mba)=1-m(a) ' (5) a formula used by Kayser [2] for combining uncertain pie­ ces of information, also a symmetric sum (Silvert, IEEE Trans. SMC,9, pp 657-659, 1979). When s1 =E: and S2=1-E: (i.e. there is a conflict which is all the more severe as E: is nearer 0 or 1 ), we get 'd £>0, m(a)=mha)= ~. £=0 is forbidden as well as E: = 1.

ii) tJ=tz=l : In this case, both sources of information a­ gree that the plausibility of the alternative a is equal to 1 and thus m1ba)=m2hal=O. Then (4) gives

m<al = s1+sz-s1.sz; m(,a) = 0 (6) We recognize the formula used in MYCIN [ 1] for combi­ ning two non-conflicting pieces of evidence.

iii) tF 1, sz=tz : This case is an hybrid of i and ii. (4) gives m<~l=szl<1-s1(1-szll ; m(,a)=1-m(a) (7)

iv) tJ=l, sz = 0 : In this case the basic probability assign­ ment m 1 expresses that we believe in the completely plausible alternative a with the degree s1 while on the contrary m~expresses a belief in1a (considered as com­ pletely plausible since s2=0) with a degree equal to 1-tz. We have thus a conflict between the two bodies of evi­ dence. Formulas (4) give

and Pl(al=m<al+m<n>= tz /(1-s1<1-tzll

<9>

In these 4 particular cases, the basic probability assignments m1 and m2 are such that either mi(n)=O then mi. is an ordinary probability allocation or mi(a)=O or miba)=O (then Pli is a possibility measure). In cases i) and iii), the result of the combination is an ordinary pro­ bability allocation, and the weight of alternative a is al­ ways reinforced in iii). In case ii), two consistent possibi­ lity measures are combined and yield a possibility measu­ re. Contrastedly, case iv) combines two conflicting possi­ bility measures, and what is obtained is neither a proba­ bility measure nor a possibility measure. In other words, two numbers, distinct from 0 or 1 , are needed here for representing the uncertainty pervading the result of the combination in case of a conflict.

N.B. If we extend the combination formula (6) of two or­ dinary probability distributions (Indeed (6) is nothing but Prob(a)=Prob 1 (a).Probz (a)/(Prob 1 (a).Prob2(a)+Prob 1 ha). Prob2ba)) )from scalar values to interval values of the form [Beli(a),Pii(a)], then this kind of sensitivity analysis yields results which are generally more imprecise those obtained from Dempster's rule of combination in cases ii, iii or iv. For instance in situation iv, we get the whole interval [0, 1] instead of the interval [m(a),PI(a)] defined by (8)-(9).

Since in cases ii and iv we deal with possibility measures, we may then also use a possibilistic rule of combination. For sake of brevity we only consider such a rule when n has two elements a and1a in the following. In this particular case a possibility distribution is a pair of plausibility values (PI(a),Plha)) such that

max<PL<al,Plball = 1 <10> (since m(a)=O or mh a)=O). Then the intersection of two possibility distributions, viewed as fuzzy sets [ 6 ],[ 3 ], is given by (P l(a),P J(,a))=( min(P !1 (a),P 12(a))/ d,

min(PJ1 (1a),P12ha))/d) with

d=max(min(PJ1 (a),PI2(a)),min(PI1 (1 a),PJ2ha))) ( 11) The normalization in (11) maintains constraint (10). Then applying ( 11) to cases ii and iv respectively gives

ii) t J=PlJ (a)=tz=Plz(a)= 1

m(a)= 1-PJ(., a)= 1-min( 1-s 1, 1-s2)=max(s1 ,s2) ( 12) since Si= 1-Pliha) ; moreover mh a)=O.

iv) t1=PIJ(a)=1 ; sz=1-Plzba)=0

m<;al = 0; Pl(al=tz1<1-min<s1,1-tzll <14> The expressions ( 12), ( 13) and ( 14) have a structure stmt­ lar to the one of formulas (6), (8) and (9) respectively. Indeed both the probabilistic sum and the operation maxi-

mum extend the disjunction in multiple-valued logic, whi­ le the product, the operation min and max(O,x+y-1) are the main extensions of the conjunction in this logic. What it is important in ( 13)-( 14) is that the obtained result is of the same nature as the combined items, which was no longer the case with (8)-(9). Particularly, m(,a)iO in (8). Moreover if we replace the min operations in ( 11) by the product, then we recover (6) exactly, while ( 13) and ( 14) remain unchanged. The apparent advantage of (6) is that in case of several pieces of positive evidences (in favor of a) there is a reinforcement of our belief in a, due to the asymptotic behavior of (6) towards 1. However this reinforcement can be only justified with an independence hypothesis which is difficult to check ; thus ( 12) may ap­ pear as a more cautious rule.

Lastly, let us examine the difference of behaviors of (8)-(9) and of ( 13)-( 14) in case of a strong symmetric conflict such as :

s 1 [Bel(a),Pl(a)J=[1+5, 1 + 5 J = [Bel(.,a),Pl(,a)J <15) which is an interval centered around t and which shrinks as s becomes nearer to 1 (strong conflict). Contrastedly ( 13)-( 14) then gives [Bel(a);PI(a)]=[O, 1 ]. At first glance the results look very different, but both of them express that a and-, a are equally believable, plausible, possible. Note that when the conflict is nothing but an absolute contra­ diction (s= 1 ), ( 15) reduces to the value t which is the probabilistic view of total ignorance.

2 - Highly improbable is not impossible

Let us now consider the particular case where we have three mutually exclusive alternatives in n' i.e. n = { a,b,c}, in order to study the sensitivity of (2) to slight modifications of m 1 and m2. First let us consider the si­ tuation discussed by Zadeh (AI Magazine,5(3),pp81-83, 1984)

Note that here m 1 and m2 reduce to ordinary probability distributions on n. When k ·is a small number , there is a strong conflict between the two assignments since the first one regards a as completely impossible and c as al­ most certain, while the second one holds the opposite po­ sition ; both assignments only agree on the point that b is quite improbable. However, whatever the value of k, (2) yields m(a)=O, m(b)= 1, mk)=O due to the norma­ lization effect. Suppose now we modify m 1 and m2 in the following way, e: being a very small amount :

For k=0.1 and e: = 0.0 1 , we obtain m(a)=mk)"'0.32 ; m(b)=0.36. For k=0.1 and €=0.001, we obtain m(a)=mk)"' 0.008 ; m(b),0.84. Clearly, Jim m(a)=lim m(c)=O and E:-+-0 e:-+-0

lim m(b)= 1. Thus we observe that when m 1 (a) and m2(c) e:-+-0

are not strictly zero but remain small in comparison with k, which is itself small in comparison with 1-k-e:, we may obtain results by (2), which are extremely different from the case where m1(a)=m2(c)=O. In this latter case m1 (resp. m2) expresses the complete certainty that a (resp. c) is impossible ; then the alternative b, although quite improbable, remains the only possible alternative. Contras­ tedly when a non-zero, even very small, value is assigned to an alternative, this alternative is not definitely ruled out although highly improbable ; it tacitely expresses that this value may be revised in the light of new information.

Thus assigning a zero value or a very small one may lead Prob(B) E [min(rs+r'(1->l/t+r'( 1-t)}, max(rs+F''( 1-s),rt+i"'( 1-t))] to very different conclusions in some instances. - - - ·- (21)

Note that the acceptance of some unforeseeable When Prob(B I A) is completely unknown, i.e. [r' ,r']=[O, 1] outcome may be better expressed by assessing a small va- (21) reduces to Prob(B) E [rs, 1-s+rs] - (22) Jue E:' to the whole set Q rather than assessing a non- Note that the information pertaining to the uncertainty zero value to each alternative in Q. Indeed it is someti- of the rule "if A, then B" is repre.sented here in terms mes difficult to identifying them. Let of conditional probabilities by the 4 numbers r, F', r', r'. This approach seemingly provides stronger results than the previous one since the lower bound obtained in (22) is greater than the one obtained by (19).

However, the upper bounds in (19) and (22) are of with d=k 2 +2d 1-d. Note that we get results which only different nature, since in ( 19) the upper bound is obtaislightly differ from those obtained with m 1 (a)=m2(c)=€ and ned from lower bounds on Bei(B-+A) and Bei(A), while in m1(Q)=m2(Q)=0, which is satisfactory. (22) the upper bound is computed from lower bounds on Prob(B I A) and Prob(A). However lower bounds in ( 19) and III - PROPAGATION PROBLEM (22) look similar, since in both cases it is a conjunctive In the following some proposals are made in order combination (in different multi-valued logics) of lower to deal with the propagation problem in Shafer's framebounds on Bel( A) and Bei(A-+B) in ( 19), and of lower bounds work. There already exists an interesting attempt (Lu et al. on Prob(A) and Prob(B 1 A) in (22). Upper bounds correspond AAAI-84 ,pp216-221) but which seems in need of justifications. to multi valued implications. Thus the differences between A belief function always satisfies the following ine(19) and (22) are due to different views of the rule (in qualities \j AcQ · Bei(A n B)>Bei(A)+Bei(B)-Bei(AuB) > terms of implication or in terms of conditionning) and to max(O,Bei(A)+Bei(B)-1) - -( 16) the absence of information in (22) regarding the uncertainApplying ( 16) to B=(AuB) n (AuB), we get Bel( B) 2. ty of the rule "if B, then A" or if we prefer "if not A, max(O~el(~uB)+Bei(AuB)-1 )~max(O,Bei(AuB)+Bei(A)-1 ). Thus then not B". Besides from Bel(A-+B)>r and Bei(A)>s we can since A UB is the material implication A-+B, we can prove establish that Bei(~B)<2-(r+s) ; but from this latter inethe validity of quality and Bei(A)>s no non-trivial lower bound on Bei(B) ~=:~~)B) ~ : ( 17) (i.e. no upper bound on PI( B)) can be obtained. Thus we . This pattern can be pro- need the complementary information on Bei(B-+A) for getBei(B) > max{O,r+s-0 ting an upper bound on PJ(B) in ( 19).

ved equivalent to some in (Garvey et al., IJCAI-81, PP Lastly we may think of introducing conditional be319-325) , but is expressed here in terms of the implicalief and plausibility functions for dealing with the propation connective. The lower bound of Bel( B) we have in ( 17) gation problem. This might be done using a conditional bais the same as can be obtained using probabilities instead sic probability assignment (ishizuka et al.,lnf.Sci.,28 (1982) of belief functions. An improved lower bound is obtained 179-206). IV _ CONCLUDING REMARI~ when the belief function is a necessity measure, see (3]. Contrastedly, with probability, which corresponds to the remarkable particular case where plausibility function examination of the behavior of Dempster's rule of comand belief function are equal, an improved lower bound cannot be obtained and this in spite of the additivity axiom. To the modus ponens-like pattern of reasoning (17) very different results. Moreover Dempster's rule applies to corresponds a modus tollens-like pattern of reasoning

PJ(A)

< min(1,1-r'+t)

combining ( 17) and ( 18) we obtain

~=:~~~~ ~ ~'

max(O,r+s-1 )<Bei(B), PJ(B)<min( 1, 1-r'+t)

Thus, if we characterize the uncertainty of the rule "if A, numbers we use for encoding the uncertainty. Particularly then B" by the two numbers Bei(A-+B) and Bei(B-+A), it is we may think of an "if ... then ... " rule in terms of an impossible from a lower bound of the belief in A and from plication or in terms of conditioning. Moreover viewing an upper bound of the plausibility of A to derive lower and upper bounds respectively of the belief in B and the plausibility of B. Bei(A-+B) may be viewed as a degree of sufficiency of having "A true" for deriving "B true", while result. Lastly, the two approaches to propagation which Bei(B-+A) is a degree of necessariness of having "A true" were briefly discussed are not learning processes as Bayefor deriving "B true". Thus the pattern ( 19) provides a tool for using belief functions in deductive schPrnes.

Another approach, partially used in (Ginsberg,AAAI-84, pp 126-129), is to view belief and plausibility degrees as lower and upper bounds of probabilities and to perform a sensitivity analysis on the formula ( 0)

2

[

]

The intended purpose of this paper was a careful bination in typical cases. It appears that assigning an extremely small value rather than a zero value may lead to situations which are probabilistic in nature (m(Q)=O in case of two alternatives) as well as to situations which are possibilistic in nature (m(a)+m(Q)=1 or mha)+m(Q)=1 in case of two alternatives) where a possibilistic rule of combination might be more suitable. Dempster's rule of combina­ tion remains an appealing tool but it should not be used in a blind manner without caution. Besides we discussed two ways of dealing with the propagation problem using belief functions. These two approaches are not equivalent and we have to take care of the intended meaning of the plausibility degrees as upper and lower bounds of probabiJity degrees and then using a sensitivity analysis, or directly dealing with degrees of belief do not lead to the same sian inference is ; the extension of Bayesian inference in the Dempster/Shafer framework is still a topic for further research

1. BudJanan B., Sortliffe E. : Ruled-Ba.sed Exfx=rt Systens, Addiscn-+lesley, 1 984.
2. Kayser, D. see ref. [117] in [3].
3. This method is in the spirit of C.A.B. Smith's view 5 of r4J Slafer G. A Matheratical 'Iheory of Eviden:::e PrincetDn 1976.
4. [ J 3 Prade, H. IEEE Trans. PAMI, 7, 1985, 260-283.
5. lower and upper probabilities rather than_Dempster/Shafer's. r5J Snith, 'c. J. Rl::xj. Statist . Sx:., A-728, 7965: 469-499. '

W1th Prob(A) E [Bei(A),PJ(A)]=£:;,tJ; P_r:ob(A) E [1-t,1-s];

Prob(B I A) E [.!:._,il and Prob(B I A) E [.!:_' ,r'], we get

1. zadeh, L . FUzzy Sets & Systens,1, 7978, 3-28. ----'~----'::.._::____.:,_

Prob(B)=Prob(B I A).Prob(A)+Prob(B I Al.Prob(A)