人工智能06--产生式优秀PPT.ppt

表示方法概述干脆表示逻辑表示产生式规则表示法语义网络表示法框架表示法脚本方法过程表示混合型学问表示方法面对对象的表示方法表示方法产生式规则表示法美国数学家Post，1943年提出了一种计算形式体系里所运用的术语。主要是运用类似文法的规则，对符号串做替换运算。这就是最早的一个产生式系统。到了60年头，产生式系统成为认知心理学探讨人类心理活动中信息加工过程的基础，由此心理学家认为，人脑对学问的存储就是产生式形式。因此，用它来建立人类认知模型。到目前为止，产生式系统已发展成为人工智能系统中最典型最普遍的一种结构。产生式表示方法是专家系统的第一选择的学问表达方式。表示方法产生式规则表示法表示形式表示形式事实的表示：可看成是断言一个语言变量的事实的表示：可看成是断言一个语言变量的值或是多个语言变量间的关系的陈述句，语言变值或是多个语言变量间的关系的陈述句，语言变量的值或语言变量间的关系可以是一个词，不确量的值或语言变量间的关系可以是一个词，不确定是数字。定是数字。例例1：香蕉是黄色的。语言变量：香蕉是黄色的。语言变量香蕉，值香蕉，值黄色的黄色的 例例2：小李宠爱小莉。语言变量：小李宠爱小莉。语言变量小李、小小李、小莉，莉，关系值关系值宠爱宠爱 一般用三元组（对象，属性，值）或一般用三元组（对象，属性，值）或 （关系，对象（关系，对象1，对象，对象2）例：（例：（Li,Age,25）,(Friend,Li,Chang)表示方法产生式规则表示法产生式系统的基本特征：产生式系统的基本特征：一组规则，即产生式本身。一组规则，即产生式本身。每个规则分左边右边。每个规则分左边右边。如：天上下雨如：天上下雨 地上湿地上湿 中国的首都是北京中国的首都是北京一一般般左左边边表表示示状状况况，即即什什么么条条件件。发发生生时时产产生生式式被被调调用用。通通常常用用匹匹配配方方法法和和式式状状况况。匹匹配配成成功功时时，执执行行右右边边规定的动作。规定的动作。表示方法产生式规则表示法产生式系统的基本特征：产生式系统的基本特征：数据库数据库存存放放的的数数据据是是构构成成产产生生式式的的基基本本元元素素，又又是是产产生生式式作作用用的的对对象象。这这里里的的数数据据是是广广义义的的常常量量、变变量量、多多元元组组谓谓词词、表表、图图像像等等。往往往往事事实实或或断断言言学问元学问元 一个说明程序一个说明程序从从匹匹配配成成功功的的规规则则（可可能能不不止止一一个个）中选出一个加以执行。中选出一个加以执行。表示方法产生式规则表示法产生式系统基本结构产生式系统基本结构推理机推理机数据库数据库规则库规则库知识库知识库产生式系统结构图产生式系统结构图 表示方法产生式规则表示法产生式系统基本结构产生式系统基本结构工工作作存存储储器器(数数据据库库)：存存放放当当前前已已知知的的数数据据，包包括括推推理理过过程程中中形形成成的的中中间间结结论论。数数据据是是广广义义的的，可可以以是是常常量量、多多元元数数组组、谓词、表示结构等。谓词、表示结构等。产产生生式式规规则则：每每条条产产生生式式规规则则分分为为左左右右两两个个部部分分。左左部部表表示示激激活活该该产产生生式式规规则则的的条条件件，右右部部表表示示调调用用该该产产生生式式规规则则后后所所作作的的动动作作。条条件件是是一一组组困困难难的的模模式式，规规则则之之间间的的限限制制也也不不是是语语句句的的传传递递，而而且且满满足足条条件件的的规规则则被被激激活活但但不不确确定定立立刻刻执执行行，取取决决于于产产生生式式系系统统的的冲冲突突消消解解策策略。略。.表示方法产生式规则表示法产生式系统基本结构产生式系统基本结构.规则说明程序规则说明程序匹配器：推断规则条件是否成立。匹配器：推断规则条件是否成立。冲突消解器：选择可调用的规则。冲突消解器：选择可调用的规则。说说明明器器：执执行行规规则则的的动动作作。并并且且在在满满足足结结束束条条件件时时终终止止产产生生式式系系统统运运行。行。表示方法产生式规则表示法推理方法：推理方法：正向、正向、反向、反向、双向，双向，与或树与或树表示方法产生式规则表示法正向推理方法：正向推理方法：从从已已知知事事实实动动身身，逐逐步步推推导导出出最最终终结结论。论。其推理过程大致是：其推理过程大致是：用用工工作作存存储储器器中中的的事事实实与与产产生生式式规规则则的的前提条件进行匹配。前提条件进行匹配。按按冲冲突突消消解解策策略略从从匹匹配配的的规规则则中中选选择择一一条规则。条规则。执执行行选选中中规规则则的的动动作作（依依次次）。修修改改工工作存储器。作存储器。用用更更新新后后的的工工作作存存储储器器，重重复复上上述述工工作作，直直到到得得出出结结论论或或工工作作存存储储器器不不再再发发生生变变更为止。更为止。表示方法产生式规则表示法反向推理方法：反向推理方法：首首先先提提出出假假设设，然然后后验验证证这这些些假假设设的的真真假假性性，找找到到假假设设成成立立的的全全部部证证据据或或事事实。实。其推理过程大致是：其推理过程大致是：看看假假设设是是否否存存在在于于工工作作存存储储器器中中，若若在在，则假设成立，推理结束。则假设成立，推理结束。找出结论与此假设匹配的规则。找出结论与此假设匹配的规则。按按冲冲突突消消解解策策略略从从匹匹配配的的规规则则实实例例中中选选择一条规则。择一条规则。将将选选中中的的规规则则的的前前提提条条件件作作为为新新的的假假设设，重重复复上上述述工工作作，直直到到假假设设的的真真假假性性被被验验证或不存在激活的规则。证或不存在激活的规则。表示方法产生式规则表示法双向推理方法：双向推理方法：即即自自顶顶向向下下、又又自自底底向向上上作作双双向向推推理理，直直至至某某个个中中间间界界面面上上两两方方向向结果相符便成功结束。结果相符便成功结束。该该方方法法较较正正向向或或反反向向推推理理所所形形成成的推理网络小，从而推理效果更高。的推理网络小，从而推理效果更高。表示方法产生式规则表示法推理方法的选择推理方法的选择推推理理方方法法的的选选择择取取决决于于推推理理的的目目标和搜寻空间的形态。标和搜寻空间的形态。假假如如目目标标是是从从一一组组给给定定事事实实动动身身，找找出出全全部部可可能能的的结结论论，那那么么，通通常常运用正向推理。运用正向推理。假假如如目目标标是是证证明明或或否否定定某某一一特特定定结结论论，那那么么，通通常常运运用用反反向向推推理理，否否则则，从从一一组组初初始始事事实实动动身身盲盲目目地地正正向向推推理理，可可能能得得出出很很多多和和所所要要证证明明的结论无关的结论。的结论无关的结论。表示方法产生式规则表示法特点特点用产生式系统结构求解问题的过程和人类求解问题时的用产生式系统结构求解问题的过程和人类求解问题时的思维很相像。因而可以用它来模拟人类求解问题的思维思维很相像。因而可以用它来模拟人类求解问题的思维过程。过程。可以把产生式系统作为人工智能系统的基本结构单元或可以把产生式系统作为人工智能系统的基本结构单元或基本模型看待。就似乎是积木世界中的积木块一样。因基本模型看待。就似乎是积木世界中的积木块一样。因而探讨产生式系统的基本问题就具有一般意义。而探讨产生式系统的基本问题就具有一般意义。表示的格式固定、形式单一、规则间相互独立表示的格式固定、形式单一、规则间相互独立,所以建所以建立简洁；推理方式单纯、学问库与推理机分别，修改便立简洁；推理方式单纯、学问库与推理机分别，修改便利、简洁理解。利、简洁理解。表示方法产生式规则表示法优点优点模块性。模块性。规则与规则之间相互独立规则与规则之间相互独立灵敏性。灵敏性。学问库易于增加、修改、删除学问库易于增加、修改、删除自然性。自然性。便利地表示专家的启发性学问与便利地表示专家的启发性学问与阅历阅历透亮性。透亮性。易于保留动作所产生的变更、轨易于保留动作所产生的变更、轨迹迹产生式系统的基本组成组成三要素：一个综合数据库存放信息一组产生式规则学问一个限制系统规则的说明或执行程序 （限制策略）（推理引擎）产生式系统的基本过程过程PROFUCTION1，DATA初始数据库2，until DATA满足结束条件，do3，4，在规则集中选择一条可应用于DATA 的规则R5，DATA R应用到DATA得到的结果6，一个简洁的例子问题：设字符转换规则ABCACDBCGBEFDE已知：A，B求：F一个简洁的例子（续1）一、综合数据库x，其中x为字符二、规则集1，IF AB THEN C2，IF AC THEN D3，IF BC THEN G4，IF BE THEN F5，IF D THEN E一个简洁的例子（续2）三、限制策略依次排队四、初始条件A，B五、结束条件Fx求解过程数据库可触发规则被触发规则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 4，IF BE THEN F2，IF AC THEN D 5，IF D THEN E 3，IF BC THEN G例例1八数码游戏八数码游戏（1）综合数据库）综合数据库 用二维数组来表示 Sij ：1=I,j=2 then Si j =Si j-1,Si j-1=0 (Si j 向左)r2:if i=2 then Si j =Si-1 j,Si-1 j=0 (Si j 向上)r3:if j+1=3 then Si j =Si j+1,Si j+1=0 (Si j 向右)r4:if i+1=3 then Si j =Si+1 j,Si+1 j=0 (Si j 向下)2 8 31 6 4751 2 3847 6 5（3）搜寻策略）搜寻策略 略略例例2传教士与野人问题（传教士与野人问题（M-C问题）问题）例1：传教士与野人问题（M-C问题）问题：N个传教士，N个野人，一条船，可同时乘坐k个人，要求在任何时刻，在河的两岸，传教士人数不能少于野人的人数。问：如何过河。以N=3，k=2为例求解。M-C问题（续问题（续1）左岸 右岸 L R L R m 3 0 m 0 3 c 3 0 c 0 3 B 1 0 B 0 1M-C问题（续问题（续2）1，综合数据库，综合数据库 （m,c,b)其中：0m,c3,b 0,1 初始状态 （3，3，1）目标状态（结束状态）（0，0，0）2，规则集，规则集IF(m,c,1)THEN(m-1,c,0)IF(m,c,1)THEN(m,c-1,0)IF(m,c,1)THEN(m-1,c-1,0)IF(m,c,1)THEN(m-2,c,0)IF(m,c,1)THEN(m,c-2,0)IF(m,c,0)THEN(m+1,c,1)IF(m,c,0)THEN(m,c+1,1)IF(m,c,0)THEN(m+1,c+1,1)IF(m,c,0)THEN(m+2,c,1)IF(m,c,0)THEN(m,c+2,1)3，限制策略：（略），限制策略：（略）例例3猴子摘香蕉问题猴子摘香蕉问题1，综合数据库，综合数据库（M,B,Box,On,H）M：猴子的位置：猴子的位置B：香蕉的位置：香蕉的位置Box：箱子的位置：箱子的位置On=0：猴子在地板上：猴子在地板上On=1：猴子在箱子上：猴子在箱子上H=0：猴子没有抓到香蕉：猴子没有抓到香蕉H=1：猴子抓到了香蕉：猴子抓到了香蕉 初始状态初始状态 （c,a,b,0,0）结束状态结束状态 （x1,x2,x3,x4,1）其中其中x1x4为变量。为变量。abc2，规则集，规则集 r1:IF (x,y,z,0,0)THEN (w,y,z,0,0)r2:IF (x,y,x,0,0)THEN (z,y,z,0,0)r3:IF (x,y,x,0,0)THEN (x,y,x,1,0)r4:IF (x,y,x,1,0)THEN (x,y,x,0,0)r5:IF (x,x,x,1,0)THEN (x,x,x,1,1)其中其中x,y,z,w为变量为变量1.4 产生式系统的特点数据驱动学问的无序性限制系统与问题无关表示方法产生式规则表示法缺点：学问库维护难。效率低。为了模块一样性。理解难。由于规则一样性彼此之间不能调用。应用实例：用于化工工业测定分子结构的DENDRAL用于诊断脑膜炎和血液病毒感染的MYCIN估计矿藏的PROSPECTORP48(1.2)对量水问题给出产生式系统描述，并给出一个解空间。对量水问题给出产生式系统描述，并给出一个解空间。有有两两个个无无刻刻度度标标记记的的水水壶壶，分分别别可可装装5 5升升和和2 2升升水水。设设另另有有一一个个水水缸缸，可可用用来来向向水水壶壶灌灌水水或或倒倒出出水水，两两个个水水壶壶之之间间，水水也也可可以以相相互互倾倾灌灌。已已知知起起先先时时，5 5升升壶壶为为满满壶壶，2 2升升壶壶为为空空壶壶，问问如如何何通通过过倒倒水水或或灌灌水水操操作作，使使能能在在2 2升升的的壶壶中中量量出出1 1升升的的水来。水来。1，综合数据库，综合数据库(x ,y)其中：0 x5,0y2初始状态（5，0）目标状态（结束状态）（n，1）0n52，规则集，规则集 当前状态为：当前状态为：(x ,y)1.IF x5 THEN (5,y)2.IF y0 THEN(x-d,y)(d0 THEN(x,y-d)(d0 THEN(0,y)6.IF y0 THEN(x,0)7.IF(x+y=5)(y0)THEN(5,y-(5-x)8.IF(x+y=2)(x0)THEN(x-(2-y),2)9.IF(x+y0)THEN(x+y,0)10.IF(x+y0)THEN(0,x+y)2，规则集，规则集 当前状态为：当前状态为：(x ,y)1.IF x5 THEN (5,y)2.IF y0 THEN(x-d,y)(d0 THEN(x,y-d)(d0 THEN(0,y)6.IF y0 THEN(x,0)7.IF(x+y=5)(y0)THEN(5,y-(5-x)8.IF(x+y=2)(x0)THEN(x-(2-y),2)9.IF(x+y0)THEN(x+y,0)10.IF(x+y0)THEN(0,x+y)3,搜寻策略（略）搜寻策略（略）解空间：解空间：应用的规则应用的规则（5，0）规则规则 8（3，2）规则规则 6（3，0）规则规则 8 （1，2）规则规则 6（1，0）规则规则 10（0，1）P49(1.4)对三枚三枚钱币问题给出出产生式系生式系统描述及状描述及状态空空间图。设有有三三枚枚钱币，其其排排列列处在在“正正、正正、反反”的的状状态，现在在允允许每每次次翻翻动其其中中随随意意一一个个钱币，问在在只只许操操作作三三次次的的状状况况下下，如如何何翻翻动钱币使使其其变成成“正正、正正、正正”状状态。1，综合数据库，综合数据库(x ,y,z)其中：x 0,1 y 0,1 z 0,1初始状态（1，1,0）目标状态（结束状态）（1，1,1）2，规则集，规则集 当前状态为：当前状态为：(x ,y,z)1.IF(x ,y,z)THEN(x ,y,z)2.IF(x ,y,z)THEN(x ,y,z)3.IF(x ,y,z)THEN(x ,y,z)2，规则集，规则集 当前状态为：当前状态为：(x ,y,z)1.IF(x ,y,z)THEN(x ,y,z)2.IF(x ,y,z)THEN(x ,y,z)3.IF(x ,y,z)THEN(x ,y,z)3,搜寻策略（略）搜寻策略（略）(1,1,0)(1,1,1)(1,0,0)32(0,1,0)1(1,0,1)3(0,0,0)1(0,1,1)3(0,0,1)1(1,1,1)2(1,1,1)1