Reasoning with Uncertainty for Expert Systems

REASONING WITH UNCERTAINTY FOR EXPERT SYSTEMS

Ronald R. Vager Machine Intelligence Institute Iona College New Rochelle, New York 10801

II CANONICAL REPRESENTATION OF DATA

Assume V is a variable or attribute which takes values in the set X. A canonical statement is a datum of the form V is A in which A is the value of the variable expressible in terms of the base set X. An example of this is the statement John is young. In a situation like this we can represent the value young as a fuzzy subset A of X such that for each xEX, A<x> indicates the degree of membership of x in the set young. The effect of such a canonical statement is to induce a possibility distribution Rv on X such that

Rv<x> = A<x>, in which Iv<x> indicates the possibility that V assumes the value x given the knowledge that V is A.

The use of the above type of formalism allows us to represent uncertain knowledge having a possibilistic as well as a fuzzy component. We should note that the certain knowledge that John is seventeen can be represented in this situation by simply making A=<17>.

If A and B are two values expressible as fuzzy subsets of X and one is asked if V is B conditioned on the fact that V is A one must use the measures of possibility and certainty to answer this question where Poss[V is B/V is Al=Ha/·=Maxw[A(x)AB(x)] Cert[V is B/V is Al = 1 - Ha-/·

In situations in which the knowledge about the value of a variable V contains probabilistic as well as possibilistic and fuzzy uncertainties we must use a more general type of canonical statement which we call a D-S granule.

Assume m is a mapping from the set of fuzzy subsets of X into the unit interval m: I· ~ [0,11. We call the fuzzy subsets of X, A~, i21 ··· p, for which m<A~>~O the focal elements of m. If the following two conditions are satisfied

1. ~ m<A~> = 1 and 2. ·<·> = 0 we call m a basic probability assignment function <bpa). A canonical statement

ABSTRACT

We discuss a methodology for handling uncertain information in expert and other intelligent systems. This approach combines the theories of approximate reasoning and Dempster­ Shafer.

I I NTRODUCTI ON

The construction of expert and other intelligent computer systems requires sophisticated mechanism for representing and reasoning with uncertain information. At least three forms of uncertainty can be identified as playing a significant role in these types of systems. The first of these possibilistic uncertainty appears in situations where the value of a variable can only be narrowed down to a set of values one of which is the actual value of the variable. This is manifested by a situation in which we know that a person·s age is between 20 and 30. The secend kind of uncertai.nty is related to situations in which there exists uncertainty as to satisfaction of a predicate by an element. This is manifested by concepts which have imprecise or gray boundaries. A very powerful tool for handling this type of uncertainty which also handlas the first type of uncertainty is the fuzzy set. The third type of uncertainty is related to situations in which the value of a variable assumes can be MOdelad by the performance of a random experiment.

The theory of approximate reasoning [11 which is based upon the theory of fuzzy subsets and possibility theory and the Dempster-Shafer mathematical theory of evidence [21 are two important attempts at providing a framewerk for the representation and manipulation of uncertain information. In this paper we briefly describe an approach to reasoning with uncertain information which is an amalgam of this two

approaches.[3l of the form V is 11

is called a 0-5 granule. In the face of a D-5 granule the measures of possibility and certainty become their expected values which we denote as the plausibility and belief measure which are Pl(B) = ~~ ffa,A~ * m(A~)

Bel<B> = ~~ Cert[A/B~l * m<A~>

More complicated structures can be obtained from these canonical forms. Consider that V and U are two variables taking their values in the sets X and V respectively. Consider the statement

"if V is Athen U is m.· In the above A is a fuzzy subset of the base set X and m is a bpa on V with focal elements B~, i=1,2, ··· p. The above Statement induces a 0-5 granule U/V is m·

in which rn· is a bpa on X x V such that the focal elemants of m· are the fuzzy sets E~ on X x V in which for each <x,y), E~<x,y> = Min[1,1-A<x>+B~(y)l and rn·<E~> = rn<A~>-

III REA50NING PROCEOURE

In this section we shall describe the basic reasoning rnechanisrn used in this approach. We first introduce some useful rules of reasoning

l.Conjunction- Assurne m~ and m2 are two bpa·s on the set X with focal elements {A~> and {Bk} respectively. The

conjunction of of the two 0-5 granules V is rn~ and V is rn:z

is a 0-5 granule

V is rn

such that rn is a bpa on X in which for each AC X, rn<A> = ~ rn~<A~)*rn:z<Bk), where the surn is taken over all i,k such that A~ 0 Bw = A.

2.Cylindrical Extension- Assurne V is m is a 0-5 granule where rn is a bpa on X. Let U be another variable taking values in the set V. The cylindrical extension of V is rn to X x V is the joint 0-5 granule

V,U is rn·

where rn· is a bpa on X x V in which if A~, i=l, ···· p, are the focal elements of rn then the focal elements of rn· are B~, i=l, ··· p, where

B~<x,y) = A~<x)

and rn·<B~) = m<A~) 3.Projection- Assume V,U is rn is a joint 0-5 granule on X x V. The projection of this on X is a 0-S granule, V is rn 4 , where m 4 is a bpa on X suchthat if A~, i=l, ··· p, are the focal elements of m then the focal elements of m 4 are B~, i=l, ··· p, where B~<x> Maxv [A~<x,y)l and m 4 <B~> = m<A~).

The basic procedure for reasoning can be described as follows.

<1>. Represent each of data as a D-5 granule.

