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

第四章 基于知识的系统,4.1 KB系统的开发4.2 设计基于产生式表示的KB系统开发工具4.3 专家系统实例MYCIN4.4 问题求解的结构化组织本章小结,4.1 KB系统的开发,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(Knowledge Engineering Environment),任务特征与外壳不匹配时不行！,编程语言不能直接描述控制结构！,4.2 设计基于产生式表示的KB系统开发工具,最著名的基于产生式表示的KB系统开发工具就是产生式系统语言OPS5。OPS5采用条件-动作型产生式规则，只允许正向推理，规则的右部可以是任何操作函数的序列。下面介绍一个命名为Xps的实验型产生式系统，它模拟了OPS5的实现。,4.2.1 总体设计,产生式系统由三个部分组成：规则库、综合数据库和控制系统。1.规则的表示:=*+可以用规则定义函数Define-Rule定义一条新规则，并将其置于规则库。例如：(Define-Rule Eat(Hungry?Person)(Edible?Food)(Write(?Person eats the?Food),2.综合数据库的表示综合数据库的内容表示为以列表形式描述的谓词公式。可以用存储函数DB-Store将它们插进综合数据库。例如，在初始化有关饮食问题的综合数据库时，若执行：(DB-Store(Hungry Peter)(DB-Store(Hungry Paul)(DB-Store(Edible Hot-Dog)(DB-Store(Edible Turkey-Leg)(DB-Store(Edible Muffin)则综合数据库的初始内容就由这5个事实元素构成，且每个元素附加一个时间标签以指示它们进入综合数据库的先后顺序.时间标签按事实元素进入综合数据库的顺序，从1开始，依次加1。,3.控制系统控制机制采用前述的识别-行动循环控制流。在每个识别-行动循环的识别阶段均有可能激活多条规则，且每条激活的规则可有多个激活例，这些规则激活例构成了所谓冲突集。例如上述有关饮食问题的规则就存在多个满足综合数据库的激活例，并由此建立了以下冲突集：规则名 激活例序号 变量置换 时间标签表Eat 1 Peter/Person,Hot-Dog/Food(1 3)Eat 2 Peter/Person,Turkey-Leg/Food(1 4)Eat 3 Peter/Person,Muffin/Food(1 5)Eat 4 Paul/Person,Hot-Dog/Food(2 3)Eat 5 Paul/Person,Turkey-Leg/Food(2 4)Eat 6 Paul/Person,Muffin/Food(2 5)其中，时间标签表记载了与规则条件部分匹配模式匹配的事实元素的时间标签。,Xps采用的冲突解法是：新近和特殊的规则激活例优先选用。冲突集可以有三种情况：空集：则系统无法继续推理过程，失败结束；单一规则激活例：直接执行该激活例；多个规则激活例：执行冲突解法。,冲突解法分三个步骤，分别由三个筛选器执行：（1）折射（Refraction）筛选将已使用过，又再一次激活的规则例删除，不让其进入冲突集。规则激活例中记载的时间标签表，使得检查规则例是否重复激活成为可能。（2）新近性（Recency）筛选优先选用能与最新近进入综合数据库的事实元素相匹配的规则激活例。由于规则条件部分往往有多个匹配模式，所以必须综合评价它们的新近性。可基于时间标签表加以评价，该方法如下：首先将各规则激活例的时间标签表按数字从大到小排列其包含标签的顺序（并删除重复的标签），然后再依次比较经排序后的时间标签表的相应元素，就可鉴别出新近性的不同。,例如，有以下各时间标签表：（1 10 3）（3 10 1）（9 1 3）（8 6 9 7）（10 3）（3 1 2 9）（3 1 10 1）则先对各时间标签表进行排序得：（10 3 1）（10 3 1）（9 3 1）（9 8 7 6）（10 3）（9 3 2 1）（10 3 1）按新近性原则，相应于时间标签表（1 10 3）（3 10 1）（3 1 10 1）的规则激活例新近性最好。,（3）特殊性（Specificity）筛选特殊性意指规则的条件部分具有更多的匹配模式。显然，特殊性高的规则难以激活，所以一旦激活，并通过了新近性筛选，就应优先选用这种规则的激活例。对于上例新近性筛选留下的三个规则激活例，按特殊性原则，就应选用对应于时间标签表（3 1 10 1）的那个。若经由上述三个步骤的筛选后仍留下多于一个的规则激活例，则从中随机选用一个。,练习,P190、二、4设在Xps运行的某个识别-行动循环激活了6条规则例，它们的时间标签表依次分别为：（1 3 5）（7 6 0）（7 6 6 0）（5 6 8）（5 6 2）（0 3 7）已知第1、4规则激活例已执行过，问此循环应选用哪条规则激活例加以执行？,4.2.2 Xps的实现,实现Xps的程序设计分三个部分进行：规则库管理、综合数据库管理和推理引擎。1、规则库管理规则库设计为一个散列表，用前述函数Define-Rule定义产生式规则。为提高使用效率，规则转变为内部形式的数据结构存放，包括5个数据场：规则名、匹配模式列表、模式变量表、操作函数列表和时间标签表集合。时间标签表集合存放已被执行过的该规则激活例的时间标签表，以备检查。,2、综合数据库管理综合数据库设计为树状层次索引网。可按事实元素列表中的元素次序逐层建立事实元素的索引，并将事实元素置于索引路径的末端。面向综合数据库的管理操作包括PS-Store、PS-Erase和PS-Fetch，分别实现事实元素的插入、删除和取用。,3、推理引擎 推理引擎也称为解释器，其主要工作就是对规则库中的规则进行解释性执行。基本的控制流是识别-行动循环。1）建立冲突集每当一个规则条件部分的所有匹配模式都找到匹配的事实元素时，就建立该规则的一个激活例，记载模式变量束缚值和时间标签表。随即检查该标签表是否出现于该规则的标签表集合中，若出现，则该激活例已使用过，不再进入冲突集，否则加进冲突集。2）解决冲突由于折射筛选步已在建立冲突集的过程中完成，解决冲突实际上就是进行后二步：新近性筛选和特殊性筛选，若筛选后冲突集中还剩余多个规则激活例，就随机取一个。,3）执行选用的规则例首先把该规则激活例的时间标签表加进相应规则内部结构的时间标签表集合；然后将模式变量的束缚值取出，作为参数调用规则右部的操作函数加以执行。为增加产生式规则的表示功能，Xps允许在规则的条件部分应用特殊谓词Assign，连词AND和NOT，关系表达式（以前缀方式表示）和任何真值函数（以$符号作为函数名前缀）。,应用Assign谓词的表达式形如：（Assign）用于提高规则表示的便易性。其用法通过下面例子加以说明：（Define-Rule Fill-Big-Box(Assign?A（On?X Table）)(Color?X Green)(PS-Store(In?X Big-Box)(Write(?X is now in the big box)(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”指示的空时间标签。例如时间标签（9 0 3）就意指条件部分第2个匹配模式是NOT匹配模式。关系表达式和真值函数不需要在综合数据库中进行匹配检查，而是依据关系符的语义或真值函数的执行来确定真值（T或F）。因此，同样不可能取得时间标签，可相应地引入空时间标签。,上周回顾,知识表示的实用化问题程序性知识陈述性知识本体表示语言的研究XMLDTDRDFKB系统特点、组成、评价、开发实验型产生式系统XPs的设计和实现,4.2.3 应用实例家族树,下面通过一个关于家族树应用简例，观察基于产生式表示的KB系统设计和问题求解流程。问题求解任务是查询某人的祖先，可以设计5条产生式规则加以表示。该KB系统启动后首先初始化综合数据库：用PS-Store插入标记（Load-Signal）作为第1个事实元素。,1）(Define-Rule Load-Data(Assign?A(Load-Signal)(PS-Erase?A)(PS-Store(Parents Penelope Jessica Jeremy)(PS-Store(Parents Jessica Mary-Elizabeth Homer)(PS-Store(Parents Jeremy Jenny Steven)(PS-Store(Parents Steven Loree Nil)(PS-Store(Parents Loree Nil Jason)(PS-Store(Parents Homer Stephanie Nil)(PS-Store(Start-Singal)2）(Define-Rule Start-Example(Assign?A(Start-Signal)(PS-Erase?A)(Write(Name of Person:)(Read?Input)(PS-Store(Request Ancestors?Input),插入事实元素,请求输入姓名,3）(Define-Rule Find-Ancestors(Request Ancestors?Name)(NOT(Equal?Name Nil)(Parents?Name?Mother?Father)(PS-Store(Request Ancestors?Mother)(PS-Store(Request Ancestors?Father)4）(Define-Rule Print-Ancestor(Assign?Request1(Request Ancestors?Name)(NOT(=?Name Nil)(Write(?Name is an ancestor)(PS-Erase Request1)5）(Define-Rule Stop-Finding-Ancestors(Request Ancestors?Name)(NOT(=?Name Nil)(NOT(AND(Request Ancestors?X)(NOT(=?X Nil)(NOT(=?X?Name)(Write(No more ancestors)(Halt),查询父亲母亲,打印祖先名,无其他祖先！,(Load-Signal)(Parents Penelope Jessica Jeremy)(Parents Jessica Mary-Elizabeth Homer)(Parents Jeremy Jenny Steven)(Parents Steven Loree Nil)(Parents Loree Nil Jason)(Parents Homer Stephanie Nil)(Start-Singal)(Request Ancestors Penelope)(Request Ancestors Jessica)(Request Ancestors Jeremy)(Request Ancestors Jenny)(Request Ancestors Steven)(Request Ancestors Loree)(Request Ancestors Jason)(Request Ancestors Mary-Elizabeth)(Request Ancestors Homer)(Request Ancestors Stephanie),4.2.4 性能改进,缺点：从上例可看出，Xps求解过程中重复地产生冲突集。每个识别-行动循环都重新生成一个冲突集，但系统只从中选一个规则激活例执行，其余规则激活例全部抛弃。实用上，相邻二个循环之间综合数据库的内容往往变化很小，造成许多同样的匹配检查工作重复地进行，浪费时间，降低问题求解效率。改进：Xps应设计成不是每个循环重新生成一个冲突集，而是始终保持一个全局冲突集。一旦初始冲突集生成，在以后的识别-行动循环中只需依据综合数据库的增删变化，加新的规则激活例到冲突集，删去条件部分变得不满足的规则激活例。,对Xps作以下改进：（1）将规则条件部分的匹配模式置于另一树状层次索引网，并记载匹配模式在规则条件部分中的排列次序和模式变量束缚值。用增删的事实去匹配规则。（2）记载规则的部分满足状态。（3）处理否定的匹配模式。Xps的主要功能与OPS5相当，推理控制机制也相同；主要区别在于知识表示形式和内部存储方式。,4.2.5 开发工具OPS5,OPS5开发于70年代后期，属表示语言型专家系统开发工具。能提供比骨架型工具更为通用的推理控制机制和知识表示语言去适应于较宽范围的应用领域，尤其是专家系统开发者可以通过OPS5的表示语言去设计特别的控制要求。Xps较好地模仿了OPS5的实现，主要差别在下面三个方面。,1）对象表示,Xps用一组相互独立的事实元素来描述一个对象，而OPS5则用对象子句集描述一个对象，形如：（+）例如Xps用一组事实元素来描述某个人Penelope：(Parents Penelope Jessica Jeremy）(Age Penelope 20)(Sex Penelope Female)而在OPS5中则紧凑地表示为：(Person Name Penelope Age 20 Sex Female Parents Jessica Jeremy),指示属性名,2)对象的存储形式,Xps以树状层次索引网存储事实元素，OPS5则为每类对象定义一个类（Class）结构，使类的每个实例（即对象）具有固定数量的属性和固定的属性名。OPS5以LITERALIZE格式定义类。例如类Person定义为：（LITERALIZE Person Name Age Sex Parents）类定义允许最后一个属性取多值，这种属性称为向量属性。,3）规则条件,规则条件部分匹配模式中的模式变量常会受到一些值束缚限制，例如要求模式变量?X非空。Xps以插入规则条件部分的（NOT(EQUAL?X NIL)）来表示；OPS5中规则前提部分的模式则以带变量的类实例（对象）来实现更为方便和紧凑的表示。就以前述家族树最后一条规则的条件部分为例，OPS5将其表示为：（Request Type Ancestors Target NIL）-(Request Type Ancestors Target NIL),OPS5（和Xps）的一个不同于骨架型工具的重要特点是允许专家系统开发者定制特别的控制要求。定制建立在二个重要概念的基础上：目标模式和控制元素。OPS5提供的这种推理控制的定制能力既是优点也是缺点。优点体现在能够定制控制要求以适应于问题特征和更有效地求解问题，也有利于知识库维护；缺点体现在要求专家系统开发者具有一定的技术水平，无经验的开发者会感觉到难以使用。,4.3 专家系统实例MYCIN,MYCIN是一个通过提供咨询服务来帮助普通内科医生诊治细菌感染性疾病的专家系统，其于1972年开始研制，74年基本完成，并投入实际应用。围绕着MYCIN的各种研究工作一直延续了10年，对于推动知识工程以及专家系统学科的建立和发展具有重要影响。,知识表示方式：,MYCIN也设计为典型的产生式系统，由规则库、综合数据库和控制系统三个部分组成；只是基于规则的推理采用逆向方式。从KB系统的组成来看，规则库就是MYCIN的知识库，综合数据库和控制系统联合形成推理机。由于当时尚未出现视窗技术，用户界面只提供基于文本(text)的问答过程和结果显示。,4.3.1 知识库的构造,MYCIN的知识库以前提-动作型产生式规则来表示。:=RULE PREMISE($AND+)ACTION+:=|（$OR+）。常用函数：(SAME)(CONCLUDE TALLY),可信度，-1,+1,关联三元组,MYCIN系统建立的初期就以上述格式表示和收集了200多条规则于知识库，其中047号规则表示如下：RULE 047 PREMISE($AND(SAME CNTXT SITE BLOOD)(NOTDEFINITE CNTXT IDENT)(SAME CNTXT STAIN GRAMNEG)(SAME CNTXT MORPH ROD)(SAME CNTXT BURN T)ACTION(CONCLUDE CNTXT IDENT PSEUDOMONAS TALLY 0.4)规则047如果：1）培养物取自血液，且2）病原体的身份未鉴别，且3）病原体的染色是革兰氏阴性，且 4）病原体的形态为杆状，且5）病人被烧伤；那么：该病原体的身份应鉴别为假单胞细菌，且可信度为0.4。,需考察的对象（上下文）,4.3.2 推理机的设计,整个推理过程通过称为目标规则的092号规则来启动。规则092如果：1）存在一种病原体需要治疗，且2）可能存在其它需要治疗的病原体，尽管它们尚未从目前的培养物中分离出来；那么：1）依据病原体对药物的敏感情况，制定能有效抑制这些病原体的治疗方案（可以有多个），且2）从中制定最佳的综合治疗方案；否则：病人不必治疗。,1、诊断的推理控制,采用逆向推理和深度优先的搜索策略。步骤：在综合数据库（MYCIN称为动态数据库）中建立上下文对象：病人-1（patient-1），作为一棵上下文树的根节点。以建立病人的治疗方案(REGIMEN)为目标，激活上述规则092。规则链的形成导致推理树（或称目标树）的建立。,由于导出相同结论的规则（如090和149）相互独立地支持结论的成立（有或关系），而规则前提包含的条件又有与关系，所以推理树成为与或树。,MYCIN系统通过两个相互调用的程序MONITOR和FINDOUT去推进整个推理（咨询）过程。MONITOR分析相关的规则能否激活；FINDOUT则搜索规则激活所需的数据（属性值及其CF）。MYCIN将规则按上下文对象分类，使得每次对于一个目标作推理时，只需考虑该目标涉及的那个上下文对象相关的规则，从而大幅度提高了推理的效率。,FINDOUT的程序流程,2、不确定推理,鉴于推理过程生成了与或推理树，MYCIN的不确定推理既要处理CF沿推理链的传递，又要处理CF的与或组合。,3、治疗选择机制,所谓治疗方案，就是依据推断出的可能病菌（病原体）选用适当的治疗药物。知识库中已包含一组治疗规则，每条规则为一种病菌制定一个药物治疗方案。当然，医生对药物的使用有最后决定权，若发现用药不合理，可以要求除掉这些不合理的药物，并重新启动治疗方案的综合制定。,4.3.3 系统服务设施,1、推理解释WHY:主要用于推理过程中系统请求医生提供观测数据时。HOW:主要用于推理结束后，回答医生对推理结果提出的疑问。WHYNOT:医生询问某条规则为何未被使用，系统的解释通常是该规则的前提不能满足。,为了使系统提供的解释适合于不同专业的医生（甚至病人），MYCIN的研制者于1982年提出了能依据用户知识水平加以裁剪的解释；并设置了二个参数：复杂性和重要性，来量化知识单元（规则和对象属性）的可解释性。复杂性-用以指示为理解-知识单元，需要用户自身具备的知识水平。重要性-为让用户理解给出的解释，该知识单元不可缺少的程度。,2、知识库维护,MYCIN系统知识库中包含的推理规则，尽管形式上相互独立，但语义上却相互关联，并由此形成推理树。正是这种语义上的关联，使知识库的维护面临困难。,以增加规则到知识库为例，通常会出现以下三类问题：包含问题在知识库包含规则r:A B D的情况下，增加新规则r：A B C D。显然，这二条规则不应同时存在于知识库（会引起冗余）。究竟保存哪条规则于知识库取决于是否存在这样的情况：A B C D。单一规则的不一致在知识库包含规则A B的情况下，增加新规则A B，就会产生这种不一致问题。显然，让系统自动发现该问题是容易的。多规则的不一致在知识库包含规则A B，B C，C D的情况下，增加新规则A D就会产生这种不一致问题。由于涉及到一条推理链，要查出这种问题往往既困难又耗时。,3、教学,MYCIN的知识库包含了医学专家提供的丰富经验知识，可以作为医疗教学的知识来源。,4.3.4 开发工具EMYCIN,EMYCIN是从MYCIN系统抽取出的与应用领域无关的骨架型专家系统开发工具。EMYCIN继承了MYCIN的主要特点，如下：采用逆向链深度优先的控制策略；使用产生式规则表示领域知识；允许事实和规则具有不确定性（以可信度指示）。,EMYCIN定义的规则可以用BNF范式描述如下：:=(IF THEN ELSE):=的与或组合:=:=:=(),用EMYCIN开发的一些有影响的专家系统,PUFF：设计于1978年，是一个面向肺部疾病治疗；HEADMED：1978年，面向心理医药学的；SACON：1979年，面向机械结构分析；ONCOCIN：1981年，用于辅助医生管理患淋巴瘤癌症病人的化疗协议；CLOT：1980年，用于诊断血液凝结系统的疾病；DART：1981年，用于诊断IBM计算机远程处理系统中出现的软件和硬件故障。,4.4 问题求解的结构化组织,原因：传统的知识表示技术与人组织问题求解的思维方式严重失配。为此，需要在易于人理解的更高级别去开展知识表示的研究，那就是纽厄尔提议的 知识级。问题求解行为是通过目标集和动作集加以刻画的，知识作为关联动作到目标的媒介，基于简单的合理性原则。,4.4.1 结构化组织的要求,表示和组合应用领域知识的最简单策略，是把问题求解所用的全部知识统统表示为规则，利用规则搜索从问题求解的初始状态到目标状态的路径。利用产生式规则表示领域知识有许多优点，但也有缺点，具体表现为：难以扩展。选择规则的低效性。不灵活的控制策略。单一的表示形式。,为克服这些缺点，将求解复杂问题的知识划分为一组相对独立的模块比较合适。模块化的一个重要议题就是如何协调模块在问题求解过程中的相互合作。模块的划分可以是面向动作的或面向对象的。前者面向怎么做知识的组织，后者面向是什么知识的组织。,4.4.2 事务表,事务表(Agenda)是一张应由系统执行的事务的列表，也称任务表，是面向动作的问题求解组织方式之一。它允许各个推理模块经由事务表相互通信，以求协调它们在问题求解中的合作关系。,任务,推理模块,优先级,理由表,4.4.3 黑板法,黑板法(Blackboard)也是面向动作的组织方式。用黑板法组织问题求解首先出现于70年代对取名为HEARSAY-的口语理解系统的研究。系统由一组称为知识源(KS-Knowledge Source)的独立推理模块和黑板组成。每个KS包括三个部分：触发模式、直接码和体。黑板是所有KS可以访问的公共数据区。,4.4.4 问题求解建模4.4.5 新一代KB系统技术这两节有兴趣自己看，了解一下！,本章小结,