人工智能知识表示2产生式表示法.ppt

《人工智能知识表示2产生式表示法.ppt》由会员分享，可在线阅读，更多相关《人工智能知识表示2产生式表示法.ppt（61页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 2.3 产生式表示法产生式的基本概念产生式的知识表示方法产生式的知识表示方法产生式系统的组成产生式系统的组成产生式系统的推理方式产生式系统的推理方式一、一、产生式基本概念产生式基本概念例例:1)如果 某种动物是哺乳动物，并且吃肉，那么 这种动物被称为食肉动物。P：该动物是哺乳该动物吃肉R：该动物是食肉动物 P R 产生式产生式:P R 或或 IF P THEN RR：后项它说明应用这条规则产生的操作、结果P：前项 它说明应用这条规则必须满足的条件；2)如果病人出现如打喷嚏，咳嗽等症状，则 该病人感冒了。前提条件前提条件 P1 打喷嚏 P2 咳嗽结论结论 Q：该病人感冒P1 P2 Q3)x-1

2、1null(y)=x:=04）文法分析语言学的一个重要问题就是判定一个符号序列是否合法句，称为文法分析。文法分析可用产生式系统加以解决，下面就以英语为例。S,N,NP,P,PP,V,VP,DET一组重写规则作为产生式规则：一组重写规则作为产生式规则：NNP/名词就是名词词组；DETNPNP/冠词加名词词组还是名词词组；PNPPP/介词加名词词组构成介词词组；NPPPNP/名词词组后跟介词词组仍是名词词组；VNPPPVP/动词词组后跟名词词组和介词词组构成谓语；NPVPS/名词词组与谓语一起构成句子；二、二、产生式系统的知识表示方法产生式系统的知识表示方法1 (AGE ZHAOLING 43)2

3、(FATHER ZHAOLYIN TRUE)4(DOSE DRUG 2.0 GRAMS)5(MAN ZHAOLING TRUE)6(WOMAN ZHAOLING FASE)例例 1 ZHAOLING IS 43.2 ZHAOLYIN IS FATHER.4 DRUG DOSE IS 2.0 GRAMS.5 ZHAOLING IS MAN.6ZHAOLING ISNT WOMAN.1）、确定性事实表示 三元组表示 特性 对象 取值2）、确定性规则知识的产生式表示）、确定性规则知识的产生式表示 IF P THEN Q Q 或者或者 PQ,Q,例例:IF 动物会飞动物会飞 AND 会下蛋会下蛋 TH

4、EN 该动物该动物是鸟。是鸟。其中其中,前提前提（FLY X TRUE）（EGG X TRUE）结论结论（BIRD X TRUE）PQ:Q:（FLY X TRUE）（EGG X TRUE）（BIRD X TRUE）11/18/20229 3)、不完全事实、不完全事实的表示的表示 为了表示不完全的事实事实，常需加入关于该事实事实确定性程度确定性程度的数值度量。一般用四元组表示一般用四元组表示 (属性属性,对象对象,值值,置信度置信度)或或 (关系关系,对象对象1,对象对象2,置信度置信度)例例1:1)ZHAOLINGMAYBE40。(AGEZHAOLING400.8)2)老李和老张可能是朋友老李

5、和老张可能是朋友.(friend,li,zhang，0.8)例2：MYCIN中用置信度来表示事实的可信程度。1)(细菌2菌属（IDENT）是连锁状球菌属（STRETOCOCCUS）的置信度为0.7)(IDENT ORGANISM2 STRETOCOCCUS 0.7)2)(细菌2菌属（IDENT）是葡萄球（STAHYOCOCCUS）菌属的置信度为0.3)(IDENT ORGANISM2 STAHYOCOCCUS 0.3)3)(细菌1的形态（MORH）为杆状形态的置信度是0.8)(MORH ORGANISM1 ROD 0.8)4)(细菌1的形态（MORH）是球状（COCCUS）形态的置信度为0.2

6、)(MORH ORGANISM1 COCCUS 0.2)5)(细菌3革兰氏染色（GRAMSTAIN）为革兰氏阴性（GRAMNEG）置信度为1.0)6)(GRAMSTAIN ORGANISM3 GRAMNEG 1.0)4)、不完全知识、不完全知识的表示的表示为了表示不完全的知识，常需加入关于该规则确定性程度确定性程度的数值度量。基本形式是基本形式是 IF P THEN Q(置信度置信度)或者或者 PQ(置信度置信度)例 已知症状如下：E1：打喷嚏，E2：咳嗽。诊断结果：H1：可能感冒 H2：另一种可能是花粉过敏IF E1 THEN H2（.50）。IF E1，E2 THEN H2（0.50）。例

