搜索推理技术2

1、搜索推理技术搜索推理技术(2)伍淳华伍淳华北京邮电大学计算机学院北京邮电大学计算机学院Machine Intelligence主要内容主要内容产生式系统产生式系统不确定性推理不确定性推理非单调性推理非单调性推理Machine Intelligence产生式系统产生式系统v 概述概述l“产生式” 1943 年 Post 首先在一种计算形式体系中提出的术语。l60年代开始，产生式系统成为专家系统的最基本的结构。l产生式系统在形式上很简单，但在一定意义上模仿了人类思考的过程。 Machine Intelligencev产生式规则l产生式用于表示具有因果关系的知识l基本形式： P Q或者 IF P T

2、HEN Qn P 是产生式的前提（前件），用于指出该产生式是否可用的条件n Q 是一组结论或操作（后件），用于指出当前提 P 所指示的条件满足时，应该得出的结论或应该执行的操作产生式系统产生式系统Machine Intelligencel产生式规则的语义：n如果前提 P 被满足，则可推出结论 Q 或执行 Q 所规定的操作l 例：R: IF 动物会飞 AND 会下蛋 THEN 该动物是鸟产生式系统产生式系统Machine Intelligencev产生式系统的组成l 三要素：1、一个总数据库存放问题求解过程中各种当前信息的数据结构；2、一组产生式规则 描述相应领域内的知识3、一个控制系统 选择规

3、则库中与当前综合数据库相匹配的规则并执行，必要时进行冲突消解。产生式系统产生式系统Machine Intelligence产生式规则库综合数据库控制系统产生式系统的基本结构产生式系统产生式系统Machine Intelligence规则库n用于描述相应领域内知识的产生式集合称为规则库有效的表达领域内的过程性的知识对知识进行合理的组织和管理综合数据库n用于存放问题求解过程中各种当前信息的数据结构n 初始状态、事实或证据n 中间推理结论n 最后结果产生式系统产生式系统Machine Intelligence 推理机（控制系统）n由一组程序组成，用来控制产生式系统的运行，决定问题求解过程的推理线路，

4、实现对问题的求解。 匹配 冲突消解 操作产生式系统产生式系统Machine Intelligencev产生式系统的推理l 正向推理n从一组表示事实的谓词或命题出发， 使用一组产生式规则，用以证明该谓词公式或命题是否成立。 例：总数据库：P1 规则集合：R1:P1-P2 R2:P2-P3 R3:P3-P4 产生式系统产生式系统Machine Intelligencev产生式系统的推理l 正向推理将初始事实/数据置入动态数据库；用动态数据库中的事实/数据，匹配/测试目标条件，若目标条件满足，则推理成功，结束。用规则库中各规则的前提匹配动态数据库中的事实/数据，将匹配成功的规则组成待用规则集；若待用

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

6、用动态数据库中的事实/数据同其匹配，若匹配成功，转步2；n用规则集中的各规则的结论同该目标匹配，若匹配成功，则将第一个匹配成功且未用过的规则的前提作为新的目标，并取代原来的父目标而加入目标链，转步3；n若该目标是初始目标，则推理失败，退出。n将该目标的父目标移回目标链，取代该目标及其兄弟目标，转步3；产生式系统产生式系统Machine Intelligence产生式系统产生式系统v产生式系统的推理l 正逆向推理的比较 项 目正向推理逆向推理驱动方式推理方法启动方法推理方向典型系统数据驱动从一组数据出发向前推导结论从一个事件启动由底向上推理CLIPS，OPS目标驱动从可能的解答出发，向后推理验证

7、明解答由询问关于目标状态的一个问题而启动由顶向下推理PROLOGMachine Intelligencev一个简单的例子 问题：设字符转换规则ABCACDBCGBEFDE 已知：A，B求：F产生式系统产生式系统Machine Intelligencev一个简单的例子（续1）n综合数据库x，其中x为字符n规则集 1：IF AB THEN C2：IF AC THEN D3：IF BC THEN G4：IF BE THEN F5：IF D THEN E产生式系统产生式系统Machine Intelligencev一个简单的例子（续2）n控制策略 顺序排队n初始条件A，Bn结束条件Fx产生式系统产生式

