人工智能及应用ch4课件3.ppt

1、不确定性推理不确定性推理证据理论D-S理论理论l证据理论是由德普斯特证据理论是由德普斯特(A.P.Dempster)提提出，并由沙佛出，并由沙佛(G.Shfer)进一步发展起来的进一步发展起来的一种处理不确定性的理论。也称为一种处理不确定性的理论。也称为D-S理理论。论。l其将概率的单点赋值扩展为集合赋值，弱其将概率的单点赋值扩展为集合赋值，弱化了公理系统。处理由不知道引起的的不化了公理系统。处理由不知道引起的的不确定性。确定性。概率分配函数概率分配函数l定义定义4-14-1：设：设是样本集，则由是样本集，则由的所有子集的所有子集构成的集合称为构成的集合称为的幂集，记为的幂集，记为2。l例：设

2、例：设=红，黄，白红，黄，白，求，求的幂集的幂集2 解：解：的幂集元素为的幂集元素为 ，红红，黄黄，白白，红，黄红，黄，红，白红，白，黄，白黄，白，红，黄，白红，黄，白。概率分配函数概率分配函数定义定义4-24-2：设函数：设函数m:20,10,1，且满足且满足 m()=0 A m(A)=1m(A)=1称称mm是是2上的概率分配函数，上的概率分配函数，m(A)m(A)称为称为A A的基的基本概率数。本概率数。概率分配函数概率分配函数例：为上一个例子定义一个概率分配函数。例：为上一个例子定义一个概率分配函数。解：解：m(，红红，黄黄，白白，红，黄红，黄，红，白红，白，黄，白黄，白，红，黄，白红，

3、黄，白)=0,0.3,0,0.1,0.2,0.2,0,0.2概率分配函数的两点说明概率分配函数的两点说明l概率分配函数将样本空间中的任意子集映射到概率分配函数将样本空间中的任意子集映射到，的一个数。，的一个数。当子集是一个元素时，表示对此元素的精确信任度，当子集是一个元素时，表示对此元素的精确信任度，也是对子集的精确信任度。也是对子集的精确信任度。当子集是多个元素时，表示对子集的精确信任度，当子集是多个元素时，表示对子集的精确信任度，但不清楚子集中每个元素的信任度。但不清楚子集中每个元素的信任度。当子集是样本空间时，不知道如何将信任度分配给当子集是样本空间时，不知道如何将信任度分配给每个元素。

4、每个元素。概率分配函数的两点说明概率分配函数的两点说明如例中如例中A=红红，m(红红)=0.3表示对红的精确信表示对红的精确信任度是任度是0.3；A=红，黄，白红，黄，白，m(红，黄，红，黄，白白)=0.2表示这些信任度不知道如何分配给集合中表示这些信任度不知道如何分配给集合中的元素。的元素。l概率分配函数不是概率。概率分配函数不是概率。不满足概率的归一性。不满足概率的归一性。信任函数信任函数定义定义4-34-3：信任函数：信任函数(Belief function)(Belief function)Bel:2Bel:2 0,10,1为对任给的为对任给的AA Bel(A)=Bel(A)=B Am

5、(B)m(B)BelBel函数又称为下限函数，表示对函数又称为下限函数，表示对A A的总的信的总的信任度。任度。信任函数信任函数接前例：接前例：Bel()=0 Bel(红红)=0.3Bel(红红,白白)=Bel(红红)+Bel(白白)+Bel(红红,白白)=0.3+0.1+0.2=0.6Bel(红红,白白,黄黄)=Bel(红红)+Bel(白白)+Bel(黄黄)+Bel(红红,白白)+Bel(红红,黄黄)+Bel(黄黄,白白)+Bel(红红,黄黄,白白)=1信任函数信任函数Bel()=m()=0Bel()=m()=0Bel()=Bel()=BBm(B)=1m(B)=1似然函数似然函数定义定义4-

6、44-4：似然函数：似然函数(Plausibility function)(Plausibility function)Pl(A):2Pl(A):2 0,1 0,1 对任给的对任给的AA Pl(A)=1-Bel(A)Pl(A)=1-Bel(A)似然函数又称为不可驳斥函数或上限函数。表似然函数又称为不可驳斥函数或上限函数。表示对示对A A非假的信任度。非假的信任度。似然函数似然函数接前例：接前例：Pl(红红)=1-Bel(红红)=1-Bel(黄黄,白白)=1-Bel(黄黄)-Bel(白白)-Bel(黄黄,白白)=0.9Pl(黄黄,白白)=1-Bel(黄黄,白白)=1-Bel(红红)=0.7似然函

