《DS证据理论--浙大ppt课件》由会员分享，可在线阅读，更多相关《DS证据理论--浙大ppt课件（69页珍藏版）》请在金锄头文库上搜索。
1、火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去浙江大学研究生浙江大学研究生人工智能人工智能课件课件徐从富徐从富(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
2、-S证据理论(Chapter5 D-S Evidential Theory )火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去Outlinen本章的主要参考文献n证据理论的发展简况n经典证据理论n关于证据理论的理论模型解释n证据理论的实现途径证据理论的实现途径n基于DS理论的不确定性推理n计算举例计算举例火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去1 Dempster, A. P. Upper and lower probabilities induced by a mu
3、ltivalued 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、论的第一本专著，标志其正式成为一门理论】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、留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去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.
6、 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 e
7、vidence 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）火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲
8、出去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.
9、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
10、. 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
11、-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
12、 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）火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、
13、湿被褥勇敢地冲出去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 李岳峰 等. 证据理
14、论中的近似计算方法证据理论中的近似计算方法. 吉林大学自然科学学报, 1995, (1):28-32.24 刘大有 等. 广义证据理论的解释广义证据理论的解释. 计算机学报, 1997, 20(2): 158-164.25 刘大有 等. 凸函数证据理论模型凸函数证据理论模型. 计算机研究与发展, 2000, 37(2): 175-181.本章的主要参考文献本章的主要参考文献（续（续4）火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去26 杨莹 等. 对一种基于证据理论的不确定性处理模型的重要扩充对一种基于证据理论的不确定性处理模型的重
15、要扩充. 计算机学报, 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
16、): 1043-1046. 31 王永庆. 人工智能原理与方法人工智能原理与方法. 西安交通大学出版社, 1998. pp. 185-197. （第5章第5.5节 “证据理论”）本章的主要参考文献本章的主要参考文献（续（续5）火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去5.1 5.1 证据理论的发展简况证据理论的发展简况 1 1、证据理论的名称、证据理论的名称 证据理论(Evidential Theory) Dempster-Shafer理论 Dempster-Shafer证据理论 DS (或D-S)理论其它叫法： Dempste
17、r规则 Dempster合成规则 Dempster证据合成规则火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 2 2、证据理论的诞生和形成、证据理论的诞生和形成 诞生诞生：源于20世纪60年代美国哈佛大学数学家A. P. Dempster在利用上、下限概率来解决多值映射问题利用上、下限概率来解决多值映射问题方面的研究工作。自1967年起连续发表了一系列论文，标志着证据理论的正式诞生。 形成形成：Dempster的学生G. Shafer对证据理论做了进一步的发展，引入信任函数信任函数概念，形成了一套基于“证据”和“组合”来处理不确定性
18、推理问题的数学方法，并于1976年出版了证据的数学理论(A Mathematical Theory of Evidence)，这标志着证据理论正式成为一种处理不确定性问题的完整理论。火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 3 3、证据理论的核心、优点及适用领域、证据理论的核心、优点及适用领域 核心核心：Dempster合成规则合成规则，这是Dempster在研究统计问题时首先提出的，随后Shafer把它推广到更为一般的情形。 优点优点：由于在证据理论中需要的先验数据比概率推理理论中的更为直观、更容易获得，再加上Dempste
19、r合成公式可以综合不同专家或数据源的知识或数据，这使得证据理论在专家系统、信息融合专家系统、信息融合等领域中得到了广泛应用。 适用领域适用领域：信息融合、专家系统、情报分析、法律案件分析、多属性决策分析，等等。火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 4 4、证据理论的局限性、证据理论的局限性 要求证据必须是独立的证据必须是独立的，而这有时不易满足 证据合成规则没有非常坚固的理论支持，其合理合理性和有效性还存在较大的争议性和有效性还存在较大的争议 计算上存在着潜在的指数爆炸问题指数爆炸问题火灾袭来时要迅速疏散逃生，不可蜂拥而出
20、或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 5 5、证据理论的发展概况、证据理论的发展概况 “Zadeh悖论悖论”：对证据理论的合成公式的合理性进行质疑。 例子例子：利用Dempster证据合成规则对两个目击证人（W1, W2）判断某宗“谋杀案” 的三个犯罪嫌疑人（Peter, Paul, Mary）中究竟谁是真正的凶手，得到的结果（认定Paul是凶手）却违背了人的常识推理结果，Zadeh认为这样的结果无法接受。m1()m2()m m1212() ()Peter0.990.000.000.00Paul0.010.011.001.00Mary0.000.990.000
21、.00火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 专家系统专家系统MYCIN的主要开发者之一的主要开发者之一Shortliffe：对证据理论的理论模型解释和算法实现进行了研究。 AI专家专家Dubois & Prade ：指出证据理论中的信任函数（Belief function）是一种模糊测度，以集合论的观点研究证据的并、交、补和包含等问题。 Smets等人等人：将信任函数推广到识别框架的所有模糊子集上，提出Pignistic概率和可传递信度模型（TBM）。 粗糙集理论的创始人粗糙集理论的创始人Pawlak：认为粗糙集理论使得无
22、限框架上的证据处理向有限框架上的证据处理的近似转化成为可能。证据理论的发展概况（证据理论的发展概况（续续1）火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 为了避免证据组合爆炸，提高证据合成的效率：为了避免证据组合爆炸，提高证据合成的效率： Voorbraak：提出一种Dempster证据合成公式的Bayes近似方法，使得焦元个数小于等于识别框架中元素的个数。 Dubois & Prade ：提出一种 “和谐近似”（Consonant approximation），即用和谐函数来代替原来的信任函数。 Tessem：提出了一种称为(k
23、, 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 6、证据理论在中国的发展情况、证据理论在中国的发展情况 段新生：段新生：在1993年出版了一本专门论述证据理
24、论的专著证据理论与决策、人工智能。【注：由于此书出版时间较早，故其内容不是很新，未能反映证据理论及其应用方面的最新成果】 刘大有等人：刘大有等人：国内较早研究证据理论的专家，并发表了一系列的论文，主要集中研究该理论的模型解释、理论扩展、近似实现等问题。 肖人彬等人：肖人彬等人：对证据的相关性及相关证据的组合问题进行了研究。 苏运霖、管纪文等人：苏运霖、管纪文等人：对证据理论与粗糙集理论进行了比较研究。 【苏运霖, 管纪文等. 证据论与约集论.软件学报,1999, 10(3): 277-282. 注：此处的“约集”即为“粗糙集”(Rough set)】火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋
25、财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 曾成等人：曾成等人：研究了不完备的识别框架下的证据合成问题，并提出相应的证据合成公式。 顾伟康等人：顾伟康等人：对证据合成公式进行扩展，提出一种改进的证据合成公式。 徐从富等人：徐从富等人：1999-2001总结国内外关于证据理论及其应用的代表性文献，先后发表2篇关于证据理论及其应用的综述文章。 证据理论在中国的发展情况（证据理论在中国的发展情况（续续）火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去5.2 5.2 经典证据理论经典证据理论 1 1、证据理论的主要特点、
26、证据理论的主要特点 满足比Bayes概率理论更弱的条件，即不必满足概不必满足概率可加性率可加性。 具有直接表达直接表达“不确定不确定”和和“不知道不知道”的能力，这些信息表示在mass函数中，并在证据合成过程中保留了这些信息。 证据理论不但允许人们将信度赋予假设空间的单个元素，而且还能赋予它的子集，这很象人类在各级抽象层很象人类在各级抽象层次上的证据收集过程次上的证据收集过程。火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 2 2、基本概念、基本概念 设是一个识别框架识别框架，或称假设空间假设空间。 （1）基本概率分配 基本概率分配
27、：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) 。 在识别框架上基于B
28、PA 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火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物
29、，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 3、Dempster合成规则合成规则 Dempster合成规则（Dempsters combinational rule）也称证据合成公式证据合成公式，其定义如下： 对于A，上的两个mass函数m1, m2的Dempster合成规则合成规则为：其中， K为归一化常数归一化常数火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 对于A，识别框架上的有限个mass函数m1, m2, ., mn的Dempster合成规则合成规则为：其中，n个个mass函数的函数的Dempster合
30、成规则合成规则火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去m1()m2()m12()Peter0.990.000.00Paul0.010.011.00Mary0.000.990.00 4、Dempster合成规则计算举例合成规则计算举例 例1. “Zadeh悖论悖论” ：某宗“谋杀案” 的三个犯罪嫌疑人组成了识别框架 =Peter, Paul, Mary ，目击证人（W1, W2）分别给出下表所示的BPA。【要求】：计算证人W1和W2提供证据的组合结果。【解】：首先，计算归一化常数K。火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财
31、物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去其次，利用Dempster证据合成规则分别计算Peter, Paul, Mary的组合BPA（即组合mass函数）。（1）关于Peter的组合mass函数（2）关于Paul的组合mass函数火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去（3）关于Mary的组合mass函数【说明】：对于这个简单的实例而言，对于Peter, Paul, Mary的组合mass函数，再求信任函数、似然函数，可知：信任函数值似然函数值组合后的mass函数值即， Bel(Peter) = Pl(P
32、eter) = m12(Peter) = 0 Bel(Paul) = Pl(Paul) = m12(Paul) = 1 Bel(Mary) = Pl(Mary) = m12(Mary) = 0火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 例2. 若修改“Zadeh悖论悖论” 表中的部分数据，如下表所示。请重新计算证人W1和W2提供证据的组合结果。【解】【解】：首先，计算归一化常数K。m1()m2()m12()Peter0.9800.49Paul0.010.010.015Mary00.980.49 =Peter, Paul, Mar
33、y0.010.010.005火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去归一化常数K的另一种计算法：火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去（1）计算关于）计算关于Peter的组合的组合mass函数函数火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去（2）计算关于）计算关于Paul的组合的组合mass函数函数火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇
34、敢地冲出去（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.
35、005 = 0.495 Bel() = Pl() = 0.49 + 0.015 + 0.49 + 0.005 = 1火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 5.3 5.3 关于证据理论的理论模型解释关于证据理论的理论模型解释 对Dempster-Shafer证据理论的解释共有四种： （1）上、下概率解释上、下概率解释（Upper and lower probability interpretation）； （2）广义化）广义化Bayes理论理论（Generalized Bayesian theory）解释； （3）随机集理论
36、随机集理论（Random sets）模型解释； （4）可传递信度模型）可传递信度模型（Transferable belief model，简称TBM）解释；【注】第(1)(3)这三种解释都以“概率理论”为基础的；而第(4)种，即TBM为“纯粹的”的DS理论模型，它已经完全从任何概率内涵中“提纯”了出来，不依赖于任何概率理论。火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 1、上、下概率解释 Dempster在1967年发表的第一篇关于证据理论的论文中给出了上、下概率的概念，用以表示不满足可加性的概率。 2、广义化Bayes理论解释
37、当mass函数m中的所有焦元都是单点集单点集（即单个假设集单个假设集），且这些焦元都满足Bayes独立条件时，Dempster证据合成公式就退化为Bayes公式，所以， Bayes公式是Dempster证据合成公式的特例特例。反过来说， Dempster证据合成公式是Bayes公式的广义化广义化。火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 3、随机集理论模型解释 Mahler和Fixsen分别于1996，1997年发表了下面两篇论文：1 Mahler, R. P. S. Combining ambiguous evidence
38、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 Cybern
39、etics- Part A: Systems and Humans, 1997, 27(1): 27-41.指出条件化(Conditional) Dempster-Shafer理论（简称CDS）和修改的(Modified) Dempster-Shafer理论（简称MDS）都是建立在随机集（随机集（Random）理论理论基础上的。火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 补充说明：补充说明： （1）当证据和先验知识都是模糊的情况下，则条件化Dempster-Shafer理论（CDS）是Bayes理论的广义化，它完全是一种概率理论
40、。 （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.】火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋
41、财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 4、可传递信度模型（可传递信度模型（TBM）解释解释 Smets认为从信度（信度（Belief）的“更新/条件化”（Updating/Conditioning）方式中，可以看出各种DS理论模型的主要差别。 (1) TBM模型模型 Smets发现许多DS模型的研究者只看到了BPA是在识别框架 的幕集上的静态概率分布，但他们都没有研究DS模型的动态部分，即信度是如何更新的，因此，提出了一种不依赖任何概率理论的不依赖任何概率理论的“可传递可传递信度模型信度模型TBM”。 火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披
42、上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 (2) TBM是一个双层模型是一个双层模型 “credal层”：位于底层，在该层中获取信度并对其进行量化、赋值和更新处理。 “pignistic层”：位于上层，它将credal层上的信度转换成pignistic概率，并由此做出决策。 只有必须做出决策时，pignistic层才出现。其中，pignistic概率分布公式如下：火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 (3) TBM模型的意义模型的意义 TBM模仿了人类的“思维思维”和“行动行动”的区别，即模仿了“推理”和“行为”的差别
43、： 推理：推理：表明信度是如何受证据影响的 行动：行动：从多个可行的行为方案中选择一个似乎是最好的 TBM实际上是一种层次化的递进模型层次化的递进模型，体现了证据的层次化描述特征，它比较适用于需要逐层进行数据、特征和决策层融合的数据融合系统。【说明】：上述关于证据理论的四种典型的解释模型，各有其适用领域，没有哪一个能适用于所有的应用领域，也不存在哪种模型更好的情况。火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 5.4 5.4 证据理论的实现途径证据理论的实现途径 Dempster合成公式的算法实现一直是困绕着DS理论的一个重点和难
44、点问题重点和难点问题，这直接关系到其实用性直接关系到其实用性。 1、实现途径分类 目前主要有如下三种途径： （1）针对特殊的证据组织结构，构造相应的快速算法针对特殊的证据组织结构，构造相应的快速算法 （注：该方法比较简单，故从略。感兴趣者可参考Barnett, Shafer等人的相关文献。） （2）近似计算）近似计算 （3）修改修改DS方法方法火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 2、Dempster合成规则的近似计算方法合成规则的近似计算方法 DS近似计算的基本思想：通过减少mass函数的焦元个数来达到计算的简化。 （1
45、 1）Voorbraak的工作的工作“Bayes近似法近似法” Voorbraak发现，如果mass函数的合成将产生一个Bayes信任函数（即一个识别框架上的概率测度），则mass函数用它们的Bayes近似来代替，将不会影响Dempster合成规则的结果。Voorbraak给出了mass函数的Bayes近似计算公式，即火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 Voorbraak证明了如下结论：massmass函数的函数的BayesBayes近似的合成近似的合成massmass函数的合成的函数的合成的BayesBayes近似近似
46、 Voorbraak的“Bayes近似法”的意义： 对于那些只关心识别框架中的“元素”（即单个假设）而不是其“子集”（即多个假设组成的子集）的最终结论的情况是非常有用的，并且大大简化了计算量。【注】：感兴趣者可参考本课件给出的Voorbraak 发表的相关论文。 Voobraak, F. A computationally efficient approximation of Dempster-Shafer theory. International Journal of Man-Machine Study, 1989, 30: 525-536. Bayes近似法（续）近似法（续）火灾袭来时要
47、迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 （2 2）Dubois&Prade的工作的工作“一致近似法一致近似法” 一致近似法：Consonant approximation 特点特点：通过近似计算后的焦元是嵌套的，且焦元个数不超过识别框架中的假设个数。 缺点缺点：该方法不太适合用Dempster合成规则来进行计算，可能会产生很大的误差。 用途用途：适用于证据的表达。【注】：感兴趣者可参考本章参考文献中列的Dubois&Prade发表的相关论文。火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥
48、勇敢地冲出去 （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函数，但它确实减少了焦元。火灾袭来时要迅速疏散逃生，不可蜂拥而出
49、或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去5.5 5.5 基于基于DSDS理论的不确定性推理理论的不确定性推理 基于DS理论的不确定性推理步骤如下： 步1：概率分配函数的确定 步2：证据和知识的不确定性表示 步3：组合证据不确定性的算法 步4：不确定性的传递算法 步5：得到最终的推理结果【注】：对基于DS理论的不确定性推理方法感兴趣者，可参考王永庆人工智能原理与方法中的“5.5.2 一个具体的不确定性推理模型”pp190-198。火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去5.6 5.6 计算举例计算举
50、例n假设在2001年美国发生“911事件”之前，布什总统分别接到美国中央情报局（CIA）和国家安全局（NSA）两大情报机构发来的绝密情报，其内容是关于中东地区的某些国家或组织企图对美国实施突然的恐怖袭击。CIA和NSA得到的证据如表1所示。试计算并回答下列问题： 1. 请直接利用Dempster证据合成公式计算表1中的所有“？”内容。 2. 根据BPA（mass函数值）的Bayes近似计算公式，重新调整表1中的BPA分布，并利用Dempster证据合成公式重新计算调整后的表1中的所有“？”内容。火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢
51、地冲出去 情报部门恐怖分子中央情报局（CIA）国家安全局（NSA）布什政府根据DS理论计算后的结果本拉登（简称“本本”）0.400.20？萨达姆（简称“萨萨”）0.300.20？霍梅尼（简称“霍霍”）0.100.05？本本拉登，萨萨达姆0.100.50？ = 本本, 萨萨, 霍霍0.100.05？表1 美国CIA和NSA所掌握的证据 火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去实例解答：n首先，计算归一化常数K。火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去实例解答（续
52、实例解答（续1）n计算关于本拉登（“本”）的组合mass函数火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去实例解答（续实例解答（续2）n同理可得：火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去实例解答（续实例解答（续3）n同理可得：火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去实例解答（续实例解答（续4）n同理可得：火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥
53、勇敢地冲出去实例解答（续实例解答（续5）n同理可得：火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 情报部门恐怖分子中央情报局（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 火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当
54、机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去计算计算BPA的的Bayes近似近似n根据BPA的Bayes近似公式：火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去BPA的的Bayes近似（续近似（续1）火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去BPA的的Bayes近似（续近似（续2）火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去BPA的的Bayes近似（续近似（续3）火灾袭来时要迅速疏散逃生，不可蜂
55、拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去BPA的的Bayes近似（续近似（续4）火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去BPA的的Bayes近似（续近似（续5）火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去BPA的的Bayes近似（续近似（续6）火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 情报部门恐怖分子中央情报局（CIA）国家安全局（NSA）布什政府根据DS理论计
56、算后的结果本拉登（简称“本本”）0.46150.4688？萨达姆（简称“萨萨”）0.38460.4688？霍梅尼（简称“霍霍”）0.15380.0625？本本拉登，萨萨达姆00？ = 本本, 萨萨, 霍霍00？表3 经Bayes变换后的BPA 火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去利用利用Dempster规则合成经规则合成经Bayes变换后的变换后的BPA先求新的归一化常数K火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去经经Bayes变换后的变换后的mass合成合
57、成火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去经经Bayes变换后的变换后的mass合成（续合成（续1）火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去经经Bayes变换后的变换后的mass合成（续合成（续2）火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 情报部门恐怖分子中央情报局（CIA）国家安全局（NSA）布什政府根据DS理论计算后的结果本拉登（简称“本本”）0.46150.46880.5326萨达姆（简
58、称“萨萨”）0.38460.46880.4438霍梅尼（简称“霍霍”）0.15380.06250.0236本本拉登，萨萨达姆000 = 本本, 萨萨, 霍霍000表4 经Bayes变换后的BPA的合成结果 火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 【作业】：请认真阅读Tessem，Voorbraak, Dubois & Prade，李岳峰，刘大有等人关于“Dempster证据合成公式”的近似计算方法的相关文献。 【要求】：深刻理解Dempster证据合成公式的典型的近似算法的求解过程。 【注】：可参考徐从富等人在模式识别与人工
59、智（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 additio
60、n 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