8、系统Machine Intelligencev一个简单的例子（续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，F1，IF AB THEN C 2，IF AC THEN D3，IF BC THEN G 4，IF BE THEN F5，IF D THEN E求解过程求解过程产生式系统产生式系统Machine Intelligencev 例 动物分类问题的产生式系统描述及其求解。 设由下列动物识别规则组成一个规则库，推理机采用正向推理算法，建立一个

9、产生式系统。该产生式系统就是一个小型动物分类知识库系统。n 规则： r1：若某动物有奶，则它是哺乳动物。 r2：若某动物有毛发，则它是哺乳动物 r3：若某动物有羽毛，则它是鸟。 r4：若某动物会飞且生蛋，则它是鸟。 r5：若某动物是哺乳动物且有爪且有犬齿且目盯前方，则它是食肉动物。v 产生式系统产生式系统Machine Intelligence r6：若某动物是哺乳动物且吃肉，则它是食肉动物。 r7：若某动物是哺乳动物且有蹄，则它是有蹄动物。 r8：若某动物是有蹄动物且反刍食物，则它是偶蹄动物。 r9：若某动物是食肉动物且黄褐色且有黑色条纹，则它是老虎。 r10：若某动物是食肉动物且黄褐色且有

10、黑色斑点，则它是金钱豹。 r11：若某动物是有蹄动物且长腿且长脖子且黄褐色且有暗斑点，则它是长颈鹿。产生式系统产生式系统Machine Intelligence r12：若某动物是有蹄动物且白色且有黑色条纹，则它是斑马。 r13：若某动物是鸟且不会飞且长腿且长脖子且黑白色，则它是驼鸟。 r14：若某动物是鸟且不会飞且会游泳且黑白色，则它是企鹅。 r15：若某动物是鸟且善飞且不怕风浪，则它是海燕。产生式系统产生式系统Machine Intelligencen初始事实： f1：某动物有毛发。 f2：吃肉。 f3：黄褐色。 f4：有黑色条纹。n 目标条件为：该动物是什么？产生式系统产生式系统Mach

11、ine Intelligence动物分类正向推理树动物分类正向推理树 老虎食肉动物哺乳动物有毛发吃肉黄褐色有黑色条纹产生式系统产生式系统r2r6r6r9r9r9Machine Intelligence图55 动物分类反向推理树 产生式系统产生式系统逆向推理，判断该动物是否为老虎：Machine Intelligencev产生式表示法的特点 优点：（1）自然性： “如果 ，则 ” 形式表示知识，直观、自然，便于推理。（2）模块性： 规则与推理机构相对独立；对规则库的维护方便。（3）有效性： 既可表示确定性知识，又可表示不确定性知识；既有利于表示启发式知识，又可方便地表示过程性知识。（4）清晰性：

12、 规则格式固定，由前件与后件构成。产生式系统产生式系统Machine Intelligence 局限性：（1）效率不高：求解过程是 “匹配-冲突消解-执行” 的过程，若规则库较大，易引起组合爆炸。（2）不能表示具有结构性的知识：产生式适合于表示具有因果关系的过程性知识，不能表示具有结构关系的事物间的区别与联系。产生式系统产生式系统Machine Intelligencev证据的不确定性v结论的不确定性不确定性推理不确定性推理Machine Intelligencev 证据的不确定性n一般通过对事实赋予一个介于0和1之间的系数来表示事实的不确定性。这个系数被称为可信度。n当规则具有一个以上的条件

13、时，需要根据各条件的可信度来求得总条件的可信度。有两类方法：n以模糊集理论为基础的方法n以概率为基础的方法 不确定性推理不确定性推理Machine Intelligencev 证据的不确定性不确定性推理不确定性推理0.90.51.00.5证据可信度的模糊集处理法产生式规则的各个条件之间是合取的关系产生式规则的各个条件之间是合取的关系, ,取其可信度取其可信度的最小值代表总的可信度的最小值代表总的可信度Machine Intelligencev 证据的不确定性不确定性推理不确定性推理赋予每个证据以可信度赋予每个证据以可信度, ,当把单独条件的可信度结合起来求取当把单独条件的可信度结合起来求取总的

