A Synthetic View of Approximate Reasoning Techniques

Henri PRADE

Laboratoire "Langages et Systemes Informatiques" Universite Paul Sabatier, I 18 route de Narbonne 31062 TOULOUSE CEDEX FRANCE

Abstract: This paper presents a review of different approximate reasoning techniques which have been pro­ posed for dealing with uncertain or imprecise know­ ledge ,especially in expert systems based on produc­ tion rule methodology . Theoretical approaches such as Bayesian inference,Shafer's belief theory or Za­ deh's possibility theory as well as more empirical proposals such as the ones used in MYCIN or in PROS­ PECTOR, are considered. The presentation is focused on two basic inference schemes : the deductive infe­ rence and the combination of several uncertain or im­ precise evidences relative to a same matter. Several kinds of uncertainty are taken into account in the models which are described in the paper : different degrees of certainty or of truth may be associated with the observed or produced facts or with the "if ·.. then ··. " rules; moreover the statements of facts or of rules may be imprecise or fuzzy and the values of the degrees of certainty which are used may be only approximately known. An extensive bibliography, to which it is referred in the text, is appended.

Key words: uncertainty; imprecision; inference; com­ bination of evidence; belief function; possibility; necessity; degree of truth; fuzzy set; production systems; expert systems.

!-Introduction: The pieces of information with which we have to deal in decision or reasoning processes, may be uncertain, imprecise or even vague, incomple­ te, mutually inconsistent, and time-varying. Thus,so­ called approximate,inexact, plausible reasoning me­ thods are strongly needed in knowledge engineering. Inference procedures with uncertainty are becomingmo­ re important in rule-based expert systems since the knowledge given by human experts is often uncertain or imprecisely stated.

For a long time, the Bayesian model had been the only numerical approach to inference with uncertainty,sin­ ce no quantification was introduced in the patterns of plausible reasoning analyzed by Polya[33]. Several mathematical models of uncertainty, which departfrom the usual probability approach, have been recently proposed, particularly Shafer's belief theory[4o]and Zadeh's possibility theory [531. In the same time, many researchers in Artificial Intelligence have felt a need for alternatives of the standard Bayesian ap­ proach (see[45] for a discussion) and have proposed and used (generally with success) more empirical mo­ dels, particularly in expert systems such as MYCitl [41], PROSPECTOR l11], CASNET [48], SPERIL [20],(see also [ 27], [13 ],~ 27 ],[ 39 ]).

In the following, we try to present a synthetic view of most of these proposals within the compass of a small number of pages. The paper is organized in furee main parts. The first part is devoted to an unified presentation of the different mathematical approaches of uncertainty, including Shafer's belief theory, Za­ deh's possibility and fuzzy set theories and probabi­ lity theory. Then, the deductive inference schemewith various kinds of uncertainty is dealt with in the fra­ mework of probability and/or possibility theory. Last­ ly, the combination of several uncertain or imprecise evidences, relative to a same matter and possibly par­ tially inconsistent, is discussed using Dempster-·Sha­ fer's approach.

II-Different mathematical approaches of uncertainty embedded in a common framework

a)- representaing an uncertain body of evidence and measuring the uncerta inty of events :

We start with an elementary presentation of Shafer's belief theory [ 40] (see also[15] or[ 3] for an A.I.­ oriented introduction),whose probability theory and Zadeh's possibility theory are particular cases,as it will be seen later.

Let U be the exhaustive set of the possible (and mu­ tually exclusive) values of a quantity X. X may be a numerical quantity or just a "parameter" tha t takes non-numerical values. U will be suppose~ finite for simplicity, except if the contrary is explicitly sta­ ted. U is sometimes ca lled the universe of discourse or the frame of discernement. In-the-following~ we­ are interested In-propositions of the form "the true value of X is in A",or more briefly "X is in A",where A.U. Let ~(U) denote the set of subsets of U; ~(U) may be viewed as the set of the events,eachevent corresponding to a proposition.

Let m be a set function from l(U) to[ 0 , 1] ,such that

