人工智能及应用

不确定性推理证据理论人工智能及应用第1页D-S理论证据理论是由德普斯特(A.P.Dempster)提出，并由沙佛(G.Shfer)深入发展起来一个处理不确定性理论。也称为D-S理论。其将概率单点赋值扩展为集合赋值，弱化了公理系统。处理由不知道引发不确定性。人工智能及应用第2页概率分配函数定义4-1：设Ω是样本集，则由Ω全部子集组成集合称为Ω幂集，记为2Ω。例：设Ω={红，黄，白}，求Ω幂集2Ω解：Ω幂集元素为Φ，{红}，{黄}，{白}，{红，黄}，{红，白}，{黄，白}，{红，黄，白}。人工智能及应用第3页概率分配函数定义4-2：设函数m:2Ω→[0,1]，且满足

m(Φ)=0∑A⊆Ωm(A)=1称m是2Ω上概率分配函数，m(A)称为A基本概率数。人工智能及应用第4页概率分配函数例：为上一个例子定义一个概率分配函数。解：m(Φ，{红}，{黄}，{白}，{红，黄}，{红，白}，{黄，白}，{红，黄，白})={0,0.3,0,0.1,0.2,0.2,0,0.2}人工智能及应用第5页概率分配函数两点说明概率分配函数将样本空间中任意子集映射到［０，１］一个数。当子集是一个元素时，表示对此元素准确信任度，也是对子集准确信任度。当子集是多个元素时，表示对子集准确信任度，但不清楚子集中每个元素信任度。当子集是样本空间时，不知道怎样将信任度分配给每个元素。人工智能及应用第6页概率分配函数两点说明如例中A={红}，m({红})=0.3表示对红准确信任度是0.3；A={红，黄，白}，m({红，黄，白})=0.2表示这些信任度不知道怎样分配给集合中元素。概率分配函数不是概率。不满足概率归一性。人工智能及应用第7页信任函数定义4-3：信任函数(Belieffunction)

Bel:2Ω→[0,1]为对任给A⊆ΩBel(A)=∑B⊆Am(B)

Bel函数又称为下限函数，表示对A总信任度。

人工智能及应用第8页信任函数接前例：Bel(Φ)=0Bel({红})=0.3Bel({红,白})=Bel({红})+Bel({白})+Bel({红,白})=0.3+0.1+0.2=0.6Bel({红,白,黄})=Bel({红})+Bel({白})+Bel({黄})+Bel({红,白})+Bel({红,黄})+Bel({黄,白})+Bel({红,黄,白})=1人工智能及应用第9页信任函数Bel(Φ)=m(Φ)=0Bel(Ω)=∑B⊆Ωm(B)=1人工智能及应用第10页似然函数定义4-4：似然函数(Plausibilityfunction)

Pl(A):2Ω→[0,1]对任给A⊆ΩPl(A)=1-Bel(¬A)似然函数又称为不可驳斥函数或上限函数。表示对A非假信任度。

人工智能及应用第11页似然函数接前例：Pl({红})=1-Bel(¬{红})=1-Bel({黄,白})=1-Bel({黄})-Bel({白})-Bel({黄,白})=0.9Pl({黄,白})=1-Bel(¬{黄,白})=1-Bel({红})=0.7人工智能及应用第12页似然函数能够证实

Pl(A)=∑A∩B≠Φ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人工智能及应用第13页似然函数Pl(A)-∑A∩B≠Φm(B)=1-Bel(¬A)-∑A∩B≠Φm(B)=1-(Bel(¬A)+∑A∩B≠Φm(B))=1-(∑B⊆¬Am(B)+∑A∩B≠Φm(B))=1-∑B⊆Ω

m(B)=0∴Pl(A)=∑A∩B≠Φm(B)人工智能及应用第14页信任函数与似然函数关系定理4-1：信任函数与似然函数有以下关系：对任给A⊆Ω有

Pl(A)≥Bel(A)证实：

∵Bel(A)+Bel(¬A)=∑B⊆Am(B)+∑C⊆¬Am(C)≤∑B⊆Ωm(B)=1人工智能及应用第15页信任函数与似然函数关系又∵Pl(A)-Bel(A)=1-Bel(¬A)-Bel(A)=1-(Bel(¬A)+Bel(A))≥0∴Pl(A)≥Bel(A)人工智能及应用第16页使用信任函数与似然函数Bel(A)：表示A为真信任度，为信任度下限。Pl(A)：表示A为非假信任度，为信任度上限。人工智能及应用第17页使用信任函数与似然函数表示事物不确定性能够由事物这两个函数值来描述，比如{红}{红}：[0.3,0.9]表示{红}准确信任度为0.3，不可驳斥部分为0.9，而必定不是{红}为0.1人工智能及应用第18页经典值含义A[0,1]：说明对A一无所知。Bel(A)=0,Pl(A)=1,说明对A没有信任，对¬A也没有信任。A[0,0]：说明A为假。Bel(A)=0,Pl(A)=0，Bel(¬A)=1。A[1,1]：说明A为真。人工智能及应用第19页概率分配函数正交和定义4-5：设m和n是两个不一样概率分配函数，其正交和m⊕n满足

