2013证据理论.ppt

《2013证据理论.ppt》由会员分享，可在线阅读，更多相关《2013证据理论.ppt（68页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2023/3/41 证据理论(Theory of Evidence)也称为D-S(Dempster-Shafer)理论。证据理论(D-S理论)最早是基于德姆斯特(A.P.Dempster)所做的工作，他试图用一个概率范围而不是单个的概率值去模拟不确定性。证据理论证据理论 1 1、证据理论的诞生和形成、证据理论的诞生和形成 诞生诞生：源于20世纪60年代美国哈佛大学数学家A.P.Dempster在利用上、下限概率来解决多值映射问题利用上、下限概率来解决多值映射问题方面的研究工作。自1967年起连续发表了一系列论文，标志着证据理论的正式诞生。形成形成：Dempster的学生G.Shafer对证据理

2、论做了进一步的发展，引入信任函数信任函数概念，形成了一套基于“证据”和“组合”来处理不确定性推理问题的数学方法，并于1976年出版了证据的数学理论(A Mathematical Theory of Evidence)，这标志着证据理论正式成为一种处理不确定性问题的完整理论。2023/3/43 莎弗(G.Shafer)进一步拓展了Dempster的工作，这一拓展称为证据推理(Evidential Reasoning)，用于处理不确定性、不精确以及间或不准确的信息。由于证据理论将概率论中的单点赋值扩展为集合赋值，弱化了相应的公理系统，满足了比概率更弱的要求，因此可看作一种广义概率广义概率论论。证据

3、理论证据理论 证据理论的发展简况证据理论的发展简况 2 2、证据理论的名称、证据理论的名称 证据理论(Evidential Theory)Dempster-Shafer理论 Dempster-Shafer证据理论 DS(或D-S)理论其它叫法：Dempster规则 Dempster合成规则 Dempster证据合成规则 3 3、证据理论的核心、优点及适用领域、证据理论的核心、优点及适用领域 核心核心：Dempster合成规则合成规则，这是Dempster在研究统计问题时首先提出的，随后Shafer把它推广到更为一般的情形。优点优点：由于在证据理论中需要的先验数据比概率推理理论中的更为直观、更容

4、易获得，再加上Dempster合成公式可以综合不同专家或数据源的知识或数据，这使得证据理论在专家系统、信息融合专家系统、信息融合等领域中得到了广泛应用。适用领域适用领域：信息融合、专家系统、情报分析、法律案件分析、多属性决策分析，等等。4 4、证据理论的局限性、证据理论的局限性 要求证据必须是独立的证据必须是独立的，而这有时不易满足 证据合成规则没有非常坚固的理论支持，其合理合理性和有效性还存在较大的争议性和有效性还存在较大的争议 计算上存在着潜在的指数爆炸问题指数爆炸问题2023/3/47 在证据理论中，引入了信任函数来度量不确定性，并引用似然函数来处理由于“不知道”引起的不确定性，并且不必

5、事先给出知识的先验概率，与主观Bayes方法相比，具有较大的灵活性。因此，证据理论得到了广泛的应用。同时，可信度可以看作是证据理论的一个特例，证据理论给了可信度一个理论性的基础。证据理论证据理论2023/3/482013证据理论 在D-S理论中，可以分别用信任函数、似然函数及类概率函数来描述知识的精确信任度、不可驳斥信任度及估计信任度，即可以从各个不同角度刻画命题的不确定性。D-S理论采用集合来表示命题，先建立命题与集合之间的一一对应关系，把命题的不确定性问题转化为集合的不确定性问题。2023/3/49 设为变量x的所有可能取值的有限集合(亦称样本空间)，且中的每个元素都相互独立，则由的所有子

6、集构成的集合称为幂集，记为2。当中的元素个数为N时，则其幂集的元素个数为2N，且其中的每一个元素A都对应于一个关于x的命题，称该命题为“x的值在A中”。2013证据理论2023/3/410 如，用x代表所看到的颜色，=红，黄，蓝，则A=红表示“x是红色”；若A=红，蓝，则表示“x或者是红色，或者是蓝色”。2013证据理论2023/3/4112013证据理论 定义定义 设函数m:20,1，且满足 则称m是2上的概率分配函数，m(A)称为A的基本概率数。m(A)表示依据当前的环境对假设集表示依据当前的环境对假设集A的信任的信任程度。程度。2023/3/412 对于上面给出的有限集=红，黄，蓝，若定

