人工智能及应用_ch4_3.ppt

不确定性推理,证据理论,D-S理论,证据理论是由德普斯特(A.P.Dempster)提出，并由沙佛(G.Shfer)进一步发展起来的一种处理不确定性的理论。也称为D-S理论。其将概率的单点赋值扩展为集合赋值，弱化了公理系统。处理由不知道引起的的不确定性。,概率分配函数,定义4-1：设是样本集，则由的所有子集构成的集合称为的幂集，记为2。例：设=红，黄，白，求的幂集2解：的幂集元素为，红，黄，白，红，黄，红，白，黄，白，红，黄，白。,概率分配函数,定义4-2：设函数m:20,1，且满足m()=0Am(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：信任函数(Belieffunction)Bel:20,1为对任给的ABel(A)=BAm(B)Bel函数又称为下限函数，表示对A的总的信任度。,信任函数,接前例：Bel()=0Bel(红)=0.3Bel(红,白)=Bel(红)+Bel(白)+Bel(红,白)=0.3+0.1+0.2=0.6Bel(红,白,黄)=Bel(红)+Bel(白)+Bel(黄)+Bel(红,白)+Bel(红,黄)+Bel(黄,白)+Bel(红,黄,白)=1,信任函数,Bel()=m()=0Bel()=Bm(B)=1,似然函数,定义4-4：似然函数(Plausibilityfunction)Pl(A):20,1对任给的APl(A)=1-Bel(A)似然函数又称为不可驳斥函数或上限函数。表示对A非假的信任度。,似然函数,接前例：Pl(红)=1-Bel(红)=1-Bel(黄,白)=1-Bel(黄)-Bel(白)-Bel(黄,白)=0.9Pl(黄,白)=1-Bel(黄,白)=1-Bel(红)=0.7,似然函数,可以证明Pl(A)=ABm(B)红Bm(B)=m(红)+m(红,白)+m(红,黄)+m(红,白,黄)=0.3+0.2+0.2+0.2=0.9黄,白Bm(B)=m(黄)+m(白)+m(红,黄)+m(白,黄)+m(红,白)+m(红,白,黄)=0+0.1+0+0.2+0.2+0.2=0.7,似然函数,Pl(A)-ABm(B)=1-Bel(A)-ABm(B)=1-(Bel(A)+ABm(B)=1-(BAm(B)+ABm(B)=1-Bm(B)=0Pl(A)=ABm(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)0Pl(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()=0mn(A)=K-1Xxy=Am(x)Xn(y)其中K=1-xy=m(x)Xn(y),概率分配函数的正交和,设m1,m2,mn是n个不同的概率分配函数，其正交和m1m2,mn满足m1m2,mn()=0m1m2,mn(A)=K-1XAi=A1inmi(Ai)其中K=Ai1inmi(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=m1m2？,概率分配函数的正交和,解：先求K-1K-1=1-xy=m1(x)Xm2(y)=1-m1(a)xm2(b)-m1(b)xm2(a)=1-0.3x0.3-0.5x0.6=0.61,概率分配函数的正交和,m()=0m(a)=K-1xy=am1(x)Xm2(y)=K-1(m1(a)Xm2(a,b)+m1(a)Xm2(a)+m1(a,b)Xm2(a)=0.54m(b)=0.43m(a,b)=0.03,D-S理论的推理模型,如前面介绍，可以使用信任函数和似然函数表示命题A的信任度下限和上限。我们使用同样的方式表示知识信任度。似然函数和信任函数的计算是建立在概率分配函数的基础之上，概率分配函数不同，结论会不同。,一类特殊的概率分配函数,设=s1,s2,sn,m为定义在2上的概率分配函数，且m满足：m(si)0,对任给sim(si)1m()=1-m(si)当A，且A的元素多于1个或没有元素，则m(A)=0。,一类特殊的概率分配函数,对上面的概率分配函数，可以得到信任函数和似然函数的性质：Bel(A)=siAm(si)Bel()=sim(si)+m()=1Pl(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|/|0Bel(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()=0f()=1对任何A,0f(A)1,知识不确定性的表示,D-S理论中，不确定性知识的表示形式为ifEthenH=h1,h2,hnCF=c1,c2,cn其中：E为前提条件，它可以是简单条件，也可以是复合条件；H是结论，它用样本空间的子集表示，h1,h2,hn是该子集的元素；CF是可信度因子，用集合的方式表示。c1,c2,cn用来表示h1,h2,hn的可信度。,证据不确定性的表示,证据的不确定性由证据的类概率函数给出。CER(E)=f(E),不确定性的更新,设有知识ifEthenH=h1,h2,hnCF=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),结论不确定性的合成,如果有两条知识支持同一结论ifE1thenH=h1,h2,hnCF=c1,c2,cnifE2thenH=h1,h2,hnCF=e1,e2,en先求出每条知识的概率分配函数m1,m2,然后求出两个概率分配函数的正交和m1m2以正交和作为H的概率分配函数。,示例,设有如下规则r1:ifE1andE2thenA=a1,a2CF=0.3,0.5r2:ifE3and(E4orE5)thenB=b1CF=0.7r3:ifAthenH=h1,h2,h3CF=0.1,0.5,0.3r4:ifBthenH=h1,h2,h3CF=0.4,0.2,0.1用户给出CER(E1)=0.8,CER(E2)=0.6CER(E3)=0.9,CER(E4)=0.5,CER(E5)=0.7并假定中有10个元素，求CER(H)=？,示例,求CER(A)CER(E1andE2)=minCER(E1),CER(E2)=0.6m(a1,a2)=(0.6*0.3,0.6*0.5)=(0.18,0.3)Bel(A)=0.18+0.3=0.48Pl(A)=1-Bel(A)=1-0=1f(A)=Bel(A)+|A|/|*(Pl(A)-Bel(A)=0.48+2/10*(1-0.48)=0.584CER(A)=f(A)=0.584,示例,求CER(B)CER(E3and(E4orE5)=0.7m(b1)=(0.7*0.7)=(0.49)Bel(B)=0.49Pl(B)=1-Bel(B)=1-0=1f(A)=Bel(A)+|A|/|*(Pl(A)-Bel(A)=0.49+1/10*(1-0.49)=0.541CER(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=m1m2K=1-xy=m1(x)Xm2(y)=0.855m(h1)=K-1Xxy=h1m1(x)Xm2(y)