DS证据理论-浙大.ppt

浙江大学研究生人工智能课件,徐从富(Congfu Xu)PhD,Associate Professor Email:Institute of Artificial Intelligence,College of Computer Science,Zhejiang University,Hangzhou 310027,P.R.ChinaMarch 10,2002第一稿September 25,2006第四次修改稿,第五章 D-S证据理论(Chapter5 D-S Evidential Theory),Outline,本章的主要参考文献证据理论的发展简况经典证据理论关于证据理论的理论模型解释证据理论的实现途径基于DS理论的不确定性推理计算举例,1 Dempster,A.P.Upper and lower probabilities induced by a multivalued mapping.Annals of Mathematical Statistics,1967,38(2):325-339.【提出证据理论的第一篇文献】2 Dempster,A.P.Generalization of Bayesian Inference.Journal of the Royal Statistical Society.Series B 30,1968:205-247.3 Shafer,G.A Mathematical Theory of Evidence.Princeton University Press,1976.【证据理论的第一本专著，标志其正式成为一门理论】4 Barnett,J.A.Computational methods for a mathematical theory of evidence.In:Proceedings of 7th International Joint Conference on Artificial Intelligence(IJCAI-81),Vancouver,B.C.,Canada,Vol.II,1981:868-875.【第一篇将证据理论引入AI领域的标志性论文】,本章的主要参考文献,5 Zadeh,L.A.Review of Shafers a mathematical theory of evidence.AI Magazine,1984,5:81-83.【对证据理论进行质疑的经典文献之一】6 Shafer,G.Perspectives on the theory and practice of belief functions.International Journal of Approximate Reasoning,1990,4:323-362.7 Shafer,G.Rejoinder to comments on“Perspectives on the theory and practice of belief functions”.International Journal of Approximate Reasoning,1992,6:445-480.8 Voorbraak,F.On the justification of Dempsters rule of combination.Artificial Intelligence,1991,48:171-197.9 Smets,P.The combination of evidence in the transferable model.IEEE Transactions on Pattern Analysis and Machine Intelligence,1990,12(5):447-458.10 Smets,P,and Kennes,R.The transferable belief model.Artificial Intelligence,1994,66:191-234.,本章的主要参考文献（续1）,11 Voobraak,F.A computationally efficient approximation of Dempster-Shafer theory.International Journal of Man-Machine Study,1989,30:525-536.12 Dubois,D,Prade,H.Consonant approximations of belief functions.International Journal of Approximate Reasoning,1990,4:279-283.13 Tessem,B.Approximations for efficient computation in the theory of evidence.Artificial Intelligence,1993,61:315-329.【注：文献10-12均为证据理论近似计算方法】14 Simard,M.A.,et al.Data fusion of multiple sensors attribute information for target identity estimation using a Dempster-Shafer evidential combination algorithm.In:Proceedings of SPIE-International Society for Optical Engineering,1996,Vol.2759:577-588.【提出了一种实现证据理论的“修剪算法”】,本章的主要参考文献（续2）,15 Josang,A.The consensus operator for combining beliefs.Artificial Intelligence,2002,141(1-2):157-170.16 Yang,Jian-Bo,Xu,Dong-Ling.On the evidential reasoning algorithm for multiple attribute decision analysis under uncertainty.IEEE Transaction on Systems,Man,and Cybernetics Part A:Systems and Humans,2002,32(3):289-304.17 Yaghlane,B.B.,et al.Belief function independence:I.The marginal case.International Journal of Approximate Reasoning,2002,29(1):47-70.18 Yaghlane,B.B.,et al.Belief function independence:II.The conditional case.International Journal of Approximate Reasoning,2002,31:31-75.,本章的主要参考文献（续3）,19 段新生.证据理论与决策、人工智能.中国人民大学出版社,1993.20 徐从富 等.Dempster-Shafer证据推理方法理论与应用的综述.模式识别与人工智能,1999,12(4):424-430.21 徐从富 等.面向数据融合的DS方法综述.电子学报,2001,29(3):393-396.22 徐从富 等.解决证据推理中一类“0绝对化”问题的方法.计算机科学,2000,27(5):53-56.23 李岳峰 等.证据理论中的近似计算方法.吉林大学自然科学学报,1995,(1):28-32.24 刘大有 等.广义证据理论的解释.计算机学报,1997,20(2):158-164.25 刘大有 等.凸函数证据理论模型.计算机研究与发展,2000,37(2):175-181.,本章的主要参考文献（续4）,26 杨莹 等.对一种基于证据理论的不确定性处理模型的重要扩充.计算机学报,1990,(10):772-778.27 刘大有 等.一种简化证据理论模型的研究.计算机研究与发展,1999,36(2):134-138.28 肖人彬 等.相关证据合成方法的研究.模式识别与人工智能,1993,6(3):227-234.29 孙全 等.一种新的基于证据理论的合成公式.电子学报,2000,28(8):117-119.30 曾成,赵保军,何佩昆.不完备框架下的证据组合方法.电子与信息学报,2005,27(7):1043-1046.31 王永庆.人工智能原理与方法.西安交通大学出版社,1998.pp.185-197.（第5章第5.5节“证据理论”）,本章的主要参考文献（续5）,5.1 证据理论的发展简况 1、证据理论的名称 证据理论(Evidential Theory)Dempster-Shafer理论 Dempster-Shafer证据理论 DS(或D-S)理论其它叫法：Dempster规则 Dempster合成规则 Dempster证据合成规则,2、证据理论的诞生和形成 诞生：源于20世纪60年代美国哈佛大学数学家A.P.Dempster在利用上、下限概率来解决多值映射问题方面的研究工作。自1967年起连续发表了一系列论文，标志着证据理论的正式诞生。形成：Dempster的学生G.Shafer对证据理论做了进一步的发展，引入信任函数概念，形成了一套基于“证据”和“组合”来处理不确定性推理问题的数学方法，并于1976年出版了证据的数学理论(A Mathematical Theory of Evidence)，这标志着证据理论正式成为一种处理不确定性问题的完整理论。,3、证据理论的核心、优点及适用领域 核心：Dempster合成规则，这是Dempster在研究统计问题时首先提出的，随后Shafer把它推广到更为一般的情形。优点：由于在证据理论中需要的先验数据比概率推理理论中的更为直观、更容易获得，再加上Dempster合成公式可以综合不同专家或数据源的知识或数据，这使得证据理论在专家系统、信息融合等领域中得到了广泛应用。适用领域：信息融合、专家系统、情报分析、法律案件分析、多属性决策分析，等等。,4、证据理论的局限性 要求证据必须是独立的，而这有时不易满足 证据合成规则没有非常坚固的理论支持，其合理性和有效性还存在较大的争议 计算上存在着潜在的指数爆炸问题,5、证据理论的发展概况“Zadeh悖论”：对证据理论的合成公式的合理性进行质疑。例子：利用Dempster证据合成规则对两个目击证人（W1,W2）判断某宗“谋杀案”的三个犯罪嫌疑人（Peter,Paul,Mary）中究竟谁是真正的凶手，得到的结果（认定Paul是凶手）却违背了人的常识推理结果，Zadeh认为这样的结果无法接受。,专家系统MYCIN的主要开发者之一Shortliffe：对证据理论的理论模型解释和算法实现进行了研究。AI专家Dubois&Prade：指出证据理论中的信任函数（Belief function）是一种模糊测度，以集合论的观点研究证据的并、交、补和包含等问题。Smets等人：将信任函数推广到识别框架的所有模糊子集上，提出Pignistic概率和可传递信度模型（TBM）。粗糙集理论的创始人Pawlak：认为粗糙集理论使得无限框架上的证据处理向有限框架上的证据处理的近似转化成为可能。,证据理论的发展概况（续1）,为了避免证据组合爆炸，提高证据合成的效率：Voorbraak：提出一种Dempster证据合成公式的Bayes近似方法，使得焦元个数小于等于识别框架中元素的个数。Dubois&Prade：提出一种“和谐近似”（Consonant approximation），即用和谐函数来代替原来的信任函数。Tessem：提出了一种称为(k,l,x)近似方法。Yen等人：将模糊集引入证据理论。Yen,J.Generalizing the Dempster-Shafer theory to fuzzy sets.IEEE Trans.on Systems,Man,and Cybernetics,1990,20(3):559-570.】,证据理论的发展概况（续2）,6、证据理论在中国的发展情况 段新生：在1993年出版了一本专门论述证据理论的专著证据理论与决策、人工智能。【注：由于此书出版时间较早，故其内容不是很新，未能反映证据理论及其应用方面的最新成果】刘大有等人：国内较早研究证据理论的专家，并发表了一系列的论文，主要集中研究该理论的模型解释、理论扩展、近似实现等问题。肖人彬等人：对证据的相关性及相关证据的组合问题进行了研究。苏运霖、管纪文等人：对证据理论与粗糙集理论进行了比较研究。【苏运霖,管纪文等.证据论与约集论.软件学报,1999,10(3):277-282.注：此处的“约集”即为“粗糙集”(Rough set)】,曾成等人：研究了不完备的识别框架下的证据合成问题，并提出相应的证据合成公式。顾伟康等人：对证据合成公式进行扩展，提出一种改进的证据合成公式。徐从富等人：1999-2001总结国内外关于证据理论及其应用的代表性文献，先后发表2篇关于证据理论及其应用的综述文章。,证据理论在中国的发展情况（续）,5.2 经典证据理论 1、证据理论的主要特点 满足比Bayes概率理论更弱的条件，即不必满足概率可加性。具有直接表达“不确定”和“不知道”的能力，这些信息表示在mass函数中，并在证据合成过程中保留了这些信息。证据理论不但允许人们将信度赋予假设空间的单个元素，而且还能赋予它的子集，这很象人类在各级抽象层次上的证据收集过程。,2、基本概念 设是一个识别框架，或称假设空间。（1）基本概率分配 基本概率分配：Basic Probability Assignment，简称BPA。在识别框架上的BPA是一个2 0,1的函数m，称为mass函数。并且满足 m()=0 且,其中，使得m(A)0的A称为焦元(Focal elements)。,（2）信任函数 信任函数也称信度函数（Belief function）。在识别框架上基于BPA m的信任函数定义为：,（3）似然函数 似然函数也称似然度函数(Plausibility function)。在识别框架上基于BPA m的似然函数定义为：,在证据理论中，对于识别框架 中的某个假设A，根据基本概率分配BPA分别计算出关于该假设的信任函数Bel(A)和似然函数Pl(A)组成信任区间Bel(A),Pl(A)，用以表示对某个假设的确认程度。,（4）信任区间,“Teach us to number our days aright,that we may gain a heart of wisdom.”From Psalms 90:12,3、Dempster合成规则 Dempster合成规则（Dempsters combinational rule）也称证据合成公式，其定义如下：对于A，上的两个mass函数m1,m2的Dempster合成规则为：,其中，K为归一化常数,对于A，识别框架上的有限个mass函数m1,m2,.,mn的Dempster合成规则为：,其中，,n个mass函数的Dempster合成规则,4、Dempster合成规则计算举例 例1.“Zadeh悖论”：某宗“谋杀案”的三个犯罪嫌疑人组成了识别框架=Peter,Paul,Mary，目击证人（W1,W2）分别给出下表所示的BPA。【要求】：计算证人W1和W2提供证据的组合结果。,【解】：首先，计算归一化常数K。,其次，利用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悖论”表中的部分数据，如下表所示。请重新计算证人W1和W2提供证据的组合结果。,【解】：首先，计算归一化常数K。,归一化常数K的另一种计算法：,（1）计算关于Peter的组合mass函数,（2）计算关于Paul的组合mass函数,（3）计算关于Mary的组合mass函数,（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,5.3 关于证据理论的理论模型解释 对Dempster-Shafer证据理论的解释共有四种：（1）上、下概率解释（Upper and lower probability interpretation）；（2）广义化Bayes理论（Generalized Bayesian theory）解释；（3）随机集理论（Random sets）模型解释；（4）可传递信度模型（Transferable belief model，简称TBM）解释；【注】第(1)(3)这三种解释都以“概率理论”为基础的；而第(4)种，即TBM为“纯粹的”的DS理论模型，它已经完全从任何概率内涵中“提纯”了出来，不依赖于任何概率理论。,1、上、下概率解释 Dempster在1967年发表的第一篇关于证据理论的论文中给出了上、下概率的概念，用以表示不满足可加性的概率。2、广义化Bayes理论解释 当mass函数m中的所有焦元都是单点集（即单个假设集），且这些焦元都满足Bayes独立条件时，Dempster证据合成公式就退化为Bayes公式，所以，Bayes公式是Dempster证据合成公式的特例。反过来说，Dempster证据合成公式是Bayes公式的广义化。,3、随机集理论模型解释 Mahler和Fixsen分别于1996，1997年发表了下面两篇论文：1 Mahler,R.P.S.Combining ambiguous evidence with respect to ambiguous a priori knowledge,I:Boolean logic.IEEE Transactions on Systems,Man,and Cybernetics-Part A:Systems and Humans,1996,26(1):27-41.2 Fixsen,D.and Mahler,R.P.S.The modified Dempster-Shafer approach to classification.IEEE Transactions on Systems,Man,and Cybernetics-Part A:Systems and Humans,1997,27(1):27-41.指出条件化(Conditional)Dempster-Shafer理论（简称CDS）和修改的(Modified)Dempster-Shafer理论（简称MDS）都是建立在随机集（Random）理论基础上的。,补充说明：（1）当证据和先验知识都是模糊的情况下，则条件化Dempster-Shafer理论（CDS）是Bayes理论的广义化，它完全是一种概率理论。（2）当证据和先验知识都是统计独立时，则条件化Dempster-Shafer理论（CDS）的证据合成相当于随机条件事件的并（或交）。Yen在医疗专家系统GERTIS中提出了扩展（Extended）的Dempster-Shafer理论（简称EDS），实际上EDS就是一种CDS或MDS。【Yen,J.GERTIS:a Dempster-Shafer approach to diagnosing hierarchical hypotheses.Communications of the ACM,1989,32(5):573-585.】,4、可传递信度模型（TBM）解释 Smets认为从信度（Belief）的“更新/条件化”（Updating/Conditioning）方式中，可以看出各种DS理论模型的主要差别。(1)TBM模型 Smets发现许多DS模型的研究者只看到了BPA是在识别框架 的幕集上的静态概率分布，但他们都没有研究DS模型的动态部分，即信度是如何更新的，因此，提出了一种不依赖任何概率理论的“可传递信度模型TBM”。,(2)TBM是一个双层模型“credal层”：位于底层，在该层中获取信度并对其进行量化、赋值和更新处理。“pignistic层”：位于上层，它将credal层上的信度转换成pignistic概率，并由此做出决策。只有必须做出决策时，pignistic层才出现。其中，pignistic概率分布公式如下：,(3)TBM模型的意义 TBM模仿了人类的“思维”和“行动”的区别，即模仿了“推理”和“行为”的差别：推理：表明信度是如何受证据影响的 行动：从多个可行的行为方案中选择一个似乎是最好的 TBM实际上是一种层次化的递进模型，体现了证据的层次化描述特征，它比较适用于需要逐层进行数据、特征和决策层融合的数据融合系统。【说明】：上述关于证据理论的四种典型的解释模型，各有其适用领域，没有哪一个能适用于所有的应用领域，也不存在哪种模型更好的情况。,5.4 证据理论的实现途径 Dempster合成公式的算法实现一直是困绕着DS理论的一个重点和难点问题，这直接关系到其实用性。1、实现途径分类 目前主要有如下三种途径：（1）针对特殊的证据组织结构，构造相应的快速算法（注：该方法比较简单，故从略。感兴趣者可参考Barnett,Shafer等人的相关文献。）（2）近似计算（3）修改DS方法,2、Dempster合成规则的近似计算方法 DS近似计算的基本思想：通过减少mass函数的焦元个数来达到计算的简化。（1）Voorbraak的工作“Bayes近似法”Voorbraak发现，如果mass函数的合成将产生一个Bayes信任函数（即一个识别框架上的概率测度），则mass函数用它们的Bayes近似来代替，将不会影响Dempster合成规则的结果。Voorbraak给出了mass函数的Bayes近似计算公式，即,Voorbraak证明了如下结论：mass函数的Bayes近似的合成mass函数的合成的Bayes近似 Voorbraak的“Bayes近似法”的意义：对于那些只关心识别框架中的“元素”（即单个假设）而不是其“子集”（即多个假设组成的子集）的最终结论的情况是非常有用的，并且大大简化了计算量。【注】：感兴趣者可参考本课件给出的Voorbraak 发表的相关论文。Voobraak,F.A computationally efficient approximation of Dempster-Shafer theory.International Journal of Man-Machine Study,1989,30:525-536.,Bayes近似法（续）,（2）Dubois&Prade的工作“一致近似法”一致近似法：Consonant approximation 特点：通过近似计算后的焦元是嵌套的，且焦元个数不超过识别框架中的假设个数。缺点：该方法不太适合用Dempster合成规则来进行计算，可能会产生很大的误差。用途：适用于证据的表达。【注】：感兴趣者可参考本章参考文献中列的Dubois&Prade发表的相关论文。,（3）Tessem的工作(k,l,x)近似算法”k：表示保留的焦元的最少个数；l：表示保留的焦元的最多个数；x：表示允许被删除的最大mass值，x通常在0,0.1上取值。算法步骤如下：步1：先对mass值从大到小排序；步2：依次循环求mass函数值之和totalmass，若保留的焦元个数等于1，或totalmass=1-x，则循环结束，否则，继续循环；步3：对保留的焦元所对应的mass函数值重新归一化。该算法的特点：它既不给出Bayes mass函数，也不给出一致mass函数，但它确实减少了焦元。,5.5 基于DS理论的不确定性推理 基于DS理论的不确定性推理步骤如下：步1：概率分配函数的确定 步2：证据和知识的不确定性表示 步3：组合证据不确定性的算法 步4：不确定性的传递算法 步5：得到最终的推理结果【注】：对基于DS理论的不确定性推理方法感兴趣者，可参考王永庆人工智能原理与方法中的“5.5.2 一个具体的不确定性推理模型”pp190-198。,5.6 计算举例,假设在2001年美国发生“911事件”之前，布什总统分别接到美国中央情报局（CIA）和国家安全局（NSA）两大情报机构发来的绝密情报，其内容是关于中东地区的某些国家或组织企图对美国实施突然的恐怖袭击。CIA和NSA得到的证据如表1所示。试计算并回答下列问题：1.请直接利用Dempster证据合成公式计算表1中的所有“？”内容。2.根据BPA（mass函数值）的Bayes近似计算公式，,重新调整表1中的BPA分布，并利用Dempster证据合成公式重新计算调整后的表1中的所有“？”内容。,表1 美国CIA和NSA所掌握的证据,实例解答：,首先，计算归一化常数K。,实例解答（续1）,计算关于本拉登（“本”）的组合mass函数,实例解答（续2）,同理可得：,实例解答（续3）,同理可得：,实例解答（续4）,同理可得：,实例解答（续5）,同理可得：,表2 经Dempster规则合成后的mass,计算BPA的Bayes近似,根据BPA的Bayes近似公式：,BPA的Bayes近似（续1）,BPA的Bayes近似（续2）,BPA的Bayes近似（续3）,BPA的Bayes近似（续4）,BPA的Bayes近似（续5）,BPA的Bayes近似（续6）,表3 经Bayes变换后的BPA,利用Dempster规则合成经Bayes变换后的BPA,先求新的归一化常数K,经Bayes变换后的mass合成,经Bayes变换后的mass合成（续1）,经Bayes变换后的mass合成（续2）,表4 经Bayes变换后的BPA的合成结果,【作业】：请认真阅读Tessem，Voorbraak,Dubois&Prade，李岳峰，刘大有等人关于“Dempster证据合成公式”的近似计算方法的相关文献。【要求】：深刻理解Dempster证据合成公式的典型的近似算法的求解过程。【注】：可参考徐从富等人在模式识别与人工智（1999第4期）和电子学报（2001第3期）上发表的两篇关于证据理论及其应用的综述文章，以辅助理解。,课外作业（可选）,THANKS FOR YOUR PRESENCE!,“The words of the wise are like goads,their collected sayings like firmly embedded nailsgiven by one Shepherd.Be warned,my son,of anything in addition to them.Of making many books there is no end,and much study wearies the body.Now all has been heard;here is the conclusion of the matter:Fear God and keep his commandments,for this is the whole duty of man.For God will bring every deed into judgment,including every hidden thing,whether it is good or evil.”from Ecclesiastes 12:11-14,NIV,