1、第6章 基于产生式规则的机器推理 6.1 6.1 产生式规则产生式规则 6.2 6.2 产生式系统产生式系统6.36.3 产生式系统与图搜索问题求解产生式系统与图搜索问题求解 6.1 产生式规则6.1.1 产生式规则与推理网络产生式规则的一般形式为IF前件THEN后件或者更形式化地表示为 前件 后件 产生式规则的语义是：如果前提成立或条件满足，则可得结论或者执行相应的动作，即后件由前件来触发。所以,前件是规则的执行条件,后件是规则体。例：例：(1)如果银行存款利率下调,那么股票价格上涨。(2)如果炉温超过上限,则立即关闭风门。(3)如果键盘突然失灵,且屏幕上出现怪字符,则是病毒发作。(4)如果
2、胶卷感光度为200,光线条件为晴天,目标距离不超过5米,则快门速度取250,光圈大小取f16。(1)being-cut(利率)be-rising(股价)或者(1”)（利率）下调（股价）上涨(4)IF x1=200ANDx2=“晴天”ANDx35，THENy1=250ANDy2=f16或者(4”)x1=200 x2=“晴天”x35y1=250y2=f16 推理网络推理网络A1A2A3B1A4A5B2B1CB2CB1B2DB3D6.1.2基于产生式规则的推理模式ABA B这里的大前提就是一个产生式规则,小前提就是证据事实。其实,我们也可以把上面的有前提条件的操作和逻辑推理统称为推理。那么,上面的式
3、子也就是基于产生式规则的一般推理模式。这就是说,产生式系统中的推理是更广义的推理。6.2 产生式系统 6.2.1系统结构产生式系统由三部分组成：产生式规则库、推理机和动态数据库,其结构如图6-2所示。6.2.2运行过程 产生式系统运行时,除了需要规则库以外,还需要有初始事实(或数据)和目标条件。目标条件是系统正常结束的条件,也是系统的求解目标。产生式系统启动后,推理机就开始推理,按所给的目标进行问题求解。推理机的一次推理过程可如图 6-3所示。图 6-3 推理机的一次推理过程6.2.3控制策略与常用算法 产生式系统的推理可分为正向推理和反向推理两种基本方式。简单来讲,正向推理就是从初始事实数据
4、出发,正向使用规则进行推理(即用规则前提与动态数据库中的事实匹配,或用动态数据库中的数据测试规则的前提条件,然后产生结论或执行动作),朝目标方向前进；反向推理就是从目标出发,反向使用规则进行推理(即用规则结论与目标匹配,又产生新的目标,然后对新目标再作同样的处理),朝初始事实或数据方向前进。下面我们给出产生式系统正向推理和反向推理的常用算法：1.1.正向推理正向推理 正向推理算法一：(1)将初始事实/数据置入动态数据库。(2)用动态数据库中的事实/数据,匹配/测试目标条件,若目标条件满足,则推理成功,结束。(3)用规则库中各规则的前提匹配动态数据库中的事实/数据,将匹配成功的规则组成待用规则集
5、。(4)若待用规则集为空,则运行失败,退出。(5)将待用规则集中各规则的结论加入动态数据库,或者执行其动作,转步(2)。例例6-1动物分类问题的产生式系统描述及其求解。设由下列动物识别规则组成一个规则库,推理机采用上述正向推理算法,建立一个产生式系统。该产生式系统就是一个小型动物分类知识库系统。规则集：r1：若某动物有奶,则它是哺乳动物。r2：若某动物有毛发,则它是哺乳动物。r3：若某动物有羽毛且生蛋,则它是鸟。r4：若某动物是哺乳动物且有爪且有犬齿且目盯前方,则它是食肉动物。r5：若某动物是哺乳动物且吃肉,则它是食肉动物。r6：若某动物是哺乳动物且有蹄,则它是有蹄动物。r7：若某动物是有蹄动
6、物且反刍食物,则它是偶蹄动物。r8：若某动物是食肉动物且黄褐色且有黑色条纹,则它是老虎。r9：若某动物是食肉动物且黄褐色且有黑色斑点,则它是金钱豹。r10：若某动物是有蹄动物且长腿且长脖子且黄褐色且有暗斑点,则它是长颈鹿。r11：若某动物是有蹄动物且白色且有黑色条纹,则它是斑马。r12：若某动物是鸟且不会飞且长腿且长脖子且黑白色,则它是驼鸟。r13：若某动物是鸟且不会飞且会游泳且黑白色,则它是企鹅。r14：若某动物是鸟且善飞且不怕风浪,则它是海燕。再给出初始事实：f1：某动物有毛发。f2：吃肉。f3：黄褐色。f4：有黑色条纹。目标条件为：该动物是什么？易见,该系统的运行结果为：该动物是老虎。其
7、推理树如图6-5所示。图6-5关于“老虎”的正向推理树2.2.反向推理反向推理反向推理算法：(1)将初始事实/数据置入动态数据库，将目标条件置入目标链。(2)若目标链为空，则推理成功，结束。(3)取出目标链中第一个目标，用动态数据库中的事实/数据同其匹配，若匹配成功，转步(2)。(4)用规则集中的各规则的结论同该目标匹配，将第一个匹配成功且未用过的规则的前提作为新的目标，并取代原来的父目标而加入目标链，转步(3)。(5)若该目标是初始目标，则推理失败，退出。(6)将该目标的父目标移回目标链，取代该目标及其兄弟目标，转步(3)。例 6-2对于例6-1中的产生式系统,改为反向推理算法,则得到图6-
8、6所示的推理树。图6-6关于“老虎”的反向推理树3.冲突消解策略推理时规则的选取策略称为“冲突消解”策略。常用的冲突消解策略有：优先级法（优先级高者优先）、可信度法（可信度高者优先）、代价法（代价低者优先）及自然顺序法等。当然，要使用优先级法、可信度法、代价法等策略时，须事先给规则设定相关的参数，即优先级、可信度、代价等。正向推理算法二：(1)将初始事实/数据置入动态数据库。(2)用动态数据库中的事实/数据，匹配/测试目标条件，若目标条件满足，则推理成功，结束。(3)用规则库中各规则的前提匹配动态数据库中的事实/数据，将匹配成功的规则组成待用规则集。(4)若待用规则集为空，则运行失败，退出。(
9、5)用某种策略，从待用规则集中选取一条规则，将其结论加入动态数据库，或者执行其动作，撤消待用规则集，转步(2)。6.2.4程序实现1.1.产生式规则的程序语言产生式规则的程序语言实现实现 为了使表达简单规范,且便于推理,在实践中往往把规则的前提部分作成形如条件1 AND 条件2 AND AND 条件n或条件1 OR 条件2 OR OR 条件m把规则结论部分作成形如 断言1/动作1 AND 断言2/动作2 AND AND 断言k/动作k或断言1/动作1 OR 断言2/动作2 OR OR 断言k/动作k的形式，或者进一步简化成断言/动作由于含OR关系的规则也可以分解为几个不含OR关系的规则,所以,
10、产生式规则也可仅取下面的一种形式：条件1 AND 条件2 AND AND 条件n断言/动作 即前件是若干与关系的条件,后件仅有一个断言或动作。对规则作进一步细化。其条件、断言和动作都应该是陈述句。所以,它们可以用n元谓词(或子句)形式表示,或者用n元组的形式表示,如“对象-属性-值”三元组,“属性-值”二元组,或仅有“值”(符号、字符串或数值)的一元组等,而且谓词和元组中的项可以是常量、变量或复合项。当然,对于条件还可以用通常的关系式表示。如果规则解释程序(即推理机)不能直接支持上述的谓词或元组表示形式,那么,可用通常的记录、数组、结构、函数等数据结构来实现规则中的条件和断言,用通常的赋值式、
11、运算式、函数、过程等形式实现规则中的动作。至于规则的语言表示是否一定要有“IF-THEN”,或者“AND”、“OR”等连接符,这倒不一定。但原则是,在程序执行时必须能体现出规则前提和结论的对应关系,必须能体现出前提和结论中的逻辑关系。例如,我们完全可以用一个二元组(前件,后件)表示一个产生式规则。在PROLOG程序中要表示产生式规则,至少有两种形式：(1)用PROLOG的规则表示产生式规则。(2)用PROLOG的事实表示产生式规则。对这两种表示,对应的推理机是不一样的。若用方法(1),则一般就不必编写显式的推理机程序,因为对于这种形式的规则,PROLOG语言的翻译程序就是它的推理机。但若用方法
12、(2),则就必须用PROLOG语言编写显式的推理机程序。例6-3把例6-1中给出的产生式规则用PROLOG的规则可表示如下：animal_is(老虎):-it_is(食肉动物),fact(黄褐色),fact(有黑色条纹).it_is(食肉动物):-it_is1(哺乳动物),fact(有爪),fact(有犬齿),fact(目盯前方).it_is(食肉动物):-it_is1(哺乳动物),fact(吃肉).it_is1(哺乳动物):-fact(有奶).it_is1(哺乳动物):-fact(有毛发).对于这种规则表示形式，可以不用再编写推理机程序，而可直接利用PROLOG自身的推理机进行推理。例如，当
13、再给出如下的事实：fact(黄褐色).fact(有黑色条纹).fact(吃肉).fact(有奶).和目标：animal_is(Y).则程序运行后的结果就是:Y老虎但如果把上面的规则表示成如下的形式：rule(食肉动物,黄褐色,有黑色条纹,老虎).rule(哺乳动物,有爪,有犬齿,目盯前方,食肉动物).rule(哺乳动物,吃肉,食肉动物).rule(有奶,哺乳动物).rule(有毛发,哺乳动物).则就需要用PROLOG语言编写一个推理机程序。否则，无法实施基于上述规则的推理。还需说明的是,并非凡是用PROLOG规则表示的产生式规则,都可直接使用PROLOG的推理机。例如,rule(X,Y):-Y
14、=X+1.这是一个含变量的规则,其中X为前提,Y是结论。也就是说,在推理时是把rule(X,Y)作为规则使用的。显然,对于这种形式的规则,仍然需要重新编写推理机。2.规则库的程序规则库的程序实现实现 规则库的程序实现分为内存和外存两个方面。在内存中规则库可用链表实现,在外存则就是以规则为基本单位的数据文件。但若用PROLOG程序,对于用PROLOG的规则表示的产生式规则,规则库就是程序的一部分；对于PROLOG事实表示的规则,则规则库在内存就是动态数据库,在外存就是数据库文件。还需说明的是,对于规则库实际上还需配一个管理程序,即知识库管理系统,专门负责规则及规则库的各项管理工作。知识库管理系统
15、的设计也与规则的表示形式密切相关。3.动态数据库的程序动态数据库的程序实现实现 动态数据库由推理时所需的初始事实数据、推理的中间结果、最后结果以及其他控制或辅助信息组成。这些事实数据的具体表示方法与上面所述的规则条件与结论的语言表示方法基本一样,区别就是动态数据库中的事实数据中不能含有变量。动态数据库在内存可由(若干)链表实现并组成。在PROLOG程序中实现动态数据库,则可不必编写链表程序,而利用PROLOG提供的动态数据库直接实现。4.推理机的程序推理机的程序实现实现 推理机的程序实现,除了依据某一控制策略和算法编程外,一般来说,程序中还应具有模式匹配与变量的替换合一机制。因为模式匹配是推理
16、的第一步,同时规则中一般都含有变量,而变量的匹配必须有替换合一机制的支持。当然,要实现合一,就要用合一算法。那么,前面归结推理中的合一算法,对产生式系统也是适用的(如果不是谓词公式合一,则需稍作修改)。6.3 产生式系统与图搜索问题求解 分析前面给出的两个正向推理算法,可以看出,它们只能用于解决逻辑推理性问题。那么,如何用正向推理来求解规划性问题呢？如果要用正向推理求解规划性问题,则上述算法中至少还需增加以下功能：(1)记录动态数据库状态变化的历史,这就需要增设一个CLOSED表。(2)若要回溯,则还需保存与每个动态数据库状态对应的可用规则集。因为动态数据库状态与可用规则集实际是一一对应的。当回溯到上一个动态数据库状态(节点)后,需从其可用规则集中重新选取一条规则。(3)要进行树式搜索,还需设置一个OPEN表,以进行新生动态数据库的状态保存和当前动态数据库状态的切换。(4)还要考虑一条规则是否只允许执行一次。若是,则要对已执行了的规则进行标记。但这样以来,产生式系统的推理算法就与第3章的图搜索算法相差无几了。下面我们再将产生式系统与图搜索(含状态图搜索和与或图搜索)中的有关概念作一对比(如表6-1所示)。