m is called a basic probability assignment and is sup­ posed to represent-an uncertain- body-of evidence re­ garding the value of some quantity X. A certain body of evidence would be represented by a statement 'X is in F, exactly and certainly' (i.e.m(F)=I and VA# F, m(A)=O); note that a certain body of evidence does not necessarily lead to a precise specification of the value of X(the value of X would be kno'm with precision only ifF is a singleton of U). When the body of evi­ dence is uncertain, the subset F is randomnized (in­ deed mathematically speaking,(I)expresses that m re­ presents a random set). m is a probability distribu­ tion on~(U),not onU. Thus,m(A) is not the probabili­ ty of the proposition 1 X is in A' ingeneral. The sub­ sets A s;u such that m(A))O are called the focal ele­ ments,they correspond to the possible conte~t~-;f-the

~ncertain evidence under consideration.

From m a so-called belief (or credibility) function cr,from1'(u) to[ 0 ,1J,-is defined-as--------

Thus the credibility of the propos~t~on "X is in A"is computed from the values of m a ttached to the proposi­ tions 'X is in B' which entail 'X is in A'.

By duality a so-called plausibility function Pl,from ~ (U) to[ 0,1], is defined-as, the overbar denoting the

Thus the pl ausib il ity of the proposition 'X is in A' is computed from the values of m attached t o the pro­ posi tions which do not ent ai l "X is not in A";the plausibility of an event corresponds to the non-credi­ bility of the opposite event,which is natural . It can be checked that

. Cr(C/J)=O; pl (C/J)=O; Cr(U)=l; Pl(U)=l (S)

. J/Ac;U, Cr(A) +Cr(A) S1 ,Pl(A)+Pl(A) d

( 8 )

All these properties are in agreement with the intui­ tive meaning gener ally attached t o the concepts of plausibili t y and credibility. For i ns t ance (8) shows tha t two opposi t e events may seen both plausible whi­ l e it is allowed to find an event not credible and the opposite event too. In this framework the situation of t o t a l ignorance can be easily modelled, while it is not possible t o deal with ignorance in an effect ive manner in the framework of probability theory. With this apporach it is possible to distinguish between the lack of belief and msbelief since Cr(A)=O does no t enta ils Cr(A)=l = Pl(A)=O, while Cr(A)=I entails Cr(A) = 0.

This model does not seem in disagreement with the m­ sic ideas used by Co lby and Smith[ S] in their empiri­ ca l but quantitative approach of belief.

Two important particular cases of credibility and sibility functions are go t for specia l struc tures the set of focal e l ements. plru-

- When the only possible focal elements are singletons of U(i.e. m(A)=O as soon as A has more than one ele­ ment),we c learly recover a probability measure

P=Cr=Pl and (3) reduces to P(A)+P(A)=l. Thus probabi­ lity corresponds, in terms ·af m, to an evidence which is precise but "inconsistent"(the focal elements are mutually exclusive since they are singletons).

u E of From a practical point of view,it is important tha t probabili t y , possibility and necessity measures can be directly expressed in terms of a distribu­ tion which require only iUI-1 numerical values t o be de­ fined, while 2IUI_2 values ar e needed to define a function m_.

- When the set of focal elements can be ordered in a nested sequence A 1 f A 2 £ . . . <;.An, it can be shown (see

for instance[40] tha t

't/Ag U, VB r;U,Cr(AnB)=in(Cr(A) ,Cr(B)) (9)

VA~U, VB s;U,Pl(AuB)=ax(Pl(A) ,Pl(B))

(10)

cation of the value of the quantity X under conside­ ration(at most one focal element is a singleton). (S),(9) and (IO)yield as immediate consequences

(14)expresses that an event must be completely possi­ ble before be ing somewha t necessary . An event whose probality or necessity is equa l t o I can be regarded as cer t ain, while it is not the case for an event who­ se possibility is I since the opposite event may also have a poss ibility equal t o I.

An important consequence of (10) is the fact tha t a possibility measure(and then the dual necessi t y mea­ sure) can be expressed in terms of a so-cal led possi­ bility distribution'l:;', from U t o[ 0,1], defined by V UEU, ~(u) = IT ({u}) and then

The extension of (IS) and (16) to non-finite sets such that Rn, is obvious. Since IT (U) = I,~ is normalized in the sense tha t maxX(u)=I. When X is the-cl1aracte-- uEU

ristic function of a crisp subset Q of U{then m(Q)=l and m(A)=O if A#Q), (IS) and (16) r educe respectively t o IT (A)={ I if AnQ#C/J and N(A)={ I if A~Q h' h h 0 otherwise 0 otherwi se ' w ~c sows

the links between possibili t y and intersection and be t­ ween necessi t y and inclusion. When eva luating the possi ­ bility of an event, only the most favorable case is t a­ ken into account as it is shown by (IS), which departs from probability where the evaluation is cumulative (P(A) = ~ P({u})).

N.B.: For a discussion of the axiomatics of plausibili­ ~credibility functions, possibility, probability and necessity measures in a common framework, see Dubois Prade[9]; see also[9]for a "possibilistic" interpreta­ tion of histogr ams concurrently with the usua l probabi­ listic interpretation;this double interpretation enables t o build possibility, probability and necessity measures based on a same body of evidence such that V A,N(A) S P(A)!: IT (A), which is satisfactory for the intuition.

A plausibility function that satisfie s (IO) is nothing b) - Fuzzy events and vague statements : From an uncertain body of evidence, we may want to evaluate the pro­ but a y_o~~ip!)_i_ty_l!l~a_s~.r~- in the sense of Zadeh[ 54] ; a credibility function which satisfies(9) is called a bability, the possibility,or the necessity of a propo~~c~~sjty_~e~~u~~ (see Dubois Prade[B]) since the dua- sition which is itself vaguely . sta ted. Zadeh[Sl]hasin­ lity expressed by (3) mirrors the fact that the neces- traduced the concept of a fuzzy set in order to repre­ s ity of an event corresponds to the impossibility of sent vague predicates such as "tall","large", ..· More the opposite event in modal semantics. In the follorecently, in PR~F! this author ~as proposed. t~ :epre~ent. · 'b'l't d th d 1 f a vague propos~t~on by equat~ng the poss~b~l~ty d~stnw~ng,a pass~ ~ ~ y measure an e ua measure o ne-. . . . "t - 11 b · 1 d db IT d N h but~on of the var~able whose value ~s restr~cted by the cess~ y w~ e respect~ve y enote y an , t e re-. . . . . lation VA£U,N(A)=I-n (A) (1 2) propos~t10n,w~th the memb~rsh~p funct~on of th~ fuzzy contrasts with the probabilistic situation where set r~present~ng the mean~n~ of the vagu~ ~red~c~te P(A) = 1 _ P(A) (poss~bly compound)present ~n the propos~t~on;th~s approach enables also to deal with fuzzy quantifiers such

· Possibility and necessity correspond, in terms of m, to an evidence which is consistent(all the focal ele- as'~st','several','a few', ·.. See[53]. ments are nested;in that case Shafer[ 40] speaks of Let~(U),the set of fuzzy subsets of U. A fuzzy set is consonant plausibility and belief functions)but which defined by its membership function ~Afrom U to[O,l]. is not precise in general with respect to the specifi- Usual set-operations are extended to fuzzy sets in the following way[5I](see[8]for alternative definitions). complementation tueU,~i(u)=l-~A(u) (17)

The usual properties of set-operations are preserved except the non-contradiction and excluded-mirldle laws which are weakened in~ue U,min(~A(u),~i(u)) si and in Vue U,max(~A(u),~A(u)) ~ 2 ; it is not surprising thatan ill-defined set somewhat overlaps its complementwhich is itself not-accurately defined. The fuzzy set inclu­ sion is defined by A!<B~Vu,~A (u) S~B(u) (20) .!ote that viewing ~A and ~Bas two possibility distributions re­ presenting two uncertain bodies of evidence,the pos­ sibility and the necessity measures defined from ~B are respectively greater and smaller than the possi­ bility and the necessity measures defined from ~A' which is quite natural since the body of evidence re­ presented by ~B is less informative than the one represented by ~A· The standard definitions of the pro­ bability,of the ROssibility and of the necessity of a fuz~event Ae ~(U) are respectively given by P(A)=2__ ~A(u).p(u) with p(u)=P({u})(Zadeh[5ZJ) (21) ueU

IT(A)=max min(~A(u), n (u)) withn(u)= rr ({u})(Zadeh[53])(22)

ueU

When U is not finite, 'L' is replaced by a Lebesgue­ Stielges integral, 'max' and'min' by 'sup' and 'inf'. (21) is the expression of an expectation and (!!)still holds using (18) and (19). It can be easily checked that (22) and (23) generalizes (15) and (16) and that (9)~(10),(12)still holds using (17)-(19)as well as rAe ~(U),TI(A) ~N(A);however,only weaker versions of (13) and (14)hold,due to the lack of non-contradiction and excluded-middle laws for fuzzy sets. From a multi-va­ lued logic point of view,(22)still evaluates the non­ emptiness of a generalized intersection while (23)is a degree of inclusion. The fact that probability,pos­ sibility and necessity measures are increasing with respect to set inclusion as defined by (20),is compa­ tible with the entailment principle(see[54l)"if X is in A, then X is in B"as soon as A 5:: B in the sense of (;D) · It may seems surprising that a measure of a fuzzy e­ vent is a scalar rather than a fuzzy number;indeed an alternative approach which yields fuzzy numbers exists (see[8]for instance),but scalar evaluations are generally sufficient for practical purposes.Smets [43]has defined the plausibility and the credibility of fuzzy event in a natural '"ay as upper and lower ex­ pectations (see[6]) .Yager[50Jhas introduced generali­ zed plausibility and credibility functions definedfrom fuzzy focal elements (see also[21]).

c) non-interactivity : The notion of non-interactivi­ ty 1n possibility theory plays a role analogous to that of independence in probability theory. Two quantities or variables, X and Y,which take their values respec­ tively on U and V are said to be non-interactive if their join possibility -diStribution "x ,from UxV to ,Y

where Xx and xy are the marginal possibility distri­ butions obtained from XX,Y by projection :

(24) expresses the fact that the fuzzy set of thepos­ sible values of X does not depend on the value of Y and reciprocally. Defining the cartesian product of two fuzzy sets A and B of U and V respectively, by VueU, VveV ·1'-AxB (u, v) =min (I'" A (u) ,JI-B (v)) ( 26)

it can be shown,if X andY are non-interactive varia­ bles (see[35],)that VAe ~(U),VBe ~(V),TIX yCAxB)=min(TIX(A),TIY(B))

