搜索推理技术2讲述

《搜索推理技术2讲述》由会员分享，可在线阅读，更多相关《搜索推理技术2讲述（47页珍藏版）》请在金锄头文库上搜索。

1、搜索推理技术(2) 伍淳华 北京邮电大学计算机学院 主要内容 产生式系统 不确定性推理 非单调性推理 产生式系统 v概述 l“产生式” 1943 年 Post 首先在 一种计算形式体系中提出的术语。 l60年代开始，产生式系统成为专家系 统的最基本的结构。 l产生式系统在形式上很简单，但在一 定意义上模仿了人类思考的过程。 v产生式规则 l产生式用于表示具有因果关系的知识 l基本形式：P Q 或者 IF P THEN Q n P 是产生式的前提（前件），用于指出该产 生式是否可用的条件 n Q 是一组结论或操作（后件），用于指出当 前提 P 所指示的条件满足时，应该得出的结 论或应该执行的操作

2、 产生式系统 l产生式规则的语义： n如果前提 P 被满足，则可推出结论 Q 或执行 Q 所规定的操作 l 例： R: IF 动物会飞 AND 会下蛋 THEN 该动物是鸟 产生式系统 v产生式系统的组成 l 三要素： 1、一个总数据库 存放问题求解过程中各种当前信息的数据结构； 2、一组产生式规则 描述相应领域内的知识 3、一个控制系统 选择规则库中与当前综合数据库相匹配的规则并 执行，必要时进行冲突消解。 产生式系统 产生式规则库综合数据库 控制系统 产生式系统的基本结构 产生式系统 规则库 n用于描述相应领域内知识的产生式集合称为 规则库 有效的表达领域内的过程性的知识 对知识进行合理的

3、组织和管理 综合数据库 n用于存放问题求解过程中各种当前信息的数 据结构 n初始状态、事实或证据 n中间推理结论 n最后结果 产生式系统 推理机（控制系统） n由一组程序组成，用来控制产生式系 统的运行，决定问题求解过程的推理 线路，实现对问题的求解。 匹配 冲突消解 操作 产生式系统 v产生式系统的推理 l 正向推理 n从一组表示事实的谓词或命题出发， 使用一组 产生式规则，用以证明该谓词公式或命题是否成 立。 例：总数据库：P1 规则集合：R1:P1-P2 R2:P2-P3 R3:P3-P4 产生式系统 v产生式系统的推理 l 正向推理 1) 将初始事实/数据置入动态数据库； 2) 用动态

4、数据库中的事实/数据，匹配/测试目 标条件，若目标条件满足，则推理成功，结 束。 3) 用规则库中各规则的前提匹配动态数据库中 的事实/数据，将匹配成功的规则组成待用规 则集； 4) 若待用规则集为空，则运行失败，退出。 5) 将待用规则集中各个规则的结论加入动态数 据库，或者执行其动作，转入2； 产生式系统 v产生式系统的推理 l 逆向推理 n从表示目标的谓词或命题出发，使用一组产生式 规则证明事实谓词或命题成立，即首先提出一批 假设目标，然后逐一验证这些假设。 例：总数据库：P1 规则集合：R1:P1-P2 R2:P2-P3 R3:P3-P4 产生式系统 v产生式系统的推理 l 逆向推理

5、1.将初始事实/数据置入动态数据库，将目标条件置入 目标链； 2.若目标链为空，则推理成功，结束。 3.取出目标链中的第一个目标，用动态数据库中的事实/ 数据同其匹配，若匹配成功，转步2； 4.用规则集中的各规则的结论同该目标匹配，若匹配成 功，则将第一个匹配成功且未用过的规则的前提作为新 的目标，并取代原来的父目标而加入目标链，转步3； 5.若该目标是初始目标，则推理失败，退出。 6.将该目标的父目标移回目标链，取代该目标及其兄弟 目标，转步3； 产生式系统 产生式系统 v产生式系统的 推理 l 正逆向推理的比较 项 目正向推理逆向推理 驱动方式 推理方法 启动方法 推理方向 典型系统 数据

