人工智能原理教案03章 不确定性推理方法323证据理论41341.docx

3.4证据理论 0. 前言l 主观Bayes方法必须给出先验概率。l Dempsteer和Shaafer提出出的证据理论论，可用来处处理这种由不不知道所引起起的不确定性性。l 证据理论采用信信任函数而不不是概率作为为不确定性度度量，它通过过对一些事件件的概率加以以约束来建立立信任函数而而不必说明精精确的难于获获得的概率。l 证据理论满足比比概率论更弱弱的公理系统统，当这种约约束限制为严严格的概率时时（即概率值值已知时），证证据理论就退退化为概率论论了。 1. 证据的不确确定性度量(1) 基本本理论 辨别框概念：设U为假设设x的所有可可能的穷举集集合，且设UU中的各元素素间是互斥的的，我们称UU为辨别框（FFrame of diiscernnment）。设设U的元素个个数为N，则则U的幂集合合2U的元素个数数为2N，每个幂集集合的元素对对应于一个关关于x取值情情况的命题（子子集）。对任一AU，命命题A表示了了某些假设的的集合(这样样的命题间不不再有互斥性性)。针对医医疗诊断问题题，U就是所所有可能疾病病(假设)的的集合，诊断断结果必是UU中确定的元元素构成的。AA表示某一种种(单元素)或某某些种疾病。医医生为了进行行诊断所进行行的各种检查查就称作证据据，有的证据据所支持的常常不只是一种种疾病而是多多种疾病，即即U的一子集集A。定义1：基本概概率分配函数数（Basiic proobabillity aassignnment）：对任一个属于UU的子集A（命命题），命它它对应于一个个数m0,1，而且满足足 则称函数m为幂幂集2U上的基本概率率分配函数bbpa，称m(A)为A的基本本概率数。m(A)表示了了证据对U的子集A成成立的一种信信任的度量，取取值于0,1，而且22U中各元素信信任的总和为为1。m(AA)的意义为为l 若AÌU且A¹U，则则m(A)表表示对A的确确定信任程度度。l 若A=U，则mm(A)表示示这个数不知知如何分配（即即不知道的情况况）。例如， 设U=红，黄，白白，2U上的基本概概率分配函数数m为m（ ，红，黄黄，白，红,黄黄，红,白，黄黄,白，红,黄,白白）=（0，0.33，0，0.1，0.22，0.2，00，0.2）其中，m(红)=0.3 表表示对命题红的确定定信任度。m(红,黄,白)=00.2 表示示不知道这00.2如何分分配。值得注意的是， m(红)+mm(黄)+m(白白) =0.3+0+00.1=0.4<1因此，m不是概概率，因为概概率函数P要要求P(红)+P(黄)+P(白)=1即即有P(A)=1-P(A)而这里 m(A)11-m(A)其中：A=UU-A，是A的补集。小结：bpa不不同于Bayyes方法，因因为Bayees方法仅对对U中单个元元素赋予一种种信任概率。而而对于bpaa来说：l 给U的每个子集集指派0，11中的一个个数；l 空集的指派为00；l 所有子集的指派派值之和等于于1。l m(U)只是总总可信度的一一部分。在对对U中的适当子子集分派可信信度之后，剩剩余的可信度度就不再分派派给其它任何何子集，而只只分派给U本身。即：如如果有一证据据仅支持U的一个子集集A，m(A)=S，而不支支持其它任何何子集B，则指派m(U)=1-S，m(B)=0，BA，BU 。定义2：信任函函数（Bellief ffunctiion）：命题A的信任函函数Bel：2U0,1为 "AÍU表示对A的总信信任。即，命题A的信信任函数的值值，是A的所所有子集的基基本概率之和和。例如，在前面的的例子中Bel(红，白)=m(红)+m(白白)+m(红,白)=0.3+0.1+0.22=0.6根据定义可以看看出Bel()=00 Bel(U)=1单元素集上m与与Bel是相相等的，例如如:Bel(红)=m(红)=0.3。定义3：似然函函数（Plaausibiility functtion）：命题A的似然函函数Pl: 2U0,1为 "AÍU表示对于不否定定A的信任度度，是所有与与A相交的子子集的基本概概率之和。其其中：A=U-A，是是A的补集。信任函数与似然然函数有以下下的关系：0Bel(AA)Pl(A)1Pl(A)-BBel(A)表示示了既不信任任A也不信任任A的一种种度量，可表表示对命题AA是真是假不不知道的度量量。用记号ABel(AA)，Pl(A)来综合描述A的的不确定性。其其中，Bell(A)和PPl(A)分别表表示命题A的的下限函数和和上限函数。实际上m，Beel，Pl只要要知其一，必必可求得另两两个，但三个个函数有不同同含义。例如如，在前面的的例子中： m(红)=0.33Bel(红)=m(红)+mm( )=0.3+0=0.3 Pl(红)=1-Bell(红) =1-Bell (黄,白) =1- mm(黄)+m(白白)+m(黄,白) =1-(0+0.1+00) =0.9所以，红 Bel(红)，PPl(红) = 红 0.3，00.9。以下列举几个典典型值的含义义：A1，1 表示A为真。因为Bel(AA)=1， Bel(A)= 11- Pl(A)=0。A0，0 表示A为假。因为Bel(AA)=0, Bel(A)= 11- Pl(A)=1。 A0，1 表示对A一无所所知。因为：Bel(A)=0，说说明对A缺少少信任；Beel(A)=1- PPl(A)=0，说明对对A也缺少少信任。A0.6，11 表示对A部分信信任。因为Bel(AA)=0.66， Bel(A)=0。A0，0.44 表示对A部分分信任。因为Bel(AA)=0， Bel(A)=0.6。A0.3，00.9表示同时对A和和A部分信信任。(2) 证据描述述 设某个领领域的辨别框框U=S11,S2,Sn，m为22U上定义的基基本概率分配配函数，在下下面描述的算算法中，应满满足如下条件件： a) mm(Si)0, 对SiiU b) c) mm(U)=11- d) mm(A)=00, 对AÌU，且且|A|1（集合AA的元素个数数不为1，且且又不包括全全体元素）例如，U=红红，黄，白时下面的基基本概率分配配函数： m（红红，黄，白，红,黄,白白， ）=（0.6，00.2，0.1，0.11，0）其中，m（红红,黄）= m（红红,白）= m（黄黄,白）= 0。定义4（证据的的信任函数）：对任何命题AÍUU，其信任函函数为 BBel(A)= "AAÌU BBel(U)=定义5 (证据据的似然函数数)： 对任何何命题AÍU，其其似然函数为为 PPl(A)=1-Bell(A)=1- AÌU =11- =11-1-mm(U)-BBel(A) =mm(U)+BBel(A) 根据以以上定义，可可以看出命题题的信任函数数和似然函数数之间满足下下列关系：l Pl(A)³Beel(A)l Pl(A)-BBel(A)=m(U)除了以ABeel(A)，PPl(A)来来作为证据AA的不确定性性度量外，还还可用类概率率函数来度量量。定义6(类概率率函数)：设U为有限域，对对任何命题AAÍU，命题AA的类概率函函数为其中|A|、|U|分别表表示A和U所所含元素个数数。类概率函数具有有如下性质：1）2) Bell(A)Pl(A)， "AÍU3) =1-， "AÍU根据以上性质，可可以得出以下下推论：1) 2）3) 可以看出，类概概率函数与概概率函数具有有非常相似的的性质。 (3) 证据的组组合对于同样的证据据，由于来源源不同，会得得到不同的概概率分配函数数。Demppster提提出用正交和和来组合这些些函数。定义7(正交和和)：设m1,m2,mn为2U上的n个基基本概率分配配函数，它们们的正交和mm(A)=（mm1m2mn）（A）为为其中k-1=1-若k-10,则mi之间是矛盾盾的，没有联联合基本概率率分配函数。若若k-10,这样的mmi就确定一个个基本概率分分配函数。常常数k是根据据m1m2mn需对2U的所有元素素的基本概率率分配之和为为1来确定的的。(这种规定称作作Dempsster组合合规则，要求求m1m2mn提供的证据据满足某种独独立性条件)2. 规则的不不确定性度量量设某个领域的辨辨别框U=S1,Sn，命题A、BB、为U的子集集，推理规则则为EH，CF其中，E、H为为命题的逻辑辑组合，CFF为可信度因因子。命题和可信度因因子可表示为为A=a1, ak CF=(c1,ck)其中ci用来描描述ai的可信度，ii=1,2,k。对任何命题A，AA的可信度CCF应满足：1) ci0，1ik 2)3. 推理计算算(1) 当条件件部分为命题题的逻辑组合合时，整个条条件部分的确确定性计算：=min 合取=max 析取(2) 结论部部分的命题的的确定性计算算：即，已知，AB (c1,ck)，如何计计算。思路：根据前面面介绍的方法法，首先计算算基本分配函函数m(B),然后计算算结论部分命命题B的信任任函数Bell(B)、似似然函数Pll(B)，最后后计算类概率率函数和确定定性。 设B=b1,b2,bk，且U=b1,b2,bk，则U上的基本本概率分配函函数为 m(b11,bk) = (c1,ck) ci便可得。(3) 独立证证据导出同一一假设如果有n条规则则支持同一命命题时，根据据Dempsster组合合规则，总的的基本概率分分配函数m为为各规则结论论得到的基本本概率分配函函数的正交和和：m=m1m2mn例如，已知 A1B (c1, ck)A2B ()以及如何计算。首先计算总的基基本概率分配配函数m=mm1m2，然后计算算命题B的信信任函数、似似然函数，进进而可求出类类概率函数。例 U=aa,b,c,d （参见p1101）:b,c,dd0.7 U0.3:a,b 0.6 U0.4可列表求m=mm1m2m1m2 于是b0.442，a,b0.18, b,cc,d0.28U0.12 (=0.7(0.6+00.4)+0.3(0.6+00.4)=1)有了便可计算算，如()(a,bb)=m()+m(a)+m(b)+m(a,b)=0+0+0.42+0.18=0.60随之可计算，从从而可得4. 举例 （p1102）(1)已知 =0.8. =0.6) |U|=20 B=, ()=(0.3,00.5) 来计算。先计算=minn=min0.8,00.6=00.6 进而计算=(00.6×0.3,00.6×0.5)=(0.18,0.3) 于是有Bel(B)=m()十m()+m()+ =0+0.18+0.3+0=00.48 (依Ci定义, m()=0.118，m()=0.3，随之有有m(U)=1(0.18+0.3)=0.522，而对U的的其他子集的的m值均赋以以零) Pl(B)=11-Be1(B)=11-0=1最后得 =0.48+ (1-0.48)=00.53。(2)已知=00.53, =0.522,|U|=20。以及及B=，( )=(0.11,0.5,0.3)B=，()=(0.4,00.2,0.1)求。先求=(0.53××0.1,00.53×0.5,00.53×0.3)=(0.0053,0.265,OOJ59)(U)=1一(0.0533+0.2665+0.1159)=00.524=(0.52××0.4,00.52×0.2,00.52×0.1)=(0.2088,0.1004,0.0052)(U)=1-( 0.2008+0.1104+0.052)=0.6366以及m=()()+()(U)+ ()()+()(U)+( ()+()(U)+ (U)() +(U)() +(U)()+(U)(U) =0.8744得m()=()()+()(U)+(UU)() =0.176 m()=()()+()(U)+ (U)() =0.2999 m ()=()+()(U)+ (U)() =0.1577 m(U)=1-(0.1776+0.2299+0.157)=0.3688 于是 Bel(B)= mm()+m()+m ()=0.6332 Pl(B)=11最后得 =0.632十十(1-0.6632)·3/20=0.687 从代数数观点看，MMYCIN、EEMYCINN、PROSSPECTOOR、D-SS给出的不确确定方法均可可构成半群；MYCINN、D-S方方法还有单位位元但无逆元元；EMYCCIN、PRROSPECCTOR方法法既有单位元元又有逆元，从从而可构成群群。5. 本节小结结证据理论有如下下一些特点：1) 证据理论满足比比概率论更弱弱的公理系统统。当|A|>1，m(A)=0时时，证据理论论就退化为概概率论；当对对所有的m(Ai)¹0，有A1ÍA2ÍÍAn时，证据理理论退化为ZZadeh的的可能性理论论。2) 证据理论能够区区分不知道和和不确定。3) 证据理论可以处处理证据影响响一类假设的的情况，即证证据不仅能影影响一个明确确的假设（与与单元素子集集相对应）、还还可影响一个个更一般的不不明确的假设设（与非单元元素子集相对对应）。因此此，证据理论论可以在不同同细节、不同同水平上聚集集证据，更精精确地反应了了证据收集过过程。4) 证据理论的缺点点是：要求辨辨别框中的元元素满足相互互排斥的条件件，在实际系系统中不易满满足。而且，基基本概率分配配函数要求给给的值太多，计计算比较复杂杂。