DS证据理论 浙大课件.ppt

《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-S证 据 理 论(Chapter5 D-S Evidential Theory ) Outlinen 本 章

2、 的 主 要 参 考 文 献n 证 据 理 论 的 发 展 简 况n 经 典 证 据 理 论n 关 于 证 据 理 论 的 理 论 模 型 解 释n 证 据 理 论 的 实 现 途 径n 基 于 DS理 论 的 不 确 定 性 推 理 n 计 算 举 例 1 Dempster, A. P. Upper and lower probabilities induced by a multivalued mapping. Annals of Mathematical Statistics, 1967, 38(2): 325-339. 【 提 出证 据 理 论 的 第 一 篇 文 献 】2 Demps

3、ter, 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 mathemati

4、cal 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 Maga

5、zine, 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”. Int

6、ernational 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 Intelli

7、gence, 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-

8、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均 为 证据 理 论 近 似 计 算

9、方 法 】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. 【 提 出 了 一 种 实 现 证 据 理 论 的 “ 修剪

10、算 法 ” 】本 章 的 主 要 参 考 文 献 （ 续 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

11、, 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

12、. International Journal of Approximate Reasoning, 2002, 31: 31-75. 本 章 的 主 要 参 考 文 献 （ 续 3） 19 段 新 生 . 证 据 理 论 与 决 策 、 人 工 智 能 . 中 国 人 民 大 学 出 版 社 , 1993. 20 徐 从 富 等 . Dempster-Shafer证 据 推 理 方 法 理 论 与 应 用 的 综 述 . 模式 识 别 与 人 工 智 能 , 1999, 12(4): 424-430. 21 徐 从 富 等 . 面 向 数 据 融 合 的 DS方 法 综 述 . 电 子 学 报

13、 , 2001, 29(3): 393-396.22 徐 从 富 等 . 解 决 证 据 推 理 中 一 类 “ 0绝 对 化 ” 问 题 的 方 法 . 计 算 机科 学 , 2000, 27(5): 53-56. 23 李 岳 峰 等 . 证 据 理 论 中 的 近 似 计 算 方 法 . 吉 林 大 学 自 然 科 学 学 报 , 1995, (1):28-32.24 刘 大 有 等 . 广 义 证 据 理 论 的 解 释 . 计 算 机 学 报 , 1997, 20(2): 158-164.25 刘 大 有 等 . 凸 函 数 证 据 理 论 模 型 . 计 算 机 研 究 与 发 展

14、 , 2000, 37(2): 175-181.本 章 的 主 要 参 考 文 献 （ 续 4） 26 杨 莹 等 . 对 一 种 基 于 证 据 理 论 的 不 确 定 性 处 理 模 型 的 重 要 扩 充 . 计算 机 学 报 , 1990, (10): 772-778. 27 刘 大 有 等 . 一 种 简 化 证 据 理 论 模 型 的 研 究 . 计 算 机 研 究 与 发 展 , 1999, 36(2): 134-138.28 肖 人 彬 等 . 相 关 证 据 合 成 方 法 的 研 究 . 模 式 识 别 与 人 工 智 能 , 1993, 6(3): 227-234. 29

15、 孙 全 等 . 一 种 新 的 基 于 证 据 理 论 的 合 成 公 式 . 电 子 学 报 , 2000, 28(8): 117-119.30 曾 成 , 赵 保 军 , 何 佩 昆 . 不 完 备 框 架 下 的 证 据 组 合 方 法 . 电 子 与 信 息学 报 , 2005, 27(7): 1043-1046. 31 王 永 庆 . 人 工 智 能 原 理 与 方 法 . 西 安 交 通 大 学 出 版 社 , 1998. pp. 185-197. （ 第 5章 第 5.5节 “ 证 据 理 论 ” ）本 章 的 主 要 参 考 文 献 （ 续 5） 5.1 证 据 理 论 的

