人工智能知识表示.ppt

第五章知识表示 表示是使用人造的体系对自然界事物的运算规律进行概括与抽象的模型 知识表示是概括智能的模型 需同时满足 刻画智能现象 与 计算装置可接受 两个条件 表示观 注重形式化的认知观注重模拟客观世界本体的本体观 产生式规则是一种使用最广泛的表示方法 语义网络 框架 脚本都是结构化的表示方法 结构化表示法适合描述那些带有结构 层次 比较复杂的事物 反映了人们使用知识的方式 提供了结构的描述关系 评价知识表示方法从表示的能力和效率两个方面考虑 表示能力 区分与避免不必要区分 一阶谓词逻辑最强 其它方法是其子集 效率 考虑知识获取和知识库维护的效率 适合人的思维 考虑推理机的效率 适合机器实现 一阶谓词逻辑最弱 经典人工智能的主要表示方法 一阶谓词逻辑是最基本的表示方法 具有严谨的公理体系 5 1逻辑表示法 用谓词表示知识 命题 表示知识的陈述性形式称为命题 例 张平是学生 树叶是绿色的 谓词 带有参数的命题叫做谓词 例 是学生 X 谓词比命题有更强的表达能力 1 有概括能力 2 引进了变量 3 在知识之间建立联系 是学生 X X是学生受纪律约束 X X受纪律约束犯错误 X X犯错误受纪律惩罚 X X受纪律惩罚 连接后 是学生 X 受纪律约束 X 犯错误 X 受纪律惩罚 X 6 X 是学生 X 学籍 X Y 是教师 Y 职称 Y 例 没有无学籍的学生 也没有无职称的教师 1 Q 2 没有无学籍的学生 也没有无职称的教师 3 存在无学籍的学生 存在无职称的教师 4 X 无学籍的学生 X Y 无职称的教师 Y 5 X 是学生 X 无学籍 X Y 是教师 Y 无职称 Y 第一种谓词简单 个数多 较灵活第二种谓词复杂 个数少 利于检索 这个命题可在六个不同的层次表示 分得细知识多推理效率低分得粗知识少推理效率高上述方式是谓词多 参数少 另一种是谓词少 参数多P x1 x2 x10 其中 x1表示是否 x2表示动作 x3表示有无 x4 x5表示对象 x6到x10与x1到x5一样 即 P 不 存在 无 学籍 学生 不 存在 无 职称 教师 可表示为 x A x B x 或 x B x A x 或 x A x B x 用谓词表示知识的例子 1 所有的有理数都是实数 令P x 表x是有理数 Q x 表x是实数 则应为 x P x Q x 而不是 x P x Q x 2 有的实数是有理数 应为 x Q x P x 而不是 x Q x P x 3 没有无理数是有理数 A x 表示无理数 B x 表示有理数 x 机器 x 型号 x B 电源故障 x 4 凡是桌面上没放书本的桌子都配有台灯 x 桌子 x 上面放书 x 配有台灯 x x 桌子 x y 书 y 在上面 y x z 台灯 z 在上面 z x x 桌子 x 在上面 书 x 在上面 台灯 x 5 张宏的母亲和谁都没吵过架 x 人 x 吵架 母亲 张宏 x 6 型号B的所有机器都有电源故障 7 放在台灯下面的书可能是数据结构 也可能是编译原理 不会是别的书 用谓词表示自然语言 用谓词和项表示句子的关系和实体一元谓词表示一个集合 多元谓词表示一个关系 x 学校 x 老同学 母亲 赵亮 校长 x 8 赵亮的母亲和某校的校长是老同学 书 a 台灯下面 a 是 a 数据结构 是 a 编译原理 重迭量词 对于二元谓词R x y 可以连续两次引用量词 有四种形式 x y R x y 一切x和一切y有关系R x y R x y 一切x和有的y有关系R x y R x y 有的x和一切y有关系R x y R x y 有的x和有的y有关系R 例 一切固体都可以被某些液体所溶解 x 固体 x y 液体 y 被溶解 x y 有的液体可以溶解一切固体 y 液体 y x 固体 x 被溶解 x y 产生式也称作规则 或产生式规则 产生式一词来源于Post机 Post机是E Post在1943年根据字符串替换规则提出的称为产生式系统的一种计算模型 5 2产生式系统知识之间存在着大量的因果关系 可以用一种称之为 产生式 的形式来描述 例 如果大学毕业 就能找到工作如果大学毕业 热门专业 名牌大学 就能找到好工作 综合数据库是产生式使用的主要数据结构 它用来表述问题状态或有关事实 对应于表示问题的说明式知识 产生式系统的基本结构 产生式系统是问题求解系统 它是把一组产生式放在一起 让它们互相配合 协同作用 一个产生式生成的结论可以供另一个产生式作为前提 以这种方式求得问题的解决 一个产生式系统由三个基本部分组成 一个综合数据库 一组产生式规则和一个控制系统 一组产生式规则构成了规则库 每一条规则形如 IF条件THEN行动或IF前提THEN结论 IF积木X在A处AND积木X上面为空AND机械手在A处AND机械手为空THEN机械手抓起积木X 条件 行动 例如 IF动物是哺乳动物AND动物吃肉THEN动物是食肉动物 前提 结论 控制系统是规则的解释程序 它规定了如何选择一条可用的规则的原则 搜索策略 和规则使用的方式 推理方向 并根据综合数据库的信息 控制求解问题的过程 PrecedureRespond扫描数据库 找到可用规则集S whileS非空且问题未被求解dobegin调用过程select Rule S 从S中选出规则R 执行R的结果部分 更新数据库的内容 扫描数据库 找到可用规则集Send 5 2 1推理方式 正向推理正向推理的基本思想是从已知数据信息出发 正向使用规则 让规则的前提与数据库匹配 求解问题 它要求用户首先输入有关当前问题的信息作为数据库中的事实 下述的过程Respond是这种策略的基本思想 正向推理的主要缺点是激活规则表面看无目的 或者说系统为达到目标可能执行若干无用动作 规则 可用 是指数据库中有满足该规则的条件部分的事实 过程select Rule负责选择规则 与问题有关的控制信息在此体现 可使用评价函数 也可精心排序 过程Respond是原理示意程序 实际系统要复杂的多 例如 如何查找规则 是顺序 还是索引 如何判断规则可用 是简单匹配 比较 还是计算 正向推理就是执行 识别 动作 正向推理的主要优点是允许用户主动提供有用的事实信息 而不必等到用户需要时才提供 它适合于 解空间 很大的一类问题 象设计 规划 预测 监控 管理等 反向推理的优点 适合解空间教小的问题不必使用与总目标无关的规则有利于向用户提供明确的解释反向推理的缺点 目标选择盲目 不允许用户主动提供信息指导推理当规则的then是动作时 反向推理无法使用 反向推理 反向推理基本思想是 选定一个目标 然后在知识库中查找能导出该目标的规则集 若这些规则中的某条规则前提与数据库匹配 则成功 否则 将该规则前提作为子目标 递归执行上述过程 直到总目标被求解或者没有能导出目标的规则 过程Achieve G 给出了反向推理的基本思想 ProcedureAchieve G 扫描数据库 如果找到G 返回T否则找到能导出G的规则集S whileS非空dobegin调用过程Choose Rule S 从S中选出规则RwhileR在S中且R的前提部分非空dobeginG HEAD R的前提部分 R的前提部分 TAIL R的前提部分 M Achieve G ifM为F then从S中去掉RendIfR在S中then返回Tend当S为空时 返回Fend R1 如果叶子脱落则是落叶树R2 如果叶子保持则是常青树R3 如果松树球果则是裸子植物R4 如果针叶则是裸子植物R5 如果二针叶or三针叶or五针叶则是针叶R6 如果是裸子植物and常青树and五针叶则是白松树R7 如果是裸子植物and落叶树and簇针叶则是落叶松树 例 已知有如下数据库和规则库数据库 叶子保持 五针叶规则库 解 产生式系统的正向推理的一般策略为 1 找出可用规则集2 若可用规则集空或已找到目标则结束 否则3 选择一条规则 本题可按自然顺序 4 将结论放入数据库5 找出可用规则集 转2 开始 找出可用规则集 R2和R5执行2 后 继续3 5 条 结果如下 选择一条规则 按自然顺序 R2将结论放入数据库 叶子保持 五针叶 常青树找出可用规则集 R5再次执行2 后 继续3 5 条 结果如下 使用上述的数据库和规则库说明产生式的正向推理过程 反向推理略 选择一条规则 按自然顺序 R5将结论放入数据库 叶子保持 五针叶 常青树 针叶找出可用规则集 R4再次执行2 后 继续3 5 条 结果如下 选择一条规则 按自然顺序 R4将结论放入数据库 叶子保持 五针叶 常青树 针叶 裸子植物找出可用规则集 R6再次执行2 后 继续3 5 条 结果如下 选择一条规则 按自然顺序 R6将结论放入数据库 叶子保持 五针叶 常青树 针叶 裸子植物 白松树找出可用规则集 nil再次执行2 后 结束 数据与数据的匹配是指在规则中没有变量的情况 此时 规则的前提中 不论是要比较 还是计算 最后 总之是用数据和数据库中的数据进行匹配 5 2 2匹配方式 不论是正向推理 还是反向推理 在挑选可用的规则时 都是要利用数据库的数据或事实 判定规则的前提是否为真 即规则前提与数据库匹配 考虑规则中是否带有变量 这种匹配可分为三种 数据与数据的匹配 数据与变量的匹配 变量与变量的匹配 这里的变量概念是广义的 可是一般的变量 也可是指数据与一般的变量共同组成的模式 变量与变量的匹配是在有变量的情况下进行反向推理时出现 给定一个断言 假定不含变量 在反向推理中 用它和规则的结论匹配 形成一个环境 规则前提的变量应从此环境取值 但是 前提中的变量在结论中可能不出现 这样 当前提作为新的未知断言 让它去和某规则的结论匹配时 就出现变量与变量的匹配 这种匹配正是我们在归结推理中讲的合一算法 数据与变量的匹配是在规则中有变量的情况下进行正向推理时出现 有变量的正向推理数据与变量的匹配是在规则中有变量的情况下进行正向推理时出现 我们假定有一个使用汉语的演绎系统做正向推理 其中用英语字母表示变量 用汉语表示常量 有如下规则 规则203 如果 x是y的母亲 y是男性 z是x的姐妹 z是w的母亲 则 z是y的姨母 y是w的表兄弟 若又有以下事实 王夫人是贾宝玉的母亲 王夫人是贾元春的母亲 薛王氏是王夫人的姐妹 薛王氏是薛蟠的母亲 薛王氏是薛宝钗的母亲 贾宝玉是男性 贾元春是女性 薛蟠是男性 薛宝钗是女性 可推出新事实 薛王氏是贾宝玉的姨母 贾宝玉是薛蟠的表兄弟 贾宝玉是薛宝钗的表兄弟 在检查规则中某前提是否成立时 带变量的正向演绎与不带变量的正向演绎是有区别的 不带变量 检查该前提是否与已知事实相同 带变量 检查该前提是否与已知事实相匹配 当把该前提中的变量换成匹配中所获得的约束值时 它才与那个事实相同 我们说匹配成功 既建立了约束关系 并把建立的一组约束关系称为一个演绎环境 例如 第一个前提与事实库的四个事实匹配成功 建立了编号为1 2 3 4的四个环境 1 x 王夫人 y 贾宝玉 2 x 王夫人 y 贾元春 3 x 薛王氏 y 薛蟠 4 x 薛王氏 y 薛宝钗 为使用一条规则演绎 应使规则中的所有前提同时成立 即不同前提中的同名变量可以取到同一个约束值 实际上是说 各前提与事实相匹配中所获得的环境应当是相容的 应有一个公共的环境 满足各前提的要求 我们采用 累积 的方法寻找这一环境 当第一个前提获得四个环境 让第二个前提使用这些环境寻找与之相配的事实 于是 符合前两个前提的环境为1 3 1 x 王夫人 y 贾宝玉 3 x 薛王氏 y 薛蟠 第三个前提使用这两个环境寻找相匹配的事实 环境3不适合 使用环境1 增加了一个约束 扩充为环境5 5 x 王夫人 y 贾宝玉 z 薛王氏 最后 第四个前提使用环境5找到两个事实 环境5扩充为环境6和环境7 6 x 王夫人 y 贾宝玉 z 薛王氏 w 薛蟠 7 x 王夫人 y 贾宝玉 z 薛王氏 w 薛宝钗 这两个环境就是符合所有前提的公共环境 使用此环境 可得出新事实 薛王氏是贾宝玉的姨母 贾宝玉是薛蟠的表兄弟 和 薛王氏是贾宝玉的姨母 贾宝玉是薛宝钗的表兄弟 去掉重复 获得三条 有变量的反向推理变量与变量的匹配是在有变量的情况下进行反向推理时出现 给定一个断言 假定不含变量 在反向推理中 用它和规则的结论匹配 形成一个环境 规则前提的变量应从此环境取值 但是 前提中的变量在结论中可能不出现 这样 当前提作为新的未知断言 让它去和某规则的结论匹配时 就出现变量与变量的匹配 这种匹配正是我们在归结推理中讲的合一算法 只是算法的实现细节有所不同 在带变量的反向推理中 合一算法所得到的置换实现成约束表 对未匹配部分做置换通过对变量求 终值 而解决 算法的基本过程是一样的 参与合一的变量先在环境中取终值 无值则为本身 常量值为常量 双方为常量 相等则合一成功 否则失败 一方为变量 则建立约束关系 合一成功 双方为变量 建立约束关系 合一成功 在带变量的反向推理中 使用的搜索算法与归结推理方法相同 都是回溯算法 为了证明分支1 2 3都成立 可用1和规则I II III的结论合一 若使用规则1成功 而2搜索后失败 失败的原因可能是1给的环境不对 若1使用规则2成功 也许2也会成功 因此 分支失败回溯到 兄长 节点 而不是 父 节点 III123III4567 正向推理的缺点是有些盲目 求解了许多与总目标无关的子目标 反向推理的缺点是盲目选择目标 求解了许多可能为假的总目标 要是解空间较大 则更为明显 解决这些问题的有效办法 是综合利用正向推理与反向推理的优点 即正向推理帮助选择目标 再反向求解目标 这就是混合推理的思想 过程Alternate给出了这种策略的基本思想 3 2 4混合推理 ProcedureAlternateRepeat让用户将事实输入到数据库中 调用Respond 从已知事实出发演绎出部分结果 调用Choose Goal 选出一个目标G 调用Achieve G 确定目标G的真假性until问题被求解这是个原理示意程序 在实际应用中 有多种混合推理模式 语义网络形式上是一个有向图 由一组节点和若干条连接节点的弧构成 节点 表示一个问题领域的物体 概念 状态 弧 表示节点间的关系 常用的关系有分类关系 事物属性关系 推理关系等 分类 1 Subset of关系 子集关系 Subset ofSubset of 鸽子 鸟 动物 5 3语义网络 2 A Menber of关系 成员关系 A Menber of3 A Part of关系 部件关系 A Part of部件关系没有属性继承权 事物属性关系 黄色推理关系 infer 翅膀 鸟 白点 鸽子 中国人 黄色 下雪后 气温降低 语义网络是一种网络结构 节点之间的连接是二元关系 若表示一元关系 如张平是一个学生 作为谓词可是student zhangping 用语义网络可为 is a这就是说 语义网络很容易表示一元关系 Is a关系是Subset of关系 A Menber of关系和A Part of关系的一种通用的表示 Zhangping student 如果我们要表示的是多元关系 可以把这个多元关系转化成一组二元关系的组合 在转化中 需要引入附加节点 例如 03年足球甲A联赛 北京国安主场4比1战胜青岛 谓词表示SCORE 03甲A联赛 国安 青岛 4 1 用语义网络可表示为 主队IS A客队成绩图6 1多元关系的语义网络 03甲A联赛 国安 附加节点 青岛 4 1 推理网络的基本节点是事实或概念 而节点间的关系则表示规则 已证明 凡是用一阶谓词可表示的 用语义网络均可表示 在人工智能系统中 分类网络和推理网络也有较多的应用 分类网络的构造非常简单 每个节点代表一个概念 节点间的关系只有两种 子集关系和成员关系 子集关系连接中间节点 个体关系连接叶节点 整个网络一般呈树形 在语义网络上的推理主要是继承推理和匹配推理 继承推理就是通过继承关系得到某些个体的一些特征值 虽然 鸽子与翅膀之间没有连接 但鸽子是鸟的子集 翅膀是鸟的一个部分 因此 鸽子就继承了有翅膀这一特性 在语义网络中 匹配推理是指对于给定的事物或事实 构造一个语义网络片段 然后到已有的语义网络中去寻找在结构和细节相一致的对象 若能找到 则称二者匹配 使用推理网络 也可进行正向推理和反向推理 框架与语义网络一样 都是结构化表示法 实际上 我们可以把框架看成是由一组语义网络的节点和弧构成 只不过这些节点和弧描述的是格式固定的事物 行动和事件 语义网络注重表示对象间的关系 而框架更注重对象的内部结构 较典型的一种框架由描述对象的各个方面的槽组成 每个槽可有若干个侧面 每个侧面又可有若干个值 槽 侧面和值的多少要根据具体问题的具体需要来确定 5 4框架5 4 1框架的基本概念 框架名 槽名1 侧面1 值1 值2 值n 侧面2 侧面m 槽名2 槽名k 例 张平a member of学生身高1 78米体重70公斤爱好滑冰 击剑 下面是一个用LISP语言表示的框架结构 用框架表示 张平 a member of value 学生 身高 value 1 78米 体重 value 70公斤 爱好 value 滑冰 击剑 每个槽除了值侧面 value 以外 还可有一些其它的侧面 例如 1 默认 Default 侧面可有一个默认值2 需要 if needed 侧面当值侧面与默认侧面都没有值时 此侧面的求值结果作为该槽的值 如不知体重 对于成人 可以用身高减去1 1为其体重 1 增加 if added 侧面当一个槽的值侧面被赋值或修改时 这个槽 可继承 的增加侧面可自动求值 包括对其它槽的值侧面的赋值 例如 计算体重的过程可放在身高槽的if added侧面 修改身高时 既可重新计算体重 2 删除 if removed 侧面删除值侧面的一个值 3 约束 require 侧面是对槽的约束条件 对于框架有三条基本操作 1 提取信息给出 框架名 槽名 侧面名返回 侧面的值 1 存取信息给出 框架名 槽名 侧面名 值返回 1 如果找到框架名 槽名 侧面名 则把值放入2 找不到 则增加新的槽名 侧面名和值2 删除信息给出 框架名 槽名 侧面名 值返回 如果存在 则删除这个值 如果删除后 已无其它值 则连侧面也同时删除 框架的推理与语义网络类似 也是利用框架间的子集关系 成员关系 部件关系 使用继承和匹配进行推理 继承是把对事物的描述从概念框架或类框架传递到实例框架 常用的有三种继承 值继承 需要继承和默认继承 关于这三种继承的搜索也有几种方式 1 沿着父框架的槽 只搜索值侧面 相对应槽 2 沿着父框架的槽 第一次搜索值侧面 第二次搜索默认侧面 第三次再搜索需要侧面 3 沿着父框架的槽 一次就搜索值侧