where A+B=Ax~, and nX,Y'NX,Y' TIX,N~Y'NY are the pos­ sibility and necessity measures built fromxx y·xxand ' Xy respectively. When X andY are interactive,thesign '=' is ~eplaced by 's 'in (27) and (28) and by ' ~ 'in (29) and (30).

Remark: In MYCIN[41], a measure of belief and a mea­ sure of disbelief in the hypothesis h knowing the evi­ dence e,respectively denoted by MB(h,e) and MD(h,e), are used. From the definitions of MB(h,e) and of MD(h,e)in terms of the probabilities P(h\e)and P(h), it can be easily checked that (',' means the negation) MB(,h,e) = MD(h,e) (31)

MB(h,e) >04MD(h,e)=O;l-MD(h,e) <l4 MB(h,e)=O (32) (31) and (32) are analogous to (12) and (14) respec­ tively,viewing MB(h,e)as a necessity measure and MD(h,e)as the complement to I of a possibility measu­ re. Indeed,the following formulae are used in MYCIN (Aand v denote the conjmction and the disjunction res­ pectively).

which are the exact counterparts of (27)-(30).

d) degree of truth : We close this background on the representation and the measurement of uncertainty with a short discussion of the relation between the notion of a degree of truth and possibility and necessity measures. A degree of truth may be viewed as a measu­ re of the conformity between a representation of the contents of-the-proposition under consideration and a representation of what is actually known of the rea­ lity. Thus the degree of truth of a propos1t1on is re­ lative to our state of knowledge. Let us suppose that the uncertain body of evidence is represented by a possibility distributionxe and that the contents of