m⊕n(Φ)=0m⊕n(A)=K-1X∑x∩y=Am(x)Xn(y)

其中K=1-∑x∩y=Φm(x)Xn(y)人工智能及应用第20页概率分配函数正交和设m1,m2,…,mn是n个不一样概率分配函数，其正交和m1⊕

m2⊕,…,⊕mn满足

m1⊕

m2⊕,…,⊕mn(Φ)=0m1⊕

m2⊕,…,⊕mn(A)=K-1X∑∩Ai=A∏1≤i≤nmi(Ai)

其中K=∑∩Ai≠Φ∏1≤i≤nmi(Ai)人工智能及应用第21页概率分配函数正交和例：设样本空间Ω={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？人工智能及应用第22页概率分配函数正交和解：先求K-1K-1=1-∑x∩y=Φm1(x)Xm2(y)=1-m1({a})xm2({b})-m1({b})xm2({a})=1-0.3x0.3-0.5x0.6=0.61

人工智能及应用第23页概率分配函数正交和m(Φ)=0m({a})=K-1∑x∩y={a}m1(x)Xm2(y)=K-1(m1({a})Xm2((a,b})+m1({a})Xm2({a})+m1({a,b})Xm2({a}))=0.54

m({b})=0.43m({a,b})=0.03人工智能及应用第24页D-S理论推理模型如前面介绍，能够使用信任函数和似然函数表示命题A信任度下限和上限。我们使用一样方式表示知识信任度。似然函数和信任函数计算是建立在概率分配函数基础之上，概率分配函数不一样，结论会不一样。人工智能及应用第25页一类特殊概率分配函数设Ω={s1,s2,,…,sn},m为定义在2Ω上概率分配函数，且m满足：m({si})≥0,对任给si∊Ω∑m({si})≤1m(Ω)=1-∑m({si})当A⊆Ω，且A元素多于1个或没有元素，则m(A)=0。人工智能及应用第26页一类特殊概率分配函数对上面概率分配函数，能够得到信任函数和似然函数性质：Bel(A)=∑si∊Am(si)Bel(Ω)=∑si∊Ωm(si)+m(Ω)=1Pl(A)=1-Bel(¬A)=1-∑si∊¬Am(si)=1-∑si∊Ωm(si)+∑si∊Am(si)=m(Ω)+Bel(A)Pl(Ω)=1-Bel(¬Ω)=1人工智能及应用第27页类概率函数定义4-6：设Ω为有限域，对任何命题A⊆Ω其类概率函数为f(A)=Bel(A)+|A|/|Ω|[Pl(A)-Bel(A)]其中|A|和|Ω|表示A和Ω中元素个数。人工智能及应用第28页类概率函数性质∑si∊Ω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人工智能及应用第29页类概率函数性质对任何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)人工智能及应用第30页类概率函数性质对任何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(Ω)人工智能及应用第31页类概率函数性质∴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)人工智能及应用第32页类概率函数性质依据前面性质能够很轻易得到

f(Φ)=0

f(Ω)=1对任何A⊆Ω,0≤f(A)≤1人工智能及应用第33页知识不确定性表示D-S理论中，不确定性知识表示形式为

ifEthenH={h1,h2,,…,hn}CF={c1,c2,,…,cn}其中：E为前提条件，它能够是简单条件，也可以是复合条件；H是结论，它用样本空间子集表示，h1,h2,,…,hn是该子集元素；CF是可信度因子，用集合方式表示。c1,c2,,…,cn用来表示h1,h2,,…,hn可信度。人工智能及应用第34页证据不确定性表示证据不确定性由证据类概率函数给出。

CER(E)=f(E)人工智能及应用第35页不确定性更新设有知识ifEthenH={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})人工智能及应用第36页不确定性更新求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)人工智能及应用第37页结论不确定性合成假如有两条知识支持同一结论ifE1thenH={h1,h2,,…,hn}CF={c1,c2,,…,cn}ifE2thenH={h1,h2,,…,hn}CF={e1,e2,,…,en}先求出每条知识概率分配函数m1,m2,然后求出两个概率分配函数正交和m1⊕

m2以正交和作为H概率分配函数。人工智能及应用第38页示例设有以下规则r1:ifE1and

E2thenA={a1,a2}CF={0.3,0.5}r2:ifE3and(E4or

E5)thenB={b1}CF={0.7}r3:ifA

thenH={h1,h2,h3}CF={0.1,0.5,0.3}r4:ifB

thenH={h1,h2,h3}CF={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)=？人工智能及应用第39页示例求CER(A)CER(E1and

E2)=min{CER(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人工智能及应用第40页示例求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人工智能及应用第41页示例求CER(H)由规则r3可得m1({h1},{h2},{h3})=(C