第6章-基于产生式规则的机器推理

第6章基于产生式规则的机器推理第6章基于产生式规则的机器推理6.1产生式规则6.2产生式系统习题六第6章基于产生式规则的机器推理6.1产生式规则6.1.1产生式(Production)一词,首先是由美国数学家波斯特(E.Post)提出来的。波斯特根据替换规则提出了一种称为波斯特机的计算模型,模型中的每一条规则当时被称为一个产生式。后来,这一术语几经修改扩充,被用到许多领域。例如,形式语言中的文法规则就称为产生式。产生式也称为产生式规则,或简称规则。第6章基于产生式规则的机器推理产生式的一般形式为〈前件〉→〈后件〉其中,前件就是前提,后件是结论或动作,前件和后件可以是由逻辑运算符AND、OR、NOT组成的表达式。产生式规则的语义是:如果前提满足,则可得结论或者执行相应的动作,即后件由前件来触发。所以,前件是规则的执行条件,后件是规则体。第6章基于产生式规则的机器推理例如,下面就是几个产生式规则：(1)如果银行存款利率下调,那么股票价格上涨。(2)如果炉温超过上限,则立即关闭风门。(3)如果键盘突然失灵,且屏幕上出现怪字符,则是病毒发作。(4)如果胶卷感光度为200,光线条件为晴天,目标距离不超过5米,则快门速度取250,光圈大小取f16。第6章基于产生式规则的机器推理可以看出,产生式与逻辑蕴含式非常相似。是的,逻辑蕴含式就是产生式,但它只是一种产生式。除逻辑蕴含式外,产生式还包括各种操作、规则、变换、算子、函数等等。比如上例中的(2)是一个产生式,但并不是一个逻辑蕴含式。概括来讲,产生式描述了事物之间的一种对应关系(包括因果关系和蕴含关系),其外延十分广泛。例如,图搜索中的状态转换规则和问题变换规则就都是产生式规则。另外还有程序设计语言的文法规则、逻辑中的逻辑蕴含式和等价式、数学中的微分和积分公式、化学中分子结构式的分解变换规则等等,也都是产生式规则；甚至体育比赛中的规则、国家的法律条文、单位的规章制度等等,也都可以表示成产生式规则。第6章基于产生式规则的机器推理6.1.2由产生式的涵义可知,利用产生式规则可以实现有前提条件的指令性操作,也可以实现逻辑推理。实现操作的方法是当测试到一条规则的前提条件满足时,就执行其后部的动作。这称为规则被触发或点燃。利用产生式规则实现逻辑推理的方法是当有事实能与某规则的前提匹配(即规则的前提成立)时,就得到该规则后部的结论(即结论也成立)。第6章基于产生式规则的机器推理实际上,这种基于产生式规则的逻辑推理模式,就是逻辑上所说的假言推理(对常量规则而言)和三段论推理(对变量规则而言),即：A→BAB这里的大前提就是一个产生式规则,小前提就是证据事实。其实,我们也可以把上面的有前提条件的操作和逻辑推理统称为推理。那么,上面的式子也就是基于产生式规则的一般推理模式。这就是说,产生式系统中的推理是更广义的推理。第6章基于产生式规则的机器推理6.2产生式系统6.2.1产生式系统由三部分组成：产生式规则库、推理机和动态数据库,其结构如图6－1所示。产生式规则库亦称产生式规则集,由领域规则组成,在机器中以某种动态数据结构进行组织。一个产生式规则集中的规则,按其逻辑关系,一般可形成一个称为推理网络的结构图。推理机亦称控制执行机构,它是一个程序模块,负责产生式规则的前提条件测试或匹配,规则的调度与选取,规则体的解释和执行。即推理机实施推理,并对推理进行控制,它也就是规则的解释程序。第6章基于产生式规则的机器推理图6-1产生式系统的结构第6章基于产生式规则的机器推理6.2.2产生式系统运行时,除了需要规则库以外,还需要有初始事实(或数据)和目标条件。目标条件是系统正常结束的条件,也是系统的求解目标。产生式系统启动后,推理机就开始推理,按所给的目标进行问题求解。推理机的一次推理过程可如图6-2所示。第6章基于产生式规则的机器推理图6-2推理机的一次推理过程第6章基于产生式规则的机器推理一个实际的产生式系统,其目标条件一般不会只经一步推理就可满足,往往要经过多步推理才能满足或者证明问题无解。所以,产生式系统的运行过程,就是推理机不断运用规则库中的规则,作用于动态数据库,不断进行推理并不断检测目标条件是否满足的过程。当推理到某一步,目标条件被满足,则推理成功,于是系统运行结束；或者再无规则可用,但目标条件仍未满足,则推理失败,当然系统也运行结束。第6章基于产生式规则的机器推理由上所述,产生式系统的运行过程也就是从初始事实出发,寻求到达目标条件的通路的过程。所以,产生式系统的运行过程也是一个搜索的过程。但一般把产生式系统的整个运行过程也称为推理。那么,一个产生式系统启动后,从哪儿开始推理？下面我们就回答这个问题。第6章基于产生式规则的机器推理6.2.3产生式系统的推理可分为正向推理和反向推理两种基本方式。简单来讲,正向推理就是从初始事实数据出发,正向使用规则进行推理(即用规则前提与动态数据库中的事实匹配,或用动态数据库中的数据测试规则的前提条件,然后产生结论或执行动作),朝目标方向前进；反向推理就是从目标出发,反向使用规则进行推理(即用规则结论与目标匹配,又产生新的目标,然后对新目标再作同样的处理),朝初始事实或数据方向前进。下面我们给出产生式系统正向推理和反向推理的常用算法：第6章基于产生式规则的机器推理1.正向推理算法一：步1将初始事实/数据置入动态数据库。步2用动态数据库中的事实/数据,匹配/测试目标条件,若目标条件满足,则推理成功,结束。步3用规则库中各规则的前提匹配动态数据库中的事实/数据,将匹配成功的规则组成待用规则集。步4若待用规则集为空,则运行失败,退出。步5将待用规则集中各规则的结论加入动态数据库,或者执行其动作,转步2。第6章基于产生式规则的机器推理可以看出,随着推理的进行,动态数据库的内容或者状态在不断变化。如果我们把动态数据库的每一个状态作为一个节点的话,则上述推理过程也就是一个从初始状态(初始事实/数据)到目标状态(目标条件)的状态图搜索过程。如果我们把动态数据库中每一个事实/数据作为一个节点的话,则上述推理过程就是一个“反向”(即自底向上)与或树搜索过程。第6章基于产生式规则的机器推理图6-3正向推理的动态数据库第6章基于产生式规则的机器推理例6.1动物分类问题的产生式系统描述及其求解。设由下列动物识别规则组成一个规则库,推理机采用上述正向推理算法,建立一个产生式系统。该产生式系统就是一个小型动物分类知识库系统。规则集：r1：若某动物有奶,则它是哺乳动物。r2：若某动物有毛发,则它是哺乳动物。r3：若某动物有羽毛,则它是鸟。r4：若某动物会飞且生蛋,则它是鸟。第6章基于产生式规则的机器推理r5：若某动物是哺乳动物且有爪且有犬齿且目盯前方,则它是食肉动物。r6：若某动物是哺乳动物且吃肉,则它是食肉动物。r7：若某动物是哺乳动物且有蹄,则它是有蹄动物。r8：若某动物是有蹄动物且反刍食物,则它是偶蹄动物。r9：若某动物是食肉动物且黄褐色且有黑色条纹,则它是老虎。r10：若某动物是食肉动物且黄褐色且有黑色斑点,则它是金钱豹。第6章基于产生式规则的机器推理r11：若某动物是有蹄动物且长腿且长脖子且黄褐色且有暗斑点,则它是长颈鹿。r12：若某动物是有蹄动物且白色且有黑色条纹,则它是斑马。r13：若某动物是鸟且不会飞且长腿且长脖子且黑白色,则它是驼鸟。r14：若某动物是鸟且不会飞且会游泳且黑白色,则它是企鹅。r15：若某动物是鸟且善飞且不怕风浪,则它是海燕。第6章基于产生式规则的机器推理图6-4规则集形成的部分推理网络第6章基于产生式规则的机器推理再给出初始事实：f1f2f3f4：有黑色条纹。目标条件为：易见,该系统的运行结果为：该动物是老虎。其推理树如图6-5所示。第6章基于产生式规则的机器推理图6-5关于“老虎”的正向推理树第6章基于产生式规则的机器推理2.步1将初始事实/数据置入动态数据库,将目标条件置入目标链。步2若目标链为空,则推理成功,结束。步3取出目标链中第一个目标,用动态数据库中的事实/数据同其匹配,若匹配成功,转步2。第6章基于产生式规则的机器推理步4用规则集中的各规则的结论同该目标匹配,若匹配成功,则将第一个匹配成功且未用过的规则的前提作为新的目标,并取代原来的父目标而加入目标链,转步3。步5若该目标是初始目标,则推理失败,退出。步6将该目标的父目标移回目标链,取代该目标及其兄弟目标,转步3第6章基于产生式规则的机器推理例6.2对于例6.1中的产生式系统,改为反向推理算法,则得到图6-6所示的推理树。图6-6关于“老虎”的反向推理树第6章基于产生式规则的机器推理可以看出,与正向推理不同,这次的推理树是从上而下扩展而成的,而且推理过程中还发生过回溯。反向推理也称为后向推理、反向链、目标驱动的推理等。从上面的两个算法可以看出,正向推理是自底向上的综合过程,而反向推理则是自顶向下的分析过程。除了正向推理和反向推理外,产生式系统还可进行双向推理。双向推理就是同时从初始数据和目标条件出发进行推理,如果在中间某处相遇,则推理搜索成功。第6章基于产生式规则的机器推理3.上述正向推理算法中,对所有匹配成功的规则都同时触发启用。所以,它实现的搜索是穷举式的树式盲目搜索。下面我们给出一个正向推理的启发式线式搜索算法。正向推理算法二：步1将初始事实/数据置入动态数据库。步2用动态数据库中的事实/数据,匹配/测试目标条件,若目标条件满足,则推理成功,结束。第6章基于产生式规则的机器推理步3用规则库中各规则的前提匹配动态数据库中的事实/数据,将匹配成功的规则组成待用规则集。步4若待用规则集为空,则运行失败,退出。步5用某种策略,从待用规则集中选取一条规则,将其结论加入动态数据库,或者执行其动作,撤消待用规则集,转步2。第6章基于产生式规则的机器推理可以看出,该算法与前面的算法仅在步5有所差别。但它已是不可回溯的线式搜索了。该算法的启发性表现在“用某种策略,从待用规则集中选取一条规则”。这种选取策略,也称为“冲突消解”策略。因为这时可用规则集中的规则都可触发执行,但只取其中之一,因而就产生了冲突或竞争。所以,冲突消解策略对正向推理有重要意义。常用的冲突消解策略有：优先级法(优先级高者优先)、可信度法(可信度高者优先)、代价法(代价低者优先)及自然顺序法等。当然,要使用优先级法、可信度法、代价法等策略时,须事先给规则设定相关的参数,即优先级、可信度、代价等。第6章基于产生式规则的机器推理可以看出,上述的两个推理算法的“启发”性就体现在冲突消解策略中。如果再采用优先级、可信度、代价等冲突消解策略,则就是启发式搜索；但如果采用自然顺序法,则就是一种盲目碰撞搜索。产生式系统的推理方式、搜索策略及冲突消解策略等,一般统称为推理控制策略,或简称控制策略。一个产生式系统的控制策略就体现在推理机的算法描述中。第6章基于产生式规则的机器推理6.2.41.上面我们对产生式的讨论,只是用自然语言进行描述并仅在概念层次上进行阐述,而并未涉及它的具体结构和程序语言实现问题。现在讨论产生式规则的程序语言实现问题。首先,讨论产生式规则的结构问题。一般来讲,产生式规则的前提和结论部分可以是一个复杂的逻辑表达式,但为了使表达简单规范,且便于推理,在实践中人们往往把规则的前提部分作成形如条件1AND条件2AND…AND条件n第6章基于产生式规则的机器推理条件1OR条件2OR…OR条件m的形式(其中的条件可以带否定词)；把规则结论部分作成形如断言1/动作1AND断言2/动作2AND…AND断言k/动作k断言1/动作1OR断言2/动作2OR…OR断言k/动作k的形式,断言/即仅有一项的形式。第6章基于产生式规则的机器推理由于含OR关系的规则也可以分解为几个不含OR关系的规则,所以,产生式规则也可仅取下面的一种形式：条件1AND条件2AND…AND条件n→断言/动作即前件是若干与关系的条件,后件仅有一个断言或动作。第6章基于产生式规则的机器推理对规则作进一步细化。其条件、断言和动作都应该是陈述句。所以,它们可以用n元谓词(或子句)形式表示,