人工智能及其应用知识.ppt

第二章知识表示 本章主要讨论知识表示问题 介绍7种知识表示方法 状态空间法 问题归约法 谓词演算法 语义网络法 框架表示 本体技术 过程表示 掌握状态空间法 问题归约法 谓词演算法 语义网络法的要点及其之间的关系 了解框架表示 本体技术 过程表示 知识表示的基本概念 知识表示 研究用机器表示知识的可行性 有效性的一般方法 是一种数据结构与控制结构的统一体 既考虑知识的存储又考虑知识的使用 知识表示可看成是一组描述事物的约定 以把人类知识表示成机器能处理的数据结构 人工智能系统所关心的知识 事实有关问题环境的一些事物的知识 常以 是 的形式出现 如事物的分类 属性 事物间关系 科学事实 客观事实等 如雪是白色的 鸟有翅膀 张三李四是好朋友 这辆车是张三的 规则有关问题中与事物的行动 动作相联系的因果关系知识 是动态的 常以 如果 那么 形式出现 控制有关问题的求解步骤 技巧性知识 告诉怎么做一件事 元知识有关知识的知识 是知识库中的高层知识 包括怎样使用规则 解释规则 校验规则 解释程序结构等知识 2 1状态空间法 问题求解问题求解 problemsolving 是个大课题 它涉及归约 推断 决策 规划 常识推理 定理证明和相关过程的核心概念 在分析了人工智能研究中运用的问题求解方法之后 就会发现许多问题求解方法是采用试探搜索方法的 也就是说 这些方法是通过在某个可能的解空间内寻找一个解来求解问题的 状态空间法 基于解答空间的问题表示和求解方法 它是以状态和算符 operator 为基础来表示和求解问题的 2 1状态空间法 1 问题求解技术两个主要的方面 1 问题的表示 如果描述方法不对 对问题求解会带来很大的困难 2 求解的方法 采用试探搜索方法 2 状态空间法三要点 1 状态 state 2 算符 operator 3 状态空间方法 2 1状态空间法 2 1 1问题状态描述1 定义状态 state 为描述某类不同事物间的差别而引入的一组最少变量q0 q1 qn的有序集合 其矢量形式如下 Q q0 q1 qn T式中每个元素qi i 0 1 n 为集合的分量 称为状态变量 给定每个分量的一组值就得到一个具体的状态 如Qk q0k q1k qnk T式中每个元素qi i 0 1 n 为集合的分量 称为状态变量 算符 使问题从一种状态变化为另一种状态的手段称为操作符或算符 操作符可为走步 过程 规则 数学算子 运算符号或逻辑符号等 问题的状态空间 statespace 是一个表示该问题全部可能状态及其关系的图 它包含三种说明的集合 即所有可能的问题初始状态集合S 操作符集合F以及目标状态集合G 可把状态空间记为三元状态 S F G 2 1状态空间法 2 状态空间表示详释让我们先用数码难题 puzzleproblem 来说明状态空间表示的概念 由15个编有1至15并放在4 4方格棋盘上的可走动的棋子组成 棋盘上总有一格是空的 以便可能让空格周围的棋子走进空格 这也可以理解为移动空格 图中绘出了两种棋局 即初始棋局和目标棋局 它们对应于该下棋问题的初始状态和目标状态 如何把初始棋局变换为目标棋局呢 问题的解答就是某个合适的棋子走步序列 如 左移棋子12 下移棋子15 右移棋子4 等等 2 1状态空间法 2 状态空间表示详释状态空间法 从某个初始状态开始 每次加一个操作符 递增的建立起操作符的试验序列 直到达到目标状态为止 寻找状态空间的全部过程包括从旧的状态描述产生新的状态描述 以及此后检验这些新的状态描述 看是否达到了该目标状态 对于最优化问题找到任一目标状态是不够的 必须按某个准则实现最优化路径 P26完成目标状态的三件事 状态描述方式 特别是初始状态描述 操作符集合及其对状态描述的作用 目标状态的特性 2 1状态空间法 2 1 2状态图示法为了对状态空间图有更深入的了解 这里介绍一下图论中的几个术语和图的正式表示法 1 图论中的几个术语节点 node 图形上的汇合点 用来表示状态 事件和时间关系的汇合 也可用来指示通路的汇合 弧线 arc 节点间的连接线 有向图 directedgraph 一对节点用弧线连接起来 从一个节点指向另一个节点 后继节点 descendantnode 与父辈节点 parentnode 如果某条弧线从节点ni指向节点nj 那么节点nj就叫做节点ni的后继节点或后裔 而节点ni叫做节点nj的父辈节点或祖先 2 1状态空间法 2 1 2状态图示法1 图论中的几个术语路径 某个节点序列 ni1 ni2 nik 当j 2 3 k时 如果对于每一个ni j 1都有一个后继节点nij存在 那么就把这个节点序列叫做从节点ni1至节点nik的长度为k的路径 代价 用c ni nj 来表示从节点ni指向节点nj的那段弧线的代价 两节点间路径的代价等于连接该路径上各节点的所有弧线代价之和 显式表示 各节点及其具有代价的弧线由一张表明确给出 此表可能列出该图中的每一节点 它的后继节点以及连接弧线的代价 隐式表示 节点的无限集合 si 作为起始节点是已知的 后继节点算符 也是已知的 它能作用于任一节点以产生该节点的全部后继节点和各连接弧线的代价 2 1状态空间法 2 1 2状态图示法2 图的显式和隐式表示一个图可由显式说明也可由隐式说明 显然 显式说明对于大型的图是不切实际的 而对于具有无限节点集合的图则是不可能的 此外 引入后继节点算符的概念是方便的 后继节点算符 也是已知的 它能作用于任一节点以产生该节点的全部后继节点和各连接弧线的代价把后继算符应用于 si 的成员和它们的后继节点以及这些后继节点的后继节点 如此无限制地进行下去 最后使得由 和 si 所规定的隐式图变为显示图 问题的表示对求解工作量有很大的影响 人们显然希望有较小的状态空间表示 许多似乎很难的问题 当表示适当时就可能具有小而简单的状态空间 2 1状态空间法 2 1 2状态图示法根据问题状态 操作符和目标条件选择各种表示 是高效率问题求解必须的 各种问题都可以用状态空间加以表示 并用状态空间搜索法来求解 2 1状态空间法 2 1 2状态图示法1 产生式系统 ProductionSystem 一个总数据库 globaldatabase 它含有与具体任务有关的信息 随着应用情况的不同 这些数据库可能小得像数字矩阵那样简单 或许大得如检索文件结构那么复杂 一套规则 它对数据库进行操作运算 每条规则由左右两部分组成 左部鉴别规则的适用性或先决条件 右部描述规则应用时所完成的动作 用规则来改变数据库就象用算符来改变状态一样 一个控制策略 它确定应该采用哪一条适用规则 而且当数据库的终止条件满足时 就停止计算 控制策略由控制系统选择和确定 推销员旅行问题 总数据库 到目前为止所访问的城市 规则对应于决策 即下一步走向城市 下一步走向城市 下一步走向城市 一条规则必须能把某个数据库变为一个合法数据库 否则不适应这个数据库 任一以 为起点和终点 并出现所有其它城市的总数据库 都满足终止条件 2 1状态空间法 2 1 2状态图示法2 状态空间表示举例例2猴子和香蕉问题 monkeyandbananaproblem 在一个房间内有一只猴子 可把这只猴子看做一个机器人 一个箱子和一束香蕉 香蕉挂在天花板下方 但猴子的高度不足以碰到它 那么这只猴子怎样才能摘到香蕉呢 图2 4表示出猴子 香蕉和箱子在房间内的相对位置 猴子和香蕉 用一个四元表列 W X Y Z 来表示这个问题的状态 其中W 猴子的水平位置X 当猴子在箱子顶上时取X 1 否则取X 0Y 箱子的水平位置Z 当猴子摘到香蕉时取Z 1 否则取Z 0图2 4猴子和香蕉问题 2 1状态空间法 2 1 2状态图示法这个问题中的操作 算符 如下 1 goto U 猴子走到水平位置U 或者用产生式规则表示为 W 0 Y z U 0 Y z 2 3 即应用操作goto U 能把状态 W 0 Y z 变换为状态 U 0 Y z 2 pushbox V 猴子把箱子推到水平位置V 即有 W 0 W z V 0 V z 2 4 应当注意的是 要应用算符pushbox V 就要求产生式规则的左边 猴子与箱子必须在同一位置上 并且 猴子不是在箱子顶上 这种强加于操作的适用性条件 叫做产生式规则的先决条件 2 1状态空间法 2 1 2状态图示法这个问题中的操作 算符 如下 3 climbbox猴子爬上箱顶 即有 W 0 W z W 1 W z 2 5 在应用算符climbbox时也必须注意到 猴子和箱子应当在同一位置上 而且猴子不在箱顶上 4 grasp猴子摘到香蕉 即有 c 1 c 0 c 1 c 1 2 6 其中 c是香蕉正下方的地板位置 在应用算符grasp时 要求猴子和箱子都在位置c上 并且猴子已在箱子顶上 2 1状态空间法 对于规则 2 只有当算符pushbox V 的先决条件 即猴子与箱子在同一位置上而且猴子不在箱顶上这些条件得到满足时 算符pushbox V 才是适用的 这一操作算符的作用是猴子把箱子推到位置V 在这一表示中 目标状态的集合可由任何最后元素为1的表列来描述 令初始状态为 a 0 b 0 这时 goto U 是唯一适用的操作 并导致下一状态 U 0 b 0 现在有3个适用的操作 即goto U pushbox V 和climbbox 若U b 猴子和香蕉问题的状态空间图 2 2问题归约法 2 2 1问题归约描述先把问题分解为子问题和子 子问题 然后解决较小的问题 对该问题的某个具体子集的解答就意味着对原始问题的一个解答 问题归约表示的组成部分 一个初始问题描述 一套把问题变换为子问题的操作符 一套本原问题描述 问题归约的实质 从目标 要解决的问题 出发逆向推理 建立子问题以及子问题的子问题 直至最后把初始问题归约为一个平凡的本原问题集合 2 2问题归约法 2 2 1问题归约描述 梵塔难题有3个柱子 1 2和3 和3个不同尺寸的圆盘 A B和C 在每个圆盘的中心有一个孔 所以圆盘可以堆叠在柱子上 最初 3个圆盘都堆在柱子1上 最大的圆盘C在底部 最小的圆盘A在顶部 要求把所有圆盘都移到柱子3上 每次只许移动一个 而且只能先搬动柱子顶部的圆盘 还不许把尺寸较大的圆盘堆放在尺寸较小的圆盘上 这个问题的初始配置和目标配置如图2 6所示 2 2问题归约法 解题过程 将原始问题归约为一个较简单问题集合 要把所有圆盘都移至柱子3 我们必须首先把圆盘C移至柱子3 而且在移动圆盘C至柱子3之前 要求柱子3必须是空的 只有在移开圆盘A和B之后 才能移动圆盘C 而且圆盘A和B最好不要移至柱子3 否则就不能把圆盘C移至柱子3 因此 首先应该把圆盘A和B移到柱子2上 然后才能够进行关键的一步 把圆盘C从柱子1移至柱子3 并继续解决难题的其余部分 将原始难题归约 简化 为下列子难题 移动圆盘A和B至柱子2的双圆盘难题 如图 a 所示 2 2问题归约法 图2 7梵塔问题解答 a 图2 8梵塔问题解答 b 图2 9梵塔问题解答 c 2 2问题归约法 梵塔问题归约图 子问题2可作为本原问题考虑 因为它的解只包含一步移动 应用一系列相似的推理 子问题1和子问题3也可被归约为本原问题 如图2 10所示 这种图式结构 叫做与或图 AND ORgraph 它能有效地说明如何由问题归约法求得问题的解答 梵塔问题归约图 2 2问题归约法 2 2 1问题归约描述 问题归约描述问题归约方法应用算符把问题描述变换为子问题描述 问题描述可以用多种数据结构形式 包括表列 树 字符串 矢量 数组等 梵塔问题采用包含两个数列的表列来描述 113 333 表示把配置 113 变换为配置 333 用状态空间表示的三元组合 S F G 来规定与描述问题 有关子问题可以当作状态空间中的两个一定的 脚踏石 之间寻找路径来辨别 梵塔问题中的子问题 111 122 122 322 322 333 规定了最后的路径将要通过 脚踏石 状态 122 和 322 2 2问题归约法 2 2 2与或图表示与图 或图 与或图 一般地 我们用一个类似图的结构来表示把问题归约为后继问题的替换集合 这种结构图叫做问题归约图 或叫与或图 如下图所示 引入附加节点使含有一个以上后继问题的每个集合能够聚集在它们各自的父辈节点之下 子问题替换集合结构图 与或图 2 2问题归约法 2 2 2问题归约描述一些关于与或图的术语 终叶节点 对应于原问题的本原节点 或节点 只要解决某个问题就可解决其父辈问题的节点集合 如 M N H 与节点 只有解决所有子问题 才能解决其父辈问题的节点集合 如 B C 和 D E F 各个结点之间用一端小圆弧连接标记 2 2问题归约法 2 2 2问题归约描述与或图 由与节点及或节点组成的结构图 可解节点的一般定义 1 终叶节点是可解节点 因为它们与本原问题相关连 2 如果某个非终叶节点含有或后继节点 那么只要当其后继节点至少有一个是可解的时 此非终叶节点才是可解的 3 如果某个非终叶节点含有与后继节点 那么只有当其后继节点全部为可解时 此非终叶节点才是可解的 图2 15与或图例子 2 2问题归约法 2 2 2问题归约描述不可解节点的一般定义 1 没有后裔的非终叶节点为不可解节点 2 如果某个非终叶节点含有或后继节点 那么只有当其全部后裔为不可解时 此非终叶节点才是不可解的 3 如果某个非终叶节点含有与后继节点 那么只要当其后裔至少有一个为不可解时 此非终叶节点才是不可解的 2 2问题归约法 2 2 2问题归约描述与或图构成规则 1 与或图中的每个节点代表一个要解决的单一问题或问题集合 图中所含起始节点对应于原始问题 2 对应于本原问题的节点 叫做终叶节点 它没有后裔 3 对于把算符应用于问题A的每种可能情况 都把问题变换为一个子问题集合 有向弧线自A指向后继节点表示所求得的子问题集合 如下图所示 把问题A归约为3个不同的子问题集合N M H 或节点 图2 16与或树 2 2问题归约法 2 2 2问题归约描述与或图构成规则 4 一般对于代表两个或两个以上子问题集合的每个节点 有向弧线从此节点指向此子问题集合中的各个节点 由于只有当集合中所有的项都有解时 这个子问题的集合才能获得解答 所以这些子问题节点叫做与节点 5 在特殊情况下 当只有一个算符可应用于问题A 而且这个算符产生具有一个以上子问题的某个集合时 由上述规则3和规则4所产生的图可以得到简化 因此 代表子问题集合的中间或节点可以被略去 如右图所示 图2 16与或树 2 3谓词逻辑法 2 3 1谓词演算 PredicateCalculus 1 语法和语义 Syntax Semantics 谓词逻辑的基本组成部分 谓词符号 变量符号 函数符号和常量符号 并用圆括号 方括号 花括号和逗号隔开 表示论域内的关系 原子公式 atomicformulas 由若干谓词符号和项组成的谓词演算 原子公式是谓词演算基本积木块 例如 要表示 机器人 ROBOT 在 号房间 r1 内 如图2 19所示 可以应用原子公式 2 3谓词逻辑法 2 3 1谓词演算 PredicateCalculus 1 语法和语义 Syntax Semantics 当机器人ROBOT移到房间r2时 原子公式可以表示为 INROOM ROBOT r2 这两个原子公式的通用形式就是又如 李的母亲和他的父亲结婚 这句话的原子公式表示如下 2 3谓词逻辑法 2 3 1谓词演算 PredicateCalculus 2 连词和量词 Connective Quantifiers 1 连词与 合取 conjunction 合取就是用连词 把几个公式连接起来而构成的公式 合取项是合取式的每个组成部分 例 LIKE I MUSIC LIKE I PAINTING 我喜爱音乐和绘画 2 3谓词逻辑法 2 3 1谓词演算 PredicateCalculus 2 连词和量词 Connective Quantifiers 或 析取 disjunction 析取就是用连词 把几个公式连接起来而构成的公式 析取项是析取式的每个组成部分 例 PLAYS LILI BASKETBALL PLAYS LILI FOOTBALL 李力打篮球或踢足球 2 3谓词逻辑法 2 3 1谓词演算 PredicateCalculus 2 连词和量词 Connective Quantifiers 1 连词蕴涵 表示 如果 那么 的语句 用连词 连接两个公式所构成的公式叫做蕴涵 IF THEN前项后项 左式 右式 例 RUNS LIUHUA FASTEST TWINS LIUHUA CHAMPION 如果刘华跑得最快 那么他取得冠军 非 NOT 表示否定 均可表示否定 例 INROOM ROBOT r2 机器人不在2号房间内 2 3谓词逻辑法 2 3 1谓词演算 PredicateCalculus 2 连词和量词 Connective Quantifiers 2 量词全称量词 UniversalQuantifier 若一个原子公式P x 对于所有可能变量x都具有T值 则用 x P x 表示 例 x ROBOT x COLOR x GRAY 所有的机器人都是灰色的 x Student x Uniform x Color 所有学生都穿彩色制服 2 3谓词逻辑法 2 3 1谓词演算 PredicateCalculus 2 连词和量词 Connective Quantifiers 2 量词存在量词 ExistentialQuantifier 若一个原子公式P x 至少有一个变元X 可使P X 为T值 则用 x P x 表示 例 x INROOM x r1 1号房间内有个物体 量化变元 QuantifiedVariables 被量化了的变元x 约束变量 2 3谓词逻辑法 2 3 2谓词公式 PredicateFormulas 1 谓词公式的定义原子谓词公式 用P x1 x2 xn 表示一个n元谓词公式 其中P为n元谓词 x1 x2 xn为客体变量或变元 通常把P x1 x2 xn 叫做谓词演算的原子公式 或原子谓词公式 分子谓词公式 可以用连词把原子谓词公式组成复合谓词公式 并把它叫做分子谓词公式 合适公式 WFF well formedformulas 的递归定义 1 原子谓词公式是合适公式 2 若A为合适公式 则 A也是一个合适公式 3 若A和B都是合适公式 则 A B A B A B A B 也都是合适公式 4 若A是合适公式 x为A中的自由变元 则 x A x A都是合适公式 5 只有按上述规则 1 至 4 求得的那些公式 才是合适公式 2 3谓词逻辑法 2 3 2谓词公式 PredicateFormulas 1 谓词公式的定义例题 对于所有的x 如果x是整数 则x或为正的或者为负的 x I x P x N x I x 表示 x是整数 P x 表示 x是正数 N x 表示 x是负数 2 3谓词逻辑法 2 3 2谓词公式 PredicateFormulas 2 合适公式的性质合适公式的真值 p36表2 1真值表 2 3谓词逻辑法 2 3 3置换与合一 Substitution Unification 1 置换在谓词逻辑中 有些推理规则可应用于一定的合适公式和合适公式集 以产生新的合适公式 一个重要的推理规则是假元推理 这就是由合适公式W1和W1 W2产生合适公式W2的运算 另一个推理规则叫做全称化推理 它是由合适公式 x W x 产生合适公式W A 其中A为任意常量符号 假元推理 全称化推理 综合推理 2 3谓词逻辑法 2 3 3置换与合一 Substitution Unification 1 置换置换 用项 A 替换函数表达式中的变量 x 记为ES 即表示一个表达式E Expression 用一个置换S Substitution 而得到的表达式的置换 例1表达式P x f y B 的4个置换为s1 z x w y s2 A y s3 q z x A y s4 c x A y 我们用Es来表示一个表达式E用置换s所得到的表达式的置换 于是 我们可得到P x f y B 的4个置换的例 如下 P x f y B s1 P z f w B P x f y B s2 P x f A B P x f y B s3 P q z f A B P x f y B s4 P c f A B 2 3谓词逻辑法 2 3 3置换与合一 Substitution Unification 2 性质可结合律 LS1 S2 L S1S2 L表示一表达式 S1S2 S3 S1 S2S3 置换是可结合的 用s1s2表示两个置换s1和s2的合成 L表示一表达式 则有 Ls1 s2 L s1s2 以及 s1s2 s3 s1 s2s3 即用s1和s2相继作用于表达式L是同用s1s2作用于L一样的 一般说来 置换是不可交换的 即s1s2 s2s13 合一 unification P38合一 寻找项对变量的置换 以使两表达式一致 可合一 如果一个置换s作用于表达式集 Ei 的每个元素 则我们用 Ei s来表示置换例的集 我们称表达式集 Ei 是可合一的 2 3谓词逻辑法 2 3 3置换与合一 Substitution Unification 例 表达式集P x f y B P x f B B 的合一者为 s A x B y 因为P x f y B s P x f B B P A f B B 即s使表达式成为单一形式 P A f B B 但最简单的合一者为 s B Y 2 4语义网络法 语义网络是1968年Quilian在研究人类联想记忆时提出的心理学模型 认为记忆是由概念间的联系来实现的 1972年 Simmons首先将语义网络表示法用于自然语言理解系统 语义网络的结构 语义网络是知识的一种图解表示 它由节点和弧线或链线组成 节点用于表示实体 概念和情况等 弧线用于表示节点间的关系 组成部分 1词法部分 决定表示词汇表中允许有哪些符号 它涉及各个节点和弧线 2结构部分 叙述符号排列的约束条件 指定各弧线连接的节点对 3过程部分 说明访问过程 这些过程能用来建立和修正描述 以及回答相关问题 4语义部分 确定与描述相关的 联想 意义的方法即确定有关节点的排列及其占有物和对应弧线 2 4语义网络法 2 4 1二元语义网络的表示 RepresentationofTwo ElementSemanticNetwork 1 表示简单的事实例1 所有的燕子都是鸟 2 4语义网络法 2 4 1二元语义网络的表示 RepresentationofTwo ElementSemanticNetwork 2 表示占有关系和其它情况P40例2 小燕是一只燕子 燕子是鸟 巢 1是小燕的巢 巢 1是巢中的一个 3 选择语义基元试图用一组基元来表示知识 以便简化表示 并可用简单的知识来表示更复杂的知识 2 4语义网络法 例3 我椅子的颜色是咖啡色的 椅子包套是皮革 椅子是一种家具 椅子是座位的一部分 椅子的所有者是X X是个人 如下图所示 2 4语义网络法 2 4 2多元语义网络的表示语义网络是一种网络结构 节点之间以链相连 多元语义网络表示的实质 把多元关系转化为一组二元关系的组合 或二元关系的合取 如果所要表示的知识是一元关系 例如 要表示李明是一个人 这在谓词逻辑中可表示为MAN LIMING 用语义网络 这就可以表示为 与这样的表示法相等效的关系在谓词逻辑中表示为ISA LIMING MAN 这说明语义网络可以毫无困难地表示一元关系 2 4语义网络法 例如 要表达北京大学 BEIJINGUniversity 简称BU 和清华大学 TSINGHUAUniversity 简称TU 两校篮球队在北大进行的一场比赛的比分是85比89 若用谓词逻辑可表示为SCORE BU TU 85 89 这个表示式中包含3项 而语义网络从本质上来说 只能表示二元关系 解决这个矛盾的一种方法是把这个多元关系转化成一组二元关系的组合 或二元关系的合取 具体来说 多元关系R X1 X2 Xn 总可以转换成R1 X11 X12 R2 X21 X22 Rn Xn1 Xn2 图2 20多元关系的语义网络表示 2 4语义网络法 2 4 3语义网络的推理过程在语义网络知识表达方法中 赋予网络结构的含义完全决定于管理这个网络的过程的特性 为了便于以下的叙述 对所用符号作进一步的规定 区分在链的头部和在链的尾部的节点 把在链的尾部的节点称为值节点 另外 我们还规定节点的槽相当于链 不过取不同的名字而已 在图2 28中砖块12 BRICK12 有3个链 构成两个槽 其中一个槽只有一个值 另外一个槽有两个值 我们说颜色槽 COLOR 填入红色 RED ISA槽填入了砖块 BRICK 和玩具 TOY 图2 28语义网络的槽和数值 2 4语义网络法 2 4 3语义网络的推理过程语义网络中的推理过程主要有两种 一种是继承 另一种是匹配 以下我们分别介绍这两种过程 1 继承在语义网络中所谓的继承是把对事物的描述从概念节点或类节点传递到实例节点 例如在图2 29上所示的语义网络中BRICK是概念节点 BRICK12是一个实例节点 BRICK节点在SHAPE 外形 槽 其中填入了RECTANGULAR 矩形 说明砖块的外形是矩形的 这个描述可以通过ISA链传递给实例节点BRICK12 因此 虽然BRICK12节点没有SHAPE槽 但可以从这个语义网络推理出BRICK12的外形是矩形的 图2 29语义网络的值继承 2 4语义网络法 2 4 3语义网络的推理过程1 继承这种推理过程 类似于人的思维过程 一旦知道了某种事物的身份以后 可以联想起很多关于这件事物的一般描述 例如 我们通常认为鲸鱼很大 鸟比较小 城堡很古老 运动员很健壮 这就像我们用每种事物的典型情况来描述各种事物 鲸鱼 鸟 城堡和运动员 那样 一共有3种继承过程 值继承 如果需要 继承和 默认 继承 2 4语义网络法 2 4 3语义网络的推理过程语义网络中的推理过程主要有两种 一种是继承 另一种是匹配 以下我们分别介绍这两种过程 1 继承 1 值继承除了ISA链以外 另外还有一种AKO 是某种 链也可被用于语义网络中的描述或特性的继承 AKO是A KIND OF的缩写 总之 ISA和AKO链直接地表示类的成员关系以及子类和类之间的关系 提供了一种把知识从某一层传递到另一层的途径 为了能利用语义网络的继承特性进行推理我们还需要一个搜索程序用来在合适的节点寻找合适的槽 2 4语义网络法 2 4 3语义网络的推理过程1 继承 2 如果需要 继承在某些情况下 当我们不知道槽值时 可以利用已知信息来计算 例如 我们可以根据体积和物质的密度来计算积木的重量 进行上述计算的程序称为if needed 如果需要 程序 为了储存进行上述计算的程序 我们需要改进节点槽值的结构 允许槽有几种类型的值 而不只是一个类型 为此 每个槽又可以有若干个侧面 以储存这些不同类型的值 这样 以前我们讨论的原始意义上的值就放 值侧面 中 if needed程序 存放在IF NEEDED侧面中 例如在图2 30 a 中 一个重量确定程序存放在BLOCK节点的WEIGHT槽的IF NEEDED侧面中 图2 30语义网络的 如果需要 继承 2 4语义网络法 2 4 3语义网络的推理过程1 继承 3 缺省 继承某些情况下 当我们对事物所作的假设不是十分有把握时 最好对所作的假设加上 可能 这样的字眼 例如 我们可以认为法官可能是诚实的 但不一定是 或认为宝石可能是很昂贵的 但不一定是 我们把这种具有相当程度的真实性 但又不能十分肯定的值称为 缺省 值 这种类型的值被放入槽的DEFAULT 缺省 侧面中 例如 在图2 31中 网络所表示的含义是 从整体来说 积木的颜色很可能是蓝色的 但在砖块中 颜色可能是红的 对BLOCK和BRICK节点来说 在COLOR槽中找到的侧面都是DEFAULT侧面 在图中以括弧加以标志 图2 31语义网络的 缺省 继承 2 4语义网络法 2 4 3语义网络的推理过程2 匹配至今我们所讨论的是类节点和实例节点 例如BRICK和BRICK12之间的继承值 现在我们转向讨论更为困难一些的问题 当解决涉及由几部分组成的事物时 如图2 32中的玩具房 TOY HOUSE 和玩具房 77 TOY HOUSE77 继承过程将如何进行 我们不仅必须制定如何把值从玩具房传递到玩具房 77的路径 而且必须制定把值从玩具房部件传递到玩具房 77部件的路径 例如 很明显 由于TOY HOUSE77是TOY HOUSE的一个实例 所以它必须有两个部件 一个是砖块 另一个是楔块 wedge 另外 作为玩具房的一个部件的砖块必须支撑楔块 在图2 32中 玩具房 77部件以及它们之间的链 都用虚线画的节点的箭头来表示 因为这些知识是通过继承而间接知道的 并不是通过实际的节点和链直接知道的 因此 我们说虚线所表示的节点和箭头表示的链是虚节点和虚链 图2 32虚节点和虚链 图2 32虚节点和虚链 没有必要从TOYHOUSE节点把这些节点和链复制到TOY HOUSE77节点去 除非我们需要在这些复制节点加上玩具房 77所特有的信息 例如 如果我们要表示玩具房 77的砖块的颜色是红的 就必须为TOY HOUSE77建立一个BRICK节点 并把RED放在这个BRICK节点的COLOR槽中 假设我们把RED放在作为玩具房部件的BRICK节点的COLOR槽中 这将意味着所有玩具房的砖都是红色的 而不是只在由玩具房 77所描述的特定房子中的砖是红色的 2 4语义网络法 2 4 3语义网络的推理过程现在我们来研究图2 33中的结构35 STRUCTURE35 已知这个结构有两个部件 一个砖块BRICK12和一个楔块WEDGE18 一旦在STRUCTURE35和TOY HOUSE之间放上ISA链 我们就知道BRICK12必须支撑WEDGE18 在图2 18上用虚线箭头表示BRICK12和WEDGE18之间的SUPPORT虚链 因为很容易做部件匹配 所以虚线箭头的位置和方向很容易确定 WEDGE18肯定和作为TOY HOUSE的一个部件的楔块相匹配 而BRICK12肯定和砖块相匹配 图2 33部件匹配 2 5框架表示法 心理学的研究结果表明 在人类日常的思维和理解活动中 当分析和解释遇到的新情况时 要使用到过去经验中积累的知识 这些知识规模巨大而且以很好的组织形式保留在人们的记忆中 例如 当我们走进一家从来没来过的饭店时 根据以往的经验 可以预见在这家饭店我们将会看到菜单 桌子 服务员等等 当我们走进教室时 可以预见在教室里可以看到椅子 黑板等等 我们试图用以往的经验来分析解释当前所遇到的情况 2 5框架表示法 当然 我们无法把过去的经验一一都存在脑子里 而只能以一个通用的数据结构的形式存储以往的经验 这样的数据结构称为框架 框架提供了一个结构 一种组织 在这个结构或组织中 新的资料可以用从过去的经验中得到的概念来分析和解释 因此 框架是一种结构化表示法 通常框架采用语义网络中的节点 槽 值表示结构 所以框架也可以定义为是一组语义网络的节点和槽 这组节点和槽可以描述格式固定的事物 行动和事件 语义网络可看做节点和弧线的集合 也可以视为框架的集合 2 5框架表示法 2 5 1框架的构成框架通常由描述事物的各个方面的槽组成 每个槽可以拥有若干个侧面 而每个侧面又可以拥有若干个值 这些内容可以根据具体问题的具体需要来取舍 一个框架的一般结构如下 2 5框架表示法 2 5 1框架的构成较简单的情景是用框架来表示诸如人和房子等事物 例如 一个人可以用其职业 身高和体重等项描述 因而可以用这些项目组成框架的槽 当描述一个具体的人时 再用这些项目的具体值填入到相应的槽中 表2 3给出的是描述John的框架 对于大多数问题 不能这样简单地用一个框架表示出来 必须同时使用许多框架 组成一个框架系统 表2 3简单框架示例JOHN的描述框架 2 5框架表示法 一个框架系统图2 32所示的就是表示立方体的一个视图的框架 图中 最高层的框架 用isa槽说明它是一个立方体 并由region槽指示出它所拥有的3个可见面A B E 而A B E又分别用3个框架来具体描述 用mustbe槽指示出它们必须是一个平行四边形 图2 32一个立体视图的框架表示 2 5框架表示法 一个框架系统为了能从各个不同的角度来描述物体 可以对不同角度的视图分别建立框架 然后再把它们联系起来组成一个框架系统 图2 35所示的就是从3个不同的角度来研究一个立方体的例子 为了简便起见 图中略去了一些细节 在表示立方体表面的槽中 用实线与可见面连接 用虚线与不可见面连接 图2 35表示立方体的框架系统 2 5框架表示法 以下是另一个框架系统的例子 今天一次强度为里氏8 5级的强烈地震袭击了下斯洛文尼亚 LowSlabovia 地区 造成25人死亡和5亿美元的财产损失 下斯洛文尼亚地区主席说 多年来 靠近萨迪豪金斯断层的重灾区一直是一个危险地区 可以用图2 36中虚线部分所示的EARTHQUAKE13框架来表示这一新闻 图2 36表示灾害事件的框架系统 图中在链上标明的地点 place 日期 day 伤亡 fatalities 损失 damage 震级 magnitude 断层 fault 是槽的名称 在节点中填入相应的填充值 这个框架可以发展成框架系统 以描述更复杂更广泛的事件 例如 向上移动一层的话 可以把地震看成是一种灾害事件 disasterevent 除此之外还可以有洪水 flood 飓风 huricane 等灾害事件 它们组成一个DISASTEREVENT的基本框架 如向下移动一层 在每个槽中也可以填入一个框架 例如FATALITIES 也可以用一个框架来描述 2 5框架表示法 显而易见 这种框架系统具有树状结构 树状结构框架系统的每个节点具有如下框架结构形式 框架名AKOVALUEPROPDEFAULTSFIF NEEDEDCONFLICTADD其中框架名用类名表示 AKO是一个槽 VALUE是它的侧面 通过填写的内容表示出该框架属于哪一类 PROP槽用来记录该节点所具有的特性 其侧面DEFAULT表示该槽的内容是可以进行缺省继承的 即当为非NIL时 PROP的槽值为 当为NIL时 PROP的槽值用其父节点的PROP槽值来代替 2 5框架表示法 2 5 2框架的推理框架是一种复杂结构的语义网络 因此语义网络推理中的匹配和特性继承在框架系统中也可以实行 除此以外 由于框架用于描述具有固定格式的事物 动作和事件 因此可以在新的情况下 推论出未被观察到的事实 框架用以下几种途径来帮助实现这一点 1 框架包含它所描述的情况或物体的多方面的信息 这些信息可以被引用 就像已经直接观察到这些信息一样 2 框架包含物体必须具有的属性 在填充框架的各个槽时 要用到这些属性 3 框架描述它们所代表的概念的典型事例 如果某一情况在很多方面和一个框架相匹配 只有少部分相互之间存在不同之处 这些不同之处很可能对应于当前情况的重要方面 也许应该对这些不同之处作出解答 因此 如果一个椅子被认为应有4条腿 而某一椅子只有3条腿 那么或许这把椅子需要修理 2 5框架表示法 2 5 2框架的推理用一个框架来具体体现一个特定情况的过程 经常不是很顺利的 但当这个过程碰到障碍时 经常不必放弃原来的努力去从头开始 而是有很多办法可想的 1 选择和当前情况相对应的当前的框架片断 并把这个框架片断和候补框架相匹配 选择最佳匹配 如果当前的框架 总的来说差不多是可以接受的 则许多已经做的 有关建立子结构以填入这个框架的工作将可保留 2 尽管当前的框架和要描述的情况之间有不相匹配的地方 但是仍然可以继续应用这个框架 例如 所研究的只有3条腿的椅子 可能是一个破椅子或是有另一个在椅子前面的物体挡住了一条腿 框架的某一部分包含关于哪些特性是允许不相匹配的信息 同样的 也有一般的启发性原则 比如一个漏失某项期望特性的框架 可能由于被挡住视线造成的 比另一个多了某一项不应有的特性的框架更适合当前的情况 举例来说 一个人只有一条腿比说一个人有3条腿或有尾巴更合乎情理些 2 5框架表示法 2 5 2框架的推理 3 查询框架之间专门保存的链 以提出应朝哪个方向进行试探的建议 这种链的例子与图2 35所示网络相似 例如 如果和CHAIR框架匹配时 发现没有靠背 并且太宽 这时就建议用BENCH 条凳 框架 如果太高 并且没有靠背 就建议用STOOL 凳子 框架 图2 37相似网络 2 5框架表示法 2 5 2框架的推理 4 沿着框架系统排列的层次结构向上移动 即从狗框架 哺乳动物框架 动物框架 直到找到一个足够通用 并不与已有事实矛盾的框架 如果框架足够具体 可以提供所要求的知识 那就采用这个框架 或者建立一个新的 正好在匹配的框架下一层的框架 2 6剧本 script 表示 剧本是框架的一种特殊形式 它用一组槽来描述某些事件的发生序列 就像剧本中的事件序列一样 故称为 剧本 2 6 1剧本的构成一个剧本一般由以下各部分组成 1 开场条件给出在剧本中描述的事件发生的前提条件 2 角色用来表示在剧本所描述的事件中可能出现的有关人物的一些槽 3 道具这是用来表示在剧本所描述的事件中可能出现的有关物体的一些槽 4 场景描述事件发生的真实顺序 可以由多个场景组成 每个场景又可以是其它的剧本 5 结果给出在剧本所描述的事件发生以后通常所产生的结果 2 6剧本 script 表示 剧本是框架的一种特殊形式 它用一组槽来描述某些事件的发生序列 就像剧本中的事件序列一样 故称为 剧本 2 6 1剧本的构成下面以餐厅剧本为例说明剧本各个部分的组成 1 开场条件 a 顾客饿了 需要进餐 b 顾客有足够的钱 2 角色顾客 服务员 厨师 老板 3 道具食品 桌子 菜单 钱 2 6剧本 script 表示 2 6 1剧本的构成 4 场景场景1进入餐厅 a 顾客走入餐厅 b 寻找桌子 c 在桌子旁坐下 场景2点菜 a 服务员给顾客菜单 b 顾客点菜 c 顾客把菜单还给服务员 d 顾客等待服务员送菜 场景3等待 a 服务员把顾客所点的菜告诉厨师 b 厨师做菜 场景4吃菜 a 厨师把做好的菜给服务员 b 服务员给顾客送菜 c 顾客吃菜 场景5离开 a 服务员拿来帐单 b 顾客付钱给服务员 c 顾客离开餐厅 2 6剧本 script 表示 2 6 1剧本的构成 5 结果 a 顾客吃了饭 不饿了 b 顾客花了钱 c 老板挣了钱 d 餐厅食品少了 2 6剧本 script 表示 2 6 2剧本的推理剧本是有用的知识表达结构 因为在现实世界中事件发生的某种模式来自事件之间的因果关系 事件中的主人公完成一个动作后才能完成另一个动作 剧本中所描述的事件形成一个巨大的因果链 这个链的起点是一组开场条件 满足这些开场条件 剧本中的事件才能产生 链的终点是一组结果 有了这组结果 以后的事件或事件序列 可能用其他的剧本来描述 才能发生 在这个链内一件事情和前后的事情都相互联系 前面的事件 使当前的事件有可能产生 而当前事件又使后面的事件有可能产生 2 6剧本 script 表示 2 6 2剧本的推理如已知某一剧本适用于所给定的情形 剧本在预言一些没有直接提到的事件方面特别有用 同时剧本对表示已经提到的事件之间的关系也很有用 例如 要表示某人点了炖牛肉这道菜和此人吃牛肉之间是什么联系 就可以利用剧本 但在应用某一剧本以前 必须先准备好剧本 也就是先要确定这个剧本适用于当前的情形 根据剧本的重要性 可以有二种准备剧本的方法 1 对于不属于事件核心部分的剧本 只需设置指向该剧本的指针即可 以便当它成为核心时启用 如对于餐厅剧本 在下述事件中应采用这种方法 苏珊在去博物馆的路上经过她喜欢的餐厅 她非常喜欢这次的毕加索作品展览会 2 对于符合事件核心部分的剧本 则应使用在当前事件中涉及到的具体对象和人物去填写剧本的槽 剧本的前提 道具 角色和事件等常能起到启用剧本的指示器的作用 一旦剧本被启用 则可以应用它来进行推理 其中最重要的是运用剧本可以预测没有明显提及的事件的发生 2 6剧本 script 表示 2 6 2剧本的推理例如 对于以下情节 昨晚 约翰到了餐厅 他订了牛排 当他要付款时发现钱已用光 因为开始下雨了 所以他赶紧回家了 如果有人提问 昨晚 约翰吃饭了吗 虽然在上面的情节中并没有提到约翰吃没吃饭的问题 但借助于餐厅剧本 可以回答 他吃了 这是因为启用了餐厅剧本 情节中的所有事件与剧本中所预测的事件序列相对应 因而可以推断出整个事件正常进行时所得出的结果 但是 一旦一个典型的事件被中断 也就是给定情节中的某个事件与剧本中的事件不能对应时 则剧本便不能预测被中断以后的事件了 2 6剧本 script 表示 2 7 2剧本的推理例如如下情节 约翰走进餐厅 他被带到餐桌旁 订了一大块牛排之后 他坐在那儿等了许久 于是 他生气地走了 该情节中 因为要久等 所以约翰走了 这一事件改变了餐厅剧本中所预测的事件序列 因而被中断了 这时就不能推断约翰是否付了帐等情节 但仍然可以推断出他看了菜单 这是因为看菜单事件发生在中断之前 从该例也可以看出 利用剧本可以将事情的注意力集中在 因为久等 约翰生气了 这样一些特殊事件的发生上 剧本结构 比起框架这样的一些通用结构来 要呆板得多 知识表达的范围也很窄 因此不适用于表达各种知识 但对于表达预先构思好的特定知识 如理解故事情节等 是非常有效的 2 7过程 procedure 表示 过程式表示就是将有关某一问题领域的知识 连同如何使用这些知识的方法 均隐式地表达为一个求解问题的过程 过程式不像陈述式那样具有固定的形式 如何描述知识完全取决于具体的问题 下面以八数码问题为例 给出一种求解该问题的过程式描述 我们用一个3 3的方格阵来表示该问题的一个状态 为叙述上的方便 我们用a i来标记这9个方格 如图2 38 a 所示 问题的目标状态设定为图2 38 b 当任意给定一初始状态后 求解该问题的过程如下 图2 38状态的描述及其目标状态 2 7过程 procedure 表示 1 首先移动棋牌 使得棋子1和空格均不在位置c上 2 依次移动棋牌 使得空格位置沿图2 39 a 所示的箭头方向移动 直到棋子1位于a为止 3 依次移动将牌 使得空格位置沿图2 39 b 所示的箭头方向移动 直到数码2位于b为止 若这时刚好数码3在位置c 则转 6 图2 39空格移动方向示意图 2 7过程 procedure 表示 4 依次移动将牌 使得空格位置沿图2 39 c 所示的箭头方向移动 直到数码3位于e为止 这时空格刚好在位置d 2 7过程 procedure 表示 7 依次移动将牌 使得空格位置沿图2 39 f 所示的箭头方向移动 直到数码5位于e为止 这时空格刚好在位置d 8 依次移动将牌 使得空格位置沿图2 39 g 所示的箭头方向移动 直到空格又回到位置d为止 9 依次移动将牌 使得空格位置沿图2 39 h 所示的箭头方向移动 直到数码6在位置h为止 若这时数码7 8分别在位置g和d 则问题得解 否则 说明由所给初