D-S证据理论[知识课件].ppt

《D-S证据理论[知识课件].ppt》由会员分享，可在线阅读，更多相关《D-S证据理论[知识课件].ppt（69页珍藏版）》请在三一文库上搜索。

1、浙江大学研究生人工智能课件,徐从富(Congfu Xu) PhD, Associate Professor Email: Institute of Artificial Intelligence, College of Computer Science, Zhejiang University, Hangzhou 310027, P.R. China March 10, 2002第一稿 September 25, 2006第四次修改稿,第五章 D-S证据理论(Chapter5 D-S Evidential Theory ),1,优质荟萃,Outline,本章的主要参考文献 证据理论的发展简况

2、经典证据理论 关于证据理论的理论模型解释 证据理论的实现途径 基于DS理论的不确定性推理 计算举例,2,优质荟萃,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

3、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 Intelligenc

4、e(IJCAI-81), Vancouver, B. C., Canada, Vol. II, 1981: 868-875. 【第一篇将证据理论引入AI领域的标志性论文】,本章的主要参考文献,3,优质荟萃,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. Internat

5、ional 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. Arti

6、ficial 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.,本章的主要

7、参考文献（续1）,4,优质荟萃,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.

8、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 combin

9、ation algorithm. In: Proceedings of SPIE-International Society for Optical Engineering, 1996, Vol.2759: 577-588. 【提出了一种实现证据理论的“修剪算法”】,本章的主要参考文献（续2）,5,优质荟萃,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

10、 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

11、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）,6,优质荟萃,19 段新生. 证据理论与决策、人工智能. 中国人民大学出版社, 1993. 20 徐从富 等. Dempster-Shafer证据推理方法理论与应用的综述. 模式识别与人工智

12、能, 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.,本章的主要参考

13、文献（续4）,7,优质荟萃,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

14、-1046. 31 王永庆. 人工智能原理与方法. 西安交通大学出版社, 1998. pp. 185-197. （第5章第5.5节 “证据理论”）,本章的主要参考文献（续5）,8,优质荟萃,5.1 证据理论的发展简况 1、证据理论的名称 证据理论(Evidential Theory) Dempster-Shafer理论 Dempster-Shafer证据理论 DS (或D-S)理论 其它叫法： Dempster规则 Dempster合成规则 Dempster证据合成规则,9,优质荟萃,2、证据理论的诞生和形成 诞生：源于20世纪60年代美国哈佛大学数学家A. P. Dempster在利用上、下

15、限概率来解决多值映射问题方面的研究工作。自1967年起连续发表了一系列论文，标志着证据理论的正式诞生。 形成：Dempster的学生G. Shafer对证据理论做了进一步的发展，引入信任函数概念，形成了一套基于“证据”和“组合”来处理不确定性推理问题的数学方法，并于1976年出版了证据的数学理论(A Mathematical Theory of Evidence)，这标志着证据理论正式成为一种处理不确定性问题的完整理论。,10,优质荟萃,3、证据理论的核心、优点及适用领域 核心：Dempster合成规则，这是Dempster在研究统计问题时首先提出的，随后Shafer把它推广到更为一般的情形。

16、 优点：由于在证据理论中需要的先验数据比概率推理理论中的更为直观、更容易获得，再加上Dempster合成公式可以综合不同专家或数据源的知识或数据，这使得证据理论在专家系统、信息融合等领域中得到了广泛应用。 适用领域：信息融合、专家系统、情报分析、法律案件分析、多属性决策分析，等等。,11,优质荟萃,4、证据理论的局限性 要求证据必须是独立的，而这有时不易满足 证据合成规则没有非常坚固的理论支持，其合理性和有效性还存在较大的争议 计算上存在着潜在的指数爆炸问题,12,优质荟萃,5、证据理论的发展概况 “Zadeh悖论”：对证据理论的合成公式的合理性进行质疑。 例子：利用Dempster证据合成规

17、则对两个目击证人（W1, W2）判断某宗“谋杀案” 的三个犯罪嫌疑人（Peter, Paul, Mary）中究竟谁是真正的凶手，得到的结果（认定Paul是凶手）却违背了人的常识推理结果，Zadeh认为这样的结果无法接受。,13,优质荟萃, 专家系统MYCIN的主要开发者之一Shortliffe：对证据理论的理论模型解释和算法实现进行了研究。 AI专家Dubois 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

