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

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

2、人感冒了。前提条件前提条件 P1 打喷嚏 P2 咳嗽结论结论 Q： 该病人感冒P1 P2 Q2021/6/1653) x-1 1 null (y) = x:= 04）文法分析 语言学的一个重要问题就是判定一个符号序列是否合法句，称为文法分析。 文法分析可用产生式系统加以解决，下面就以英语为例。S, N, NP, P, PP, V, VP, DET2021/6/166一组重写规则作为产生式规则：一组重写规则作为产生式规则：N NP /名词就是名词词组；DET NP NP /冠词加名词词组还是名词词组；P NP PP /介词加名词词组构成介词词组；NP PP NP /名词词组后跟介词词组仍是名词词

3、组；V NP PP VP /动词词组后跟名词词组和介词词组构成谓语；NP VP S /名词词组与谓语一起构成句子；2021/6/167二、二、 产生式系统的知识表示方法产生式系统的知识表示方法2021/6/1681 (AGE ZHAOLING 43)2(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.6ZH

4、AOLING ISNT WOMAN. 1）、确定性事实表示 三元组表示 特性 对象 取值2021/6/1692）、确定性规则知识的产生式表示）、确定性规则知识的产生式表示 IF P THEN Q Q 或者或者 PQ, Q, 例例: IF 动物会飞动物会飞 AND 会下蛋会下蛋 THEN 该动物该动物是鸟。是鸟。其中其中,前提前提（FLY X TRUE） （EGG X TRUE）结论结论（BIRD X TRUE）PQ:Q:（FLY X TRUE） （EGG X TRUE） （BIRD X TRUE）2021/6/1610 3)、不完全事实、不完全事实的表示的表示 为了表示不完全的事实事实，常需加

5、入关于该事实事实确定性程度确定性程度的数值度量。一般用四元组表示一般用四元组表示 (属性属性, 对象对象, 值值, 置信度置信度) 或或 (关系关系,对象对象1,对象对象2,置信度置信度)例例1: 1) ZHAOLING MAYBE 40 。 (AGE ZHAOLING 40 0.8)2) 老李和老张可能是朋友老李和老张可能是朋友. (friend, li, zhang，0.8)2021/6/1611 例2： MYCIN中用置信度来表示事实的可信程度。1) (细菌2菌属（ IDENT ）是连锁状球菌属（ STRETOCOCCUS ）的置信度为0.7)(IDENT ORGANISM2 STRET

6、OCOCCUS 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)(MORH ORGANISM1 COCCUS 0.2)(细菌3革兰氏染色（ GRAMSTAIN ）为革兰氏阴性（ GRAMNEG ）置信度为1.0) 5) (GRAMSTAIN ORGANISM3 GRAMNEG

7、1.0)2021/6/1612 4)、不完全知识、不完全知识的表示的表示 为了表示不完全的知识，常需加入关于该规则确定性程度确定性程度的数值度量。基本形式是基本形式是 IF P THEN Q (置信度置信度) 或者或者 PQ (置信度置信度) 例 已知症状如下： E1：打喷嚏，E2：咳嗽。 诊断结果： H1：可能感冒 H2：另一种可能是花粉过敏IF E1 THEN H2（.50）。 IF E1，E2 THEN H2（0.50）。2021/6/1613例例1: IF 动物会飞动物会飞 AND 会下蛋会下蛋 THEN 该动物可能是鸟该动物可能是鸟。 （FLY, X, TRUE） （EGG, X,

8、TRUE） （BIRD, X, TRUE）(0.8)2021/6/1614例例2: 在专家系统在专家系统MYCIN中有这样一条产生式中有这样一条产生式: IF 本微生物的染色斑是革兰氏阴性本微生物的染色斑是革兰氏阴性 本微生物的形状呈杆状本微生物的形状呈杆状 病人是中间宿主病人是中间宿主 THEN 该微生物是绿脓杆菌该微生物是绿脓杆菌,置信度为置信度为0.6. 它表示当前提中列出的各个条件都满足时它表示当前提中列出的各个条件都满足时,结论结论“该微生物是绿生杆菌该微生物是绿生杆菌”可以相信的程度为可以相信的程度为0.6 。 2021/6/1615三、 产生式系统的组成产生式系统的组成2021/