the proposition p="X is in A' under consideration is also represented by a possibility distribution K p

(which is crisp ~pis a non- vague statement).Then, using (22) and (23) we can compute the possibility that p is true given e:

and the necessity that p is true given e

N. B.: Cayrol, Farreny, Prade [4] have designed a procedure of pattern-matching where n(p,e) and N(p,e) are used in order to evaluate the semantic similari­ ties between patterns and data. It has been shown that either when x is the charac-

e

teristic function of a singleton (i.e. the evidence is precise) or when the proposition p is non-vague, the quantity v(p,e)= TI (p,e)+N(p,e) (37) 2

can be regarded as a genuine degree of truth in the sense that the truth-functionality is preserved for the negation,the conjunction and the disjunction; see Dubois Prade [ IO] and also Gaines 04] . For instance, we have vhp,e) = I - v(p,e) (38)

As pointed out in Prade 04] , the certainty factor

CF(h , e) =MB(h, e) -MD(h, e), used in MYCIN, can be vie­

wed as a degree of truth up to a scaling effect sin-

ce v(h,e)= I+CF(h,e)

(39)

2

coincides with (37) in the analogy presented in the remark of section II.c. Zadeh [54] has introduced a fuzzy degree of truth named'compatibility'. The com­ patibility of 7( with respect to X is a fuzzy set CP(p,e) of the ¥eal interval [O,I]ewhose membership func tion is defined by

CP(p,e) is nothing but the fuzzy set of the possible values of the variableJt' (u) when the possible values p of u are restricted by the possibility distribution ~ . It can be shown [3~ that e

Thus CP(p,e) contains the informations TI (p,e) and N(p,e). Using extended operations on fuzzy numbers [ 8 ] , CP(,p,e) can be easily expressed in terms of CP(p,e), and CP(p~q,e) or CP(pvq,e) in terms ofCP(p,e) and of CP(q,e), See [35] ,[7] . Conversely,given the possibility distribution~ of p

the proposition under consideration,and its fuzzy truth-value~, it is possible to ge t the greates t so­ lution (in the sense of fuzzy set inclusion) Jt'~ of

:1(+ represents-hat we may conclude about the reality kfu;wing that the proposition p is 't -true. See [54] , [35]. Note that .11:+ = 1C for 1.1 (r)=r, Yr; if t. is a e p "t:

crisp subset of [0, I] (particularly if 'tis a scalar value)n~ is non fuzzy.

III - Deductive inference with uncertainty

a) - The general problem under consideration :Let us consider a causal link between a variable Y taking its values in V and a variable X taking its values in U, expressed by a col lection of rules, if Xis in Ai, then Y is in Bi with gi (44)

where 'v'i, Ai 6 U, Bi £V and gi is a degree of uncertainty of the rule such as a probability or a possi­ bility degree or is a truth-value; the subsets Aiand Bi may be fuzzy; moreover,whatever its nature gimay be only approximately known and the set of its possi­ ble values represented by a fuzzy number. Given some uncertain body of evidence concerning the value of X, the problem consists in deducing what can be saidabout the value of Y taking into account the unce rtainty of the rules and the fact that they may be only vaguely stated . Using representations i n terms of probability or in terms of possibility,this general problem can rece ive at least approximate solutions in general. In the following,we review the main results.

b)- Complete description of the causal link :Let us suppose we know a possibility distributionnx of the

variable X and a conditional possibility distribution Xy I X defined on VxU which r es tricts the possible va-

lues of Y when the value of X is given . Then the pos­ sibility distribution]( attached to the pair (X,Y) X,Y

is ob t ained as

By projection we get the possibility distribution ofY VvE V,~y(v)=sup min(XYIX(v,u),~(u)) (46) UEU

The problem in possibility theory of derivingxXIY orx. 1 from X remains open, however see the --x y X,Y

proposals of Nguyen [30] , Hisda l [18], Zadeh [53].We may think of using operators other than min in (46); other noticeable eligible operators are the product or the operator T defined by T(a,b)=max(O,a+b-l);ho­ wever,min is the greatest of all the possible eligi­ ble operators (see [35]). In general Jt'yjx or :n'yJxare

not available since the A.'s and B.'s of (44) are not

~

~

just singletons;then we have to deal with an incomple­ te description of the causal link.

c) - Incomplete description of the causal link :

