人工智能第二次上机.ppt

《人工智能第二次上机.ppt》由会员分享，可在线阅读，更多相关《人工智能第二次上机.ppt（42页珍藏版）》请在三一办公上搜索。

1、1页,第5章 产生式系统,5.1 产生式规则5.2 产生式系统5.3 产生式系统与图搜索 5.4 产生式系统的应用5.5 产生式系统的程序实现,产生式系统的体系结构是实现图搜索的理想的程序结构。产生式系统是人工智能系统的一种最典型最普遍的结构形式。从体系结构看，智能系统（如专家系统）都是产生式系统。,2页,5.1 产生式规则,5.1.1 产生式规则 产生式(Production)一词，首先是由美国数学家波斯特（E.Post）提出来的。波斯特根据替换规则提出了一种称为波斯特机的计算模型，模型中的每一条规则当时被称为一个产生式。后来，这一术语几经修改扩充，被用到许多领域。例如，形式语言中的文法规则

2、就称为产生式。产生式也称为产生式规则，或简称规则。,3页,产生式的一般形式为 前件后件 其中，前件就是前提，后件是结论或动作，前件和后件可以是由逻辑运算符AND、OR、NOT组成的表达式。产生式规则的语义是：如果前提满足，则可得结论或者执行相应的动作，即后件由前件来触发。所以，前件是规则的执行条件，后件是规则体。,4页,例如，下面就是几个产生式规则：(1)如果银行存款利率下调，那么股票价格上涨。(2)如果炉温超过上限，则立即关闭风门。(3)如果键盘突然失灵，且屏幕上出现怪字符，则是病毒发作。(4)如果胶卷感光度为200，光线条件为晴天，目标距离不超过5米，则快门速度取250，光圈大小取f16。

3、逻辑蕴含式就是产生式，产生式还包括各种操作、规则、变换、算子、函数等等。产生式描述了事物之间的一种对应关系（包括因果关系和蕴含关系）。一条产生 式规则就是一条知识。用产生式可以实现推理和操作，产生式规则是知识表示形式。,5页,5.1.2 基于产生式的推理模式 由产生式的涵义可知，利用产生式规则可以实现有前提条件的指令性操作，也可以实现逻辑推理。实现操作的方法是当测试到一条规则的前提条件满足时，就执行其后部的动作。这称为规则被触发或点燃。利用产生式规则实现逻辑推理的方法是当有事实能与某规则的前提匹配（即规则的前提成立）时，就得到该规则后部的结论（即结论也成立）。,6页,实际上，这种基于产生式规则

4、的逻辑推理模式，就是逻辑上所说的假言推理（对常量规则而言）和三段论推理（对变量规则而言），即：AB AB A BC B AC 这里的大前提就是一个产生式规则，小前提就是证据事实。有前提条件的操作和逻辑推理统称为推理，上式是基于产生式规则的一般推理模式，产生式系统中的推理是更广义的推理。,7页,5.2 产生式系统,5.2.1 产生式系统的组成 产生式系统由三部分组成：产生式规则库、推理机和动态数据库，其结构如图5-1所示。,8页,图51 产生式系统结构,产生式规则库,推理机,动态数据库,产生式规则库亦称产生式规则集，由领域规则组成，在机器中以某种动态数据结构进行组织。,推理机亦称控制执行机构，它

5、是一个程序模块，负责产生式规则的前提条件测试或匹配，规则的调度与选取，规则体的解释和执行。即推理机实施推理，并对推理进行控制，它也就是规则的解释程序。,动态数据库是动态数据结构，用来存放初始事实数据、中间结果和最后结果等。,9页,5.2.2 产生式系统的运行过程 产生式系统运行时，除了需要规则库以外，还需要有初始事实(或数据)和目标条件。目标条件是系统正常结束的条件，也是系统的求解目标。产生式系统启动后，推理机就开始推理，按所给的目标进行问题求解。推理机的一次推理过程，可如图52所示。,10页,图52 推理机的一次推理过程,11页,一个实际的产生式系统，其目标条件一般不会只经一步推理就可满足，

