《人工智能及应用》由会员分享，可在线阅读，更多相关《人工智能及应用（46页珍藏版）》请在金锄头文库上搜索。
1、不确定性推理不确定性推理证据理论D-S理论理论l证据理论是由德普斯特证据理论是由德普斯特(A.P.Dempster)提提出，并由沙佛出，并由沙佛(G.Shfer)进一步发展起来的进一步发展起来的一种处理不确定性的理论。也称为一种处理不确定性的理论。也称为D-S理论。理论。l其将概率的单点赋值扩展为集合赋值，弱其将概率的单点赋值扩展为集合赋值，弱化了公理系统。处理由不知道引起的的不化了公理系统。处理由不知道引起的的不确定性。确定性。概率分配函数概率分配函数l定义定义4-1：设：设是样本集，则由是样本集，则由的所有子集的所有子集构成的集合称为构成的集合称为的幂集，记为的幂集，记为2。l例：设例：设
2、=红，黄，白红，黄，白 ，求，求的幂集的幂集2 解：解： 的幂集元素为的幂集元素为 ， 红红 ， 黄黄 ， 白白 ， 红，黄红，黄 ， 红，白红，白 ， 黄，白黄，白 ， 红，黄，白红，黄，白 。概率分配函数概率分配函数定义定义4-2：设函数：设函数m: 20,1，且满足 m()=0A m(A)=1称m是2上的概率分配函数，m(A)称为A的基本概率数。 概率分配函数概率分配函数例：为上一个例子定义一个概率分配函数。例：为上一个例子定义一个概率分配函数。解：解：m(， 红红 ， 黄黄 ， 白白 ， 红，黄红，黄 ， 红，白红，白 ， 黄，白黄，白 ， 红，黄，白红，黄，白 ) =0,0.3,0,
3、0.1,0.2,0.2,0,0.2概率分配函数的两点说明概率分配函数的两点说明l概率分配函数将样本空间中的任意子集映射到概率分配函数将样本空间中的任意子集映射到，的一个数。，的一个数。当子集是一个元素时，表示对此元素的精确信任度，当子集是一个元素时，表示对此元素的精确信任度，也是对子集的精确信任度。也是对子集的精确信任度。当子集是多个元素时，表示对子集的精确信任度，当子集是多个元素时，表示对子集的精确信任度，但不清楚子集中每个元素的信任度。但不清楚子集中每个元素的信任度。当子集是样本空间时，不知道如何将信任度分配给当子集是样本空间时，不知道如何将信任度分配给每个元素。每个元素。概率分配函数的两
4、点说明概率分配函数的两点说明如例中如例中A= 红红 ， m( 红红 )=0.3表示对红的精确信表示对红的精确信任度是任度是0.3；A= 红，黄，白红，黄，白 ， m( 红，黄，白红，黄，白 )= 0.2表示这些信任度不知道如何分配给集合中的表示这些信任度不知道如何分配给集合中的元素。元素。l概率分配函数不是概率。概率分配函数不是概率。 不满足概率的归一性。不满足概率的归一性。信任函数信任函数定义定义4-3：信任函数：信任函数(Belieffunction) Bel:20,1为对任给的A Bel(A)=B Am(B) Bel函数又称为下限函数，表示对函数又称为下限函数，表示对A的总的信的总的信任
5、度。任度。信任函数信任函数接前例：接前例：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()=B m(B)=1似然函数似然函数定义定义4-4：似然函数：似然函数(Plausibilityfunction) Pl(A):20,1对任给的A Pl(A)=1-Bel(A) 似然函数又
6、称似然函数又称为不可不可驳斥函数或上限函数。表斥函数或上限函数。表示示对A非假的信任度。非假的信任度。似然函数似然函数接前例：接前例：Pl(红红)=1-Bel(红红)=1-Bel(黄黄,白白) =1-Bel(黄黄)-Bel(白白)-Bel(黄黄,白白) =0.9Pl(黄黄,白白)=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(红红, ,
7、黄黄)+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-(B A m(B)+AB m(B)=1-B m(B)=0Pl(A)=AB m(B)信任函数与似然函数的关系信任函数与似然函数的关系定理定理4-1：信任函数与似然函数有如下关系：对信任函数与似然函数有如下关系：对任给的任给的A 有 Pl(A)Bel(A)证明：明：Bel(A)+Bel(A)=B Am(B)+C Am(C)B m(B)=1信任函数与似然函
8、数的关系信任函数与似然函数的关系又又Pl(A)-Bel(A)=1-Bel(A)-Bel(A)=1-(Bel(A)+Bel(A)0Pl(A)Bel(A)使用信任函数与似然函数使用信任函数与似然函数lBel(A)：表示：表示A为真的信任度，为信任度为真的信任度，为信任度下限。下限。lPl(A)：表示：表示A为非假的信任度，为信任度为非假的信任度，为信任度的上限。的上限。使用信任函数与似然函数使用信任函数与似然函数l表示事物的不确定性可以由事物的这两个函数表示事物的不确定性可以由事物的这两个函数值来描述，例如值来描述，例如红红 红红：0.3,0.9 表示表示红红的精确信任度为的精确信任度为0.3，不
9、可驳斥部分，不可驳斥部分为为0.9，而肯定不是，而肯定不是红红的为的为0.1典型值的含义典型值的含义lA0,1：说明对：说明对A一无所知。一无所知。Bel(A)=0,Pl(A)=1,说明对说明对A A没有信任，对没有信任，对A也没有信任。也没有信任。lA0,0：说明：说明A为假。为假。 Bel(A)=0,Pl(A)=0，Bel(A)=1。lA1,1：说明：说明A为真。为真。概率分配函数的正交和概率分配函数的正交和定义定义4-5：设：设m和和n是两个不同的概率分配函数，是两个不同的概率分配函数，其正交和其正交和mn满足满足 mn()=0mn(A)=K-1Xxy=Am(x)Xn(y)其中K=1-x
10、y=m(x)Xn(y)概率分配函数的正交和概率分配函数的正交和设设m1,m2,mn是是n个不同的概率分配函数，其个不同的概率分配函数，其正交和正交和m1m2,mn满足满足 m1m2,mn()=0m1m2,mn(A)=K-1XAi=A1in mi(Ai)其中K=Ai1in mi(Ai)概率分配函数的正交和概率分配函数的正交和例：设样本空间例：设样本空间=a,b,=a,b,从不同的知识来源得从不同的知识来源得 到的概率分配函数分别为：到的概率分配函数分别为：m1( (,a,b,a,b)=(0,0.4,0.5,0.1),a,b,a,b)=(0,0.4,0.5,0.1)m2( (,a,b,a,b)=(
11、0,0.6,0.2,0.2),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.03D-S理论的推理模型理论的推理模型l如前面介绍，可以
12、使用信任函数和似然函数表如前面介绍，可以使用信任函数和似然函数表示命题示命题A的信任度下限和上限。我们使用同样的信任度下限和上限。我们使用同样的方式表示知识信任度。的方式表示知识信任度。l似然函数和信任函数的计算是建立在概率分配似然函数和信任函数的计算是建立在概率分配函数的基础之上，概率分配函数不同，结论会函数的基础之上，概率分配函数不同，结论会不同。不同。一类特殊的概率分配函数一类特殊的概率分配函数l设设=s1,s2,sn,m为定义在为定义在2上的概率分上的概率分配函数，且配函数，且m满足：满足：1.m(si)0,0,对任给对任给si 2.m(si)13.m()=1-m(si)4.4.当当A
13、 ，且，且A的元素多于的元素多于1 1个或没有元素，则个或没有元素，则m(A)=0。一类特殊的概率分配函数一类特殊的概率分配函数l对上面的概率分配函数，可以得到信任函数对上面的概率分配函数，可以得到信任函数和似然函数的性质：和似然函数的性质：1.Bel(A)=si Am(si)2.Bel()=si m(si)+m()=13.Pl(A)=1-Bel(A)=1-si Am(si)=1-si m(si)+si Am(si)=m()+Bel(A)4.Pl()=1-Bel()=1类概率函数类概率函数定义定义4-6：设：设为有限域，对任何命题为有限域，对任何命题A 其类概率函数为f(A)=Bel(A)+|
14、A|/|Pl(A)-Bel(A)其中|A|和|表示A和中的元素个数。类概率函数的性质类概率函数的性质lsi f(si)=1证明：f(si)=Bel(si)+|si|/|Pl(si)-Bel(si)=m(si)+(1/n)m()si f(si)=si m(si)+m()=1类概率函数的性质类概率函数的性质l对任何对任何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)类概率函数的性质类概率函数的性质l对任何对任何A 有f(A)=1-f(A)证明：f(A)=Bel(A)+|A|/|Pl(A
15、)-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)类概率函数的性质类概率函数的性质l根据前面的性质可以很容易得到根据前面的性质可以很容易得到1. f()=02. f()=13. 对任何对任何A ,0f(A)1知识不确定性的表示知识不确定性的表示lD-S理论中，不确定性知识的表示形式为理论中，不确定性知识的表示形式为 ifEthe
16、nH=h1,h2,hnCF=c1,c2,cn其中：其中：E E为前提条件，它可以是简单条件，也可为前提条件，它可以是简单条件，也可以是复合条件；以是复合条件；H H是结论，它用样本空间的子集表示，是结论，它用样本空间的子集表示，h1,h2,hn是该子集的元素；是该子集的元素；CFCF是可信度因子，用集合的方式表示。是可信度因子，用集合的方式表示。 c1,c2,cn用来表示用来表示h1,h2,hn的可信度。的可信度。证据不确定性的表示证据不确定性的表示l证据的不确定性由证据的类概率函数给出。证据的不确定性由证据的类概率函数给出。 CER(E)=f(E)不确定性的更新不确定性的更新l设有知识设有知
17、识ifEthenH=h1,h2,hnCF=c1,c2,cn证据E E的不确定性为CER(E)，确定结论H的不确定性描述CER(H)，方法如下：1.1.求H H的概率分配函数m(h1,h2,hn)=(c1XCER(E),c2XCER(E),cnXCER(E)m()=1-m(hi)不确定性的更新不确定性的更新2.求求Bel(H),Pl(H)及及f(H) Bel(H)=m(hi)Pl(H)=1-Bel(H)f(H)=Bel(H)+|H|/|m()3.CER(H)=f(H)结论不确定性的合成结论不确定性的合成如果有两条知识支持同一结论如果有两条知识支持同一结论ifE1thenH=h1,h2,hnCF=
18、c1,c2,cnifE2thenH=h1,h2,hnCF=e1,e2,en先求出每条知识的概率分配函数m1 , ,m2, ,然后求出两个概率分配函数的正交和m1m2以正交和以正交和作为作为H 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)
19、=0.9,CER(E4)=0.5,CER(E5)=0.7并假定并假定中有中有1010个元素，求个元素，求CER(H)=？示例示例1.求求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示例示例2.求求CER(B)CER(E3and(E4orE5)=0.7m(b1)=
20、(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示例示例3.求求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,C
21、ER(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)=(1/0.855)m1(h1)Xm2(h1)+m1(h1)Xm2()+m1()Xm2(h1)=0.178m(h2)=0.309m(h3)=0.168m()=0.345示例示例4.求求CER(H)Bel(H)=m(h1)+m(h2)+m(h3)=0.655Pl(H)=m()+Bel(H)=1f(H)=Bel(H)+|H|/|*(Pl(H)-Bel(H)=0.759CER(H)=f(H)=0.759证据理论的优点证据理论的优点l满足比概率更弱的公理系统.l能处理由”不知道”引起的不确定性.