a) - in terms of probability: Let us consider the n rules 11 if X is in A.,then Y is in B."with P(B.IA.)(and ~ ~ ~ ~ Y is in B. with P(B.JA.)=I-P(B.JA.) togetherwiththe ~ ~ ~ ~ ~ rule 11 if X is in Ao,then Y is in V (P(VIAo)=l) where (Ao,A 1 , .·· ,An) forms a P!!E.~i:~i:~!?; of U(i.e. the Ai's are exhaustive and mutually exclusive), then from Px

with the underlaying assumption that the probability is distributed uniformly in the designa~ed subset be­ cause no information is available. See L21] · Ishizuka, Fu and Yao [21] have proposed an extension of this ap­ proach when the Ai's are fuzzy sets.

~ ) - In terms of possibility : Again we consider a

collection of rules

if X is in Ai, theR Y is in Bi is ~i true (49) where the Ai's and the Bi's may be normalized fuzzy sets (which can be viewed as possibility distributions)

and where ~i is a fuzzy truth-value (i.e. a fuzzy set of [0,1] which may represent linguistic truth­ qualifications,see [54] , [7] ) . Note that there is no hypothesis of mutual exclusiveness or of exhaus­ tiveness concerning the Ai's.

Each rule (49) expresses a partial knowledge about the unknown possibility distributionXYIX'More preci-

sely "if X is in Ai, then Y is in Bi" can be under­ stood as

(50) expresses that the possibility distribution of Y,computed from (46) withXx= uAi is included in Bi. The greatest solution of (50) with respect to fuzzy set inclusion is given by (see [38], [35] )

1 ... 1

implication which is sometimes known as Godel-Brouwer implication (see [14] );when we use the product ins­

which corresponds to a multivalent implication alrea­ dy considered by Goguen [17] and Gaines [14]; lastly, when we use T(a,b)=max(O,a+b-I),we get

which corresponds to tukasiewicz implication . It can be s9own that

Using (43),(46) a~d (5I),from the rule i and an uncer­ tain body of evidence concerning the value of X repre­ sented by 7t' X' supposed to be normalized, we deduce

It can be noticed that uAixBi(defined by(26)) is also a solution of (50),however it tion generally and its use in 'TTY (in the sense of fuzzy set would be arbitrarily precise. is not the grea test solu­ (55) leads to a smaller inclusion) which thus When u .(r)=r, Vr, if "1:: 1

TIX= uAi (and more generally if TIXo>uAi),we get Tiy=uBi by (55)which is in conformity with the usual modus po­ nens;if TIX=uAi' TIY(v)=I,VvEV(i.e.Y remains indeter-

minate)which is natural;as soon as TIX is not comple­ tely included in uAi' some level of indetermination

It must be pointed out that (55) does not allow to infer from "if X is in Ai, then Y is in Bi" and from "X is almost in Ai" that "Y is almost in Bi" except if we introduce fuzzy tolerance relations Ru and Rv

