人工智能第6章

《人工智能第6章》由会员分享，可在线阅读，更多相关《人工智能第6章（56页珍藏版）》请在金锄头文库上搜索。

1、第第 6 6 章章 基于产生式规则的机器推理基于产生式规则的机器推理 第第 6 6 章章 基于产生式规则的机器推理基于产生式规则的机器推理 6.1 产生式规则 6.2 产生式系统习题六 第第 6 6 章章 基于产生式规则的机器推理基于产生式规则的机器推理 6.1 产 生 式 规 则6.1.1 产生式规则产生式(Production)一词, 首先是由美国数学家波斯特(E.Post)提出来的。波斯特根据替换规则提出了一种称为波斯特机的计算模型, 模型中的每一条规则当时被称为一个产生式。 后来, 这一术语几经修改扩充, 被用到许多领域。例如, 形式语言中的文法规则就称为产生式。产生式也称为产生式规

2、则, 或简称规则。 第第 6 6 章章 基于产生式规则的机器推理基于产生式规则的机器推理 产生式的一般形式为 前件后件 其中, 前件就是前提, 后件是结论或动作,前件和后件可以是由逻辑运算符AND、OR、NOT组成的表达式。 产生式规则的语义是: 如果前提满足,则可得结论或者执 行相应的动作, 即后件由前件来触发。 所以, 前件是规则的执行条件, 后件是规则体。 第第 6 6 章章 基于产生式规则的机器推理基于产生式规则的机器推理 例如, 下面就是几个产生式规则： (1) 如果银行存款利率下调, 那么股票价格上涨。 (2) 如果炉温超过上限, 则立即关闭风门。 (3) 如果键盘突然失灵, 且屏

3、幕上出现怪字符, 则是病毒发作。 (4) 如果胶卷感光度为200, 光线条件为晴天, 目标距离 不超过5米, 则快门速度取250, 光圈大小取f16。 第第 6 6 章章 基于产生式规则的机器推理基于产生式规则的机器推理 可以看出,产生式与逻辑蕴含式非常相似。是的, 逻辑蕴含式就是产生式, 但它只是一种产生式。除逻辑蕴含式外, 产生式还包括各种操作、规则、变换、算子、函数等等。 比如上例中的(2)是一个产生式, 但并不是一个逻辑蕴含式。 概括来讲, 产生式描述了事物之间的一种对应关系(包括因果关系和蕴含关系), 其外延十分广泛。例如, 图搜索中的状态转换规则和问题变换规则就都是产生式规则。另外

4、还有程序设计语言的文法规则、逻辑中的逻辑蕴含式和等价式、数学中的微分和积分公式、化学中分子结构式的分解变换规则等等, 也都是 产生式规则；甚至体育比赛中的规则、国家的法律条文、 单位的规章制度等等, 也都可以表示成产生式规则。 第第 6 6 章章 基于产生式规则的机器推理基于产生式规则的机器推理 6.1.2 基于产生式规则的推理模式由产生式的涵义可知,利用产生式规则可以实现有前提条件的指令性操作, 也可以实现逻辑推理。实现操作的方法是当测试到一条规则的前提条件满足时, 就执行其后部的动作。 这称为规则被触发或点燃。利用产生式规则实现逻辑推理 的方法是当有事实能与某规则的前提匹配(即规则的前提成

5、立)时, 就得到该规则后部的结论(即结论也成立)。 第第 6 6 章章 基于产生式规则的机器推理基于产生式规则的机器推理 实际上,这种基于产生式规则的逻辑推理模式, 就是逻辑 上所说的假言推理(对常量规则而言)和三段论推理(对变量规则而言), 即： A B A B 这里的大前提就是一个产生式规则, 小前提就是证据事实。 其实, 我们也可以把上面的有前提条件的操作和逻辑推理统称为推理。那么,上面的式子也就是基于产生式规则的一般 推理模式。这就是说, 产生式系统中的推理是更广义的推理。 第第 6 6 章章 基于产生式规则的机器推理基于产生式规则的机器推理 6.2 产 生 式 系 统 6.2.1 系