6、往往要经过多步推理才能满足或者证明问题无解。产生式系统的运行过程就是从初始事实出发，寻求到达目标条件的通路的过程。所以，产生式系统的运行过程也是一个搜索的过程但一般把产生式系统的整个运行过程也称为推理。,12页,5.2.3 控制策略与常用算法 产生式系统的推理可分为正向推理和反向推理两种基本方式。正向推理就是从初始事实数据出发，正向使用规则进行推理（即用规则前提与动态数据库中的事实匹配，或用动态数据库中的数据测试规则的前提条件，然后产生结论或动作），朝目标方向前进。下面我们给出产生式系统正向推理和反向推理的常用算法：,13页,1.正向推理 正向推理算法一：步1 将初始事实/数据置入动态数据库；

7、步2 用动态数据库中的事实/数据，匹配/测试目标条件，若目标条件满足，则推理成功，结束。步3 用规则库中各规则的前提匹配动态数据库中的事实/数据，将匹配成功的规则组成待用规则集；步4 若待用规则集为空，则运行失败，退出。步5 将待用规则集中各规则的结论加入动态数据库，或者执行其动作，转步2。,14页,图53 正向推理的动态数据库,可以看出，随着推理的进行，动态数据库的内容或者状态在不断变化。如果把动态数据库的每一个状态作为一个节点的话，则上述推理过程就是一个从初始状态（初始事实或数据）到目标状态（目标条件）的状态图搜索过程。,15页,例5.1 动物分类问题的产生式系统描述及其求解。设由下列动物

8、识别规则组成一个规则库，推理机采用上述正向推理算法，建立一个产生式系统。该产生式系统就是一个小型动物分类知识库系统。规则：r1：若某动物有奶，则它是哺乳动物。r2：若某动物有毛发，则它是哺乳动物。r3：若某动物有羽毛，则它是鸟。r4：若某动物会飞且生蛋，则它是鸟。r5：若某动物是哺乳动物且有爪且有犬齿且目盯前方，则它是食肉动物。,16页,r6：若某动物是哺乳动物且吃肉，则它是食肉动物。r7：若某动物是哺乳动物且有蹄，则它是有蹄动物。r8：若某动物是有蹄动物且反刍食物，则它是偶蹄动物。r9：若某动物是食肉动物且黄褐色且有黑色条纹，则它是老虎。r10：若某动物是食肉动物且黄褐色且有黑色斑点，则它是

9、金钱豹。r11：若某动物是有蹄动物且长腿且长脖子且黄褐色且有暗斑点，则它是长颈鹿。,17页,r12：若某动物是有蹄动物且白色且有黑色条纹，则它是斑马。r13：若某动物是鸟且不会飞且长腿且长脖子且黑白色，则它是驼鸟。r14：若某动物是鸟且不会飞且会游泳且黑白色，则它是企鹅。r15：若某动物是鸟且善飞且不怕风浪，则它是海燕。,18页,再给出初始事实：f1：某动物有毛发。f2：吃肉。f3：黄褐色。f4：有黑色条纹。目标条件为：该动物是什么？易见，该系统的运行结果为：该动物是老虎。其推理树如图54所示。,19页,图54 动物分类正向推理树,老虎,食肉动物,哺乳动物,有毛发,吃肉,黄褐色,有黑色条纹,2

10、0页,2.反向推理 反向推理就是从目标出发，反向使用规则进行推理（即用规则结论与目标匹配，又产生新的目标，然后对新目标再作同样的处理），朝初始事实或数据方向前进。反向推理算法：步1 将初始事实/数据置入动态数据库，将目标条件置入目标链；步2 若目标链为空，则推理成功，结束。步3 取出目标链中第一个目标，用动态数据库中的事实/数据同其匹配，若匹配成功，转步2；,21页,步4 用规则集中的各规则的结论同该目标匹配，若匹配成功，则将第一个匹配成功且未用过的规则的前提作为新的目标，并取代原来的父目标而加入目标链，转步3；步5 若该目标是初始目标，则推理失败，退出。步6 将该目标的父目标移回目标链，取代