7、义2上的一个基本函数m:m(,红红,黄黄,蓝蓝,红红,黄黄,红红,蓝蓝,黄黄,蓝蓝,红红,黄黄,蓝蓝)=0,0.3,0,0.1,0.2,0.2,0.1,0.1其中，0,0.3,0,0.1,0.2,0.2,0.1,0.1分别是幂集中各个子集的基本概率数。显然m满足概率分配函数的定义。例子说明例子说明2023/3/413 （1）概率分配函数的作用是把）概率分配函数的作用是把的任意一的任意一个子集都映射为个子集都映射为0,1上的一个数上的一个数m(A)。当A包含于且A由单个元素组成时，m(A)表示对A的精确信任度；当A包含于、A,且A由多个元素组成时，m(A)也表示对A的精确信任度，但却不知道这部分

8、信任度该分给A中哪些元素；当A=时，则m(A)是对的各个子集进行信任分配后剩下的部分，它表示不知道该如何对它进行分配。对概率分配函数的对概率分配函数的几点说明几点说明2023/3/414 以以=红红,黄黄,蓝蓝为例说明。为例说明。当当A=红时红时，由于m(A)=0.3，它表示对命题“x是红色”的精确信任度为0.3。当当A=红，黄红，黄时时，由于m(A)=0.2，它表示对命题“x或者是红色，或者是黄色”的精确信任度为0.2，却不知道该把这0.2分给红还是分给黄。当当A=红，黄，蓝红，黄，蓝时时，由于m(A)=0.2，表示不知道该对这0.2如何分配，但它不属于红，就一定属于黄或蓝，只是基于现有的知

9、识，还不知道该如何分配而已。例如例如2023/3/415 （2）m 是是 2上而非上而非上的概率分布，所上的概率分布，所以基本概率分配函数不是概率，它们不必以基本概率分配函数不是概率，它们不必相等，而且相等，而且m(A)l-m(A)。事实上 m(红)+m(黄)+m(蓝)=0.3+0+0.1=0.41。概率分配函数的概率分配函数的几点说明几点说明2023/3/4162013证据理论 定义定义 信任函数(Belief Function)Bel:2 0,1对任意的 有,Bel(A)表示当前环境下，对假设集A的信任程度，其值为A的所有子集的基本概率之和，表示对表示对A的总的信任度。的总的信任度。202

