基于产生式规则的推理

《基于产生式规则的推理》由会员分享，可在线阅读，更多相关《基于产生式规则的推理（46页珍藏版）》请在金锄头文库上搜索。

1、基于产生式规则的机器推理小组成员 雷晓艳张丽芳王瑞霞 主要内容 一 产生式规则概述二 产生式系统 产生式系统构成产生式系统的类型产生式系统的程序实现产生式系统的特点 产生式规则的产生和发展人工智能中使用产生式的理由产生式规则的界定及内容 产生式规则概述 产生式 1943年美国数学家Post首先在一种计算形式体系中提出的术语 20世纪70年代 Newell和Simon等学者在对人类认知模型研究中 开发了基于规则的产生式系统等 从那时开始 产生式系统成为专家系统的最基本的结构 从此 产生知识表示在人工智能中得到了广泛的应用 产生式系统在形式上很简单 但在一定意义上模仿了人类思考的过程 产生式规则的

2、产生和发展 为什么要采用产生式系统作为人工智能系统的主要结构呢 这可以有两点理由 用产生式系统结构求解问题的过程和人类求解问题时的思维过程很相象 下面要举例说明 因而可以用它来模拟人类求解问题时的思维过程 可以把产生式系统作为人工智能系统的基本结构单元或基本模式看待 就好像是积木世界中的积木块一样 因而研究产生式系统的基本问题就具有一般意义 人工智能中使用产生式的理由 产生式规则的界定及内容 产生式规则其实就是产生式系统的主体 是产生式系统知识表示的核心 故人们常把产生式表示直接称为产生式规则 或简称规则 这里所说的 规则 是指人们思维判断中的一种固定逻辑结构关系 一般产生式的结构可表示为自然

3、语言形式 事实上 在自然语言表达中 人们广泛使用的各种 原因 结果 条件 结论 前提 操作 事实 进展 情况 行为 等结构 都可归结为产生式的知识表达形式 例如 1 天下雨 地上湿 原因 结果 结构 2 如果把冰加热到零摄氏度以上 冰就会融化为水 条件 结论 结构 3 夜来风雨声 花落知多少 事实及其进展结构 4 若能找到一根合适的杠杆 就能撬起那座大山 前提 操作 5 才饮长江水 又食武昌鱼 事实及其进展结构 6 刚才开机了 意味着发出了捕获目标图像的信号 情况 行为 产生式规则的界定及内容 基本形式 A B或者IFATHENBA是产生式的前提 前件 用于指出该产生式是否可用的条件B是一组结

4、论或操作 后件 用于指出当前提A所指示的条件满足时 应该得出的结论或应该执行的操作例 R IF动物会飞AND会下蛋THEN该动物是鸟 产生式规则的界定及内容 基本形式 前件 后件 其中 前件就是前提 后件是结论或动作 前件和后件可以是由逻辑运算符AND OR NOT组成的表达式 语义 如果前提满足 则可得结论或者执行相应的动作 即后件由前件来触发 所以 前件是规则的执行条件 后件是规则体 产生式规则的界定及内容 产生式系统构成 组成三要素 一个综合数据库存放问题求解过程中当前信息的数据结构 一组产生式规则描述相应领域内的知识 有效的表达领域内的过程性的知识 对知识进行合理的组织和管理 一个控制

5、系统选择规则库中与当前综合数据库相匹配的规则并执行 必要时进行冲突消解 产生式系统的基本结构 产生式系统推理的基本过程 推理机的一次推理过程 问题 设字符转换规则A B CA C DB C GB E FD E已知 A B求 F 一个简单的例子 一 综合数据库 x 其中x为字符二 规则集1 IFA BTHENC2 IFA CTHEND3 IFB CTHENG4 IFB ETHENF5 IFDTHENE 一个简单的例子 续1 三 控制策略顺序排队四 初始条件 A B 五 结束条件F x 一个简单的例子 续2 在介绍求解过程之前 为了方便叙述 我们首先介绍两个术语 1 可触发规则 当一个规则的前件被