9、6/1616该动物是人该动物会思考该动物有智慧例例1R1 R2 R3依次使用依次使用2021/6/1617产生式系统的基本工作过程（1 1）初始化综合数据库。初始化综合数据库。（2 2）检查规则库中检查规则库中是否存在尚未使用过的规则是否存在尚未使用过的规则，若有则执行（，若有则执行（3 3）；）；否则转（否则转（7 7）。）。（3 3）选择可与综合数据库中已知事实相匹配的规则；如没有转（选择可与综合数据库中已知事实相匹配的规则；如没有转（6 6）。）。（4 4）执行并标记当前选中规则，把所得到的结论作为新事实放入综合执行并标记当前选中规则，把所得到的结论作为新事实放入综合数据库；如果该规则的

10、结论是一些操作，则执行这些操作。数据库；如果该规则的结论是一些操作，则执行这些操作。（5 5）检查综合数据库中是否包含了该问题的解，如是，问题求解结束；检查综合数据库中是否包含了该问题的解，如是，问题求解结束；否则，转（否则，转（2 2）（6 6）当规则库中当规则库中没有与综合数据库中的已有事实相匹配的规则没有与综合数据库中的已有事实相匹配的规则时，要时，要求用户进一步提供关于该问题的已知事实，若能提供，则转（求用户进一步提供关于该问题的已知事实，若能提供，则转（2 2）；）；否则，说明该问题无解，终止问题求解过程。否则，说明该问题无解，终止问题求解过程。（7 7）若知识库中不再有未使用规则，

11、也说明该问题无解，终止问题求若知识库中不再有未使用规则，也说明该问题无解，终止问题求解过程。解过程。R1该动物是人R2 该动物会思考R3 该动物有智慧该动物会劳动该动物脑部没毛病2021/6/1618例2:设字符转换规则为:ABCACDBEFDE已知：A，B求：F2021/6/1619分析:一、数据库x，其中x为字符二、规则集1，IF AB THEN C2，IF AC THEN D3，IF BC THEN G4，IF BE THEN F5，IF D THEN E2021/6/1620三、控制策略顺序排队四、初始数据A，B五、结束条件Fx2021/6/1621求解过程数据库可触发规则被触发规则A

12、，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，F1，IF AB THEN C 2，IF AC THEN D3，IF BC THEN G 4，IF BE THEN F5，IF D THEN E2021/6/1622例3: 设综合数据库db的初始内容为集合a,b,c, 其中a、b、c均为字符； 规则库包含以下三条插入双字符的规则： R1: ?(a b db) =insert(db,ab) R2: ?(a c db) =insert(db,ac) R3: ?(b c db) =ins

13、ert(db,bc)推理的目标是使db成为： a, b, c, ab, ac, bc2021/6/1623规则库综合数据库产生式系统：产生式系统：综合据库、产生式规则和控制系统。寻找满足要求的事实寻找满足要求的规则改变综合数据库的事实 控制策略作用说明下一步应该选用什么规则。 产生式系统的控制机制控制机制就是不断地挑选可触发触发/激活激活的规则对综合数据库进行操作，直至得到解答（综合数据库内容转变为描述了目标状态），或失败结束。 通常从选择规则到执行操作分3步： 1)匹配 2) 冲突解决 3) 操作2021/6/1624冲突解决被触发的规则不一定总是启用规则。 因为可能同时有几条规则的条件部分

