人工智能知识表示.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调用过程ChooseRule（S），从S中选出规则RwhileR在S中且R的前提部分非空dobeginGHEAD(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）沿着父框架的槽，一次就搜索值侧面、默认侧面和需要侧面。,5.4.2框架的推理,设F是一个给定的框架1）建立一个表，初始时只有F一个元素。2）如果表中第一个元素的S槽的值侧面有非NIL值，则找到值。转8。3）如果表中第一个元素的S槽的默认侧面有非NIL值，则找到值。转8。4）如果表中第一个元素的S槽的需要侧面有非NIL值，则找到值。转8。5）从表中删除第一个元素，如果第一个元素的父节点槽的值侧面的值不是NIL，则把这个值指向的父节点加入到表的末尾。6）如果此时表空,则说明F框架S槽没有值。转8。7）转2。8）结束。,下面我们求给定框架S槽的值，给出第三种方法的搜索过程：,剧本是框架的一种特殊形式，它用一组槽来描述某些事件的发生序列，很象剧本中的过程，故成为“剧本”。一个剧本一般由以下各部分组成：1）开场条件给出在剧本描述的事件发生的前提条件2）人物用来表示可能出现的有关人物3）道具用来表示可能出现的有关物体4）场景描述事件发生的顺序，剧本可由多个场景组成，每个场景又可是其它的剧本。5）结果给出在剧本所描述的事件发生后所产生的结果。,5.5剧本,下面以去医院看病剧本为例说明剧本各个部分的组成。1）开场条件病人有病并带有一定数量的钱。2）人物病人、医生、护士3）道具药品、桌子、处方、钱4）场景,4.3剧本,场景1看病之前a）进入医院b）挂号c）取病历d）在诊室门前等候e）护士叫号场景2看病a）叙述病情b）医生检查c）医生写诊断书d）医生开处方e）离开诊室,场景3看病之后a）在药房划价b）交费c）取药d）离开医院5）结果a）病人看了病b）病人取了药c）医院收了费d）医院的药少了,一旦剧本被启用，可应用它进行推理，最重要的是运用剧本可以预测没有明显提及的事件的发生。假如有如下情节：“老张去医院，看了病，拿着处方单去药房，划完价，就离开了医院。”,如果提问：“老张取到病历了吗？”根据剧本，可回答：“取到病历。”如果提问：“取药需付现金还是采用记帐方式？”根据剧本，可回答：“付现金。”如果在剧本中再存储一些知识，当提问：“老张为什么没取药？”时，系统会回答：“可能现金不够，或药太贵。”,