基于产生式规则的推理实用教案

1、主要(zhyo)内容一 、产生(chnshng)式规则概述二、 产生(chnshng)式系统p 产生式系统构成p 产生式系统的类型(lixng)p 产生式系统的程序实现p 产生式系统的特点第1页/共46页第一页，共47页。p产生式规则的产生和发展p人工智能中使用产生式的理由(lyu)p产生式规则的界定及内容产生式规则(guz)概述第2页/共46页第二页，共47页。 “产生式” 1943 年美国数学家 Post 首先在一种计算形式体系中提出的术语。 20世纪70年代，Newell和Simon等学者在对人类认知模型研究中，开发了基于规则的产生式系统等。从那时开始，产生式系统成为(chngwi)专家

2、系统的最基本的结构。从此，产生知识表示在人工智能中得到了广泛的应用。 产生式系统在形式上很简单，但在一定意义上模仿了人类思考的过程。产生式规则(guz)的产生和发展第3页/共46页第三页，共47页。 为什么要采用产生式系统(xtng)作为人工智能系统(xtng)的主要结构呢？这可以有两点理由；用产生式系统(xtng)结构求解问题的过程和人类求解问题时的思维过程很相象（下面要举例说明），因而可以用它来模拟人类求解问题时的思维过程。可以把产生式系统(xtng)作为人工智能系统(xtng)的基本结构单元或基本模式看待，就好像是积木世界中的积木块一样，因而研究产生式系统(xtng)的基本问题就具有一般

3、意义。 人工智能中使用(shyng)产生式的理由第4页/共46页第四页，共47页。产生式规则的界定(ji dn)及内容 产生式规则其实就是产生式系统的主体，是产生式系统知识表示的核心。故人们常把产生式表示直接称为产生式规则，或简称规则。这里所说的“规则” ” ，是指人们思维判断中的一种固定逻辑结构关系。一般产生式的结构可表示为自然语言形式，事实上，在自然语言表达中，人们广泛使用的各种“原因-结果”，“条件结论”，“前提(qint)(qint)操作”，“事实进展”，“情况行为”等结构，都可归结为产生式的知识表达形式。第5页/共46页第五页，共47页。例如例如(lr)(lr)： （1 1）天下雨，

4、地上湿。（）天下雨，地上湿。（“原因原因结果结果”结构）结构） （2 2）如果把冰加热到零摄氏度以上，冰就会融化为水。）如果把冰加热到零摄氏度以上，冰就会融化为水。 （“条件条件结论结论”结构）结构） （3 3）“夜来风雨声，花落知多少。夜来风雨声，花落知多少。”（事实及其进展结构）（事实及其进展结构） （4 4）若能找到一根合适的杠杆，就能撬起那座大山。（前提）若能找到一根合适的杠杆，就能撬起那座大山。（前提操作）操作） （5 5）“才饮长江水，又食武昌鱼，才饮长江水，又食武昌鱼，”（事实及其进展结构）（事实及其进展结构） （6 6）刚才开机了，意味着发出了捕获目标图像的信号。）刚才开机了，

5、意味着发出了捕获目标图像的信号。 （情（情况况行为）行为）产生(chnshng)式规则的界定及内容第6页/共46页第六页，共47页。基本形式：基本形式： A B A B 或者或者 IF A THEN B IF A THEN BA A 是产生式的前提（前件），用于指出该产生式是是产生式的前提（前件），用于指出该产生式是 否可用的条件否可用的条件B B 是一组结论或操作（后件），用于指出当前提是一组结论或操作（后件），用于指出当前提 A A所指所指示的条件满足时，应该得出示的条件满足时，应该得出(d ch)(d ch)的结论或应该的结论或应该执行的操作执行的操作例：例：R: IF R: IF 动物

6、会飞动物会飞 AND AND 会下蛋会下蛋 THEN THEN 该动物是鸟该动物是鸟产生(chnshng)式规则的界定及内容第7页/共46页第七页，共47页。基本形式：基本形式： 前件前件后件后件 其中其中, , 前件就是前提前件就是前提, , 后件是结论或动作后件是结论或动作, ,前件和后前件和后件可以是由逻辑件可以是由逻辑(lu j)(lu j)运算符运算符ANDAND、OROR、NOTNOT组成组成的表达式。的表达式。 语义语义: : 如果前提满足如果前提满足, ,则可得结论或者执行相应则可得结论或者执行相应的动作的动作, , 即后件由前件来触发。即后件由前件来触发。 所以所以, , 前