14、被满足。 这就要在解决冲突中来解决这个问题。 在复杂的情况下，在数据库和规则的条件部分之间可能要进行近似匹配。 2021/6/1625两条美式足球规则 R1：进攻一方如果在前三次进攻中前进的距离少于10码(short yardage)，那么在第四次进攻(fourth dawn)时，可以踢悬空球(punt)。 R2：如果进攻这一方，在前三次进攻中，前进的距离少于10码，而进攻的位置又在离对方球门线30码距离之内，那么就可以射门(field goal)。2021/6/1626专一性排序如果当前数据库包含事实“fourth dawn” 和 “short yardage” 以及 “within 30

15、yards”，则上述两条规则都被触发，这就需要用冲突解决来决定首先使用哪一条规则。 有很多种冲突解决策略，其中一种策略是先使用规则R2，因为R2的条件部分包括了更多的限制，因此规定了一个更为特殊的情况。这是一种按专一性来编排顺序的策略，称为专一性排序。 如果某一规则条件部分规定的情况，比另一规则条件部分规定的情况更有针对性，则这条规则有较高的优先级。 2021/6/1627规则1：问：该动物有奶吗？ 是。结论：这种动物为哺乳动物。规则2：问：该动物有奶吗？ 是。问：有蹄吗？ 是。结论：这种动物为有蹄动物。专一性排序2021/6/1628反例规则：如果该动物会飞，并且会下蛋，那么，该动物是鸟。补

16、充数据库:该动物有羽毛。2021/6/1629四、四、 产生式系统的推理方式产生式系统的推理方式2021/6/1630 1. 正向推理 2. 逆向推理 3. 双向推理四、四、 产生式系统的推理方式产生式系统的推理方式2021/6/1631例1：（Mammal ?x） (Eat ?x Meat) (Carnivore ?x)IF(Mammal Dog) (Eat Dog Meat)THEN(Carnivore Dog )2021/6/1632例例2：文法分析问题：文法分析问题 （正向推理）一组重写规则作为产生式规则： N NP /名词就是名词词组；DET NP NP /冠词加名词词组还是名词词组

17、；P NP PP /介词加名词词组构成介词词组；NP PP NP /名词词组后跟介词词组仍是名词词组；V NP PP VP /动词词组后跟名词词组和介词词组构成谓语；NP VP S /名词词组与谓语一起构成句子；2021/6/1633作文法分析的句子是：the boy plays football in the place.1）将该句子的所有单词先替换为语法词汇：DET N V N P DET N2）作进一步的替代为：NP V NP PP3）通过激活规则去进行符号重写：NP VP4）最后，综合数据库只剩下符号S（指示合法句），文法分析成功结束。2021/6/1634 例例3 ：区分动物区分动物

18、（逆向推理）逆向推理） 机器人去逛动物园，为帮助它区分其中的七种动物，机器人去逛动物园，为帮助它区分其中的七种动物，给它存入了如下几条产生式规则：给它存入了如下几条产生式规则： p1：若动物有毛发，则它是：若动物有毛发，则它是哺乳动物哺乳动物；p2：若动物有奶，则它是哺乳动物；：若动物有奶，则它是哺乳动物；p3：若动物有羽毛，则它是鸟类；：若动物有羽毛，则它是鸟类；p4：若动物会飞且生蛋，则它是鸟类；：若动物会飞且生蛋，则它是鸟类；p5：若动物是哺乳动物且吃肉，则它是：若动物是哺乳动物且吃肉，则它是食肉动物食肉动物；p6：若动物是哺乳动物且有犬齿，有爪，眼睛紧盯着前方，则它：若动物是哺乳动物且

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

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

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

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

23、长长颈鹿颈鹿；p12：若动物是有蹄类，白色有黑条纹，则它是：若动物是有蹄类，白色有黑条纹，则它是斑马斑马；p13：若动物是鸟，不会飞，长腿，长脖子，黑、白色，则它是驼鸟；：若动物是鸟，不会飞，长腿，长脖子，黑、白色，则它是驼鸟；p14：若动物是鸟，不会飞，会游泳，黑、白色，则它是企鹅；：若动物是鸟，不会飞，会游泳，黑、白色，则它是企鹅；p15：若动物是鸟，善飞，则它是信天翁。：若动物是鸟，善飞，则它是信天翁。哺乳、有蹄是中间结果哺乳、有蹄是中间结果网络中标识出逻辑关系合取与析取网络中标识出逻辑关系合取与析取2021/6/1638 小结小结 1 产生式由产生式由前项前项P和和后项后项R两部分组成

