人工智能ppt课件 213 产生式表示法.ppt
2022/12/11,中国矿业大学计算机学院,1,2.3 产生式表示法,第2章 知识表示,2.1 概 述,2.2 谓词逻辑表示法,2022/12/11,中国矿业大学计算机学院,2,产生式系统(Production System): 1943年,由珀斯特(Post)提出，他用这种规则对符号串作替换运算。 1965年美国的纽威尔和西蒙利用这种原理建立了认知模型。同年，斯坦福大学设计第一个专家系统DENDRAL时，就采用产生式系统的结构。 产生式系统是目前已建立的专家系统中知识表示的主要手段之一,如MYCIN、CLIPS/JESS系统等。 在产生式系统中，把推理和行为的过程用产生式规则表示，所以又称基于规则的系统。,2.3 产生式表示法,2022/12/11,中国矿业大学计算机学院,3,一般地，一个规则由前项和后项两部分组成。前项表示前提条件，各个条件由逻辑连接词（合取、析取等）组成各种不同的组合。后项表示当前提条件为真时，应采取的行为或所得的结论。产生式系统中每条规则是一个“条件结论”或“前提结论”的产生式，起简单形式为： IF前提THEN结论 IF条件THEN动作,2.3.1 规则的表示,2022/12/11,中国矿业大学计算机学院,4,为了严格地描述产生式，下面用巴科斯范式给出它的形式描述和语义：=|=|= And (And ) | Or (Or ) =(,),2022/12/11,中国矿业大学计算机学院,5,1. 产生式规则通常用于表示事物间的因果关系；【基本形式】IF P then Q 或 P Q，其中P表示规则的条件（或称前提）；谓词、多元组、常量、变量、关系运算Q表示规则激活时应该执行的动作（或得到的结论）；激活规则条件P满足；【规则分类】前提-结论型条件-动作型,2022/12/11,中国矿业大学计算机学院,6,1. 产生式规则前提-结论型规则（P Q）例如，关于动物世界的产生式系统中有规则IF 动物是哺乳动物，且吃肉；Then 这种动物是食肉动物。或形式化为：Mammal(x) Eat(x,Meat)Carnivore(x)(Mammal,?x) (Eat,?x,Meat) (Carnivore,?x) P谓词、多元组、关系表达式和真值函数的任意 组合；不要求遵从一阶谓词演算的表示形式 变量视为隐含地受全称量词约束；Q结论任意数据结构，如向量、数组、表格等。,2022/12/11,中国矿业大学计算机学院,7,1. 产生式规则条件-动作型规则（P Q）P谓词、多元组、关系表达式和真值函数的任意 组合；不要求遵从一阶谓词演算的表示形式 变量可视为隐含地受全称量词约束；Q动作，任意操作函数操作综合数据库；屏幕、图像、文件操作；执行各种预定的计算功能；例如：x-1 1 null(y) x:=0,2022/12/11,中国矿业大学计算机学院,8,1. 产生式规则前提-结论型规则（P Q）条件-动作型规则（P Q）,左部（前件）,右部（后件）,谓词,关系表达式,真值函数,2022/12/11,中国矿业大学计算机学院,9,1确定性和不确定性规则知识的产生式表示 确定性规则知识可用前面介绍的产生式的简单形式表示即可。 不确定性规则知识对基本形式作一定的扩充，用如下形式表示 PQ （可信度） 或者 IF P THEN Q （可信度） 其中，P是产生式的前提或条件，用于指出该产生式是否是可用的条件；Q是一组结论或动作，用于指出该产生式的前提条件P被满足时，应该得出的结论或因该执行的操作。这一表示形式主要在不确定推理中当已知事实与前提中的条件不能精确定匹配时，只要按照“可信度”的要求达到一定的相似度，就认为已知事实与前提条件匹配，再按照一定的算法将这种可能性（或不确定性）传递到结论。,2.3.2 事实的表示,2022/12/11,中国矿业大学计算机学院,10,2确定性和不确定性事实性知识的产生式表示 确定性事实性知识一般使用三元组 （对象，属性，值）或 （关系，对象1，对象2）来表示，其中对象就是语言变量，这种表示的机器内部实现就是一个表。如事实“老李年龄是35岁”，便可以表示成 （Lee， Age， 35）其中，Lee是事实性知识涉及的对象，Age是该对象的属性，而35岁是该对象属性的值。而老李、老张是朋友，可表示成 （Friend， Lee， Zhang ）,2022/12/11,中国矿业大学计算机学院,11,而有些事实性知识带有不确定性和模糊性，若考虑不确定性，这种知识就可以用四元组的形式表示如下 （对象，属性，值，不确定度量值）或 （关系，对象1，对象2，不确定度量值）如不确定性事实性知识 “老李年龄可能是35岁”，这里老李是35岁的可能性取90%，便可以表示成 （Lee， Age， 35，0.9）而老李、老张是朋友的可能性不大，这里老李、老张是朋友的可能性取20%，可表示成（Friend， Lee， Zhang，0.2 ）,2022/12/11,中国矿业大学计算机学院,12,2.3.3 产生式系统的组成部分,产生式系统一般由三个基本部分组成：规则库、综合数据库和推理机。它们之间的关系如图所示。,产生式系统的基本结构,2022/12/11,中国矿业大学计算机学院,13,用于描述某领域内知识的产生式集合，是某领域知识(规则)的存储器，其中的规则是以产生式形式表示的。规则库中包含着将问题从初始状态转换成目标状态(或解状态)的那些变换规则。 规则库是专家系统的核心，也是一般产生式系统赖以进行问题求解的基础，其中知识的完整性和一致性、知识表达的准确性和灵活性以及知识组织的合理性，都将对产生式系统的性能和运行效率产生直接的影响。,1.规则库:,2022/12/11,中国矿业大学计算机学院,14,综合数据库又称为事实库，用于存放输入的事实、从外部数据库输入的事实以及中间结果(事实)和最后结果的工作区。当规则库中的某条产生式的前提可与综合数据库中的某些已知事实匹配时，该产生式就被激活，并把用它推出的结论放入综合数据库中，作为后面推理的已知事实。 显然，综合数据库的内容是在不断变化的，是动态的。,2.综合数据库:,2022/12/11,中国矿业大学计算机学院,15,推理机是一个或一组程序，用来控制和协调规则库与综合数据库的运行，包含了推理方式和控制策略。控制策略的作用就是确定选用什么规则或如何应用规则。 通常从选择规则到执行操作分3步完成：匹配、冲突解决和操作。,3.推理机:,(1) 匹配：匹配就是将当前综合数据库中的事实与规则中的条件进行比较，如果相匹配，则这一规则称为匹配规则。,2022/12/11,中国矿业大学计算机学院,16,(2) 冲突解决：冲突解决的策略有很多种 , 其中专一性排序、规则排序、规模排序和就近排序是比较常见的冲突解决策略。,(3) 操作：操作就是执行规则的操作部分。经过操作以后，当前的综合数据库将被修改，其他的规则有可能将成为启用规则。,因为可能同时有几条规则的前提条件与事实相匹配，究竟选哪一条规则去执行呢？这就是规则冲突解决。通过冲突解决策略选中的在操作部分执行的规则称为启用规则。,2022/12/11,中国矿业大学计算机学院,17,2. 产生式系统组成3个部分组成：规则库；综合数据库；推理机；,推理机,规则库,综合数据库,产生式系统的问题描述,控制应用规则推出解答的全过程,2022/12/11,中国矿业大学计算机学院,18,3. 应用实例八数码游戏综合数据库规则库冲突解决策略,2022/12/11,中国矿业大学计算机学院,19,2.3.4 产生式系统的分类,按产生式所表示的知识是否具有确定性分为：确定性产生式系统和不确定性产生式系统；按推理机的推理方向分为：正向、反向和双向推理产生式系统。按规则库及综合数据库的性质与结构特征分为：可交换的产生式系统、可分解的产生式系统和可恢复的产生式系统。,2022/12/11,中国矿业大学计算机学院,20, 按推理方向正向、逆向和双向产生式系统（前提-结论型）： (1) 正向产生式系统这种系统通过检查前提是否满足当前问题状态（与综合数据库内容匹配）来决定规则的激活，由此实现正向推理方式，并推动问题求解从初始状态向目标状态逼近。以正向推理方式使用的规则称为正向规则，或F规则（Forward rule）。 (2) 逆向产生式系统这种系统通过检查结论是否满足当前问题状态来决定规则的激活，由此实现逆向推理方式，并推动问题求解从目标状态向初始状态逼近。以逆向推理方式使用的规则称为逆向规则，或B规则（Backward rule）。 (3) 双向产生式系统这种系统以双向推理方式（正、逆向同时进行）去求解问题。双向系统的综合数据库必须有两套数据结构，分别描述从初始状态出发推得的中间状态正向状态，和从目标状态出发推得的中间状态逆向状态。换言之，综合数据库 = 正向状态描述 + 逆向状态描述，以便于F、B规则分别作用于不同的状态描述。,2022/12/11,中国矿业大学计算机学院,21,可交换的产生式系统 如果一个产生式系统对规则的使用次序是可交换的，那么无论先使用哪一条规则，都可以达到目的，即规则的使用次序对问题的最终求解是无关紧要的。我们称这样的产生式系统为可交换的产生式系统。,可分解的产生式系统 把一个规模较大且较复杂的问题分解为若干个规模较小且较简单的子问题，然后对每个子问题分别进行求解，这是人们求解问题时常用到的方法，可分解的产生式系统就是基于这一思想提出来的。,2022/12/11,中国矿业大学计算机学院,22,可恢复的产生式系统 在可交换产生式系统中，要求每条规则的执行只能为综合数据库增添新的内容，且不能删除和修改综合数据库已有的内容。这一要求是很强的，在许多规则的设计中难以达到。因此就需要产生式系统具有回溯功能，一旦问题求解到某一步发现无法继续下去时，就撤销在此之前得到的某些结果，恢复到先前的某个状态，然后选用别的规则继续求解。在问题求解过程中既可以对综合数据库添加新内容、又可删除或修改老内容的产生式系统称为可恢复的产生式系统。,2022/12/11,中国矿业大学计算机学院,23,2.3.5 产生式系统的优缺点,(1)模块化：规则使得知识容易封装并不断补充。(2)解释机制：通过规则容易建立解释机，这是因为一个规则的前件指明了激活这个规则的条件。通过跟踪已触发的规则，解释机可以得到推出某个结论的推理链。(3)类似人类认识过程：规则似乎是模拟人类怎样解决问题的一个自然方法。因此，产生式方法是当今最流行的专家系统设计模式。,优点:,2022/12/11,中国矿业大学计算机学院,24,缺点或不足:,(1)难以扩展：尽管规则形式上相互独立，但实际问题中往往彼此是相关的。这样当知识库不断扩大时，要保证新的规则和已有的规则没有矛盾就会越来越困难，知识库的一致性越来越难以实现。(2)规则选择效率较低：在推理过程中，每一步都要和规则库中的规则做匹配检查。如果知识库中规则数目很大，显然效率会降低。(3)控制策略不灵活：产生式系统往往采用单一的控制策略，如顺序考察规则库中的每一条规则，这同样会降低系统的效率。,2022/12/11,中国矿业大学计算机学院,25,(3)控制策略不灵活：产生式系统往往采用单一的控制策略，如顺序考察规则库中的每一条规则，这同样会降低系统的效率。(4)知识表示形式单一：产生式系统比较适合于表示非结构化的知识，对于结构化的知识可能用语义网络或框架或面向对象的表示方式更为合适。,注意：以纯粹的产生式系统表示复杂的知识结构比较困难，因此发展了一系列知识的结构化表示方法，如框架和语义网络等。知识以这种形式表示的系统，称为基于知识的系统。,2022/12/11,中国矿业大学计算机学院,26,例题,动物识别系统的规则库。这是一个用以识别虎、金钱豹、斑马、长颈鹿、企鹅、驼鸟、信天翁等7种动物的产生式系统。为了实现对这些动物的识别，该系统建立了如下规则库：,R1: IF 该动物有毛 THEN 该动物是哺乳动物R2: IF 该动物有奶 THEN 该动物是哺乳动物R3: IF 该动物有羽毛 THEN 该动物是鸟R4: IF 该动物会飞 AND会下蛋 THEN 该动物是鸟R5: IF 该动物吃肉 THEN 该动物是食肉动物R6: IF 该动物有犬齿 AND有爪AND 眼盯前方 THEN 该动物食肉动物,2022/12/11,中国矿业大学计算机学院,27,R7: IF 该动物是哺乳动物 AND有蹄 THEN 该动物是有蹄类动物R8: IF 该动物是哺乳动物 AND 是嚼反刍动物 THEN 该动物是动物有蹄类动物R9: IF 该动物是哺乳动物 AND 是食肉动物 AND 是黄褐色 AND 身上有暗斑点 THEN 该动物是金钱豹 R10: IF 该动物是哺乳动物 AND 是食肉动物 AND 是黄褐色 AND 身上有黑色条纹 THEN 该动物是虎R11: IF 该动物是有蹄类动物 AND 有长脖子 AND 有长腿 AND 身上有暗斑点 THEN 该动物是长颈鹿,2022/12/11,中国矿业大学计算机学院,28,R12: IF 该动物是有蹄类动物 AND 身上有黑色条纹 THEN 该动物是斑马R13: IF 该动物是鸟 AND 有长脖子 AND 有长腿 AND 不会飞 AND 有黑白二色 THEN 该动物是驼鸟 R14: IF 该动物是鸟 AND 会游泳 AND 不会飞 AND 有黑白二色 THEN 该动物是企鹅R15: IF 该动物是鸟 AND 善飞 THEN 该动物是信天翁,2022/12/11,中国矿业大学计算机学院,29,在上例中, R1-R15分别是对各产生式规则所做的编号,以便于对它们的引用. 同时,我们还看出,虽然该系统是用来识别7种动物的,但它并没有简单地设计7条规则,而是设计了15条.识别动物基本想法是: 首先根据一些比较简单的条件,如“有毛发”“有羽毛”“会飞”等对动物进行比较粗的分类,如“哺乳动物”“鸟类”等, 然后随着条件的增多,逐步缩小分类范围,最后给出分别识别7种动物的规则.这样做有下列好处:(1)当已知的事实不完全时,虽不能推出最终结论,但可以得到分类结果;(2)当需要增加对其它动物(如牛马等)的识别时,规则中只需增加关于这些动物个性方面的知识,如R9-R15那样,而对R1-R10可直接利用,这样增加的规则就不会太多;(3)由上述规则,很容易形成各种动物的推理链,例如虎及长颈鹿的推理过程如图所示.,2022/12/11,中国矿业大学计算机学院,30,图: 虎及长颈鹿的推理过程,2022/12/11,中国矿业大学计算机学院,31,作业:,产生式系统由哪几个部分组成? 它们的作用是什么?可以从哪些角度对产生式系统进行分类? 阐述各类产生式系统的特点.简述产生式系统的优缺点.,
