人工智能及应用ch43.ppt

不确定性推理,证据理论,D-S理论,证据理论是由德普斯特(A.P.Dempster)提出，并由沙佛(G.Shfer)进一步发展起来的一种处理不确定性的理论。也称为D-S理论。 其将概率的单点赋值扩展为集合赋值，弱化了公理系统。处理由不知道引起的的不确定性。,概率分配函数,定义4-1：设是样本集，则由的所有子集构成的集合称为的幂集，记为2。 例：设=红，黄，白，求的幂集2 解： 的幂集元素为 ，红，黄，白，红，黄， 红，白，黄，白，红，黄，白。,概率分配函数,定义4-2：设函数m: 20,1，且满足 m()=0 Am(A)=1 称m是2上的概率分配函数，m(A)称为A的基本概率数。,概率分配函数,例：为上一个例子定义一个概率分配函数。 解： m(，红，黄，白，红，黄， 红，白，黄，白，红，黄，白) =0,0.3,0,0.1,0.2,0.2,0,0.2,概率分配函数的两点说明,概率分配函数将样本空间中的任意子集映射到，的一个数。 当子集是一个元素时，表示对此元素的精确信任度，也是对子集的精确信任度。 当子集是多个元素时，表示对子集的精确信任度，但不清楚子集中每个元素的信任度。 当子集是样本空间时，不知道如何将信任度分配给每个元素。,概率分配函数的两点说明,如例中A=红， m(红)=0.3表示对红的精确信任度是0.3；A=红，黄，白， m(红，黄，白)= 0.2表示这些信任度不知道如何分配给集合中的元素。 概率分配函数不是概率。 不满足概率的归一性。,信任函数,定义4-3：信任函数(Belief function) Bel:20,1为对任给的A Bel(A)=BAm(B) Bel函数又称为下限函数，表示对A的总的信任度。,信任函数,接前例： Bel()=0 Bel(红)=0.3 Bel(红,白)=Bel(红)+Bel(白)+Bel(红,白) =0.3+0.1+0.2=0.6 Bel(红,白,黄)=Bel(红)+Bel(白)+Bel(黄)+ Bel(红,白)+Bel(红,黄)+Bel(黄,白) +Bel(红,黄,白) =1,信任函数,Bel()=m()=0 Bel()=Bm(B)=1,似然函数,定义4-4：似然函数(Plausibility function) Pl(A):20,1 对任给的A Pl(A)=1-Bel(A) 似然函数又称为不可驳斥函数或上限函数。表示对A非假的信任度。,似然函数,接前例： Pl(红)=1-Bel(红)=1-Bel(黄,白) =1-Bel(黄)-Bel(白)-Bel(黄,白) =0.9 Pl(黄,白)=1-Bel(黄,白)=1-Bel(红) =0.7,似然函数,可以证明 Pl(A)=AB m(B) 红B m(B)=m(红)+m(红,白)+m(红,黄) +m(红,白,黄)=0.3+0.2+0.2+0.2=0.9 黄,白B m(B)=m(黄)+m(白)+m(红,黄) +m(白,黄) +m(红,白)+m(红,白,黄) =0+0.1+0+0.2+0.2+0.2=0.7,似然函数,Pl(A)-AB m(B)=1-Bel(A)-AB m(B) =1-(Bel(A)+AB m(B) =1-(BA m(B)+AB m(B) =1-B m(B) =0 Pl(A)=AB m(B),信任函数与似然函数的关系,定理4-1：信任函数与似然函数有如下关系：对任给的A有 Pl(A)Bel(A) 证明： Bel(A)+Bel(A)=BAm(B)+CAm(C) Bm(B)=1,信任函数与似然函数的关系,又 Pl(A)-Bel(A)=1-Bel(A)-Bel(A) =1-(Bel(A)+Bel(A) 0 Pl(A) Bel(A),使用信任函数与似然函数,Bel(A)：表示A为真的信任度，为信任度下限。 Pl(A)：表示A为非假的信任度，为信任度的上限。,使用信任函数与似然函数,表示事物的不确定性可以由事物的这两个函数值来描述，例如红 红：0.3,0.9 表示红的精确信任度为0.3，不可驳斥部分为0.9，而肯定不是红的为0.1,典型值的含义,A0,1：说明对A一无所知。Bel(A)=0,Pl(A)=1,说明对A没有信任，对A也没有信任。 A0,0：说明A为假。 Bel(A)=0,Pl(A)=0， Bel(A)=1。 A1,1：说明A为真。,概率分配函数的正交和,定义4-5：设m和n是两个不同的概率分配函数，其正交和mn满足 mn()=0 mn(A)=K-1 X xy=Am(x) X n(y) 其中K=1-xy=m(x) X n(y),概率分配函数的正交和,设m1,m2,mn是n个不同的概率分配函数，其正交和m1 m2, mn满足 m1 m2, mn()=0 m1 m2, mn(A) =K-1 X Ai=A1in mi(Ai) 其中K=Ai1in mi(Ai),概率分配函数的正交和,例：设样本空间=a,b,从不同的知识来源得 到的概率分配函数分别为： m1(,a,b,a,b)=(0,0.4,0.5,0.1) m2(,a,b,a,b)=(0,0.6,0.2,0.2) 求正交和m=m1 m2 ？,概率分配函数的正交和,解：先求K-1 K-1=1-xy=m1(x) X m2(y) =1- m1(a)xm2(b)-m1(b)xm2(a) =1-0.3x0.3-0.5x0.6 =0.61,概率分配函数的正交和,m()=0 m(a)= K-1 xy=am1(x) X m2(y) = K-1(m1(a) X m2(a,b)+ m1(a) X m2(a)+m1(a,b) X m2(a) =0.54 m(b)=0.43 m(a,b)=0.03,D-S理论的推理模型,如前面介绍，可以使用信任函数和似然函数表示命题A的信任度下限和上限。我们使用同样的方式表示知识信任度。 似然函数和信任函数的计算是建立在概率分配函数的基础之上，概率分配函数不同，结论会不同。,一类特殊的概率分配函数,设=s1,s2,sn,m为定义在2上的概率分配函数，且m满足： m(si)0,对任给si m(si)1 m()=1- m(si) 当A，且A的元素多于1个或没有元素，则m(A)=0。,一类特殊的概率分配函数,对上面的概率分配函数，可以得到信任函数和似然函数的性质： Bel(A)= siAm(si) Bel()=sim(si) +m()=1 Pl(A)=1-Bel(A)=1- siAm(si) =1- sim(si)+siAm(si)=m()+Bel(A) Pl()=1-Bel()=1,类概率函数,定义4-6：设为有限域，对任何命题A其类概率函数为 f(A)=Bel(A)+|A|/|Pl(A)-Bel(A) 其中|A|和|表示A和中的元素个数。,类概率函数的性质,sif(si)=1 证明： f(si)=Bel(si)+|si|/|Pl(si)-Bel(si) =m(si)+(1/n)m() sif(si)= sim(si)+m()=1,类概率函数的性质,对任何A有Bel(A)f(A)Pl(A) 证明：Pl(A)-Bel(A)0, |A|/|0 Bel(A)f(A) f(A)Bel(A)+Pl(A)-Bel(A) =Pl(A),类概率函数的性质,对任何A有f(A)=1-f(A) 证明： f(A)=Bel(A)+|A|/|Pl(A)-Bel(A) |A|=|-|A| Pl(A)-Bel(A)=m() Bel(A)=1-Bel(A)-m(),类概率函数的性质, f(A)=1-Bel(A)-m()+(|-|A|)/|m() =1-Bel(A)-m()+m()-|A|/|m() =1-(Bel(A)+|A|/|(Pl(A)-Bel(A) =1-f(A),类概率函数的性质,根据前面的性质可以很容易得到 f()=0 f()=1 对任何A,0f(A)1,知识不确定性的表示,D-S理论中，不确定性知识的表示形式为 if E then H=h1,h2,hn CF=c1,c2,cn 其中：E为前提条件，它可以是简单条件，也可 以是复合条件； H是结论，它用样本空间的子集表示，h1,h2, ,hn是该子集的元素； CF是可信度因子，用集合的方式表示。 c1,c2, ,cn用来表示h1,h2,hn的可信度。,证据不确定性的表示,证据的不确定性由证据的类概率函数给出。 CER(E)=f(E),不确定性的更新,设有知识 if E then H=h1,h2,hn CF=c1,c2,cn 证据E的不确定性为CER(E)，确定结论H的不确定性描述CER(H)，方法如下： 求H的概率分配函数 m(h1 ,h2 ,hn )=(c1XCER(E),c2XCER(E),cnXCER(E) m()=1-m(hi),不确定性的更新,求Bel(H),Pl(H)及f(H) Bel(H)=m(hi) Pl(H)=1-Bel(H) f(H)=Bel(H)+|H|/|m() CER(H)=f(H),结论不确定性的合成,如果有两条知识支持同一结论 if E1 then H=h1,h2,hn CF=c1,c2,cn if E2 then H=h1,h2,hn CF=e1,e2,en 先求出每条知识的概率分配函数m1 ,m2,然后求 出两个概率分配函数的正交和m1 m2以正交和 作为H的概率分配函数。,示例,设有如下规则 r1: if E1 and E2 then A=a1,a2 CF=0.3,0.5 r2: if E3 and (E4 or E5) then B=b1 CF=0.7 r3: if A then H=h1,h2,h3 CF=0.1,0.5,0.3 r4: if B then H=h1,h2,h3 CF=0.4,0.2,0.1 用户给出CER(E1)=0.8, CER(E2)=0.6 CER(E3)=0.9, CER(E4)=0.5, CER(E5)=0.7 并假定中有10个元素，求CER(H)=？,示例,求CER(A) CER(E1 and E2)=minCER(E1),CER(E2)=0.6 m(a1,a2)=(0.6*0.3,0.6*0.5)=(0.18,0.3) Bel(A)=0.18+0.3=0.48 Pl(A)=1-Bel(A)=1-0=1 f(A)=Bel(A)+|A|/|*(Pl(A)-Bel(A) =0.48+2/10*(1-0.48)=0.584 CER(A)=f(A)=0.584,示例,求CER(B) CER(E3 and(E4 or E5)=0.7 m(b1)=(0.7*0.7)=(0.49) Bel(B)=0.49 Pl(B)=1-Bel(B)=1-0=1 f(A)=Bel(A)+|A|/|*(Pl(A)-Bel(A) =0.49+1/10*(1-0.49)=0.541 CER(A)=f(A)=0.541,示例,求CER(H) 由规则r3可得 m1(h1,h2,h3)=(CER(A)*0.1,CER(A)*0.5,CER(A)*0.3)=(0.058,0.292,0.175) m1()=1-m1(h1)+ m1(h2)+m1(h3)=0.475,示例,由规则r4可得 m2(h1,h2,h3)=(CER(A)*0.4,CER(A)*0.2,CER(A)*0.1)=(0.216,0.108,0.054) m2()=1-m2(h1)+ m2(h2)+m2(h3)=0.622,示例,求正交和m=m1m2 K=1-xy=m1(x) X m2(y)=0.855 m(h1) =K-1 X xy= h1m1(x) X m2(y)