18、+ 0.005 = 0.495 Bel() = Pl() = 0.49 + 0.015 + 0.49 + 0.005 = 1,32,优质荟萃,5.3 关于证据理论的理论模型解释 对Dempster-Shafer证据理论的解释共有四种： （1）上、下概率解释（Upper and lower probability interpretation）； （2）广义化Bayes理论（Generalized Bayesian theory）解释； （3）随机集理论（Random sets）模型解释； （4）可传递信度模型（Transferable belief model，简称TBM）解释； 【注】第(1

19、)(3)这三种解释都以“概率理论”为基础的；而第(4)种，即TBM为“纯粹的”的DS理论模型，它已经完全从任何概率内涵中“提纯”了出来，不依赖于任何概率理论。,33,优质荟萃,1、上、下概率解释 Dempster在1967年发表的第一篇关于证据理论的论文中给出了上、下概率的概念，用以表示不满足可加性的概率。 2、广义化Bayes理论解释 当mass函数m中的所有焦元都是单点集（即单个假设集），且这些焦元都满足Bayes独立条件时，Dempster证据合成公式就退化为Bayes公式，所以， Bayes公式是Dempster证据合成公式的特例。 反过来说， Dempster证据合成公式是Bayes

20、公式的广义化。,34,优质荟萃,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

21、, 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）理论基础上的。,35,优质荟萃,补充说明： （1）当证据和先验知识

22、都是模糊的情况下，则条件化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. Communication

23、s of the ACM, 1989, 32(5): 573-585.】,36,优质荟萃,4、可传递信度模型（TBM）解释 Smets认为从信度（Belief）的“更新/条件化”（Updating/Conditioning）方式中，可以看出各种DS理论模型的主要差别。 (1) TBM模型 Smets发现许多DS模型的研究者只看到了BPA是在识别框架 的幕集上的静态概率分布，但他们都没有研究DS模型的动态部分，即信度是如何更新的，因此，提出了一种不依赖任何概率理论的“可传递信度模型TBM”。,37,优质荟萃,(2) TBM是一个双层模型 “credal层”：位于底层，在该层中获取信度并对其进行量

24、化、赋值和更新处理。 “pignistic层”：位于上层，它将credal层上的信度转换成pignistic概率，并由此做出决策。 只有必须做出决策时，pignistic层才出现。其中，pignistic概率分布公式如下：,38,优质荟萃,(3) TBM模型的意义 TBM模仿了人类的“思维”和“行动”的区别，即模仿了“推理”和“行为”的差别： 推理：表明信度是如何受证据影响的 行动：从多个可行的行为方案中选择一个似乎是最好的 TBM实际上是一种层次化的递进模型，体现了证据的层次化描述特征，它比较适用于需要逐层进行数据、特征和决策层融合的数据融合系统。 【说明】：上述关于证据理论的四种典型的解释

25、模型，各有其适用领域，没有哪一个能适用于所有的应用领域，也不存在哪种模型更好的情况。,39,优质荟萃,5.4 证据理论的实现途径 Dempster合成公式的算法实现一直是困绕着DS理论的一个重点和难点问题，这直接关系到其实用性。 1、实现途径分类 目前主要有如下三种途径： （1）针对特殊的证据组织结构，构造相应的快速算法 （注：该方法比较简单，故从略。感兴趣者可参考Barnett, Shafer等人的相关文献。） （2）近似计算 （3）修改DS方法,40,优质荟萃,2、Dempster合成规则的近似计算方法 DS近似计算的基本思想：通过减少mass函数的焦元个数来达到计算的简化。 （1）Voo

26、rbraak的工作“Bayes近似法” Voorbraak发现，如果mass函数的合成将产生一个Bayes信任函数（即一个识别框架上的概率测度），则mass函数用它们的Bayes近似来代替，将不会影响Dempster合成规则的结果。Voorbraak给出了mass函数的Bayes近似计算公式，即,41,优质荟萃,Voorbraak证明了如下结论： mass函数的Bayes近似的合成mass函数的合成的Bayes近似 Voorbraak的“Bayes近似法”的意义： 对于那些只关心识别框架中的“元素”（即单个假设）而不是其“子集”（即多个假设组成的子集）的最终结论的情况是非常有用的，并且大大简化

27、了计算量。 【注】：感兴趣者可参考本课件给出的Voorbraak 发表的相关论文。 Voobraak, F. A computationally efficient approximation of Dempster-Shafer theory. International Journal of Man-Machine Study, 1989, 30: 525-536.,Bayes近似法（续）,42,优质荟萃,（2）Dubois 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,69,优质荟萃,