人工智能之不确定知识表示及推理.ppt

07 04 2020 1 第一章不确定知识表示及推理 07 04 2020 2 内容1 1概述1 2概率模型1 3主观Bayes方法1 4可信度方法 07 04 2020 3 1 1概述 07 04 2020 4 所谓不确定性推理就是从不确定性的初始事实 证据 出发 通过运用不确定的知识 最终推出具有一定程度的不确定性却是合理或者近乎合理的结论的思维过程 需要解决的问题 不确定性的表示不确定性的匹配不确定性的更新算法 07 04 2020 5 证据的不确定性 一 不确定性的表示 证据通常有两类 一类为初始事实 这一类证据多来源于观察 因而通常具有不确定性 另一类为推理过程中产生的中间结果 证据不确定性用C E 表示 它代表相应证据的不确定性程度 即表示证据E为真的程度 如果E为初始事实 则C E 由用户给出 如果E为推理过程中产生的中间结果 则C E 可以通过不确定性的更新算法来计算 知识的不确定性 07 04 2020 6 规则 IFETHENH 规则是知识 E是规则的前提即证据 H是该规则的结论 也可以是其他规则的证据 规则的不确定性通常用一个数值f E H 表示 称为规则强度 规则的假设 结论 H也可以作为其他规则的证据 其不确定用C H 表示 C H 必须通过不确定性的更新算法来计算 07 04 2020 7 在确定一种量度方法及其范围时 应注意以下几点 量度要能充分表达相应的知识和证据的不确定性程度 量度范围的指定应便于领域专家及用户对不确定性的估计 量度要便于对不确定性的更新进行计算 而且对结论算出的不确定性量度不能超出量度的范围 量度的确定应当是直观的 同时应有相应的理论依据 07 04 2020 8 二 不确定性的匹配算法 设计一个数用来计算匹配双方相似的程度 另外再指定一个相似的限度 称为阈值 用来衡量匹配双方相似的程度是否落在指定的限度内 如果落在指定的限度内 就称它们是可匹配的 相应的知识可被应用 否则就称它们是不可匹配的 相应的知识不可应用 07 04 2020 9 三 不确定性的更新算法 即在推理过程中如何考虑知识不确定性的动态积累和传递 1 已知规则前提的不确定性C E 和规则的强度f E H 如何求假设H的不确定性C H 即定义算法g1 使C H g1 C E f E H 2 并行规则算法 定义算法g2 C H g2 C1 H C2 H 07 04 2020 10 3 证据合取的不确定性算法 C E1 E2 g3 C E1 C E2 C E1 E2 g4 C E1 C E2 4 证据析取的不确定性算法 合取和析取的不确定性算法统称为组合证据的不确定性算法 最大最小法 C E1 E2 min C E1 C E2 C E1 E2 max C E1 C E2 C E E2 C E1 C E2 C E E2 C E1 C E2 C E1 C E2 有界方法 概率方法 C E1 E2 max 0 C E1 C E2 1 C E1 E2 min 1 C E1 C E2 07 04 2020 11 设A1 A2 A3 A4为原始证据 不确定性分别为 C A1 C A2 C A3 C A4 求A5 A6 A7的不确定性 举例 A1 A2 OR A4 A3 AND A5 R1 f1 A6 R2 f2 A7 R3 f3 R4 f4 07 04 2020 12 由证据A1和A2的不确定性C A1 和C A2 由A1和A2析取的不确定性C A1 A2 和规则R1的规则强度f1 根据算法4求出A1和A2析取的不确定性C A1 A2 根据算法1求出A5的不确定性C A5 由证据A3和A4的不确定性C A3 和C A4 由A3和A4合取的不确定性C A3 A4 和规则R2的规则强度f2 根据算法3求出A3和A4合取的不确定性C A3 A4 根据算法1求出A6的不确定性C A6 07 04 2020 13 由A5的不确定性C A5 和规则R3的规则强度f3 由A6的不确定性C A6 和规则R4的规则强度f4 由A7的两个根据独立证据分别求出的不确定性C A7 和C A7 根据算法1求出A7的其中一个不确定性C A7 根据算法1求出A7的另外一个不确定性C A7 根据算法2求成A7最后的不确定性C A7 07 04 2020 14 1 2概率方法 07 04 2020 15 一 基础 1 全概率公式 P Ai 0 两两互不相容 即当i j时 有 设事件满足 D为必然事件 则对任何事件B有下式成立 提供了一种计算P B 的方法 07 04 2020 16 2 Bayes公式 定理 设事件满足上述定理的条件 则对任何事件B有 该定理称为Bayes定理 上式称为Bayes公式 07 04 2020 17 如果把全概率公式代入Bayes公式中 就可得到 即 07 04 2020 18 二 概率推理模型 Bayes方法用于不精确推理的条件是已知 P E P H P E H IFETHENH 若一组证据E1 E2 En同时支持假设H时 则 对于H E1 E2 En之间相互独立 对于一般的不精确推理网络 必须做如下约定 当一个证据E支持多个假设H1 H2 Hn时 则 假设H1 H2 Hn之间互不相容 07 04 2020 19 如果一个证据E支持多个假设H1 H2 Hn 即 IFETHENHi并已知P Hi 和P E Hi 则 如果有多个证据E1 E2 Em和多个结论H1 H2 Hn 则 07 04 2020 20 设已知 P H1 0 4 P H2 0 3 P H3 0 3P E1 H1 0 5 P E1 H2 0 6 P E1 H3 0 3P E2 H1 0 7 P E2 H2 0 9 P E2 H3 0 1 0 45 同理 求 P H1 E1E2 P H2 E1E2 P H3 E1E2 举例 07 04 2020 21 概率推理模型的优缺点 有较强的理论背景和良好的数学特征 当证据及结论都彼此独立时 计算的复杂度比较低 它要求给出结论Hi的先验概率P Hi 及证据Ej的条件概率P Ej Hi 要获得这些数据是一件相当困难的工作 Bayes公式的应用条件很严格 它要求各事件互相独立 若证据之间存在依赖关系 就不能直接使用这个方法 07 04 2020 22 1 3主观Bayes方法 07 04 2020 23 LS LN 0 分别称为充分性量度和必要性量度 这两个数值由领域专家给出 一 不确定性的表示 1 知识的不确定性表示 IFETHEN LS LN H P H 07 04 2020 24 O等价于概率函数P 定义如下 P越大则O越大 P和O在概率含义上等价的 但取值范围不同 当P 0 5时 O 1 P 0 1 O 0 当P 0 5时 O 1 当P 0 5时 O 1 当P 0时 O 0 几率函数O odds 07 04 2020 25 H的先验几率O H 和后验几率O H E 07 04 2020 26 同理可得 O H E LN O H O H E LS O H 07 04 2020 27 LS 规则的充分性量度 LS 1时 O H E O H 说明E对H没有影响 LS 1时 O H E O H 说明E支持H 且LS越大 E对H的支持越充分 可见 E的出现对H为真是充分的 故称LS为充分性度量 LS 1时 O H E O H 说明E排斥H 若LS为 则E为真时H就为真 若LS为0时 则E为真时H就为假 当证据E越是支持H为真是 则使相应LS的值越大 反映E出现对H的支持程度 07 04 2020 28 LN 规则的必要性量度 LN 1时 O H E O H 说明 E对H没有影响 LN 1时 O H E O H 说明 E支持H 且LN越大 E对H的支持越充分 当LN 1时 O H E O H 说明 E排斥H 若LN为 则 E为真时H就为真 若LN为0时 则 E为真时H就为假 由于E不出现 将导致H为假 可看出E对H为真的必要性 故称LN为必要性度量 若证据E对H越是必要 则相应的LN的值越小 反映E不出现对H的支持程度 即E的出现对H的必要性 07 04 2020 29 LS和LN的关系 LS 1且LN 1 LS1 LS LN 1 由于E和 E不可能同时支持H或同时反对H 所以领域专家在为一条知识中的LS和LN赋值时 不应该同时大于1或同时小于1 07 04 2020 30 2 证据的不确定性表示 在主观Bayes方法中 证据E的不确定性由用户根据观察S给出后验概率P E S 或后验几率O E S 表示 当E为真时 P E S 1 O E S 当E为假时 P E S 0 O E S 0 当E不确定时 0 P E S 1 07 04 2020 31 二 主观Bayes方法推理的基本算法 根据证据E的后验概率P E S 及LS LN的值 把H的先验概率P H 更新为后验概率P H E 或P H E 即 07 04 2020 32 当P E S 1 1 证据E确定 则 O H E LS O H 07 04 2020 33 当P E S 1 则 O H E LN O H 同理可得 07 04 2020 34 在证据不确定的情况下 不能再用上面的公式计算后验概率 而要用杜达 R O DUDA 等人于1976年证明了的如下公式 2 证据E不确定 当P E S 1时 P E S 0P H S P H E 当P E S 0时 P E S 1P H S P H E 当P E S P E 时 P H S P H E P E P H E P E P H 当P E S 为其它值时 通过分段线性插值可得计算P H S 的公式 如图所示 P H S P H E P E S P H E P E S 此即为证据确实存在的情况 此即为证据确实不存在的情况 07 04 2020 35 07 04 2020 36 函数的解析式 即EH公式 P H E P H E P H 根据专家给出的参数可计算出来 EH公式中 有两组参数需要确认 P E S 由用户根据观察S给出P E S 相当困难 所以引入可信度的概念 采用 5 5这11个整数作为证据的可信度 用户根据实际情况选择 07 04 2020 37 C E S 5 表示在观察S之下证据E肯定存在 即P E S 1 可信度C E S 和概率P E S 的对应关系 C E S 5 表示在观察S之下证据E肯定不存在 即P E S 0 C E S 0 表示S与E无关系 即P E S P E C E S 为其他数时与P E S 的对应关系 可通过对上述3点进行分段线性插值得到 如图所示 07 04 2020 38 07 04 2020 39 C E S 与P E S 的关系式 CP公式 07 04 2020 40 当用初始证据进行推理时 通过提问用户得到C E S 通过运用CP公式就可求出P H S 当用推理过程中得到的中间结论作为证据进行推理时 通过运用EH公式就可求得P H S 具体思路 07 04 2020 41 3 证据E为若干证据的组合 独立证据导出同一假设 当有n个证据Ei i 1 2 n 对假设H都有某种程度的影响时 即存在规则 E1 H E2 H En H Ei之间相互独立 且对每个Ei都有相应的观察Si与之对应 求在所有观测之下的后验概率 P H S1 S2 Sn 07 04 2020 42 合成法 O H S1 S2 Sn 只要对每条规则分别求出O H Si 则这些独立证据的组合所得到的H的后验几率 07 04 2020 43 结论更新算法 先利用第一条规则对结论的先验概率进行更新 再把得到的后验概率当作第二条规则的先验概率 再用第二条知识对其进行更新 把更新后的值作为第三条知识的先验概率 继续更新到所有的规则都使用完 07 04 2020 44 证据的合取 E E1 E2 En 如果在观察S下 其概率为 P E1 S P E2 S P En S 则 P E S min P E1 S P E2 S P En S 07 04 2020 45 证据的析取 E E1 E2 En 如果在观察S下 证据其概率为 P E1 S P E2 S P En S 则 P E S max P E1 S P E2 S P En S 07 04 2020 46 设有如下知识 三 主观Bayes方法应用举例 已知 结论B的先验概率P B 0 03 当证据A1 A2 A3 A4必然发生后 求结论B的概率变化 R1 IFA1THEN 20 1 B R2 IFA2THEN 300 1 B R3 IFA3THEN 75 1 B R4 IFA4THEN 4 1 B 07 04 2020 47 解法1 利用合成算法 07 04 2020 48 依据规则R1 依据规则R2 依据规则R3 07 04 2020 49 依据规则R4 07 04 2020 50 解法2 利用更新算法 07 04 2020 51 R1 IFE1THEN 2 0 001 H1 设有如下规则 R3 IFH1THEN 65 0 01 H2 R2 IFE2THEN 100 0 001 H1 R4 IFE3THEN 300 0 01 H2 且已知先验几率 O H1 0 1 O H2 0 01 通过提问用户得到 C E1 S1 3 C E2 S2 1 C E3 S3 2 求 O H2 S1S2S3 举例 07 04 2020 52 20 001 1000 001 650 01 3000 01 C E1 S1 3 C E2 S2 1 C E3 S3 2 07 04 2020 53 求O H1 S1 因为C E1 S1 3 0 所以使用CP公式的后一部分 07 04 2020 54 求O H1 S2 因为C E2 S2 1 0 所以使用CP公式的后一部分 07 04 2020 55 求O H1 S1S2 07 04 2020 56 求O H2 S1S2 为了确定应用EH公式的哪一部分 需要判断P H1 S1S2 与P H1 的关系 P H1 S1S2 P H1 必须用EH公式的后半部分 07 04 2020 57 07 04 2020 58 求O H2 S3 因为C E3 S3 2 0 所以使用CP公式的前一部分 07 04 2020 59 求O H2 S1S2S3 可以看出 H2先验的几率为0 01 经过推理后 算出其后验几率为0 081 相当于几率增加了8倍 07 04 2020 60 四 主观Bayes方法的主要优缺点 优点 主观Bayes方法中的计算公式大多是在概率论的基础上推导出来的 具有较坚实的理论基础 规则的LS和LN由领域专家根据实践经验给出的 这就避免了大量的数据统计工作 另外 它既用LS指出了证据E对结论H的支持程度 又用LN指出了E对H的必要性程度 这就比较全面地反映了证据与结论间的因果关系 符合现实世界中某些领域的实际情况 使推出的结论具有较准确的确定性 07 04 2020 61 它的主要缺点有 要求领域专家在给出规则的同时 给出H的先验概率P H 这是比较困难的 Bayes定理中关于事件间独立性的要求使主观Bayes方法的应用受到了限制 由其推理过程可以看出 它确实实现了不确定性的逐级传递 因此可以说主观Bayes方法是一种比较全面实用且灵活的不确定性推理方法 主观Bayes方法不仅给出了在证据确定的情况下由H的先验概率更新为后验概率的方法 而且给出了在证据不确定情况下更新先验概率为后验概率的方法 07 04 2020 62 练习 1 设有如下知识 R1 IFE1THEN 1 0 003 H1 0 4 R2 IFE2THEN 18 1 H2 0 06 R3 IFE3THEN 12 1 H3 0 04 求 当证据E1 E2 E3出现及不出现时 P Hi Ei 及P Hi Ei 的值各是多少 2 设有如下知识 R1 IFATHEN 20 1 B1 0 03 R2 IFB1THEN 300 0 0001 B2 0 01 当证据A必然发生时 求P B2 A 07 04 2020 63 3 设有如下知识 R1 IFE1THEN 20 1 H 0 03 R2 IFE2THEN 300 1 H 0 03 若证据E1和E2依次出现 按主观Bayes推理 求H在此条件下的概率P H E1E2 按两种方法求 07 04 2020 64 1 4可信度方法 07 04 2020 65 一 基于可信度的不确定的表示 根据经验对一个事物或现象为真的相信程度称为可信度 知识用产生式规则表示 每一条规则都有一个可信度 每个证据也具有一个可信度 07 04 2020 66 1 知识不确定性的表示 IFETHENH CF H E CF H E 是该规则的可信度 称为可信度因子或规则强度 CF H E 1 1 表示在已知证据E的情况下对假设H为真的支持程度 CF H E 0 表示证据的存在增加结论为真的程度 CF H E 的值越大结论H越真 CF H E 1 表示证据存在结论为真 CF H E 0 表示证据的存在增加结论为假的程度 CF H E 的值越小结论H越假 CF H E 1 表示证据存在结论为假 CF H E 0 表示证据E和结论H没有关系 07 04 2020 67 如果P H E 1 CF H E 1 如果P H E 0 CF H E 1 如果P H E P H CF H E 0 可信度的性质 07 04 2020 68 对同一个证据E 若有n个互不相容的假设Hi i 1 2 n 则 如果发现专家给出的可信度出现CF H1 E 0 6 CF H2 E 0 7 而H1和H2互不相容 说明规则的可信度是不合理的 应调整 07 04 2020 69 可信度CF和概率P有一定的对应关系 但又有区别 P H E P H E 1 CF H E CF H E 0 表明 一个证据对某个假设的成立有利 必然对该假设的不成立不利 而且对两者的影响程度相同 07 04 2020 70 根据定义式 由先验概率P H 和后验概率P H E 可求CF H E 但是实际应用中 P H 和P H E 的值是难以获得的 因此CF H E 的值要求由领域专家直接给出 其原则是 若由于证据的出现增加结论H为真的可信度 则使 CF H E 0 证据的出现越是支持H为真 就使CF H E 的值越大 反之 使 CF H E 0 证据的出现越是支持H为假 就使CF H E 的值越小 若证据的出现与H无关 使 CF H E 0 可信度的确定 07 04 2020 71 2 证据的不确定性的表示 证据E的不确定性用证据的可信度CF E 表示 原始证据的可信度由用户在系统运行时提供 中间结果的可信度由不精确推理算法得到 证据E的可信度取值范围为 1 CF E 1 当证据以某种程度为真时 CF E 0 当证据肯定为真时 CF E 1 当证据以某种程度为假时 CF E 0 当证据肯定为假时 CF E 1 当证据一无所知时 CF E 0 07 04 2020 72 证据的合取E E1 E2 EnCF E min CF E1 CF E2 CF En 二 可信度方法推理的基本算法 1 组合证据的不确定性算法 证据的析取E E1 E2 EnCF E max CF E1 CF E2 CF En 07 04 2020 73 2 不确定性的传递算法 不确定性的传递算法就是根据证据和规则的可信度求结论的可信度 已知规则如下 IFETHENH CF H E 并已知证据E的可信度为CF E 则结论H的可信度CF H 为 CF H CF H E max 0 CF E 若CF E 0 即证据以某种程度为真 则CF H CF H E CF E 若CF E 1 即证据为真时 则CF H CF H E 若CF E 0 即证据以某种程度为假 则CF H 0 在可信度方法的不精确推理中 并没有考虑证据为假时对结论H所产生的影响 07 04 2020 74 IFE1THENH CF H E1 IFE2THENH CF H E2 3 多个独立证据推出同一假设的合成算法 先分别求两条规则得出的结论的可信度 CF1 H CF H E1 max 0 CF E1 CF2 H CF H E2 max 0 CF E2 利用下式求出E1和E2对H的综合影响所形成的CF1 2 H CF1 H 0 CF2 H 0 CF1 2 H CF1 H CF2 H CF1 H CF2 H CF1 H 0 CF2 H 0 CF1 2 H CF1 H CF2 H CF1 H CF2 H CF1 H 和CF2 H 异号 CF1 2 H CF1 H CF2 H 07 04 2020 75 在MYCIN系统的基础上形成的专家系统工具EMYCIN 将其修改为 在组合两个以上的独立证据时 可先组合其中两个 再将结果与第三个证据组合 如此下去 直到组合完毕为止 当CF1 H 0 CF2 H 0时 CF1 2 H CF1 H CF2 H CF1 H CF2 H 当CF1 H 0 CF2 H 0 CF1 2 H CF1 H CF2 H CF1 H CF2 H 当CF1 H 和CF2 H 异号时 07 04 2020 76 即 已知规则IFETHENHCF H E 及CF H 求CF H E 4 在已知结论原始可信度的情况下 结论可信度的更新计算方法 这时分三种情况进行讨论 07 04 2020 77 CF H 0 CF H E 0 CF H E CF H CF H E CF H E CF H CF H 0 CF H E 0 CF H E CF H CF H E CF H E CF H CF H 和CF H E 异号 当CF E 1时 即证据肯定出现时 07 04 2020 78 CF H 0 CF H E 0 CF H E CF H CF H E CF E CF H CF H E CF E CF H 0 CF H E 0 CF H E CF H CF H E CF E CF H CF H E CF E CF H 和CF H E 异号 当0 CF E 1时 07 04 2020 79 当CF E 0时 在MYCIN系统中就规定 当CF E 0 2时 规则IFETHENH不可使用 结论可信度的合成算法和更新算法本质上是一致的 但对不同前提条件 使用不同的方法 解题的效果或难易程度不同 有些题目使用合成法求解就比较容易 而有些题目就需要使用更新法 规则不可使用 对结论H的可信度无影响 07 04 2020 80 R1 IFA1THENB1CF B1 A1 0 8R2 IFA2THENB1CF B1 A2 0 5R3 IFB1 A3THENB2CF B2 B1 A3 0 8并且已知 CF A1 CF A2 CF A3 1而对B1 B2一无所知 求CF B1 和CF B2 三 可信度方法应用举例 1 多条知识下 合成法求结论可信度举例 举例1 07 04 2020 81 解 由于对B1 B2的初始可信度一无所知 使用合成算法计算 对知识R1和R2 分别计算CF B1 CF1 B1 CF B1 A1 max 0 CF A1 0 8 1 0 8CF2 B1 CF B1 A2 max 0 CF A2 0 5 1 0 5 利用合成算法计算B1的综合可信度 CF1 2 B1 CF1 B1 CF2 B1 CF1 B1 CF2 B1 0 8 0 5 0 8 0 5 0 9 计算B2的可信度CF B2 CF B2 CF B2 B1 A3 max 0 CF B1 A3 0 8 max 0 min CF B1 CF A3 0 8 max 0 min 0 9 1 0 8 max 0 0 9 0 8 0 9 0 72 07 04 2020 82 R1 IFE1THENHCF H E1 0 8R2 IFE2THENHCF H E2 0 6R3 IFE3THENHCF H E3 0 5R4 IFE4 E5 E6 THENE1CF E1 E4 E5 E6 0 7R5 IFE7 E8THENE3CF E3 E7 E8 0 9在系统运行中已从用户处得 CF E2 0 8 CF E4 0 5 CF E5 0 6 CF E6 0 7 CF E7 0 6 CF E8 0 9求 CF H 举例2 07 04 2020 83 解 由已知知识建立推理网络如图 07 04 2020 84 由R4 CF E1 CF E1 E4 E5 E6 max 0 CF E4 E5 E6 0 7 max 0 min CF E4 CF E5 E6 0 7 max 0 min CF E4 max CF E5 CF E6 0 7 max 0 min CF E4 max 0 6 0 7 0 7 max 0 min CF E4 0 7 0 7 max 0 min 0 5 0 7 0 7 max 0 0 5 0 7 0 5 0 35 由R5 CF E3 CF E3 E7 E8 max 0 CF E7 E8 0 9 max 0 min CF E7 CF E8 0 9 max 0 min 0 6 0 9 0 9 max 0 0 6 0 9 0 6 0 54 07 04 2020 85 由R1 将R1和R2两条知识合成 CF1 2 H CF1 H CF2 H CF1 H CF2 H 0 28 0 48 0 28 0 48 0 6256 CF1 H CF H E1 max 0 CF E1 0 8 max 0 0 35 0 8 0 35 0 28 由R2 CF2 H CF H E2 max 0 CF E2 0 6 max 0 0 8 0 6 0 8 0 48 由R3 CF3 H CF H E3 max 0 CF E3 0 5 max 0 0 54 0 5 0 54 0 27 07 04 2020 86 将CF1 2 H 和CF3 H 合成 07 04 2020 87 规则可信度为 2 多条知识下 更新法求结论可信度举例 证据可信度为 CF A CF B CF C CF D 0 5 X Y的初始可信度为 CF0 X