7、件是规则前件是规则的执行条件的执行条件, , 后件是规则体。后件是规则体。 产生式规则的界定(ji dn)及内容第8页/共46页第八页，共47页。产生式系统构成(guchng)组成三要素： 一个综合(zngh)数据库 存放问题求解过程中当前信息的数据结构。 一组产生式规则 描述相应领域内的知识。有效的表达领域内的过程性的知识。对知识进行合理的组织和管理。 一个控制系统 选择规则库中与当前综合(zngh)数据库相匹配的规则并执行，必要时进行冲突消解。第9页/共46页第九页，共47页。产生式系统的基本(jbn)结构产生式规则库综合数据库控制系统第10页/共46页第十页，共47页。产生式系统推理的基

8、本(jbn)过程推理(tul)机的一次推理(tul)过程第11页/共46页第十一页，共47页。问题(wnt)：设字符转换规则ABCACDBCGBEFDE已知：A，B求：F一个简单(jindn)的例子第12页/共46页第十二页，共47页。一、综合(zngh)数据库x，其中x为字符二、规则集 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一个(y )简单的例子（续1）第13页/共46页第十三页，共47页。三、控制策略顺序排队四、初始条件A，B五、结束( jish)条件Fx一个(y )简单的例子（续2

9、）第14页/共46页第十四页，共47页。 在介绍求解过程之前，为了方便叙述，我们首先介绍两个术语。（1）可触发规则(guz)：当一个规则(guz)的前件被综合数据库中的数据满足时，该规则(guz)称为可触发规则(guz)。 （2）被触发规则(guz)：从可触发规则(guz)中选择一个规则(guz)来执行，被执行的规则(guz)称为被触发规则(guz)。该问题的求解过程，如下表所示。 第15页/共46页第十五页，共47页。综合数据库可触发规则 被触发规则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

10、）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求解(qi ji)过程第16页/共46页第十六页，共47页。 A、B是已知的条件，一开始就在综合数据库中。此时只有规则1是可触发的。由于只有一个可触发规则，所以选择规则1执行。规则1的执行结果得到C，C被加入(jir)到综合数据库中。由于有了C，使得规则2和规则3成为可触发规则（此时规则1的前件虽然也同样可以被满足，由于该规则已经被执行过，而且其当前的触发条件并没有改变，与他被执行时的条件是一样的，所以规则1不在可触发规则之列

11、）。此时可触发规则有两条，按照顺序排队策略，排在前面的规则优先执行，所以选择规则2为被触发规则。规则2的执行结果产生了D，D被加入(jir)到综合数据库中。依次类推，规则3、规则5和规则4先后被执行，最终产生了F。从而F被求得，结束运行。第17页/共46页第十七页，共47页。 （一）按推理方向分类 1.正向推理 2.逆向推理 3.双向推理 （二）按搜索策略分类 1.不可撤回(chhu)方式 2.试探性方式 （1）回溯方式 （2）图搜索方式产生式系统的类型(lixng)第18页/共46页第十八页，共47页。 从一组表示事实的谓词或命题出发，使用一组产生式规则，用以证明该谓词公式或命题是否成立。一

12、般策略：先提供一批事实（数据）到总数据库中。系统利用这些事实与规则的前提相匹配(ppi)，触发匹配(ppi)成功的规则，把其结论作为新的事实添加到总数据库中。继续上述过程，用更新过的总数据库的所有事实再与规则库中另一条规则匹配(ppi)，用其结论再次修改总数据库的内容，直到没有可匹配(ppi)的新规则，不再有新的事实加到总数据库中。正向(zhn xin)推理第19页/共46页第十九页，共47页。步1 将初始事实/数据置入动态数据库。 步2 用动态数据库中的事实/数据, 匹配/测试目标 条件, 若目标条件满足, 则推理成功, 结束。 步3 用规则库中各规则的前提匹配动态数据库中的事实/数据, 将

