DS证据理论课件.ppt

证据理论 证据理论是由德普斯特 A P Dempster 首先提出 并由沙佛 G Shafer 进一步发展起来的一种处理不确定性的理论 因此又称为D S理论 证据理论与Bayes理论区别 Bayes理论 需要有统一的识别框架 完整的先验概率和条件概率知识 只能将概率分派函数指定给完备的互不包含的假设 证据理论 用先验概率分派函数去获得后验的证据区间 证据区间量化了命题的可信程度 可将证据分派给假设或命题 提供了一定程度的不确定性 即证据既可指定给互不相容的命题 也可指定给相互重叠 非互不相容的命题 证据理论满足比概率论更弱的公理系统 当概率值已知时 证据理论就变成了概率论 D S理论 基本理论一个具体的不确定性推理模型举例小结 基本理论 设D是变量x所有可能取值的集合 且D中的元素是互斥的 在任一时刻x都取且只能取D中的某一个元素为值 则称D为x的样本空间 也称D为辨别框 在证据理论中 D的任何一个子集A都对应于一个关于x的命题 称该命题为 x的值在A中 引入三个函数 概率分配函数 信任函数及似然函数等概念 概率分配函数 设D为样本空间 领域内的命题都用D的子集表示 则概率分配函数定义如下 定义1 设函数M 2D 0 1 且满足M 0 M A 1A D则称M是2D上的概率分配函数 M A 称为A的基本概率数 说明 设样本空间D中有n个元素 则D中子集的个数为2n个 定义中的2D就是表示这些子集的 概率分配函数的作用是把D的任意一个子集A都映射为 0 1 上的一个数M A 当A D时 M A 表示对相应命题的精确信任度 实际上就是对D的各个子集进行信任分配 M A 表示分配给A的那一部分 当A由多个元素组成时 M A 不包括对A的子集的精确信任度 而且也不知道该对它如何进行分配 当A D时 M A 是对D的各子集进行信任分配后剩下的部分 它表示不知道该对这部分如何进行分配 定义 若A D则M A 0 称A为M的一个焦元 概率分配函数不是概率 信任函数 定义2 命题的信任函数Bel 2D 0 1 且Bel A M B 对所有的A DB A其中2D表示D的所有子集 Bel函数又称为下限函数 Bel A 表示对命题A为真的信任程度 由信任函数及概率分配函数的定义推出 Bel M 0Bel D M B 1B D 似然函数 定义3 似然函数Pl 2D 0 1 且Pl A 1一Bel A 其中A D似然函数的含义 由于Bel A 表示对A为真的信任程度 所以Bel A 就表示对非A为真 即A为假的信任程度 由此可推出Pl A 表示对A为非假的信任程度 似然函数又称为不可驳斥函数或上限函数 推广到一般情况可得出 Pl A M B A B 证明如下 Pl A M B 1 Bel A M B A B A B 1 Bel A M B A B 1 M C M B C AA B 1 M E E D 0 Pl A M B A B 信任函数与似然函数的关系 Pl A Bel A 证明 Bel A 十Bel A M B M C B AC A M E 1E D Pl A Bel A 1 Bel A 一Bel A 1 Bel A Bel A 0 Pl A Bel A 由于Bel A 表示对A为真的信任程度 Pl A 表示对A为非假的信任程度 因此可分别称Bel A 和Pl A 为对A信任程度的下限与上限 记为A Bel A Pl A 01 1 1 A为真 BelPl 0 0 A为假 确知未知确知 0 1 对A一无所知 单位元 为真为假Pl A Bel A 对A不知道的程度 下面用例子进一步说明下限与上限的意义 A 0 25 1 由于Bel A 0 25 说明对A为真有一定程度的信任 信任度为0 25 另外 由于Bel A 1 Pl A 0 说明对 A不信任 所以A 0 25 1 表示对A为真有0 25的信任度 A 0 0 85 由于Bel A 0 而Bel A 1一Pl A 1 0 85 0 15 所以A 0 0 85 表示对A为假有一定程度的信任 信任度为0 15 A 0 25 0 85 由于Bel A 0 25 说明对A为真有0 25的信任度 由于Bel A 1 0 85 0 15 说明对A为假有0 15的信任度 所以A 0 25 0 85 表示对A为真的信任度比对A为假的信任度稍高一些 概率分配函数的正交和 定义4 设M1和M2是两个概率分配函数 则其正交和M M1 M2为M 0M A K 1 M1 x M2 y x y A其中 K 1 M1 x M2 y M1 x M2 y x y x y 如果K 0 则正交和M也是一个概率分配函数 如果K 0 则不存在正交和M 称M1与M2矛盾 定义5 设M1 M2 Mn是n个概率分配函数 则其正交和M M1 M2 Mn为M 0M A K 1 Mi Ai Ai A1 i n其中 K Mi Ai Ai 1 i n例 设D 黑 白 且M1 黑 白 黑 白 0 3 0 5 0 2 0 M2 黑 白 黑 白 0 6 0 3 0 1 0 K 1 M1 x M2 y 0 61x y M 黑 K 1 M1 x M2 y 0 54x y 黑 同理可得M 白 0 43 M 黑 白 0 03所以 组合后的概率分配函数为M 黑 白 黑 白 0 54 0 43 0 03 0 一个具体的不确定性推理模型 信任函数Bel A 和似然函数Pl A 分别表示对命题A信任程度的下限与上限 两元组 Bel A Pl A 表示证据的不确定性 不确定性知识用Bel和Pl分别表示规则强度的下限与上限 在此表示的基础上建立相应的不确定性推理模型 由于信任函数与似然函数都是在概率分配函数的基础上定义的 因而随着概率分配函数的定义不同 将会产生不同的应用模型 概率分配函数与类概率函数 样本空间D s1 s2 sn 上的概率分配函数按如下要求定义 1 M si 0对任何si Dn 2 M si 1i ln 3 M D 1 M si i 1 4 当A D且 A 1或 A 0时 M A 0其中 A 表示命题A对应集合中元素的个数 性质 Bel A M si si AnBel D M si M D 1i lPl A 1 Bel A 1 M si si An 1 M si M si i 1si A 1 1 M D Bel A M D Bel A Pl D 1 Bel D 1 Bel 1显然 对任何A D及B D均有 Pl A Bel A Pl B Bel B M D 它表示对A 或B 不知道的程度 由该概率分配函数的定义 可把概率分配函数M1与M2的正交和简化为M si K 1 Ml si M2 si M1 si M2 D M1 D M2 si 其中 K可由下式计算 K M1 D M2 D n M1 si M2 si M1 si i 1M2 D M1 D xM2 si 定义6 命题A的类概率函数为f A Bel A Pl A 一Bel A 其中 A丨和 D 分别是A及D中元素的个数 f A 具有如下性质 n 1 f si 1i 1 2 对任何A D 有Bel A f A Pl A f A 1 f A 由以上性质可得到如下推论 1 f 0 2 f D 1 3 对任何A D 有0 f A 1 A D 知识不确定性的表示 在该模型中 不确定性知识用如下形式的产生式规则表示 IFETHENH h1 h2 hn CF c1 c2 Cn 其中 1 E为前提条件 它既可以是简单条件 也可以是用AND或OR连接起来的复合条件 2 H是结论 它用样本空间中的子集表示 h1 h2 hn是该子集中的元素 3 CF是可信度因子 用集合形式表示 其中ci用来指出hi i 1 2 n 的可信度 ci与hi一一对应 Ci应满足如下条件 ci 0i 1 2 n ci 1i 1 证据不确定性的表示 不确定性证据E的确定性用CER E 表示 对于初始证据 其确定性一般由用户给出 对于用前面推理所得结论作为当前推理的证据 其确定性由推理得到 CER E 的取值范围为 0 1 即0 CER E 1 组合证据不确定性的算法 当组合证据是多个证据的合取时 即E E1ANDE2AND ANDEn则E的确定性CER E 为 CER E min CER El CER E2 CER En 当组合证据是多个证据的析取时 即E ElORE2OR OREn则E的确定性CER E 为CER E max CER El CER E2 CER En 不确定性的传递算法 对于知识 IFETHENH h1 h2 hn CF c1 c2 cn 结论H的确定性可通过下述步骤求出 1 求出H的概率分配函数 对上述知识 H的概率分配函数为 M hl h2 hn CER E c1 CER E c2 CER E cn M D 1 CER E cii l 如果有两条知识支持同一结论H 即IFE1THENH hl h2 hn CF c1 c2 cn IFE2THENH hl h2 hn CF c1 c2 cn 则首先分别对每一条知识求出概率分配函数 M1 hl h2 hn M2 hl h2 hn 然后再用公式M M1 M2对M1与M2求正交和 从而得到H的概率分配函数M 如果有n条知识都支持同一结论H 则用公式M M1 M2 Mn对M1 M2 Mn求其正交和 从而得到H的概率分配函数M 2 求出Bel H Pl H 及f H 其中 nBel H M hi i 1Pl H 1 Bel H f H Bel H Pl H Bel H Bel H M D H D H D 3 按如下公式求出H的确定性CER H CER H MD H E f H 其中MD H E 是知识的前提条件与相应证据E 的匹配度 定义为 这样 就对一条知识或者多条有相同结论的知识求出了结论的确定性 如果该结论不是最终结论 即它又要作为另一条知识的证据继续进行推理 则重复上述过程就可得到新的结论及其确定性 如此反复运用该过程 就可推出最终结论及它的确定性 MD H E 1如果H所要求的证据都已出现 0否则 举例 设有如下推理规则 rule1 ifE1andE2thenA a1 a2 CF 0 3 0 5 rule2 ifE3and E4orE5 thenN n1 CF 0 7 rule3 ifAthenH h1 h2 h3 CF 0 1 0 5 0 3 rule4 ifNthenH h1 h2 h3 CF 0 4 0 2 0 1 根据上述规则得到的推理网络如下图所示 给出的初始证据的确定性为 CER E1 0 8 CER E2 0 6 CER E3 0 9 CER E4 0 5 CER E5 0 7 现要求假设H的确定性 假设 20 推理网络图 H A N E1 E2 E3 E4 E5 H1 H2 H3 a1 a2 n1 and and or 求解步骤如下 1 求CER A 规则rule1条件部分的确定性为CER E CER E1ANDE2 min 0 8 0 6 0 6因此有m a1 a2 0 6 0 3 0 6 0 5 0 18 0 3 再根据m求Bel A Pl A 及CER A Bel A m a1 m a2 0 18 0 3 0 48Pl A Bel A m 1 0 18 0 3 0 52f A Bel A Pl A Bel A 0 48 2 20 0 52 0 532CER A MD A E f A 0 532 A 2 求CER N 规则rule2条件部分的确定性为CER E CER E3AND E4ORE5 0 7因此有m n1 0 7 0 7 0 49再根据m求Bel N Pl N f N 及CER N Bel N m n1 0 49Pl N Bel N m 1 0 49 0 51f N 0 49 1 20 0 51 0 515CER N MD N E f N 0 515 3 求CER H 根据rule3 可求得m1 h1 h2 h3 0 532 0 1 0 532 0 5 0 532 0 3 0 053 0 266 0 160 及m1 1 0 053 0 266 0 160 0 521根据rule4 可求得m2 h1 h2 h3 0 515 0 4 0 515 0 2 0 515 0 1 0 206 0 103 0 052 及m2 1 0 206 0 103 0 052 0 639求正交和m m1 m2 k m1 m2 m1 h1 m2 h2 m1 h1 m2 m1 m2 h1 m1 h2 m2 h2 m1 h1 m2 m1 m2 h2 m1 h3 m2 h3 m1 h3 m2 m1 m2 h3 0 874 m h1 1 k m1 h1 m2 h1 m1 h1 m2 m1 m2 h1 1 0 874 0 053 0 206 0 053 0 639 0 521 0 206 0 174同理得m h2 0 287 m h3 0 157m 1 m h1 m h2 m h3 1 0 174 0 287 0 157 0 382再根据m求Bel H Pl H f H 及CER H Bel H m h1 m h2 m h3 0 174 0 287 0 157 0 618Pl H Bel H m 1 0 618 0 382f H Bel H Pl H Bel H 0 618 3 20 0 382 0 675CER H MD H E f H 0 675 H 小结 证据理论有如下一些特点 证据理论满足比概率论更弱