(2). Cylindrically axtend each granule so that they are all on the same space.

(3). Conjunct all the individual pieces of data.

(4). Project onto the variable of interest.

A simple example will clarify the procedure.

Exarnple Assurne V is a variable which can take its value in the set X = <1,2,3,4}

and U is a variable which can take its value in the set

V= { Bob,Jim,5ue,Mary>=<B,J,5,t1}. Assurne we have the knowladge that " if V is srnall then there is at least a ninty percent chance that U is a women." Futhermore, let us assurne that there exists a probability distribution on X suchthat p~=-5, p:z=-2, ps=.2 and p4=.1. We are interested in using this data to find the value of U. Our first piece of data can be repesented forrnally as "if V is srnall the U is rn"

in which m& is a bpa such that

m~<W> = .9 and rn:z<V> = .1, where W = {5,11}. 5mall is a fuzzy subset of X which can be small = {1/1, 112, .513, 0/4}. The above piece of data is representable as conditional D-5 granule

U/V is m,...

rn:z is a bpa on X x V where m:z<A~> = .9 and .,..(A:z) = .1 in which

A&<x,y> = Min[1,1-small<x> + W<y>l. A& is representable as the matrix

A&

B J 5 11

1

0

0

1

1

2

0

0

1

1

3

.5 .5 1

1

4

1

1

1

1

A:z<x,y) = Min[1,1-small<x>+V<y>l, however since V<y> = 1 then A:z<x,y) = 1.

The secend piece of data can be represented as a 0-5 granule V is rns in which ms<1> = .5, ms<2>=rns<3>=.2 and rn3 (4)=.1. The cylindrical extension of rns is m4 whose focal elements are C&, c,.., Cs and C4 where the rnernbership function of c~ is

C~(x,y) = 1 for X i 0 for x :j i.

In addition ~<C~) P~· The conjunction of these two pieces of data is the D-5 granule V,U is rn

with focal elernents

o& c~ i = 1,2,3,4

Os {1/(1 1 5>, 11<1,11)}

D. {1/<2,5), 1/(2,11)}

D7 <.51<3,B>,.51<3,J),1/(3,S),

1/(3,1'1)} De {1/(4,B>,11<4,J),1/(4,S>,11<4,1'1>> The weights Associated with this focal elements are m<D1>=.05, m<D2>=.02, m<D3>=.02, m<D4>=.01, m<Da>=.45, m<D.>=.18, m<D7>=.18, m<De>=.09 The projection on U is the D-S granule U is m· in which the focal ele111ents are E1 = V = <B, J, S, 1'1>, E2 = <S, 1'1> E3 = <.5/B, .5/J, 1/S, 1/1'1} and m·<E1>= III(D1)+m<D2)+m<D3)+m<D4)+111<D.>=.19 m·<E2>= m<Da>+m<D.>=.63

m·<D3>= III(D7>=.18

IV ENTAIU1ENT

A very useful principle in reAsoning is called the entail.ent principle. It allows us to infer that John is tall from the knowledge that he is six feet six. Iri [4] Vager has introduced an entailment principle for D-S granules. Def: Assu111e 1111 is a bpa on X with focal elements A1, ····· AP with weights m1<Aa>· Let 1112 be another bpa on X with focAl elements Bss,Bs2t···tBs.nCS)tB2St···t ~n<z>t··tBP1t···tBPn<p> suchthat for each i

Aa C Ba~ for all j

and ~~ 1112<Ba~) = m1<A1>

then we say 1111 C m2.

Entailment Principle: Assume m1 C m2 then from knowlege that V is m1 we can infer the D-S granule V is ~-

The entailment principle is usa for as aid in 111aking inferences and answering questions. The entailment principle can also be used to simplify bpa's to forms that are 111ore comprehendible. This simplification can be either for the purpese of presenting the results of a reasoning process 111ora succintly or for easing tha procass of evaluating the weights in providing a bpa.

For exa111ple, in the case of the problem we just workad out since E3 C E1 = V we can infer that the result of our reasoning i& that the probability that U is a female is at least .63.

A situation in which one could use a D-S granule would be the following. Assu111e we are interested in John's age, which we will denote as V. Therefore V is a variable which takes its value in the set of integers less then 120, denote this X. We are given the information that John graduatad from high school this year. We know that people usually graduate from his at "about seventeen years of age." However there are some paople who for various reasons don't graduate at that age. Wa can usa a D-S granule to represent this information. In particular we can say that V is m, where m is the bpa with focal elements A "about seventeen"

B = "young graduate"

C = "old graduata"

However since B C X and C C X we can simply use the focal elements A and X and let m<A> = a and m<X> = 1-a. In this case a is the value such that "at least a portion of the people graduate at about seventeen."

With the aid of the entailment principle one can get a better understanding of the Dempster rule used by Shafer in combining bpa's.

Assume m1 and m2 are two bpa's on X. We previously defined tha conjunction of two as m = 1111 n 1112, in which for aach AC X m<A> = ~ m1 <Aa>*~<B~>, with the sum taken over all Aa and Bk such that Aa 0 Bk = A.

Shafer's combination of thesa two bpa's is m· = m1 e 1112 in which m·<·> = 0

m·<A> = III(A)/(1-m<·>> for all other A. We nota if ·<·>=O then m=m·. In the above m· is obtainad by proportionally allocatting the weight in the null sat to the other focal elements of m. Since $ C Aa tha Dempstar rule can ba sean as si~ly a conjunction followed by a special application of the entail111ent principle.