13、匹配成功的规则组成待用规则集。 步4 若待用规则集为空, 则运行失败, 退出。 步5 将待用规则集中各规则的结论(jiln)加入动态数据库, 或者执行其动作, 转步2。 正向(zhn xin)推理算法：第20页/共46页第二十页，共47页。 例动物分类问题的产生式系统描述例动物分类问题的产生式系统描述(mio sh)(mio sh)及其求解。及其求解。 r1 r1：若某动物有奶：若某动物有奶, , 则它是哺乳动物。则它是哺乳动物。 r2 r2： 若某动物有毛发若某动物有毛发, , 则它是哺乳动物。则它是哺乳动物。 r3 r3： 若某动物有羽毛若某动物有羽毛, , 则它是鸟。则它是鸟。 r4 r

14、4： 若某动物会飞且生蛋若某动物会飞且生蛋, , 则它是鸟。则它是鸟。 r5 r5： 若某动物是哺乳动物且有爪且有犬齿且目盯前方若某动物是哺乳动物且有爪且有犬齿且目盯前方, , 则则 它是食肉动物。它是食肉动物。 r6 r6： 若某动物是哺乳动物且吃肉若某动物是哺乳动物且吃肉, , 则它是食肉动物。则它是食肉动物。 r7 r7： 若某动物是哺乳动物且有蹄若某动物是哺乳动物且有蹄, , 则它是有蹄动物。则它是有蹄动物。 r8 r8： 若某动物是有蹄动物且反刍食物若某动物是有蹄动物且反刍食物, , 则它是偶蹄动物。则它是偶蹄动物。 r9 r9： 若某动物是食肉动物且黄褐色且有黑色条纹若某动物是食肉

15、动物且黄褐色且有黑色条纹, , 则它是老虎。则它是老虎。 r10 r10：若某动物是食肉动物且黄褐色且有黑色斑点：若某动物是食肉动物且黄褐色且有黑色斑点, , 则它是金钱豹。则它是金钱豹。 r11 r11：若某动物是有蹄动物且长腿且长脖子且黄褐色且有暗斑点：若某动物是有蹄动物且长腿且长脖子且黄褐色且有暗斑点, , 则它是长颈鹿。则它是长颈鹿。 第21页/共46页第二十一页，共47页。r10：若某动物是食肉动物且黄褐色且有黑色斑点, 则它是金钱豹。 r11：若某动物是有蹄动物且长腿且长脖子且黄褐色且有暗斑点, 则 它是长颈鹿。r12：若某动物是有蹄动物且白色且有黑色条纹, 则它是斑马。 r13：

16、若某动物是鸟且不会飞且长腿且长脖子且黑白色, 则它是驼鸟(tu nio)。 r14：若某动物是鸟且不会飞且会游泳且黑白色, 则它是企鹅。 r15：若某动物是鸟且善飞且不怕风浪, 则它是海燕。第22页/共46页第二十二页，共47页。规则(guz)集形成的部分推理网络第23页/共46页第二十三页，共47页。再给出初始事实： f1：某动物有毛发。f2：吃肉。f3：黄褐色。f4： 有黑色条纹。 目标条件(tiojin)为： 该动物是什么？该系统的运行结果为： 该动物是老虎。第24页/共46页第二十四页，共47页。 从表示目标的谓词或命题出发，使用一组产生式规则证明事实谓词或命题成立，即首先提出一批假设

17、目标，然后逐一验证(ynzhng)这些假设。一般策略：首先假设一个可能的目标，然后由产生式系统试图证明此假设目标是否在总数据库中。若在总数据库中，则该假设目标成立；否则，若该假设为终叶（证据）节点，则询问用户。若不是，则再假定另一个目标，即寻找结论部分包含该假设的那些规则，把它们的前提作为新的假设，并力图证明其成立。这样反复进行推理，直到所有目标均获证明或者所有路径都得到测试为止。逆向(n xin)推理 第25页/共46页第二十五页，共47页。逆向推理(tul)(tul)算法： 步1 将初始事实/数据置入动态数据库, 将目标条件置入目标链。 步2 若目标链为空,则推理(tul)成功,结束。 步

