《产生式系统 》PPT课件.ppt

2019/7/2,1,第五章 产生式系统,产生式表示方法 产生式系统基本原理 产生式系统与图搜索 产生式系统应用,2019/7/2,2,第五章 产生式系统,产生式系统的体系结构是 实现图搜索的理想程序结构，产生式已是人工智能系统的一种最典型最普遍的结构形式。 许多专家系统和机器学习系统都是用产生式系统实现的。从结构形式上看很多人工智能系统都是产生式系统。,2019/7/2,3,第五章 产生式系统,产生式表示方法 产生式系统基本原理 产生式系统与图搜索 产生式系统应用,2019/7/2,4,产生式表示法,产生式 产生式一词是从波斯特机中借用来的。波斯特机是一种自动机，它是根据串替换规则提出的一种计算模型。其中的每一条规则就叫一个产生式。也称产生式规则，简称规则。 这里产生式就是前面讨论过的操作、逻辑蕴含式、推理规则以及各种关系（包含经验性联想）的一种逻辑抽象。,2019/7/2,5,产生式表示法,产生式的一般形式为： 前件后件（情况行为） 前件是前提，规则的执行条件。 后件是结论或动作，规则体。 产生式规则的语义：如果前提满足，则可得结论或者执行相应的动作，即后件由前件触发。 从基本事实到结论之间的复杂推理可以借助中间结论形成小型简单产生式。,2019/7/2,6,产生式表示法,例：一条知识的原始形态是 R: ( (A B) (C D) (E F) G)=S 引入中间结论S1，S2，形成一些小型的产生式: R1： A B =S1 R2： C D =S1 R3： E F =S2 R4： S1 G =S R5: S1 S2 =S,2019/7/2,7,产生式表示法,给定一组事实之后可用匹配技术寻找可用产生式，其基本思想是将已知事实代入产生式的前件，若前件为真，则该产生式是可用的。 提高匹配效率的方法 索引匹配。为状态建立可用产生式索引表，减少可用产生式搜索范围。 分层匹配。将产生式分成若干层或组，按一定特征进行分层搜索。 过滤匹配。边匹配边 按某些附加特征或参数对可用产生式进行精选。,2019/7/2,8,产生式表示法,如果一组事实可以同时使几个产生式前提为真，常用以下方法进行选择（冲突消解策略）： 将所有产生式排序，选最早匹配成功的一个，不管其余的产生式； 在所有匹配成功的产生式中取最强的，即前提条件最多或情况元素最多者； 最近用过的产生式优先（或反之）； 给情况元素以不同的优先权； 使用估计函数f(x)排序； 利用上下文限制。,2019/7/2,9,产生式表示法,在产生式系统中，从前提到结论通常也是一棵与或树。 合取，与节点：一个产生式的前提包含了几个事实，那么它的结论对应这些事实的合取。 析取，或节点：一个结论可以由多个产生式得到，则这个结论对应这些产生式的析取。 每个产生式系统都隐含着许多这样的与或树。,2019/7/2,10,产生式表示法,事实,中介事实 B、C、D,产生式规则 P1、P2、P3、P4、P5,结论,2019/7/2,11,产生式表示法（例）,例 三个聪明人问题。古代有个国王想知道他的三个大王中谁最聪明，就在他们每个人前额上都画了一个点，他们都能看到别人点的颜色，但看不到别人点的颜色。国王说，你们中间至少有一个人的点式白色的。于是重复地问他们：“谁知道自己点地颜色？”三位大臣们头两次都回答说不知道。题目要求证明下一次他们全都会说“知道”，并且所有的点都是白色。,2019/7/2,12,产生式表示法（例）,分析： 这类问题的特点是有有限个受试者，每个人对问题都只有部分了解，无法直接求解。但在推理过程中每个人又可以从别人那里获得新的知识，重新进行推理。可以用产生式来表达推理过程中所用到的各种知识。,2019/7/2,13,产生式表示法（例）,状态集合表示： 用x1,x2,x3表示三个人点的颜色，1表示白色，0表示非白色。 X(x1,x2,x3)表示颜色分布状态。 全部可能的状态集合(可能界PW0)： (0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1) 实际给定的状态为现实界X0 (x10,x20,x30) 用排除法找到X0 。,2019/7/2,14,产生式表示法（例）,排除过程： 第一次，大臣只知道至少有一个人是白点，排除X0(0,0,0)状态。这时如果有人看到两个非白点，根据排除的状态可推知自己是白点。 第二次大臣根据没有一个人知道自己点颜色的事实推知至少两人为白点。排除(0,0,1)(0,1,0)(1,0,0)状态。这时如果有人看到一个非白点，根据排除后得到的状态可推知自己的点是白的。 第三次，大臣们根据仍无人知道自己点颜色的新事实推知没有一个非白点出现，即X0(1,1,1)。于是三人都知道自己点的颜色是白的。,2019/7/2,15,产生式表示法（例）,引入中介状态并定义下述符号： Si i大臣看到的非白点数； Wi i大臣猜出自己点的颜色否。如果他宣布已知道自己点的颜色，为1，否则为0； nX0中白点的个数。,2019/7/2,16,产生式表示法（例）,(1)(已知)(n=1) X0 (0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)； (2)(有人看见两个非白点)(n=1) (Si=2) =(Wi=1),(i=1,2,3,下同)； (3)( i ) (Wi=1) (n=1) = (n=1) ； (4) (n=1) = ( i ) (Wi=1) ； (5) ( i ) (Wi=0) (n=1) = (n=2) ; (6) (n=2) X0 (0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)； (7) (有人看见一个非白点)(n=2) (Si=1) =(Wi=1); (8) ( i ) (Wi=1) (n=2) = (n=2) ; (9) (n=2) = ( i ) (Wi=1); (10) ( i ) (Wi=0) (n=2) = (n=3); (11) (n=3) X0 (1,1,1)； (12) (n=3) = ( i ) (Wi=1).,2019/7/2,17,产生式表示法（例）,上述结果可以推广到更一般的情况：设有m个大臣，国王说至少有l个人的点是白色的，则有下述产生式： (1) (n=l) X0 x|x中的白点数=l； (2) (n=l) (Si=2) =(Wi=1),(i=1,2,m,下同)； (3)( i ) (Wi=1) (n=l) = (n=l) ； (4) (n=l) = ( i ) (Wi=l) ； (5)( i ) (Wi=0) (n=l) (l (n=l1) ; (6)( i ) (Wi=0) (n=l) (lm-1)= (nm)。,2019/7/2,18,第五章 产生式系统,产生式表示方法 产生式系统基本原理 产生式系统与图搜索 产生式系统应用,2019/7/2,19,产生式系统基本原理,组成和分类 运行过程 常用算法,2019/7/2,20,产生式系统基本原理（组成和分类）,产生式系统结构,产生式规则库(知识库),推理机（控制）,全局数据库,2019/7/2,21,产生式系统基本原理（组成和分类）,组成 全局数据库人工智能系统的数据结构中心。是一个动态数据结构，用来存放初始事实数据、中间结构和最后结果。对应叙述性知识。 产生式规则库作用在全局数据库上的一些规则的集合。每条规则都有一定的条件，若全局数据库中内容满足这些条件可调用这条规则。对应过程性知识。 推理机负责产生式规则的前提条件测试或匹配，规则的调度和选取，规则体的解释和执行。对应控制性知识。,2019/7/2,22,产生式系统基本原理（组成和分类）,例 旅行推销员问题。求从A城出发，经过其他城市一次且仅一次，最后回到A城的最小费用路线。城市之间的交通费用标在相应的联线上。建立产生式系统。,2019/7/2,23,产生式系统基本原理（组成和分类）,（1）全局数据库（已访问过的城镇名称序列）。约束条件是除城镇A之外其他名称不得在序列中重复出现；只有所有的名称都在序列中出现后，城镇A才能重复出现。 （2）规则集如下表所示。 （3）推理： （A） （AB） （ABE） （4）终止条件序列始于A，终止于A，其中包含其他所有城镇一次，且费用最少。 （5）各种搜索策略选择规则，如广度优先搜索，最好优先搜索等。,R2,R5,2019/7/2,24,产生式系统基本原理（组成和分类）,规则集,2019/7/2,25,产生式系统基本原理（组成和分类）,与一般分级组织的计算机软件相比具有特点： 全局数据库的内容可以为所有规则所访问，没有任何部分是专为某一规则建立的，这种特性便于模仿智能行为中的强数据驱动。 规则本身不调用其他规则。规则之间的联系必须通过全部数据库联系。 全局数据库、规则和推理机之间相对独立，这种积木式结构便于整个系统增加和修改知识。,2019/7/2,26,产生式系统基本原理（组成和分类）,分类体系（尼尔逊） 按搜索策略分 不可挽回（irreversible）的产生式系统 试探性的（Tentative）产生式系统 回溯式（Backing）产生式系统 图搜索式（Graph Search）产生式系统 按搜索方向分 向前产生式系统（Forward Production System） 向后产生式系统（Backward Production System） 双向产生式系统（Bidirectional Production System） 两种特殊的产生式系统 可交换的（Commutative）产生式系统 可分解的（Decomposable）产生式系统,2019/7/2,27,产生式系统基本原理,组成和分类 运行过程 控制策略与常用算法,2019/7/2,28,产生式系统基本原理（运行过程）,推理机一次运行过程,2019/7/2,29,产生式系统基本原理（运行过程）,产生式系统运行过程 实际的产生式系统，目标条件往往要经过多步推理才能满足或者证明问题无解。产生式系统的运行过程就是推理机不断的运用规则库中的规则，作用于动态数据库，不断进行推理并不断检测目标条件是否被满足的过程。 产生式系统运行过程是从初始事实出发，寻求到达目标条件的通路的过程。所以也是一个搜索的过程。,2019/7/2,30,产生式系统基本原理,组成和分类 运行过程 常用算法,2019/7/2,31,产生式系统基本原理（常用算法）,推理方式 正向推理 从初始事实数据出发，正向使用规则进行推理，朝目标方向前进。又称为前向推理、正向链、数据驱动的推理。 反向推理 从目标出发，反向使用规则进行推理，朝初始事实或数据方向前进。又称反向推理、反向链、目标驱动的推理。,2019/7/2,32,产生式系统基本原理（常用算法）,正向推理算法 步1 将初始事实/数据置入动态数据库； 步2 用动态数据库中的事实匹配目标条件，若目标条件满足，推理成功，结束。 步3 用规则库中各规则的前提匹配动态数据库中的事实，将匹配成功的规则组成待用规则集。 步4 若待用规则集为空，则运行失败，退出。 步5 将待用规则集中各规则的结论加入动态数据库，或者执行其动作，转步2。,2019/7/2,33,产生式系统基本原理（常用算法）,反向推理算法 步1 将初始事实/数据置入动态数据库，将目标条件置入目标链； 步2 若目标链为空，则推理成功，结束。 步3 取出目标链中第一个目标，用动态数据库中的事实同其匹配，若匹配成功，转步2。 步4 用规则集中的各规则的结论同该目标匹配，若匹配成功，则33将第一个匹配成功且未用过的规则的前提作为新的目标，并取代原来的父目标加入目标链，转步3。 步5 若该目标是初始目标，则推理失败，退出。 步6 将该目标的父目标移回目标链，取代该目标及其兄弟目标，转步3。,2019/7/2,34,产生式系统基本原理（常用算法）,例：动物识别系统的产生是系统描述及求解。 规则： r1： IF 该动物有毛发 THEN 该动物是哺乳动物 r2： IF 该动物有奶 THEN 该动物是哺乳动物 r3： IF 该动物有羽毛 THEN 该动物是鸟 r4： IF 该动物会飞 AND 会下蛋 THEN 该动物是鸟 r5： IF 该动物吃肉 THEN 该动物是食肉动物 r6： IF 该动物有犬齿 AND 有爪 AND 眼盯前方 THEN 该动物是食肉动物动物,2019/7/2,35,产生式系统基本原理（常用算法）,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 该动物是长颈鹿 r12：IF 该动物有蹄类动物 AND 身上有黑色条纹 THEN 该动物是斑马,2019/7/2,36,产生式系统基本原理（常用算法）,r13： IF 该动物是鸟 AND 有长脖子 AND 有长腿 AND 不会飞 AND 有黑白二色 THEN 该动物是鸵鸟 r14： IF 该动物是鸟 AND 会游泳 AND 不会飞 AND 有黑白二色 THEN 该动物是企鹅 r15：IF 该动物是鸟 AND 善飞 THEN 该动物是信天翁,2019/7/2,37,产生式系统基本原理（常用算法）,初始事实： f1：某动物有毛发。 f2：吃肉。 f3：黄褐色。 f4：有黑色条纹 目标条件为：该动物为什么？,2019/7/2,38,产生式系统基本原理（常用算法）,2019/7/2,39,产生式系统基本原理（常用算法）,2019/7/2,40,第五章 产生式系统,产生式表示方法 产生式系统基本原理 产生式系统与图搜索 产生式系统应用,2019/7/2,41,产生式系统与图搜索,产生式系统与图搜索对比,2019/7/2,42,第五章 产生式系统,产生式表示方法 产生式系统基本原理 产生式系统与图搜索 产生式系统应用,2019/7/2,43,产生式系统的应用实例,基于消解原理的产生式系统 基于自然演绎法的产生式系统 基于专用知识的产生式系统,2019/7/2,44,基于消解原理的产生式系统,消解原理的产生式系统 全局数据库：子句集合S 产生式规则集：一般形式是消解 控制系统 终止条件：NIL S 搜索策略：是个可交换的系统，使用各个具体的消解与先后顺序无关，采用不可挽回的控制策略。,2019/7/2,45,基于消解原理的产生式系统,过程RESOLUTION 步1 CLAUSES S； 步2 until NIL是CLAUSES中的元素为止，do； 步3 begin 步4 在CLAUSES中选取两个可消解的子句Ci和Cj； 步5 计算Ci和Cj的消解式Rij； 步6 把Rij并入到CLAUSES中； 步7 end。,2019/7/2,46,基于消解原理的产生式系统,控制策略 广度优先搜索策略 相当于水平浸透法。完备的但效率低。 支持集消解策略 反向产生式系统。完备的，但不一定得到最优解。 启发式搜索策略 利用消解原理求解问题的经验，设计启发函数。,2019/7/2,47,补充：解树代换的一致性（一）,设有一个代换集u1,u2,，un，其中每个ui都是一个代换ti1/ vi1, ti2/ vi2,， tim(i)/ vim(i) 又设U1v11, , vim(1),， vn1, , vnm(n)（所有下边的变量） U2t11, , tim(1),， tn1, , tnm(n) （所有上边的项） 定义：代换集u1,u2,，un是一致的，当且仅当U1和U2是可合一的。 定义：u1,u2,，un的合一复合U是U1和U2的最一般合一。 解树上所有代换是一致的，则该问题有解，最后的代换是合一复合U。,2019/7/2,48,补充：解树代换的一致性（二）,例设有一个代换集u1,u2，其中 u1f(g(x1)/x3,f(x2)/x4 U1和U2是可合一的，其最一般合一是： Uf(g(x1)/x3,f(g(x1)/x4， g(x1)/x2,u2x4/x3,g(x1)/x2 U1=x3, x4, x3 ,x2 U2=f(g(x1) f(x2) ,x4 ,g (x1),2019/7/2,49,产生式系统的应用实例,基于消解原理的产生式系统 基于自然演绎法的产生式系统 基于专用知识的产生式系统,2019/7/2,50,基于自然演绎法的产生式系统,消解原理产生式系统特点 优点：形式单一，处理规则简单。 缺点：太一般化，丢失了原公式重要语义信息，对应用启发搜索系统和人机交互带来了困难；组合爆炸，难以直接使用。 自然演绎法 保持专家知识原始的逻辑形态，保留了控制信息。 推理规则复杂，但便于设计启发函数。 推理过程直观，便于理解。,2019/7/2,51,基于自然演绎法的产生式系统,规则基产生式系统 事实 用非蕴含形式谓词公式表示， 规则 用蕴含形式表示 F规则 前向推理系统中应用 B规则 后向推理系统中应用,2019/7/2,52,1、基于规则的向前推理系统（一）,基本原理 从代表初始事实的谓词公式F0出发通过一组F规则F1，F2来证明目标公式G成立。 初始事实F0 任意谓词公式 前束范式表示；运用Skolem函数消去存在量词；省去全称量词；得到任意与或型事实表达式，改名，使各主要合取项的变量应不相同。 与或图表示：析取部分用与节点表示合取部分用或节点表示,2019/7/2,53,1、基于规则的向前推理系统（二）,F规则 形如 L=W L为单一文字 W为任意与或型谓词公式；W中用Skolem消去存在量词，变元只受全称量词约束；改名，使不同规则具有不同变元，规则变元与事实变元也不同。 复杂规则化为简单规则。,2019/7/2,54,1、基于规则的向前推理系统（三）,终止条件 用目标谓词G表示 G为文字的析取式（文字都为目标文字）；用Skolem函数消去全称量词；消去存在量词；改名，使同一变元在各目标文字、规则、事实中最多出现一次。 推理基本过程 不断将规则L=W利用匹配弧连接在与或图的L叶结点上；目标文字G本身可看作G =G作用在与或图上； 一致解树各个叶结点都终止在目标节点，成功终止。,2019/7/2,55,1、基于规则的向前推理系统（四）,例:命题逻辑中一个定理证明问题 构造一个向前的规则基推理系统来求解。 事实 F0： 规则 F1： F2 ： F3： 目标 G：,2019/7/2,56,1、基于规则的向前推理系统（五）,2019/7/2,57,1、基于规则的向前推理系统（六）,例:谓词逻辑中一个定理证明问题 自然数都是大于0的整数 所有整数不是偶数就是奇数 偶数的一半是整数 所有自然数不是奇数就是一半为整数的数。 构造一个向前的规则基推理系统来求解,2019/7/2,58,1、基于规则的向前推理系统（六）,一、预处理F0为事实表达式方法： （1）将公式化称任意与或型前束范式，每个否定词仅管 辖一个谓词； （2）用Skolem函数去掉存在量词并改名使主合取项之间无相同变量； （3）隐去全称量词。,2019/7/2,59,1、基于规则的向前推理系统（七）,二、预处理F1 F2为F规则方法： （1）暂时消去； （2）将公式化为前束范式，一个否定词管辖一个谓词； （3）用Skolem函数消去存在量词； （4）改变变元名称使其与其他公式不同； （5）恢复蕴含式。,2019/7/2,60,1、基于规则的向前推理系统（八）,三、处理目标G： （1）用Skolem函数消去全称量词； （2）隐去存在量词。,2019/7/2,61,1、基于规则的向前推理系统（九）,2019/7/2,62,2、基于规则的向后推理系统（一）,基本原理 从代表目标的谓词公式出发，通过一组B规则证明事实公式成立。 目标 任意谓词公式，Skolem函数消去全称量词；隐去存在量词；改名，公式中主要析取项的变元应不相同。 与或图表示：与节点对应合取；或节点对应析取；根节点上任何后裔都为子目标。,2019/7/2,63,2、基于规则的向后推理系统（二）,B规则 W=L； L为单一文字； W为任意与或型谓词公式，变元受全称量词约束，变元改名。 复杂规则化为简单规则。,2019/7/2,64,2、基于规则的向后推理系统（三）,推理过程 目标谓词公式的与或图中有一节点标为L，且可与L合一，则可将规则作用在该与或树上。其结果使在与或树上从L引出一条匹配弧，连接一个以L为根，表示W的与或图， 为L与L的最一般合一。 终止条件 当与或树的一致解树各个叶节点都终止在事实节点时，此产生式系统成功终止。,2019/7/2,65,2、基于规则的向后推理系统（四）,例:基于规则的向后推理系统。 给定事实为: Fido是狗 Fido不会吠叫 Fido会摇尾巴 Myetle会咪咪叫,2019/7/2,66,2、基于规则的向后推理系统（五）,已知规则为 目标：存在猫不怕狗的现象，即,2019/7/2,67,2、基于规则的向后推理系统（六）,2019/7/2,68,3、F系统和B系统的对比（一）,2019/7/2,69,3、F系统和B系统的对比（一）,2019/7/2,70,产生式系统的应用实例,基于消解原理的产生式系统 基于自然演绎法的产生式系统 基于专用知识的产生式系统,2