DS证据理论PPT课件.ppt

《DS证据理论PPT课件.ppt》由会员分享，可在线阅读，更多相关《DS证据理论PPT课件.ppt（32页珍藏版）》请在三一办公上搜索。

1、证据理论,证据理论是由德普斯特（A.P.Dempster）首先提出，并由沙佛（GShafer）进一步发展起来的一种处理不确定性的理论，因此又称为DS理论。证据理论与Bayes理论区别：Bayes理论： 需要有统一的识别框架、完整的先验概率和条件概率知识， 只能将概率分派函数指定给完备的互不包含的假设，证据理论：用先验概率分派函数去获得后验的证据区间，证据区间量化了命题的可信程度。可将证据分派给假设或命题， 提供了一定程度的不确定性，即证据既可指定给互不相容的命题，也可指定给相互重叠、非互不相容的命题。证据理论满足比概率论更弱的公理系统，当概率值已知时，证据理论就变成了概率论。,D-S理论,基本

2、理论 一个具体的不确定性推理模型 举例 小结,基本理论,设D是变量x所有可能取值的集合，且D中的元素是互斥的，在任一时刻x都取且只能取D中的某一个元素为值，则称D为x的样本空间，也称D为辨别框 。在证据理论中，D的任何一个子集A都对应于一个关于x的命题，称该命题为“x的值在A中”。 引入三个函数：概率分配函数，信任函数及似然函数等概念。,概率分配函数,设D为样本空间，领域内的命题都用D的子集表示，则概率分配函数定义如下：定义1： 设函数M：2D0，1，且满足M（）0 M（A）1AD则称M是2D上的概率分配函数，M（A）称为A的基本概率数。,说明 ：设样本空间D中有n个元素，则D中子集的个数为2

