人工智能chapter8uncertainty.ppt

第八章不确定知识与推理 概述非精确性推理不确定性人工智能的数学基础贝叶斯网络 8 1概述 知识的不确定性 随机性模糊性自然语言中的不确定性常识知识的不确定性知识的其他不确定性 随机性以牛顿理论为代表的确定性科学 创造了给世界以精确描绘的方法 将整个宇宙看作是钟表式的动力学系统 处于确定 和谐 有序的运动之中 客观世界上随机的 映射到人脑的客观世界 即主观世界也应该是随机的 因此 人类在认知过程中表现出的智能和知识 不可避免地伴随有随机性 随机性无处不在 随机性使得世界更为复杂 也更为丰富多彩 8 1概述 模糊性直到20世纪 人们才认识到 模糊性并不是坏事 它能够用较少的代价 传递足够的信息 并能对复杂事物做出高效率的判断和处理 模糊性的客观性哲学家罗素早在1923年一篇题为Vagueness的论文中明确指出 认为模糊知识必定是靠不住的 这种看法是大错特错的 随着科学技术的发展 科学家们已经认识到 硬要把模糊事物人为地精确化 不仅会以方法的复杂性为代价 而且会降低结果的意义性 8 1概述 自然语言中的不确定性语言带有不确定性是很自然的 是人类思维的本质特征之一 计算机自然语言理解 机器翻译等研究 从20世纪40年代兴起至今已经有60多年的历史 人们寄希望于表示概念的语言值的不确定性研究取得突破 8 1概述 常识知识的不确定性在人工智能界 常识知识的表示 处理和验证是非常困难的 常识知识的相对性目前 人工智能界有这样的共识 有无常识是人和机器的根本区别之一 8 1概述 知识的其他不确定性知识的不完备性知识的不协调性知识的非恒常性 8 1概述 不确定性知识的表示 处理和模拟 寻找并且形式化地表示不确定性知识中的规律性 让机器模拟人类知识客观世界和人类自身的认知过程 使机器具有不确定性智能 成为人工智能学家的重要任务 8 1概述 8 2非精确性推理 非精确性推理方法研究产生的原因大致如下 很多原因导致同一结果 推理所需的信息不完备 背景知识不足 信息描述模糊 信息中含有噪声 划分是模糊的 推理能力不足 解题方案不唯一 ES是通过大量专家知识来取得高水平的问题求解能力 由于专家知识是不确定的 因此ES要达到高性能 必须解决好不确定性问题 传统的概率统计方法受限制放弃传统程序求解的逻辑完备性 8 2非精确性推理 Shortliffe等人1975年结合MYCIN系统的建立提出了确定性理论 DURA等人1976在PROSPECTOR的基础上给出了概率法 DempsterShafter同年提出证据理论 Zadeh两年后提出了可能性理论 1983年提出了模糊逻辑 8 2非精确性推理 非确定性推理的研究和发展 MYCIN系统是第一个采用了不确定推理逻辑的专家系统 在20世纪70年代非常有名 这个系统提出该确定性方法时遵循了下面的原则 1 不采用严格的统计理论 使用的是一种接近统计理论的近似方法 2 用专家的经验估计代替统计数据 3 尽量减少需要专家提供的经验数据 尽量使少量数据包含多种信息 4 新方法应适用于证据为增量式地增加的情况 5 专家数据的轻微扰动不影响最终的推理结论 确定性理论 MYCIN概述 用户 解释模块 咨询模块 知识获取模块 感染病专家与知识工程师 知识库 动态数据库 推理记录 患者数据库 原始数据库 MYCIN系统结构图 MYCIN推理策略 采用反向推理和深度优先搜索 诊断治疗过程如下 1 确定患者有无细菌性感染 2 确定可能引起感染的有机体 3 确定对其有抑制作用的药物 4 选择对治疗最合适的药物 这四个步骤由目标规则来执行 MYCIN知识表示 如 RULE037 PREMISE AND NOTKNOWNCONTXTIDENT SAMECONTXTGRAMGRAMNEG SAMECONTXTMORPHROD SAMECONTXTAIRAEROBIC ACTION CONCLUDECONTXTCLASSENTEROBACTERIACEAETALLY0 8 可信度是指人们根据以往经验对某个事物或现象为真的程度的一个判断 或者说是人们对某个事物或现象为真的相信程度 可信度的概念 可信度具有一定的主观性 较难把握 但对某一特定领域 让该领域专家给出可信度还是可行的 8 3 2CF模型 表示形式 在C F模型中 知识是用产生式规则表示的 其一般形式为 IFETHENH CF H E 其中 E是知识的前提条件 H是知识的结论 CF H E 是知识的可信度 1 知识不确定性的表示 例子 IF发烧AND流鼻涕THEN感冒 0 8 说明 当某人确实有 发烧 及 流鼻涕 症状时 则有80 的把握是患了感冒 说明 1 E可以是单一条件 也可以是复合条件 例如 E E1ORE2 ANDE3ANDE4 2 H可以是单一结论 也可以是多个结论 3 CF是知识的静态强度 CF H E 的取值为 1 1 表示当E为真时 证据对H的支持程度 其值越大 支持程度越大 4 CF H E 可以理解为规则的可信度 可信度的定义在CF模型中 把CF H E 定义为CF H E MB H E MD H E 2 可信度的定义与性质 MB 信任增长度 MB H E 定义为 MD 不信任增长度 MB H E 定义为 MB和MD的关系 当MB H E 0时 P H E P H E的出现增加了H的概率当MD H E 0时 P H E P H E的出现降低了H的概率 CF H E MB H E MD H E 可信度的性质 互斥性对同一证据 它不可能既增加对H的信任程度 又同时增加对H的不信任程度 这说明MB与MD是互斥的 即有如下互斥性 当MB H E 0时 MD H E 0当MD H E 0时 MB H E 0 值域 典型值 1 当CF H E 1时 有P H E 1 它说明由于E所对应证据的出现使H为真 此时 MB H E 1 MD H E 0 2 当CF H E 1时 有P H E 0 说明由于E所对应证据的出现使H为假 此时 MB H E 0 MD H E 1 3 当CF H E 0时 有MB H E 0 MD H E 0 前者说明E所对应证据的出现不证实H 后者说明E所对应证据的出现不否认H 4 对H的信任增长度等于对非H的不信任增长度 对H的信任增长度等于对非H的不信任增长度对H的可信度与非H的可信度之和等于0可信度不是概率概率满足 P H P H 1和0 P H P H 1但可信度不满足 5 对同一前提E 若支持若干个不同的结论Hi i 1 2 n 则 若 专家给出的知识有如下情况CF H1 E 0 7 CF H2 E 0 4 非法 应进行调整或规范化 证据 E 不确定性的表示 证据的不确定性也是用可信度来表示的 其取值范围也为 1 1 若E为初始证据 其值由用户给出 若E为中间结论 其值可通过计算得到 不确定性的含义 对E 其可信度CF E 的含义如下 CF E 1 证据E肯定它为真CF E 1 证据E肯定它为假CF E 0 对证据E一无所知0 CF E 1 证据E以CF E 程度为真 1 CF E 0 证据E以CF E 程度为假 3 证据不确定性的表示 4 否定证据不确定性的计算CF E CF E 5 组合证据不确定性的计算 合取 与 析取 两种基本情况 析取 当组合证据是多个单一证据的析取时即E E1ORE2OR OREn时 若已知CF E1 CF E2 CF En 则CF E max CF E1 CF E2 CF En 合取 当组合证据是多个单一证据的组合时即E E1ANDE2AND ANDEn时 若已知CF E1 CF E2 CF En 则CF E min CF E1 CF E2 CF En CF模型中的不确定性推理实际上是从不确定的初始证据出发 不断运用相关的不确性知识 逐步推出最终结论和该结论可信度的过程 每一次运用不确定性知识 都需要由证据的不确定性和知识的不确定性去计算结论的不确定性 6 不确定性推理 不确定性的更新公式 CF H CF H E max 0 CF E 若CF E 0 若CF E 1 CF H 0即该模型没考虑E为假对H的影响 CF H CF H E 即规则强度CF H E 实际上是在E为真时 H的可信度 当有多条知识支持同一个结论 且这些知识的前提相互独立 结论的可信度又不相同时 可利用不确定性的合成算法求出结论的综合可信度 设有知识 IFE1THENH CF H E1 IFE2THENH CF H E2 则结论H的综合可信度可分以下两步计算 1 分别对每条知识求出其CF H 即CF1 H CF H E1 max 0 CF E1 CF2 H CF H E2 max 0 CF E2 2 用如下公式求E1与E2对H的综合可信度 7 结论不确定性的合成 设有如下一组知识 r1 IFE1THENH 0 9 r2 IFE2THENH 0 6 r3 IFE3THENH 0 5 r4 IFE4AND E5ORE6 THENE1 0 8 已知 CF E2 0 8 CF E3 0 6 CF E4 0 5 CF E5 0 6 CF E6 0 8求 CF H 解 由r4得到 CF E1 0 8 max 0 CF E4AND E5ORE6 0 8 max 0 min CF E4 CF E5ORE6 0 8 max 0 min CF E4 max CF E5 CF E6 0 8 max 0 min CF E4 max 0 6 0 8 0 8 max 0 min 0 5 0 8 0 8 max 0 0 5 0 4 例子 由r1得到 CF1 H CF H E1 max 0 CF E1 0 9 max 0 0 4 0 36由r2得到 CF2 H CF H E2 max 0 CF E2 0 6 max 0 0 8 0 48由r3得到 CF3 H CF H E3 max 0 CF E3 0 5 max 0 0 6 0 3根据结论不精确性的合成算法 CF1 H 和CF2 H 同号 有 CF12 H 和CF3 H 异号 有 即综合可信度为CF H 0 53 不精确推理过程可以总结如下 每条规则RULE和每项事实FACT各自都有一个确定的可信度 数值在 1 1 闭区间内 给了事实FACT的可信度F 按照规则RULE的可信度R 即可以如下地自下而上 从树叶到树根 前一层的C是后一层的F 计算出各层推断出结论CONCLUSION的可信度CF 自下而上算 MYCIN不精确推理 与 节点处的结论可信度C 推断规则的可信度R 输入分支中的min可信度F或C 或 节点处的结论可信度C 规则可信度R1 与 输入分支1的可信度C1 之乘积C1R1 规则可信度R2 与 输入分支2的可信度C2 之乘积C2R2 C1R1 C2R2 在推理过程中 一般还规定有一个统一的阈值 比方MYCIN系统是0 2 凡遇可信度 阈值时 即置成0 0 表示谈不上可信不可信 所以在推理链上 凡遇C 0 2者 置成C 0 C1 min 0 8 C2 0 8 0 24 R9 1 0 C7 C6 C3 C4 C5 C2 R8 0 5 R5 0 75 R10 1 0 R6 1 0 R7 0 5 R4 0 8 F5 0 9 R3 0 9 R1 0 8 R2 0 75 F6 1 0 F8 0 5 F1 0 8 F7 0 5 F4 0 9 F3 0 9 F2 0 4 例 其中 C2 0 4 0 75 0 3 C3 0 9 0 8 0 72C4 1 0 0 75 0 75 1 0 1 0 0 75 0 7 1 0 0 93 C5 0 8 0 5 0 4 C6 min 0 5 0 4 0 5 0 2 0 C7 0 5 1 0 0 5 1 0 0 5 1 0 1 0 0 5 0 75 推理链上的可信度计算过程 8 3 不确定性人工智能的数学基础 人工智能是在数学的基础上发展起来的为了解决人工智能中的各种不确定性问题 同样需要数学的支持 概率理论模糊集理论核函数和主曲线粗糙集理论 8 3 1概率理论 概率理论是处理随机性最好的数学工具 17世纪人们对赌博中随机现象的研究 20世纪概率论的公理化体系 数理统计 随机过程的研究 奠基人 JacobBernoulliP S Laplace J W LindebergP L Chebyshev A A Markov A N Kolmogorov K Pearson 生物统计进行研究R Fisher 模型的参数估计方法以及试验设计方法R Brown 布朗运动 随机过程A K Erlang Poisson过程 由概率论 数理统计和随机过程构成的概率理论 为研究随机性奠定了数学基础 也为研究不确定性提供了工具 8 3 1 1贝叶斯定理 随机事件的关系及逻辑运算集合表示随机事件事件A不出现 事件A包含于时间B 事件A B至少出现一个 事件A B同时出现 事件间的运算满足交换律 结合律 分配律 对偶律 确定事件A的概率P A 通常有三种计算方法 古典概率 P A k m 其中 k为A中所包含的基本事件数 n为基本事件的总数 频率法 P A m n 其中 n为重复实验次数 n为事件A出现的次数 主观确定法 P A 专家主观赋值 通常用于不宜大量重复的随机现象 条件概率及贝叶斯定理 定义1 随机事件的独立性 设 F P 是一概率空间 A B是F中的任意两个随机事件 如果P A B P A P B 则称A B是相互独立的 一个事件的发生对另一事件的发生没有任何影响 事件才具有独立性 定义2 设 F P 是一概率空间 A B是F中的任意两个随机事件 假设P B 0 称为事件B出现条件下 事件A发生的条件概率 条件概率及贝叶斯定理 条件概率的意义在于 如果在随机试验中 已经观察到了事件B的发生 那么可以利用事件B发生的概率 去认识事件A的不确定性 贝叶斯定理 Bayes 设事件A1 A2 A3 An中任意两个事件都不相交 则对任何事件B有下式成立 该定理就叫Bayes定理 上式称为Bayes公式 条件概率及贝叶斯定理 贝叶斯定理 设Ai是导致事件B发生的所有可能原因 已知他们的概率为P Ai 这些概率被称为先验概率 设Ai在随机试验中不能或者没有被直接观察到 只能观察到与之联系的B的发生 在此条件下 对事件Ai出现的可能性作出判断 即求出关于B的条件概率P Ai B 又称为Ai的后验概率 例如 用B代表发烧 A代表感冒 P A B P B A 贝叶斯公式给出用先验概率P B A 求后验概率P A B 的方法 例子 已知 s表示病人脖子强直 m表示病人患有脑膜炎p s m 0 5 p m 1 50000 p s 1 20 p m s p m s p s m p m p s 0 0002 8 3 2粗糙集理论 RoughSet 1965年 L A Zadeh提出FuzzySets的概念 试图通过这一理论解决G frege的含糊概念 FS方法 利用隶属函数描述边界上的不确定对象 1982年 波兰华沙理工大学Z Pawlak教授针对G frege的边界线区域思想提出了RoughSets理论 RS方法 把无法确认的个体都归属于边界区域 把边界区域定义为上近似集和下近似集的差集 Roughsettheoryisstillanotherapproachtovagueness Similarlytofuzzysettheoryitisnotanalternativetoclassicalsettheorybutitisembeddedinit RoughsettheorycanbeviewedasaspecificimplementationofFrege sideaofvagueness i e imprecisioninthisapproachisexpressedbyaboundaryregionofaset andnotbyapartialmembership likeinfuzzysettheory Roughsetconceptcanbedefinedbyapproximations 1982Z Pawlak波兰 1问题 医生 症状头痛 肌肉痛 体温 患病 流感 条件属性 决策属性 条件属性 决策属性 是 不可分辨关系 RS理论是基于不可分辨关系的 等价关系 1问题 医生 症状头痛 肌肉痛 体温 患病 流感 表达条件属性等价类和决策属性等价类的关系 其中存在vague 在条件属性下的等价类 在决策属性下的等价类 b1 p1 p2 p3 b2 p5 b3 p4 p6 b4 p7 X p1 p4 p5 Y p2 p3 p6 p7 条件属性下 决策属性下 决策属性 是 X p1 p4 p5 上近似b1Ub2Ub3 下近似b1 边界域b2Ub3 直观理解 对于上近似集外的元素 一定不属于X 对于边界域内的元素 可能属于X 也可能不属于X 对于下近似内的元素 一定属于X RoughSet的能力 属性约简 属性的重要度 规则生成 8 4贝叶斯网络 根据概率理论的法则建立网络模型 对不确定性进行推理 贝叶斯网络是一系列变量的联合概率分布的图形表示 8 4 1贝叶斯网络的表示 包含两个部分 贝叶斯网络结构图 有向无环图 DAG 其中图中的每个节点代表相应的变量 节点之间的连接关系代表了贝叶斯网络的条件独立语义 节点和节点之间的条件概率表 CPT 一系列的概率值 命题S moker 吸烟者命题C oalMiner 煤矿矿井工人命题L ungCancer 他患了肺癌命题E mphysema 他患了肺气肿 贝叶斯网有时也叫因果网 因为可以将连接结点的弧认为是表达了直接的因果关系 如果一个贝叶斯网络提供了足够的条件概率值 足以计算任何给定的联合概率 我们就称 它是可计算的 即可推理的 贝叶斯网的两个要素 其一为贝叶斯网的结构 也就是各节点的继承关系 其二就是条件概率表CPT 若一个贝叶斯网可计算 则这两个条件缺一不可 贝叶斯网络 例 给定了他们是否给你打电话的证据 估计有人入室行窃的概率 7 4 2贝叶斯网络的语义 贝叶斯网络能表示任意概率分布的同时 它们为这些能用简单结构表示的分布提供了可计算优势 假设对于顶点xi 其双亲节点集为Pai 每个变量xi的条件概率P xi Pai 则顶点集合X x1 x2 xn 的联合概率分布可如下计算 贝叶斯网络的联合概率分布 Burglary Earthquake P B 0 001 JohnCalls Alarm P E 0 002 MaryCalls BEP A tt 95 tf 90 ft 30 ff 001 AP J t 90 f 05 AP M t 70 f 01 计算报警器响了 但既没有盗贼闯入 也没有发生地震 同时John和Mary都给你打电话的概率 P j m a b e P j a P m a P a b e P b P e 0 90 0 70 0 001 0 999 0 998 0 00062 贝叶斯网络的联合概率分布 该等式暗示了早先给定的图结构有条件独立语义 它说明贝叶斯网络所表示的联合分布作为一些单独的局部交互作用模型的结果具有因式分解的表示形式 7 4 3贝叶斯网的推理模式 因果推理 由上向下推理 诊断推理辩解 在确定某个已观察事件 也就是一组证据变量值的某个赋值后 任何概率推理系统的基本任务都是要计算一组查询变量的后验概率 因果推理 由上向下推理 7 4 3贝叶斯网络的推理模式 给定患者是一个吸烟者 S 计算他患肺气肿 E 的概率P E S S 推理的证据 E 询问结点 P E S P E C S P E C S 全概率公式 P E C S P C S P E C S P C S 贝叶斯公式在图中 C和S并没有双亲关系 符合条件独立条件 P C S P C P C S P C 由此可得 P E S P E S C P C P E C S P C P E C S P E C S P S P E C S P C S P S 贝叶斯定理 P E C S P C S 反向利用贝叶斯定理 因