2.3产生式法知识表示与问题求解

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,自动化系仪自教研室,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,是产生式的前提，,也称为前件，它给出了该产生式可否使用的先决条件，由事实的逻辑组合来构成；,-,描述事物之间的,因果,关系,-,规则的产生式表示形式常称为产生式规则,规则的作用,产生式规则的基本形式,P,Q,或者,IF P THEN Q,Q,是一组结论或操作，,也称为产生式的后件，它指出当前题,P,满足时，应该推出的结论或应该执行的动作,10,2.2.2,产生式知识表示法,2.2.2.1,产生式表示知识的,基本方法,规则,的表示,产生式的含义,如果前提,P,满足，则可推出结论,Q,或执行,Q,所规定的操作,产生式规则的例子,r,6,: IF,动物有犬齿,AND,有爪,AND,眼盯前方,THEN,该动物是食肉动物,其中，,r,6,是该产生式的编号；“动物有犬齿,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,推理机的一次正向推理过程,从规则库中取一个条规则，将其前提同当前,动态数据库中的事实,/,数据进行模式匹配,匹配成功否,把该规则的结论放入当前动态数据库：或执,行规则所规定的动作,N,Y,2.2.2,产生式知识表示法,2.2.2.3,产生式系统的,推理策略,正向推理,20,优点是不寻找无用数据，不使用与问题无关的规则。因此，,对那些目标明确的问题，使用反向推理方式是一种最佳选择。,2.2.2,产生式知识表示法,2.2.2.3,产生式系统的,推理策略,也称为目标驱动方式，,它是从目标（作为假设）状态出发,，朝着初始状态前进，反向使用规则的一种推理方法。,所谓逆向使用规则，是指以问题的目标状态作为初始综合数据库，仅当综合数据库中的事实满足某条规则的后件时，该规则才被使用。,反向推理,21,例,-,动物识别系统,这是一个用以识别虎、金钱豹、斑马、长颈鹿、企鹅、驼鸟、信天翁等7种动,物的产生式系统。为了实现对这些动物的识别，该系统建立了如下规则库：,R,1,: IF,该动物有毛,THEN,该动物是哺乳动物,R,2,: IF,该动物有奶,THEN,该动物是哺乳动物,R,3,: IF,该动物有羽毛,THEN,该动物是鸟,R,4,: IF,该动物会飞,AND,会下蛋,THEN,该动物是鸟,R,5,: IF,该动物吃肉,THEN,该动物是食肉动物,R,6,: IF,该动物有犬齿,AND,有爪,AND,眼盯前方,THEN,该动物食肉动物,2.2.2,产生式知识表示法,2.2.2.4,产生式系统的,应用举例,22,R,7,: IF,该动物是哺乳动物,AND,有蹄,THEN,该动物是有蹄类动物,R,8,: IF,该动物是哺乳动物,AND,是嚼反刍动物,THEN,该动物是动物有蹄类动物,R,9,: IF,该动物是哺乳动物,AND,是食肉动物,AND,是黄褐色,AND,身上有暗斑点,THEN,该动物是金钱豹,2.2.2,产生式知识表示法,例,-,动物识别系统,2.2.2.4,产生式系统的,应用举例,例,-,动物识别系统,这是一个用以识别虎、金钱豹、斑马、长颈鹿、企鹅、驼鸟、信天翁等7种动,物的产生式系统。为了实现对这些动物的识别，该系统建立了如下规则库：,23,R,10,: IF,该动物是哺乳动物,AND,是食肉动物,AND,是黄褐色,AND,身上有黑色条纹,THEN,该动物是虎,R,11,: IF,该动物是有蹄类动物,AND,有长脖子,AND,有长腿,AND,身上有暗斑点,THEN,该动物是长颈鹿,2.2.2,产生式知识表示法,例,-,动物识别系统,2.2.2.4,产生式系统的,应用举例,这是一个用以识别虎、金钱豹、斑马、长颈鹿、企鹅、驼鸟、信天翁等7种动,物的产生式系统。为了实现对这些动物的识别，该系统建立了如下规则库：,24,R,12,: IF,该动物是有蹄类动物,AND,身上有黑色条纹,THEN,该动物是斑马,R,13,: IF,该动物是鸟,AND,有长脖子,AND,有长腿,AND,不会飞,AND,有黑白二色,THEN,该动物是驼鸟,2.2.2,产生式知识表示法,2.2.2.4,产生式系统的,应用举例,例,-,动物识别系统,这是一个用以识别虎、金钱豹、斑马、长颈鹿、企鹅、驼鸟、信天翁等7种动,物的产生式系统。为了实现对这些动物的识别，该系统建立了如下规则库：,25,2.2.2,产生式知识表示法,2.2.2.4,产生式系统的,应用举例,例,-,动物识别系统,这是一个用以识别虎、金钱豹、斑马、长颈鹿、企鹅、驼鸟、信天翁等7种动,物的产生式系统。为了实现对这些动物的识别，该系统建立了如下规则库：,R,14,: IF,该动物是鸟,AND,会游泳,AND,不会飞,AND,有黑白二色,THEN,该动物是,企鹅,R,15,: 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种动,物的产生式系统。为了实现对这些动物的识别，该系统建立了如下规则库：,当已知的事实不完全时,虽不能推出最终结论,但可以得到分类结果,当需要增加对其它动物(如牛马等)的识别时,规则中只需增加关于这些动物个性方面的知识,如,R,9,-R,15,那样,而对,R,1,-R,10,可直接利用,这样增加的规则就不会太多,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,产生式知识表示法,