DS证据理论-浙大课件.ppt

浙江大学研究生人工智能课件,徐从富(CongfuXu)PhD,AssociateProfessorEmail:xucongfuInstituteofArtificialIntelligence,CollegeofComputerScience,ZhejiangUniversity,Hangzhou310027,P.R.ChinaMarch10,2002第一稿September25,2006第四次修改稿,第五章D-S证据理论(Chapter5D-SEvidentialTheory),Outline,本章的主要参考文献证据理论的发展简况经典证据理论关于证据理论的理论模型解释证据理论的实现途径基于DS理论的不确定性推理计算举例,1Dempster,A.P.Upperandlowerprobabilitiesinducedbyamultivaluedmapping.AnnalsofMathematicalStatistics,1967,38(2):325-339.【提出证据理论的第一篇文献】2Dempster,A.P.GeneralizationofBayesianInference.JournaloftheRoyalStatisticalSociety.SeriesB30,1968:205-247.3Shafer,G.AMathematicalTheoryofEvidence.PrincetonUniversityPress,1976.【证据理论的第一本专著，标志其正式成为一门理论】4Barnett,J.A.Computationalmethodsforamathematicaltheoryofevidence.In:Proceedingsof7thInternationalJointConferenceonArtificialIntelligence(IJCAI-81),Vancouver,B.C.,Canada,Vol.II,1981:868-875.【第一篇将证据理论引入AI领域的标志性论文】,本章的主要参考文献,5Zadeh,L.A.ReviewofShafersamathematicaltheoryofevidence.AIMagazine,1984,5:81-83.【对证据理论进行质疑的经典文献之一】6Shafer,G.Perspectivesonthetheoryandpracticeofbelieffunctions.InternationalJournalofApproximateReasoning,1990,4:323-362.7Shafer,G.Rejoindertocommentson“Perspectivesonthetheoryandpracticeofbelieffunctions”.InternationalJournalofApproximateReasoning,1992,6:445-480.8Voorbraak,F.OnthejustificationofDempstersruleofcombination.ArtificialIntelligence,1991,48:171-197.9Smets,P.Thecombinationofevidenceinthetransferablemodel.IEEETransactionsonPatternAnalysisandMachineIntelligence,1990,12(5):447-458.10Smets,P,andKennes,R.Thetransferablebeliefmodel.ArtificialIntelligence,1994,66:191-234.,本章的主要参考文献（续1）,11Voobraak,F.AcomputationallyefficientapproximationofDempster-Shafertheory.InternationalJournalofMan-MachineStudy,1989,30:525-536.12Dubois,D,Prade,H.Consonantapproximationsofbelieffunctions.InternationalJournalofApproximateReasoning,1990,4:279-283.13Tessem,B.Approximationsforefficientcomputationinthetheoryofevidence.ArtificialIntelligence,1993,61:315-329.【注：文献10-12均为证据理论近似计算方法】14Simard,M.A.,etal.DatafusionofmultiplesensorsattributeinformationfortargetidentityestimationusingaDempster-Shaferevidentialcombinationalgorithm.In:ProceedingsofSPIE-InternationalSocietyforOpticalEngineering,1996,Vol.2759:577-588.【提出了一种实现证据理论的“修剪算法”】,本章的主要参考文献（续2）,15Josang,A.Theconsensusoperatorforcombiningbeliefs.ArtificialIntelligence,2002,141(1-2):157-170.16Yang,Jian-Bo,Xu,Dong-Ling.Ontheevidentialreasoningalgorithmformultipleattributedecisionanalysisunderuncertainty.IEEETransactiononSystems,Man,andCyberneticsPartA:SystemsandHumans,2002,32(3):289-304.17Yaghlane,B.B.,etal.Belieffunctionindependence:I.Themarginalcase.InternationalJournalofApproximateReasoning,2002,29(1):47-70.18Yaghlane,B.B.,etal.Belieffunctionindependence:II.Theconditionalcase.InternationalJournalofApproximateReasoning,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、证据理论的名称证据理论(EvidentialTheory)Dempster-Shafer理论Dempster-Shafer证据理论DS(或D-S)理论其它叫法：Dempster规则Dempster合成规则Dempster证据合成规则,2、证据理论的诞生和形成诞生：源于20世纪60年代美国哈佛大学数学家A.P.Dempster在利用上、下限概率来解决多值映射问题方面的研究工作。自1967年起连续发表了一系列论文，标志着证据理论的正式诞生。形成：Dempster的学生G.Shafer对证据理论做了进一步的发展，引入信任函数概念，形成了一套基于“证据”和“组合”来处理不确定性推理问题的数学方法，并于1976年出版了证据的数学理论(AMathematicalTheoryofEvidence)，这标志着证据理论正式成为一种处理不确定性问题的完整理论。,3、证据理论的核心、优点及适用领域核心：Dempster合成规则，这是Dempster在研究统计问题时首先提出的，随后Shafer把它推广到更为一般的情形。优点：由于在证据理论中需要的先验数据比概率推理理论中的更为直观、更容易获得，再加上Dempster合成公式可以综合不同专家或数据源的知识或数据，这使得证据理论在专家系统、信息融合等领域中得到了广泛应用。适用领域：信息融合、专家系统、情报分析、法律案件分析、多属性决策分析，等等。,4、证据理论的局限性要求证据必须是独立的，而这有时不易满足证据合成规则没有非常坚固的理论支持，其合理性和有效性还存在较大的争议计算上存在着潜在的指数爆炸问题,5、证据理论的发展概况“Zadeh悖论”：对证据理论的合成公式的合理性进行质疑。例子：利用Dempster证据合成规则对两个目击证人（W1,W2）判断某宗“谋杀案”的三个犯罪嫌疑人（Peter,Paul,Mary）中究竟谁是真正的凶手，得到的结果（认定Paul是凶手）却违背了人的常识推理结果，Zadeh认为这样的结果无法接受。,专家系统MYCIN的主要开发者之一Shortliffe：对证据理论的理论模型解释和算法实现进行了研究。AI专家DuboisPl(Peter)=0.49+0.005=0.495Bel(Paul)=0.015;Pl(Paul)=0.015+0.005=0.020Bel(Mary)=0.49;Pl(Mary)=0.49+0.005=0.495Bel()=Pl()=0.49+0.015+0.49+0.005=1,5.3关于证据理论的理论模型解释对Dempster-Shafer证据理论的解释共有四种：（1）上、下概率解释（Upperandlowerprobabilityinterpretation）；（2）广义化Bayes理论（GeneralizedBayesiantheory）解释；（3）随机集理论（Randomsets）模型解释；（4）可传递信度模型（Transferablebeliefmodel，简称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年发表了下面两篇论文：1Mahler,R.P.S.Combiningambiguousevidencewithrespecttoambiguousaprioriknowledge,I:Booleanlogic.IEEETransactionsonSystems,Man,andCybernetics-PartA:SystemsandHumans,1996,26(1):27-41.2Fixsen,D.andMahler,R.P.S.ThemodifiedDempster-Shaferapproachtoclassification.IEEETransactionsonSystems,Man,andCybernetics-PartA:SystemsandHumans,1997,27(1):27-41.指出条件化(Conditional)Dempster-Shafer理论（简称CDS）和修改的(Modified)Dempster-Shafer理论（简称MDS）都是建立在随机集（Random）理论基础上的。,2019/12/13,36,可编辑,补充说明：（1）当证据和先验知识都是模糊的情况下，则条件化Dempster-Shafer理论（CDS）是Bayes理论的广义化，它完全是一种概率理论。（2）当证据和先验知识都是统计独立时，则条件化Dempster-Shafer理论（CDS）的证据合成相当于随机条件事件的并（或交）。Yen在医疗专家系统GERTIS中提出了扩展（Extended）的Dempster-Shafer理论（简称EDS），实际上EDS就是一种CDS或MDS。【Yen,J.GERTIS:aDempster-Shaferapproachtodiagnosinghierarchicalhypotheses.CommunicationsoftheACM,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近似计算