《产生式知识表示与第二次大实验》由会员分享,可在线阅读,更多相关《产生式知识表示与第二次大实验(60页珍藏版)》请在金锄头文库上搜索。
1、2、产生式表示、产生式表示12、产生式表示、产生式表示n产生式表示的起源产生式表示的起源q1943,美国数学家,美国数学家 Post 构造了形式化的计算工具构造了形式化的计算工具q1955,美国语言学家,美国语言学家乔姆斯基乔姆斯基 Chomsky创立了转换创立了转换生成语法生成语法q1960,美国计算机科学家,美国计算机科学家巴克斯巴克斯 Backus提出了提出了巴巴克斯范式,描述克斯范式,描述ALGOL 60的语法规则,的语法规则,1977年获年获图灵奖图灵奖q1972年,纽厄尔和西蒙在研究人类的认知模型中开年,纽厄尔和西蒙在研究人类的认知模型中开发了基于规则的产生式系统。发了基于规则的产
2、生式系统。1975年获图灵奖,人年获图灵奖,人工智能符号主义学派创始人工智能符号主义学派创始人 22、产生式表示、产生式表示n产生式产生式(condition-action规则规则)的基本形式的基本形式qPQ 或者或者 IF P THEN Q; P:前件前件condition,是产生式的前提,它给出了该产生式可,是产生式的前提,它给出了该产生式可否使用的先决条件,由事实的逻辑组合来构成否使用的先决条件,由事实的逻辑组合来构成 Q:后件后件action,是一组结论或操作,它指出当前题,是一组结论或操作,它指出当前题P满足时,满足时,应该推出的结论或应该执行的动作应该推出的结论或应该执行的动作n产
3、生式的含义产生式的含义q如果前提如果前提P满足,则可推出结论满足,则可推出结论Q或执行或执行Q所规定的操作所规定的操作n事实事实+规则规则32、产生式表示、产生式表示n事实:事实:q第一类:给一个语言变量赋值第一类:给一个语言变量赋值如:香蕉是黄色的,如:香蕉是黄色的, 老李年龄老李年龄35岁岁 张韶涵是一个歌手张韶涵是一个歌手q表示表示 三元组;三元组;(对象,属性,值对象,属性,值)香蕉是黄色的香蕉是黄色的 (banana,color,yellow)老李年龄老李年龄35岁岁 (Li,age,35)张韶涵是一个歌手张韶涵是一个歌手 (Angela Chang ,job,Singer)42、产
4、生式表示、产生式表示q第二类:描述多个语言变量之间的关系第二类:描述多个语言变量之间的关系n如:小莉是小刘的女朋友如:小莉是小刘的女朋友 王老师是张三的导师王老师是张三的导师 天青色等烟雨天青色等烟雨 q表示表示 三元组;三元组; (关系,对象关系,对象1,对象,对象2)小莉是小刘的女朋友小莉是小刘的女朋友 (girlfriend,Li,Liu)王老师是张三的导师王老师是张三的导师 (tutor,Mr Wang,Zhangsan)天青色等烟雨天青色等烟雨 (wait for,azure,misty rain)52、产生式表示、产生式表示q存在不确定条件的表示存在不确定条件的表示四元组:四元组:
5、 (对象,属性,值,可信度对象,属性,值,可信度(0-1之间的数之间的数)硬币有硬币有50%的可能为正面向上的可能为正面向上 (coin,up,obverse,0.5)全班全班2/3的同学爱听周杰伦的歌的同学爱听周杰伦的歌(student,like Jay Chou songs,true,0.667)产生式表示有产生式表示有70%的可能会考的可能会考(CA,test,true,0.7)62、产生式表示、产生式表示n规则规则q表示事实间的因果关系表示事实间的因果关系q以以if then的形式描述的形式描述q一般形式为:前件一般形式为:前件后件后件q前件通常为一些事实的合取或者析取前件通常为一些事
6、实的合取或者析取q后件可以是结论,也可以是动作后件可以是结论,也可以是动作q一个产生式规则的结论可以作为另一个产生式规则一个产生式规则的结论可以作为另一个产生式规则的前提的前提72、产生式表示、产生式表示n例例qIf 天下雪了天下雪了 then穿棉袄穿棉袄qIf 骄傲被现实大海冷冷拍下骄傲被现实大海冷冷拍下 then 懂得要多努力才懂得要多努力才能走到远方能走到远方qIf 水电解水电解 then (生成氢气生成氢气生成氧气生成氧气)qIf (想考研想考研学习好学习好毕业生毕业生) then 考研成功考研成功qIf (动物有犬齿动物有犬齿 有爪有爪 眼盯前方眼盯前方) then 食肉动食肉动物物
7、qIf (有有流感症状流感症状 (去过去过甲流甲流疫区疫区接触过甲流患者接触过甲流患者) ) then 甲流,可信度甲流,可信度 x82、产生式表示、产生式表示n以产生式规则求解问题的系统称作产生式系统以产生式规则求解问题的系统称作产生式系统n产生式系统的结构产生式系统的结构92、产生式表示、产生式表示q知识库知识库n规则库:存放产生式规则规则库:存放产生式规则q包含从初始状态到目标状态的所有变换规则包含从初始状态到目标状态的所有变换规则q完整性、一致性、准确性、合理性、灵活性完整性、一致性、准确性、合理性、灵活性n数据库:存放事实数据库:存放事实q已知事实已知事实q中间结果中间结果q推理结果
8、推理结果n匹配规则:当数据库中的事实与规则库中的产生式规则的匹配规则:当数据库中的事实与规则库中的产生式规则的前件相匹配时,该规则被激活,其结论成为中间结果加入前件相匹配时,该规则被激活,其结论成为中间结果加入数据库数据库102、产生式表示、产生式表示q推理机:推理机:n问题求解的实现部件问题求解的实现部件n控制整个产生式系统的运行控制整个产生式系统的运行n决定推理路线决定推理路线n控制协同规则库与数据库控制协同规则库与数据库q推理机的工作推理机的工作n规则匹配规则匹配n冲突消解冲突消解n执行后件执行后件n终止条件终止条件112、产生式表示、产生式表示q规则匹配:按一定策略从规则库选择规则与数
9、据库规则匹配:按一定策略从规则库选择规则与数据库中的事实进行匹配中的事实进行匹配n匹配成功:此条规则被激活,加入被激活候选集(冲突集)匹配成功:此条规则被激活,加入被激活候选集(冲突集) 事实:牛;事实:牛; 规则:规则: if 牛牛 then 吃草吃草 n匹配失败:输入与已知条件矛盾,此条规则被放弃匹配失败:输入与已知条件矛盾,此条规则被放弃 事实:牛;事实:牛; 规则:规则: if 马马 then 吃草吃草n匹配无结果:规则前件与事实无关,则该条规则加入待测匹配无结果:规则前件与事实无关,则该条规则加入待测式规则集式规则集 事实:牛;事实:牛; 规则:规则: if 有蹄有蹄 then 吃草
10、吃草122、产生式表示、产生式表示q冲突消解:当匹配成功的规则多于一条时,需要根冲突消解:当匹配成功的规则多于一条时,需要根据一定的策略进行选择据一定的策略进行选择n事实:牛;事实:牛; n规则规则1: if 牛牛 then 吃草吃草n规则规则2: if 牛牛 then 有蹄有蹄n冲突消解策略:依次执行冲突消解策略:依次执行2条规则条规则132、产生式表示、产生式表示q有时多条规则间会存在相互冲突有时多条规则间会存在相互冲突n事实:地震,室内,教师,有未成年人事实:地震,室内,教师,有未成年人n规则:规则: R1: if 地震地震室内室内then 跑出室外跑出室外 R2: if 地震地震室内室
11、内 教师教师 then 组织学生跑出室外组织学生跑出室外 R3: if 地震地震室内室内有未成年人有未成年人 then 保护未成年人保护未成年人n冲突消解策略为:冲突消解策略为: R3 R2 R1142、产生式表示、产生式表示q执行后件:如果后件不是问题的目标,则解释并执执行后件:如果后件不是问题的目标,则解释并执行规则后件的动作行规则后件的动作n如果后件是一个或者多个结论,则将其加入数据库中如果后件是一个或者多个结论,则将其加入数据库中事实:牛;事实:牛; 规则:规则: if 牛牛 then 有蹄有蹄 执行结果:将执行结果:将“有蹄有蹄”加入数据库中加入数据库中n如果后件是一个或多个行动,则
12、按照一定策略执行如果后件是一个或多个行动,则按照一定策略执行事实:地震,睡午觉事实:地震,睡午觉规则:规则:if 地震地震睡午觉睡午觉 then 跑跑穿衣服穿衣服q终止条件终止条件n如果后件是问题的目标,则结束,输出求解路径如果后件是问题的目标,则结束,输出求解路径 152、产生式表示、产生式表示n产生式系统的推理产生式系统的推理q正向推理正向推理n从已知事实出发,与规则库中的规则匹配的方式从已知事实出发,与规则库中的规则匹配的方式n自底向上,也称为数据驱动方式自底向上,也称为数据驱动方式q反向推理反向推理n从目标出发,反向使用规则,直到找到已知事实从目标出发,反向使用规则,直到找到已知事实n
13、自顶向下,也称为目标驱动方式自顶向下,也称为目标驱动方式q双向推理双向推理n正向推理与反向推理同时使用,直到在某一中间结果重合正向推理与反向推理同时使用,直到在某一中间结果重合162、产生式表示、产生式表示n正向推理的步骤正向推理的步骤步步1 将初始事实置入动态数据库;将初始事实置入动态数据库;步步2 用用动动态态数数据据库库中中的的事事实实,匹匹配配目目标标条条件件,若若目目标标条件满足,则推理成功,结束。条件满足,则推理成功,结束。 步步3 用用规规则则库库中中各各规规则则的的前前件件匹匹配配动动态态数数据据库库中中的的事事实实,将匹配成功的规则组成冲突集;,将匹配成功的规则组成冲突集;步
14、步4 若冲突集为空,则运行失败,退出。若冲突集为空,则运行失败,退出。步步5 对对冲冲突突集集做做冲冲突突消消解解,对对选选择择执执行行的的各各规规则则,将将其结论加入动态数据库,或执行其动作,转步其结论加入动态数据库,或执行其动作,转步2。17182、产生式表示、产生式表示n例:植物分类问题的产生式系统描述及其求解例:植物分类问题的产生式系统描述及其求解q设由下列植物识别规则组成一个规则库,推理机采用正向推设由下列植物识别规则组成一个规则库,推理机采用正向推理算法,建立一个产生式系统。理算法,建立一个产生式系统。q规则规则R1: if 它种子的胚有两个子叶它种子的胚有两个子叶它的叶脉为网状它
15、的叶脉为网状 then 它是双子叶植物它是双子叶植物R2: if 它种子的胚有一个子叶它种子的胚有一个子叶 then 它是单子叶植物它是单子叶植物R3: if 它的叶脉平行它的叶脉平行 then 它是单子叶植物它是单子叶植物R4: if (它是双子叶植物它是双子叶植物 它的花托呈杯形它的花托呈杯形) (它是双子叶植它是双子叶植 物物 它的花为两性它的花为两性 它的花瓣有它的花瓣有5枚枚) then 它是蔷薇科植物它是蔷薇科植物192、产生式表示、产生式表示R5: if 它是蔷薇科植物它是蔷薇科植物它的果实为核果它的果实为核果 then 它是李亚科它是李亚科植物植物R6: if 它是蔷薇科植物它
16、是蔷薇科植物它的果实为梨果它的果实为梨果 then 它是苹果亚它是苹果亚科植物科植物R7: if 它是李亚科植物它是李亚科植物它的果皮有毛它的果皮有毛 then 它是桃它是桃R8: if 它是李亚科植物它是李亚科植物它的果皮光滑它的果皮光滑 then 它是李它是李R9: if 它的果实为扁圆形它的果实为扁圆形它的果实外有纵沟它的果实外有纵沟 then 它是桃它是桃R10: if 它是苹果亚科植物它是苹果亚科植物它的果实里无石细胞它的果实里无石细胞 then 它是它是苹果苹果R11: if 它是苹果亚科植物它是苹果亚科植物它的果实里有石细胞它的果实里有石细胞 then 它是它是梨梨R12: if
17、 它的果肉为乳黄色它的果肉为乳黄色它的果肉质脆它的果肉质脆 then 它是苹果它是苹果202、产生式表示、产生式表示q初始事实:初始事实:n它的果肉为乳黄色它的果肉为乳黄色n它的果实里无石细胞它的果实里无石细胞n它的果实为梨果它的果实为梨果n它的果实无毛它的果实无毛n它的花托呈杯形它的花托呈杯形n它种子的胚有两个子叶它种子的胚有两个子叶q目标条件:该植物是什么目标条件:该植物是什么q设动态数据库、冲突集、待测试规则集均为空设动态数据库、冲突集、待测试规则集均为空212、产生式表示、产生式表示n推理过程推理过程q初始事实写入动态数据库初始事实写入动态数据库 果肉为乳黄色,果实里无石细胞,果实为梨
18、果,果实无毛,果肉为乳黄色,果实里无石细胞,果实为梨果,果实无毛, 花托呈杯形,种子的胚有两个子叶花托呈杯形,种子的胚有两个子叶第一次循环第一次循环q用动态数据库的事实匹配目标条件,目标条件不成立用动态数据库的事实匹配目标条件,目标条件不成立q用规则库中的规则逐一与数据库匹配用规则库中的规则逐一与数据库匹配R1: if 它种子的胚有两个子叶它种子的胚有两个子叶它的叶脉为网状它的叶脉为网状 then 它是双子叶植物它是双子叶植物 ”双子叶胚双子叶胚”匹配成功,冲突集为匹配成功,冲突集为R1R2: if 它种子的胚有一个子叶它种子的胚有一个子叶 then 它是单子叶植物它是单子叶植物 匹配失败,该
19、条规则放弃匹配失败,该条规则放弃R3: if 它的叶脉平行它的叶脉平行 then 它是单子叶植物它是单子叶植物 匹配无结果,该条规则加入待测试规则集,待测试规则集匹配无结果,该条规则加入待测试规则集,待测试规则集R3 222、产生式表示、产生式表示事实:事实:果肉为乳黄色,果实里无石细胞,果实为梨果,果实无毛,果肉为乳黄色,果实里无石细胞,果实为梨果,果实无毛, 花托呈杯形,种子的胚有两个子叶花托呈杯形,种子的胚有两个子叶R4:if (它是双子叶植物它是双子叶植物 它的花托呈杯形它的花托呈杯形) (它是双子叶植它是双子叶植 物物 它的花为两性它的花为两性 它的花瓣有它的花瓣有5枚枚) then
20、 它是蔷薇科植物它是蔷薇科植物 “双子叶植物双子叶植物”目前的动态数据库无法匹配,匹配无结果,该条目前的动态数据库无法匹配,匹配无结果,该条规则加入待测试规则集,待测试规则集规则加入待测试规则集,待测试规则集R3, R4R5: if 它是蔷薇科植物它是蔷薇科植物它的果实为核果它的果实为核果 then 它是李亚科植物它是李亚科植物 “果实为梨果果实为梨果” 匹配失败,该条规则放弃匹配失败,该条规则放弃R6: if 它是蔷薇科植物它是蔷薇科植物它的果实为梨果它的果实为梨果 then 它是苹果亚科植物它是苹果亚科植物 “蔷薇科植物蔷薇科植物”目前的动态数据库无法匹配,匹配无结果,该条目前的动态数据库
21、无法匹配,匹配无结果,该条规则加入待测试规则集,待测试规则集规则加入待测试规则集,待测试规则集R3, R4 , R6232、产生式表示 事实:事实:果肉为乳黄色,果实里无石细胞,果实为梨果,果实无毛,果肉为乳黄色,果实里无石细胞,果实为梨果,果实无毛, 花托呈杯形,种子的胚有两个子叶花托呈杯形,种子的胚有两个子叶R7: if 它是李亚科植物它是李亚科植物它的果皮有毛它的果皮有毛 then 它是桃它是桃 ”果实有毛果实有毛“匹配失败,该条规则放弃匹配失败,该条规则放弃R8: if 它是李亚科植物它是李亚科植物它的果皮光滑它的果皮光滑 then 它是李它是李 匹配无结果,待测试规则集匹配无结果,待
22、测试规则集R3, R4 , R6, R8R9: if 它的果实为扁圆形它的果实为扁圆形它的果实外有纵沟它的果实外有纵沟 then 它是桃它是桃 匹配无结果,待测试规则集匹配无结果,待测试规则集R3, R4 , R6, R8, R9R10: if 它是苹果亚科植物它是苹果亚科植物它的果实里无石细胞它的果实里无石细胞 then 它是苹果它是苹果 匹配无结果,待测试规则集匹配无结果,待测试规则集R3, R4 , R6, R8, R9, R10242、产生式表示、产生式表示 事实:事实:果肉为乳黄色,果实里无石细胞,果实为梨果,果实无毛,果肉为乳黄色,果实里无石细胞,果实为梨果,果实无毛, 花托呈花托
23、呈杯形,种子的胚有两个子叶杯形,种子的胚有两个子叶R11: if 它是苹果亚科植物它是苹果亚科植物它的果实里有石细胞它的果实里有石细胞 then 它是梨它是梨 ”果实有石细胞果实有石细胞“ 匹配失败,该条规则放弃匹配失败,该条规则放弃R12: if 它的果肉为乳黄色它的果肉为乳黄色它的果肉质脆它的果肉质脆 then 它是苹果它是苹果 匹配无结果,待测试规则集匹配无结果,待测试规则集R3, R4 , R6, R8, R9, R10, R12q冲突消解冲突消解 冲突集冲突集R1无冲突,则将后件加入动态数据库无冲突,则将后件加入动态数据库 果肉为乳黄色,果实里无石细胞,果实为梨果,果实无毛,果肉为乳
24、黄色,果实里无石细胞,果实为梨果,果实无毛, 花托呈杯形,种子的胚有两个子叶,花托呈杯形,种子的胚有两个子叶,双子叶双子叶252、产生式表示、产生式表示第二次循环第二次循环q用动态数据库的事实匹配目标条件,目标条件不成立用动态数据库的事实匹配目标条件,目标条件不成立q用待测试规则库中的规则与数据库匹配用待测试规则库中的规则与数据库匹配 R3, R4 , R6, R8, R9, R10, R12 果肉为乳黄色,果实里无石细胞,果实为梨果,果实无毛,花托果肉为乳黄色,果实里无石细胞,果实为梨果,果实无毛,花托呈杯形,种子的胚有两个子叶,双子叶呈杯形,种子的胚有两个子叶,双子叶 R4: if (它是
25、双子叶植物它是双子叶植物 它的花托呈杯形它的花托呈杯形) (它是双子叶植它是双子叶植 物物 它的花为两性它的花为两性 它的花瓣有它的花瓣有5枚枚) then 它是蔷薇科植物它是蔷薇科植物匹配成功,冲突集为匹配成功,冲突集为R4 R3、6、8、9、10、R12 :匹配无结果,新待测试规则集匹配无结果,新待测试规则集R3 , R6 , R8 , R9 , R10, R12262、产生式表示、产生式表示q冲突消解冲突消解 冲突集冲突集R4无冲突,则将后件加入动态数据库无冲突,则将后件加入动态数据库 果肉为乳黄色,果实里无石细胞,果实为梨果,果实无毛,果肉为乳黄色,果实里无石细胞,果实为梨果,果实无毛
26、, 花托呈杯形,种子的胚有两个子叶,双子叶,花托呈杯形,种子的胚有两个子叶,双子叶,蔷薇科蔷薇科第三次循环第三次循环q用动态数据库的事实匹配目标条件,目标条件不成立用动态数据库的事实匹配目标条件,目标条件不成立q用待测试规则库中的规则与数据库匹配用待测试规则库中的规则与数据库匹配 R3, R6, R8, R9, R10, R12 R6: if 它是蔷薇科植物它是蔷薇科植物它的果实为梨果它的果实为梨果 then 它是苹果亚科植物它是苹果亚科植物 匹配成功,冲突集为匹配成功,冲突集为R6 R3、8、9、10、R12 :匹配无结果,新待测试规则集匹配无结果,新待测试规则集R3 , R8 , R9 ,
27、 R10, R12272、产生式表示、产生式表示q冲突消解冲突消解 冲突集冲突集R6无冲突,则将后件加入动态数据库无冲突,则将后件加入动态数据库 果肉为乳黄色果肉为乳黄色, 果实里无石细胞果实里无石细胞, 果实为梨果果实为梨果, 果实无毛果实无毛, 花托呈杯形花托呈杯形, 种子的胚有两个子叶种子的胚有两个子叶, 双子叶双子叶, 蔷薇科蔷薇科, 苹果亚科苹果亚科第四次循环第四次循环q用动态数据库的事实匹配目标条件,目标条件不成立用动态数据库的事实匹配目标条件,目标条件不成立q用待测试规则库中的规则与数据库匹配用待测试规则库中的规则与数据库匹配 R3, R8, R9, R10, R12 R10:
28、if 它是苹果亚科植物它是苹果亚科植物它的果实里无石细胞它的果实里无石细胞 then 它是苹果它是苹果 匹配成功,冲突集为匹配成功,冲突集为R10 R3、8、9、12 :匹配无结果,新待测试规则集匹配无结果,新待测试规则集R3 , R8 , R9 , R12282、产生式表示、产生式表示q冲突消解冲突消解 冲突集冲突集R10无冲突,则将后件加入动态数据库无冲突,则将后件加入动态数据库 果肉为乳黄色果肉为乳黄色, 果实里无石细胞果实里无石细胞, 果实为梨果果实为梨果, 果实无毛果实无毛, 花托呈杯形花托呈杯形, 种子的胚有两个子叶种子的胚有两个子叶, 双子叶双子叶, 蔷薇科蔷薇科, 苹果亚科苹果
29、亚科, 苹苹果果第五次循环第五次循环q用动态数据库的事实匹配目标条件,目标条件满足,结束循环用动态数据库的事实匹配目标条件,目标条件满足,结束循环q结果为苹果结果为苹果n正向推理是一种自底向上的推理方法正向推理是一种自底向上的推理方法292、产生式表示、产生式表示n例:冲突消解例:冲突消解q同一事实与多条规则匹配成功时,进行冲突消解同一事实与多条规则匹配成功时,进行冲突消解n事实:地震,室内,教师,有未成年人事实:地震,室内,教师,有未成年人n规则:规则: R1: if 地震地震室内室内then 跑出室外跑出室外 R2: if 地震地震室内室内 教师教师 then 组织学生跑出室外组织学生跑出
30、室外 R3: if 地震地震室内室内有未成年人有未成年人 then 保护未成年人保护未成年人n匹配过程匹配过程 R1: 匹配成功,冲突集为匹配成功,冲突集为 R1 R2: 匹配成功,冲突集为匹配成功,冲突集为 R1, R2 R3: 匹配成功,冲突集为匹配成功,冲突集为 R1, R2, R3n冲突消解,冲突消解,执行执行R3302、产生式表示、产生式表示不进行冲突消解会引起的错误不进行冲突消解会引起的错误R1: 匹配成功,不考虑冲突消解,执行后件匹配成功,不考虑冲突消解,执行后件“跑出教室跑出教室”, 数据库数据库 地震,地震,室外室外,教师,有未成年人,教师,有未成年人R2、 R3全部匹配失败
31、全部匹配失败q不同事实与规则匹配成功时,需要进行冲突消解吗?不同事实与规则匹配成功时,需要进行冲突消解吗?n事实:地震,教师,夏天事实:地震,教师,夏天n规则:规则:R1: if 地震地震 then 跑跑 R2: if 教师教师 then 上课上课 R3: if 夏天夏天 then 穿短袖穿短袖n冲突集冲突集 R1, R2, R3n冲突消解,执行冲突消解,执行R1 , R3 312、产生式表示、产生式表示n正向推理总结正向推理总结q用规则库中各规则的前件匹配动态数据库中的事实用规则库中各规则的前件匹配动态数据库中的事实q是一种自底向上的推理方法是一种自底向上的推理方法q将匹配成功的规则组成冲突
32、集,进行冲突消解将匹配成功的规则组成冲突集,进行冲突消解n反向推理:从目标出发,反向使用规则,直到反向推理:从目标出发,反向使用规则,直到找到已知事实找到已知事实322、产生式表示、产生式表示n反向推理步骤反向推理步骤: 步步1 将初始事实置入动态数据库,将目标条件置入目标集;将初始事实置入动态数据库,将目标条件置入目标集; 步步2 若目标集为空,则推理成功,结束。若目标集为空,则推理成功,结束。 步步3 取取目目标标集集中中第第一一个个目目标标,用用动动态态数数据据库库中中的的事事实实同同其其匹匹配配,若匹配成功,删除该目标,转步若匹配成功,删除该目标,转步2; 步步4 用用规规则则集集中中
33、的的各各规规则则的的后后件件同同该该目目标标匹匹配配,若若匹匹配配成成功功,则则将将第第一一个个匹匹配配成成功功且且未未用用过过的的规规则则的的前前件件作作为为新新的的目目标标,并并取代原来的父目标而加入目标集,转步取代原来的父目标而加入目标集,转步3; 步步5 若该目标是初始目标,则推理失败,退出。若该目标是初始目标,则推理失败,退出。 步步6 将将该该目目标标的的父父目目标标移移回回目目标标集集,取取代代该该目目标标及及其其兄兄弟弟目目标标,转步转步3。33342、产生式表示、产生式表示n恋爱规则产生式系统恋爱规则产生式系统q设由下列恋爱规则组成一个规则库,推理机采用逆向推理算设由下列恋爱
34、规则组成一个规则库,推理机采用逆向推理算法,建立一个产生式系统。法,建立一个产生式系统。q恋爱的各阶段恋爱的各阶段n认识认识n交往交往n赢得好感赢得好感n确立恋爱关系确立恋爱关系n建立长期关系建立长期关系q共存共存 q反依赖反依赖q独立独立q共生共生352、产生式表示、产生式表示q规则规则R1: if 请人介绍请人介绍 then 认识认识R2: if 参加聚会参加聚会 then 认识认识R3: if 搭讪搭讪 then 认识认识R4: if 设计邂逅设计邂逅 then 认识认识R5: if 认识认识一起自习一起自习 then 交往交往R6: if 认识认识送花送花 then 交往交往R7: i
35、f 认识认识约会约会 then 交往交往R8: if 交往交往(有责任心有责任心 踏实可靠踏实可靠) then 赢得好感赢得好感362、产生式表示、产生式表示R9: if 交往交往(温柔善良温柔善良 善解人意善解人意) then 赢得好感赢得好感R10: if 交往交往勤奋努力勤奋努力 then 赢得好感赢得好感R11: if 交往交往阳光活泼阳光活泼 then 赢得好感赢得好感R12: if 赢得好感赢得好感暗示暗示 then 确立恋爱关系确立恋爱关系R13: if 赢得好感赢得好感明示明示 then 确立恋爱关系确立恋爱关系R14: if 赢得好感赢得好感牵手牵手 then 确立恋爱关系确
36、立恋爱关系R15: if 恋爱关系恋爱关系 体贴容让体贴容让不百依百顺不百依百顺 then 建立长期建立长期关系关系372、产生式表示、产生式表示q初始事实:初始事实:n设计邂逅设计邂逅n送花送花n有责任心有责任心n勤奋努力勤奋努力n明确表示明确表示n体贴容让体贴容让n不百依百顺不百依百顺q目标条件:建立长期关系目标条件:建立长期关系q设动态数据库、目标集、待测试规则集均为空设动态数据库、目标集、待测试规则集均为空382、产生式表示、产生式表示n推理过程推理过程q初始事实写入动态数据库初始事实写入动态数据库 设计邂逅,送花,有责任心,勤奋努力,明示,体贴容让,不百依设计邂逅,送花,有责任心,勤
37、奋努力,明示,体贴容让,不百依百顺百顺q将目标条件置入目标集将目标条件置入目标集建立长期关系建立长期关系第一次循环第一次循环q目标集目标集建立长期关系建立长期关系不为空不为空q取目标集的第一条目标取目标集的第一条目标建立长期关系建立长期关系,用动态数据库中的事实与,用动态数据库中的事实与之匹配,匹配不成功之匹配,匹配不成功q用规则库中各条规则的后件与该目标匹配用规则库中各条规则的后件与该目标匹配R15:匹配成功,将其前件替换父目标放入目标集,转步匹配成功,将其前件替换父目标放入目标集,转步3 体贴容让,不百依百顺,恋爱关系体贴容让,不百依百顺,恋爱关系替换父目标替换父目标 建立长期关系建立长期
38、关系392、产生式表示、产生式表示第二次循环第二次循环q取目标集的第一条目标取目标集的第一条目标体贴容让体贴容让,用动态数据库中的,用动态数据库中的事实与之匹配,匹配成功,删除该目标,转步事实与之匹配,匹配成功,删除该目标,转步2第三次循环第三次循环q目标集目标集不百依百顺,恋爱关系不百依百顺,恋爱关系不为空不为空q取目标集的第一条目标取目标集的第一条目标不百依百顺不百依百顺,用动态数据库中,用动态数据库中的事实与之匹配,匹配成功,删除该目标,转步的事实与之匹配,匹配成功,删除该目标,转步2402、产生式表示、产生式表示第四次循环第四次循环q目标集目标集恋爱关系恋爱关系不为空不为空q取目标集的
39、第一条目标取目标集的第一条目标恋爱关系恋爱关系,用动态数据库中的事实与之匹,用动态数据库中的事实与之匹配,匹配不成功配,匹配不成功q用规则库中的规则后件与该目标匹配用规则库中的规则后件与该目标匹配R12: if 赢得好感赢得好感暗示暗示 then 确立恋爱关系确立恋爱关系 匹配成功,将其前件替换父目标放入目标集,转步匹配成功,将其前件替换父目标放入目标集,转步3 暗示,赢得好感暗示,赢得好感 替换父目标替换父目标 恋爱关系恋爱关系R12: if 赢得好感赢得好感暗示暗示 then 确立恋爱关系确立恋爱关系R13: if 赢得好感赢得好感明示明示 then 确立恋爱关系确立恋爱关系R14: if
40、 赢得好感赢得好感牵手牵手 then 确立恋爱关系确立恋爱关系412、产生式表示、产生式表示第五次循环第五次循环q取目标集的第一条目标取目标集的第一条目标暗示暗示,用动态数据库中的事实与之匹配,用动态数据库中的事实与之匹配,匹配不成功匹配不成功q用规则库中的规则后件与该目标匹配,无规则的后件能够匹配用规则库中的规则后件与该目标匹配,无规则的后件能够匹配q检查该目标是否为原始目标,不是,则继续执行推理检查该目标是否为原始目标,不是,则继续执行推理q将该目标的父目标移回目标集,取代该目标及其兄弟目标,转步将该目标的父目标移回目标集,取代该目标及其兄弟目标,转步3父目标为父目标为 替换该目标替换该目
41、标暗示暗示与兄弟目标与兄弟目标替换后目标集为替换后目标集为R12: if 赢得好感赢得好感暗示暗示 then 确立恋爱关系确立恋爱关系恋爱关系恋爱关系赢得好感赢得好感恋爱关系恋爱关系422、产生式表示、产生式表示第六次循环第六次循环q取目标集的第一条目标取目标集的第一条目标恋爱关系恋爱关系,用动态数据库中的事实与之匹,用动态数据库中的事实与之匹配,匹配不成功配,匹配不成功q用规则库中的规则后件与该目标匹配用规则库中的规则后件与该目标匹配R12: 已匹配过,舍弃已匹配过,舍弃R13: if 赢得好感赢得好感明示明示 then 确立恋爱关系确立恋爱关系匹配成功,将其前件替换父目标放入目标集,转步匹
42、配成功,将其前件替换父目标放入目标集,转步3 明示,赢得好感明示,赢得好感 替换父目标替换父目标 恋爱关系恋爱关系R12: if 赢得好感赢得好感暗示暗示 then 确立恋爱关系确立恋爱关系R13: if 赢得好感赢得好感明示明示 then 确立恋爱关系确立恋爱关系R14: if 赢得好感赢得好感牵手牵手 then 确立恋爱关系确立恋爱关系432、产生式表示、产生式表示第七次循环第七次循环 设计邂逅,送花,有责任心,勤奋努力,明示,体贴容让,不百依设计邂逅,送花,有责任心,勤奋努力,明示,体贴容让,不百依百顺百顺 q取目标集的第一条目标取目标集的第一条目标明示明示,用数据库中的事实与之匹配,匹
43、配,用数据库中的事实与之匹配,匹配成功,删除该目标,转步成功,删除该目标,转步2第八次循环第八次循环q目标集目标集赢得好感赢得好感不为空不为空q取目标集的第一条目标取目标集的第一条目标赢得好感赢得好感,用动态数据库中的事实与之匹,用动态数据库中的事实与之匹配,匹配不成功配,匹配不成功q用规则库中的规则后件与该目标匹配用规则库中的规则后件与该目标匹配 R8: if 交往交往(有责任心有责任心 踏实可靠踏实可靠) then 赢得好感赢得好感匹配成功,将其前件替换父目标放入目标集,转步匹配成功,将其前件替换父目标放入目标集,转步3 有责任心有责任心 踏实可靠,交往踏实可靠,交往 替换父目标替换父目标
44、 赢得好感赢得好感442、产生式表示、产生式表示第九次循环第九次循环设计邂逅,送花,有责任心,勤奋努力,明示,体贴容让,不百依设计邂逅,送花,有责任心,勤奋努力,明示,体贴容让,不百依百顺百顺 q取目标集的第一条目标取目标集的第一条目标 有责任心有责任心 踏实可靠踏实可靠 , 用动态数据库中的事实与之匹配,匹配成功,删除该目标,转步用动态数据库中的事实与之匹配,匹配成功,删除该目标,转步2第十次循环第十次循环q目标集目标集交往交往不为空不为空q取目标集的第一条目标取目标集的第一条目标交往交往,用动态数据库中的事实与之匹配,用动态数据库中的事实与之匹配,匹配不成功匹配不成功q用规则库中的规则后件
45、与该目标匹配用规则库中的规则后件与该目标匹配 R5: if 认识认识一起自习一起自习 then 交往交往 匹配成功,将其前件替换父目标放入目标集,转步匹配成功,将其前件替换父目标放入目标集,转步3 一起自习,认识一起自习,认识 替换父目标替换父目标 交往交往R5: if 认识认识一起自习一起自习 then 交往交往R6: if 认识认识送花送花 then 交往交往R7: if 认识认识约会约会 then 交往交往452、产生式表示、产生式表示第十一次循环第十一次循环设计邂逅,送花,有责任心,勤奋努力,明示,体贴容让,不百依设计邂逅,送花,有责任心,勤奋努力,明示,体贴容让,不百依百顺百顺 q取
46、目标集的第一条目标取目标集的第一条目标一起自习一起自习, 用动态数据库中的事实与之匹配,匹配不成功用动态数据库中的事实与之匹配,匹配不成功q用规则库中的规则后件与该目标匹配,无规则的后件能够匹配用规则库中的规则后件与该目标匹配,无规则的后件能够匹配q检查该目标是否为原始目标,不是,则继续执行推理检查该目标是否为原始目标,不是,则继续执行推理q将该目标的父目标移回目标集,取代该目标及其兄弟目标,转步将该目标的父目标移回目标集,取代该目标及其兄弟目标,转步3父目标为父目标为 交往交往替换该目标替换该目标一起自习一起自习与兄弟目标与兄弟目标认识认识 替换后目标集为替换后目标集为交往交往462、产生式
47、表示第十二次循环第十二次循环q取目标集的第一条目标取目标集的第一条目标交往交往,用动态数据库中的事实与之匹配,用动态数据库中的事实与之匹配,匹配不成功匹配不成功q用规则库中的规则后件与该目标匹配用规则库中的规则后件与该目标匹配R5: 已匹配过,舍弃已匹配过,舍弃R6: if 认识认识送花送花 then 交往交往匹配成功,将其前件替换父目标放入目标集,转步匹配成功,将其前件替换父目标放入目标集,转步3 送花,认识送花,认识 替换父目标替换父目标 交往交往第十三次循环第十三次循环设计邂逅,送花,有责任心,勤奋努力,明示,体贴容让,不百依设计邂逅,送花,有责任心,勤奋努力,明示,体贴容让,不百依百顺
48、百顺 q取目标集的第一条目标取目标集的第一条目标送花送花 , 用用动态数据库中的事实与之匹配,匹配成功,删除该目标,转用用动态数据库中的事实与之匹配,匹配成功,删除该目标,转步步2R5: if 认识认识一起自习一起自习 then 交往交往R6: if 认识认识送花送花 then 交往交往R7: if 认识认识约会约会 then 交往交往472、产生式表示、产生式表示第十四次循环第十四次循环q取目标集的第一条目标取目标集的第一条目标认识认识,用动态数据库中的事实,用动态数据库中的事实与之匹配,匹配不成功与之匹配,匹配不成功q用规则库中的规则后件与该目标匹配用规则库中的规则后件与该目标匹配R1:
49、if 请人介绍请人介绍 then 认识,认识, R2: if 参加聚会参加聚会 then 认识,认识,R3: if 搭讪搭讪 then 认识,认识, R4: if 设计邂逅设计邂逅 then 认识,认识,R1、R2、R3、R4都能匹配成功,逐一用前件替换都能匹配成功,逐一用前件替换认识认识,再与动态数据库中的事实匹配再与动态数据库中的事实匹配482、产生式表示、产生式表示第第 十七次循环十七次循环q取目标集的第一条目标取目标集的第一条目标设计邂逅设计邂逅 ,用动态数据库中,用动态数据库中的事实与之匹配,匹配成功,删除该目标,转步的事实与之匹配,匹配成功,删除该目标,转步2第第 十八次循环十八次
50、循环q目标集为空,推理成功目标集为空,推理成功反向推理的最终规则链为:反向推理的最终规则链为:R15R13 R8 R6 R4492、产生式表示、产生式表示n正向推理与反向推理的比较正向推理与反向推理的比较q推理方向推理方向n正向推理是从事实到结论的自底向上的推理正向推理是从事实到结论的自底向上的推理n反向推理是从目标到事实的自顶向下的推理反向推理是从目标到事实的自顶向下的推理q规则匹配以及匹配成功后的执行方式规则匹配以及匹配成功后的执行方式n正向推理是用事实匹配规则的前件,匹配成功则执行后件,将正向推理是用事实匹配规则的前件,匹配成功则执行后件,将后件的结论加入动态数据库后件的结论加入动态数据
51、库n反向推理是用目标匹配规则的后件,匹配成功则将规则前件作反向推理是用目标匹配规则的后件,匹配成功则将规则前件作为新的目标加入目标集,替换其父目标为新的目标加入目标集,替换其父目标q冲突消解冲突消解n正向推理需要进行冲突消解正向推理需要进行冲突消解n反向推理不需要冲突消解反向推理不需要冲突消解502、产生式表示、产生式表示q动态数据库动态数据库n正向推理不断向动态数据库中添加中间结果;正向推理不断向动态数据库中添加中间结果;n反向推理动态数据库内容不变反向推理动态数据库内容不变q目标集目标集n正向推理的目标集就是初始目标,且推理过程中目标集内容不正向推理的目标集就是初始目标,且推理过程中目标集
52、内容不变变n反向推理中不断用子目标替代父目标反向推理中不断用子目标替代父目标q终止条件终止条件n正向推理:动态数据库中的事实能够与目标匹配正向推理:动态数据库中的事实能够与目标匹配n反向推理:目标集中的所有目标都匹配成功,即目标集为空反向推理:目标集中的所有目标都匹配成功,即目标集为空512、产生式表示、产生式表示n双向推理双向推理q正向推理与反向推理同时使用,直到在某一中间结果重合正向推理与反向推理同时使用,直到在某一中间结果重合522、产生式表示、产生式表示n双向推理双向推理q进程进程1和进程和进程2分别执行正向推理和反向推理分别执行正向推理和反向推理q动态数据库动态数据库n进程进程1 正
53、向推理向动态数据库添加事实正向推理向动态数据库添加事实n进程进程2 反向推理使用动态数据库进行匹配反向推理使用动态数据库进行匹配q终止条件终止条件n进程进程2 中的目标集为空,则推理成功中的目标集为空,则推理成功532、产生式表示、产生式表示n产生式与蕴涵式的异同产生式与蕴涵式的异同q共同点共同点n都表示由条件推出结论都表示由条件推出结论q不同点不同点n蕴涵式是一个逻辑表达式,其逻辑值只有真和假,不能表蕴涵式是一个逻辑表达式,其逻辑值只有真和假,不能表达不确定的知识。谓词逻辑中蕴涵式的匹配必须是精确的。达不确定的知识。谓词逻辑中蕴涵式的匹配必须是精确的。n产生式表示的知识可以是不确定的,产生式
54、的匹配可以是产生式表示的知识可以是不确定的,产生式的匹配可以是不确定的不确定的542、产生式表示、产生式表示n产生式与条件语句的主要区别产生式与条件语句的主要区别 q前件结构不同前件结构不同 传统程序设计语言中条件语句的左部仅仅是一个布尔表达式传统程序设计语言中条件语句的左部仅仅是一个布尔表达式产生式的前件可以是一个复杂的结构产生式的前件可以是一个复杂的结构q控制流程不同控制流程不同 程序设计语言中条件一旦被激活,就严格地从一个前提向其程序设计语言中条件一旦被激活,就严格地从一个前提向其结论传递。结论传递。 产生式系统中满足前提条件的规则被激活后,不一定被立即产生式系统中满足前提条件的规则被激
55、活后,不一定被立即执行,能否执行将取决于推理机的冲突消解策略执行,能否执行将取决于推理机的冲突消解策略552、产生式表示、产生式表示n优点优点n自然性好,自然性好,“Ifthen”的形式与人类的判断性知识基本的形式与人类的判断性知识基本一致,便于推理一致,便于推理;n便于引入各种启发式知识便于引入各种启发式知识n格式固定,形式简单,规则间相互独立,便于统一处理,格式固定,形式简单,规则间相互独立,便于统一处理,模块性好。模块性好。n缺点缺点n推理效率低下推理效率低下 n难以表现规则间的关系,难以表现结构和层次关系难以表现规则间的关系,难以表现结构和层次关系56专家系统基础专家系统基础n专家系统
56、专家系统(Expert System,ES)(Expert System,ES)就是能像人类专家就是能像人类专家一样解决困难、复杂的实际问题的计算机系统。一样解决困难、复杂的实际问题的计算机系统。 n专家系统的四个要素专家系统的四个要素: (1) (1) 应用于某专门领域。应用于某专门领域。 (2) (2) 拥有专家级知识。拥有专家级知识。 (3) (3) 能模拟专家的思维和推理。能模拟专家的思维和推理。 (4) (4) 能达到专家级水平。能达到专家级水平。57专家系统基础专家系统基础n专家系统是靠知识和推理来解决问题专家系统是靠知识和推理来解决问题( (不像传统软不像传统软件系统使用固定的算
57、法来解决问题件系统使用固定的算法来解决问题), ), 所以所以, , 专家专家系统是基于知识的智能问题求解系统系统是基于知识的智能问题求解系统n专家系统则强调知识与推理的分离专家系统则强调知识与推理的分离, , 因而系统具因而系统具有很好的灵活性和可扩充性。有很好的灵活性和可扩充性。n专家系统一般具有解释功能专家系统一般具有解释功能, , 即在运行过程中一即在运行过程中一方面能回答用户提出的问题方面能回答用户提出的问题, ,另一方面还能对最后另一方面还能对最后的输出的输出( (结论结论) )或处理问题的过程作出解释或处理问题的过程作出解释n有些专家系统还具有有些专家系统还具有“学习学习”能力能
58、力, , 即不断对自即不断对自己的知识进行扩充、完善和提炼己的知识进行扩充、完善和提炼58专家系统基础专家系统基础n系统结构系统结构q知识库:知识库:q推理机:推理机:q动态数据库:动态数据库:q人机界面:人机界面:q解释模块:解释模块:q知识库管理模块:知识库管理模块:59第二次实验报告第二次实验报告n利用产生式规则构建一个简单的专家系统利用产生式规则构建一个简单的专家系统q题目自拟(手机选择、电脑选择、玉石选择题目自拟(手机选择、电脑选择、玉石选择 )q要求:要求:1、确定推理方法(正向还是反向),并根据问题设计实现一个简、确定推理方法(正向还是反向),并根据问题设计实现一个简单的不通用推理机(匹配、冲突消解)单的不通用推理机(匹配、冲突消解)2、规则库要求至少包含、规则库要求至少包含15条规则条规则3、初始事实可以任意给定,输入初始事实后能够得到推理结果、初始事实可以任意给定,输入初始事实后能够得到推理结果4、设计人机界面,解释模块提供查询规则的功能、设计人机界面,解释模块提供查询规则的功能5、可以不考虑知识库管理模块、可以不考虑知识库管理模块6、提交实验报告,实验名称为:、提交实验报告,实验名称为:基于回溯推理的小型专家系统基于回溯推理的小型专家系统7、报告中要有推理树、报告中要有推理树60