6、综合数据库中的数据满足时 该规则称为可触发规则 2 被触发规则 从可触发规则中选择一个规则来执行 被执行的规则称为被触发规则 该问题的求解过程 如下表所示 1 IFA BTHENC2 IFA CTHEND3 IFB CTHENG4 IFB ETHENF5 IFDTHENE 求解过程 A B是已知的条件 一开始就在综合数据库中 此时只有规则1是可触发的 由于只有一个可触发规则 所以选择规则1执行 规则1的执行结果得到C C被加入到综合数据库中 由于有了C 使得规则2和规则3成为可触发规则 此时规则1的前件虽然也同样可以被满足 由于该规则已经被执行过 而且其当前的触发条件并没有改变 与他被执行时的

7、条件是一样的 所以规则1不在可触发规则之列 此时可触发规则有两条 按照顺序排队策略 排在前面的规则优先执行 所以选择规则2为被触发规则 规则2的执行结果产生了D D被加入到综合数据库中 依次类推 规则3 规则5和规则4先后被执行 最终产生了F 从而F被求得 结束运行 一 按推理方向分类1 正向推理2 逆向推理3 双向推理 二 按搜索策略分类1 不可撤回方式2 试探性方式 1 回溯方式 2 图搜索方式 产生式系统的类型 从一组表示事实的谓词或命题出发 使用一组产生式规则 用以证明该谓词公式或命题是否成立 一般策略 先提供一批事实 数据 到总数据库中 系统利用这些事实与规则的前提相匹配 触发匹配成

8、功的规则 把其结论作为新的事实添加到总数据库中 继续上述过程 用更新过的总数据库的所有事实再与规则库中另一条规则匹配 用其结论再次修改总数据库的内容 直到没有可匹配的新规则 不再有新的事实加到总数据库中 正向推理 步1将初始事实 数据置入动态数据库 步2用动态数据库中的事实 数据 匹配 测试目标条件 若目标条件满足 则推理成功 结束 步3用规则库中各规则的前提匹配动态数据库中的事实 数据 将匹配成功的规则组成待用规则集 步4若待用规则集为空 则运行失败 退出 步5将待用规则集中各规则的结论加入动态数据库 或者执行其动作 转步2 正向推理算法 例动物分类问题的产生式系统描述及其求解 r1 若某动

9、物有奶 则它是哺乳动物 r2 若某动物有毛发 则它是哺乳动物 r3 若某动物有羽毛 则它是鸟 r4 若某动物会飞且生蛋 则它是鸟 r5 若某动物是哺乳动物且有爪且有犬齿且目盯前方 则它是食肉动物 r6 若某动物是哺乳动物且吃肉 则它是食肉动物 r7 若某动物是哺乳动物且有蹄 则它是有蹄动物 r8 若某动物是有蹄动物且反刍食物 则它是偶蹄动物 r9 若某动物是食肉动物且黄褐色且有黑色条纹 则它是老虎 r10 若某动物是食肉动物且黄褐色且有黑色斑点 则它是金钱豹 r11 若某动物是有蹄动物且长腿且长脖子且黄褐色且有暗斑点 则它是长颈鹿 r10 若某动物是食肉动物且黄褐色且有黑色斑点 则它是金钱豹

10、r11 若某动物是有蹄动物且长腿且长脖子且黄褐色且有暗斑点 则它是长颈鹿 r12 若某动物是有蹄动物且白色且有黑色条纹 则它是斑马 r13 若某动物是鸟且不会飞且长腿且长脖子且黑白色 则它是驼鸟 r14 若某动物是鸟且不会飞且会游泳且黑白色 则它是企鹅 r15 若某动物是鸟且善飞且不怕风浪 则它是海燕 规则集形成的部分推理网络 再给出初始事实 f1 某动物有毛发 f2 吃肉 f3 黄褐色 f4 有黑色条纹 目标条件为 该动物是什么 该系统的运行结果为 该动物是老虎 从表示目标的谓词或命题出发 使用一组产生式规则证明事实谓词或命题成立 即首先提出一批假设目标 然后逐一验证这些假设 一般策略 首先

11、假设一个可能的目标 然后由产生式系统试图证明此假设目标是否在总数据库中 若在总数据库中 则该假设目标成立 否则 若该假设为终叶 证据 节点 则询问用户 若不是 则再假定另一个目标 即寻找结论部分包含该假设的那些规则 把它们的前提作为新的假设 并力图证明其成立 这样反复进行推理 直到所有目标均获证明或者所有路径都得到测试为止 逆向推理 逆向推理算法 步1将初始事实 数据置入动态数据库 将目标条件置入目标链 步2若目标链为空 则推理成功 结束 步3取出目标链中第一个目标 用动态数据库中的事实 数据同其匹配 若匹配成功 转步2 步4用规则集中的各规则的结论同该目标匹配 若匹配成功 则将第一个匹配成功