which enable to enlarge Ai and Bi respectively in sup min(uA.(u), pR __ (u,u')) ~uA.(u) and in u I EU 1 -1) 1

sup min(uBi(v),plh,(v,v'))~uB.(v),uR and u modeling

V 1 EV

"V

1

U RV

approximate equalities; see [35].

Provided that the collection of rules is consistent with the existence of a unique is obtained by aggregating the by (55) for each rule by means rator 'min '. TIYI X' the global result different results given of the idempotent ope- N. B. : The approximate reasoning scheme which leads ~55) can also be discussed equivalently in terms of fuzzy truth-values introducing the compatibility of uAi with respect to TIX and the compatibility of uBi with respect to r:y , see Baldwi:1 [2] ; i_t can al.so be shown that (55) generalizes the rule of detachment in multivalent logics ,see [7] and [35] .For other dis­ cussions see [25] , [28], [42],[46], [47] .

Remark : If we suppose that a possibility measureiT and its dual necessity measure N are defined on a set of propositions p,q, ..· ,then it can be shown that (Prade [35])

.N(p ... q) ~a and N(p) ~b

... N(q) ~in(a,b)

(56)

.P(p ... q) ~a and P(p) ~b ... P(q) ~max(O,a+b-1)( 59)

• .P(ql p) ~a and P(p) ~b ... P(q) ~ a .b where P is a probability measure.

(60)

1. - Hixed problem : Lastly, we consider a situation where probability and possibility are mixed together . We have the n + I rules

if X is in Ai, then Y is in Bi i= I, n

if X is in Ao, then Y is 1n V where the Ao,A1, ·.. ,An

are non-fuzzy and form a partition of U and the Bi's are normalized fuzzy sets.A distribution of probabili­ ty p.=P(A.)(~~ P.=l) is known. The problem is to 1 1 .L-1:0 1

know what can be said of the proposition "y is in B" in terms of ~robability . As it has been recognized by Zadeh [56] , the information consists of a probability distribution and of a conditional possibility distri­ bution 'TTYI x<v,u)=uBi(v) if UEAi. This.problem has been

considered by Dempster [6] when the Bi are non-fuzzy. \fuen they are,using the degree of intersection Il(B,Bi) and the degree on inclusion of Bi in B obtained from (22) and (23),i.e.

N(B,Bi)=inf max(uB(v),l-uBi(v)) we a re in position to VEV

where (6 1) and (62) are straightforward generaliza­ tions of (4) and (2) using degrees of intersection and of inclusion respectively.Lastly,when the values of the pi's are approximatively known and represen­ ted by fuzzy numbers,expressions (61) and (62) can be generalized and remain computationally tractable using recent results in fuzzy arithmetics by Dubois and Pra­ de(see [35] ).

IV- Combining : In this section we successively deal with the combination of uncertain bodies of evidence and with the combination of uncertain informations

a)- combining uncertain bodies of evidence :Let m 1

and m 2 be two basic probability assignments (in the

sense of (I)) representing two uncertain bodies of evidence relative to a same matter .Dempster 's rule of combination [ '6 ] enables t o combine them in order to get a new basic probability assignment m defined by

Note that m does not exist when there is no common part between the foca l elements of m 1 and those of m 2 .

Dempster's rule of combination is associative.Zadeh [55] has discussed the normalization in (63)which may be unsuit~ince \~hen the denominator of (63) is not l,we have~i,j m 1 (Ai).m 2 (Bj)>O which evaluates the

degree to which the two evidences are dissonant; the normalization conceals the existence of this dissonan­ ce . Some particular cases of (63) are noticeable.When m 1 and m 2 reduce to two probability distributions p 1

If U has only two elements t\m possibilities), p(u) = (64) gives u and u(i.e.there are only PI (u) . pz (u) (65)

This aggregation operation has been extensively used by Kayser [22 ] .When m 1 reduces to p 1 and m 2 (A)=I

(which entails m 2 (B)=O, VB/-A), (63) gives the usual

If m 1 and m 2 are such that,3A,m 1 (A)=I-m 1 (U) and m 2 (A) =I-m 2 (U),i.e.A is the unique and common focal element (apart U)of m 1 and m 2 .Then (63) gives form,

When m 1 and m 7 reduce to two possibility distributions n 1 and n 2 ,the-result given bv (63) is not a possibility distribution except in some noticeable particular

cases(when apart of U,m 1 and m 2 have only one focal

element each,but not necessarily the same).If we want to obtain a possibility distribution n,several propo­ sals can be made with some justifications (see [35]), among them,we have the analogous of (64)

In (67),the use of the normalization may be discussed as in the case of Dempster's rule and we may think of using other operations than 'min',see [35] ·

b) - combining uncertain informations First we brrefly recall the Bayesian model. Knowing the conditional probabilities P(hl e 1 ) and P(hl e 2 ) of the hypothesis h

when the evidences e 1 and e 2 are respectively observed,

the probability of h when we observe e 1 and e 2 is e-

where P(h)is the a priori probability of the hypothesis.

When the two sources of evidence are independent, P(e 1 ,e 2 )=P(e 1 ).P(e 2 ) and (68) can be simplified.

In PROSPECTOR [ II ] , [12], a rule of combination ,which is derived of the Bayesian model with some additio­ na l assumptions for "subjective" probability has been proposed;some limitations of this rule has been poin­ ted out in [32].See also [31] . In MYCIN [40] ,the be­ lief or disbelief measures are combined in the follo­ wing way

In case of a positive measure of belief and a posi­ tive measure of disbelief there is a conflic t. Note that (69) and (70) are similar to (66) .Adams [I] has shown that (69) or (70) are consistent with Bayesian model provided that the two sources of evidence are independent(remember that MB(h,e) and MD(h,e) are defined from P(h le) and P(h)).Lastly,Ishizuka,Fu,Yao [ 19] have proposed a slightly different rule of com­ bination for the certainty factors CF(h,e) in MYCIN.

V - Concluding remarks : The intented purpose of this paper is to give an unified view of the mathematical models we have at our disposal in order to deal with uncertainty.The presentation has particularly empha­ sized two recent theories which are still ill-known specially in A.I.:Shafer's belief theory and Zadeh's possibility theory (see t23], [49],[26],[44]for ex­ amples of use of this latter theory in diagnosis and expert systems).The main applications of these models to two inference schemes,particularly important for applicationsto expert systems,the deductive inferen­ ce and the combination,have been surveyed and the link with more empirical approaches,such as the one used in MYCIN,has been stressed.Unfortunately it was not possible to present each proposal in great detai~ within the compass of a small number of pages.Lastly, important classes of approximate or plausible reaso­ ning techniques have not been considered here,espe­ cially analogical reasoning and default reasoning (see [36]) ;although these approaches do not use nu­ merical quantification in general it would be interes­ ting to consider them in an enlarged synthesis in the future .