24、两部分组成P R 2 产生式的表示产生式的表示 1) 可用谓词逻辑、符号和语言的形式表示事实及规则。2021/6/1639谓词表示谓词表示 ：1) MAN(ZHAOLING) 真值 T / F2) WOMAN(ZHAOLING) 真值 T / F 3) FLY (X) （EGG( X) IS IS (X, BIRD) IF 动物会飞动物会飞 AND 会下蛋会下蛋 THEN 该动物可能是鸟该动物可能是鸟。2021/6/16403 产生式与蕴涵式 产生式的特殊形式为蕴涵。 表示不精确知识 / 精确知识 进行不精确匹配 / 精确匹配 无真值 / 有真值 T / F2021/6/1641产生式应用实例

25、2021/6/1642有N个传教士和N个野人要过河。约束条件: 现在有一条船只能承载K个人（包括野人和传教士），KN。 在任何时刻，如果有野人和传教士在一起（包括岸上与船上），必须要求传教士的人数多于或等于野人的人数。 传教士和野人都可以撑船过河2021/6/1643变量m 传教士在左岸的实际人数变量c：野人在左岸的实际人数变量变量b: 指示船是否在左岸（值1指示船在左岸，否 则为0）综合数据库综合数据库: （ m ， c ，b） 初始状态: （N，N，1） 目标状态: （0，0，0）2021/6/16442）传教士与野人问题L(Sm,Sc):从左岸到右岸的划船操作R(Sm,Sc):从右岸回到

26、左岸的划船操作规则库规则库:例：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 2021/6/1645传教士野人问题传教士野人问题规则库规则库（N=3，K=2） if L10 ( M ,C , B=1 ) then ( M1 , C , B =0 ) if L01 ( M ,C , B=1 ) then ( M , C1 , B =0 ) if L11 ( M

27、 ,C , B=1 ) then ( M1 , C1 , B =0 ) if L20 ( M ,C , B=1 ) then ( M2 , C , B =0) if L02 ( M ,C , B=1 ) then ( M , C2 , B =0 ) if R10 ( M ,C , B=0 ) then ( M+1 , C , B=1) if R01 ( M ,C , B=0 ) then ( M , C+1 , B =1 ) if R11 ( M ,C , B=0 ) then ( M+1 , C +1, B =1 ) if R20 ( M ,C , B=0 ) then ( M+2 , C

28、, B =1 ) if R02 ( M ,C , B=0 ) then ( M , C +2,B =1) 指示推理成功结束（到达目标状态）的规则：m = 0 c = 0 b = 0 T halt()；R1R2R3R4R5R6R7R8R9R102021/6/1646例例2八数码游戏规则八数码游戏规则 在3*3的方格棋盘上放置分别标语有数字的八张牌： 初始状态为S0 目标状态为Sg 。 可使用的操作算符： 位于空格的的牌 移入空格。2021/6/1647 操作算符 通过空格移动来实现棋盘布局。 设 Sij 指示第i行第j列的数码（1i, j3），io、jo指示空格所在的行、列数，则有： R1: j

29、o -1 1 = Siojo := Sio(jo-1) Sio(jo-1) := 0 (空格左移)R2: io -1 1 = Siojo := S(io-1)jo S(io-1)jo := 0 (空格上移)R3: jo + 1 3 = Siojo := Sio(jo+1) Sio(jo+1) := 0 (空格右移)R4: io + 1 3 = Siojo := S(io+1)jo S(io+1)jo := 0 (空格下移)2021/6/1648 例3 旅行商问题 一个在A城市工作的推销员需去几个外地城市办理业务，每个城市只允许去一次，遍历这些城市后返回A城市；已知各城市间的里程，要求寻找最短的