6、统结构产生式系统由三部分组成： 产生式规则库、 推理机和动 态数据库, 其结构如图61所示。 产生式规则库亦称产生式规则集, 由领域规则组成, 在机 器中以某种动态数据结构进行组织。一个产生式规则集中的规 则, 按其逻辑关系, 一般可形成一个称为推理网络的结构图。推理机亦称控制执行机构,它是一个程序模块,负责产生式 规则的前提条件测试或匹配,规则的调度与选取,规则体的解释 和执行。即推理机实施推理, 并对推理进行控制, 它也就是规 则的解释程序。 第第 6 6 章章 基于产生式规则的机器推理基于产生式规则的机器推理 图 6-1 产生式系统的结构第第 6 6 章章 基于产生式规则的机器推理基于产

7、生式规则的机器推理 6.2.2 运行过程产生式系统运行时, 除了需要规则库以外, 还需要有初始事实(或数据)和目标条件。目标条件是系统正常结束的条件, 也是系统的求解目标。产生式系统启动后, 推理机就开始推理, 按所给的目标进行问题求解。 推理机的一次推理过程可如图 6-2所示。 第第 6 6 章章 基于产生式规则的机器推理基于产生式规则的机器推理 图 6-2 推理机的一次推理过程 第第 6 6 章章 基于产生式规则的机器推理基于产生式规则的机器推理 一个实际的产生式系统, 其目标条件一般不会只经一步推理就可满足, 往往要经过多步推理才能满足或者证明问题无解。 所以, 产生式系统的运行过程,就

8、是推理机不断运用规则库中的规则, 作用于动态数据库, 不断进行推理并不断检测目标条件是否满足的过程。当推理到某一步, 目标条件被满足, 则推理成功, 于是系统运行结束；或者再无规则可 用, 但目标条件仍未满足, 则推理失败, 当然系统也运行结束。 第第 6 6 章章 基于产生式规则的机器推理基于产生式规则的机器推理 由上所述, 产生式系统的运行过程也就是从初始事实出发, 寻求到达目标条件的通路的过程。 所以, 产生式系统的运行过程也是一个搜索的过程。但一般把产生式系统的整个运行过程也称为推理。那么, 一个产生式系统启动后,从哪儿 开始推理？ 下面我们就回答这个问题。 第第 6 6 章章 基于产

9、生式规则的机器推理基于产生式规则的机器推理 6.2.3 控制策略与常用算法产生式系统的推理可分为正向推理和反向推理两种基本方式。简单来讲, 正向推理就是从初始事实数据出发, 正向使用规则进行推理(即用规则前提与动态数据库中的事实匹配, 或用动态数据库中的数据测试规则的前提条件, 然后产生结论或执行动作),朝目标方向前进；反向推理就是从目标出发, 反向使用规则进行推理(即用规则结论与目标匹配, 又产生新的目标, 然后对新目标再作同样的处理),朝初始事实或数据方向前进。下面我们给出产生式系统正向推理和反向推理的常用算法 ： 第第 6 6 章章 基于产生式规则的机器推理基于产生式规则的机器推理 1.

10、 正向推理正向推理算法一： 步1 将初始事实/数据置入动态数据库。步2 用动态数据库中的事实/数据, 匹配/测试目标条件, 若目标条件满足, 则推理成功, 结束。 步3 用规则库中各规则的前提匹配动态数据库中的事实/数据, 将匹配成功的规则组成待用规则集。步4 若待用规则集为空, 则运行失败, 退出。 步5 将待用规则集中各规则的结论加入动态数据库, 或者执行其动作, 转步2。 第第 6 6 章章 基于产生式规则的机器推理基于产生式规则的机器推理 可以看出, 随着推理的进行, 动态数据库的内容或者状态在不断变化。如果我们把动态数据库的每一个状态作为一个节点的话, 则上述推理过程也就是一个从初始

11、状态(初始事实/数据)到目标状态(目标条件)的状态图搜索过程。 如果我们把动态数据库中每一个事实/数据作为一个节点的话, 则上述推理过程就是一个“反向”(即自底向上)与或树搜索过程。 第第 6 6 章章 基于产生式规则的机器推理基于产生式规则的机器推理 图 6-3 正向推理的动态数据库第第 6 6 章章 基于产生式规则的机器推理基于产生式规则的机器推理 例6.1 动物分类问题的产生式系统描述及其求解。 设由下列动物识别规则组成一个规则库, 推理机采用上述正向推理算法, 建立一个产生式系统。该产生式系统就是一个小型动物分类知识库系统。 规则集： r1： 若某动物有奶, 则它是哺乳动物。 r2：