6、驱动 从一组数据出发向前推 导结论 从一个事件启动 由底向上推理 CLIPS，OPS 目标驱动 从可能的解答出发，向后推 理验证明解答 由询问关于目标状态的一个 问题而启动 由顶向下推理 PROLOG v一个简单的例子 问题：设字符转换规则 ABC ACD BCG BEF DE 已知：A，B 求：F 产生式系统 v一个简单的例子（续1） n综合数据库 x，其中x为字符 n规则集 1：IF AB THEN C 2：IF AC THEN D 3：IF BC THEN G 4：IF BE THEN F 5：IF D THEN E 产生式系统 v一个简单的例子（续2） n控制策略 顺序排队 n初始条件

7、 A，B n结束条件 Fx 产生式系统 v一个简单的例子（续3） 综合数据库可触发规则被触发规则 A，B（1）（1） A，B，C（2）（3）（2） A，B，C，D（3）（5）（3） A，B，C，D，G（5）（5） A，B，C，D，G，E（4）（4） A，B，C，D，G，E，F 1，IF AB THEN C 2，IF AC THEN D 3，IF BC THEN G 4，IF BE THEN F 5，IF D THEN E 求解过程 产生式系统 v 例 动物分类问题的产生式系统描述及其求解。 设由下列动物识别规则组成一个规则库，推理机采用 正向推理算法，建立一个产生式系统。该产生式系统就是 一个

8、小型动物分类知识库系统。 n 规则： r1：若某动物有奶，则它是哺乳动物。 r2：若某动物有毛发，则它是哺乳动物 r3：若某动物有羽毛，则它是鸟。 r4：若某动物会飞且生蛋，则它是鸟。 r5：若某动物是哺乳动物且有爪且有犬齿且目盯前方 ，则它是食肉动物。 v 产生式系统 r6：若某动物是哺乳动物且吃肉，则它是食肉动物 。 r7：若某动物是哺乳动物且有蹄，则它是有蹄动物 。 r8：若某动物是有蹄动物且反刍食物，则它是偶蹄 动物。 r9：若某动物是食肉动物且黄褐色且有黑色条纹， 则它是老虎。 r10：若某动物是食肉动物且黄褐色且有黑色斑点， 则它是金钱豹。 r11：若某动物是有蹄动物且长腿且长脖子

9、且黄褐色 且有暗斑点，则它是长颈鹿。 产生式系统 r12：若某动物是有蹄动物且白色且有黑色 条纹，则它是斑马。 r13：若某动物是鸟且不会飞且长腿且长脖 子且黑白色，则它是驼鸟。 r14：若某动物是鸟且不会飞且会游泳且黑 白色，则它是企鹅。 r15：若某动物是鸟且善飞且不怕风浪，则 它是海燕。 产生式系统 n初始事实： f1：某动物有毛发。 f2：吃肉。 f3：黄褐色。 f4：有黑色条纹。 n 目标条件为：该动物是什么？ 产生式系统 动物分类正向推理树 老虎 食肉动物 哺乳动物 有毛发 吃肉 黄褐色 有黑色条纹 产生式系统 r2 r6 r6 r9 r9 r9 图55 动物分类反向推理树 产生式

10、系统 逆向推理，判断该动物是否为老虎： v产生式表示法的特点 优点： （1）自然性： “如果 ，则 ” 形式表示知识，直观、自然，便 于推理。 （2）模块性： 规则与推理机构相对独立；对规则库的维护方便。 （3）有效性： 既可表示确定性知识，又可表示不确定性知识；既 有利于表示启发式知识，又可方便地表示过程性知 识。 （4）清晰性： 规则格式固定，由前件与后件构成。 产生式系统 局限性： （1）效率不高： 求解过程是 “匹配-冲突消解-执行” 的 过程，若规则库较大，易引起组合爆炸。 （2）不能表示具有结构性的知识： 产生式适合于表示具有因果关系的过程性 知识，不能表示具有结构关系的事物间的

11、区别与联系。 产生式系统 v证据的不确定性 v结论的不确定性 不确定性推理 v证据的不确定性 n一般通过对事实赋予一个介于0和1 之间的系数来表示事实的不确定性 。这个系数被称为可信度。 n当规则具有一个以上的条件时，需 要根据各条件的可信度来求得总条 件的可信度。有两类方法： n以模糊集理论为基础的方法 n以概率为基础的方法 不确定性推理 v证据的不确定性 不确定性推理 0.9 0.5 1.0 0.5 证据可信度的模糊集处理法 产生式规则的各个条件之间是合取的关系,取其可信度 的最小值代表总的可信度 v证据的不确定性 不确定性推理 赋予每个证据以可信度,当把单独条件的可信度结合起来求取 总的

