人工智能幻灯片213产生式表示法

《人工智能幻灯片213产生式表示法》由会员分享，可在线阅读，更多相关《人工智能幻灯片213产生式表示法（31页珍藏版）》请在金锄头文库上搜索。

1、2019/4/19,中国矿业大学计算机学院,1,2.3 产生式表示法,第2章 知识表示,2.1 概 述,2.2 谓词逻辑表示法,2019/4/19,中国矿业大学计算机学院,2,产生式系统(Production System): 1943年,由珀斯特(Post)提出，他用这种规则对符号串作替换运算。 1965年美国的纽威尔和西蒙利用这种原理建立了认知模型。同年，斯坦福大学设计第一个专家系统DENDRAL时，就采用产生式系统的结构。 产生式系统是目前已建立的专家系统中知识表示的主要手段之一,如MYCIN、CLIPS/JESS系统等。 在产生式系统中，把推理和行为的过程用产生式规则表示，所以又称基于

2、规则的系统。,2.3 产生式表示法,2019/4/19,中国矿业大学计算机学院,3,一般地，一个规则由前项和后项两部分组成。前项表示前提条件，各个条件由逻辑连接词（合取、析取等）组成各种不同的组合。后项表示当前提条件为真时，应采取的行为或所得的结论。产生式系统中每条规则是一个“条件结论”或“前提结论”的产生式，起简单形式为： IF前提THEN结论 IF条件THEN动作,2.3.1 规则的表示,2019/4/19,中国矿业大学计算机学院,4,为了严格地描述产生式，下面用巴科斯范式给出它的形式描述和语义： = =| =| = And (And ) | Or (Or ) =(,),2019/4/19

3、,中国矿业大学计算机学院,5,1. 产生式规则 通常用于表示事物间的因果关系； 【基本形式】 IF P then Q 或 P Q，其中 P表示规则的条件（或称前提）； 谓词、多元组、常量、变量、关系运算 Q表示规则激活时应该执行的动作（或得到的结论）； 激活规则条件P满足； 【规则分类】 前提-结论型 条件-动作型,2019/4/19,中国矿业大学计算机学院,6,1. 产生式规则 前提-结论型规则（P Q） 例如，关于动物世界的产生式系统中有规则 IF 动物是哺乳动物，且吃肉； Then 这种动物是食肉动物。 或形式化为： Mammal(x) Eat(x,Meat)Carnivore(x) (

4、Mammal,?x) (Eat,?x,Meat) (Carnivore,?x) P谓词、多元组、关系表达式和真值函数的任意 组合； 不要求遵从一阶谓词演算的表示形式 变量视为隐含地受全称量词约束； Q结论 任意数据结构，如向量、数组、表格等。,2019/4/19,中国矿业大学计算机学院,7,1. 产生式规则 条件-动作型规则（P Q） P谓词、多元组、关系表达式和真值函数的任意 组合； 不要求遵从一阶谓词演算的表示形式 变量可视为隐含地受全称量词约束； Q动作，任意操作函数 操作综合数据库； 屏幕、图像、文件操作； 执行各种预定的计算功能； 例如： x-1 1 null(y) x:=0,201

5、9/4/19,中国矿业大学计算机学院,8,1. 产生式规则 前提-结论型规则（P Q） 条件-动作型规则（P Q）,左部（前件）,右部（后件）,谓词,关系表达式,真值函数,2019/4/19,中国矿业大学计算机学院,9,1确定性和不确定性规则知识的产生式表示 确定性规则知识可用前面介绍的产生式的简单形式表示即可。 不确定性规则知识对基本形式作一定的扩充，用如下形式表示 PQ （可信度） 或者 IF P THEN Q （可信度） 其中，P是产生式的前提或条件，用于指出该产生式是否是可用的条件；Q是一组结论或动作，用于指出该产生式的前提条件P被满足时，应该得出的结论或因该执行的操作。这一表示形式主

