基于产生式规则的机器推理

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,人工智能,*,第,6,章 基于产生式规则的机器推理,第,6,章基于产生式规则的机器推理,6.1,产生式规则,6.2,产生式系统,9/13/2024,2,人工智能,6.1,产生式规则,6.1.1,产生式规则,6.1.2,基于产生式规则的推理模式,9/13/2024,3,人工智能,6.1.1,产生式规则（,1,）,产生式,产生式（,Production,）一词从波斯特机中借用来的。波斯特机是一种自动机，它是根据串替换规则提出的一种计算模型。其中的每一条规则就叫一个产生式。也称产生式规则，简称规则。,这里产生式就是前面讨论过的操作（二阶梵塔问题，猴子摘香蕉问题等）、逻辑蕴含式、推理规则以及各种关系（包含经验性联想）的一种逻辑抽象。,9/13/2024,4,人工智能,6.1.1,产生式规则,（,2,）,产生式的一般形式为：,前件,后件（情况,行为）,前件是前提，规则的执行条件。,后件是结论或动作，规则体。,产生式规则的语义：如果前提满足，则可得结论或者执行相应的动作，即后件由前件触发。,一个产生式规则就是一条知识，用产生式不仅可以进行推理，也可以实现操作。,9/13/2024,5,人工智能,6.1.1,产生式规则,（,3,）,产生式规则例子,如果银行存款利率下调，那么股票价格上涨。,如果炉温超过上限，则立即关闭风门。,如果发烧、呕吐并且出现黄疸，那么得了肝炎。（,0.7,）,如果键盘突然失灵，且屏幕上出现怪字符，则是病毒发作。,9/13/2024,6,人工智能,6.1.1,产生式规则,（例）,例,三个聪明人问题。古代有个国王想知道他的三个大,臣,中谁最聪明，就在他们每个人前额上都画了一个点，他们都能看到别人点的颜色，但看不到自己点的颜色。国王说，你们中间至少有一个人的点是白色的。于是重复地问他们：“谁知道自己点的颜色？”三位大臣们头两次都回答说不知道。题目要求证明下一次他们全都会说“知道”，并且所有的点都是白色。,9/13/2024,7,人工智能,6.1.1,产生式规则,（例）,分析,：,这类问题的特点是有有限个受试者，每个人对问题都只有部分了解，无法直接求解。但在推理过程中每个人又可以从别人那里获得新的知识，重新进行推理。可以用产生式来表达推理过程中所用到的各种知识。,9/13/2024,8,人工智能,6.1.1,产生式规则,（例）,状态集合表示：,用,x,1,x,2,x,3,表示三个人点的颜色，,1,表示白色，,0,表示非白色。,X,(x,1,x,2,x,3,),表示颜色分布状态。,全部可能的状态集合,(,可能界,PW,0,),：,(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1),实际给定的状态为,现实界,X,0,(x,10,x,20,x,30,),用排除法找到,X,0,。,9/13/2024,9,人工智能,6.1.1,产生式规则,（例）,排除过程：,第一次，大臣只知道至少有一个人是白点，排除,X,0,=(0,0,0),状态。,这时如果有人看到两个非白点，根据排除的状态可推知自己是白点。,第二次大臣根据没有一个人知道自己点颜色的事实推知至少两人为白点。排除,(0,0,1)(0,1,0)(1,0,0),状态。,这时如果有人看到一个非白点，根据排除后得到的状态可推知自己的点是白的。,第三次，大臣们根据仍无人知道自己点颜色的新事实推知没有一个非白点出现，即,X,0,=(1,1,1),。,于是三人都知道自己点的颜色是白的。,9/13/2024,10,人工智能,6.1.1,产生式规则,（例）,引入中介状态并定义下述符号：,S,i, i,大臣看到的非白点数；,W,i, i,大臣猜出自己点的颜色否。如果他宣布已知道自己点的颜色，为,1,，否则为,0,；,nX,0,中白点的个数。,9/13/2024,11,人工智能,6.1.1,产生式规则,（例）,(1),(n=1) X,0, (0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1),；,(2) (n=1),(S,i,=2),=(W,i,=1),(i=1,2,3,下同,),；,(3)(,i ),(W,i,=1),(n=1) = (n=1),；,(4) (n=1) = (,i ),(W,i,=1),；,(5) (,i ),(W,i,=0),(n=1) = (n=2) ;,(6) (n=2) X,0, (0,1,1),(1,0,1),(1,1,0),(1,1,1),；,(7) (n=2),(S,i,=1),=(W,i,=1);,(8) (,i ),(W,i,=1),(n=2) = (n=2) ;,(9) (n=2) = (,i ),(W,i,=1);,(10) (,i ),(W,i,=0),(n=2) = (n=3);,(11) (n=3) X,0, (1,1,1),；,(12) (n=3) = (,i ),(W,i,=1).,9/13/2024,12,人工智能,6.1.1,产生式规则,（例）,上述结果可以推广到更一般的情况：设有,m,个大臣，国王说至少有,l,个人的点是白色的，则有下述产生式：,(1) (n=l) X,0,x|x,中的白点数,=l,；,(2) (n=l),(,S,i,=2),=(,W,i,=1),(i=1,2,m,下同,),；,(3)(,i ),(,W,i,=1),(n=l) = (n=l),；,(4) (n=l) = (, i ),(,W,i,=l),；,(5)(,i ),(,W,i,=0),(n=l),(l (n=l,1) ;,(6)(,i ),(,W,i,=0),(n=l),(l,m-1)= (n,m),。,9/13/2024,13,人工智能,6.1.2,基于产生式规则的推理模式,A,B,A,B,把有前提的操作和逻辑推理统称为推理，产生式系统中的推理是更广义的推理。,9/13/2024,14,人工智能,6.2,产生式系统,6.2.1,系统结构,6.2.2,运行过程,6.2.3,控制策略常用算法,6.2.4,程序实现,*,6.2.5,产生式系统与问题求解,9/13/2024,15,人工智能,6.2.1,系统结构（,1,）,产生式系统结构,产生式规则库,推理机,全局数据库,9/13/2024,16,人工智能,6.2.1,系统结构（,2,）,组成,产生式规则库,作用在全局数据库上的一些规则的集合。每条规则都有一定的条件，若全局数据库中内容满足这些条件可调用这条规则。一般可形成一个称为推理网络的结构图。对应过程性知识。,推理机,负责产生式规则的前提条件测试或匹配，规则的调度和选取，规则体的解释和执行。即推理机实施推理，并对推理进行控制，它也是规则的解释程序。对应控制性知识。,全局数据库,人工智能系统的数据结构中心。是一个动态数据结构，用来存放初始事实数据、中间结果和最后结果。对应叙述性知识。,9/13/2024,17,人工智能,6.2.1,系统结构（,3,）,例,旅行推销员问题。求从,A,城出发，经过其他城市一次且仅一次，最后回到,A,城的最小费用路线。城市之间的交通费用标在相应的联线上。建立产生式系统。,B,C,A,D,E,7,13,10,9,6,5,6,7,10,10,9/13/2024,18,人工智能,6.2.1,系统结构（,4,）,（,1,）,全局数据库,（已访问过的城镇名称序列）。,约束条件是除城镇,A,之外其他名称不得在序列中重复出现；只有所有的名称都在序列中出现后，城镇,A,才能重复出现。,（,2,）,规则集,如下表所示,。,（,3,）,推理,：,（,A,） （,AB,） （,ABE,）,（,4,）,终止条件,序列始于,A,，,终止于,A,，,其中包含其他所有城镇一次，且费用最少。,（,5,）,各种,搜索策略,选择规则，如广度优先搜索，最好优先搜索等。,R,2,R,5,9/13/2024,19,人工智能,6.2.1,系统结构（,5,）,规则集,规则,动作,条件,R,1,下一步到,A,系列中包含所有城镇时可用,R,2,下一步到,B,每条规则只能使用一次，即序列中已有某城镇时，不能再使用相应规则,R,3,下一步到,C,R,4,下一步到,D,R,5,下一步到,E,9/13/2024,20,人工智能,6.2.1,系统结构（,6,）,与一般分级组织的计算机软件相比具有特点：,全局数据库的内容可以为所有规则所访问，没有任何部分是专为某一规则建立的，这种特性便于模仿智能行为中的强数据驱动。,规则本身不调用其他规则。规则之间的联系必须通过全局数据库联系。,全局数据库、规则和推理机之间相对独立，这种积木式结构便于整个系统增加和修改知识。,9/13/2024,21,人工智能,6.2.2,产生式系统的,运行过程（,1,）,推理机一次运行过程,从,规则库中取出一条规则，将其前提同,当前动态数据库中的事实进行模式匹配,匹配成功否？,把该,规则的结论放入当前动态数据库；,或执行规则所规定的动作,Y,N,9/13/2024,22,人工智能,6.2.2,产生式系统的,运行过程,（,2,）,产生式系统运行过程,实际的产生式系统，目标条件往往要经过多步推理才能满足或者证明问题无解。,产生式系统的运行过程就是推理机不断的运用规则库中的规则，作用于动态数据库，不断进行推理并不断检测目标条件是否被满足的过程。,产生式系统运行过程是从初始事实出发，寻求到达目标条件的通路的过程。所以也是一个,搜索,的过程。,9/13/2024,23,人工智能,6.2.3,控制策略与常用算法,（,1,）,推理方式,正向推理,从初始事实数据出发，正向使用规则进行推理，朝目标方向前进。又称为前向推理、正向链、数据驱动的推理。,反向推理,从目标出发，反向使用规则进行推理，朝初始事实或数据方向前进。又称反向推理、反向链、目标驱动的推理。,9/13/2024,24,人工智能,6.2.3,控制策略与常用算法,（,2,）,正向推理算法一,步,1,将初始事实,/,数据置入动态数据库；,步,2,用动态数据库中的事实匹配目标条件，若目标条件满足，推理成功，结束。,步,3,用规则库中各规则的前提匹配动态数据库中的事实，将匹配成功的规则组成待用规则集。,步,4,若待用规则集为空，则运行失败，退出。,步,5,将待用规则集中各规则的结论加入动态数据库，或者执行其动作，转步,2,。,9/13/2024,25,人工智能,6.2.3,控制策略与常用算法（,3,）,若把,动态数据库,的,每一个状态,作为一个,节点,的话，则上述推理过程就是一个从初始状态到目标状态的,状态图搜索,过程。,如果把动态数据库中的,每一个事实,/,数据,作为一个,节点,的话，则上述推理过程就是一个自底向上的,与或树搜索,过程。,9/13/2024,26,人工智能,6.2.3,控制策略与常用算法,（,4,）,反向推理算法,步,1,将初始事实,/,数据置入动态数据库，,将目标条件置入目标链；,步,2,若目标链为空，则推理成功，结束。,步,3,取出目标链中第一个目标，用动态数据库中的事实同其匹配，若匹配成功，转步,2,。,步,4,用规则集中的各规则的结论同该目标匹配，若匹配成功，则将第一个匹配成功且未用过的规则的前提作为新的目标，并取代原来的父目标加入目标链，转步,3,。,步,5,若该目标是初始目标，则推理失败，退出。,步,6,将该目标的父目标移回目标链，取代该目标及其兄弟目标，转步,3,。,9/13/2024,27,人工智能,6.2.3,控制策略与常用算法,（,5,）,在产生式系统中，从前提到结论的产生式规则通常也是一棵与或树。,合取，与节点：一个产生式的前提包含了几个事实，那么它的结论对应这些事实的合取。,析取，或节点：一个结论可以由多个产生式得到，则这个结论对应这些产生式的析取。,每个产生式系统都隐含着许多这样的与或树。,9/13/2024,28,人工智能,6.2.3,控制策略与常用算法,（,6,）,F1,P1,F3,F4,F5,F6,B,C,D,A,P2,P3,P4,P5,F2,事实,中介事实,B,、,C,、,D,产生式规则,P1,、,P2,、,P3,、,P4,、,P5,结论,9/13/2024,29,人工智能,6.2.3,控制策略与常用算法,（,7,）,例,6.1,：动物分类问题的产生式系统描述及求解。,规则,：,r1,：,IF,该动物有毛发,THEN,该动物是哺乳动物,r2,：,IF,该动物有奶,THEN,该动物是哺乳动物,r3,：,IF,该动物有羽毛,THEN,该动物是鸟,r4,：,IF,该动物会飞,AND,会下蛋,THEN,该动物是鸟,r5,：,IF,该动物吃肉,THEN,该动物是食肉动物,r6,：,IF,该动物有犬齿,AND,有爪,AND,眼盯前方,THEN,该动物是食肉动物动物,9/13/2024,30,人工智能,6.2.3,控制策略与常用算法,（,8,）,r7,：,IF,该动物是哺乳动物,AND,有蹄,THEN,该动物是有蹄类动物,r8,：,IF,该动物是哺乳动物,AND,是嚼反刍动物,THEN,该动物是有蹄动物,r9,：,IF,该动物是哺乳动物,AND,是食肉动物,AND,是黄褐色,AND,身上有暗斑点,THEN,该动物是,金钱豹,r10,：,IF,该动物是哺乳动物,AND,是食肉动物,AND,是黄褐色,AND,身上有黑色条纹,THEN,该动物是,虎,9/13/2024,31,人工智能,6.2.3,控制策略与常用算法,（,9,）,r11,：,IF,该动物是有蹄类动物,AND,有长脖子,AND,有长腿,AND,身上有暗斑点,THEN,该动物是,长颈鹿,r12,：,IF,该动物有蹄类动物,AND,身上有黑色条纹,THEN,该动物是,斑马,r13,：,IF,该动物是鸟,AND,有长脖子,AND,有长腿,AND,不会飞,AND,有黑白二色,THEN,该动物是,鸵鸟,9/13/2024,32,人工智能,6.2.3,控制策略与常用算法,（,10,）,r14,：,IF,该动物是鸟,AND,会游泳,AND,不会飞,AND,有黑白二色,THEN,该动物是,企鹅,r15,：,IF,该动物是鸟,AND,善飞,AND,不怕风浪,THEN,该动物是,海燕,9/13/2024,33,人工智能,老虎,黄褐色,有黑色条纹,食肉动物,哺乳动物,有毛发,有奶,吃肉,有爪,有犬齿,目盯前方,金钱豹,有黑色斑点,长颈鹿,有蹄动物,有蹄,长腿,长脖子,有暗斑点,图,6-4,动物分类产生式规则集所形成的部分推理网络,9/13/2024,34,人工智能,6.2.3,控制策略与常用算法,（,12,）,初始事实：,f1,：,某动物有毛发。,f2,：,吃肉。,f3,：,黄褐色。,f4,：,有黑色条纹,目标条件为：该动物为什么？,9/13/2024,35,人工智能,6.2.3,控制策略与常用算法,（,13,）,9/13/2024,36,人工智能,6.2.3,控制策略与常用算法,（,14,）,例,6.2,使用反向推理算法,9/13/2024,37,人工智能,6.2.3,控制策略与常用算法（,15,）,3,冲突消解策略,给定一组事实之后可用匹配技术寻找可用产生式，其基本思想是将已知事实代入产生式的前件，若前件为真，则该产生式是可用的。,提高匹配效率的方法,索引匹配。为状态建立可用产生式索引表，减少可用产生式搜索范围。,分层匹配。将产生式分成若干层或组，按一定特征进行分层搜索。,过滤匹配。边匹配边 按某些附加特征或参数对可用产生式进行精选。,9/13/2024,38,人工智能,6.2.3,控制策略与常用算法,（,2,）,正向推理算法二,步,1,将初始事实,/,数据置入动态数据库；,步,2,用动态数据库中的事实匹配目标条件，若目标条件满足，推理成功，结束。,步,3,用规则库中各规则的前提匹配动态数据库中的事实，将匹配成功的规则组成待用规则集。,步,4,若待用规则集为空，则运行失败，退出。,步,5,用某种策略，从待用规则集中选取一条规则，,将其结论加入动态数据库，或者执行其动作，撤消待用规则集，转步,2,。,9/13/2024,39,人工智能,6.2.3,控制策略与常用算法（,16,）,如果一组事实可以同时使几个产生式前提为真，常用以下方法进行选择（冲突消解策略）：,优先级法（优先级高者优先）,可信度法（可信度高者优先）,自然顺序法,采用优先级、可信度、代价等冲突消解策略，就是,启发式搜索,；采用自然顺序法，就是一种,盲目碰撞搜索,。,产生式系统的推理方式、搜索策略及冲突消解策略等成为推理控制策略。,产生式系统的控制策略体现在推理机的算法描述中。,9/13/2024,40,人工智能,6.2.4,程序实现*,产生式规则的程序语言实现,规则库的程序实现,动态数据库的程序实现,推理机的程序实现,9/13/2024,41,人工智能,6.2.5,产生式系统与问题求解,（,1,）,如果用正向推理来解决规划性问题，在算法中需要增加以下功能：,记录动态数据库状态变化的历史,需要回溯，保存与每个动态数据库状态对应的可用规则集,要进行树式搜索，还需设置一个,OPEN,表,对已执行的规则进行标记,9/13/2024,42,人工智能,6.2.5,产生式系统与问题求解,（,2,）,产生式系统,图,搜索,初始事实数据,初始节点,目标条件,目标节点,产生式规则,状态转换规则、问题变换规则,规则库,操作集,动态数据库,节点（状态,/,问题）,控制策略,搜索策略,产生式系统与图搜索对比,9/13/2024,43,人工智能,6.2.5,产生式系统与问题求解,（,3,）,问题求解、图搜索和产生式系统的关系是：,问题求解是目的，图搜索是方法，产生式系统是形式,。,产生式系统能实施功能更强的搜索。,产生式系统的应用,基于消解原理的产生式系统,基于自然演绎法的产生式系统,基于专用知识的产生式系统,基于遗传算法的产生式系统,产生式系统几乎成了人工智能问题求解系统的,通用模型。,9/13/2024,44,人工智能,The End,！,