12、且未用过的规则的前提作为新的目标 并取代原来的父目标而加入目标链 转步3 步5若该目标是初始目标 则推理失败 退出 步6将该目标的父目标移回目标链 取代该目标及其兄弟目标 转步3 例对于上例中的产生式系统 改为反向推理算法 则得到下图所示的推理树 关于 老虎 的反向推理树 双向推理双向推理的推理策略是同时从目标向事实推理和从事实向目标推理 并在推理过程中的某个步骤 实现事实与目标的匹配 1 不可撤回方式这种方式是利用问题给出的局部知识来决定如何选取规则 就是说根据当前可靠的局部知识选一条可应用规则并作用于当前综合数据库 接着再根据新状态继续选取规则 搜索过程一直进行下去 不必考虑撤回用过的规则

13、 这是由于在搜索过程中如能有效利用局部知识 即使使用了一条不理想的规则 也不妨碍下一步选得另一条更合适的规则 这样不撤消用过的规则 并不影响求到解 只是解序列中可能多了一些不必要的规则 显然这种策略具有控制简单的优点 下面用登山问题来进一步说明这种方式的基本思想 人们在登山过程中 目标是爬到峰顶 问题就是确定如何一步一步地朝着目标前进达到顶峰 其实这就是一个 爬山 过程中寻求函数的极大值问题 我们很容易想到利用高度随位置变化的函数H P 来引导爬山 就可实现不可撤回的控制方式 2 试探式的产生式系统即规则使用后 允许返回原来出发点重新选用其他规则 可分为 1 回溯法产生式系统在规则使用后 记住

14、原来的节点 若搜索遇到困难时可返回再选用其规则 如有界深度优先搜索 先试用某一规则 如果以后发现不合适 退回另选一条规则 新生成的状态前面出现过回溯条件确定从初态开始 用了若干规则仍未到达目标涉及两个问题 对当前状态 再无可用规则 利用已有知识对规则排序 可减少回溯次数 2 图搜索产生式系统同时掌握若干规则序列的效果 从中寻找问题的答案 为避免循环 通常采用树搜索 如广度优先搜索 四 产生式系统的程序实现 一 程序实现 1 产生式规则的程序语言实现2 规则库的程序实现 3 动态数据库的程序实现 4 推理机的程序实现 二 Prolog语言及其基本结构1 Prolog语言2 Prolog的基本结构

15、 1 产生式规则的程序语言实现将规则的前提部分做成形如条件1AND条件2AND AND条件n或条件1OR条件2OR OR条件m 将规则结论部分做成形如断言1 动作1AND断言2 动作2AND AND断言k 动作k 或 断言1 动作1OR断言2 动作2OR OR断言k 动作一般地做成 条件1AND条件2AND AND条件n 断言 动作 一 程序实现 一种是先确定好规则的语言表示形式 再根据规则形式设计规则解释程序 推理机 另一种是对已有的解释程序 推理机 设计规则表示形式 当然只能采用推理机所约定的规则形式 在PROLOG程序中要表示产生式规则 至少有两种形式 1 用PROLOG的规则表示产生式

16、规则 2 用PROLOG的事实表示产生式规则 例把上述动物分类系统中的产生式规则用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 有毛发 也可以将上面的规则表示成如下的形式 rule 食肉动物 黄褐色 有黑色条纹 老虎 rule 哺乳动物 有爪 有犬齿 目盯前方 食肉动物 rule 哺乳动物 吃肉 食肉动物 rule 有奶 哺乳动物 rule 有毛发 哺乳动物 2 规则库的程序实现 3 动态数据库的程序实现 4 推理机的程序实现 Prolog ProgramminginLogic的缩写 是一种逻辑编程语言 它建立在逻辑学的理论基础之上 最初被运用于自然语言等研究领域 Prolog是当代最有影响的人工智能语言之一 由于该语言很适合表达人的思维和推理规则 在自然语言理解 机器定理证明 专家