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

3.4证据理论0.前言主观Bayes方法必须给出先验概率。Dempster和Shafer提出的证据理论，可用来处理这种由不知道所引起的不确定性。证据理论采用信任函数而不是概率作为不确定性度量，它通过对一些事件的概率加以约束来建立信任函数而不必说明精确的难于获得的概率。证据理论满足比概率论更弱的公理系统，当这种约束限制为严格的概率时（即概率值已知时），证据理论就退化为概率论了。1.证据的不确定性度量(1)基本理论辨别框概念：设U为假设x的所有可能的穷举集合，且设U中的各元素间是互斥的，我们称U为辨别框（Frameofdiscernment）。设U的元素个数为N，则U的幂集合2U的元素个数为2N，每个幂集合的元素对应于一个关于x取值情况的命题（子集）。对任一AU，命题A表示了某些假设的集合(这样的命题间不再有互斥性)。针对医疗诊断问题，U就是所有可能疾病(假设)的集合，诊断结果必是U中确定的元素构成的。A表示某一种(单元素)或某些种疾病。医生为了进行诊断所进行的各种检查就称作证据，有的证据所支持的常不只是一种疾病而是多种疾病，即U的一子集A。定义1：基本概率分配函数（Basicprobabilityassignment）：对任一个属于U的子集A（命题），命它对应于一个数m∈[0,1]，而且满足UAAmm1)(0)(则称函数m为幂集2U上的基本概率分配函数bpa，称m(A)为A的基本概率数。m(A)表示了证据对U的子集A成立的一种信任的度量，取值于[0,1]，而且2U中各元素信任的总和为1。m(A)的意义为若AU且AU，则m(A)表示对A的确定信任程度。若A=U，则m(A)表示这个数不知如何分配（即不知道的情况）。例如，设U={红，黄，白}，2U上的基本概率分配函数m为m（{}，{红}，{黄}，{白}，{红,黄}，{红,白}，{黄,白}，{红,黄,白}）=（0，0.3，0，0.1，0.2，0.2，0，0.2）其中，m({红})=0.3表示对命题{红}的确定信任度。m({红,黄,白})=0.2表示不知道这0.2如何分配。值得注意的是，m({红})+m({黄})+m({白})=0.3+0+0.1=0.41因此，m不是概率，因为概率函数P要求P(红)+P(黄)+P(白)=1即有P(A)=1-P(~A)而这里m(A)1-m(~A)其中：~A=U-A，是A的补集。小结：bpa不同于Bayes方法，因为Bayes方法仅对U中单个元素赋予一种信任――概率。而对于bpa来说：给U的每个子集指派[0，1]中的一个数；空集的指派为0；所有子集的指派值之和等于1。m(U)只是总可信度的一部分。在对U中的适当子集分派可信度之后，剩余的可信度就不再分派给其它任何子集，而只分派给U本身。即：如果有一证据仅支持U的一个子集A，m(A)=S，而不支持其它任何子集B，则指派m(U)=1-S，m(B)=0，B≠A，BU。定义2：信任函数（Belieffunction）：命题A的信任函数Bel：2U→[0,1]为ABBmABel)()(AU表示对A的总信任。即，命题A的信任函数的值，是A的所有子集的基本概率之和。例如，在前面的例子中Bel({红}，{白})=m({红})+m({白})+m({红,白})=0.3+0.1+0.2=0.6根据定义可以看出Bel()=0Bel(U)=1单元素集上m与Bel是相等的，例如:Bel({红})=m({红})=0.3。定义3：似然函数（Plausibilityfunction）：命题A的似然函数Pl:2U→[0,1]为ABBmABelAPl)()(~1)(AU表示对于不否定A的信任度，是所有与A相交的子集的基本概率之和。其中：～A=U-A，是A的补集。信任函数与似然函数有以下的关系：0≤Bel(A)≤Pl(A)≤1Pl(A)-Bel(A)表示了既不信任A也不信任~A的一种度量，可表示对命题A是真是假不知道的度量。用记号A[Bel(A)，Pl(A)]来综合描述A的不确定性。其中，Bel(A)和Pl(A)分别表示命题A的下限函数和上限函数。实际上m，Bel，Pl只要知其一，必可求得另两个，但三个函数有不同含义。例如，在前面的例子中：m({红})=0.3Bel({红})=m({红})+m({})=0.3+0=0.3Pl({红})=1-Bel({~红})=1-Bel({黄,白})=1-[m({黄})+m({白})+m({黄,白})]=1-(0+0.1+0)=0.9所以，{红}[Bel({红})，Pl({红})]={红}[0.3，0.9]。以下列举几个典型值的含义：A[1，1]表示A为真。因为Bel(A)=1，Bel(~A)=1-Pl(A)=0。A[0，0]表示A为假。因为Bel(A)=0,Bel(~A)=1-Pl(A)=1。A[0，1]表示对A一无所知。因为：Bel(A)=0，说明对A缺少信任；Bel(~A)=1-Pl(A)=0，说明对~A也缺少信任。A[0.6，1]表示对A部分信任。因为Bel(A)=0.6，Bel(~A)=0。A[0，0.4]表示对~A部分信任。因为Bel(A)=0，Bel(~A)=0.6。A[0.3，0.9]表示同时对A和~A部分信任。(2)证据描述设某个领域的辨别框U={S1,S2,…,Sn}，m为2U上定义的基本概率分配函数，在下面描述的算法中，应满足如下条件：a)m({Si})≥0,对Si∈Ub)1})({1niiSmc)m(U)=1-niiSm1})({d)m(A)=0,对AU，且|A|≠1（集合A的元素个数不为1，且又不包括全体元素）例如，U={红，黄，白}时下面的基本概率分配函数：m（{红}，{黄}，{白}，{红,黄,白}，{}）=（0.6，0.2，0.1，0.1，0）其中，m（{红,黄}）=m（{红,白}）=m（{黄,白}）=0。定义4（证据的信任函数）：对任何命题AU，其信任函数为Bel(A)=ABAaamBm})({)(AUBel(U)=UBUaUmamBm1)(})({)(定义5(证据的似然函数)：对任何命题AU，其似然函数为Pl(A)=1-Bel(～A)=1-Aaam})({AU=1-UaAbbmam})]({})({[=1-[1-m(U)-Bel(A)]=m(U)+Bel(A)根据以上定义，可以看出命题的信任函数和似然函数之间满足下列关系：Pl(A)Bel(A)Pl(A)-Bel(A)=m(U)除了以A[Bel(A)，Pl(A)]来作为证据A的不确定性度量外，还可用类概率函数来度量。定义6(类概率函数)：设U为有限域，对任何命题AU，命题A的类概率函数为))()((||||)()(1ABelAPlUAABelAf其中|A|、|U|分别表示A和U所含元素个数。类概率函数)(1Af具有如下性质：1）Uaaf1})({12)Bel(A)≤)(1Af≤Pl(A)，AU3))~(1Af=1-)(1Af，AU根据以上性质，可以得出以下推论：1)0)(1f2）1)(1Uf3)UAAf对,1)(01可以看出，类概率函数与概率函数具有非常相似的性质。(3)证据的组合对于同样的证据，由于来源不同，会得到不同的概率分配函数。Dempster提出用正交和来组合这些函数。定义7(正交和)：设m1,m2,…,mn为2U上的n个基本概率分配函数，它们的正交和m(A)=（m1m2…mn）（A）为AAnii1iiA),(Amkm(A)A0,=)m(其中k-1=1-)()(11iAniiAniiiAmAmii若k-1＝0,则mi之间是矛盾的，没有联合基本概率分配函数。若k-1≠0,这样的mi就确定一个基本概率分配函数。常数k是根据m1m2…mn需对2U的所有元素的基本概率分配之和为1来确定的。(这种规定称作Dempster组合规则，要求m1m2…mn提供的证据满足某种独立性条件)2.规则的不确定性度量设某个领域的辨别框U={S1,…,Sn}，命题A、B、…为U的子集，推理规则为E→H，CF其中，E、H为命题的逻辑组合，CF为可信度因子。命题和可信度因子可表示为A={a1,…,ak}CF=(c1,…,ck)其中ci用来描述ai的可信度，i=1,2,…,k。对任何命题A，A的可信度CF应满足：1)ci≥0，1≤i≤k2)11kjjc3.推理计算(1)当条件部分为命题的逻辑组合时，整个条件部分的确定性计算：)(211AAf=min{)(),(2111AfAf}合取)(211AAf=max{)(),(2111AfAf}析取(2)结论部分的命题的确定性计算：即，已知)(1Af，A→B(c1,…,ck)，如何计算)(1Bf。思路：根据前面介绍的方法，首先计算基本分配函数m(B),然后计算结论部分命题B的信任函数Bel(B)、似然函数Pl(B)，最后计算类概率函数和确定性。设B={b1,b2,…,bk}，且U={b1,b2,…,bk}，则U上的基本概率分配函数为m({b1},…,{bk})=()(1Afc1,…,)(1Afck)kiAfUm11)(1)(ci便可得)(1Bf。(3)独立证据导出同一假设如果有n条规则支持同一命题时，根据Dempster组合规则，总的基本概率分配函数m为各规则结论得到的基本概率分配函数的正交和：m=m1m2…mn例如，已知A1→B(c1,…,ck)A2→B('c,,'ck1)以及)(),(2111AfAf如何计算)(1Bf。首先计算总的基本概率分配函数m=m1m2，然后计算命题B的信任函数、似然函数，进而可求出类概率函数)(1Bf。例U={a,b,c,d}（参见p101）1m:{b,c,d}→0.7U→0.32m:{a,b}→0.6U→0.4可列表求m=m1m2m1m27.0},,{dcb3.0U6.0},{ba4.0U6.07.0}{b3.06.0},{ba4.07.0},,{dcb3.04.0U于是21mm{b}→0.42，{a,b}→0.18,{b,c,d}→0.28U→0.12(YX(Y)m(X)mK211-=0.7(0.6+0.4)+0.3(0.6+0.4)=1)有了21mm便可计算21BelBel，如(21BelBel)({a,b})=},{11)(baBBm=m()+m({a})+m({b})+m({a,b})=0+0+0.42+0.18=0.60随之可计算21PlPl，从而可得)(1Bf4.举例（p102）(1)已知)(11Af=0.8.)(21Af=0.6)|U|=2021AA→B={1b,2b}(2,1cc)=(0.3,0.5)来计算)(1Bf。先计算)(211AAf=min{)(),(2111AfAf}=min{0.8,0.6}=0.6进而计算}){},({21bbm=(0.6×0.3,0.6×0.5)=(0.18,0.3)于是有Bel(B)=m()十m({1b})+m({2b})+}){},({21bbm=0+0.18+0.3+0=0.48(依Ci定义,m({1b})=0.18，m({2b})=0.3，随之有m(U)=1－(0.18+0.3)=0.52，而对U的其他子集的m值均赋以零)Pl(B)=1-Be1(~B)=1-0=1最后得))()((||||)()(1BBelBPlUBBBelBf=0.48+202(1-0.48)=0.53。(2)已知)(11Af=0.53,)(21Af=0.52,|U|=20。以及1A→B={321b,b,b}，(3C21c,c)=(0.1,0.5,0.3)2A→B={321b,b,b}，(3C21c,c)=(0.4,0.2,0.1)求)(1Bf。先求}){},{},({321bbbm=(0.53×