18、3 取出目标链中第一个目标, 用动态数据库中的事实/数据同其匹配, 若匹配成功, 转步2。 步4 用规则集中的各规则的结论同该目标匹配，若匹配成功,则将第一个匹配成功且未用过的规则的前提作为新的目标,并取代原来的父目标而加入目标链, 转步3。 步5 若该目标是初始目标, 则推理(tul)失败, 退出。 步6 将该目标的父目标移回目标链, 取代该目标及其兄弟目标, 转步3。 第26页/共46页第二十六页，共47页。例对于上例中的产生式系统, 改为反向推理(tul)算法, 则得到下图所示的推理(tul)树。 关于“老虎(loh)”的反向推理树 第27页/共46页第二十七页，共47页。双向推理 双向

19、推理的推理策略(cl)是同时从目标向事实推理和从事实向目标推理，并在推理过程中的某个步骤，实现事实与目标的匹配。第28页/共46页第二十八页，共47页。（1）不可撤回方式 这种方式是利用问题给出的局部知识来决定如何选取规则，就是说根据当前可靠的局部知识选一条可应用规则并作用(zuyng)于当前综合数据库。接着再根据新状态继续选取规则，搜索过程一直进行下去，不必考虑撤回用过的规则。这是由于在搜索过程中如能有效利用局部知识，即使使用了一条不理想的规则，也不妨碍下一步选得另一条更合适的规则。这样不撤消用过的规则，并不影响求到解，只是解序列中可能多了一些不必要的规则。显然这种策略具有控制简单的优点，下

20、面用登山问题来进一步说明这种方式的基本思想。人们在登山过程中，目标是爬到峰顶，问题就是确定如何一步一步地朝着目标前进达到顶峰。其实这就是一个爬山过程中寻求函数的极大值问题。我们很容易想到利用高度随位置变化的函数H（P）来引导爬山，就可实现不可撤回的控制方式。 第29页/共46页第二十九页，共47页。2）试探式的产生式系统 即规则使用后，允许返回原来出发点重新选用其他规则。可分为：（1）回溯法产生式系统 在规则使用后，记住原来的节点，若搜索遇到困难时可返回再选用其规则。如有界深度优先搜索。 先试用某一规则，如果以后发现不合适，退回另选一条(y tio)规则。新生成的状态前面出现过回溯条件确定从初

21、态开始，用了若干规则仍未到达目标涉及两个问题： 对当前状态，再无可用规则。 利用已有知识对规则排序，可减少回溯次数。（2）图搜索产生式系统 同时掌握若干规则序列的效果，从中寻找问题的答案。为避免循环，通常采用树搜索，如广度优先搜索。第30页/共46页第三十页，共47页。四、产生式系统的程序实现（一）程序实现 1) 产生式规则的程序语言(yyn)实现 2）规则库的程序实现 3）动态数据库的程序实现 4）推理机的程序实现（二） Prolog语言(yyn)及其基本结构 1 ） Prolog语言(yyn) 2 ） Prolog的基本结构第31页/共46页第三十一页，共47页。1) 产生(chnshng

22、)式规则的程序语言实现 将规则的前提部分做成形如 条件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断言/动作（一）程序实现第32页/共46页第三十二页，共47页。 一种(y zhn)是先确定好规则的语言表示形式，再根据规则形式设计规则解释程序（推理机）；另一种(y zhn)是对已有的解释程序（推理机），设计规则表示形式（当然只能采

23、用推理机所约定的规则形式） 在PROLOG程序中要表示产生式规则, 至少有两种形式： (1) 用PROLOG的规则表示产生式规则。 (2) 用PROLOG的事实表示产生式规则。第33页/共46页第三十三页，共47页。例把上述动物分类系统中的产生式规则用例把上述动物分类系统中的产生式规则用PROLOGPROLOG的规则可表示如下的规则可表示如下(rxi)(rxi)： animal_is( animal_is(老虎老虎):-it_is():-it_is(食肉动物食肉动物),), fact( fact(黄褐色黄褐色),), fact( fact(有黑色条纹有黑色条纹).). it_is( it_is

24、(食肉动物食肉动物):-it_is1():-it_is1(哺乳动物哺乳动物),), fact( fact(有爪有爪),), fact( fact(有犬齿有犬齿),), fact( fact(目盯前方目盯前方). ). it_is( it_is(食肉动物食肉动物):-it_is1():-it_is1(哺乳动物哺乳动物),), fact(fact(吃肉吃肉).). it_is1( it_is1(哺乳动物哺乳动物):-fact():-fact(有奶有奶).). it_is1( it_is1(哺乳动物哺乳动物):-fact():-fact(有毛发有毛发).).第34页/共46页第三十四页，共47页。也