REFERENCES :

• [I] Adams,J .B. (1976)A probability model of medical reasoning and the MYCIN model.Math . Biosci. ~. 177-186.
• Baldwin,J.F.(I979)A new approach to approximate reasoning using a fuzzy logic.Fuzzy Sets & Syst. 2, 309-325.
• [3 ] Barnett ,J .A. ( 1981) Computational methods for a mathematical theory of evidence.Proc.7th I.J.C.A.I.,Vancouver,868-875.
• Cayrol,M. ,Farreny,H. ,Prade,H. (1982)Fuzzy pattern matching.Kybernetes,ll, 103-116.
• Colby,K.M. ,Smith,D.C-:(1969)Dialogues between humans and an artificial belief systems.Proc.lst, I.J.C.A.I., Washington,D.C.,319-324.
• ~] Dempster,A.P.(I967)Upper and lower probabilities induces by a multivalent mapping.Ann.Math.Stat. 38, 325-339.

[7]Dubois D., Prade H.(l979)0perations in a fuzzy- va­ lued l ogic ,Infor .& Cont.,~3,n° 2,224-240.

[8]Dubois D.,Prade,H. (I980) Fuzzy Sets & Systems:Theo­ ry and Applications.Academic Press,New York .

[9]Dubois D.,Prade H.(l982)0n several representations of an uncertain body of evidence . In:Fuzzy Information and Decision Processes(N .M.Gupta,E.Sanchez,eds.)porth­ Holland,167-181).

[ IO ]Dubois D.,Prade H.(I982)Degree of truth and truth­ functionality .Proc . 2nd World Conf . on Xaths.at the Ser­ vice of Man,Las Palmas , 262-265.

[ II]Duda R. ,Gachnig J.,Hart P.(I 98 1)Model design in the Prospector consultant system for mineral explora­ tion . In :Expert Systems in the Micro-Electronic Age (D.Michie,ed),Edinburgh,Univ.Press,l53-167 .

[12]Duda R.O.,Hart P.E. Nil sson N.J.(I976)Subj ec tive bayesian methods for rule-based inference systems .Tech . No te no 124,SRI-Inter,Menl o Park .

[ 13]Friedman L.(I981)Extended plausible inference . Proc . 7th I.J.C.A.I., Vancouver,487-495.

[14]Gaines B.R.(I976)Foundations of fuzzy reasoning. Int.J .Man-Machine Stu .,8, 623-668.

[IS]Garvey T.D. ,Lowrance J.D.,Fischler MA. (198 1) An inference technique for integrating knowledge from disparate sources.Proc.7th I.J.C.A.I.,Vancouver~l9-325 . [16]Giles R.(I980)A computer program for fuzzy reaso­ ning.Fuzzy Sets & Syst . 4, 22 1-234 .

[I1 ]Goguen J.A. (I969)The- logic of inexact concepts . Synthese, 19, 325- 373.

[18]Hisdal~ . (I978)Conditional possibilities.Indepen­ dence and nouinteraction .Fuzzy Sets & Syst. 1, 283-297 . [ 19]Ishizuka M.,Fu K. S. ,Yao J.T . P.(I981)A theoretical treatment of cer t ainty factor in production systems. Memo CE- STR-81-6,Purdue Univ . ,In .

[20]Ishizuka M. ,Fu K. S.,Yao J . T. P.(I981)Inexac t infe­ rence for rule- based damage assessment of existing structures.Proc .7th I.J.C.A.I.,Vancouver,837-842 .

[21]Ishizuka M.,Fu K.S ., Yao J.T . P.(I981)Inference procedure with uncertainty for problem reduction me­ thod .Memo TR-EE-81-33,Purdue Univ.,In.

[22]Kayser D.(l979) Vers une modelisation du raison­ nement"approximatif".Proc.Colloq."Representation des Connaissances et Raisonnement dans les Sciences de l'Homme"(M.Borillo,ed.),Saint-Maximin,Publ . by INRIA, 440-457 .

[23]Lesmo L., Sai tta L. ,Torasso P.(I983)Fuzzy produc­ tion rules:A learning methodology .To appear in:Advan­ ced in Fuzzy Set Theory and Applications(P.P.Wang,ed.), Plenum Press.

[24]Lesser V.R.,Reed S.,Pavlin J.(I980)Quantifying and simulating the behavior of knowledge-based inter­ pretation systems.Proc.lst Annual N. Conf .Art.Intellig. Stanford ,lll-115.

[25]Mamdani E.H.(I977)Application of fuzzy l ogic t o approximate reasoning using linguistic systems.IEEE Trans.on Comp. C- 26 , 11 82-11 91.

[26]Mar tin-Clouaire R. (I982)A compu ter-aided medical diagnosis method based on a fuzzy set theoretical approach .M. S.Thesi s,Univ.of Saskatchewan .

[27]Michalski R.S.,Chilausky R. L.(I980)Knowledge ac­ quisition by encoding expert rules versus computer induction from examples:a case study involving soy­ bean pathology . Int.J .Man-Machine Stu .1 2, 63-88 .