14、可信度时总的可信度时, ,它取决于各可信度的乘积它取决于各可信度的乘积. .0.90.51.00.45证据可信度的概率论处理法Machine Intelligencev 结论的不确定性n结论的不确定性也叫规则的不确定性，表示当规则的条件被完全满足时，产生某种结论的不确定性程度。n不确定性的表示：通过赋予一个介于0和1之间的系数来表示不确定性。不确定性推理不确定性推理Machine Intelligencev 结论的不确定性n不确定性的处理 如果规则的条件部分不完全确定，则求得结论的可信度的方法有两种：n取结论可信度为条件可信度与系数的乘积；不确定性推理不确定性推理0.5CinCout0.40.

15、8Machine Intelligencev 结论的不确定性按照某种概率论的解释，可以假设规则的条件部分的可信度Cin和其结论部分的可信度Cout间存在某种关系，用这种关系来代表规则的不确定性； 不确定性推理不确定性推理CinCoutCinCoutCinCoutMachine Intelligence不确定性推理不确定性推理v结论的不确定性n多个规则支持同一事实的不确定性n基于模糊集理论的方法n 取支持这个事实的多个规则的可信度的最大值作为事实的可信度。n基于概率论的方法 -首先把各个证据的可信度转换成可信性比例r。可信性比例r和可信度c之间的关系可表示为 -将各证据的可信度比例简单地相乘就可

16、以求得这些证据所支持的事实的可信性比例。 -利用公式将可信性比例转换为可信度。 1,1rrcccrMachine Intelligencev 单调推理：新的命题的加入不会推翻原来的命题，随着时间的推移，系统内含的知识有增无减，如建立在谓词逻辑基础上的系统。v 非单调推理：新的命题的加入有可能会推翻原有命题，随着时间的推移，系统内含的知识不一定是增加。非单调性推理非单调性推理Machine Intelligencev 需要非单调推理的理由v 知识的不完全，由于知识的不完全性，只能对某些问题做暂时的假设，这些假设可能对也可能不对，可在以后进一步修正；v 一个有限的信念集合仅仅是现实世界的近似描述，

17、会有很多的例外； 客观世界变化太快；非单调性推理非单调性推理Machine Intelligencev 缺省推理n 定义：当缺乏信息时，只要不出现相反的证据，就可以作一些有益的猜想。构造这种猜想称为缺省推理(default reasoning)。 Reiter的缺省逻辑：“S在缺省的条件下成立”是指“当且仅当没有事实证明S不成立时S是成立的”非单调性推理非单调性推理Machine Intelligencev 非单调推理系统：正确性维持系统n 定义：正确性维持系统(Truth Maintenance System,简称TMS)是一个已经实现了的非单调系统，用以协助其他推理程序维持系统的正确性，其

18、在其它程序所产生的命题之间保持相容性。非单调性推理非单调性推理Machine Intelligencev 非单调推理系统：正确性维持系统n 工作原理： 在TMS中，每一命题或规则均称为节点，且对任一节点以下两种状态必居其一：lIN 相信为真lOUT 不相信为真，或无理由相信为真，或当前没有可相信的理由。 IN节点是指那些至少有一个在当前说来是有效证实的节点。OUT结点则指那些当前无任何有效证实的节点。非单调性推理非单调性推理Machine Intelligencev 非单调推理系统：正确性维持系统n 工作原理：在系统中，有两种方式可用来证实一个节点的有效性可依赖于其它节点的有效性：(1) 支持

19、表 (SL (IN-节点) (OUT-节点)(2) 条件证明 (CP (结论) (IN-假设) (OUT-假设)非单调性推理非单调性推理Machine Intelligencev 非单调推理系统：正确性维持系统n 工作原理：(1) 支持表 (SL (IN-节点) (OUT-节点)-如果某个结论中所有IN节点表中提到的节点当前都是IN，且在OUT节点表中提到的节点当前都是OUT，那么该结论当前是有效的。 例：a. 现在是冬天(SL()() b.天气是寒冷的(SL(a)()非单调性推理非单调性推理Machine Intelligencev 非单调推理系统：正确性维持系统n 工作原理：(2) 条件证明 (CP (结论) (IN-假设) (OUT-假设) 条件证明可以