7、例1:IF 动物会飞动物会飞 AND 会下蛋会下蛋 THEN 该动物可能是鸟该动物可能是鸟。（FLY,X,TRUE）（EGG,X,TRUE）（BIRD,X,TRUE）(0.8)11/18/202213例例2:在专家系统在专家系统MYCIN中有这样一条产生式中有这样一条产生式:IF 本微生物的染色斑是革兰氏阴性本微生物的染色斑是革兰氏阴性 本微生物的形状呈杆状本微生物的形状呈杆状 病人是中间宿主病人是中间宿主 THEN 该微生物是绿脓杆菌该微生物是绿脓杆菌,置信度为置信度为0.6.它表示当前提中列出的各个条件都满足时它表示当前提中列出的各个条件都满足时,结论结论“该微生物是绿生杆菌该微生物是绿生

8、杆菌”可以相信的程度为可以相信的程度为0.6。三、产生式系统的组成产生式系统的组成该动物是人该动物会思考该动物有智慧例例1R1 R2 R3依次使用依次使用例2:设字符转换规则为:ABCACDB BCGCGBEFDE已知：A，B求：F分析:一、数据库x，其中x为字符二、规则集1，IF AB THEN C2，IF AC THEN D3，IF BC THEN G4，IF BE THEN F5，IF D THEN E三、控制策略顺序排队四、初始数据A，B五、结束条件Fx求解过程数据库可触发规则被触发规则A，B（1）（1）A，B，C（2）（3）（2）A，B，C，D（3）（5）（3）A，B，C，D，G（5

9、）（5）A，B，C，D，G，E（4）（4）A，B，C，D，G，E，F1，IF AB THEN C 2，IF AC THEN D3，IF BC THEN G 4，IF BE THEN F5，IF D THEN E例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规则库综合数据库控制机制控制机制控制机制控制机制产生式系统：产生式系统：综合据库、产

10、生式规则和控制系统。寻找满足要求的事实寻找满足要求的规则改变综合数据库的事实 控制策略作用说明下一步应该选用什么规则。产生式系统的控制机制控制机制就是不断地挑选可触发触发/激活激活的规则对综合数据库进行操作，直至得到解答（综合数据库内容转变为描述了目标状态），或失败结束。通常从选择规则到执行操作分3步：1)匹配 2)冲突解决 3)操作冲突解决被触发的规则不一定总是启用规则。因为可能同时有几条规则的条件部分被满足。这就要在解决冲突中来解决这个问题。在复杂的情况下，在数据库和规则的条件部分之间可能要进行近似匹配。两条美式足球规则 R1：进攻一方如果在前三次进攻中前进的距离少于10码(short y

11、ardage)，那么在第四次进攻(fourth dawn)时，可以踢悬空球(punt)。R2：如果进攻这一方，在前三次进攻中，前进的距离少于10码，而进攻的位置又在离对方球门线30码距离之内，那么就可以射门(field goal)。专一性排序如果当前数据库包含事实“fourth dawn”和“short yardage”以及“within 30 yards”，则上述两条规则都被触发，这就需要用冲突解决来决定首先使用哪一条规则。有很多种冲突解决策略，其中一种策略是先使用规则R2，因为R2的条件部分包括了更多的限制，因此规定了一个更为特殊的情况。这是一种按专一性来编排顺序的策略，称为专一性排序。如