6、要在不确定推理中当已知事实与前提中的条件不能精确定匹配时，只要按照“可信度”的要求达到一定的相似度，就认为已知事实与前提条件匹配，再按照一定的算法将这种可能性（或不确定性）传递到结论。,2.3.2 事实的表示,2019/4/19,中国矿业大学计算机学院,10,2确定性和不确定性事实性知识的产生式表示 确定性事实性知识一般使用三元组 （对象，属性，值）或 （关系，对象1，对象2） 来表示，其中对象就是语言变量，这种表示的机器内部实现就是一个表。如事实“老李年龄是35岁”，便可以表示成 （Lee， Age， 35） 其中，Lee是事实性知识涉及的对象，Age是该对象的属性，而35岁是该对象属性的值

7、。而老李、老张是朋友，可表示成 （Friend， Lee， Zhang ）,2019/4/19,中国矿业大学计算机学院,11,而有些事实性知识带有不确定性和模糊性，若考虑不确定性，这种知识就可以用四元组的形式表示如下 （对象，属性，值，不确定度量值）或 （关系，对象1，对象2，不确定度量值） 如不确定性事实性知识 “老李年龄可能是35岁”，这里老李是35岁的可能性取90%，便可以表示成 （Lee， Age， 35，0.9） 而老李、老张是朋友的可能性不大，这里老李、老张是朋友的可能性取20%，可表示成 （Friend， Lee， Zhang，0.2 ）,2019/4/19,中国矿业大学计算机学

8、院,12,2.3.3 产生式系统的组成部分,产生式系统一般由三个基本部分组成：规则库、综合数据库和推理机。它们之间的关系如图所示。,产生式系统的基本结构,2019/4/19,中国矿业大学计算机学院,13,用于描述某领域内知识的产生式集合，是某领域知识(规则)的存储器，其中的规则是以产生式形式表示的。规则库中包含着将问题从初始状态转换成目标状态(或解状态)的那些变换规则。 规则库是专家系统的核心，也是一般产生式系统赖以进行问题求解的基础，其中知识的完整性和一致性、知识表达的准确性和灵活性以及知识组织的合理性，都将对产生式系统的性能和运行效率产生直接的影响。,1.规则库:,2019/4/19,中国

9、矿业大学计算机学院,14,综合数据库又称为事实库，用于存放输入的事实、从外部数据库输入的事实以及中间结果(事实)和最后结果的工作区。当规则库中的某条产生式的前提可与综合数据库中的某些已知事实匹配时，该产生式就被激活，并把用它推出的结论放入综合数据库中，作为后面推理的已知事实。 显然，综合数据库的内容是在不断变化的，是动态的。,2.综合数据库:,2019/4/19,中国矿业大学计算机学院,15,推理机是一个或一组程序，用来控制和协调规则库与综合数据库的运行，包含了推理方式和控制策略。控制策略的作用就是确定选用什么规则或如何应用规则。 通常从选择规则到执行操作分3步完成：匹配、冲突解决和操作。,3

10、.推理机:,(1) 匹配：匹配就是将当前综合数据库中的事实与规则中的条件进行比较，如果相匹配，则这一规则称为匹配规则。,2019/4/19,中国矿业大学计算机学院,16,(2) 冲突解决：冲突解决的策略有很多种 , 其中专一性排序、规则排序、规模排序和就近排序是比较常见的冲突解决策略。,(3) 操作：操作就是执行规则的操作部分。经过操作以后，当前的综合数据库将被修改，其他的规则有可能将成为启用规则。,因为可能同时有几条规则的前提条件与事实相匹配，究竟选哪一条规则去执行呢？这就是规则冲突解决。通过冲突解决策略选中的在操作部分执行的规则称为启用规则。,2019/4/19,中国矿业大学计算机学院,1

11、7,2. 产生式系统组成 3个部分组成： 规则库； 综合数据库； 推理机；,推理机,规则库,综合数据库,产生式系统的问题描述,控制应用规则推出解答的全过程,2019/4/19,中国矿业大学计算机学院,18,3. 应用实例八数码游戏 综合数据库 规则库 冲突解决策略,2019/4/19,中国矿业大学计算机学院,19,2.3.4 产生式系统的分类,按产生式所表示的知识是否具有确定性分为：确定性产生式系统和不确定性产生式系统； 按推理机的推理方向分为：正向、反向和双向推理产生式系统。 按规则库及综合数据库的性质与结构特征分为：可交换的产生式系统、可分解的产生式系统和可恢复的产生式系统。,2019/4