3、n个，定义中的2D就是表示这些子集的。 概率分配函数的作用是把D的任意一个子集A都映射为0，1上的一个数M（A）。当AD时，M（A）表示对相应命题的精确信任度。实际上就是对D的各个子集进行信任分配，M（A）表示分配给A的那一部分。当A由多个元素组成时，M(A)不包括对A的子集的精确信任度，而且也不知道该对它如何进行分配。当AD时，M（A）是对D的各子集进行信任分配后剩下的部分，它表示不知道该对这部分如何进行分配。 定义：若AD则M(A)0，称A为M的一个焦元。概率分配函数不是概率。,信任函数,定义2 :命题的信任函数Bel：2D0，1，且Bel(A）M（B）对所有的AD BA其中2D表示D的所

4、有子集。 Bel函数又称为下限函数，Bel（A）表示对命题A为真的信任程度。由信任函数及概率分配函数的定义推出：Bel（）M（）0Bel（D）M（B）1 BD,似然函数,定义3: 似然函数Pl：2D0，1，且 Pl（A）1一Bel（A） 其中AD 似然函数的含义：由于Bel(A)表示对A为真的信任程度，所以Bel(A)就表示对非A为真，即A为假的信任程度，由此可推出Pl（A）表示对A为非假的信任程度。似然函数又称为不可驳斥函数或上限函数。,推广到一般情况可得出：Pl(A)= M(B) AB证明如下：Pl(A) M(B) 1-Bel(A)- M(B) AB AB 1-(Bel(A)+ M(B)

5、AB 1-( M(C)+ M(B) CA AB 1- M(E) ED 0Pl（A）M（B） AB,信任函数与似然函数的关系,Pl（A）Bel（A） 证明： Bel（A）十Bel（A）M（B）M（C） BA CAM（E）1 EDPl（A）Bel（A）1Bel（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为真。 Bel Pl （0，0）A为假。 确知 未知 确知（0，1）对A一

6、无所知，单位元。 为真为假Pl(A)Bel(A) 对A不知道的程度。下面用例子进一步说明下限与上限的意义：A（0.25，1）：由于Bel（A）0.25，说明对A为真有一定程度的信任，信任度为0.25；另外，由于Bel（A）1Pl（A）0，说明对A不信任。所以A（0.25，1）表示对A为真有0.25的信任度。A（0，085）：由于Bel（A）0，而Bel（A）1一Pl（A）10.850.15，所以A（0，0.85）表示对A为假有一定程度的信任，信任度为0.15。A（0.25，0.85）：由于Bel（A）0.25，说明对A为真有0.25的信任度；由于Bel（A）10.850.15，说明对A为假有0

7、.15的信任度。所以A（0.25，0.85）表示对A为真的信任度比对A为假的信任度稍高一些。,概率分配函数的正交和,定义4 :设M1和M2是两个概率分配函数，则其正交 和M= M1 M2为M()=0M(A)=K1M1(x)M2(y) xy=A其中:K=1-M1(x)M2(y)=M1(x)M2(y) xy= xy如果K0,则正交和M也是一个概率分配函数；如果K=0，则不存在正交和M，称M1 与M2矛盾。,定义5 ：设M1,M2,，Mn是n个概率分配函数，则其正交和MM1M2Mn为M()=0M(A)=K1 Mi(Ai) Ai =A 1in其中:K= Mi(Ai) Ai 1in例：设D黑，白，且 M

8、1(黑,白,黑,白,)=(0.3,0.5,0.2,0) M2(黑,白,黑,白,)=(0.6,0.3,0.1,0)K=1-M1(x)M2(y)=0.61 xy= M(黑)K1M1(x)M2(y)0.54 xy=黑同理可得 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分别表示规则强度的下限与上限。 在此表示的基础上建立相应的不

9、确定性推理模型。 由于信任函数与似然函数都是在概率分配函数的基础上定义的，因而随着概率分配函数的定义不同，将会产生不同的应用模型。,概率分配函数与类概率函数,样本空间Ds1，s2,sn上的概率分配函数按如下要求定义：（1）M（si）0 对任何siD n（2）M（si）1 il n（3）M（D）1-M（si） i=1（4）当AD且|A|1或|A|0时，M（A）=0 其中，|A|表示命题A对应集合中元素的个数。,性质：Bel（A）M（si） siA nBel（D）M（si）M（D）1 ilPl（A）1Bel（A）1M（si） siA n 1M（si）M（si） i1 siA 11M(D) Bel(

10、A) M(D)+Bel(A)Pl(D)=1-Bel(D) =1-Bel()=1显然，对任何AD及BD均有：Pl(A)-Bel(A)=Pl(B)-Bel(B)=M(D)它表示对A（或B）不知道的程度。,由该概率分配函数的定义，可把概率分配函数M1与M2的正交和简化为M（si）K-1Ml（si）M2（si）M1（si）M2（D）M1（D）M2（si） 其中，K可由下式计算：KM1（D）M2（D）+ nM1（si）M2（si）+M1（si） i=1M2（D）M1（D）x M2（si）,定义6 :命题A的类概率函数为f（A）=Bel（A） Pl（A）一Bel（A）其中，A丨和D分别是A及D中元素的个数

11、。f（A）具有如下性质： n（1）f（si）1 i1（2）对任何AD，有 Bel（A）f（A）Pl（A）f（A）1 - f（A）由以上性质可得到如下推论：（1）f（）=0（2）f（D）1（3）对任何AD，有 0f（A）1,|A|,|D|,知识不确定性的表示,在该模型中，不确定性知识用如下形式的产生式规则表示：IF E THEN Hh1,h2,hn CFc1，c2，Cn其中：（1）E为前提条件，它既可以是简单条件，也可以是用 AND或OR连接起来的复合条件。（2）H是结论,它用样本空间中的子集表示，h1,h2，, hn 是该子集中的元素。（3）CF是可信度因子，用集合形式表示，其中ci用来指出

12、hi（i1，2，n）的可信度，ci与hi一一对应。Ci 应满足如下条件： ci0 i1,2,，n ci1 i1,证据不确定性的表示,不确定性证据E的确定性用CER（E）表示。对于初始证据，其确定性一般由用户给出；对于用前面推理所得结论作为当前推理的证据，其确定性由推理得到。CER（E）的取值范围为0，1，即0CER（E）1,组合证据不确定性的算法,当组合证据是多个证据的合取时，即EE1 AND E2 AND AND En则E的确定性CER（E）为：CER（E）minCER（El），CER（E2），CER（En）当组合证据是多个证据的析取时，即EEl OR E2 OR OR En 则E的确定性C

13、ER（E）为CER（E）maxCER（El），CER（E2），,CER(En),不确定性的传递算法,对于知识：IF E THEN Hh1,h2,hn CF=c1,c2,cn结论H的确定性可通过下述步骤求出： （1）求出H的概率分配函数。对上述知识，H的概率分配函数为：M（hl，h2，hn）CER（E）c1，CER（E）c2，CER（E）cnM（D）1 CER（E）ciil,如果有两条知识支持同一结论H，即IF E1 THEN Hhl，h2，,hn CF c1,c2,cn IF E2 THEN Hhl，h2，,hn CF c1,c2,cn 则首先分别对每一条知识求出概率分配函数：M1（hl，h2

14、，,hn）M2（hl，h2，,hn）然后再用公式MM1M2对M1与M2求正交和，从而得到H的概率分配函数M。如果有n条知识都支持同一结论H，则用公式MM1M2Mn对M1，M2，Mn求其正交和，从而得到H的概率分配函数M。,（2）求出Bel（H），Pl（H）及f（H）其中： n Bel（H）M（hi） i=1 Pl（H）1Bel（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的匹配度，定义为：这样，就对一条知识或

15、者多条有相同结论的知识求出了结论的确定性。如果该结论不是最终结论，即它又要作为另一条知识的证据继续进行推理，则重复上述过程就可得到新的结论及其确定性。如此反复运用该过程，就可推出最终结论及它的确定性。,MD(H/E)=,1 如果H所要求的证据都已出现,0 否则,举例,设有如下推理规则：rule1: if E1 and E2 then A=a1,a2,CF=0.3,0.5rule2: if E3 and (E4 or E5) then N=n1,CF=0.7rule3: if A then H=h1,h2,h3,CF=0.1,0.5,0.3rule4: if N then H=h1,h2,h3,

16、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.7。现要求假设H的确定性（假设|=20）。,推理网络图：,H,A,N,E1,E2,E3,E4,E5,=H1,H2,H3,=a1,a2,=n1,and,and,or,求解步骤如下：（1）求CER(A)规则rule1条件部分的确定性为CER(E)=CER(E1 AND E2) =min0.8,0.6=0.6因此有m(a1,a2)=0.60.3,0.60.5=0.18,0.3再根据m求Bel(A

17、)、Pl（A）、及CER（A）:Bel(A)=m(a1)+m(a2)=0.18+0.3=0.48Pl(A)Bel(A)=m()=1（0.18+0.3）=0.52 f(A)=Bel(A)+ Pl(A)Bel(A) =0.48+(2/20)0.52=0.532CER(A)=MD(A,E)f(A)=0.532,|A|,|,（2）求CER(N)规则rule2条件部分的确定性为CER(E)=CER(E3 AND (E4 OR E5)=0.7因此有m(n1)=0.70.7=0.49再根据m求Bel(N)、Pl（N）、f（N）及CER(N):Bel(N)=m(n1)=0.49Pl(N)Bel(N)=m（）1

18、0.49=0.51f(N)=0.49+(1/20)0.51=0.515 CER(N)=MD(N,E)f(N)=0.515,（3）求CER(H)根据rule3，可求得m1(h1,h2,h3)=0.5320.1, 0.5320.5, 0.5320.3 =0.053,0.266,0.160及 m1()=1(0.053+0.266+0.160)=0.521根据rule4，可求得m2(h1,h2，h3)=0.5150.4, 0.5150.2, 0.5150.1 =0.206,0.103,0.052及 m2()=1(0.206+0.103+0.052)=0.639求正交和m=m1m2:k=m1()m2()

19、+m1(h1) m2(h2)+ m1(h1) m2()+ m1() m2(h1)+m1(h2) m2(h2) + m1(h1) m2()+ m1() m2(h2)+m1(h3) m2(h3)+ m1(h3) m2()+ m1() m2(h3)=0.874,m(h1)=1/km1(h1)m2(h1)+m1(h1) m2()+m1() m2(h1)=1/0.8740.0530.206+0.0530.639+0.5210.206=0.174同理得m(h2)=0.287，m(h3)=0.157m()=1m(h1)+m(h2)+m(h3) =1(0.174+0.287+0.157)=0.382再根据m求

20、Bel(H)、Pl（H）、f(H)及CER(H):Bel(H)=m(h1)+m(h2)+m(h3) =0.174+0.287+0.157=0.618Pl(H)Bel(H)=m()=10.618=0.382f(H)=Bel(H)+ Pl(H)Bel(H) =0.618+（3/20）0.382=0.675CER(H)=MD(H,E) f(H)=0.675,|H|,|,小结,证据理论有如下一些特点：证据理论满足比概率论更弱的公理系统。当m的焦元都是单元素集合时，即若|A|1 则m（A）0时，证据理论就退化为概率论； 当m的焦元呈有序的嵌套结构时， 即对所有的m（Ai）0，有A1A2An时，证据理论退化为Zadeh的可能性理论。证据理论能够区分不知道和不确定。证据理论可以处理证据影响一类假设的情况，即证据不仅能影响一个明确的假设（与单元素子集相对应），还可以影响一个更一般的不明确的假设（与单元素子集相对应）。因此，证据理论可以在不同细节、不同水平上聚集证据，更精确的反映了证据收集过程。证据理论的缺点是:要求辨别框中的元素满足相互排斥的条件，在实际系统中不易满足。而且，基本概率分配函数要求给的值太多，计算比较复杂。,