7、数似然函数可以证明可以证明 Pl(A)=Pl(A)=AB m(B)m(B)红红B m(B)=m(m(B)=m(红红)+m()+m(红红,白白)+m()+m(红红,黄黄)+m(+m(红红,白白,黄黄)=0.3+0.2+0.2+0.2=0.9)=0.3+0.2+0.2+0.2=0.9 黄黄,白白B m(B)=m(m(B)=m(黄黄)+m()+m(白白)+m()+m(红红,黄黄)+m(+m(白白,黄黄)+m()+m(红红,白白)+m()+m(红红,白白,黄黄)=0+0.1+0+0.2+0.2+0.2=0.7 =0+0.1+0+0.2+0.2+0.2=0.7似然函数似然函数Pl(A)-Pl(A)-AB

8、 m(B)=1-Bel(m(B)=1-Bel(A)-A)-AB m(B)m(B)=1-(Bel(=1-(Bel(A)+A)+AB m(B)m(B)=1-(=1-(B A m(B)+m(B)+AB m(B)m(B)=1-=1-B m(B)m(B)=0 =0 Pl(A)=Pl(A)=AB m(B)m(B)信任函数与似然函数的关系信任函数与似然函数的关系定理定理4-14-1：信任函数与似然函数有如下关系：对信任函数与似然函数有如下关系：对任给的任给的AA有有 Pl(A)Bel(A)Pl(A)Bel(A)证明：证明：Bel(A)+Bel(A)=Bel(A)+Bel(A)=B Am(B)+m(B)+C

9、Am(C)m(C)B m(B)=1m(B)=1信任函数与似然函数的关系信任函数与似然函数的关系又又 Pl(A)-Bel(A)=1-Bel(A)-Bel(A)Pl(A)-Bel(A)=1-Bel(A)-Bel(A)=1-(Bel(A)+Bel(A)=1-(Bel(A)+Bel(A)0 0 Pl(A)Bel(A)Pl(A)Bel(A)使用信任函数与似然函数使用信任函数与似然函数lBel(A)Bel(A)：表示：表示A A为真的信任度，为信任度为真的信任度，为信任度下限。下限。lPl(A)Pl(A)：表示：表示A A为非假的信任度，为信任度为非假的信任度，为信任度的上限。的上限。使用信任函数与似然函

10、数使用信任函数与似然函数l表示事物的不确定性可以由事物的这两个函数表示事物的不确定性可以由事物的这两个函数值来描述，例如值来描述，例如红红 红红：0.3,0.9 表示表示红红的精确信任度为的精确信任度为0.3，不可驳斥部分为，不可驳斥部分为0.9，而肯定不是，而肯定不是红红的为的为0.1典型值的含义典型值的含义lA0,1A0,1：说明对：说明对A A一无所知。一无所知。Bel(A)=0,Pl(A)=1,Bel(A)=0,Pl(A)=1,说明对说明对A A没有信任，对没有信任，对AA也没有信任。也没有信任。lA0,0A0,0：说明：说明A A为假。为假。Bel(A)=0,Pl(A)=0Bel(A

11、)=0,Pl(A)=0，Bel(A)=1Bel(A)=1。lA1,1A1,1：说明：说明A A为真。为真。概率分配函数的正交和概率分配函数的正交和定义定义4-54-5：设：设m和和n是两个不同的概率分配函数，是两个不同的概率分配函数，其正交和其正交和mn满足满足 mn()=0mn()=0 mn(A)=K mn(A)=K-1-1 X X xy=Axy=Am(x)X n(y)m(x)X n(y)其中其中K=1-K=1-xy=xy=m(x)X n(y)m(x)X n(y)概率分配函数的正交和概率分配函数的正交和设设mm1 1,m,m2,2,m,mn n是是n n个不同的概率分配函数，其正个不同的概率

12、分配函数，其正交和交和mm1 1 mm2 2,m,mn n满足满足 mm1 1 mm2 2,m,mn n()=0()=0 m m1 1 mm2 2,m,mn n(A)(A)=K =K-1-1 X X Ai=AAi=A1in mmi i(A(Ai i)其中其中K=K=AiAi1in mmi i(A(Ai i)概率分配函数的正交和概率分配函数的正交和例：设样本空间例：设样本空间=a,b,=a,b,从不同的知识来源得从不同的知识来源得 到的概率分配函数分别为：到的概率分配函数分别为：mm1 1(,a,b,a,b)=(0,0.4,0.5,0.1)(,a,b,a,b)=(0,0.4,0.5,0.1)m

13、m2 2(,a,b,a,b)=(0,0.6,0.2,0.2)(,a,b,a,b)=(0,0.6,0.2,0.2)求正交和求正交和mm=mm1 1 mm2 2？概率分配函数的正交和概率分配函数的正交和解：先求解：先求K K-1-1K K-1-1=1-=1-xy=xy=mm1 1(x)X m(x)X m2 2(y)(y)=1-m =1-m1 1(a)xm(a)xm2 2(b)-m(b)-m1 1(b)xm(b)xm2 2(a)(a)=1-0.3x0.3-0.5x0.6 =1-0.3x0.3-0.5x0.6 =0.61 =0.61 概率分配函数的正交和概率分配函数的正交和 m()=0 m()=0 m

14、(a)=K m(a)=K-1-1 xy=axy=amm1 1(x)X m(x)X m2 2(y)(y)=K =K-1-1(m(m1 1(a)X m(a)X m2 2(a,b)+(a,b)+m m1 1(a)X m(a)X m2 2(a)+m(a)+m1 1(a,b)X m(a,b)X m2 2(a)(a)=0.54 =0.54 m(b)=0.43m(b)=0.43 m(a,b)=0.03 m(a,b)=0.03D-S理论的推理模型理论的推理模型l如前面介绍，可以使用信任函数和似然函数表如前面介绍，可以使用信任函数和似然函数表示命题示命题A的信任度下限和上限。我们使用同样的信任度下限和上限。我们

15、使用同样的方式表示知识信任度。的方式表示知识信任度。l似然函数和信任函数的计算是建立在概率分配似然函数和信任函数的计算是建立在概率分配函数的基础之上，概率分配函数不同，结论会函数的基础之上，概率分配函数不同，结论会不同。不同。一类特殊的概率分配函数一类特殊的概率分配函数l设设=s=s1 1,s,s2 2,s,sn n,m,m为定义在为定义在2上的概率分上的概率分配函数，且配函数，且mm满足：满足：1.1.m(sm(si i)0,0,对任给对任给s si i 2.2.m(s m(si i)1)13.3.m()=1-m(sm()=1-m(si i)4.4.当当AA，且，且A A的元素多于的元素多于

16、1 1个或没有元素，则个或没有元素，则m(A)=0m(A)=0。一类特殊的概率分配函数一类特殊的概率分配函数l对上面的概率分配函数，可以得到信任函数对上面的概率分配函数，可以得到信任函数和似然函数的性质：和似然函数的性质：1.1.Bel(A)=Bel(A)=siAsiAm(sm(si i)2.2.Bel()=Bel()=sisim(sm(si i)+m()=1)+m()=13.3.Pl(A)=1-Bel(A)=1-Pl(A)=1-Bel(A)=1-siAsiAm(sm(si i)=1-)=1-sisim(sm(si i)+)+siAsiAm(sm(si i)=m()+Bel(A)=m()+Be

17、l(A)4.4.Pl()=1-Bel()=1Pl()=1-Bel()=1类概率函数类概率函数定义定义4-64-6：设：设 为有限域，对任何命题为有限域，对任何命题AA其类其类概率函数为概率函数为 f(A)=Bel(A)+|A|/|Pl(A)-Bel(A)f(A)=Bel(A)+|A|/|Pl(A)-Bel(A)其中其中|A|A|和和|表示表示A A和和 中的元素个数。中的元素个数。类概率函数的性质类概率函数的性质l sisif(sf(si i)=1)=1证明：证明：f(sf(si i)=Bel(s)=Bel(si i)+|s)+|si i|/|Pl(s|/|Pl(si i)-Bel(s)-Be

18、l(si i)=m(s =m(si i)+(1/n)m()+(1/n)m()sisif(sf(si i)=)=sisim(sm(si i)+m()=1)+m()=1类概率函数的性质类概率函数的性质l对任何对任何AA有有Bel(A)f(A)Pl(A)Bel(A)f(A)Pl(A)证明：证明：Pl(A)-Bel(A)0,|A|/|0Pl(A)-Bel(A)0,|A|/|0 Bel(A)f(A)Bel(A)f(A)f(A)Bel(A)+Pl(A)-Bel(A)f(A)Bel(A)+Pl(A)-Bel(A)=Pl(A)=Pl(A)类概率函数的性质类概率函数的性质l对任何对任何AA有有f(A)=1-f(

19、A)f(A)=1-f(A)证明：证明：f(f(A)=Bel(A)=Bel(A)+|A)+|A|/|Pl(A|/|Pl(A)-Bel(A)-Bel(A)A)|A|=|-|A|A|=|-|A|Pl(Pl(A)-Bel(A)-Bel(A)=m()A)=m()Bel(Bel(A)=1-Bel(A)-m()A)=1-Bel(A)-m()类概率函数的性质类概率函数的性质 f(f(A)=1-Bel(A)-m()+(|-|A|)/|m()A)=1-Bel(A)-m()+(|-|A|)/|m()=1-Bel(A)-m()+m()-|A|/|m()=1-Bel(A)-m()+m()-|A|/|m()=1-(Bel

20、(A)+|A|/|(Pl(A)-Bel(A)=1-(Bel(A)+|A|/|(Pl(A)-Bel(A)=1-f(A)=1-f(A)类概率函数的性质类概率函数的性质l根据前面的性质可以很容易得到根据前面的性质可以很容易得到1.f()=0f()=02.f()=1f()=13.对任何对任何A,0f(A)1A,0f(A)1知识不确定性的表示知识不确定性的表示lD-SD-S理论中，不确定性知识的表示形式为理论中，不确定性知识的表示形式为 if E then H=hif E then H=h1 1,h,h2 2,h,hn n CF=c CF=c1 1,c,c2 2,c,cn n 其中：其中：E E为前提条

21、件，它可以是简单条件，也可为前提条件，它可以是简单条件，也可以是复合条件；以是复合条件；H H是结论，它用样本空间的子集表示，是结论，它用样本空间的子集表示，h h1 1,h,h2 2,h,hn n是该子集的元素；是该子集的元素；CFCF是可信度因子，用集合的方式表示。是可信度因子，用集合的方式表示。c c1 1,c,c2 2,c,cn n用来表示用来表示h h1 1,h,h2 2,h,hn n的可信度。的可信度。证据不确定性的表示证据不确定性的表示l证据的不确定性由证据的类概率函数给出。证据的不确定性由证据的类概率函数给出。CER(E)=f(E)CER(E)=f(E)不确定性的更新不确定性的

22、更新l设有知识设有知识 if E then H=hif E then H=h1 1,h,h2 2,h,hn n CF=c CF=c1 1,c,c2 2,c,cn n 证据证据E E的不确定性为的不确定性为CER(E)CER(E)，确定结论，确定结论H H的不的不确定性描述确定性描述CER(H)CER(H)，方法如下：，方法如下：1.1.求求H H的概率分配函数的概率分配函数m(hm(h1 1,h,h2 2,h,hn n)=(c)=(c1 1XCER(E),cXCER(E),c2 2XCERXCER(E),(E),c,cn nXCER(E)XCER(E)m()=1-m(hm()=1-m(hi i

23、)不确定性的更新不确定性的更新2.求求Bel(H),Pl(H)Bel(H),Pl(H)及及f(Hf(H)Bel(H)=m(hBel(H)=m(hi i)Pl(H)=1-Bel(Pl(H)=1-Bel(H)H)f(H)=Bel(H)+|H|/|m()f(H)=Bel(H)+|H|/|m()3.3.CER(H)=f(H)CER(H)=f(H)结论不确定性的合成结论不确定性的合成如果有两条知识支持同一结论如果有两条知识支持同一结论 if Eif E1 1 then H=h then H=h1 1,h,h2 2,h,hn n CF=c CF=c1 1,c,c2 2,c,cn n if E if E2

24、2 then H=h then H=h1 1,h,h2 2,h,hn n CF=e CF=e1 1,e,e2 2,e,en n 先求出每条知识的概率分配函数先求出每条知识的概率分配函数mm1 1,mm2 2,然后求然后求出两个概率分配函数的正交和出两个概率分配函数的正交和mm1 1 mm2 2以正交和以正交和作为作为H H的概率分配函数。的概率分配函数。示例示例设有如下规则设有如下规则r1:if Er1:if E1 1 andand E E2 2 then A=athen A=a1 1,a,a2 2 CF=0.3,0.5 CF=0.3,0.5r2:if Er2:if E3 3 and(Eand

25、(E4 4 oror E E5 5)then B=b)then B=b1 1 CF=0.7 CF=0.7r3:if Ar3:if A then H=hthen H=h1 1,h,h2 2,h,h3 3 CF=0.1,0.5,0.3 CF=0.1,0.5,0.3r4:if Br4:if B then H=hthen H=h1 1,h,h2 2,h,h3 3 CF=0.4,0.2,0.1 CF=0.4,0.2,0.1用户给出用户给出CER(ECER(E1 1)=0.8,CER(E)=0.8,CER(E2 2)=0.6)=0.6CER(ECER(E3 3)=0.9,CER(E)=0.9,CER(E4

26、 4)=0.5,CER(E)=0.5,CER(E5 5)=0.7)=0.7并假定并假定中有中有1010个元素，求个元素，求CER(H)=CER(H)=？示例示例1.求求CER(A)CER(A)CER(ECER(E1 1 andand E E2 2)=minCER(E)=minCER(E1 1),CER(E),CER(E2 2)=0.6)=0.6m(am(a1 1,a,a2 2)=(0.6)=(0.6*0.3,0.60.3,0.6*0.5)=(0.18,0.3)0.5)=(0.18,0.3)Bel(A)=0.18+0.3=0.48Bel(A)=0.18+0.3=0.48Pl(A)=1-Bel(P

27、l(A)=1-Bel(A)=1-0=1A)=1-0=1f(A)=Bel(A)+|A|/|f(A)=Bel(A)+|A|/|*(Pl(A)-Bel(A)(Pl(A)-Bel(A)=0.48+2/10 =0.48+2/10*(1-0.48)=0.584(1-0.48)=0.584CER(A)=f(A)=0.584CER(A)=f(A)=0.584示例示例2.求求CER(B)CER(B)CER(ECER(E3 3 and(Eand(E4 4 or Eor E5 5)=0.7)=0.7m(bm(b1 1)=(0.7)=(0.7*0.7)=(0.49)0.7)=(0.49)Bel(B)=0.49Bel(

28、B)=0.49Pl(B)=1-Bel(Pl(B)=1-Bel(B)=1-0=1B)=1-0=1f(A)=Bel(A)+|A|/|f(A)=Bel(A)+|A|/|*(Pl(A)-Bel(A)(Pl(A)-Bel(A)=0.49+1/10 =0.49+1/10*(1-0.49)=0.541(1-0.49)=0.541CER(A)=f(A)=0.541CER(A)=f(A)=0.541示例示例3.求求CER(H)CER(H)由规则由规则r3可得可得m1 1(h1 1,h2 2,h3 3)=(CER(A)*0.1,CER(A)*0.5,CER(A)*0.3)=(0.058,0.292,0.175)m

29、1 1()=1-m1 1(h1 1)+m1 1(h2 2)+m1 1(h3 3)=0.475示例示例由规则由规则r4可得可得m2 2(h1 1,h2 2,h3 3)=(CER(A)*0.4,CER(A)*0.2,CER(A)*0.1)=(0.216,0.108,0.054)m2 2()=1-m2 2(h1 1)+m2 2(h2 2)+m2 2(h3 3)=0.622示例示例求正交和求正交和m=mm=m1 1mm2 2K=1-K=1-xy=xy=mm1 1(x)X m(x)X m2 2(y)=0.855(y)=0.855m(hm(h1 1)=K)=K-1-1 X X xy=h1xy=h1mm1

30、1(x)X m(x)X m2 2(y)(y)=(1/0.855)m =(1/0.855)m1 1(h(h1 1)X m)X m2 2(h(h1 1)+m)+m1 1(h(h1 1)X)X mm2 2()+m()+m1 1()X m()X m2 2(h(h1 1)=0.178)=0.178m(hm(h2 2)=0.309)=0.309m(hm(h3 3)=0.168)=0.168m()=0.345m()=0.345示例示例4.求求CER(H)CER(H)Bel(H)=m(hBel(H)=m(h1 1)+m(h)+m(h2 2)+m(h)+m(h3 3)=0.655 =0.655Pl(H)=m()+Bel(H)=1Pl(H)=m()+Bel(H)=1f(H)=Bel(H)+|H|/|f(H)=Bel(H)+|H|/|*(Pl(H)-Bel(H)=0.759(Pl(H)-Bel(H)=0.759CER(H)=f(H)=0.759CER(H)=f(H)=0.759证据理论的优点证据理论的优点l满足比概率更弱的公理系统.l能处理由”不知道”引起的不确定性.