12、果某一规则条件部分规定的情况，比另一规则条件部分规定的情况更有针对性，则这条规则有较高的优先级。规则1：问：该动物有奶吗？是。结论：这种动物为哺乳动物。规则2：问：该动物有奶吗？是。问：有蹄吗？是。结论：这种动物为有蹄动物。专一性排序反例规则：如果该动物会飞，并且会下蛋，那么，该动物是鸟。补充数据库:该动物有羽毛。四、四、产生式系统的推理方式产生式系统的推理方式1.正向推理2.逆向推理3.双向推理四、四、产生式系统的推理方式产生式系统的推理方式例1：（Mammal?x）(Eat?xMeat)(Carnivore?x)IF(MammalDog)(EatDogMeat)THEN(Carnivore

13、Dog)例例2：文法分析问题：文法分析问题（正向推理）一组重写规则作为产生式规则：NNP/名词就是名词词组；DETNPNP/冠词加名词词组还是名词词组；PNPPP/介词加名词词组构成介词词组；NPPPNP/名词词组后跟介词词组仍是名词词组；VNPPPVP/动词词组后跟名词词组和介词词组构成谓语；NPVPS/名词词组与谓语一起构成句子；作文法分析的句子是：theboyplaysfootballintheplace.1）将该句子的所有单词先替换为语法词汇：DETNVNPDETN2）作进一步的替代为：NPVNPPP3）通过激活规则去进行符号重写：NPVP4）最后，综合数据库只剩下符号S（指示合法句）

14、，文法分析成功结束。例例3：区分动物区分动物（逆向推理）逆向推理）机器人去逛动物园，为帮助它区分其中的七种动物，机器人去逛动物园，为帮助它区分其中的七种动物，给它存入了如下几条产生式规则：给它存入了如下几条产生式规则：p1：若动物有毛发，则它是：若动物有毛发，则它是哺乳动物哺乳动物；p2：若动物有奶，则它是哺乳动物；：若动物有奶，则它是哺乳动物；p3：若动物有羽毛，则它是鸟类；：若动物有羽毛，则它是鸟类；p4：若动物会飞且生蛋，则它是鸟类；：若动物会飞且生蛋，则它是鸟类；p5：若动物是哺乳动物且吃肉，则它是：若动物是哺乳动物且吃肉，则它是食肉动物食肉动物；p6：若动物是哺乳动物且有犬齿，有爪，

15、眼睛紧盯着前方，则它：若动物是哺乳动物且有犬齿，有爪，眼睛紧盯着前方，则它 是食肉动物；是食肉动物；p7：若动物是哺乳动物且反刍食物，则它是蹄类且是偶蹄动物；：若动物是哺乳动物且反刍食物，则它是蹄类且是偶蹄动物；p8：若动物是哺乳类且有蹄，则它是有蹄类；：若动物是哺乳类且有蹄，则它是有蹄类；p9：若动物是食肉类，黄褐色，有黑的斑点，则它是一只：若动物是食肉类，黄褐色，有黑的斑点，则它是一只金钱豹金钱豹；p10：若动物是食肉类，黄褐色，有黑色条纹，则它是老虎；：若动物是食肉类，黄褐色，有黑色条纹，则它是老虎；p11：若动物是有蹄类，长腿，长脖子，有黄褐色暗斑点，则它是长：若动物是有蹄类，长腿，长

16、脖子，有黄褐色暗斑点，则它是长颈鹿；颈鹿；p12：若动物是有蹄类，白色有黑条纹，则它是斑马；：若动物是有蹄类，白色有黑条纹，则它是斑马；p13：若动物是鸟，不会飞，长腿，长脖子，黑、白色，则它是驼鸟；：若动物是鸟，不会飞，长腿，长脖子，黑、白色，则它是驼鸟；p14：若动物是鸟，不会飞，会游泳，黑、白色，则它是企鹅；：若动物是鸟，不会飞，会游泳，黑、白色，则它是企鹅；p15：若动物是鸟，善飞，则它是信天翁。：若动物是鸟，善飞，则它是信天翁。判断金钱豹的推理树判断金钱豹的推理树p8：若动物是哺乳类且有蹄，则它是有蹄类；：若动物是哺乳类且有蹄，则它是有蹄类；p9：若动物是食肉类，黄褐色，有黑的斑点，

17、则它是一只：若动物是食肉类，黄褐色，有黑的斑点，则它是一只金钱豹金钱豹；p10：若动物是食肉类，黄褐色，有黑色条纹，则它是老虎；：若动物是食肉类，黄褐色，有黑色条纹，则它是老虎；p11：若动物是有蹄类，长腿，长脖子，有黄褐色暗斑点，则它是长：若动物是有蹄类，长腿，长脖子，有黄褐色暗斑点，则它是长颈鹿；颈鹿；p12：若动物是有蹄类，白色有黑条纹，则它是斑马；：若动物是有蹄类，白色有黑条纹，则它是斑马；p13：若动物是鸟，不会飞，长腿，长脖子，黑、白色，则它是驼鸟；：若动物是鸟，不会飞，长腿，长脖子，黑、白色，则它是驼鸟；p14：若动物是鸟，不会飞，会游泳，黑、白色，则它是企鹅；：若动物是鸟，不会