11、该目标及其兄弟目标，转步3。可以看出，上述反向推理算法的推理过程也是一个图搜索过程，而且一般是一个与或树搜索。,22页,例5.2 对于例5.1中的产生式系统，改为反向推理算法，则得到图55所示的推理树。,23页,图55 动物分类反向推理树,24页,可以看出，与正向推理不同，这次的推理树是从上而下扩展而成的，而且推理过程中还发生过回溯。反向推理也称为后向推理、反向链、目标驱动的推理等。从上面的两个算法可以看出，正向推理是自底向上的综合过程，而反向推理则是自顶向下的分析过程。除了正向推理和反向推理外，产生式系统还可进行双向推理。双向推理就是同时从初始数据和目标条件出发进行推理，如果在中间某处相遇，

12、则推理搜索成功。,25页,3.冲突消解策略 上述正向推理算法中，对所有匹配成功的规则都同时触发启用。所以，它实现的搜索是穷举式的树式盲目搜索。下面我们给出一个正向推理的启发式线式搜索算法。正向推理算法二：步1 将初始事实/数据置入动态数据库；步2 用动态数据库中的事实/数据，匹配/测试目标条件，若目标条件满足，则推理成功，结束。,26页,步3 用规则库中各规则的前提匹配动态数据库中的事实/数据，将匹配成功的规则组成待用规则集；步4 若待用规则集为空，则运行失败，退出。步5 用某种策略，从待用规则集中选取一条规则，将其结论加入动态数据库，或者执行其动作，撤消待用规则集，转步2。可以看出，该算法与

13、前面的算法仅在步5有所差别。规则的选择策略成为冲突消解策略。产生式系统的推理方式、搜索策略及冲突消解策略等，一般统称为推理控制策略，简称控制策略。控制策略体现在推理机的算法描述中。,27页,5.3 产生式系统与图搜索,分析前面给出的两个正向推理算法，可以看出，它们只能用于解决逻辑推理性问题。如果要用正向推理来求解规划性问题，则上述算法中至少还需要增加以下功能：(1)记录动态数据库状态变化的历史，这就需要增设一个CLOSED表。(2)若要回溯，则还需保存与每个动态数据库状态对应的可用规则集。因为动态数据库状态与可用规则集实际是一一对应的。,28页,(3)要进行树式搜索，还需设置一个OPEN表，以

14、进行新生动态数据库的状态保存和当前动态数据库状态的切换。(4)还要考虑一条规则是否只允许执行一次。若是，则要对已执行了的规则进行标记。这样一来，产生式系统的推理算法与图搜索算法就相差无几了。事实上，产生式系统和图搜索在对问题的表示和解法实际是等价的。,29页,表5.1 产生式系统与图搜索对比,30页,可以看出，二者实际是一回事。要说差别的话，图搜索技术描述了问题求解的方法，而产生式系统则给出了实施这种方法的一种计算机程序系统的结构模式。这样，问题求解、图搜索和产生式系统三者的关系是：问题求解是目的，图搜索是方法，产生式系统是形式。,31页,5.4 产生式系统的应用,由上述产生式系统与图搜索的关

15、系可见，产生式系统完全可以作为问题求解的表示模型和求解模型，而且可作为人工智能问题求解系统的通用模型。用产生式系统也可实现基于谓词逻辑的演绎推理和证明。事实上，当一个产生式系统中的规则是逻辑蕴含式时，其运行过程就是演绎推理（假言推理或三段论）的过程。这时目标值已知时就是证明，当目标值未知时就是推理求值。,32页,还需要说明的是，归结演绎系统也可以看作是一种特殊的产生式系统，只是这时规则只有一条，那就是归结原理。由于产生式系统既可用于操作性问题求解，也可用于推理性问题求解。因此，产生式系统也是专家系统的基本结构形式。用它既可实现规划型专家系统，也可实现结论型专家系统。总之，产生式系统在人工智能技

