基于产生式规则的推理.ppt

   基于产生式规则基于产生式规则 的机器推理的机器推理 小组成员小组成员: : 雷晓艳雷晓艳 张丽芳张丽芳 王瑞霞王瑞霞  主要内容主要内容一一 、、产生式规则产生式规则概述概述二二、、 产生式系统产生式系统p 产生式系统构成产生式系统构成p 产生式系统的类型产生式系统的类型p 产生式系统的程序实现产生式系统的程序实现p 产生式系统的特点产生式系统的特点  p产生式规则的产生和发展产生式规则的产生和发展p人工智能中使用产生式的理由人工智能中使用产生式的理由p产生式规则的界定及内容产生式规则的界定及内容产生式规则产生式规则概述概述  { “产生式” — 1943 年美国数学家 Post 首先在一种计算形式体系中提出的术语。

{ 20世纪70年代，Newell和Simon等学者在对人类认知模型研究中，开发了基于规则的产生式系统等从那时开始，产生式系统成为专家系统的最基本的结构从此，产生知识表示在人工智能中得到了广泛的应用{ 产生式系统在形式上很简单，但在一定意义上模仿了人类思考的过程产生式规则的产生和发展产生式规则的产生和发展   为什么要采用产生式系统作为人工智能系统的主要结构呢？这可以有两点理由；{用产生式系统结构求解问题的过程和人类求解问题时的思维过程很相象（下面要举例说明），因而可以用它来模拟人类求解问题时的思维过程{可以把产生式系统作为人工智能系统的基本结构单元或基本模式看待，就好像是积木世界中的积木块一样，因而研究产生式系统的基本问题就具有一般意义 人工智能中使用产生式的理由人工智能中使用产生式的理由  产生式规则的界定及内容产生式规则的界定及内容 产生式规则其实就是产生式系统的主体，是产生式系统知识表示的核心故人们常把产生式表示直接称为产生式规则，或简称规则这里所说的“规则” ，是指人们思维判断中的一种固定逻辑结构关系一般产生式的结构可表示为自然语言形式，事实上，在自然语言表达中，人们广泛使用的各种“原因—-结果”，“条件—结论”，“前提—操作”，“事实—进展”，“情况—行为”等结构，都可归结为产生式的知识表达形式。

  例如：例如： （1）天下雨，地上湿原因—结果”结构） （2）如果把冰加热到零摄氏度以上，冰就会融化为水 （“条件—结论”结构） （3）“夜来风雨声，花落知多少事实及其进展结构） （4）若能找到一根合适的杠杆，就能撬起那座大山前提—操作） （5）“才饮长江水，又食武昌鱼，”（事实及其进展结构） （6）刚才开机了，意味着发出了捕获目标图像的信号 （情况—行为）产生式规则的界定及内容产生式规则的界定及内容  基本形式：基本形式： A → BA → B 或者或者 IF A THEN BIF A THEN BA 是产生式的前提（前件），用于指出该产生式是 否可用的条件B 是一组结论或操作（后件），用于指出当前提 A所指示的条件满足时，应该得出的结论或应该执行的操作例：R: IF 动物会飞 AND 会下蛋 THEN 该动物是鸟产生式规则的界定及内容产生式规则的界定及内容  基本形式：基本形式： 〈〈前件前件〉〉→→〈〈后件后件〉〉 其中, 前件就是前提, 后件是结论或动作,前件和后件可以是由逻辑运算符AND、OR、NOT组成的表达式。

语义: 如果前提满足,则可得结论或者执行相应的动作, 即后件由前件来触发 所以, 前件是规则的执行条件, 后件是规则体 产生式规则的界定及内容产生式规则的界定及内容  产生式系统构成产生式系统构成组成三要素：{ 一个综合数据库 存放问题求解过程中当前信息的数据结构{ 一组产生式规则 描述相应领域内的知识有效的表达领域内的过程性的知识对知识进行合理的组织和管理{ 一个控制系统 选择规则库中与当前综合数据库相匹配的规则并执行，必要时进行冲突消解  产生式系统的基本结构产生式规则库综合数据库控制系统  产生式系统推理的基本过程产生式系统推理的基本过程推理机的一次推理过程  问题：设字符转换规则A∧B→CA∧C→DB∧C→GB∧E→FD→E已知：A，B求：F一个简单的例子一个简单的例子  一、综合数据库{x}，其中x为字符二、规则集 1，IF A∧B THEN C 2，IF A∧C THEN D 3，IF B∧C THEN G 4，IF B∧E THEN F 5，IF D THEN E一个简单的例子（续一个简单的例子（续1））  三、控制策略顺序排队四、初始条件{A，B}五、结束条件F∈{x}一个简单的例子（续一个简单的例子（续2））   在介绍求解过程之前，为了方便叙述，我们首先介绍两个术语。

1）可触发规则：当一个规则的前件被综合数据库中的数据满足时，该规则称为可触发规则 （2）被触发规则：从可触发规则中选择一个规则来执行，被执行的规则称为被触发规则该问题的求解过程，如下表所示   综合数据库可触发规则 被触发规则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 A∧B THEN C 2，IF A∧C THEN D3，IF B∧C THEN G 4，IF B∧E THEN F5，IF D THEN E求解过程求解过程   A、B是已知的条件，一开始就在综合数据库中此时只有规则1是可触发的由于只有一个可触发规则，所以选择规则1执行规则1的执行结果得到C，C被加入到综合数据库中由于有了C，使得规则2和规则3成为可触发规则（此时规则1的前件虽然也同样可以被满足，由于该规则已经被执行过，而且其当前的触发条件并没有改变，与他被执行时的条件是一样的，所以规则1不在可触发规则之列）此时可触发规则有两条，按照顺序排队策略，排在前面的规则优先执行，所以选择规则2为被触发规则。

规则2的执行结果产生了D，D被加入到综合数据库中依次类推，规则3、规则5和规则4先后被执行，最终产生了F从而F被求得，结束运行   （一）按推理方向分类 1.正向推理 2.逆向推理 3.双向推理 （二）按搜索策略分类 1.不可撤回方式 2.试探性方式 （1）回溯方式 （2）图搜索方式产生式系统的类型产生式系统的类型  　 从一组表示事实的谓词或命题出发，使用一组产生式规则，用以证明该谓词公式或命题是否成立　　一般策略：先提供一批事实（数据）到总数据库中系统利用这些事实与规则的前提相匹配，触发匹配成功的规则，把其结论作为新的事实添加到总数据库中继续上述过程，用更新过的总数据库的所有事实再与规则库中另一条规则匹配，用其结论再次修改总数据库的内容，直到没有可匹配的新规则，不再有新的事实加到总数据库中正向推理正向推理  {　步1 将初始事实/数据置入动态数据库{ 步2 用动态数据库中的事实/数据, 匹配/测试目标 条件, 若目标条件满足, 则推理成功, 结束 { 步3 用规则库中各规则的前提匹配动态数据库中的事实/数据, 将匹配成功的规则组成待用规则集。

{ 步4 若待用规则集为空, 则运行失败, 退出 { 步5 将待用规则集中各规则的结论加入动态数据库, 或者执行其动作, 转步2 正向推理算法：正向推理算法：   例　动物分类问题的产生式系统描述及其求解例　动物分类问题的产生式系统描述及其求解 r1：若某动物有奶, 则它是哺乳动物  r2： 若某动物有毛发, 则它是哺乳动物 r3： 若某动物有羽毛, 则它是鸟  r4： 若某动物会飞且生蛋, 则它是鸟 r5： 若某动物是哺乳动物且有爪且有犬齿且目盯前方, 则 它是食肉动物 r6： 若某动物是哺乳动物且吃肉, 则它是食肉动物 r7： 若某动物是哺乳动物且有蹄, 则它是有蹄动物 r8： 若某动物是有蹄动物且反刍食物, 则它是偶蹄动物 r9： 若某动物是食肉动物且黄褐色且有黑色条纹, 则它是老虎 r10：若某动物是食肉动物且黄褐色且有黑色斑点, 则它是金钱豹 r11：若某动物是有蹄动物且长腿且长脖子且黄褐色且有暗斑点, 则它是长颈鹿   r10：若某动物是食肉动物且黄褐色且有黑色斑点, 则它是金钱豹。

r11：若某动物是有蹄动物且长腿且长脖子且黄褐色且有暗斑点, 则 它是长颈鹿r12：若某动物是有蹄动物且白色且有黑色条纹, 则它是斑马 r13：若某动物是鸟且不会飞且长腿且长脖子且黑白色, 则它是驼鸟 r14：若某动物是鸟且不会飞且会游泳且黑白色, 则它是企鹅 r15：若某动物是鸟且善飞且不怕风浪, 则它是海燕  规则集形成的部分推理网络  再给出初始事实： f1：某动物有毛发f2：吃肉f3：黄褐色f4： 有黑色条纹 目标条件为： 该动物是什么？该系统的运行结果为： 该动物是老虎   从表示目标的谓词或命题出发，使用一组产生式规则证明事实谓词或命题成立，即首先提出一批假设目标，然后逐一验证这些假设　　一般策略：首先假设一个可能的目标，然后由产生式系统试图证明此假设目标是否在总数据库中若在总数据库中，则该假设目标成立；否则，若该假设为终叶（证据）节点，则询问用户若不是，则再假定另一个目标，即寻找结论部分包含该假设的那些规则，把它们的前提作为新的假设，并力图证明其成立这样反复进行推理，直到所有目标均获证明或者所有路径都得到测试为止。

逆向推理逆向推理   逆向推理算法：逆向推理算法：{ 步1 将初始事实/数据置入动态数据库, 将目标条件置入目标链{ 步2 若目标链为空,则推理成功,结束 { 步3 取出目标链中第一个目标, 用动态数据库中的事实/数据同其匹配, 若匹配成功, 转步2{ 步4 用规则集中的各规则的结论同该目标匹配，若匹配成功,则将第一个匹配成功且未用过的规则的前提作为新的目标,并取代原来的父目标而加入目标链, 转步3{　 步5 若该目标是初始目标, 则推理失败, 退出  步6 将该目标的父目标移回目标链, 取代该目标及其兄弟目标, 转步3   例例　对于上例中的产生式系统, 改为反向推理算法, 则得到下图所示的推理树 关于“老虎”的反向推理树   双向推理双向推理 　 双向推理的推理策略是同时从目标向事实推理和从事实向目标推理，并在推理过程中的某个步骤，实现事实与目标的匹配  （1）不可撤回方式 这种方式是利用问题给出的局部知识来决定如何选取规则，就是说根据当前可靠的局部知识选一条可应用规则并作用于当前综合数据库。

接着再根据新状态继续选取规则，搜索过程一直进行下去，不必考虑撤回用过的规则这是由于在搜索过程中如能有效利用局部知识，即使使用了一条不理想的规则，也不妨碍下一步选得另一条更合适的规则这样不撤消用过的规则，并不影响求到解，只是解序列中可能多了一些不必要的规则显然这种策略具有控制简单的优点，下面用登山问题来进一步说明这种方式的基本思想　　人们在登山过程中，目标是爬到峰顶，问题就是确定如何一步一步地朝着目标前进达到顶峰其实这就是一个"爬山"过程中寻求函数的极大值问题我们很容易想到利用高度随位置变化的函数H（P）来引导爬山，就可实现不可撤回的控制方式   2）试探式的产生式系统 即规则使用后，允许返回原来出发点重新选用其他规则可分为：（1）回溯法产生式系统 在规则使用后，记住原来的节点，若搜索遇到困难时可返回再选用其规则如有界深度优先搜索 先试用某一规则，如果以后发现不合适，退回另选一条规则新生成的状态前面出现过回溯条件确定从初态开始，用了若干规则仍未到达目标涉及两个问题： 对当前状态，再无可用规则 利用已有知识对规则排序，可减少回溯次数2）图搜索产生式系统 同时掌握若干规则序列的效果，从中寻找问题的答案。

为避免循环，通常采用树搜索，如广度优先搜索  四、产生式系统的程序实现（一）程序实现 1) 产生式规则的程序语言实现 2）规则库的程序实现 3）动态数据库的程序实现 4）推理机的程序实现（二） Prolog语言及其基本结构 1 ） Prolog语言 2 ） Prolog的基本结构  1) 产生式规则的程序语言实现产生式规则的程序语言实现 将规则的前提部分做成形如 　　　　 条件1 AND 条件2 AND … AND 条件n 或 条件1 OR 条件2 OR … OR 条件m 将规则结论部分做成形如 断言1/动作1 AND 断言2/动作2 AND … AND 断言k/动作k 或 断言1/动作1 OR 断言2/动作2 OR … OR 断言k/动作 一般地做成  条件1 AND 条件2 AND … AND 条件n→断言/动作（一）程序实现（一）程序实现   一种是先确定好规则的语言表示形式，再根据规则形式设计规则解释程序（推理机）；另一种是对已有的解释程序（推理机），设计规则表示形式（当然只能采用推理机所约定的规则形式） 在PROLOG程序中要表示产生式规则, 至少有两种形式：  (1) 用PROLOG的规则表示产生式规则。

 (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）推理机的程序实现   PrologProlog（Programming in Logic的缩写）是一种逻辑编程语言。

它建立在逻辑学的理论基础之上， 最初被运用于自然语言等研究领域Prolog是当代最有影响的人工智能语言之一，由于该语言很适合表达人的思维和推理规则，在自然语言理解、机器定理证明、专家系统等方面得到了广泛的应用，已经成为人工智能应用领域的强有力的开发语言 现在的Prolog语言有许多版本，但它们的核心部分都是一样的Prolog的基本语句仅有三种，即事实、规则和目标三种类型的语句，且都用谓词表示，因而程序逻辑性强，文法简捷，清晰易懂另一方面，Prolog是陈述性语言，一旦给它提交必要的事实和规则之后，Prolog就使用内部的演绎推理机制自动求解程序给定的目标，而不需要在程序中列出详细的求解步骤 （二）（二） Prolog语言及其基本结构语言及其基本结构   Prolog的规则恰好能直接表示产生式规则，Prolog的事实也恰好能表示产生式系统中的事实，Prolog的动态数据库也刚好可用来实现产生式系统中的动态数据库，程序的目标也就是产生式系统的运行目标，Prolog的翻译程序本身就是一个推理机 下面看一个例子 注：一个Turbo Prolog程序至少包括谓词段、子句段和目标段三项。

目标可以包含在程序中，也可以在程序运行时给出  １、事实 事实用来说明一个问题中已知的对象和它们之间的关系 在Prolog程序中，事实由谓词名及用括号括起来的 一个或几个对象组成谓词和对象可由用户自己定义 例如，谓词likes(bill，book). 是一个名为like的关系，表示对象bill和book之间有喜欢的关系２、规则 规则由几个互相有依赖性的简单句（谓词）组成，用来描述事实之间的依赖关系从形式上看，规则由左边表示结论的后件谓词和右边表示条件的前提谓词组成   例如，规则 bird(X):-animal(X),has(X,feather). 表示凡是动物并且有羽毛，那么它就是鸟３、目标（问题） 把事实和规则写进Prolog程序中后，就可以向Prolog询问有关问题的案，询问的问题就是程序运行的目标目标的结构与事实或规则相同，可以是一个简单的谓词，也可以是多个谓词的组合目标分内、外两种，内部目标写在程序中，外部目标在程序运行时由用户手工键入 例如问题 ?-student(john). 表示“john是学生吗？”  例1 谁是john的朋友？predicates /*谓词段，对要用的谓词名和参数进行说明*/likes(symbol, symbol)friend(symbol, symbol)clauses /*子句段，存放所有的事实和规则*/likes(bell,sports). /*前4行是事实*/likes(mary,music).likes(mary,sports).likes(jane,smith).friend(john,X):-likes(X,sports),likes(X,music). /*本行是规则*/当上述事实与规则输入计算机后，运行该程序，用户就可以进行询问，如输入目标：friend(john,X) 即询问john的朋友是谁,,这时计算机的运行结果为：X=mary （mary是john的朋友）  （一）产生式表示法的优点（二）产生式表示法的缺点产生式系统的特点产生式系统的特点  （1）自然性： “如果… ，则 …” 形式表示知识，直观、自然，便于推理，符合人的思维习惯。

2）模块性： 规则与推理机构相对独立；对规则库的维护方便；便于规则设计，便于问题求解3）有效性： 表达知识类型准确，全面，应用广 既可表示确定性知识，又可表示不确定性知识 既有利于表示启发式知识，又可方便地表示过 性知识4）清晰性： 规则格式固定，由前件与后件构成使人一看一目了然优点：  （1）效率不高： 求解过程是 “匹配-冲突消解-执行” 的过程，若规则库较大，易引起组合爆炸2）不能表示具有结构性的知识： 产生式适合于表示具有因果关系的过程性知识，不能表示具有结构关系的事物间的区别与联系局限性  Thanks for attention!。