人工智能第四章基于知识的系统69

第四章基于知识的系统4.1KB系统的开发4.2设计基于产生式表示的KB系统开发工具4.3专家系统实例——MYCIN4.4问题求解的结构化组织本章小结4.1KB系统的开发KB系统是基于知识的问题求解系统，当其表现出专家级问题求解能力时称为专家系统。KB系统的研究起始于20世纪60年代中期。通用问题求解方法的一味追求导致了人工智能的研究陷入黑暗摸索期！1.KB系统的一般概念KB系统的特点具有求解问题所需的专门知识基本原理和常识领域专家经验知识具有使用专门知识的符号推理能力KB系统的组成KB系统的基本结构可视为由三个部分组成：知识库、推理机和用户界面KB系统执行的一些常见问题求解任务：1)解释2)诊断3)监控4)预测5)规划6)设计推理解释解释问题求解过程及结果的合理性是KB系统应具备的能力。简单的解释方式：规则追踪就是把问题求解过程中激活使用的规则按激活的次序显示给用户。高级的解释方式：按领域基本原理和常识重构解答。KB系统的评价KB系统有多个方面的评价，其中有三个最重要：计算、感观和性能对MYCIN性能的评价评价方式：首先由KB系统的设计者用各种可能的实验测试，确保无误后再交给用户；用户以大量实际案例运行KB系统，并与原有方式执行的结果相比较；一旦发现错误就立即作修改，直到用户信服KB系统的有效性，然后才正式投入应用。对于任何类型的错误，其容许出现的程度必须通过权衡错误导致的损失和正确解答带来的利益来决定。2.KB系统的体系结构原则本节内容面向研究生，可以不看了3.KB系统的开发过程知识获取：就是把用于问题求解的专门知识从某些知识源提炼出来，转化为推理机使用形式的过程。潜在的知识源包括领域专家、书本、数据库以及普通人的经验。目前，知识获取的主要方式：以知识工程师作为中间人从领域专家处获取专门知识。为实现知识获取的自动化，就要努力取消知识工程师的中介作用，让一个智能的知识获取界面直接与领域专家对话。领域专家知识工程师知识获取界面推理机知识库手工知识获取过程KB系统领域专家智能的知识获取界面推理机知识库KB系统知识获取的自动化通过知识工程师来开发KB系统可归纳为五个阶段。识别阶段，知识工程师和领域专家一起判别问题的类型和特征。概念化阶段，阐明重要的概念、关系和信息流特征，并用以描述问题求解的概念模型，包括问题求解方法、推理控制要求和约束条件。形式化阶段，决定知识表示形式和推理机制。实现阶段，以概念模型作为语义框架获取问题求解所需的详细知识，以形式化阶段决定的知识表示语言编写并存放进知识库。新建立的知识库和推理机一起构成KB系统的第一个原型。测试阶段，通过各种测试手段评价原型系统的性能。认识问题的特征找出表达知识的概念设计组织知识的原则形成概括知识的规则验证组织知识的原则必要条件概念结构规则重新描述重新设计重新完善KB系统的开发步骤识别概念化形式化实现测试4.KB系统的开发工具和环境开发工具和环境可以分为三类：外壳(骨架系统)、表示语言、开发工具箱(开发环境)。外壳：给知识工程师提供现成的实现KB系统的骨架，只要按骨架规定的表示方式编写专门知识，就可形成应用领域的KB系统。表示语言类工具：为知识工程师提供面向知识处理的高级编程语言。典型：OPS5开发工具箱(或称开发环境)：为KB系统的生命周期中各个阶段提供工具，甚至可以提供多种外壳和表示语言，以及综合它们建立复杂KB系统的手段。典型：KEE(KnowledgeEngineeringEnvironment)任务特征与外壳不匹配时不行！编程语言不能直接描述控制结构！4.2设计基于产生式表示的KB系统开发工具最著名的基于产生式表示的KB系统开发工具就是产生式系统语言OPS5。OPS5采用条件-动作型产生式规则，只允许正向推理，规则的右部可以是任何操作函数的序列。下面介绍一个命名为Xps的实验型产生式系统，它模拟了OPS5的实现。4.2.1总体设计产生式系统由三个部分组成：规则库、综合数据库和控制系统。1.规则的表示规则:=规则名{匹配模式}*{操作}+可以用规则定义函数Define-Rule定义一条新规则，并将其置于规则库。例如：(Define-RuleEat(Hungry?Person)(Edible?Food)(Write'(?Personeatsthe?Food)))2.综合数据库的表示综合数据库的内容表示为以列表形式描述的谓词公式。可以用存储函数DB-Store将它们插进综合数据库。例如，在初始化有关饮食问题的综合数据库时，若执行：(DB-Store'(HungryPeter))(DB-Store'(HungryPaul))(DB-Store'(EdibleHot-Dog))(DB-Store'(EdibleTurkey-Leg))(DB-Store'(EdibleMuffin))则综合数据库的初始内容就由这5个事实元素构成，且每个元素附加一个时间标签以指示它们进入综合数据库的先后顺序.时间标签按事实元素进入综合数据库的顺序，从1开始，依次加1。3.控制系统控制机制采用前述的识别-行动循环控制流。在每个识别-行动循环的识别阶段均有可能激活多条规则，且每条激活的规则可有多个激活例，这些规则激活例构成了所谓冲突集。例如上述有关饮食问题的规则就存在多个满足综合数据库的激活例，并由此建立了以下冲突集：规则名激活例序号Eat1{Peter/Person,Hot-Dog/Food}(13)Eat2{Peter/Person,Turkey-Leg/Food}(14)Eat3{Peter/Person,Muffin/Food}(15)Eat4{Paul/Person,Hot-Dog/Food}(23)Eat5{Paul/Person,Turkey-Leg/Food}(24)Eat6{Paul/Person,Muffin/Food}(25)其中，时间标签表记载了与规则条件部分匹配模式匹配的事实元素的时间标签。Xps采用的冲突解法是：新近和特殊的规则激活例优先选用。冲突集可以有三种情况：空集：则系统无法继续推理过程，失败结束；单一规则激活例：直接执行该激活例；多个规则激活例：执行冲突解法。冲突解法分三个步骤，分别由三个筛选器执行：（1）折射（Refraction）筛选将已使用过，又再一次激活的规则例删除，不让其进入冲突集。规则激活例中记载的时间标签表，使得检查规则例是否重复激活成为可能。（2）新近性（Recency）筛选优先选用能与最新近进入综合数据库的事实元素相匹配的规则激活例。由于规则条件部分往往有多个匹配模式，所以必须综合评价它们的新近性。可基于时间标签表加以评价，该方法如下：首先将各规则激活例的时间标签表按数字从大到小排列其包含标签的顺序（并删除重复的标签），然后再依次比较经排序后的时间标签表的相应元素，就可鉴别出新近性的不同。例如，有以下各时间标签表：（1103）（3101）（913）（8697）（103）（3129）（31101）则先对各时间标签表进行排序得：（1031）（1031）（931）（9876）（103）（9321）（1031）按新近性原则，相应于时间标签表1103）（3101）（31101）的规则激活例新近性最好。（3）特殊性（Specificity）筛选特殊性意指规则的条件部分具有更多的匹配模式。显然，特殊性高的规则难以激活，所以一旦激活，并通过了新近性筛选，就应优先选用这种规则的激活例。对于上例新近性筛选留下的三个规则激活例，按特殊性原则，就应选用对应于时间标签表（31101）的那个。若经由上述三个步骤的筛选后仍留下多于一个的规则激活例，则从中随机选用一个。练习P190、二、4设在Xps运行的某个识别-行动循环激活了6条规则例，它们的时间标签表依次分别为：（135）（760）（7660）（568）（562）（037）已知第1、4规则激活例已执行过，问此循环应选用哪条规则激活例加以执行？4.2.2Xps的实现实现Xps的程序设计分三个部分进行：规则库管理、综合数据库管理和推理引擎。1、规则库管理规则库设计为一个散列表，用前述函数Define-Rule定义产生式规则。为提高使用效率，规则转变为内部形式的数据结构存放，包括5个数据场：规则名、匹配模式列表、模式变量表、操作函数列表和时间标签表集合。时间标签表集合存放已被执行过的该规则激活例的时间标签表，以备检查。2、综合数据库管理综合数据库设计为树状层次索引网。可按事实元素列表中的元素次序逐层建立事实元素的索引，并将事实元素置于索引路径的末端。面向综合数据库的管理操作包括PS-Store、PS-Erase和PS-Fetch，分别实现事实元素的插入、删除和取用。3、推理引擎推理引擎也称为解释器，其主要工作就是对规则库中的规则进行解释性执行。基本的控制流是识别-行动循环。1）建立冲突集每当一个规则条件部分的所有匹配模式都找到匹配的事实元素时，就建立该规则的一个激活例，记载模式变量束缚值和时间标签表。随即检查该标签表是否出现于该规则的标签表集合中，若出现，则该激活例已使用过，不再进入冲突集，否则加进冲突集。2）解决冲突由于折射筛选步已在建立冲突集的过程中完成，解决冲突实际上就是进行后二步：新近性筛选和特殊性筛选，若筛选后冲突集中还剩余多个规则激活例，就随机取一个。3）执行选用的规则例则内部结构的时间标签表集合；然后将模式变量的束缚值取出，作为参数调用规则右部的操作函数加以执行。为增加产生式规则的表示功能，Xps允许在规则的条件部分应用特殊谓词Assign，连词AND和NOT，关系表达式（以前缀方式表示）和任何真值函数（以$符号作为函数名前缀）。应用Assign谓词的表达式形如：Assign模式变量匹配模式）面例子加以说明：Define-RuleFill-Big-Box(Assign?A（On?XTable）)(Color?XGreen)(PS-Store'(In?XBig-Box))(Write'(?Xisnowinthebigbox))(PS-Erase?A))这里谓词Assign,仅指示将与匹配模式匹配的事实元素作为模式变量?A的束缚值。需做匹配检查已经是束缚值了！连词AND的应用使多个匹配模式联合作为单一的匹配模式。例如某规则条件部分形如：(P?X?Y)(AND(Q?X?Y)(W?Y?Z))相当于该规则只有2个匹配模式，规则激活例的时间标签表也只包含2个时间标签。连词AND辖域内的匹配模式仍分别作匹配检查，只是仅将匹配的事实元素中最大的时间标签作为整个AND匹配模式的时间标签。连词NOT的应用引入了否定的匹配模式。例如：(NOT(P?X?Y))只有（P?X?Y）不能满足的情况下，NOT匹配模式才满足。显然,相应于满足的NOT匹配模式，不可能取得时间标签；但为了表示因NOT匹配模式的引入增加了规则的特殊性，可产生一个以数字“0”指示的空时间标签。例如时间标签（903）就意指条件部分第2个匹配模式是NOT匹配模式。行匹配检查，而是依据关系符的语义或真值函数的执行来确定真值（T或F）。因此，同样不可能取得时间标签，可相应地引入空时间标签。上周回顾知识表示的实用化问题程序性知识陈述性知识本体表示语言的研究XMLDTDRDFKB系统特点、组成、评价、开发实验型产生式系统XPs的设计和实现4.2.3应用实例——家族树下面通过一个关于家族树应用简例，观察基于产生式表示的KB系统设计和问题求解流程。问题求解任务是查询某人的祖先，可以设计5条产生式规则加以表示。该KB系统启动后首先初始化综合数据库：用PS-Store插入标记（Load-Signal）作为第1个事实元素。1）(Define-RuleLoad-Data(Assign?A(Load-Signal))(PS-Erase?A