产生式法知识表示与问题求解ppt课件.ppt

1,智能控制技术,上海大学机电工程与自动化学院杜鑫,2,2.2 知识的表示,知识表示法,2.2.1 一阶谓词知识表示法,2.2.2 产生式知识表示法,3,产生式表示法又称为产生式规则表示法。有心理学家认为，人脑对知识的存储就是产生式形式。,产生式最早由P.Post于1943年提出，用于构造Post机计算模型；1972 A.Newell和H.A.Simon在研究人类的认识模型中提出了 Rule-Based 产生式系统方法以及规则表示模式。,目前，产生式表示法已经成为人工智能中应用最多的一种知识表示法，许多成功的专家系统都用它来表示知识。,2.2.2 产生式知识表示法,4,2.2.2 产生式知识表示法,2.2.2.1 产生式表示知识的基本方法,2.2.2.2 产生式系统的组成,2.2.2.3 产生式系统的推理方式,2.2.2.4 产生式系统应用举例,2.2.2.5 产生式表示法的特点,5,2.2.2 产生式知识表示法,2.2.2.1 产生式表示知识的基本方法,事实的表示规则的表示产生式与蕴含式的区别产生式与条件语句的区别,6,2.2.2 产生式知识表示法,2.2.2.1 产生式表示知识的基本方法,事实的表示-事实的定义,事实是断言一个语言变量的值或断言多个语言变量之间关系的陈述句,“雪是白的” 其中“雪”是语言变量，“白的”是语言变量的值,“王峰热爱祖国”“王峰”和“祖国”是语言变量, “热爱”是语言变量之间的关系,例如：,语言变量的值或语言变量之间的关系可以是数字、词等,7,确定性事实知识的表示。一般使用三元组表示： （对象，属性，值）， 或者 （关系，对象1，对象2）,例如：事实“老李年龄是45岁。”可以表示为： (Li，Age，45) 事实“老李、老张是朋友。”可以表示为： (Friend，Li，Zhang),2.2.2 产生式知识表示法,2.2.2.1 产生式表示知识的基本方法,事实的表示-事实的表示,8,不确定性事实知识的表示。一般使用四元组表示： （对象，属性，值，可信度） 或者 （关系，对象1，对象2，可信度）,例如：事实“老李年龄很可能是45岁。”可以表示为： (Li，Age，45，0.8) 事实“老李、老张不大可能是朋友。”可以表示为： (Friend，Li，Zhang，0.1),2.2.2 产生式知识表示法,2.2.2.1 产生式表示知识的基本方法,事实的表示-事实的表示,9,2.2.2 产生式知识表示法,2.2.2.1 产生式表示知识的基本方法,规则的表示,P是产生式的前提，也称为前件，它给出了该产生式可否使用的先决条件，由事实的逻辑组合来构成；,-描述事物之间的因果关系-规则的产生式表示形式常称为产生式规则,规则的作用,产生式规则的基本形式,PQ 或者 IF P THEN Q,Q是一组结论或操作，也称为产生式的后件，它指出当前题P满足时，应该推出的结论或应该执行的动作,10,2.2.2 产生式知识表示法,2.2.2.1 产生式表示知识的基本方法,规则的表示,产生式的含义 如果前提P满足，则可推出结论Q或执行Q所规定的操作产生式规则的例子 r6: IF 动物有犬齿 AND 有爪 AND 眼盯前方 THEN 该动物是食肉动物 其中，r6是该产生式的编号；“动物有犬齿 AND 有爪 AND 眼盯前方”是产生式的前提P；“该动物是食肉动物”是产生式的结论Q。,11,2.2.2 产生式知识表示法,2.2.2.1 产生式表示知识的基本方法,与蕴涵式的主要区别,12,2.2.2 产生式知识表示法,2.2.2.1 产生式表示知识的基本方法,与蕴涵式的主要区别,例如，在专家系统MYCIN中有如下产生式： IF 本生物的染色斑是革兰氏阴性， 本微生物的形状呈杆状， 病人是中间宿主 THEN 该微生物是绿脓杆菌，置信度为0.6,这在谓词中的逻辑蕴含式是不能表示的！,它表示，当前题中列出的各个条件都满足时，结论“该微生物是绿脓杆菌” 可以相信的程度是0.6。,13,2.2.2 产生式知识表示法,2.2.2.1 产生式表示知识的基本方法,与(计算机程序语言)条件语句的主要区别,14,2.2.2 产生式知识表示法,2.2.2.2 产生式系统的组成,把一组产生式放在一起，让它们互相配合，协同作用， 一个产生式的结论可以供给另个产生式作为前提使用，以这种方式求得问题的解决，这样的系统称为产生式系统,15,2.2.2 产生式知识表示法,2.2.2.2 产生式系统的组成,综合数据库DB(Data Base),推理过程中，当规则库中某条规则的前提可以和综合数据库的已知事实匹配时，该规则被激活,输入的事实,中间结论,最终结论,问题的初始状态,用于推理过程的规则匹配,存放求解问题的各种当前信息,16,2.2.2 产生式知识表示法,2.2.2.2 产生式系统的组成,规则库RB(Rule Base),也称知识库KB(Knowledge Base) ,用于存放与求解问题有关的所有规则的集合,作用：是产生式系统问题求解的基础,要求：知识的完整性、一致性、准确性、灵活性和知识组织的合理性,17,2.2.2 产生式知识表示法,2.2.2.2 产生式系统的组成,推理机(Inference Engine),选择匹配,冲突消解,执行操作,终止推理,路径解释,18,正向推理,2.2.2 产生式知识表示法,2.2.2.3 产生式系统的推理策略,也称为数据驱动方式，它是从初始状态出发，朝着目标状态前进，正向使用规则的一种推理方法。,所谓正向使用规则，是指以问题的初始状态作为初始综合数据库，仅当综合数据库中的事实满足某条规则的前提时，该规则才被使用,优点是简单明了且能求出所有解缺点是执行效率较低，原因是它驱动了一些与问题无关的规则，具有一定的盲目性。,19,推理机的一次正向推理过程,2.2.2 产生式知识表示法,2.2.2.3 产生式系统的推理策略,正向推理,20,优点是不寻找无用数据，不使用与问题无关的规则。因此，对那些目标明确的问题，使用反向推理方式是一种最佳选择。,2.2.2 产生式知识表示法,2.2.2.3 产生式系统的推理策略,也称为目标驱动方式，它是从目标（作为假设）状态出发，朝着初始状态前进，反向使用规则的一种推理方法。,所谓逆向使用规则，是指以问题的目标状态作为初始综合数据库，仅当综合数据库中的事实满足某条规则的后件时，该规则才被使用。,反向推理,21,例-动物识别系统,这是一个用以识别虎、金钱豹、斑马、长颈鹿、企鹅、驼鸟、信天翁等7种动物的产生式系统。为了实现对这些动物的识别，该系统建立了如下规则库：,R1: IF 该动物有毛 THEN 该动物是哺乳动物R2: IF 该动物有奶 THEN 该动物是哺乳动物R3: IF 该动物有羽毛 THEN 该动物是鸟R4: IF 该动物会飞 AND会下蛋 THEN 该动物是鸟R5: IF 该动物吃肉 THEN 该动物是食肉动物R6: IF 该动物有犬齿 AND有爪AND 眼盯前方 THEN 该动物食肉动物,2.2.2 产生式知识表示法,2.2.2.4 产生式系统的应用举例,22,R7: IF 该动物是哺乳动物 AND有蹄 THEN 该动物是有蹄类动物R8: IF 该动物是哺乳动物 AND 是嚼反刍动物 THEN 该动物是动物有蹄类动物R9: IF 该动物是哺乳动物 AND 是食肉动物 AND 是黄褐色 AND 身上有暗斑点 THEN 该动物是金钱豹,2.2.2 产生式知识表示法,例-动物识别系统,2.2.2.4 产生式系统的应用举例,例-动物识别系统,这是一个用以识别虎、金钱豹、斑马、长颈鹿、企鹅、驼鸟、信天翁等7种动物的产生式系统。为了实现对这些动物的识别，该系统建立了如下规则库：,23,R10: IF 该动物是哺乳动物 AND 是食肉动物 AND 是黄褐色 AND 身上有黑色条纹 THEN 该动物是虎R11: IF 该动物是有蹄类动物 AND 有长脖子 AND 有长腿 AND 身上有暗斑点 THEN 该动物是长颈鹿,2.2.2 产生式知识表示法,例-动物识别系统,2.2.2.4 产生式系统的应用举例,这是一个用以识别虎、金钱豹、斑马、长颈鹿、企鹅、驼鸟、信天翁等7种动物的产生式系统。为了实现对这些动物的识别，该系统建立了如下规则库：,24,R12: IF 该动物是有蹄类动物 AND 身上有黑色条纹 THEN 该动物是斑马R13: IF 该动物是鸟 AND 有长脖子 AND 有长腿 AND 不会飞 AND 有黑白二色 THEN 该动物是驼鸟,2.2.2 产生式知识表示法,2.2.2.4 产生式系统的应用举例,例-动物识别系统,这是一个用以识别虎、金钱豹、斑马、长颈鹿、企鹅、驼鸟、信天翁等7种动物的产生式系统。为了实现对这些动物的识别，该系统建立了如下规则库：,25,2.2.2 产生式知识表示法,2.2.2.4 产生式系统的应用举例,例-动物识别系统,这是一个用以识别虎、金钱豹、斑马、长颈鹿、企鹅、驼鸟、信天翁等7种动物的产生式系统。为了实现对这些动物的识别，该系统建立了如下规则库：,R14: IF 该动物是鸟 AND 会游泳 AND 不会飞 AND 有黑白二色 THEN 该动物是企鹅R15: IF 该动物是鸟 AND 善飞 THEN 该动物是信天翁,26,2.2.2 产生式知识表示法,2.2.2.4 产生式系统的应用举例,例-动物识别系统,这是一个用以识别虎、金钱豹、斑马、长颈鹿、企鹅、驼鸟、信天翁等7种动物的产生式系统。为了实现对这些动物的识别，该系统建立了如下规则库：,说明：上述规则仅是一种直接表示方式，用三元组表示R15如下： R15：IF（动物，类别，鸟）AND（动物，本领，善飞） THEN（动物，名称，信天翁）,27,2.2.2 产生式知识表示法,2.2.2.4 产生式系统的应用举例,例-动物识别系统,这是一个用以识别虎、金钱豹、斑马、长颈鹿、企鹅、驼鸟、信天翁等7种动物的产生式系统。为了实现对这些动物的识别，该系统建立了如下规则库：,该系统是用来识别7种动物的,但它并没有简单地设计7条规则,而是设计了15条.,28,2.2.2 产生式知识表示法,2.2.2.4 产生式系统的应用举例,例-动物识别系统,这是一个用以识别虎、金钱豹、斑马、长颈鹿、企鹅、驼鸟、信天翁等7种动物的产生式系统。为了实现对这些动物的识别，该系统建立了如下规则库：,当已知的事实不完全时,虽不能推出最终结论,但可以得到分类结果,当需要增加对其它动物(如牛马等)的识别时,规则中只需增加关于这些动物个性方面的知识,如R9-R15那样,而对R1-R10可直接利用,这样增加的规则就不会太多,29,2.2.2 产生式知识表示法,2.2.2.4 产生式系统的应用举例,例-动物识别系统,这是一个用以识别虎、金钱豹、斑马、长颈鹿、企鹅、驼鸟、信天翁等7种动物的产生式系统。为了实现对这些动物的识别，该系统建立了如下规则库：,现给定初始条件，即初始综合数据库包含有如下事实： 该动物有暗斑点，有长脖子，有长腿，有奶，有蹄 求该动物是那种动物？,30,2.2.2.4 产生式系统的应用举例,例-动物识别系统,长颈鹿,斑马,长脖子,长腿,暗斑点,有蹄类,黑条纹,有蹄,哺乳动物,嚼反刍动物,有毛,r2,r7,r8,r11,r12,有奶,r1,动物识别的推理网络图(部分),2.2.2 产生式知识表示法,31,例-动物识别系统,图中最上层的结点称为“假设”或“结论”中间结点称为“中间假设”；终结点（叶结点）称为“证据”或“事实”每个“结论”都是本问题的一个目标，所有“假设”构成了本问题的目标集合,2.2.2 产生式知识表示法,2.2.2.4 产生式系统的应用举例,32,例-动物识别系统,推理机的工作过程详解,2.2.2 产生式知识表示法,2.2.2.4 产生式系统的应用举例,(1) 先从规则库中取出第一条规则r1，检查其前提是否可与综合数据库中的已知事实相匹配。r1的前提是“有毛发”，但事实库中无此事实，故匹配失败。然后取r2，该前提可与已知事实“有奶”相匹配，r2被执行，并将其结论“该动物是哺乳动物”作为新的事实加入到综合数据库中。此时，综合数据库的内容变为： 动物有暗斑，有长脖子，有长腿，有奶，有蹄，是哺乳动物,33,例-动物识别系统,推理机的工作过程详解,2.2.2 产生式知识表示法,2.2.2.4 产生式系统的应用举例,(2) 再从规则库中取r3，r4，r5，r6进行匹配，均失败。接着取r7，该前提与已知事实“是哺乳动物”相匹配，r7被执行，并将其结论“该动物是有蹄类动物” 作为新的事实加入到综合数据库中。此时，综合数据库的内容变为： 动物有暗斑，有长脖子，有长腿，有奶，有蹄，是哺乳动物，是有蹄类动物,34,例-动物识别系统,推理机的工作过程详解,2.2.2 产生式知识表示法,2.2.2.4 产生式系统的应用举例,(3) 此后，r8，r9，r10均匹配失败。接着取r11，该前提 “该动物是有蹄类动物 AND 有长脖子 AND 有长腿 AND 身上有暗斑” 与已知事实相匹配，r11被执行，并推出“该动物是长颈鹿”。 由于“长颈鹿”已是目标集合中的一个结论，即已推出最终结果，故问题求解过程结束。,35,现改变初始条件，即初始综合数据库包含有如下事实： f1：某动物有毛发。 f2：吃肉。 f3：黄褐色。 f4：有黑色条纹。求通过产生式系统得到的目标结果，即该动物是什么？ 该系统的运行结果为：该动物是老虎,例题-动物识别系统,2.2.2 产生式知识表示法,2.2.2.4 产生式系统的应用举例,36,动物分类-推出老虎的正向推理树,食肉动物,哺乳动物,有毛发,吃肉,黄褐色,有黑色条纹,老虎,例-动物识别系统,2.2.2 产生式知识表示法,2.2.2.4 产生式系统的应用举例,37,动物分类-推出老虎的反向推理树,2.2.2 产生式知识表示法,例-动物识别系统,2.2.2.4 产生式系统的应用举例,38,2.2.2 产生式知识表示法,2.2.2.5 产生式表示法的特点（优点）,清晰性：格式固定、形式简单。,模块性： 知识单元（规则）独立，知识库与推理机分离，知识库维护方便。,自然性：表达因果关系自然，符合思维习惯。,表示能力强：不仅能表示确定性知识，而且能表示不确定性知识,产生式表示法已经成为人工智能中应用最多的一种知识表示法，许多成功的专家系统都用它来表示知识。,39,基于产生式规则的二维不规则零件的排料算法 徐彦欣 - 小型微型计算机系统, 1998 - ,一个基于产生式系统的花稿轮廓识别方法 汪向前， 朱桂林 - 计算机辅助设计与图形学学报,一种基于产生式规则的造林专家系统的设计与实现 丁全龙， 吴保国 - 农业网络信息, 2006 - ,基于产生式规则轧制力传感器故障诊断系统 葛芦生， 龚幼民 - 工业仪表与自动化装置, 2001 - ,扩展产生式规则的网络故障诊断专家系统 刘培奇， 李增智， 赵银亮 - 西安交通大学学报, 2004 - ,2.2.2 产生式知识表示法,2.2.2.5 产生式表示法的特点,40,2.2.2 产生式知识表示法,2.2.2.5 产生式表示法的特点,R,传感器,对象,知识库(KB),控制规则集(CRS),特征识别与信息处理(FR&IP),推理机构(IE),S,I,U,K,Y,G,U,e,专家控制器(EC),KB存放工业过程控制的领域知识，DB和LA组成 CRS是对受控过程的各种控制模式和经验的归纳和总结 FRIP实现对信息的提取与加工，为决策和学习提供依据,工业专家控制器,41,2.2.2 产生式知识表示法,2.2.2.5 产生式表示法的特点（缺点）,效率较低：各规则之间的联系必须以综合数据库为媒介。并且，其求解过程是一种反复进行的“匹配冲突消解执行”过程。这样的执行方式将导致执行的低效率。,不便于表示结构性知识：由于产生式表示中的知识具有一致格式，且规则之间不能相互调用，因此那种具有结构关系或层次关系的知识则很难以自然的方式来表示。,42,一个老农携带一只狼、一头羊羔和一筐白菜，要从南岸过河到北岸。岸边有一条小船，只有老农自己能划船，而且除了老农以外，每次只能再带一样东西过河。在整个渡河过程中，无论什么情况，若老农不在场时，则不允许狼和羊羔单独相处，否则羊羔会遭殃；羊羔也不得与白菜放在一起，否则羊羔会吃白菜。请问，老农如何才能把它们全部安全摆渡到北岸？,2.2.2 产生式知识表示法,思考题-用产生式表示“农夫过河”,43,0表示南岸 1表示北岸初态（0，0，0，0）目态（1，1，1，1）F（famer，wolf，sheep，cabbage）if(0,0,0,0) then(1,0,1,0)if(1,0,1,0) then(0,0,1,0)if(0,0,1,0) then(1,0,1,1)if(1,0,1,1) then(0,0,0,1)if(0,0,0,1) then(1,1,0,1)if(1,1,0,1) then(1,1,1,1),思考题-用产生式表示“农夫过河”,2.2.2 产生式知识表示法,