[28]Mizumoto M.,Fukami S.,Tanaka K.( I979)Fuzzy condi ­ tional inferences and fuzzy inferences with fuzzyquan­ tifiers.Proc.6th I.J.C.A.I.,Tokyo,589-591.

[29)Ng S.W.,Walker A.(I980)Max-min chaining of weigh­ ted causal asser tions is loop free .Proc . lst AnnualNat. Conf.Art.Intellig.,Stanford,IOS-107.

[30]Nguyen H.T.(1978)0n conditional posssibility dis ­ tributions Fuzzy Sets & Syst .,l, 299-309.

[31]Pearl J .(I982)Reverend Bayes in inference engi­ nes:A distributed hierarchical approach . Proc.AAAI . [34]Pednault E. P.D., Zucker S.W.,Muresan L.V.(I981) On the independence assumption underlying subjective bayesian updating.Art.Intellig.l6, 213-222 .

[33]Polya G.(I974)Mathematics and plausible reaso­ ning .Vol . II :Patterns of plausible inference .Prince­ t on Univ.Press,2nd Ed .,l 968.

[34]Prade H.(I980)Plausible reasoning for artificial intelligence . Proc.of Selected Papers of the 1st Int. Conf . on Ar t.Intellig. & Information- Control Sys t. of Robo ts. Bratis l ava , 57-64.

[3~ Prade H.(I982)Modeles mathematiques de l ' impre­ cis e t de l ' incertain en vue d'applications au rai­ sonnement na turel . These d 'Etat,Toulouse III .

[36]Reiter R.(I980)A logic for default reasoning.Art . Intellig .,1 3, 81-132 .

[37]Rescher-N.( I976) Plausible Reasoning.Van Gorcum, Ams terdam .

[38]Sanchez E.(I 977)Solutions in composite fuzzy re­ lations equa tions:Application to medical diagnosis in Brouwerian l ogic.In :Fuzzy Automata and Decision Pro­ cesses(M .M. Gupta,G.N . Sari-is, B. R. Gaines,ed.),North­ Holland, 221 -234.

[39]Schefe P.(l 980)0n foundations of reasoning with uncertain fac ts and vague concepts . Int.J. of Man-Ma­ chine Stu .,12, 35- 62 .

[4d Shafer G. (I976)A mathema t ical Theory of Evidence . ?r. i.nceton Univ . Press .

[4 1 ]Shortliffe E. H., Buchanan B.G .(I975)A model of inexact reasoning i n medicine.Math.Biosci.,23,351-379. [42]SilvaO.de 0., Souza C.de R.(I982)Changing the fuz­ zy rule of detachment.Proc .1 2th IEEE Int.Symp.Multi­ ple-Valued Logic,Paris,267-271.

[4~ Smets P.( I981)Medical diagnosis and degrees of belief.Fuzzy Sets & Syst . S, 259- 266 .

[4~ Soula G. , Sanchez E.(I982)Soft deduction rules in medical diagnosis processes.In:Approximate Reasoning in Decision Analysis(MM.Gupta , E. Sanchez ,eds.)North­ Holland, 77-138.

[[45 pzolovits P.Pauker S.G.(I 978)Categorical and pro­ babilistic reasoning in medical diagnosis.Art.Intellig II, 11 5-1 44.

[4~ Tsukamoto Y.(I 979)An approach to fuzzy reasoning method.In:Advances in Fuzzy Se t Theory and Application! (M .M.Gupta,R. K.Ragade,Yager,eds.) North-Holland,137-149 [47JUmano M.,Mizumot o M.,Tanaka K.(I979)A system for fuzzy reasoning.Proc . 6th I . J .C.A. I .Tokyo,917-919.

[48]Weiss S.M.,Kulikowski C.A.,Amarel S. , Safir A. (l978: A model -based method for computer-aided medical decisi making .Art . Intellig .,ll , 145-172.

[49]Whalen T. , Schott B.( I98 1)Fuzzy production systems for decision support . Porc . Int . Conf . Cyber . & Societ y, Atlanta,649-653.

[SO] lager R.R. (1982)Generalized probabilities of fuzzy events from f uzzy belief structures.Tech . Rep . l!II- 203, Iona College, New ~oche l le,N . Y .

~ !]Zadeh L.A.(I 965)fuzzy Se t s.Infor . & Cont.8,338-353. [52] Zadeh L. A. (1968)I'robability measures of- fuzzy evenl J. Math.Anal .& Appl . 23 , 421 - 427.

[53] Zadeh L.A. (1978)F.uzzy sets as a basis for a theory of possibili t y .Fuzzy Sets & Sys t.l, 3-28.

54]Zadeh L.A.(I 979)A theory of appro~imate rPasoning . Machine Intelligence, 9, Elsevier , 149-1 94 .

[SS]Zadeh L.A.(I979)0nthevalidity of Dempster's rule of combina tion of evidence .Memo UCB/ERL/~79/24,Berkele :

56]Zadeh LA.(I979)Fuzzy sets and information granular : ty.In:Advances in Fuzzy Set Theory and Applications,3-ll