30、遍历路线。假设推销员需去4个外地城市B、C、D、E。BACDE2021/6/1649 综合数据库的内容表示为城市名列表，初始时该列表只包含城市A。设： 真值函数not-visit(x)指示未访问过城市x， 真值函数visit-all指示已遍历各城市， 操作函数move(x)指示去城市x并将x加进城市名列表；二条规则： R1: not-visit(x) T move(x),R2: visit-all( ) T move(A). 由于有4个外地城市，所以推理开始时相应于规则R1，有4条规则实例激活，分别相应于x取值B、C、D、E。 若以上、下2城市间路径最短作为冲突解决的依据，则相应于x := C

31、的规则实例被选用，即推销员走向城市C。 依次，经由推理，推销员将相继走向城市D、B、E。 接下去规则R2激活，推销员返回城市A。2021/6/1650例4 BADHAIRCUT 男孩规则如果HAIRCUT满意,则GOHOME否则,继续HAIRCUT 男孩规则如果HAIRCUT不满意,则继续HAIRCUT 否则男孩 GOHOME2021/6/1651BADHAIRCUT 正向推理: !男孩错误:前面满意,不等于(后面)满意,条件不充分2021/6/1652例例5 拍苍蝇拍苍蝇规则规则1如果天使拍到苍蝇苍蝇,则苍蝇苍蝇死2如果天使砸到苍蝇苍蝇,则苍蝇苍蝇死逆向推理逆向推理: 苍蝇苍蝇死 拍拍 砸砸

32、 2021/6/1653 附 1 产生式系统(Production system)首先是由Post 等提出的产生式规则(Production rule 1943)而得名的。 2021/6/1654 爱德华费根鲍姆 （Edward A. Feigenbaum) 知识工程的提出者，大型人工智能系统的开拓者 DENDRA。MYCINE 管理 诊断感染性疾病的专家系统DENDRA 化学分子结构专家系统 斯坦福大学利用产生式系统结构设计出第一个专家系统 (1965)2021/6/1655附2：English Words Predicate Calculus Meta knowledge “元知识” Pr

33、oductions Productions Systems Fire Work Memory2021/6/16561 有N个传教士和N个野人要过河。给出过河方案。 现在有一条船只能承载K个人（包括野人），KN。 在任何时刻，如果有野人和传教士在一起，必须要求传教士的人数多于或等于野人的人数。 传教士和野人都可以撑船过河2021/6/1657传教士野人问题传教士野人问题规则库规则库（N=2，K=2）if L10 ( M ,C , B=1 ) then ( M1 , C , B =0 ) if L01 ( M ,C , B=1 ) then ( M , C1 , B =0 ) if L11 ( M

34、 ,C , B=1 ) then ( M1 , C1 , B =0 ) if L20 ( M ,C , B=1 ) then ( M2 , C , B =0) if L02 ( M ,C , B=1 ) then ( M , C2 , B =0 ) if R10 ( M ,C , B=0 ) then ( M+1 , C , B=1) if R01 ( M ,C , B=0 ) then ( M , C+1 , B =1 ) if R11 ( M ,C , B=0 ) then ( M+1 , C +1, B =1 ) if R20 ( M ,C , B=0 ) then ( M+2 , C , B =1 ) if R02 ( M ,C , B=0 ) then ( M , C +2,B =1)R1R2R3R4R5R6R7R8R9R102021/6/1658 古代有个国王想知道他的二个大臣中谁最聪明，古代有个国王想知道他的二个大臣中谁最聪明，就在他们每个人前额上画了一个点，告诉他们就在他们每个人前额上画了一个点，告诉他们至少有至少有一个人额上的点是白色的一个人额上的点是白色的，并且重复地问他们：，并且重复地问他们：“谁谁知道自己点的颜色？知道自己点的颜色？” 他们头一次都回答说不知道。设每人都