人工智能知识表示.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 动物是食肉动物 （前提结论）,控制系统是规则的解释程序，它规定了如何选择一条可用的规则的原则(搜索策略)和规则使用的方式(推理方向)，并根据综合数据库的信息，控制求解问题的过程。,Precedure Respond 扫描数据库，找到可用规则集S； while S 非空且问题未被求解do begin 调用过程select-Rule（S），从S中选出规则R； 执行R的结果部分，更新数据库的内容； 扫描数据库，找到可用规则集S end,5.2.1 推理方式,正向推理 正向推理的基本思想是从已知数据信息出发，正向使用规则（让规则的前提与数据库匹配）求解问题。它要求用户首先输入有关当前问题的信息作为数据库中的事实。下述的过程Respond是这种策略的基本思想。,正向推理的主要缺点是激活规则表面看无目的，或者说系统为达到目标可能执行若干无用动作。,规则“可用”是指数据库中有满足该规则的条件部分的事实，过程select-Rule负责选择规则，与问题有关的控制信息在此体现，可使用评价函数，也可精心排序。,过程Respond是原理示意程序，实际系统要复杂的多，例如：如何查找规则？是顺序，还是索引。如何判断规则可用？是简单匹配、比较，还是计算。,正向推理就是执行“识别动作”。,正向推理的主要优点是允许用户主动提供有用的事实信息，而不必等到用户需要时才提供。它适合于“解空间”很大的一类问题，象设计、规划、预测、监控、管理等。,反向推理的优点： 适合解空间教小的问题 不必使用与总目标无关的规则 有利于向用户提供明确的解释 反向推理的缺点： 目标选择盲目，不允许用户主动提供信息指导推理 当规则的then是动作时，反向推理无法使用。,反向推理,反向推理基本思想是：选定一个目标，然后在知识库中查找能导出该目标的规则集，若这些规则中的某条规则前提与数据库匹配，则成功。否则，将该规则前提作为子目标，递归执行上述过程，直到总目标被求解或者没有能导出目标的规则。过程Achieve（G）给出了反向推理的基本思想。,Procedure Achieve（G） 扫描数据库，如果找到G，返回T 否则找到能导出G的规则集S； while S非空 do begin 调用过程ChooseRule（S），从S中选出规则R while R在S中且R的前提部分非空 do begin GHEAD(R的前提部分)； R的前提部分 TAIL(R的前提部分) M=Achieve（G） if M为F，then 从S中去掉R end If R在S中 then返回T end 当S为空时，返回F end,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也会成功。因此，分支失败回溯到“兄长”节点，而不是“父”节点。 I II 1 2 3 III 4 5 6 7,正向推理的缺点是有些盲目，求解了许多与总目标无关的子目标。反向推理的缺点是盲目选择目标，求解了许多可能为假的总目标，要是解空间较大，则更为明显。解决这些问题的有效办法，是综合利用正向推理与反向推理的优点，即正向推理帮助选择目标，再反向求解目标。这就是混合推理的思想。过程Alternate 给出了这种策略的基本思想。,3.2.4混合推理,Procedure Alternate Repeat 让用户将事实输入到数据库中； 调用Respond，从已知事实出发演绎出部分结果； 调用Choose-Goal，选出一个目标G； 调用Achieve（G），确定目标G的真假性 until 问题被求解 这是个原理示意程序，在实际应用中，有多种混合推理模式。,语义网络形式上是一个有向图：由一组节点和若干条连接节点的弧构成。 节点：表示一个问题领域的物体、概念、状态。 弧：表示节点间的关系。 常用的关系有分类关系、事物属性关系、推理关系等。 分类： 1）Subset-of关系（子集关系） Subset-of Subset-of,鸽子,鸟,动物,5.3语义网络,2）A-Menber-of关系（成员关系） A-Menber-of 3）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）沿着父框架的槽，一次就搜索值侧面、默认侧面和需要侧面。,5.4.2 框