人工智能原理与方法.ppt

2020 4 15 WeiChanghua 1 主讲人 人工智能原理与方法ArtificialIntelligence 2020 4 15 WeiChanghua 2 内容 第一章绪论 什么是人工智能 人工智能研究的目标 人工智能研究途径 人工智能研究的内容 人工智能研究中的学派 人工智能研究的内容 人工智能研究领域 2020 4 15 WeiChanghua 3 内容 第二章人工智能的数学基础 命题逻辑和谓词逻辑 概率论 模糊理论 2020 4 15 WeiChanghua 4 内容 第三章知识表示 知识与知识表示 对知识表示的要求 知识表示方法 一阶谓词逻辑 产生式规则 语义网络 框架 状态空间 脚本 Petri网 2020 4 15 WeiChanghua 5 内容 第四章基本的问题求解方法 基本概念 状态空间搜索 与 或树搜索 博弈树的启发式搜索 2020 4 15 WeiChanghua 6 内容 第五章基本推理方法 推理的基本概念 推理方式和分类 推理控制策略 归结反演 基于规则的演绎系统 2020 4 15 WeiChanghua 7 内容 第六章不确定性推理 不确定性推理的基本概念 确定因子法 主观Bayes方法 证据理论 可能性理论 2020 4 15 WeiChanghua 8 内容 第七章专家系统 专家系统的基本概念 专家系统分类 专家系统的一般结构 专家系统的建造与评价 专家系统开发工具 专家系统开发环境 新一代专家系统的研究 几个著名的专家系统 2020 4 15 WeiChanghua 9 内容 第八章机器学习 机器学习的概念 学习系统模型 机器学习分类 机器学习研究历史 机器学习的研究目标 几个著名的学习系统 2020 4 15 WeiChanghua 10 第一章绪论 1什么是人工智能 人工智能是研究知识的一门科学 即如何表示知识 如何获取知识和如何利用知识的科学 2020 4 15 WeiChanghua 11 第一章绪论 2人工智能研究的目标近期目标 在近期 人工智能研究的任务是利用冯 偌依曼型计算机模拟人类智力行为 研制智能程序 远期目标 远期是研制全新的计算机 即智能计算机 2020 4 15 WeiChanghua 12 第一章绪论 3人工智能研究途径人工智能研究可以有三种途径进行 符号主义 思维理论 符号主义认为人类认知的基本元素是符号 认知的过程就是符号处理的过程 一阶谓词逻辑 连接主义 阈值理论 连接主义认为人类认知的基本元素是神经元本身 人类的认知过程就是大量的神经元的整体活动 研究方法 人工神经网络 行为主义 进化理论 由美国麻省理工学院的R A Brook教授提出的 该理论认为人的本质能力是在动态环境中的行走能力 对外界事物的感知能力 维持生命和繁衍生息的能力 正是这些能力对智能的发展提供了基础 因此智能是某种复杂系统所浮现的性质 2020 4 15 WeiChanghua 13 第一章绪论 4人工智能研究的内容 1 人工智能研究中的学派逻辑学派 以麦卡锡和尼尔逊为代表的研究基于逻辑的知识表示和推理机制 认知学派 以纽厄尔和西蒙为代表的研究对人类认知功能的模拟 试图找出产生智能行为的原理 知识工程学派 以费根鲍姆为代表的研究知识在人类智能中的作用和地位 提出了知识工程概念 连接学派 以J L McClelland和J D Rumelhart为代表的研究神经网络 分布式学派 以C Hewitt为代表的研究智能系统中的知识分布行为 进化学派 R A Brook为代表 2020 4 15 WeiChanghua 14 第一章绪论 2 人工智能研究的内容 机器感知 所谓的机器感知就是使机器具有类似于人的感知能力 其中以机器视觉与机器听觉为主 机器思维 机器思维是指对通过感知得到的外部信息及机器内部的各种工作信息进行有目标的处理 机器学习 研究使机器具有获取新知识 学习新技巧 并在实践中不断完善 改进的能力 机器行为 与人的行为相对应 机器行为主要是指计算机的表达能力 即 说 写 画 等 2020 4 15 WeiChanghua 15 第一章绪论 5人工智能研究领域 模式识别 PatternRecognition 自然语言理解 NaturallangrageUnderstanding 专家系统 ExpertSystem 机器学习 MachineLearning 自动定理证明 AutomaticTheoremProving 自动程序设计 AutomaticProgramming 机器人学 Robots 博弈 Game 智能决策支持系统 IntelligentDecisionSupportSystem 人工神经网络 Artificialnaturalnetworks 2020 4 15 WeiChanghua 16 第一章绪论 思考题1 什么是人工智能 2 人工智能研究的对象是什么 3 人工智能研究的途径有那些 4 人工智能研究的领域有那些 5 人工智能研究的近期目的和远期目的是什么 6 简述图灵试验 2020 4 15 WeiChanghua 17 第二章人工智能的数学基础 1命题逻辑和谓词逻辑命题 命题是具有真假意义的语句 谓词 一个谓词由谓词名和个体两部分组成 谓词公式 连接词 量词 合适公式 原子是合适公式 若A是合适公式 则 A也是合适公式 若A B都是合适公式 则A B A B A B 也都是合适公式 若A是合适公式则 也是合适公式 谓词公式的永真性 可满足性和不可满足性 2020 4 15 WeiChanghua 18 第二章人工智能的数学基础 2概率论条件概率 设A B是两个事件 则称为在A事件已经发生的条件下B事件发生的概率 全概率公式和Bayes公式的条件概率 设事件满足 两两互不相容 即当时 有 则对任何事件有下式成立 为全概率公式 它提供了一种计算的方法 2020 4 15 WeiChanghua 19 第二章人工智能的数学基础 Bayes公式 称公式为Bayes公式 2020 4 15 WeiChanghua 20 第二章人工智能的数学基础 3模糊理论模糊集 设是论域 是把任意映射为 0 1 上某个值的函数 即 则称由所构成的集合A 称为U上的一个模糊集 隶属函数 称为定义在U上的一个隶属函数 语言变量 用自然语言表示变量的值和描述变量之间的内在联系的一种变量 比如 年龄就是个语言变量 它可以取值为年轻 很年轻 不很年轻 老 很老 不很老等 语言真值模糊推理 2020 4 15 WeiChanghua 21 第二章人工智能的数学基础 思考题1 什么是合适公式 2 试写出Bayes公式 3 什么是语言变量 4 试论述信息 知识 不确定性及其处理的途径 2020 4 15 WeiChanghua 22 第三章知识表示 1知识与知识表示知识是人类认识自然界的精神产物 是人类进行智能活动的基础 知识可以分为五类 描述性知识 判断性知识 过程性知识 对象级知识 或称为领域相关的知识 元级知识 2020 4 15 WeiChanghua 23 2对知识表示的要求 表示能力 可理解性 可访问性 可扩展性3知识表示方法 一阶谓词逻辑 它是一种描述性的表示方法 它的推理机制是归结原理 主要应用于定理证明 语义网络 是由Quillian等人于1968年提出的 它在知识表示中可以表示对象 概念及其相互间的关系 它广泛用于基于知识的系统 产生式规则 产生式系统把知识表示成 模式 动作 对 表示方式自然 简洁 它的推理机制以演绎为基础 它是专家系统的知识表示的主要方法 2020 4 15 WeiChanghua 24 框架 框架理论是Minsky于1974年提出的 它将知识表示成高度模块的结构 它是把关于一个概念或对象的所有信息和知识都存储在一起的数据结构 框架的层次结构可以表示对象之间的相互关系 用框架表示知识的系统称为框架的系统 状态空间 状态空间表示法把求解问题表示成问题状态 操作 约束 初始状态和目标状态 状态空间是所有状态的集合 脚本 脚本也称为剧本 它是用来描述固定事件序列 它的结构类似于框架 剧本更强调事件间的因果关系 Petri网 Petri网是由德国计算机科学家Petri提出的 由于它很好的模拟异步操作 所以在并行处理和分布式计算机领域中应用很多 2020 4 15 WeiChanghua 25 一阶谓词逻辑表示法 谓词逻辑适合于表示事物的状态 属性 概念等事物之间的知识 也可以用来表示事物之间的因果关系 谓词公式一般用合适公式表示 谓词的选取 量词的选取 作用的范围 从自然语言翻译成谓词公式不能丢失信息 易于理解 谓词公式表示法的特点 自然性 精确性 严密性 容易实现 2020 4 15 WeiChanghua 26 产生式表示法 产生式表示具有因果关系的知识 其基本形式是或者其中P是产生式前提 Q是一组结论或操作 产生式组成 规则库 综合数据库 控制系统 产生式系统分类 可交换的产生式系统 可分解的产生式系统 可恢复的产生式系统 产生式表示法的特点 自然性 有效性 模块性 清晰性 效率不高 不能表示具有结构性的知识 2020 4 15 WeiChanghua 27 框架 框架是一种描述所论对象 一个事物 一个事件 一个概念 属性的数据结构 框架的结构 一个框架是由若干槽组成 每个槽又可以有若干个侧面 槽用来描述所论对象的某方面的属性 侧面用来描述相应属性的一个方面 槽和侧面所具有的属性值分别称为槽值和侧面值 框架网络 框架中的槽值或侧面值可以是另一个框架的名字 这就在框架之间建立了联系 构成了框架网络 通过框架网络可以找到另一个框架 继承性是框架表示法的一个重要特征 它不仅可以在两层框架之间实现继承关系 而且可以通过两两的继承关系 从最底层追溯到最高层 使最高层的信息逐层向底层传递 框架中槽的设置与组织 2020 4 15 WeiChanghua 28 充分表达事物个有关方面的属性 充分表达相关事物间的各种关系 ISA槽 AKO槽 Subclass槽 Instance槽 Partof槽 Infer槽 Possible Reason槽 有利于进行框架的推理 2020 4 15 WeiChanghua 29 框架表示法的特点 结构性 继承性 自然性语义网络表示法 语义网络是通过概念及其语义关系表达知识的一种网络图 最简单的语义网络是如下的三元组 节点1 弧 节点2 知识的语义网络表示 用语义网络表示有关事实间的关系 分类关系 聚集关系 推论关系 时间 位置关系 多元关系 用语义网络表示比较复杂的知识 把一个复杂的知识命题划分为若干个子命题 每个子命题用一个较简单的语义网络表示 称为子空间 多个子空间构成一个大空间 2020 4 15 WeiChanghua 30 常用的语义联系 A Member of Composed of Have Before After At Located on at under inside outside 等 Similar to Near to 语义网络系统中求解问题的基本过程 用语义网络表示知识的问题求解系统称为语义网络系统 系统由语义网络构成的知识库 问题求解的解释程序 语义网络推理机 组成 问题求解一般是通过匹配实现的 2020 4 15 WeiChanghua 31 语义网络表示法的特点 结构性 联想性 自然性 2020 4 15 WeiChanghua 32 脚本表示法 脚本的知识表示方法是R C Schank根据他的概念依赖理论提出的一种知识表示方法 它与框架类似 由一组槽组成 用来表示特定领域内一些事件的发生序列 概念依赖理论 把人类生活中的各类故事情节的基本概念抽取出来 构成一组原子概念 确定这些原子概念之间的相互依赖关系 然后把所有故事情节都用这组原子概念及其依赖关系表示出来 脚本一般由以下几部分组成 进入条件 角色 道具 场景 结局 2020 4 15 WeiChanghua 33 过程表示法 过程性表示方法着重于对知识的利用 它把问题有关的知识以及如何应用这些知识求解问题的控制策略都表述为一个或多个求解问题的过程 每一个过程是一个程序 用于完成对一个具体事件或情况的处理 用过程规则表示过程 过程规则的一般结构 激发条件 演绎操作 状态转换 返回 过程表示法的特点 效率较高 控制系统容易设计 2020 4 15 WeiChanghua 34 Petri网表示法 对于不同的应用Petri网的构成及构成元素的意义均不相同 但有三种元素是基本的 位置 转换 标记 Petri网的特点 便于描述系统状态的变化 便于对系统特点进行分析 可以在不同层次上变换描述 而不必注意细节几相应的物理表示 面向对象表示法 对象 类 封装 继承是面向对象技术的基本概念 在面向对象方法中 类 子类 具体对象构成了一个层次结构 而且子类可以继承父类的数据和操作 这种层次结构及继承机制直接支持了分类知识的表示 2020 4 15 WeiChanghua 35 第三章知识表示 思考题1知识可以分为哪五类 2知识表示主要有那些方法 3用一阶谓词逻辑表示下列的句子 1 一个充分大的偶数 even 可以表示为两个素数 prime 之和 2 对于任意集合 存在有一个集合 使得集合的基大于集合的基 3 Acomputersystemisintelligentifitcanperformataskwhich ifperformedbyahuman requiresintelligence 4 并非所有的有理数 rationalnumber 都是整数 5 计算机系2001级的男生 manstudent 除了看电影的人外 其余的都去听学术报告 academicreport 了 2020 4 15 WeiChanghua 36 3用语义网络表示下列句子 1 树和草都是植物 2 树和草都是有根有叶的 3 水草是草 且长在水中 4 果树是树 且会结果 苹果树是果树中的一种 它结苹果 5 典型的哺乳动物有毛发 6 狗是哺乳动物 且吃肉 4一个求职框架系统包含以下框架 Frame求职类 A Frame经理 Isa求职类 Isa招聘类 学位Value 硕士以上 年龄Value Always30以下 Frame李明 学位Value Always学士以上 Isa求职类 A Frame销售经理 年龄Value 40岁 Isa经理 公关能力Value 高 公关能力Value 高 请问李明有资格申请销售经理的职位吗 为什么 2020 4 15 WeiChanghua 37 5试用框架结构表示一个大学的人事组织结构 6产生式系统由那些部分组成 它们的作用是什么 7为什么说框架系统和语义网络都是结构化的知识表示方法 两者的共同和不同之处是什么 8有3个积木块 A B C 放在桌子上 且可以叠放在一起 要求在任意初始状态 按自上而下A B C的顺序迭放这3个积木块 搬动积木块应遵循以下约束 1 每次只能搬一块 2 只有顶空的积木块才能搬动请为机器人搬动积木块设计一个产生式系统 包括综合数据库 规则库和冲突消解算法 2020 4 15 WeiChanghua 38 第四章基本的问题求解方法 1基本概念 什么是搜索人工智能要解决的问题大多数是结构不良或者非结构的问题 对这样的问题一般不存在成熟的求解算法 而只能利用已有的知识一步步地摸索着前进 在这个过程中 存在着如何寻找一条推理路线 使得付出的代价尽可能地少 而问题又能够得到解决 我们称寻找这样路线的过程为搜索 搜索分为盲目搜索和启发式搜索 盲目搜索是按预定的控制策略进行 在搜索的过程中所获得的信息不用来改进控制策略的一种搜索 启发式搜索是在搜索中加入了与问题有关的启发式信息 用来指导搜索朝着最有希望的方向前进 加速问题的求解过程 并找到最优解 2020 4 15 WeiChanghua 39 状态空间表示法 状态空间表示法是用 状态 和 算符 来表示问题的一种方法 状态 状态是描述问题求解过程中任一时刻状况的数据结构 算符 引起状态的某些分量变化 从而使问题从一个状态变为另一个状态的操作称为算符 状态空间 问题的全部状态和一切算符所构成的集合成为状态空间 例如二阶梵塔问题 解 设立柱1 2和3以及两个圆盘A和B 用Sk Sk0 Sk1 表示问题状态 Sk0表示圆盘A所在的立柱 Sk1表示圆盘B所在的立柱 全部可能的状态共有九种 S0 1 1 S1 1 2 S2 1 3 S3 2 1 S4 2 2 S5 2 3 S6 3 1 S7 3 2 S8 3 3 问题的初始状态集合是S S0 目标状态集合是G S4 S8 2020 4 15 WeiChanghua 40 S0 1 1 S1 1 2 S2 1 3 S3 2 1 S4 2 2 S5 2 3 S6 3 1 S7 3 2 S8 3 3 二阶梵塔问题状态表示 2020 4 15 WeiChanghua 41 与 或树表示法 对于一个复杂的问题 可以通过 分解 和 等价变换 两种手段相结合使用 得到一个图 这个图就是与 或图 等价变换 是一种同构或同态的变换 本原问题 不能再分解或变换 而且直接可以求解的子问题 称为本原问题 终端节点与终止节点 在一棵与 或树中 没有子节点的节点称为终端节点 本原问题所对应的节点称为终止节点 可解节点 在与 或树中 满足下列条件之一者就称为可解节点 它是一个终止节点 它是一个 或 节点 且其子节点中至少有一个是可解节点 它是一个 与 节点 且其子节点全部是可解节点 不可解节点 关于可解节点的三个条件全部不满足的节点称为不可解节点 解树 由可解节点构成 且由这些可解节点可推出初始节点 它对应于原始问题 为可解节点的子树称为解树 2020 4 15 WeiChanghua 42 2状态空间搜索 状态空间搜索的一般过程 OPEN表和CLOSED表 OPEN表是用于存放刚生成的节点 CLOSED表用于存放将要扩展的节点 搜索的一般过程 广度优先搜索 从初始节点S0开始 逐层地对节点进行扩展并考查它是否为目标节点 在第n层的节点没有全部扩展并考查之前 不对第n 1层节点进行扩展 OPEN表中的节点总是按进入的先后顺序排列 先进入的节点排在前面 后进入的节点在后 深度优先搜索 从初始节点S0开始 在其子节点中选择一个子节点进行考查 若不是目标节点 则再在该子节点中选择一个子节点进行考查 一直如此向下搜索 当到达某个子节点 且该子节点既不是目标节点又不能继续扩展时 才选择其兄弟节点进行考察 与广度优先搜索不同 深度优先搜索是把节点n的子节点放入OPEN表的首部 2020 4 15 WeiChanghua 43 有界的深度优先 对深度优先搜索引入搜索深度的界限 当搜索深度达到了深度界限 而尚未出现目标节点 就换一个分支进行搜索 代价树的广度优先搜索 与 或树中 边上有代价 或费用 的树称为代价树 代价树的广度优先搜索的基本思想是每次从OPEN表中选择节点往CLOSED表中传送时 总是选择其代价最小的节点 代价树的深度优先搜索 基本思想是从刚扩展的子节点中选择一个代价最小的节点送入CLOSED表进行考查 2020 4 15 WeiChanghua 44 启发式搜索 启发式搜索是利用问题本身的某些启发信息 以制导搜索朝着最有希望的方向前进 估价函数 用于估价节点重要性的函数称为估价函数 它的一般形式为 局部择优搜索 当一个节点被扩展后 按f x 对每个子节点计算估价值 并选择最小者作为下一个要考查的节点 由于它每次都只是在子节点的范围中选择要考查的子节点 所以称为局部择优搜索 全局择优搜索 每次都是从OPEN表的全体节点中选择一个估价值最小的节点进行扩展 2020 4 15 WeiChanghua 45 算法 把OPEN表中的节点按估价函数的值从小到大进行排序 g x 是对g x 的估计 g x 0 h x 是h x 的下界 即对所有x的均有 其中g x 是从初始节点S0到节点x的最小代价 g x 是从x节点到目标节点的最小代价 若多个目标节点 则为其中的一个 2020 4 15 WeiChanghua 46 3与 或树搜索 与 或树搜索的一般过程 与 或树搜索的广度优先搜索 与 或树搜索的深度优先搜索 与 或树搜索的有序搜索 2020 4 15 WeiChanghua 47 4博弈树的启发式搜索 博弈树的概念 博弈树是与 或树的一个特例 博弈的初始格局是初始节点 在博弈树中与节点和或节点总是逐层交替出现的 所有能使自己一方获胜的终局都是本原问题 相应的节点是可解节点 所有使对方获胜的终局都是不可解节点 极大极小法 剪枝技术 值 对于一个或节点来说 取当前子节点中的最大倒推值作为它倒推值的下界 称此值为 值 值 对于一个与节点来说 取当前子节点中的最小倒推值作为它倒推值的上界 称此值为 值 2020 4 15 WeiChanghua 48 剪枝技术 任何或节点x的 值如果不能降低其父辈节点的 值 则对节点x以下的分支可停止搜索 并使的倒推值为 这种剪枝称为 剪枝 任何 与 节点x的 值如果不能升高其父辈节点的 值 则对节点x以下的分支可停止搜索 并使的倒推值为 这种剪枝称为 剪枝 2020 4 15 WeiChanghua 49 第四章基本的问题求解方法 思考题1什么是状态和状态空间 2理解OPEN表和CLOSE表的作用 3什么是盲目搜索 什么是启发式搜索 4宽度优先与深度优先的区别是什么 5叙述可解节点和不可解节点的定义 6在博弈树中 剪枝技术是如何进行的 7试叙述搜索的估价函数的含义 8试叙述A 算法的总体思路 9有一农夫带一只狐狸 一只小羊和一篮菜过河 从左岸到右岸 假设船太小 农夫每次只能带一样东西过河 考虑到安全 无农夫看管时 狐狸和小羊不能在一起 小羊和那篮菜也不能在一起 请为该问题的解决设计状态空间 并画出状态空间图 10应用启发式搜索算法A解决八数码问题 2020 4 15 WeiChanghua 50 第五章基本推理方法 1推理的基本概念推理通常是指从已知的事实出发 通过运用已掌握的知识 找出其中蕴藏的事实 或归纳出新的事实 这一过程就称为推理 推理包括两种判断 一种是已知的判断 它包括已掌握的求解问题有关的知识和关于问题的已知事实 另一种是由已知判断推出新的判断 即推理的结论 2推理方式和分类 按推理机制划分 可以有 演绎推理 演绎推理是从全称判断推导出特称或单称判断的过程 归纳推理 归纳推理是从足够的事例中归纳出一般性结论的推理过程 默认推理 默认推理又称缺省推理 它是在知识不完全的情况下假设某些条件已经具备所进行的推理 2020 4 15 WeiChanghua 51 按所用知识的确定性划分 可以有 确定性推理 确定性推理是指推理时所用的知识都是精确的 推理出的结论也是精确的 不精确推理 不精确推理是指在推理时所用到的知识不都是精确的 推理出的结论也不完全是肯定的 按推理过程划分 可以有 单调推理 单调推理是指在推理的过程中随着推理的向前推进及新知识的加入 推理的结论呈单调增长的趋势 并越来越接近最终目标 非单调推理 非单调推理是指在推理的过程中 由于新的知识的加入 不仅没有加强推出的结论 反而要否定它 使得推理退回到前面的一步 重新开始 2020 4 15 WeiChanghua 52 按启发性知识划分 可以有 启发式推理 在推理的过程中利用了能够加快推理进程 求得最优解的启发性知识的推理 非启发性推理 在推理的过程中并不利用能够加快推理进程 求得最优解的启发性知识的推理 按方法论划分 可以有 基于知识的推理 统计推理 直觉推理 直觉推理又称为常识性推理 是根据常识进行的一种推理 2020 4 15 WeiChanghua 53 3推理控制策略 正向推理 从用户提供的初始事实出发 在知识库中找出当前可适合的知识 构成可适用的知识集 然后按某种冲突消解策略从知识集中选出一条知识进行推理 并将推理出的新事实加入到数据库作为下一步推理的已知事实 如此重复这一过程 逆向推理 首先选定一个假设目标 然后寻找支持该假设的证据 若所需要的证据都能找到 则说明假设是成立的 若无论如何都找不到所需要的证据 说明原假设不成立 混合推理 即有正向推理又有逆向推理的推理方法就是混合推理 双向推理 所谓双向推理是指正向推理和逆向推理同时进行 且在某一步骤上相遇 基本思想是 一方面根据已知事实进行正向推理 但并不推到最终目标 另一方面 从某一假设目标出发进行逆向推理 但并不推至原始事实 而是让它们在途中相遇 既正向推理所得的中间结论恰好是逆向推理此时所需要求的证据 2020 4 15 WeiChanghua 54 4归结反演归结反演就是用归结和反演的方法实现定理证明 子句定义为由文字的析取组成的公式谓词公式化为子句集的过程 消去蕴涵符号 把否定符号移到每个谓词符号的前面 变量标准化 消去存在量词 将公式化为前束形 把母式化为合取范式 略去全称量词 把母式用子句表示 子句变量标准化 2020 4 15 WeiChanghua 55 归结反演的一般过程 设有公式集S 希望从S证明某个目标公式W 证明的过程如下 将 W加入到S集合 将新的集合S转换成一组子句 应用归结原理推导出一个空子句归结反演过程主要就是证明一个集合是不可满足的过程 即从集合归结出空子句的过程 归结反演的控制策略 宽度优先策略 支持集策略 单元优先策略 线性输入策略 祖先过滤策略 2020 4 15 WeiChanghua 56 5基于规则的演绎系统将问题的知识和信息划分为规则和事实两种类型 规则有包含蕴涵形式的表达式 事实由无蕴涵形式的表达式表示 这样的推理系统称为基于规则的演绎系统 正向演绎系统 从事实出发 正向地使用蕴涵式 F规则 进行演绎推理 直到某个目标公式的一个终止条件为止 事实表达式 事实表达式为无蕴涵的任意与或形 利用规则转换与或图 正向演绎系统应用规则作用于事实的与或图 改变与或图的结构 从而产生新的事实 规则形式为其中L是单文字 W是任意的与或形表达式 L和W中的所有变量都是全称量化的 利用目标公式做结束条件 正向演绎系统的目标公式定义为文字的析取 当一个目标文字与与或图中的文字匹配时 系统便成功结束 2020 4 15 WeiChanghua 57 逆向演绎系统 在逆向演绎系统从目标表达式出发 应用逆向规则 规则 直到事实表达式 目标表达式 在逆向演绎系统中 目标公式为无蕴涵的任意与或形 规则应用 逆向演绎系统的规则称为规则 形为其中W为任意的与或形 L为单文字 结束条件 逆向演绎系统的事实表达式限制为文字的合取 可表示为文字的集合 逆向演绎系统的结束条件就是与或图中包括一个结束在事实结点上的一致解图 该解图的合一复合作用于目标表达式就是解答语句 2020 4 15 WeiChanghua 58 第五章基本推理方法 思考题1叙述求公式子句集的全过程 2归结反演方法证明定理的基本思想是什么 3归结反演的控制策略是什么 4正向演绎与逆向演绎各自的特点是什么 5设有以下的谓词演算公式 试写出其转换成子句集的过程 1 2 3 4 2020 4 15 WeiChanghua 59 6招聘工作人员 A B C三人应试 经面试后公司表示如下想法 1 三人中至少录取一人 2 如果录取A而不录取B 则一定录取C 3 如果录取B 则一定录取C试用归结反演法证明公司一定录取C 7假设已知下列事实 1 李华 LiHua 喜欢的容易的 Easy 课程 course 2 李华 LiHua 不喜欢的难的 Difficult 课程 course 3 工程类 Eng 的课程都是难的 4 物理类 Phy 的课程都是容易的 5 吴刚 Wugang 喜欢所有李华不喜欢的课程 6 Phy200是门物理类课程 7 Eng300是门工程类课程 请用归结反演方法回答下列问题 1 吴刚喜欢什么课程 2 吴刚喜欢Eng300课程吗 2020 4 15 WeiChanghua 60 8已知事实表达式 F规则 求目标公式 2020 4 15 WeiChanghua 61 第六章不确定性推理 1不确定性推理的基本概念 什么是不确定性推理所谓不确定性推理就是从不确定性的初始证据出发 通过运用不确定性的知识 最终推理出具有一定程度的不确定性 但又是合理或者似乎合理的结论的思维过程 不确定性推理的一般算法 根据规则前提E的不确定性C E 和规则强度f H E 求出假设H的不确定性C H 即定义一函数g1 使C H g1 C E f H E 根据分别由独立的证据E1和E2 求得的假设H的不确定性C1 H 和C2 H 2020 4 15 WeiChanghua 62 求得证据E1和E2的组合所导致的假设的不确定性C H 即定义一函数g2 使C H g2 C1 H C2 H 根据两个证据E1和E2的不确定性C E1 和C E2 求出证据E1和E2的合取E1 E2的不确定性 即定义一函数g3 使C E1 E2 g3 C E1 C E2 根据两个证据E1和E2的不确定性C E1 和C E2 求出证据E1和E2的析取的不确定性 即定义函数g4 使C E1 E2 g4 C E1 C E2 几种主要的不确定性推理方法 确定因子法 可信度方法 主观Bayes方法 证据理论 可能性理论 粗集理论 批注理论 2020 4 15 WeiChanghua 63 2确定因子法 知识的不确定性表示MYCIN系统称规则强度为规则确定性因子 CertaintyFactor CF H E 它表示在已知证据的情况下 对假设的确信程度 CF H E 定义如下 证据的不确定性 2020 4 15 WeiChanghua 64 不确定性推理 根据证据和规则的不确定性求假设的不确定性 组合两个独立证据导出的同一个假设的不确定性 由此计算 2020 4 15 WeiChanghua 65 证据的合取 证据的析取 2020 4 15 WeiChanghua 66 3主观Bayes方法主观Bayes方法是以概率论中的Bayes公式为基础的一种不确定性推理算法 首先应用于专家系统PROSPECTOR系统 知识不确定性的表示 在该方法中知识的不确定性表示为其中规则强度由LS和LN表示 证据的不确定性 证据的不确定性用证据的概率P E 表示 或者用证据的几率 E 2020 4 15 WeiChanghua 67 不确定性推理算法 采用三点的线性插值方法 即当时 有当时 有当时 有分段插值的解析式为 2020 4 15 WeiChanghua 68 4证据理论证据理论是由Dempster和他的学生Shafer共同提出来的一种不确定性推理模型 所以也称为D S证据理论 证据理论可以满足比概率更加弱的公里体系 当概率值已知的时候 证据理论就变成为概率论了 证据的不确定性设U的幂集2U上定义了一个基本概率赋值函数m 2U 0 1 使满足 基本概率赋值函数m A 表示了证据对U的子集A成立的一种信任程度 2020 4 15 WeiChanghua 69 信任函数 信任函数定义为似然函数 似然函数定义为信任函数与似然函数的关系 2020 4 15 WeiChanghua 70 证据组合 对于相同的证据 由于来源不同 可能得到不同的基本概率赋值函数 D S证据理论采取正交和来组合这些函数 设是上的个基本概率赋值函数 它们的正交和 且定义为其中 证据理论的推理 知识表示 系统的推理规则表示为 证据的描述 对于任何命题 其信任函数为 2020 4 15 WeiChanghua 71 似然函数为 类概率函数 不确定性推理 匹配度函数 2020 4 15 WeiChanghua 72 命题的逻辑组合的情况 合取 析取 如果几种规则支持同一命题 总的概率赋值函数定义为各规则假设得到的基本概率赋值函数的正交和 即 2020 4 15 WeiChanghua 73 5可能性理论Zadeh在1965年提出了模糊集合论 1978年又提出了可能性理论 模糊命题 含有模糊概念 模糊数据或带有确信程度的语句称为模糊命题 形式化为 xisA或者xisA CF 其中 X是论域上的变量 用来代表所论对象的属性 A是模糊概念或模糊数 CF是该模糊命题的确信度 它可以是一个确定的数 也可以是模糊数 还可以是模糊语言值 模糊知识的表示 模糊产生式规则的一般形式为其中E是用模糊命题表示的模糊条件 H是用模糊命题表示的模糊结论 CF是该产生式规则所表示的知识可信度因子 2020 4 15 WeiChanghua 74 语义距离 设A B分别是论域上相应的模糊概念的模糊集 而和分别是它们的隶属函数 则有 海明距离 海明距离定义为 欧几里德距离 明可夫斯基距离 2020 4 15 WeiChanghua 75 切比雪夫距离 语言变量 用语言而不是用数字来表示变量的值和变量之间的关系 这种变量称为语言变量 模糊命题的转换规则 修正规则 合取 析取和蕴含规则 量化规则 模糊推理 广义假言推理 模糊量词的近似推理 模糊真值限定的近似推理 2020 4 15 WeiChanghua 76 6粗集理论粗集理论是波兰华沙理工大学的Z Pawlak教授1982年首先提出的处理不确定性信息的理论 该方法特别实用于观察和测量获得的不精确数据的分类问题 2020 4 15 WeiChanghua 77 第六章不确定性推理 思考题1分别以不精确性 不完全性 模糊性 时变性和非单调性举例说明现实世界知识的不确定性 2构造一个不确定性知识系统一般要涉及到那几个问题 3说明确定因子法中的MB和MD的物理意义 4设学生考试成绩的论域为 小王成绩得A 得B 得A或B的基本概率分别分配到0 2 0 1 0 3 为0 2 请给出 和 2020 4 15 WeiChanghua 78 5设某问题求解用到下面的推理规则 试用确定因子法求出的可信度 假定已知在当前观察有6设有一组规则 推理网络如图所示 Rule1 IFE1 E2THENE3 a1 a2 CF 0 2 0 6 Rule2 IFE5 E8THENE4 b CF 0 8 Rule3 IFE3THENH h1 h2 h3 CF 0 2 0 5 0 3 Rule4 IFE4THENH h1 h2 h3 CF 0 3 0 4 0 1 Rule5 IFE6 E7THENE8CF 0 8 2020 4 15 WeiChanghua 79 已知 CF E1 0 7CF E2 0 8CF E5 0 6CF E6 0 4CF E7 0 9试用D S证据理论求出CF H H h1 h2 h3 E1 E2 E5 E6 E7 E3 E4 E5 2020 4 15 WeiChanghua 80 第七章专家系统 1专家系统的基本概念 什么是专家系统 专家系统是一个智能程序 它具有相关领域的大量专家知识 它可以模拟人类专家解决问题的思维过程 且解决问题的能力不低于人类领域专家 专家系统的特征 具有专家水平的专门知识 能进行有效的推理 具有获取知识的能力 具有灵活性 具有透明性 具有交互性 具有一定的复杂性和难度 2020 4 15 WeiChanghua 81 专家系统与常规程序的区别 常规程序 数据结构 算法专家系统 知识 推理 常规程序将知识组织成数据级和程序级 而专家系统将知识组织成数据级 知识库级和控制级 常规程序一般是通过查找或计算获取问题的解 本质上是数值计算 而专家系统是通过推理获取问题的解或证明某个假设 本质上是符号处理 常规程序处理的数据多数是精确的 而专家系统处理的数据大多数是不精确的 模糊的 常规程序一般不需要具备解释功能 而专家系统一般具有解释机构 它可以对自己的行为作出解释 常规程序与专家系统具有不同的软件体系结构 2020 4 15 WeiChanghua 82 专家系统研究的历史 世界上第一个专家系统1965年 A Feigenbum DENDRAL 中国第一个专家系统1978年 中国科学院自动化研究所涂序彦 关幼波肝病诊断与治疗专家系统 2020 4 15 WeiChanghua 83 2专家系统分类 按专家系统的特征分类 解释型 诊断型 预测型 设计型 规划型 控制型 检测型 维修型 教育型 调试型 2020 4 15 WeiChanghua 84 按系统的体系结构分类 集中式专家系统 分布式专家系统 神经网络专家系统 符号系统与神经网络相结合的专家系统3专家系统的一般结构 专家系统的基本结构专家系统的基本结构由五部分组成 知识库 用于存放问题求解所需要的知识 综合数据库 用于存放系统运行过程中所需要的原始数据和产生的所有信息 推理机 根据综合数据库当前的状态 利用知识库中的知识进行推理 知识获取程序 这个部件负责建立 修改和扩充知识库 并对知识库中的知识进行一致性 完整性进行维护 解释程序 解释程序用于对求解过程作出说明 并回答用户提出的问题 2020 4 15 WeiChanghua 85 人机接口 推理机 解释程序 知识获取程序 数据库及其管理系统 知识库及其管理系统 专家系统的一般结构 用户 领域专家 2020 4 15 WeiChanghua 86 4专家系统的建造与评价 专家系统建造的原则 恰当划定求解问题的领域 获取完备的知识 知识库与推理机的分离 选择 设计合适的知识表示 推理机应模拟领域专家求解问题的思维过程 建立良好的交互环境 渐增式的开发策略 2020 4 15 WeiChanghua 87 专家系统的开发过程 需求分析 系统设计 知识获取 编程 调试 原型测试 修正与扩充 系统包装及总调 系统维护 2020 4 15 WeiChanghua 88 专家系统的评价 知识的完备性 表示方法及组织方法的适