证据理论PPT课件

1证据理论石 峰2022-10-82 证据理论(Theory of Evidence)也称为D-S(Dempster-Shafer)理论。证据理论(D-S理论)最早是基于德姆斯特(A.P.Dempster)所做的工作，他试图用一个概率范围而不是单个的概率值去模拟不确定性。证据理论证据理论 1 1、证据理论的诞生和形成、证据理论的诞生和形成 诞生诞生：源于20世纪60年代美国哈佛大学数学家A.P.Dempster在利用上、下限概率来解决多值映射问题利用上、下限概率来解决多值映射问题方面的研究工作。自1967年起连续发表了一系列论文，标志着证据理论的正式诞生。形成形成：Dempster的学生G.Shafer对证据理论做了进一步的发展，引入信任函数信任函数概念，形成了一套基于“证据”和“组合”来处理不确定性推理问题的数学方法，并于1976年出版了证据的数学理论(A Mathematical Theory of Evidence)，这标志着证据理论正式成为一种处理不确定性问题的完整理论。2022-10-84 莎弗(G.Shafer)进一步拓展了Dempster的工作，这一拓展称为证据推理(Evidential Reasoning)，用于处理不确定性、不精确以及间或不准确的信息。由于证据理论将概率论中的单点赋值扩展为集合赋值，弱化了相应的公理系统，满足了比概率更弱的要求，因此可看作一种广义概率广义概率论论。证据理论证据理论 证据理论的发展简况证据理论的发展简况 2 2、证据理论的名称、证据理论的名称 证据理论(Evidential Theory)Dempster-Shafer理论 Dempster-Shafer证据理论 DS(或D-S)理论其它叫法：Dempster规则 Dempster合成规则 Dempster证据合成规则 3 3、证据理论的核心、优点及适用领域、证据理论的核心、优点及适用领域 核心核心：Dempster合成规则合成规则，这是Dempster在研究统计问题时首先提出的，随后Shafer把它推广到更为一般的情形。优点优点：由于在证据理论中需要的先验数据比概率推理理论中的更为直观、更容易获得，再加上Dempster合成公式可以综合不同专家或数据源的知识或数据，这使得证据理论在专家系统、信息融合专家系统、信息融合等领域中得到了广泛应用。适用领域适用领域：信息融合、专家系统、情报分析、法律案件分析、多属性决策分析，等等。4 4、证据理论的局限性、证据理论的局限性 要求证据必须是独立的证据必须是独立的，而这有时不易满足 证据合成规则没有非常坚固的理论支持，其合理合理性和有效性还存在较大的争议性和有效性还存在较大的争议 计算上存在着潜在的指数爆炸问题指数爆炸问题2022-10-88 在证据理论中，引入了信任函数来度量不确定性，并引用似然函数来处理由于“不知道”引起的不确定性，并且不必事先给出知识的先验概率，与主观Bayes方法相比，具有较大的灵活性。因此，证据理论得到了广泛的应用。同时，可信度可以看作是证据理论的一个特例，证据理论给了可信度一个理论性的基础。证据理论证据理论2022-10-89 证据的不确定性 在D-S理论中，可以分别用信任函数、似然函数及类概率函数来描述知识的精确信任度、不可驳斥信任度及估计信任度，即可以从各个不同角度刻画命题的不确定性。D-S理论采用集合来表示命题，先建立命题与集合之间的一一对应关系，把命题的不确定性问题转化为集合的不确定性问题。2022-10-810 设为变量x的所有可能取值的有限集合(亦称样本空间)，且中的每个元素都相互独立，则由的所有子集构成的集合称为幂集，记为2。当中的元素个数为N时，则其幂集的元素个数为2N，且其中的每一个元素A都对应于一个关于x的命题，称该命题为“x的值在A中”。证据的不确定性2022-10-811 如，用x代表所看到的颜色，=红，黄，蓝，则A=红表示“x是红色”；若A=红，蓝，则表示“x或者是红色，或者是蓝色”。证据的不确定性2022-10-812l.概率分配函数 定义定义 设函数m:20,1，且满足 则称m是2上的概率分配函数，m(A)称为A的基本概率数。m(A)表示依据当前的环境对假设集表示依据当前的环境对假设集A的信任的信任程度。程度。1)(0)(AAmm2022-10-813 对于上面给出的有限集=红，黄，蓝，若定义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满足概率分配函数的定义。例子说明例子说明2022-10-814 （1）概率分配函数的作用是把）概率分配函数的作用是把的任意一的任意一个子集都映射为个子集都映射为0,1上的一个数上的一个数m(A)。当A包含于且A由单个元素组成时，m(A)表示对A的精确信任度；当A包含于、A,且A由多个元素组成时，m(A)也表示对A的精确信任度，但却不知道这部分信任度该分给A中哪些元素；当A=时，则m(A)是对的各个子集进行信任分配后剩下的部分，它表示不知道该如何对它进行分配。对概率分配函数的对概率分配函数的几点说明几点说明2022-10-815 以以=红红,黄黄,蓝蓝为例说明。为例说明。当当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如何分配，但它不属于红，就一定属于黄或蓝，只是基于现有的知识，还不知道该如何分配而已。例如例如2022-10-816 （2）m 是是 2上而非上而非上的概率分布，上的概率分布，所以基本概率分配函数不是概率，它们不所以基本概率分配函数不是概率，它们不必相等，而且必相等，而且m(A)l-m(A)。事实上 m(红)+m(黄)+m(蓝)=0.3+0+0.1=0.41。概率分配函数的概率分配函数的几点说明几点说明2022-10-8172.信任函数 定义定义 信任函数(Belief Function)Bel:2 0,1对任意的 有,Bel(A)表示当前环境下，对假设集A的信任程度，其值为A的所有子集的基本概率之和，表示对表示对A的总的信任度。的总的信任度。2022-10-818 以以=红红,黄黄,蓝蓝为例说明。为例说明。Bel(红,黄)=m(红)+m(黄)+m(红，黄)=0.3+0+0.2=0.5。当A为单一元素组成的集合时,Bel(A)=m(A)。如果命题“x在B中”成立，必带有命题“x在A中”成立。Bel(A)函数又称为下限函数。下限函数。例如例如2022-10-8193.似然函数 定义定义 似然函数似然函数(Plausibility Function)对任意的对任意的 有有:Pl(A)=1-Bel(A)其中，其中，A=-A。似然函数又称为不可驳斥函数或上限函数。似然函数又称为不可驳斥函数或上限函数。由于Bel(A)表示对A为真的信任度，Bel(A)表示对A的信任度，即A为假的信任度，因此，Pl(A)表示对表示对A为非假的信任度。为非假的信任度。1,02:Pl2022-10-820 以以=红红,黄黄,蓝蓝为例说明。为例说明。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，则是知道非假，但却不能肯定为真的那部分。例如例如2022-10-821推论该式可推广为BBmPl)()(红红可见，2022-10-822 因此命题“x在A中”的似然性，由与命题“x在B中”有关的m值确定，其中命题“x在B中”并不会使得命题“x不在A中”成立。所以一个事件的似然性是建立在对其相反事件不信任的基础上的。BABmAPl)()(推论2022-10-823(1)Bel()=0，Bel()=l，Pl()=O，Pl()=1.(2)如果如果 ,则则 Bel(A)Bel(B),Pl(A)Pl(B)。(3),Pl(A)Bel(A)。,Bel(A)+Bel(A)l，Pl(A)+Pl(A)1.BAAA信任函数和似然函数有如下的性质信任函数和似然函数有如下的性质2022-10-824 由于Bel(A)和Pl(A)分别表示A为真的信任度和A为非假的信任度，因此，可分别称Bel(A)和和Pl(A)为对为对A信任程度的下限和上限，信任程度的下限和上限，记为 A(Bel(A),Pl(A)Pl(A)-Bel(A)表示既不信任表示既不信任A，也不信任，也不信任A的程度，即对于的程度，即对于A是真是假不知道的程度。是真是假不知道的程度。下限上限信任区间信任区间2022-10-825 如，在前面的例子中，曾求过Bel(红)=0.3，Pl(红)=0.8，因此有 红（0.3，0.8）它表示对红的精确信任度为0.3，不可驳斥部分为0.8，肯定不是红的为0.2。信任区间信任区间2022-10-8264.假设集A的类概率函数f(A)其中|A|、|分别表示A和中包含元素的个数。类概率函数类概率函数f(A)也可以用来度量证据A的不确定性。)()(|)()(ABelAPlAABelAf2022-10-827f(A)f(A)有如下的性质有如下的性质 (1)(2)(3)Bel(A)f(A)Pl(A),for A (4)f(A)=1-f(A),for A 1)(,0)(ffAforAf,1)(0 证据证据E E的不确定性可以用类概率函数的不确定性可以用类概率函数f(E)f(E)表表示，原始证据的示，原始证据的f(E)f(E)应由用户给出应由用户给出,作为中间结作为中间结果的证据可以由下面的不确定性传递算法确定。果的证据可以由下面的不确定性传递算法确定。2022-10-828 证据的组合函数证据的组合函数 在实际问题中，对于相同的证据，由于来源不同，可能会得到不同的概率分配函数。例如，考虑=红，黄，假设从不同知识源得到的概率分配函数分别为:m1(,红红,黄黄,红红,黄黄)=(0,0.4,0.5,0.1)m2(,红红,黄黄,红红,黄黄)=(0,0.6,0.2,0.2)在这种情况下，需要对它们进行组合。2022-10-829 定义定义 设m1和m2是两个不同的概率分配函数，则其正交和正交和m=m1m2m=m1m2满足)()()()(12121ymxmymxmKyxyx其中:正交和概念正交和概念2022-10-830 如果KO，则正交和m也是一个概率分配函数；如果K=0，则不存在正交和m，称m1与m2矛盾。注意注意2022-10-831 设=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。例例32022-10-832 解:先求K再求m(,a,b,a,b)，由于 2022-10-833 同理可得:m(b)=0.43，m(a,b)=0.03 故有 m(,a,b,a,b)=(0，0.54，0.43，0.03)2022-10-834 规则的不确定性 具有不确定性的推理规则可表示为:If E Then H,CF 其中，H为假设，E为支持H成立的假设集，它们是命题的逻辑组合。CF为可信度因子。H可表示为:H=a1,a2,am,ai(i=l,2,m)，H为假设集合的子集。2022-10-835 CF=c1,c2,cm，ci用来描述前提E成立时ai的可信度。CF应满足如下条件:规则的不确定性2022-10-836 定义定义 对于不确定性规则: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)规则的不确定性2022-10-837 规定:而对于的所有其他子集H，均有:m(H)=0。当H为的真子集时，有:进一步可以计算Pl(H)和f(H)。2022-10-838 不确定性的组合 当规则的前提(证据)E是多个命题的合取或析取时，定义:)(,),(),(min)(2121nnEfEfEfEEEf)(,),(),(max)(2121nnEfEfEfEEEf2022-10-839 当有多条规则支持同一结论时，如果H=a1,a2,an，则:If E1 Then H，CF1 (CF1=c11,c12,c1n)If E2 Then H，CF2 (CF2=c21,c22,c2n)If Em Then H，CFm (CFm=cm1,cm2,cmn)不确定性的组合2022-10-840 如果这些规则相互独立地支持结论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)。不确定性的组合2022-10-841 有如下的推理规则：有如下的推理规则：R1:If E1(E2E3)Then A1=a11,a12,a13 CF1=0.2，0.3，0.4R2: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 例例2022-10-842 这些规则形成这些规则形成如图所示的推如图所示的推理网络。理网络。原始数据的概原始数据的概率在系统中己率在系统中己经给出经给出: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)。2022-10-843 解:第一步，求A1的确定性。2022-10-844 第二步,求A2的确定性。2022-10-845 第三步,求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.522022-10-846 由正交和公式得到:2022-10-847 则有:于是:Bel(A)=m(a1)+m(a2)=0.37+0.41=0.78Pl(A)=1-Bel(A)=1-0=1f(A)=Bel(A)+(|A|/|)(Pl(A)-Bel(A)=0.78+2/10(1-0.78)=0.822022-10-848 证据理论的优点在于能够满足比概率论更弱证据理论的优点在于能够满足比概率论更弱的公理系统，可以区分不知道和不确定的情的公理系统，可以区分不知道和不确定的情况，可以依赖证据的积累，不断缩小假设的况，可以依赖证据的积累，不断缩小假设的集合。集合。证据理论的优点：证据理论的优点：2022-10-849 证据理论最早是作为经典概率理论的扩展而证据理论最早是作为经典概率理论的扩展而引入的引入的,所以受到很多的批评；所以受到很多的批评；在证据理论中，在证据理论中，证据的独立性不易得到保证证据的独立性不易得到保证；基本概率分配函数要求给的值太多，计算传基本概率分配函数要求给的值太多，计算传递关系复杂，随着诊断问题可能答案的增加，递关系复杂，随着诊断问题可能答案的增加，证据理论的计算呈指数增长，传递关系复杂，证据理论的计算呈指数增长，传递关系复杂，比较难以实现。比较难以实现。证据理论的不足：证据理论的不足：http:/www.hds.utc.fr/tdenoeux/dokuwiki/doku.php“Zadeh悖论悖论”：对证据理论的合成公式的合理性进行质疑。例子例子：利用Dempster证据合成规则对两个目击证人（W1,W2）判断某宗“谋杀案”的三个犯罪嫌疑人（Peter,Paul,Mary）中究竟谁是真正的凶手，得到的结果（认定Paul是凶手）却违背了人的常识推理结果，Zadeh认为这样的结果无法接受。m1()m2()Peter0.990.00Paul0.010.01Mary0.000.99m1()m2()m12()Peter0.990.000.00Paul0.010.011.00Mary0.000.990.00Dempster合成规则计算举例合成规则计算举例 例1.“Zadeh悖悖论论”：某宗“谋杀案”的三个犯罪嫌疑人组成了识别框架=Peter,Paul,Mary，目击证人（W1,W2）分别给出下表所示的BPA。【要求】：计算证人W1和W2提供证据的组合结果。【解】：首先，计算归一化常数K。12121212()()()()()()()()0.99 00.01 0.010 0.990.0001B CKm Bm Cm Peterm Peterm Paulm Paulm Marym Mary 其次，利用Dempster证据合成规则分别计算Peter,Paul,Mary的组合BPA（即组合mass函数）。（1）关于Peter的组合mass函数1212121()()()1()()10.990.000.000.0001BCPetermmPeterm BmCKmPetermPeterK（2）关于Paul的组合mass函数12121()()()10.01 0.0110.0001mmPaulmPaulmPaulK（3）关于Mary的组合mass函数1212121()()()1()()10.000.990.000.0001BCMarymmMarym BmCKmMarymMaryK【说明】：对于这个简单的实例而言，对于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悖论悖论”表中的部分数据，如下表所示。请重新计算证人W1和W2提供证据的组合结果。【解解】：首先，计算归一化常数K。121212121()()1()()()()()()1(0.980.010.980.980.01 0.98)0.02BCKm Bm Cm PetermPaulm PetermMarym PaulmMary m1()m2()m12()Peter0.9800.49Paul0.010.010.015Mary00.980.49=Peter,Paul,Mary0.010.010.005归一化常数K的另一种计算法：12121212121212()()()()()()()()()()()()()()0.98 0.010.01 0.010.01 0.010.01 0.010.01 0.980.01 0.010.02B CKm Bm Cm Petermm PaulmPaulm PaulmmmPaulmmMarymm 121212121()()()1()()()()1(0.9800.980.01)0.490.02BCPetermmPeterm BmCKmPetermPetermPetermK（1）计算关于）计算关于Peter的组合的组合mass函数函数12121212121()()()1()()()()()()1(0.01 0.010.01 0.010.01 0.01)0.0150.02BCPaulmmPaulm BmCKmPaulmPaulmPaulmKmmPaul（2）计算关于）计算关于Paul的组合的组合mass函数函数121212121()()()1()()()()1(00.980.01 0.98)0.490.02BCMarymmMarym BmCKmMarymMarymmMaryK（3）计算关于）计算关于Mary的组合的组合mass函数函数1212121()()()1()()10.010.010.0050.02BCmmmBmCKmmK（4）计算关于）计算关于 =Peter,Paul,Mary的组合的组合mass函数函数此外，根据信任函数、似然函数的计算公式，可得：即，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=1计算举例计算举例 假设在2001年美国发生“911事件”之前，布什总统分别接到美国中央情报局（CIA）和国家安全局（NSA）两大情报机构发来的绝密情报，其内容是关于中东地区的某些国家或组织企图对美国实施突然的恐怖袭击。CIA和NSA得到的证据如表1所示。试计算并回答下列问题：1.请直接利用Dempster证据合成公式计算表1中的所有“？”内容。2.根据BPA（mass函数值）的Bayes近似计算公式，重新调整表1中的BPA分布，并利用Dempster证据合成公式重新计算调整后的表1中的所有“？”内容。()()()|0,ABCm BAm Am CC，若是单个假设集合 否则 情报部门恐怖分子中央情报局（CIA）国家安全局（NSA）布什政府根据DS理论计算后的结果本拉登（简称“本本”）0.400.20？萨达姆（简称“萨萨”）0.300.20？霍梅尼（简称“霍霍”）0.100.05？本本拉登，萨萨达姆0.100.50？=本本,萨萨,霍霍0.100.05？表1 美国CIA和NSA所掌握的证据 实例解答：首先，计算归一化常数K。73.027.01)05.01.0.05.04.02.04.0(1)(),(.)()()()(1)()(121212121霍萨本霍本萨本mmmmmmCmBmKCB实例解答（续实例解答（续1）计算关于本拉登（“本”）的组合mass函数4658.0)02.002.002.02.008.0(73.01)2.01.005.04.02.01.05.04.02.04.0(73.01)()()()()(),(),()()()(1)()(1)(21212121212121本本本萨本萨本本本本本本mmmmmmmmmmKCmBmKmmCB实例解答（续实例解答（续2）同理可得：363.0)02.0015.002.015.006.0(73.01)1.02.005.03.01.02.05.03.02.03.0(73.01)()(1)(2121 萨萨CBCmBmKmm实例解答（续实例解答（续3）同理可得：0205.0)005.0005.0005.0(73.01)05.01.005.01.005.01.0(73.01)()(1)(2121 霍霍CBCmBmKmm实例解答（续实例解答（续4）同理可得：1438.0)05.0005.005.0(73.01)5.01.005.01.05.01.0(73.01)()(1),(2121 本，萨萨本CBCmBmKmm实例解答（续实例解答（续5）同理可得：0068.0005.073.01)05.01.0(73.01)()(1)()(1)(212121mmKCmBmKmmCB 情报部门恐怖分子中央情报局（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