25、可以将上面的规则表示成如下的形式:rule(“食肉动物”, “黄褐色”, “有黑色条纹” , “老虎”).rule(“哺乳动物(brdngw)”, “有爪”, “有犬齿”, “目盯 前方” , “食肉动物”).rule(“哺乳动物(brdngw)”, “吃肉” , “食肉动物”rule(“有奶” , “哺乳动物(brdngw)”).rule(“有毛发”, “哺乳动物(brdngw)”). 第35页/共46页第三十五页，共47页。2）规则(guz)库的程序实现3）动态数据库的程序实现4）推理机的程序实现第36页/共46页第三十六页，共47页。 Prolog（Programming in Logi

26、c的缩写）是一种逻辑编程语言。它建立在逻辑学的理论基础之上， 最初被运用于自然语言等研究领域。Prolog是当代最有影响的人工智能语言之一，由于该语言很适合表达人的思维和推理规则，在自然语言理解、机器定理证明、专家系统等方面得到了广泛的应用，已经成为人工智能应用领域的强有力的开发语言。 现在的Prolog语言有许多版本，但它们的核心部分都是一样的。Prolog的基本语句仅有三种，即事实、规则和目标三种类型的语句，且都用谓词表示，因而程序逻辑性强，文法(wnf)简捷，清晰易懂。另一方面，Prolog是陈述性语言，一旦给它提交必要的事实和规则之后，Prolog就使用内部的演绎推理机制自动求解程序给

27、定的目标，而不需要在程序中列出详细的求解步骤。 （二） Prolog语言(yyn)及其基本结构第37页/共46页第三十七页，共47页。 Prolog的规则恰好能直接表示产生式规则，Prolog的事实也恰好能表示产生式系统中的事实，Prolog的动态数据库也刚好可用来实现产生式系统中的动态数据库，程序的目标(mbio)也就是产生式系统的运行目标(mbio)，Prolog的翻译程序本身就是一个推理机。 下面看一个例子 注：一个Turbo Prolog程序至少包括谓词段、子句段和目标(mbio)段三项。目标(mbio)可以包含在程序中，也可以在程序运行时给出。第38页/共46页第三十八页，共47页。

28、、事实 事实用来说明一个问题中已知的对象和它们之间的关系。 在Prolog程序中，事实由谓词名及用括号括起来的 一个或几个(j )对象组成。谓词和对象可由用户自己定义。 例如，谓词likes(bill，book). 是一个名为like的关系，表示对象bill和book之间有喜欢的关系。、规则 规则由几个(j )互相有依赖性的简单句（谓词）组成，用来描述事实之间的依赖关系。从形式上看，规则由左边表示结论的后件谓词和右边表示条件的前提谓词组成。 第39页/共46页第三十九页，共47页。例如，规则 bird(X):-animal(X),has(X,feather). 表示凡是动物并且有羽毛，那么它就

29、是鸟。、目标（问题） 把事实和规则写进Prolog程序中后，就可以向Prolog询问有关问题的案，询问的问题就是程序运行的目标。目标的结构与事实或规则相同，可以是一个简单的谓词，也可以是多个谓词的组合。目标分内、外两种，内部(nib)目标写在程序中，外部目标在程序运行时由用户手工键入。 例如问题 ?-student(john). 表示“john是学生吗？”第40页/共46页第四十页，共47页。例1 谁是john的朋友？predicates /*谓词段，对要用的谓词名和参数进行说明*/likes(symbol, symbol)friend(symbol, symbol)clauses /*子句段，存放所有的事实和规则*/lik