12、/19,中国矿业大学计算机学院,20, 按推理方向正向、逆向和双向产生式系统（前提-结论型）： (1) 正向产生式系统这种系统通过检查前提是否满足当前问题状态（与综合数据库内容匹配）来决定规则的激活，由此实现正向推理方式，并推动问题求解从初始状态向目标状态逼近。以正向推理方式使用的规则称为正向规则，或F规则（Forward rule）。 (2) 逆向产生式系统这种系统通过检查结论是否满足当前问题状态来决定规则的激活，由此实现逆向推理方式，并推动问题求解从目标状态向初始状态逼近。以逆向推理方式使用的规则称为逆向规则，或B规则（Backward rule）。 (3) 双向产生式系统这种系统以双向推

13、理方式（正、逆向同时进行）去求解问题。双向系统的综合数据库必须有两套数据结构，分别描述从初始状态出发推得的中间状态正向状态，和从目标状态出发推得的中间状态逆向状态。换言之，综合数据库 = 正向状态描述 + 逆向状态描述，以便于F、B规则分别作用于不同的状态描述。,2019/4/19,中国矿业大学计算机学院,21,可交换的产生式系统 如果一个产生式系统对规则的使用次序是可交换的，那么无论先使用哪一条规则，都可以达到目的，即规则的使用次序对问题的最终求解是无关紧要的。我们称这样的产生式系统为可交换的产生式系统。,可分解的产生式系统 把一个规模较大且较复杂的问题分解为若干个规模较小且较简单的子问题，

14、然后对每个子问题分别进行求解，这是人们求解问题时常用到的方法，可分解的产生式系统就是基于这一思想提出来的。,2019/4/19,中国矿业大学计算机学院,22,可恢复的产生式系统 在可交换产生式系统中，要求每条规则的执行只能为综合数据库增添新的内容，且不能删除和修改综合数据库已有的内容。这一要求是很强的，在许多规则的设计中难以达到。因此就需要产生式系统具有回溯功能，一旦问题求解到某一步发现无法继续下去时，就撤销在此之前得到的某些结果，恢复到先前的某个状态，然后选用别的规则继续求解。在问题求解过程中既可以对综合数据库添加新内容、又可删除或修改老内容的产生式系统称为可恢复的产生式系统。,2019/4

15、/19,中国矿业大学计算机学院,23,2.3.5 产生式系统的优缺点,(1)模块化：规则使得知识容易封装并不断补充。 (2)解释机制：通过规则容易建立解释机，这是因为一个规则的前件指明了激活这个规则的条件。通过跟踪已触发的规则，解释机可以得到推出某个结论的推理链。 (3)类似人类认识过程：规则似乎是模拟人类怎样解决问题的一个自然方法。 因此，产生式方法是当今最流行的专家系统设计模式。,优点:,2019/4/19,中国矿业大学计算机学院,24,缺点或不足:,(1)难以扩展：尽管规则形式上相互独立，但实际问题中往往彼此是相关的。这样当知识库不断扩大时，要保证新的规则和已有的规则没有矛盾就会越来越困

16、难，知识库的一致性越来越难以实现。 (2)规则选择效率较低：在推理过程中，每一步都要和规则库中的规则做匹配检查。如果知识库中规则数目很大，显然效率会降低。 (3)控制策略不灵活：产生式系统往往采用单一的控制策略，如顺序考察规则库中的每一条规则，这同样会降低系统的效率。,2019/4/19,中国矿业大学计算机学院,25,(3)控制策略不灵活：产生式系统往往采用单一的控制策略，如顺序考察规则库中的每一条规则，这同样会降低系统的效率。 (4)知识表示形式单一：产生式系统比较适合于表示非结构化的知识，对于结构化的知识可能用语义网络或框架或面向对象的表示方式更为合适。,注意：以纯粹的产生式系统表示复杂的知识结构比较困难，因此发展了一系列知识的结构化表示方法，如框架和语义网络等。知识以这种形式表示的系统，称为基于知识的系统。,2019/4/19,中国矿业大学计算机学院,26,例题,动物识别系统