16、发 展 简 况 1、 证 据 理 论 的 名 称 证 据 理 论 (Evidential Theory) Dempster-Shafer理 论 Dempster-Shafer证 据 理 论 DS (或 D-S)理 论其 它 叫 法 ： Dempster规 则 Dempster合 成 规 则 Dempster证 据 合 成 规 则 2、 证 据 理 论 的 诞 生 和 形 成 诞 生 ： 源 于 20世 纪 60年 代 美 国 哈 佛 大 学 数 学 家 A. P. Dempster在 利 用 上 、 下 限 概 率 来 解 决 多 值 映 射 问 题 方 面 的研 究 工 作 。 自 1967

17、年 起 连 续 发 表 了 一 系 列 论 文 ， 标 志 着 证据 理 论 的 正 式 诞 生 。 形 成 ： Dempster的 学 生 G. Shafer对 证 据 理 论 做 了 进 一步 的 发 展 ， 引 入 信 任 函 数 概 念 ， 形 成 了 一 套 基 于 “ 证 据 ”和 “ 组 合 ” 来 处 理 不 确 定 性 推 理 问 题 的 数 学 方 法 ， 并 于1976年 出 版 了 证 据 的 数 学 理 论 (A Mathematical Theory of Evidence)， 这 标 志 着 证 据 理 论 正 式 成 为 一 种 处 理 不 确 定性 问 题 的

18、 完 整 理 论 。 3、 证 据 理 论 的 核 心 、 优 点 及 适 用 领 域 核 心 ： Dempster合 成 规 则 ， 这 是 Dempster在 研 究统 计 问 题 时 首 先 提 出 的 ， 随 后 Shafer把 它 推 广 到 更 为 一般 的 情 形 。 优 点 ： 由 于 在 证 据 理 论 中 需 要 的 先 验 数 据 比 概 率 推理 理 论 中 的 更 为 直 观 、 更 容 易 获 得 ， 再 加 上 Dempster合成 公 式 可 以 综 合 不 同 专 家 或 数 据 源 的 知 识 或 数 据 ， 这 使得 证 据 理 论 在 专 家 系 统 、

19、 信 息 融 合 等 领 域 中 得 到 了 广 泛应 用 。 适 用 领 域 ： 信 息 融 合 、 专 家 系 统 、 情 报 分 析 、 法 律案 件 分 析 、 多 属 性 决 策 分 析 ， 等 等 。 4、 证 据 理 论 的 局 限 性 要 求 证 据 必 须 是 独 立 的 ， 而 这 有 时 不 易 满 足 证 据 合 成 规 则 没 有 非 常 坚 固 的 理 论 支 持 ， 其 合 理性 和 有 效 性 还 存 在 较 大 的 争 议 计 算 上 存 在 着 潜 在 的 指 数 爆 炸 问 题 5、 证 据 理 论 的 发 展 概 况 “ Zadeh悖 论 ” ： 对 证

20、 据 理 论 的 合 成 公 式 的 合 理 性 进 行质 疑 。 例 子 ： 利 用 Dempster证 据 合 成 规 则 对 两 个 目 击 证 人（ W1, W2） 判 断 某 宗 “ 谋 杀 案 ” 的 三 个 犯 罪 嫌 疑 人 （ Peter, Paul, Mary） 中 究 竟 谁 是 真 正 的 凶 手 ， 得 到 的 结 果 （ 认 定 Paul是 凶 手 ） 却 违 背 了 人 的 常 识 推 理 结 果 ， Zadeh认 为 这 样 的 结 果无 法 接 受 。 m 1() m2()Peter 0.99 0.00Paul 0.01 0.01Mary 0.00 0.99

21、专 家 系 统 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 + 0.005 = 0.495 Bel() = Pl() = 0.49 + 0.015 + 0.49 + 0.005 = 1 5.3 关 于 证 据 理 论 的 理 论

22、 模 型 解 释 对 Dempster-Shafer证 据 理 论 的 解 释 共 有 四 种 ： （ 1） 上 、 下 概 率 解 释 （ Upper and lower probability interpretation） ； （ 2） 广 义 化 Bayes理 论 （ Generalized Bayesian theory） 解 释 ； （ 3） 随 机 集 理 论 （ Random sets） 模 型 解 释 ； （ 4） 可 传 递 信 度 模 型 （ Transferable belief model， 简 称 TBM）解 释 ；【 注 】 第 (1)(3)这 三 种 解 释 都