12、可信度时,它取决于各可信度的乘积. 0.9 0.5 1.0 0.45 证据可信度的概率论处理法 v结论的不确定性 n结论的不确定性也叫规则的不确定 性，表示当规则的条件被完全满足 时，产生某种结论的不确定性程度 。 n不确定性的表示：通过赋予一个介 于0和1之间的系数来表示不确定性 。 不确定性推理 v结论的不确定性 n不确定性的处理 如果规则的条件部分不完全确定 ，则求得结论的可信度的方法有两 种： n取结论可信度为条件可信度与系数的 乘积； 不确定性推理 0.5 CinCout 0.4 0.8 v结论的不确定性 n按照某种概率论的解释，可以假设规 则的条件部分的可信度Cin和其结论部 分的

13、可信度Cout间存在某种关系，用这 种关系来代表规则的不确定性； 不确定性推理 Cin Cout Cin Cout Cin Cout 不确定性推理 v 结论的不确定性 n多个规则支持同一事实的不确定性 n基于模糊集理论的方法 取支持这个事实的多个规则的可信度的 最大值作为事实的可信度。 n基于概率论的方法 -首先把各个证据的可信度转换成可信性比 例r。可信性比例r和可信度c之间的关系可表示为 -将各证据的可信度比例简单地相乘就可以 求得这些证据所支持的事实的可信性比例。 -利用公式将可信性比例转换为可信度。 v单调推理：新的命题的加入不会推翻 原来的命题，随着时间的推移，系统 内含的知识有增无

14、减，如建立在谓词 逻辑基础上的系统。 v非单调推理：新的命题的加入有可能 会推翻原有命题，随着时间的推移， 系统内含的知识不一定是增加。 非单调性推理 v需要非单调推理的理由 v知识的不完全，由于知识的不完全 性，只能对某些问题做暂时的假设 ，这些假设可能对也可能不对，可 在以后进一步修正； v一个有限的信念集合仅仅是现实世 界的近似描述，会有很多的例外； v客观世界变化太快； 非单调性推理 v缺省推理 n定义：当缺乏信息时，只要不出现 相反的证据，就可以作一些有益的 猜想。构造这种猜想称为缺省推理 (default reasoning)。 Reiter的缺省逻辑：“S在缺省 的条件下成立”是

15、指“当且仅当没 有事实证明S不成立时S是成立的” 非单调性推理 v非单调推理系统：正确性维持系统 n定义：正确性维持系统(Truth Maintenance System,简称TMS)是一 个已经实现了的非单调系统，用以 协助其他推理程序维持系统的正确 性，其在其它程序所产生的命题之 间保持相容性。 非单调性推理 v非单调推理系统：正确性维持系统 n工作原理： 在TMS中，每一命题或规则均称为节点，且对 任一节点以下两种状态必居其一： lIN 相信为真 lOUT 不相信为真，或无理由相信为真，或当前没有可 相信的理由。 IN节点是指那些至少有一个在当前说来是有效证 实的节点。OUT结点则指那些

16、当前无任何有效证实 的节点。 非单调性推理 v非单调推理系统：正确性维持系统 n工作原理： 在系统中，有两种方式可用来证实一个节点 的有效性可依赖于其它节点的有效性： (1) 支持表 (SL (IN-节点) (OUT-节点) (2) 条件证明 (CP (结论) (IN-假设) (OUT-假设) 非单调性推理 v非单调推理系统：正确性维持系统 n工作原理： (1) 支持表 (SL (IN-节点) (OUT-节点) -如果某个结论中所有IN节点表中提到的 节点当前都是IN，且在OUT节点表中提到 的节点当前都是OUT，那么该结论当前是有 效的。 例：a. 现在是冬天(SL()() b.天气是寒冷的(SL(a)() 非单调性推理 v非单调推理系统：正确性维持系统 n工作原理： (2) 条件证明 (CP (结论) (IN-假设) (OUT-假设) 条件证明可以表示出现矛盾的原 因，一个矛盾存在是该表中的理由