12、若某动物有毛发, 则它是哺乳动物。 r3： 若某动物有羽毛, 则它是鸟。 r4： 若某动物会飞且生蛋, 则它是鸟。 第第 6 6 章章 基于产生式规则的机器推理基于产生式规则的机器推理 r5： 若某动物是哺乳动物且有爪且有犬齿且目盯前方, 则它是食肉动物。 r6： 若某动物是哺乳动物且吃肉, 则它是食肉动物。 r7： 若某动物是哺乳动物且有蹄, 则它是有蹄动物。 r8： 若某动物是有蹄动物且反刍食物, 则它是偶蹄动物。 r9： 若某动物是食肉动物且黄褐色且有黑色条纹, 则它是老虎。 r10： 若某动物是食肉动物且黄褐色且有黑色斑点, 则它是金钱豹。 第第 6 6 章章 基于产生式规则的机器推理

13、基于产生式规则的机器推理 r11： 若某动物是有蹄动物且长腿且长脖子且黄褐色且有暗斑点, 则它是长颈鹿。 r12：若某动物是有蹄动物且白色且有黑色条纹, 则它是斑马。 r13： 若某动物是鸟且不会飞且长腿且长脖子且黑白色, 则它是驼鸟。 r14： 若某动物是鸟且不会飞且会游泳且黑白色, 则它是企鹅。 r15： 若某动物是鸟且善飞且不怕风浪, 则它是海燕。 第第 6 6 章章 基于产生式规则的机器推理基于产生式规则的机器推理 图 6-4 规则集形成的部分推理网络 第第 6 6 章章 基于产生式规则的机器推理基于产生式规则的机器推理 再给出初始事实： f1：某动物有毛发。f2：吃肉。f3：黄褐色。

14、f4： 有黑色条纹。 目标条件为： 该动物是什么？易见, 该系统的运行结果为： 该动物是老虎。其推理树如图 6-5所示。 第第 6 6 章章 基于产生式规则的机器推理基于产生式规则的机器推理 图 6-5 关于“老虎”的正向推理树 第第 6 6 章章 基于产生式规则的机器推理基于产生式规则的机器推理 2. 反向推理反向推理算法：步1 将初始事实/数据置入动态数据库, 将目标条件置入目标链。步2 若目标链为空, 则推理成功, 结束。 步3 取出目标链中第一个目标, 用动态数据库中的事实/数据同其匹配, 若匹配成功, 转步2。第第 6 6 章章 基于产生式规则的机器推理基于产生式规则的机器推理 步4

15、 用规则集中的各规则的结论同该目标匹配, 若匹配成功,则将第一个匹配成功且未用过的规则的前提作为新的目标, 并取代原来的父目标而加入目标链, 转步3。步5 若该目标是初始目标, 则推理失败, 退出。 步6 将该目标的父目标移回目标链, 取代该目标及其兄弟目标, 转步3。 第第 6 6 章章 基于产生式规则的机器推理基于产生式规则的机器推理 例6.2 对于例6.1中的产生式系统, 改为反向推理算法, 则得到图 6-6所示的推理树。 图 6-6 关于“老虎”的反向推理树 第第 6 6 章章 基于产生式规则的机器推理基于产生式规则的机器推理 可以看出, 与正向推理不同, 这次的推理树是从上而下扩展而成的, 而且推理过程中还发生过回溯。 反向推理也称为后向推理、反向链、目标驱动的推理等。 从上面的两个算法可以看出,正向推理是自底向上的综合过程, 而反向推理则是自顶向下的分析过程。 除了正向推理和反向推理外,产生式系统还可进行双向推 理。双向推理就是同时从初始数据和目标条件出发进行推理, 如果在中间某处相遇, 则推理搜索成功。 第第 6 6 章章 基于产生式规则的机器推理基于产生式规则的机器推理 3. 冲突消解策略上述正向推理算法中, 对所有匹配成功的规则都同时触发启用。所以, 它实现的搜索是穷举式的树式盲目