2013证据理论ppt课件

证据理论 石峰 1 2020 4 25 2 证据理论 TheoryofEvidence 也称为D S Dempster Shafer 理论 证据理论 D S理论 最早是基于德姆斯特 A P Dempster 所做的工作 他试图用一个概率范围而不是单个的概率值去模拟不确定性 证据理论 2 1 证据理论的诞生和形成 诞生 源于20世纪60年代美国哈佛大学数学家A P Dempster在利用上 下限概率来解决多值映射问题方面的研究工作 自1967年起连续发表了一系列论文 标志着证据理论的正式诞生 形成 Dempster的学生G Shafer对证据理论做了进一步的发展 引入信任函数概念 形成了一套基于 证据 和 组合 来处理不确定性推理问题的数学方法 并于1976年出版了 证据的数学理论 AMathematicalTheoryofEvidence 这标志着证据理论正式成为一种处理不确定性问题的完整理论 3 2020 4 25 4 莎弗 G Shafer 进一步拓展了Dempster的工作 这一拓展称为证据推理 EvidentialReasoning 用于处理不确定性 不精确以及间或不准确的信息 由于证据理论将概率论中的单点赋值扩展为集合赋值 弱化了相应的公理系统 满足了比概率更弱的要求 因此可看作一种广义概率论 证据理论 4 证据理论的发展简况2 证据理论的名称 证据理论 EvidentialTheory Dempster Shafer理论 Dempster Shafer证据理论 DS 或D S 理论其它叫法 Dempster规则 Dempster合成规则 Dempster证据合成规则 5 3 证据理论的核心 优点及适用领域 核心 Dempster合成规则 这是Dempster在研究统计问题时首先提出的 随后Shafer把它推广到更为一般的情形 优点 由于在证据理论中需要的先验数据比概率推理理论中的更为直观 更容易获得 再加上Dempster合成公式可以综合不同专家或数据源的知识或数据 这使得证据理论在专家系统 信息融合等领域中得到了广泛应用 适用领域 信息融合 专家系统 情报分析 法律案件分析 多属性决策分析 等等 6 4 证据理论的局限性 要求证据必须是独立的 而这有时不易满足 证据合成规则没有非常坚固的理论支持 其合理性和有效性还存在较大的争议 计算上存在着潜在的指数爆炸问题 7 2020 4 25 8 在证据理论中 引入了信任函数来度量不确定性 并引用似然函数来处理由于 不知道 引起的不确定性 并且不必事先给出知识的先验概率 与主观Bayes方法相比 具有较大的灵活性 因此 证据理论得到了广泛的应用 同时 可信度可以看作是证据理论的一个特例 证据理论给了可信度一个理论性的基础 证据理论 2020 4 25 9 证据的不确定性 在D S理论中 可以分别用信任函数 似然函数及类概率函数来描述知识的精确信任度 不可驳斥信任度及估计信任度 即可以从各个不同角度刻画命题的不确定性 D S理论采用集合来表示命题 先建立命题与集合之间的一一对应关系 把命题的不确定性问题转化为集合的不确定性问题 2020 4 25 10 设 为变量x的所有可能取值的有限集合 亦称样本空间 且 中的每个元素都相互独立 则由 的所有子集构成的集合称为幂集 记为2 当 中的元素个数为N时 则其幂集的元素个数为2N 且其中的每一个元素A都对应于一个关于x的命题 称该命题为 x的值在A中 证据的不确定性 2020 4 25 11 如 用x代表所看到的颜色 红 黄 蓝 则A 红 表示 x是红色 若A 红 蓝 则表示 x或者是红色 或者是蓝色 证据的不确定性 2020 4 25 12 l 概率分配函数 定义设函数m 2 0 1 且满足则称m是2 上的概率分配函数 m A 称为A的基本概率数 m A 表示依据当前的环境对假设集A的信任程度 2020 4 25 13 对于上面给出的有限集 红 黄 蓝 若定义2 上的一个基本函数m m 红 黄 蓝 红 黄 红 蓝 黄 蓝 红 黄 蓝 0 0 3 0 0 1 0 2 0 2 0 1 0 1 其中 0 0 3 0 0 1 0 2 0 2 0 1 0 1 分别是幂集中各个子集的基本概率数 显然m满足概率分配函数的定义 例子说明 2020 4 25 14 1 概率分配函数的作用是把 的任意一个子集都映射为 0 1 上的一个数m A 当A包含于 且A由单个元素组成时 m A 表示对A的精确信任度 当A包含于 A 且A由多个元素组成时 m A 也表示对A的精确信任度 但却不知道这部分信任度该分给A中哪些元素 当A 时 则m A 是对 的各个子集进行信任分配后剩下的部分 它表示不知道该如何对它进行分配 对概率分配函数的几点说明 2020 4 25 15 以 红 黄 蓝 为例说明 当A 红 时 由于m A 0 3 它表示对命题 x是红色 的精确信任度为0 3 当A 红 黄 时 由于m A 0 2 它表示对命题 x或者是红色 或者是黄色 的精确信任度为0 2 却不知道该把这0 2分给 红 还是分给 黄 当A 红 黄 蓝 时 由于m A 0 2 表示不知道该对这0 2如何分配 但它不属于 红 就一定属于 黄 或 蓝 只是基于现有的知识 还不知道该如何分配而已 例如 2020 4 25 16 2 m是2 上而非 上的概率分布 所以基本概率分配函数不是概率 它们不必相等 而且m A l m A 事实上m 红 m 黄 m 蓝 0 3 0 0 1 0 4 1 概率分配函数的几点说明 2020 4 25 17 2 信任函数 定义信任函数 BeliefFunction Bel 2 0 1 对任意的有 Bel A 表示当前环境下 对假设集A的信任程度 其值为A的所有子集的基本概率之和 表示对A的总的信任度 2020 4 25 18 以 红 黄 蓝 为例说明 Bel 红 黄 m 红 m 黄 m 红 黄 0 3 0 0 2 0 5 当A为单一元素组成的集合时 Bel A m A 如果命题 x在B中 成立 必带有命题 x在A中 成立 Bel A 函数又称为下限函数 例如 2020 4 25 19 3 似然函数 定义似然函数 PlausibilityFunction 对任意的有 Pl A 1 Bel A 其中 A A 似然函数又称为不可驳斥函数或上限函数 由于Bel A 表示对A为真的信任度 Bel A 表示对 A的信任度 即A为假的信任度 因此 Pl A 表示对A为非假的信任度 2020 4 25 20 以 红 黄 蓝 为例说明 Pl 红 1 Bel 红 1 Bel 黄 蓝 1 m 黄 m 蓝 m 黄 蓝 1 0 0 1 0 1 0 8这里0 8是 红 为非假的信任度 由于 红 为真的精确信任度为0 3 而剩下的0 8 0 3 0 5 则是知道非假 但却不能肯定为真的那部分 例如 2020 4 25 21 推论 该式可推广为 可见 2020 4 25 22 因此命题 x在A中 的似然性 由与命题 x在B中 有关的m值确定 其中命题 x在B中 并不会使得命题 x不在A中 成立 所以一个事件的似然性是建立在对其相反事件不信任的基础上的 推论 2020 4 25 23 1 Bel 0 Bel l Pl O Pl 1 2 如果 则Bel A Bel B Pl A Pl B 3 Pl A Bel A Bel A Bel A l Pl A Pl A 1 信任函数和似然函数有如下的性质 2020 4 25 24 由于Bel A 和Pl A 分别表示A为真的信任度和A为非假的信任度 因此 可分别称Bel A 和Pl A 为对A信任程度的下限和上限 记为A Bel A Pl A Pl A Bel A 表示既不信任A 也不信任 A的程度 即对于A是真是假不知道的程度 下限 上限 信任区间 2020 4 25 25 如 在前面的例子中 曾求过Bel 红 0 3 Pl 红 0 8 因此有 红 0 3 0 8 它表示对 红 的精确信任度为0 3 不可驳斥部分为0 8 肯定不是 红 的为0 2 信任区间 2020 4 25 26 4 假设集A的类概率函数f A 其中 A 分别表示A和 中包含元素的个数 类概率函数f A 也可以用来度量证据A的不确定性 2020 4 25 27 f A 有如下的性质 1 2 3 Bel A f A Pl A forA 4 f A 1 f A forA 证据E的不确定性可以用类概率函数f E 表示 原始证据的f E 应由用户给出 作为中间结果的证据可以由下面的不确定性传递算法确定 2020 4 25 28 证据的组合函数 在实际问题中 对于相同的证据 由于来源不同 可能会得到不同的概率分配函数 例如 考虑 红 黄 假设从不同知识源得到的概率分配函数分别为 m1 红 黄 红 黄 0 0 4 0 5 0 1 m2 红 黄 红 黄 0 0 6 0 2 0 2 在这种情况下 需要对它们进行组合 2020 4 25 29 定义设m1和m2是两个不同的概率分配函数 则其正交和m m1 m2满足 其中 正交和概念 2020 4 25 30 如果K O 则正交和m也是一个概率分配函数 如果K 0 则不存在正交和m 称m1与m2矛盾 注意 2020 4 25 31 设 a b 且从不同知识源得到的概率分配函数分别为m1 a b a b 0 0 3 0 5 0 2 m2 a b a b 0 0 6 0 3 0 1 求正交和m m1 m2 例3 2020 4 25 32 解 先求K 再求m a b a b 由于 2020 4 25 33 同理可得 m b 0 43 m a b 0 03故有m a b a b 0 0 54 0 43 0 03 2020 4 25 34 规则的不确定性 具有不确定性的推理规则可表示为 IfEThenH CF其中 H为假设 E为支持H成立的假设集 它们是命题的逻辑组合 CF为可信度因子 H可表示为 H a1 a2 am ai i l 2 m H为假设集合 的子集 2020 4 25 35 CF c1 c2 cm ci用来描述前提E成立时ai的可信度 CF应满足如下条件 规则的不确定性 2020 4 25 36 定义对于不确定性规则 IfEThenH CF定义 m ai f E ci i l 2 m 或表示为m a1 a2 am f E c1 f E c2 f E cm 规则的不确定性 2020 4 25 37 规定 而对于 的所有其他子集H 均有 m H 0 当H为 的真子集时 有 进一步可以计算Pl H 和f H 2020 4 25 38 不确定性的组合 当规则的前提 证据 E是多个命题的合取或析取时 定义 2020 4 25 39 当有多条规则支持同一结论时 如果H a1 a2 an 则 IfE1ThenH CF1 CF1 c11 c12 c1n IfE2ThenH CF2 CF2 c21 c22 c2n IfEmThenH CFm CFm cm1 cm2 cmn 不确定性的组合 2020 4 25 40 如果这些规则相互独立地支持结论H的成立 可以先计算mi a1 a2 an f Ei ci1 f Ei ci2 f Ei cim i l 2 m 然后根据前面介绍的求正交和的方法 对这些mi求正交和 以组合所有规则对结论H的支持 一旦累加的正交和m H 计算出来 就可以计算Bel H Pl H f H 不确定性的组合 2020 4 25 41 有如下的推理规则 R1 IfE1 E2 E3 ThenA1 a11 a12 a13 CF1 0 2 0 3 0 4 R2 IfE4 E5 E6 ThenA2 a21 CF2 0 7 R3 IfA1ThenA a1 a2 CF3 0 4 0 5 R4 IfA2ThenA a1 a2 CF4 0 4 0 4 例 2020 4 25 42 这些规则形成如图所示的推理网络 原始数据的概率在系统中己经给出 f E1 0 5 f E2 0 7 f E3 0 9 f E4 0 9 f E5 0 8 f E6 0 7 假设 10 现在需要求出A的确定性f A 2020 4 25 43 解 第一步 求A1的确定性 2020 4 25 44 第二步 求A2的确定性 2020 4 25 45 第三步 求A的确定性 根据R3和R4 有 m3 a1 a2 0 74 0 4 0 74 0 5 0 30 0 37 m4 a1 a2 0 6 0 4 0 6 0 4 0 24 0 24 m3 1 m3 a1 m3 a2 1 0 30 0 37 0 33m4 1 m4 a1 m4 a2 1 0 24 0 24 0 52 2020 4 25 46 由正交和公式得到 2020 4 25 47 则有 于是 Bel A m a1 m a2 0 37 0 41 0 78Pl A 1 Bel A 1 0 1f A Bel A A Pl A Bel A 0 78 2 10 1 0 78 0 82 2020 4 25 48 证据理论的优点在于能够满足比概率论更弱的公理系统 可以区分不知道和不确定的情况 可以依赖证据的积累 不断缩小假设的集合 证据理论的优点 2020 4 25 49 证据理论最早是作为经典概率理论的扩展而引入的 所以受到很多的批评 在证据理论中 证据的独立性不易得到保证 基本概率分配函数要求给的值太多 计算传递关系复杂 随着诊断问题可能答案的增加 证据理论的计算呈指数增长 传递关系复杂 比较难以实现 证据理论的不足 http www hds utc fr tdenoeux dokuwiki doku php 50 Zadeh悖论 对证据理论的合成公式的合理性进行质疑 例子 利用Dempster证据合成规则对两个目击证人 W1 W2 判断某宗 谋杀案 的三个犯罪嫌疑人 Peter Paul Mary 中究竟谁是真正的凶手 得到的结果 认定Paul是凶手 却违背了人的常识推理结果 Zadeh认为这样的结果无法接受 51 Dempster合成规则计算举例例1 Zadeh悖论 某宗 谋杀案 的三个犯罪嫌疑人组成了识别框架 Peter Paul Mary 目击证人 W1 W2 分别给出下表所示的BPA 要求 计算证人W1和W2提供证据的组合结果 解 首先 计算归一化常数K 52 其次 利用Dempster证据合成规则分别计算Peter Paul Mary的组合BPA 即组合mass函数 1 关于Peter的组合mass函数 2 关于Paul的组合mass函数 53 3 关于Mary的组合mass函数 说明 对于这个简单的实例而言 对于Peter Paul Mary的组合mass函数 再求信任函数 似然函数 可知 信任函数值 似然函数值 组合后的mass函数值即 Bel Peter Pl Peter m12 Peter 0Bel Paul Pl Paul m12 Paul 1Bel Mary Pl Mary m12 Mary 0 54 例2 若修改 Zadeh悖论 表中的部分数据 如下表所示 请重新计算证人W1和W2提供证据的组合结果 解 首先 计算归一化常数K 55 归