23、 以 “ 概 率 理 论 ” 为 基 础 的 ； 而 第 (4)种 ， 即TBM为 “ 纯 粹 的 ” 的 DS理 论 模 型 ， 它 已 经 完 全 从 任 何 概 率 内 涵 中 “ 提 纯 ” 了 出 来 ， 不 依 赖 于 任 何 概 率 理 论 。 1、 上 、 下 概 率 解 释 Dempster在 1967年 发 表 的 第 一 篇 关 于 证 据 理 论 的 论 文 中给 出 了 上 、 下 概 率 的 概 念 ， 用 以 表 示 不 满 足 可 加 性 的 概 率 。 2、 广 义 化 Bayes理 论 解 释 当 mass函 数 m中 的 所 有 焦 元 都 是 单 点 集

24、 （ 即 单 个 假 设集 ） ， 且 这 些 焦 元 都 满 足 Bayes独 立 条 件 时 ， Dempster证 据合 成 公 式 就 退 化 为 Bayes公 式 ， 所 以 ， Bayes公 式 是 Dempster证 据 合 成 公 式 的 特 例 。反 过 来 说 ， Dempster证 据 合 成 公 式 是 Bayes公 式 的 广 义 化 。 3、 随 机 集 理 论 模 型 解 释 Mahler和 Fixsen分 别 于 1996， 1997年 发 表 了 下 面 两 篇 论 文 ：1 Mahler, R. P. S. Combining ambiguous evide

25、nce 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 Cy

26、bernetics- Part A: Systems and Humans, 1997, 27(1): 27-41.指 出 条 件 化 (Conditional) Dempster-Shafer理 论 （ 简 称 CDS） 和修 改 的 (Modified) Dempster-Shafer理 论 （ 简 称 MDS） 都 是 建 立在 随 机 集 （ Random） 理 论 基 础 上 的 。 补 充 说 明 ： （ 1） 当 证 据 和 先 验 知 识 都 是 模 糊 的 情 况 下 ， 则 条 件 化Dempster-Shafer理 论 （ CDS） 是 Bayes理 论 的 广 义 化

27、， 它 完 全是 一 种 概 率 理 论 。 （ 2） 当 证 据 和 先 验 知 识 都 是 统 计 独 立 时 ， 则 条 件 化Dempster-Shafer理 论 （ CDS） 的 证 据 合 成 相 当 于 随 机 条 件 事件 的 并 （ 或 交 ） 。 Yen在 医 疗 专 家 系 统 GERTIS中 提 出 了 扩 展 （ Extended） 的Dempster-Shafer理 论 （ 简 称 EDS） ， 实 际 上 EDS就 是 一 种 CDS或 MDS。【 Yen, J. GERTIS: a Dempster-Shafer approach to diagnosing h

28、ierarchical hypotheses. Communications of the ACM, 1989, 32(5): 573-585.】 4、 可 传 递 信 度 模 型 （ TBM） 解 释 Smets认 为 从 信 度 （ Belief） 的 “ 更 新 /条 件 化 ”（ Updating/Conditioning） 方 式 中 ， 可 以 看 出 各 种 DS理 论 模 型 的 主 要 差 别 。 (1) TBM模 型 Smets发 现 许 多 DS模 型 的 研 究 者 只 看 到 了 BPA是在 识 别 框 架 的 幕 集 上 的 静 态 概 率 分 布 ， 但 他 们

29、都没 有 研 究 DS模 型 的 动 态 部 分 ， 即 信 度 是 如 何 更 新 的 ，因 此 ， 提 出 了 一 种 不 依 赖 任 何 概 率 理 论 的 “ 可 传 递信 度 模 型 TBM”。 ( )( ) | |x A m Ap x A (2) TBM是 一 个 双 层 模 型 “ credal层 ” ： 位 于 底 层 ， 在 该 层 中 获 取 信 度 并 对其 进 行 量 化 、 赋 值 和 更 新 处 理 。 “ pignistic层 ” ： 位 于 上 层 ， 它 将 credal层 上 的 信 度转 换 成 pignistic概 率 ， 并 由 此 做 出 决 策 。