16、术中占有重要地位。,33页,5.5 产生式系统的程序实现,5.5.1 产生式规则的程序语言实现 上面我们对产生式的讨论，只是用自然语言进行描述并仅在概念层次上进行阐述，而并未涉及它的具体结构和程序语言实现问题。现在讨论产生式规则的程序语言实现问题。首先，讨论产生式规则的结构问题。一般来讲，产生式规则的前提和结论部分可以是一个复杂的逻辑表达式，但为了使表达简单规范，且便于推理，在实践中人们往往把规则的前提部分作成形如,34页,条件1AND条件2ANDAND条件n 或 条件1OR条件2OROR条件m 的形式（其中的条件可以带否定词）；把规则结论部分作成形如 断言1/动作1AND断言2/动作2AND

17、AND断言k/动作k 或 断言1/动作1OR断言2/动作2OROR断言k/动作k,35页,的形式，或者进一步简化成 断言/动作即仅有一项的形式。由于含OR关系的规则也可以分解为几个不含OR关系 的规则，所以，产生式规则也可仅取下面的一种形式：条件1AND条件2ANDAND条件n断言/动作即前件是若干与关系的条件，后件仅有一个断言或动作。,36页,例5.3 把5.2节例5.1中给出的产生式规则用PROLOG的规则可表示如下：animal-is(老虎):-it-is(食肉动物),fact(黄褐色),fact(有黑色条纹).it-is(食肉动物):-it-is1(哺乳动物),fact(有爪),fac

18、t(有犬齿),fact(目盯前方).,37页,it-is(食肉动物):-it-is1(哺乳动物),fact(吃肉).It-is1(哺乳动物):-fact(有奶).It-is1(“哺乳动物”):-fact(“有毛发”).对于这种规则表示形式，可以不用再编写推理机程序，而可直接利用PROLOG自身的推理机，进行推理。例如，当再给出如下的事实：fact(黄褐色).fact(有黑色条纹).fact(吃肉).fact(有奶).,38页,和目标：animal-is(Y).则程序运行后的结果就是:Y老虎 但如果把上面的规则表示成如下的形式:rule(食肉动物,黄褐色,有黑色条纹,老虎).rule(哺乳动物,

19、有爪,有犬齿,目盯前方,食肉动物).rule(哺乳动物,吃肉,食肉动物).rule(有奶,哺乳动物).rule(有毛发,哺乳动物).,39页,则就需要用PROLOG语言编写一个推理机程序。否则，无法实施基于上述规则的推理。还需说明的是，并非凡是用PROLOG规则表示的产生式规则，都可直接使用PROLOG的推理机。例如，rule(X,Y):-Y=X+1.这是一个含变量的规则，其中X为前提，Y是结论。也就是说，在推理时是把rule(X,Y)作为规则使用的。显然，对于这种形式的规则，仍然需要重新编写推理机。,40页,5.5.2 规则库的程序实现 规则库的程序实现分为内存和外存两个方面。在内存中规则库

20、可用链表实现，在外存则就是以规则为基本单位的数据文件。但若用PROLOG程序，对于用PROLOG的规则表示的产生式规则，规则库就是程序的一部分；对于PROLOG事实表示的规则，则规则库在内存就是动态数据库，在外存就是数据库文件。还需说明的是，对于规则库实际上还需配一个管理程序，即知识库管理系统，专门负责规则及规则库的各项管理工作。知识库管理系统的设计也与规则的表示形式密切相关。,41页,5.5.3 动态数据库的程序实现 动态数据库由推理时所需的初始事实数据、推理的中间结果、最后结果以及其他控制或辅助信息组成。这些事实数据的具体表示方法与上面所述的规则条件与结论的语言表示方法基本一样，区别就是动态数据库中的事实数据中不能含有变量。动态数据库在内存可由（若干）链表实现并组成。在PROLOG程序中实现动态数据库，则可不必编写链表程序，而利用PROLOG提供的动态数据库直接实现。,42页,5.5.4 推理机的程序实现 推理机的程序实现，除了依据某一控制策略和算法编程外，一般来说，程序中还应具有模式匹配与变量的替换合一机制。因为模式匹配是推理的第一步，同时规则中一般都含有变量，而变量的匹配必须有替换合一机制的支持。当然，要实现合一，就要用合一算法。那么，前面归结推理中的合一算法，对产生式系统也是适用的（如果不是谓词公式合一，则需稍作修改）。,