人工智能知识表示产生式表示法ppt课件

2.3产生式表示法,产生式的基本概念产生式的知识表示方法产生式系统的组成产生式系统的推理方式,1,一、产生式基本概念例:1)如果某种动物是哺乳动物，并且吃肉，那么这种动物被称为食肉动物。,P：该动物是哺乳该动物吃肉R：该动物是食肉动物PR,2,产生式:PR或IFPTHENR,R：后项它说明应用这条规则产生的操作、结果,P：前项它说明应用这条规则必须满足的条件；,3,2)如果病人出现如打喷嚏，咳嗽等症状，则该病人感冒了。前提条件P1打喷嚏P2咳嗽结论Q：该病人感冒P1P2Q,4,3)x-11null(y)=x:=0,4）文法分析语言学的一个重要问题就是判定一个符号序列是否合法句，称为文法分析。文法分析可用产生式系统加以解决，下面就以英语为例。S,N,NP,P,PP,V,VP,DET,5,一组重写规则作为产生式规则：NNP/名词就是名词词组；DETNPNP/冠词加名词词组还是名词词组；PNPPP/介词加名词词组构成介词词组；NPPPNP/名词词组后跟介词词组仍是名词词组；VNPPPVP/动词词组后跟名词词组和介词词组构成谓语；NPVPS/名词词组与谓语一起构成句子；,6,二、产生式系统的知识表示方法,7,1(AGEZHAOLING43)2(FATHERZHAOLYINTRUE)4(DOSEDRUG2.0GRAMS)5(MANZHAOLINGTRUE)6(WOMANZHAOLINGFASE),例1ZHAOLINGIS43.2ZHAOLYINISFATHER.4DRUGDOSEIS2.0GRAMS.5ZHAOLINGISMAN.6ZHAOLINGISNTWOMAN.,1）、确定性事实表示三元组表示特性对象取值,8,2020/5/22,9,2）、确定性规则知识的产生式表示IFPTHENQ或者PQ,例:IF动物会飞AND会下蛋THEN该动物是鸟。其中,前提（FLYXTRUE）（EGGXTRUE）结论（BIRDXTRUE）PQ:（FLYXTRUE）（EGGXTRUE）（BIRDXTRUE）,3)、不完全事实的表示为了表示不完全的事实，常需加入关于该事实确定性程度的数值度量。一般用四元组表示(属性,对象,值,置信度)或(关系,对象1,对象2,置信度)例1:1)ZHAOLINGMAYBE40。(AGEZHAOLING400.8)2)老李和老张可能是朋友.(friend,li,zhang，0.8),10,例2：MYCIN中用置信度来表示事实的可信程度。1)(细菌2菌属（IDENT）是连锁状球菌属（STRETOCOCCUS）的置信度为0.7)(IDENTORGANISM2STRETOCOCCUS0.7)2)(细菌2菌属（IDENT）是葡萄球（STAHYOCOCCUS）菌属的置信度为0.3)(IDENTORGANISM2STAHYOCOCCUS0.3)3)(细菌1的形态（MORH）为杆状形态的置信度是0.8)(MORHORGANISM1ROD0.8)4)(细菌1的形态（MORH）是球状（COCCUS）形态的置信度为0.2)(MORHORGANISM1COCCUS0.2)(细菌3革兰氏染色（GRAMSTAIN）为革兰氏阴性（GRAMNEG）置信度为1.0)(GRAMSTAINORGANISM3GRAMNEG1.0),11,4)、不完全知识的表示为了表示不完全的知识，常需加入关于该规则确定性程度的数值度量。基本形式是IFPTHENQ(置信度)或者PQ(置信度)例已知症状如下：E1：打喷嚏，E2：咳嗽。诊断结果：H1：可能感冒H2：另一种可能是花粉过敏IFE1THENH2（.50）。IFE1，E2THENH2（0.50）。,12,2020/5/22,13,例1:IF动物会飞AND会下蛋THEN该动物可能是鸟。（FLY,X,TRUE）（EGG,X,TRUE）（BIRD,X,TRUE）(0.8),例2:在专家系统MYCIN中有这样一条产生式:IF本微生物的染色斑是革兰氏阴性本微生物的形状呈杆状病人是中间宿主THEN该微生物是绿脓杆菌,置信度为0.6.它表示当前提中列出的各个条件都满足时,结论“该微生物是绿生杆菌”可以相信的程度为0.6。,14,三、产生式系统的组成,15,该动物是人,该动物会思考,该动物有智慧,例1,R1R2R3依次使用,16,产生式系统的基本工作过程,（1）初始化综合数据库。（2）检查规则库中是否存在尚未使用过的规则，若有则执行（3）；否则转（7）。（3）选择可与综合数据库中已知事实相匹配的规则；如没有转（6）。（4）执行并标记当前选中规则，把所得到的结论作为新事实放入综合数据库；如果该规则的结论是一些操作，则执行这些操作。（5）检查综合数据库中是否包含了该问题的解，如是，问题求解结束；否则，转（2）（6）当规则库中没有与综合数据库中的已有事实相匹配的规则时，要求用户进一步提供关于该问题的已知事实，若能提供，则转（2）；否则，说明该问题无解，终止问题求解过程。（7）若知识库中不再有未使用规则，也说明该问题无解，终止问题求解过程。,R1该动物是人,R2该动物会思考,R3该动物有智慧,该动物会劳动该动物脑部没毛病,17,例2:设字符转换规则为:ABCACDBCGBEFDE已知：A，B求：F,18,分析:一、数据库x，其中x为字符二、规则集,1，IFABTHENC2，IFACTHEND3，IFBCTHENG4，IFBETHENF5，IFDTHENE,19,三、控制策略顺序排队四、初始数据A，B五、结束条件Fx,20,求解过程,数据库可触发规则被触发规则,A，B,（1）,（1）,A，B，C,（2）（3）,（2）,A，B，C，D,（3）（5）,（3）,A，B，C，D，G,（5）,（5）,A，B，C，D，G，E,（4）,（4）,A，B，C，D，G，E，F,1，IFABTHENC2，IFACTHEND3，IFBCTHENG4，IFBETHENF5，IFDTHENE,21,例3:设综合数据库db的初始内容为集合a,b,c,其中a、b、c均为字符；规则库包含以下三条插入双字符的规则：R1:?(abdb)=insert(db,ab)R2:?(acdb)=insert(db,ac)R3:?(bcdb)=insert(db,bc)推理的目标是使db成为：a,b,c,ab,ac,bc,22,规则库,综合数据库,控制机制,产生式系统：综合据库、产生式规则和控制系统。,寻找满足要求的事实,寻找满足要求的规则,改变综合数据库的事实,控制策略作用说明下一步应该选用什么规则。产生式系统的控制机制就是不断地挑选可触发/激活的规则对综合数据库进行操作，直至得到解答（综合数据库内容转变为描述了目标状态），或失败结束。通常从选择规则到执行操作分3步：匹配2)冲突解决3)操作,23,冲突解决,被触发的规则不一定总是启用规则。因为可能同时有几条规则的条件部分被满足。这就要在解决冲突中来解决这个问题。在复杂的情况下，在数据库和规则的条件部分之间可能要进行近似匹配。,24,两条美式足球规则,R1：进攻一方如果在前三次进攻中前进的距离少于10码(shortyardage)，那么在第四次进攻(fourthdawn)时，可以踢悬空球(punt)。R2：如果进攻这一方，在前三次进攻中，前进的距离少于10码，而进攻的位置又在离对方球门线30码距离之内，那么就可以射门(fieldgoal)。,25,专一性排序,如果当前数据库包含事实“fourthdawn”和“shortyardage”以及“within30yards”，则上述两条规则都被触发，这就需要用冲突解决来决定首先使用哪一条规则。有很多种冲突解决策略，其中一种策略是先使用规则R2，因为R2的条件部分包括了更多的限制，因此规定了一个更为特殊的情况。这是一种按专一性来编排顺序的策略，称为专一性排序。如果某一规则条件部分规定的情况，比另一规则条件部分规定的情况更有针对性，则这条规则有较高的优先级。,26,规则1：问：该动物有奶吗？是。结论：这种动物为哺乳动物。,规则2：问：该动物有奶吗？是。问：有蹄吗？是。结论：这种动物为有蹄动物。,专一性排序,27,反例,规则：如果该动物会飞，并且会下蛋，那么，该动物是鸟。,补充数据库:该动物有羽毛。,28,四、产生式系统的推理方式,29,1.正向推理2.逆向推理3.双向推理,四、产生式系统的推理方式,30,例1：（Mammal?x）(Eat?xMeat)(Carnivore?x)IF(MammalDog)(EatDogMeat)THEN(CarnivoreDog),31,例2：文法分析问题（正向推理）一组重写规则作为产生式规则：NNP/名词就是名词词组；DETNPNP/冠词加名词词组还是名词词组；PNPPP/介词加名词词组构成介词词组；NPPPNP/名词词组后跟介词词组仍是名词词组；VNPPPVP/动词词组后跟名词词组和介词词组构成谓语；NPVPS/名词词组与谓语一起构成句子；,32,作文法分析的句子是：theboyplaysfootballintheplace.1）将该句子的所有单词先替换为语法词汇：DETNVNPDETN2）作进一步的替代为：NPVNPPP3）通过激活规则去进行符号重写：NPVP4）最后，综合数据库只剩下符号S（指示合法句），文法分析成功结束。,33,例3：区分动物（逆向推理）机器人去逛动物园，为帮助它区分其中的七种动物，给它存入了如下几条产生式规则：p1：若动物有毛发，则它是哺乳动物；p2：若动物有奶，则它是哺乳动物；p3：若动物有羽毛，则它是鸟类；p4：若动物会飞且生蛋，则它是鸟类；p5：若动物是哺乳动物且吃肉，则它是食肉动物；p6：若动物是哺乳动物且有犬齿，有爪，眼睛紧盯着前方，则它是食肉动物；p7：若动物是哺乳动物且反刍食物，则它是蹄类且是偶蹄动物；,34,p8：若动物是哺乳类且有蹄，则它是有蹄类；p9：若动物是食肉类，黄褐色，有黑的斑点，则它是一只金钱豹；p10：若动物是食肉类，黄褐色，有黑色条纹，则它是老虎；p11：若动物是有蹄类，长腿，长脖子，有黄褐色暗斑点，则它是长颈鹿；p12：若动物是有蹄类，白色有黑条纹，则它是斑马；p13：若动物是鸟，不会飞，长腿，长脖子，黑、白色，则它是驼鸟；p14：若动物是鸟，不会飞，会游泳，黑、白色，则它是企鹅；p15：若动物是鸟，善飞，则它是信天翁。,35,判断金钱豹的推理树,p8：若动物是哺乳类且有蹄，则它是有蹄类；p9：若动物是食肉类，黄褐色，有黑的斑点，则它是一只金钱豹；p10：若动物是食肉类，黄褐色，有黑色条纹，则它是老虎；p11：若动物是有蹄类，长腿，长脖子，有黄褐色暗斑点，则它是长颈鹿；p12：若动物是有蹄类，白色有黑条纹，则它是斑马；p13：若动物是鸟，不会飞，长腿，长脖子，黑、白色，则它是驼鸟；p14：若动物是鸟，不会飞，会游泳，黑、白色，则它是企鹅；p15：若动物是鸟，善飞，则它是信天翁。,36,p8：若动物是哺乳类且有蹄，则它是有蹄类；p9：若动物是食肉类，黄褐色，有黑的斑点，则它是一只金钱豹；p10：若动物是食肉类，黄褐色，有黑色条纹，则它是老虎；p11：若动物是有蹄类，长腿，长脖子，有黄褐色暗斑点，则它是长颈鹿；p12：若动物是有蹄类，白色有黑条纹，则它是斑马；p13：若动物是鸟，不会飞，长腿，长脖子，黑、白色，则它是驼鸟；p14：若动物是鸟，不会飞，会游泳，黑、白色，则它是企鹅；p15：若动物是鸟，善飞，则它是信天翁。,哺乳、有蹄是中间结果网络中标识出逻辑关系合取与析取,37,小结,1产生式由前项P和后项R两部分组成PR2产生式的表示1)可用谓词逻辑、符号和语言的形式表示事实及规则。,38,谓词表示：1)MAN(ZHAOLING)真值T/F2)WOMAN(ZHAOLING)真值T/F3)FLY(X)（EGG(X)IS(X,BIRD)IF动物会飞AND会下蛋THEN该动物可能是鸟。,39,3产生式与蕴涵式产生式的特殊形式为蕴涵。表示不精确知识/精确知识进行不精确匹配/精确匹配无真值/有真值T/F,40,产生式应用实例,41,例1传教士与野人问题,有N个传教士和N个野人要过河。约束条件:现在有一条船只能承载K个人（包括野人和传教士），K=c右岸:N-m-Sm=N-c-Sc,44,传教士野人问题规则库（N=3，K=2）,ifL10(M,C,B=1)then(M1,C,B=0)ifL01(M,C,B=1)then(M,C1,B=0)ifL11(M,C,B=1)then(M1,C1,B=0)ifL20(M,C,B=1)then(M2,C,B=0)ifL02(M,C,B=1)then(M,C2,B=0)ifR10(M,C,B=0)then(M+1,C,B=1)ifR01(M,C,B=0)then(M,C+1,B=1)ifR11(M,C,B=0)then(M+1,C+1,B=1)ifR20(M,C,B=0)then(M+2,C,B=1)ifR02(M,C,B=0)then(M,C+2,B=1)指示推理成功结束（到达目标状态）的规则：m=0c=0b=0Thalt()；,R1R2R3R4R5R6R7R8R9R10,45,例2八数码游戏规则,在3*3的方格棋盘上放置分别标语有数字的八张牌：1，2，3，4，5，6，7，8初始状态为S0目标状态为Sg。可使用的操作算符：位于空格的左、下、右、上的牌移入空格。,46,操作算符通过空格移动来实现棋盘布局。设Sij指示第i行第j列的数码（1i,j3），io、jo指示空格所在的行、列数，则有：R1:jo-11=Siojo:=Sio(jo-1)Sio(jo-1):=0(空格左移)R2:io-11=Siojo:=S(io-1)joS(io-1)jo:=0(空格上移)R3:jo+13=Siojo:=Sio(jo+1)Sio(jo+1):=0(空格右移)R4:io+13=Siojo:=S(io+1)joS(io+1)jo:=0(空格下移),47,例3旅行商问题,一个在A城市工作的推销员需去几个外地城市办理业务，每个城市只允许去一次，遍历这些城市后返回A城市；已知各城市间的里程，要求寻找最短的遍历路线。假设推销员需去4个外地城市B、C、D、E。,48,综合数据库的内容表示为城市名列表，初始时该列表只包含城市A。设：真值函数not-visit(x)指示未访问过城市x，真值函数visit-all指示已遍历各城市，操作函数move(x)指示去城市x并将x加进城市名列表；二条规则：R1:not-visit(x)Tmove(x),R2:visit-all()Tmove(A).由于有4个外地城市，所以推理开始时相应于规则R1，有4条规则实例激活，分别相应于x取值B、C、D、E。若以上、下2城市间路径最短作为冲突解决的依据，则相应于x:=C的规则实例被选用，即推销员走向城市C。依次，经由推理，推销员将相继走向城市D、B、E。接下去规则R2激活，推销员返回城市A。,49,例4BADHAIRCUT,男孩规则如果HAIRCUT满意,则GOHOME否则,继续HAIRCUT男孩规则如果HAIRCUT不满意,则继续HAIRCUT否则男孩GOHOME,50,BADHAIRCUT,正向推理:!男孩错误:前面满意,不等于(后面)满意,条件不充分,51,例5拍苍蝇,规则1如果天使拍到苍蝇,则苍蝇死2如果天使砸到苍蝇,则苍蝇死逆向推理:苍蝇死拍砸,52,附1产生式系统(Productionsystem)首先是由Post等提出的产生式规则(Productionrule1943)而得名的。,53,爱德华费根鲍姆（EdwardA.Feigenbaum)知识工程的提出者，大型人工智能系统的开拓者DENDRA。,MYCINE管理诊断感染性疾病的专家系统,DENDRA化学分子结构专家系统斯坦福大学利用产生式系统结构设计出第一个专家系统(1965),54,附2：EnglishWords,PredicateCalculusMetaknowledge“元知识”ProductionsProductionsSystemsFireWorkMemory,55,实验1传教士与野人问题,有N个传教士和N个野人要过河。给出过河方案。现在有一条船只能承载K个人（包括野人），KN。在任何时刻，如果有野人和传教士在一起，必须要求传教士的人数多于或等于