30、 只 有 必 须 做 出 决 策 时 ， pignistic层 才 出 现 。 其 中 ，pignistic概 率 分 布 公 式 如 下 ： (3) TBM模 型 的 意 义 TBM模 仿 了 人 类 的 “ 思 维 ” 和 “ 行 动 ” 的 区 别 ， 即模 仿 了 “ 推 理 ” 和 “ 行 为 ” 的 差 别 ： 推 理 ： 表 明 信 度 是 如 何 受 证 据 影 响 的 行 动 ： 从 多 个 可 行 的 行 为 方 案 中 选 择 一 个 似 乎 是 最 好 的 TBM实 际 上 是 一 种 层 次 化 的 递 进 模 型 ， 体 现 了 证 据的 层 次 化 描 述 特 征

31、 ， 它 比 较 适 用 于 需 要 逐 层 进 行 数 据 、 特征 和 决 策 层 融 合 的 数 据 融 合 系 统 。【 说 明 】 ： 上 述 关 于 证 据 理 论 的 四 种 典 型 的 解 释 模 型 ， 各 有 其 适 用 领域 ， 没 有 哪 一 个 能 适 用 于 所 有 的 应 用 领 域 ， 也 不 存 在 哪 种 模 型 更 好 的情 况 。 5.4 证 据 理 论 的 实 现 途 径 Dempster合 成 公 式 的 算 法 实 现 一 直 是 困 绕 着 DS理 论的 一 个 重 点 和 难 点 问 题 ， 这 直 接 关 系 到 其 实 用 性 。 1、 实

32、 现 途 径 分 类 目 前 主 要 有 如 下 三 种 途 径 ： （ 1） 针 对 特 殊 的 证 据 组 织 结 构 ， 构 造 相 应 的 快 速 算 法 （ 注 ： 该 方 法 比 较 简 单 ， 故 从 略 。 感 兴 趣 者 可 参 考 Barnett, Shafer等 人 的 相 关 文 献 。 ） （ 2） 近 似 计 算 （ 3） 修 改 DS方 法 2、 Dempster合 成 规 则 的 近 似 计 算 方 法 DS近 似 计 算 的 基 本 思 想 ： 通 过 减 少 mass函 数 的 焦 元 个 数来 达 到 计 算 的 简 化 。 （ 1） Voorbraak的

33、 工 作 “ Bayes近 似 法 ” Voorbraak发 现 ， 如 果 mass函 数 的 合 成 将 产 生 一 个 Bayes信任 函 数 （ 即 一 个 识 别 框 架 上 的 概 率 测 度 ） ， 则 mass函 数 用 它们 的 Bayes近 似 来 代 替 ， 将 不 会 影 响 Dempster合 成 规 则 的 结 果 。Voorbraak给 出 了 mass函 数 的 Bayes近 似 计 算 公 式 ， 即( )( ) ( ) | | 0, A BC m B Am A m C C ， 若 是 单 个 假 设 集 合 否 则 Voorbraak证 明 了 如 下 结

34、论 ：mass函 数 的 Bayes近 似 的 合 成 mass函 数 的 合 成 的 Bayes近 似 Voorbraak的 “ Bayes近 似 法 ” 的 意 义 ： 对 于 那 些 只 关 心 识 别 框 架 中 的 “ 元 素 ” （ 即 单 个 假 设 ） 而不 是 其 “ 子 集 ” （ 即 多 个 假 设 组 成 的 子 集 ） 的 最 终 结 论 的 情 况是 非 常 有 用 的 ， 并 且 大 大 简 化 了 计 算 量 。【 注 】 ： 感 兴 趣 者 可 参 考 本 课 件 给 出 的 Voorbraak 发 表 的 相 关 论 文 。 Voobraak, F. A c

35、omputationally efficient approximation of Dempster-Shafer theory. International Journal of Man-Machine Study, 1989, 30: 525-536. Bayes近 似 法 （ 续 ） （ 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