DS证据理论课件

证据理论证据理论是由德普斯特（A.P.Dempster）首先提出，并由沙佛（G．Shafer）进一步发展起来的一种处理不确定性的理论，因此又称为D－S理论。证据理论与Bayes理论区别：Bayes理论：需要有统一的识别框架、完整的先验概率和条件概率知识，只能将概率分派函数指定给完备的互不包含的假设，证据理论：用先验概率分派函数去获得后验的证据区间，证据区间量化了命题的可信程度。可将证据分派给假设或命题，提供了一定程度的不确定性，即证据既可指定给互不相容的命题，也可指定给相互重叠、非互不相容的命题。证据理论满足比概率论更弱的公理系统，当概率值已知时，证据理论就变成了概率论。D-S理论一．基本理论二．一个具体的不确定性推理模型三．举例四．小结一．基本理论设D是变量x所有可能取值的集合，且D中的元素是互斥的，在任一时刻x都取且只能取D中的某一个元素为值，则称D为x的样本空间，也称D为辨别框。在证据理论中，D的任何一个子集A都对应于一个关于x的命题，称该命题为“x的值在A中”。引入三个函数：概率分配函数，信任函数及似然函数等概念。1.概率分配函数设D为样本空间，领域内的命题都用D的子集表示，则概率分配函数定义如下：定义1：设函数M：2D→［0，1］，且满足M（Φ）＝0ΣM（A）＝1A⊆D则称M是2D上的概率分配函数，M（A）称为A的基本概率数。说明：1.设样本空间D中有n个元素，则D中子集的个数为2n个，定义中的2D就是表示这些子集的。2.概率分配函数的作用是把D的任意一个子集A都映射为［0，1］上的一个数M（A）。当A⊂D时，M（A）表示对相应命题的精确信任度。实际上就是对D的各个子集进行信任分配，M（A）表示分配给A的那一部分。当A由多个元素组成时，M(A)不包括对A的子集的精确信任度，而且也不知道该对它如何进行分配。当A＝D时，M（A）是对D的各子集进行信任分配后剩下的部分，它表示不知道该对这部分如何进行分配。定义：若A⊆D则M(A)≠0，称A为M的一个焦元。3.概率分配函数不是概率。2.信任函数定义2:命题的信任函数Bel：2D→［0，1］，且Bel(A）＝ΣM（B）对所有的A⊆DB⊆A其中2D表示D的所有子集。Bel函数又称为下限函数，Bel（A）表示对命题A为真的信任程度。由信任函数及概率分配函数的定义推出：Bel（Φ）＝M（Φ）＝0Bel（D）＝ΣM（B）＝1B⊆D3.似然函数定义3:似然函数Pl：2D→［0，1］，且Pl（A）＝1一Bel（￢A）其中A⊆D似然函数的含义：由于Bel(A)表示对A为真的信任程度，所以Bel(￢A)就表示对非A为真，即A为假的信任程度，由此可推出Pl（A）表示对A为非假的信任程度。似然函数又称为不可驳斥函数或上限函数。推广到一般情况可得出：Pl(A)=∑M(B)A∩B≠Φ证明如下：∴Pl(A)－∑M(B)＝1-Bel(￢A)-∑M(B)A∩B≠ΦA∩B≠Φ＝1-(Bel(￢A)+∑M(B))A∩B≠Φ＝1-(∑M(C)+∑M(B))C⊆￢AA∩B≠Φ＝1-∑M(E)E⊆D＝0∴Pl（A）＝ΣM（B）A∩B≠Φ4.信任函数与似然函数的关系Pl（A）≥Bel（A）证明：∵Bel（A）十Bel（￢A）＝ΣM（B）＋ΣM（C）B⊆AC⊆￢A≤ΣM（E）＝1E⊆D∴Pl（A）－Bel（A）＝1－Bel（￢A）一Bel（A）＝1－（Bel（￢A）＋Bel（A））≥0∴Pl（A）≥Bel（A）由于Bel（A）表示对A为真的信任程度，Pl（A）表示对A为非假的信任程度，因此可分别称Bel（A）和Pl(A）为对A信任程度的下限与上限，记为A（Bel（A），Pl（A））01（1，1）—A为真。BelPl（0，0）—A为假。确知未知确知（0，1）—对A一无所知，单位元。为真为假Pl(A)－Bel(A)—对A不知道的程度。下面用例子进一步说明下限与上限的意义：A（0.25，1）：由于Bel（A）＝0.25，说明对A为真有一定程度的信任，信任度为0.25；另外，由于Bel（￢A）＝1－Pl（A）＝0，说明对￢A不信任。所以A（0.25，1）表示对A为真有0.25的信任度。A（0，0．85）：由于Bel（A）＝0，而Bel（￢A）＝1一Pl（A）＝1－0.85＝0.15，所以A（0，0.85）表示对A为假有一定程度的信任，信任度为0.15。A（0.25，0.85）：由于Bel（A）＝0.25，说明对A为真有0.25的信任度；由于Bel（￢A）＝1－0.85＝0.15，说明对A为假有0.15的信任度。所以A（0.25，0.85）表示对A为真的信任度比对A为假的信任度稍高一些。5.概率分配函数的正交和定义4:设M1和M2是两个概率分配函数，则其正交和M=M1⊕M2为M(Φ)=0M(A)=K－1×∑M1(x)×M2(y)x∩y=A其中:K=1-∑M1(x)×M2(y)=∑M1(x)×M2(y)x∩y=Φx∩y≠Φ如果K≠0,则正交和M也是一个概率分配函数；如果K=0，则不存在正交和M，称M1与M2矛盾。定义5：设M1,M2,……，Mn是n个概率分配函数，则其正交和M＝M1⊕M2⊕……⊕Mn为M(Φ)=0M(A)=K－1×∑∏Mi(Ai)∩Ai=A1in其中:K=∑∏Mi(Ai)∩Ai≠Φ1in例：设D＝{黑，白}，且M1({黑},{白},{黑,白},Φ)=(0.3,0.5,0.2,0)M2({黑},{白},{黑,白},Φ)=(0.6,0.3,0.1,0)K=1-∑M1(x)×M2(y)=0.61x∩y=ΦM({黑})＝K－1×∑M1(x)×M2(y)＝0.54x∩y={黑}同理可得M({白})=0.43,M({黑,白})=0.03所以，组合后的概率分配函数为M({黑},{白},{黑,白},Φ)=(0.54,0.43,0.03,0)二．一个具体的不确定性推理模型信任函数Bel（A）和似然函数Pl（A）分别表示对命题A信任程度的下限与上限，两元组（Bel（A），Pl（A））表示证据的不确定性，不确定性知识用Bel和Pl分别表示规则强度的下限与上限。在此表示的基础上建立相应的不确定性推理模型。由于信任函数与似然函数都是在概率分配函数的基础上定义的，因而随着概率分配函数的定义不同，将会产生不同的应用模型。1.概率分配函数与类概率函数样本空间D＝{s1，s2,…,sn}上的概率分配函数按如下要求定义：（1）M（{si}）≥0对任何si∈Dn（2）ΣM（{si}）≤1i＝ln（3）M（D）＝1-ΣM（{si}）i=1（4）当A⊂D且|A|＞1或|A|＝0时，M（A）=0其中，|A|表示命题A对应集合中元素的个数。性质：Bel（A）＝ΣM（{si}）si∈AnBel（D）＝ΣM（{si}）＋M（D）＝1i＝lPl（A）＝1—Bel（￢A）＝1—ΣM（{si}）si∈￢An＝1—[ΣM（{si}）－ΣM（{si}）]i＝1si∈A＝1—[1—M(D)—Bel(A)]＝M(D)+Bel(A)Pl(D)=1-Bel(￢D)=1-Bel(Φ)=1显然，对任何A⊂D及B⊂D均有：Pl(A)-Bel(A)=Pl(B)-Bel(B)=M(D)它表示对A（或B）不知道的程度。由该概率分配函数的定义，可把概率分配函数M1与M2的正交和简化为M（{si}）＝K-1×［Ml（{si}）×M2（{si}）＋M1（{si}）×M2（D）＋M1（D）×M2（{si}）］其中，K可由下式计算：K＝M1（D）×M2（D）+nΣ［M1（{si}）×M2（{si}）+M1（{si}）×i=1M2（D）＋M1（D）xM2（{si}）］定义6:命题A的类概率函数为f（A）=Bel（A）＋×［Pl（A）一Bel（A）］其中，｜A丨和｜D｜分别是A及D中元素的个数。f（A）具有如下性质：n（1）Σf（{si}）＝1i＝1（2）对任何A⊆D，有Bel（A）≤f（A）≤Pl（A）f（￢A）＝1-f（A）由以上性质可得到如下推论：（1）f（Φ）=0（2）f（D）＝1（3）对任何A⊆D，有0≤f（A）≤1|A||D|2.知识不确定性的表示在该模型中，不确定性知识用如下形式的产生式规则表示：IFETHENH＝{h1,h2,…,hn}CF＝{c1，c2，…，Cn}其中：（1）E为前提条件，它既可以是简单条件，也可以是用AND或OR连接起来的复合条件。（2）H是结论,它用样本空间中的子集表示，h1,h2，…,hn是该子集中的元素。（3）CF是可信度因子，用集合形式表示，其中ci用来指出hi（i＝1，2，…，n）的可信度，ci与hi一一对应。Ci应满足如下条件：ci≥0i＝1,2,…，nΣci≤1i＝13.证据不确定性的表示不确定性证据E的确定性用CER（E）表示。对于初始证据，其确定性一般由用户给出；对于用前面推理所得结论作为当前推理的证据，其确定性由推理得到。CER（E）的取值范围为［0，1］，即0≤CER（E）≤14.组合证据不确定性的算法当组合证据是多个证据的合取时，即E＝E1ANDE2AND…ANDEn则E的确定性CER（E）为：CER（E）＝min{CER（El），CER（E2），…，CER（En）}当组合证据是多个证据的析取时，即E＝ElORE2OR…OREn则E的确定性CER（E）为CER（E）＝max{CER（El），CER（E2），…,CER(En)}5.不确定性的传递算法对于知识：IFETHENH＝{h1,h2,…,hn}CF={c1,c2,…,cn}结论H的确定性可通过下述步骤求出：（1）求出H的概率分配函数。对上述知识，H的概率分配函数为：M（{hl}，{h2}，…，{hn}）＝{CER（E）×c1，CER（E）×c2，…，CER（E）×cn}M（D）＝1－ΣCER（E）×cii＝l如果有两条知识支持同一结论H，即IFE1THENH＝{hl，h2，…,hn}CF＝{c1,c2,…,cn}IFE2THENH＝{hl，h2，…,hn}CF＝{c1’,c2’,…,cn’}则首先分别对每一条知识求出概率分配函数：M1（{hl}，{h2}，…,{hn}）M2（{hl}，{h2}，…,{hn}）然后再用公式M＝M1⊕M2对M1与M2求正交和，从而得到H的概率分配函数M。如果有n条知识都支持同一结论H，则用公式M＝M1⊕M2⊕…⊕Mn对M1，M2，…，Mn求其正交和，从而得到H的概率分配函数M。（2）求出Bel（H），Pl（H）及f（H）其中：nBel（H）＝ΣM（{hi}）i=1Pl（H）＝1－Bel（￢H）f(H）＝Bel(H)＋×［Pl(H)－Bel(H)］＝Bel(H)＋×M（D）|H||D||H||D|（3）按如下公式求出H的确定性CER（H）CER（H）＝MD（H/E’）×f（H）其中MD（H/E’）是知识的前提条件与相应证据E’的匹配度，定义为：这样，就对一条知识或者多条有相同结论的知识求出了结论的确定性。如果该结论不是最终结论，即它又要作为另一条知识的证据继续进行推理，则重复上述过程就可得到新的结论及其确定性。如此反复运用该过程，就可推出最终结论及它的确定性。MD(H/E’)=1如果H所要求的证据都已出现0否则三．举例设有如下推理规则：rule1:ifE1andE2thenA={a1,a2},CF={0.3,0.5}rule2:ifE3and(E4orE5)thenN={n1},CF={0.7}rule3:ifAthenH={h1,h2,h3},CF={0.1,0.5,0.3}rule4:ifNthenH={h1,h2,h3},CF={0.4,0.2,0.1}根据上述规则得到的推理网络如下图所示。给出的初始证据的确定性为：CER(E1)=0.8,CER(E2)=0.6,CER(E3)=0.9,CER(E4)=0.5,CER(E5)=0.