10、3/3/417 以以=红红,黄黄,蓝蓝为例说明。为例说明。Bel(红,黄)=m(红)+m(黄)+m(红，黄)=0.3+0+0.2=0.5。当A为单一元素组成的集合时,Bel(A)=m(A)。如果命题“x在B中”成立，必带有命题“x在A中”成立。Bel(A)函数又称为下限函数。下限函数。例如例如2023/3/4182013证据理论 定义定义 似然函数似然函数(Plausibility Function)对任意的对任意的 有有:Pl(A)=1-Bel(A)其中，其中，A=-A。似然函数又称为不可驳斥函数或上限函数。似然函数又称为不可驳斥函数或上限函数。由于Bel(A)表示对A为真的信任度，Bel(

11、A)表示对A的信任度，即A为假的信任度，因此，Pl(A)表示对表示对A为非假的信任度。为非假的信任度。2023/3/419 以以=红红,黄黄,蓝蓝为例说明。为例说明。Pl(红)=1-Bel(红)=1-Bel(黄,蓝)=1-(m(黄)+m(蓝)+m(黄,蓝)=1-(0+0.1+0.1)=0.8这里0.8是“红”为非假的信任度。由于“红”为真的精确信任度为0.3，而剩下的0.8-0.3=0.5，则是知道非假，但却不能肯定为真的那部分。例如例如2023/3/420推论该式可推广为可见，2023/3/421 因此命题“x在A中”的似然性，由与命题“x在B中”有关的m值确定，其中命题“x在B中”并不会使

12、得命题“x不在A中”成立。所以一个事件的似然性是建立在对其相反事件不信任的基础上的。推论2023/3/422(1)Bel()=0，Bel()=l，Pl()=O，Pl()=1.(2)如果如果 ,则则 Bel(A)Bel(B),Pl(A)Pl(B)。(3),Pl(A)Bel(A)。(4),Bel(A)+Bel(A)l，Pl(A)+Pl(A)1.信任函数和似然函数有如下的性质信任函数和似然函数有如下的性质2023/3/423 由于Bel(A)和Pl(A)分别表示A为真的信任度和A为非假的信任度，因此，可分别称Bel(A)和和Pl(A)为对为对A信任程度的下限和上限，信任程度的下限和上限，记为 A(B

13、el(A),Pl(A)Pl(A)-Bel(A)表示既不信任表示既不信任A，也不信任，也不信任A的程度，即对于的程度，即对于A是真是假不知道的程度。是真是假不知道的程度。下限上限信任区间信任区间2023/3/424如，在前面的例子中，曾求过Bel(红)=0.3，Pl(红)=0.8，因此有 红（0.3，0.8）它表示对红的精确信任度为0.3，不可驳斥部分为0.8，肯定不是红的为0.2。信任区间信任区间2023/3/4252013证据理论其中|A|、|分别表示A和中包含元素的个数。类概率函数类概率函数f(A)也可以用来度量证据A的不确定性。2023/3/42620132013证据理论证据理论(1)(

14、2)(3)Bel(A)f(A)Pl(A),for A(4)f(A)=1-f(A),for A 证据证据E E的不确定性可以用类概率函数的不确定性可以用类概率函数f(E)f(E)表表示，原始证据的示，原始证据的f(E)f(E)应由用户给出应由用户给出,作为中间结作为中间结果的证据可以由下面的不确定性传递算法确定。果的证据可以由下面的不确定性传递算法确定。2023/3/42720132013证据理论证据理论 在实际问题中，对于相同的证据，由于来源不同，可能会得到不同的概率分配函数。例如，考虑=红，黄，假设从不同知识源得到的概率分配函数分别为:m1(,红红,黄黄,红红,黄黄)=(0,0.4,0.5,

15、0.1)m2(,红红,黄黄,红红,黄黄)=(0,0.6,0.2,0.2)在这种情况下，需要对它们进行组合。2023/3/428定义定义 设m1和m2是两个不同的概率分配函数，则其正交和正交和m=m1m2m=m1m2满足其中:正交和概念正交和概念2023/3/429如果KO，则正交和m也是一个概率分配函数；如果K=0，则不存在正交和m，称m1与m2矛盾。注意注意2023/3/430设=a,b，且从不同知识源得到的概率分配函数分别为 m1(,a,b,a,b)=(0,0.3,0.5,0.2)m2(,a,b,a,b)=(0,0.6,0.3,0.1)求正交和m=m1m2。例例32023/3/431解:先

16、求K再求m(,a,b,a,b)，由于 2023/3/432同理可得:m(b)=0.43，m(a,b)=0.03 故有 m(,a,b,a,b)=(0，0.54，0.43，0.03)2023/3/4332013证据理论 具有不确定性的推理规则可表示为:If E Then H,CF 其中，H为假设，E为支持H成立的假设集，它们是命题的逻辑组合。CF为可信度因子。H可表示为:H=a1,a2,am,ai(i=l,2,m)，H为假设集合的子集。2023/3/434 CF=c1,c2,cm，ci用来描述前提E成立时ai的可信度。CF应满足如下条件:2013证据理论2023/3/435定义定义 对于不确定性规

17、则:If E Then H，CF定义:m(ai)=f(E)ci (i=l,2,m)或表示为 m(a1,a2,am)=(f(E)c1,f(E)c2,f(E)cm)2013证据理论2023/3/436规定:而对于的所有其他子集H，均有:m(H)=0。当H为的真子集时，有:进一步可以计算Pl(H)和f(H)。2023/3/4372013证据理论当规则的前提(证据)E是多个命题的合取或析取时，定义:2023/3/438当有多条规则支持同一结论时，如果H=a1,a2,an，则:If E1 Then H，CF1 (CF1=c11,c12,c1n)If E2 Then H，CF2 (CF2=c21,c22,

18、c2n)If Em Then H，CFm (CFm=cm1,cm2,cmn)2013证据理论2023/3/439 如果这些规则相互独立地支持结论H的成立，可以先计算 mi(a1,a2,an)=(f(Ei)ci1,f(Ei)ci2,f(Ei)cim)(i=l,2,m)然后根据前面介绍的求正交和的方法，对这些mi求正交和，以组合所有规则对结论H的支持。一旦累加的正交和m(H)计算出来，就可以计算Bel(H)、Pl(H)、f(H)。2013证据理论2023/3/440有如下的推理规则：有如下的推理规则：R1:If E1(E2E3)Then A1=a11,a12,a13 CF1=0.2，0.3，0.4

19、R2:If E4(E5E6)Then A2=a21 CF2=0.7R3:If A1 Then A=a1,a2 CF3=0.4，0.5R4:If A2 Then A=a1,a2 CF4=0.4，0.4 例例2023/3/441这些规则形成这些规则形成如图所示的推如图所示的推理网络。理网络。原始数据的概原始数据的概率在系统中己率在系统中己经给出经给出:f(E1)=0.5,f(E2)=0.7,f(E3)=0.9,f(E4)=0.9,f(E5)=0.8,f(E6)=0.7.假设假设|=10，现在，现在需要求出需要求出A的确的确定性定性f(A)。2023/3/442解:第一步，求A1的确定性。2023/

20、3/443第二步,求A2的确定性。2023/3/444第三步,求A的确定性。根据R3和R4,有:m3(a1,a2)=(0.740.4,0.740.5)=(0.30,0.37)m4(a1,a2)=(0.60.4,0.60.4)=(0.24,0.24)m3()=1-(m3(a1)+m3(a2)=1-(0.30+0.37)=0.33m4()=1-(m4(a1)+m4(a2)=1-(0.24+0.24)=0.522023/3/445由正交和公式得到:2023/3/446则有:于是:Bel(A)=m(a1)+m(a2)=0.37+0.41=0.78Pl(A)=1-Bel(A)=1-0=1f(A)=Bel

21、(A)+(|A|/|)(Pl(A)-Bel(A)=0.78+2/10(1-0.78)=0.822023/3/447证据理论的优点在于能够满足比概率论更弱证据理论的优点在于能够满足比概率论更弱的公理系统，可以区分不知道和不确定的情的公理系统，可以区分不知道和不确定的情况，可以依赖证据的积累，不断缩小假设的况，可以依赖证据的积累，不断缩小假设的集合。集合。证据理论的优点：证据理论的优点：2023/3/448证据理论最早是作为经典概率理论的扩展而引证据理论最早是作为经典概率理论的扩展而引入的入的,所以受到很多的批评；所以受到很多的批评；在证据理论中，在证据理论中，证据的独立性不易得到保证证据的独立性

22、不易得到保证；基本概率分配函数要求给的值太多，计算传递基本概率分配函数要求给的值太多，计算传递关系复杂，随着诊断问题可能答案的增加，关系复杂，随着诊断问题可能答案的增加，证据理论的计算呈指数增长，传递关系复杂，证据理论的计算呈指数增长，传递关系复杂，比较难以实现。比较难以实现。证据理论的不足：证据理论的不足：“Zadeh悖论悖论”：对证据理论的合成公式的合理性进行质疑。例子例子：利用Dempster证据合成规则对两个目击证人（W1,W2）判断某宗“谋杀案”的三个犯罪嫌疑人（Peter,Paul,Mary）中究竟谁是真正的凶手，得到的结果（认定Paul是凶手）却违背了人的常识推理结果，Zadeh

23、认为这样的结果无法接受。m1()m2()m m1212()()Peter0.990.000.000.00Paul0.010.011.001.00Mary0.000.990.000.00m1()m2()m12()Peter0.990.000.00Paul0.010.011.00Mary0.000.990.00Dempster合成规则计算举例合成规则计算举例 例1.“Zadeh悖论悖论”：某宗“谋杀案”的三个犯罪嫌疑人组成了识别框架=Peter,Paul,Mary，目击证人（W1,W2）分别给出下表所示的BPA。【要求】：计算证人W1和W2提供证据的组合结果。【解】：首先，计算归一化常数K。其次，

24、利用Dempster证据合成规则分别计算Peter,Paul,Mary的组合BPA（即组合mass函数）。（1）关于Peter的组合mass函数（2）关于Paul的组合mass函数（3）关于Mary的组合mass函数【说明】：对于这个简单的实例而言，对于Peter,Paul,Mary的组合mass函数，再求信任函数、似然函数，可知：信任函数值似然函数值组合后的mass函数值即，Bel(Peter)=Pl(Peter)=m12(Peter)=0 Bel(Paul)=Pl(Paul)=m12(Paul)=1 Bel(Mary)=Pl(Mary)=m12(Mary)=0 例2.若修改“Zadeh悖论

25、悖论”表中的部分数据，如下表所示。请重新计算证人W1和W2提供证据的组合结果。【解解】：首先，计算归一化常数K。m1()m2()m12()Peter0.9800.49Paul0.010.010.015Mary00.980.49=Peter,Paul,Mary0.010.010.005归一化常数K的另一种计算法：（1）计算关于）计算关于Peter的组合的组合mass函数函数（2）计算关于）计算关于Paul的组合的组合mass函数函数（3）计算关于）计算关于Mary的组合的组合mass函数函数（4）计算关于）计算关于 =Peter,Paul,Mary的组合的组合mass函数函数此外，根据信任函数、

26、似然函数的计算公式，可得：即，Bel(Peter)=0.49;Pl(Peter)=0.49+0.005=0.495 Bel(Paul)=0.015;Pl(Paul)=0.015+0.005=0.020 Bel(Mary)=0.49;Pl(Mary)=0.49+0.005=0.495 Bel()=Pl()=0.49+0.015+0.49+0.005=120132013证据理论证据理论假设在2001年美国发生“911事件”之前，布什总统分别接到美国中央情报局（CIA）和国家安全局（NSA）两大情报机构发来的绝密情报，其内容是关于中东地区的某些国家或组织企图对美国实施突然的恐怖袭击。CIA和NSA得

27、到的证据如表1所示。试计算并回答下列问题：1.请直接利用Dempster证据合成公式计算表1中的所有“？”内容。2.根据BPA（mass函数值）的Bayes近似计算公式，重新调整表1中的BPA分布，并利用Dempster证据合成公式重新计算调整后的表1中的所有“？”内容。情报部门恐怖分子中央情报局（CIA）国家安全局（NSA）布什政府根据DS理论计算后的结果本拉登（简称“本本”）0.400.20？萨达姆（简称“萨萨”）0.300.20？霍梅尼（简称“霍霍”）0.100.05？本本拉登，萨萨达姆0.100.50？=本本,萨萨,霍霍0.100.05？表1 美国CIA和NSA所掌握的证据 2013证

28、据理论首先，计算归一化常数K。2013证据理论证据理论计算关于本拉登（“本”）的组合mass函数2013证据理论证据理论同理可得：实例解答（续实例解答（续3）同理可得：实例解答（续实例解答（续4）同理可得：实例解答（续实例解答（续5）同理可得：情报部门恐怖分子中央情报局（CIA）国家安全局（NSA）布什政府根据DS理论计算后的结果本拉登（简称“本本”）0.400.200.4658萨达姆（简称“萨萨”）0.300.200.3630霍梅尼（简称“霍霍”）0.100.050.0205本本拉登，萨萨达姆0.100.500.1438=本本,萨萨,霍霍0.100.050.0068表2 经Dempster规则合成后的mass