18、飞，会游泳，黑、白色，则它是企鹅；p15：若动物是鸟，善飞，则它是信天翁。：若动物是鸟，善飞，则它是信天翁。p8：若动物是哺乳类且有蹄，则它是：若动物是哺乳类且有蹄，则它是有蹄类有蹄类；p9：若动物是食肉类，黄褐色，有黑的斑点，则它是一只金钱豹；：若动物是食肉类，黄褐色，有黑的斑点，则它是一只金钱豹；p10：若动物是食肉类，黄褐色，有黑色条纹，则它是老虎；：若动物是食肉类，黄褐色，有黑色条纹，则它是老虎；p11：若动物是有蹄类，长腿，长脖子，有黄褐色暗斑点，则它是：若动物是有蹄类，长腿，长脖子，有黄褐色暗斑点，则它是长长颈鹿颈鹿；p12：若动物是有蹄类，白色有黑条纹，则它是：若动物是有蹄类，白

19、色有黑条纹，则它是斑马斑马；p13：若动物是鸟，不会飞，长腿，长脖子，黑、白色，则它是驼鸟；：若动物是鸟，不会飞，长腿，长脖子，黑、白色，则它是驼鸟；p14：若动物是鸟，不会飞，会游泳，黑、白色，则它是企鹅；：若动物是鸟，不会飞，会游泳，黑、白色，则它是企鹅；p15：若动物是鸟，善飞，则它是信天翁。：若动物是鸟，善飞，则它是信天翁。哺乳、有蹄是中间结果哺乳、有蹄是中间结果网络中标识出逻辑关系合取与析取网络中标识出逻辑关系合取与析取 小结小结1 产生式由产生式由前项前项P和和后项后项R两部分组成两部分组成PR 2 产生式的表示产生式的表示1)可用谓词逻辑、符号和语言的形式表示事实及规则。谓词表示

20、谓词表示：1)MAN(ZHAOLING)真值T/F2)WOMAN(ZHAOLING)真值T/F 3)FLY (X)（EGG(X)IS IS(X,BIRD)IF 动物会飞动物会飞 AND 会下蛋会下蛋 THEN 该动物可能是鸟该动物可能是鸟。3产生式与蕴涵式产生式的特殊形式为蕴涵。表示不精确知识/精确知识进行不精确匹配/精确匹配无真值/有真值T/F产生式应用实例例例1传教士与野人问题有N个传教士和N个野人要过河。约束条件:现在有一条船只能承载K个人（包括野人和传教士），KN。在任何时刻，如果有野人和传教士在一起（包括岸上与船上），必须要求传教士的人数多于或等于野人的人数。传教士和野人都可以撑船过

21、河变量m 传教士在左岸的实际人数变量c：野人在左岸的实际人数变量变量b:指示船是否在左岸（值1指示船在左岸，否则为0）综合数据库综合数据库:（m，c，b）初始状态:（N，N，1）目标状态:（0，0，0）2）传教士与野人问题L(Sm,Sc):从左岸到右岸的划船操作R(Sm,Sc):从右岸回到左岸的划船操作规则库规则库:例：L(1,0):IF（m,C,b=1）L(1,0)THEN（m-1,C,b=0）约束条件为约束条件为:Sm、S c 分别是分别是船上野人和传教士人数船上：船上：Sm+S c=Sc 左岸：左岸：m=c右岸右岸:N-m-Sm=N-c-Sc传教士野人问题传教士野人问题规则库规则库（N=

22、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)指示推理成功

23、结束（到达目标状态）的规则：m=0c=0b=0Thalt()；R1R2R3R4R5R6R7R8R9R10例例2八数码游戏规则八数码游戏规则 在3*3的方格棋盘上放置分别标语有数字的八张牌：1 1，2 2，3 3，4 4，5 5，6 6，7 7，8 8 初始状态为S0 目标状态为Sg。可使用的操作算符：位于空格的左、下、右、上左、下、右、上左、下、右、上左、下、右、上的牌 移入空格。操作算符 通过空格移动来实现棋盘布局。设Sij指示第i行第j列的数码（1i,j3），io、jo指示空格所在的行、列数，则有：R1:jo-11=Siojo:=Sio(jo-1)Sio(jo-1):=0(空格左移)R2:

24、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(空格下移)例3旅行商问题一个在A城市工作的推销员需去几个外地城市办理业务，每个城市只允许去一次，遍历这些城市后返回A城市；已知各城市间的里程，要求寻找最短的遍历路线。假设推销员需去4个外地城市B、C、D、E。BACDE综合数据库的内容表示为城市名列表，初始时该列表只包含城市A。设：真值函数not-visit(x)指示未访问过城市x，真值函数visit-al

25、l指示已遍历各城市，操作函数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。例4BADHAIRCUT男孩规则如果HAIRCUT满意,则GOHOME否则,继续HAIRCUT男孩规则如果HAIRCUT不满意,则继

26、续HAIRCUT否则男孩GOHOMEBADHAIRCUT正向推理:!男孩错误:前面满意,不等于(后面)满意,条件不充分例例5 拍苍蝇拍苍蝇规则规则1如果天使拍到苍蝇苍蝇,则苍蝇苍蝇死2如果天使砸到苍蝇苍蝇,则苍蝇苍蝇死逆向推理逆向推理:苍蝇苍蝇死拍拍砸砸 附1产生式系统(Productionsystem)首先是由Post 等提出的产生式规则(Productionrule1943)而得名的。爱德华费根鲍姆（EdwardA.Feigenbaum)知识工程的提出者，大型人工智能系统的开拓者DENDRA。MYCINE管理诊断感染性疾病的专家系统DENDRA化学分子结构专家系统斯坦福大学利用产生式系统结

27、构设计出第一个专家系统(1965)附2：EnglishWordsPredicateCalculusMetaknowledge“元知识”ProductionsProductionsSystemsFireWorkMemory实验1 传教士与野人问题有N个传教士和N个野人要过河。给出过河方案。现在有一条船只能承载K个人（包括野人），KN。在任何时刻，如果有野人和传教士在一起，必须要求传教士的人数多于或等于野人的人数。传教士和野人都可以撑船过河传教士野人问题传教士野人问题规则库规则库（N=2，K=2）ifL10(M,C,B=1)then(M1,C,B=0)ifL01(M,C,B=1)then(M,C1

28、,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)R1R2R3R4R5R6R7R8R9R10 古代有个国王想知道他的二个大臣中谁最聪明，古代有个国王想知道他的二个大臣中谁最聪明

29、，就在他们每个人前额上画了一个点，告诉他们就在他们每个人前额上画了一个点，告诉他们至少有至少有一个人额上的点是白色的一个人额上的点是白色的，并且重复地问他们：，并且重复地问他们：“谁谁知道自己点的颜色？知道自己点的颜色？”他们头一次都回答说不知道。设每人都能看到别他们头一次都回答说不知道。设每人都能看到别人点的颜色，但看不到自己额上点的颜色。要求证明人点的颜色，但看不到自己额上点的颜色。要求证明下一次他们全都会说下一次他们全都会说“知道知道”，而且所有的点都是白，而且所有的点都是白色的。色的。猜猜猜猜谁最聪明谁最聪明S i(a)表示表示 i 大臣看到的颜色为大臣看到的颜色为 S(a)，如白则，

30、如白则 S i(1)；W i 标识大臣是否猜出自己点的颜色，如果他宣布已知道自标识大臣是否猜出自己点的颜色，如果他宣布已知道自己点的颜色，则己点的颜色，则 ，否则为，否则为0；n 表示二位大臣额上颜色状态集表示二位大臣额上颜色状态集X中白点的个数。中白点的个数。产生式：产生式：表示表示 i 大臣看到的颜色为大臣看到的颜色为(a,b)，如是两白则，如是两白则 ；W 标识大臣是否猜出自己点的颜色，如果他宣布已知道自己点的颜色，标识大臣是否猜出自己点的颜色，如果他宣布已知道自己点的颜色，则则 ，否则为，否则为0；n 表示三位大臣额上颜色状态集表示三位大臣额上颜色状态集 中白点的个数。中白点的个数。产生式：产生式：解：解：为了形式化表示此推理过程，可建立一套产生式。为了形式化表示此推理过程，可建立一套产生式。为此引入了一些中间状态并定义了下述符号。为此引入了一些中间状态并定义了下述符号。