第5章产生式表示与专家系统20121210.ppt

《第5章产生式表示与专家系统20121210.ppt》由会员分享，可在线阅读，更多相关《第5章产生式表示与专家系统20121210.ppt（62页珍藏版）》请在三一文库上搜索。

1、2019/6/20,1,第5章 产生式表示与专家系统,2019/6/20,2,内容,5.1 产生式与产生式系统 5.2 专家系统概述 5.3 专家系统结构及工作过程 5.4 专家系统的开发 5.5 专家系统的实例 5.6 新型专家系统,2019/6/20,3,5.1 产生式与产生式系统（1）,产生式 1943年美国数学家Post，最早提出产生式系统并把它作为计算手段。 同一时期，Chomsky在研究自然语言结构时，提出了文法分层的概念，并提出了文法的重写规则，即语言生成规则，语言生成规则实际是特殊的产生式。 1960年，Backus提出了著名的BNF，用以描述计算机语言的文法。后来发现，BNF

2、范式实际上就是Chomsky的上下文无关文法。,2019/6/20,4,5.1 产生式与产生式系统（2）,5.1.1 产生式表示 5.1.2 产生式系统结构 5.1.3 产生式系统工作过程,2019/6/20,5,5.1.1产生式表示（1）,产生式的一般形式为： 前件后件（情况行为） 前件是前提，规则的执行条件。后件是结论或动作，规则体。 产生式规则的语义：如果前提满足，则可得结论或者执行相应的动作，即后件由前件触发。 产生式也可以表示前面讨论过的各种操作 在形式语言中的文法规则也称为产生式 在推理系统中产生式的前件就是前提，后件就是结论，所以，产生式又是一个前提-结论对。,2019/6/20

3、,6,产生式规则的例子： （1）如果电视机声音太大引起邻居抱怨，则将音量调小一点儿。 （2）如果申请人有良好的金融声誉和良好的资产负债表，那么贷款 应该被批准。 （3）IF 当前环境分配设备给总线组件，并且 有一个未分配的双端口磁盘驱动器，并且 已知所需控制器类别，并且 每个控制器没有任何设备分配给它，并且 这些控制器能够支持的设备数目已知 THEN 分配磁盘驱动器给每一个控制器，并且 记下相关的控制器对，其中每一个控制器支持一个驱动器 第（3）条规则用在配置DEC VAX计算机系统的XCON/R1专家系统中。,2019/6/20,7,5.1.1产生式表示（2）,例5.1 三个聪明人问题。古代

4、有个国王想知道他的三个大臣中谁最聪明，就在他们每个人前额上都画了一个点，他们都能看到别人点的颜色，但看不到自己点的颜色。国王说，你们中间至少有一个人的点是白色的。于是重复地问他们：“谁知道自己点的颜色？”三位大臣们头两次都回答说不知道。题目要求证明下一次他们全都会说“知道”，并且所有的点都是白色。,2019/6/20,8,5.1.1产生式表示（3）,分析： 这类问题的特点是有有限个受试者，每个人对问题都只有部分了解，无法直接求解。但在推理过程中每个人又可以从别人那里获得新的知识，重新进行推理。可以用产生式来表达推理过程中所用到的各种知识。,2019/6/20,9,5.1.1产生式表示（4）,状

5、态集合表示： 用x1,x2,x3表示三个人点的颜色，1表示白色，0表示非白色。 X(x1,x2,x3)表示颜色分布状态。 全部可能的状态集合(可能界PW0)： (0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1) 实际给定的状态为现实界X0 (x10,x20,x30) 用排除法寻找X0 。,2019/6/20,10,5.1.1产生式表示（5）,排除过程： 第一次，大臣只知道至少有一个人是白点，排除(0,0,0)状态。这时如果有人看到两个非白点，根据排除的状态可推知自己是白点。 第二次大臣根据没有一个人知道自己点颜色的事实

6、推知至少两人为白点。排除 (0,0,1)、(0,1,0)、(1,0,0) 状态。这时如果有人看到一个非白点，根据排除后得到的状态可推知自己的点是白的。 第三次，大臣们根据仍无人知道自己点颜色的新事实推知没有一个非白点出现，即X0=(1,1,1)。于是三人都知道自己点的颜色是白的。,2019/6/20,11,5.1.1产生式表示（6）,引入一些中介状态，并定义下述符号： Si i大臣看到的非白点数； Wi i大臣猜出自己点的颜色否。如果他宣布已知道自己点的颜色，为1，否则为0； nX0中白点的个数。 可对前面的分析过程形式化。,2019/6/20,12,5.1.1产生式表示（7）,第一次，大臣只

7、知道至少有一个人是白点，排除X0=(0,0,0)状态。 (n=1) X0 (0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)； 第二次大臣根据没有一个人知道自己点颜色的事实推知至少两人为白点。 (2) (n=1) (Si=2) =(Wi=1),(i=1,2,3,下同)； (3)( i ) (Wi=1) (n=1) = (n=1) ； (4) (n=1) = ( i ) (Wi=1) ； (5) ( i ) (Wi=0) (n=1) = (n=2) ; (6) (n=2) X0 (0,1,1),(1,0,1),(1,1,0),(1,1,

8、1)； 第三次，大臣们根据仍无人知道自己点颜色的新事实推知没有一个非白点出现。 (7) (n=2) (Si=1) =(Wi=1); (8) ( i ) (Wi=1) (n=2) = (n=2) ; (9) (n=2) = ( i ) (Wi=1); (10) ( i ) (Wi=0) (n=2) = (n=3); (11) (n=3) X0 (1,1,1)； (12) (n=3) = ( i ) (Wi=1).,2019/6/20,13,5.1.1产生式表示（8）,上述结果可以推广到更一般的情况： 设有m个大臣，国王说至少有l个人的点是白色的，则有下述产生式： (1) (n= l) X0 x|

9、x中的白点数=l； (2) (n= l) (Si=m-l) =(Wi=1),(i=1,2,m,下同)； (3)( i ) (Wi= 1) (n= l) = (n= l) ； (4) (n= l) = ( i ) (Wi= 1) ； (5)( i ) (Wi=0) (n= l) (l (n= l 1) ; (6)( i ) (Wi=0) (n= l) (l m-1) = (nm)。,2019/6/20,14,5.1.2 产生式系统结构（1）,问题求解框架与产生式系统对应： 叙述性知识动态（全局）数据库 过程性知识产生式规则库 控制性知识推理机,产生式规则库,推理机,动态数据库,2019/6/20

10、,15,5.1.2 产生式系统结构（2）,三个组成部分： 动态数据库人工智能系统的数据结构中心。是一个动态数据结构，用来存放初始事实数据、中间结果和最后结果。相当于人的短期记忆功能。 产生式规则库作用在全局数据库上的一些规则的集合。每条规则都有一定的条件，若全局数据库中内容满足这些条件可调用这条规则。一般可形成一个称为推理网络的结构图。相当于人的长期记忆功能。 推理机负责产生式规则的前提条件测试或匹配，规则的调度和选取，规则体的解释和执行。即推理机实施推理，并对推理进行控制，它也是规则的解释程序。相当于人的认知处理器。,2019/6/20,16,5.1.2 产生式系统结构（3）,例5.2 猴子

11、摘香蕉问题。如图5-2所示，一个房间里，天花板上挂着一串香蕉。房间里有一只猴子，还有一只可被猴子推移的箱子，而且，当猴子登上箱子时刚好可以摘到香蕉。设猴子在房间的a处，箱子在b处，香蕉在c处。问猴子如何行动可以摘取香蕉？建立产生式系统。 解：（1）全局数据库中表达问题在求解过程中所处的各种状态： 用四元组（w，x，y，z）表示。 其中： w：猴子的水平位置， w a，b，c； x：是否在箱子上，0表示不在箱顶，1表示在箱顶； y：箱子的水平位置， ya，b，c ； z：猴子是否拿到香蕉，0表示没有拿到香蕉，1表示拿到香蕉。 初始事实是（a，0，b，0）， 目标位置为（ c，1，c，1 ）,20

12、19/6/20,17,5.1.2 产生式系统结构（4）,（2）规则集： 规则 动作 条件 动态数据库事实变化 R1 goto（u） （w，0，y，z）（u，0，y，z） R2 pushbox（v）（w，0，w，z）（v，0，v，z） R3 climbbox （w，0，w，z）（w，1，w，z） R4 grasp （c，1，c，0）（c，1，c，1） 其中，u,v a，b，c （3）推理结果：,2019/6/20,18,5.1.3 产生式工作过程（1）,推理机在工作过程中需要完成的工作主要可以分为三个阶段： 高效模式匹配 冲突消解 推理 常用提高匹配效率的方法： （1）索引匹配 （2）分层匹配

13、（3）过滤匹配,2019/6/20,19,5.1.3 产生式工作过程（2）,冲突消解策略 马尔科夫算法：按优先级排序消除冲突 Rete算法：不是用事实去匹配每一条规则，仅考察有变化的规则。 其他： 规模排序：对所有匹配成功的产生式中选择前提条件最多或者情况元素最多者作为优先执行的规则 加权排序：给初始事实或中间结论以不同的优先权，与优先权较高的事实匹配的产生式优先使用,2019/6/20,20,5.1.3 产生式工作过程（3）,产生式系统推理 正向推理 反向推理 双向推理,2019/6/20,21,5.1.3 产生式工作过程（4）,正向推理过程,2019/6/20,22,5.1.3 产生式工作

14、过程（5）,反向推理过程,2019/6/20,23,5.1.3 产生式工作过程（6）,例5.3 5.4 汽车轮胎故障诊断及采取相应措施的产生式系统及其求解。 r1： IF 轮胎瘪了 AND 空气很快泄出 THEN 确认故障：轮胎没有气 r2： IF 轮胎变形了 AND 你的轮胎边缘有凹入 THEN 确认故障：变形了的轮胎。 r3： IF 轮胎被磨损 AND 磨损严重 THEN 确认故障：磨损了的轮胎 r4： IF 变形了的轮胎 AND 你要更换轮胎 THEN 轮胎需要更换 r5： IF 磨损了的轮胎 AND 你要更换轮胎 THEN 轮胎需要更换 r6： IF 轮胎没有气 AND 你要更换轮胎

15、THEN 轮胎需要更换 r7： IF 轮胎没有气 AND 你要修理轮胎 THEN 轮胎需要修理 r8： IF 轮胎需要修理 AND 你有一个扳手 AND 你有一个千斤顶 AND 你的状态良好 THEN 采取措施：自己修理它,2019/6/20,24,5.1.3 产生式工作过程（7）,r9： IF 轮胎需要更换 AND 你离电话很近 THEN 采取措施：呼叫公路服务获得帮助 r10： IF 轮胎需要修理 AND 你要给这个轮胎充气 AND 你有一个泵 AND 你知道如何使用它 THEN 采取措施：自己给轮胎充气 r11： IF 轮胎需要修理 AND 你知道某人有这个技术 AND 他能够做这个事情

16、 THEN 采取措施：请求他的帮助 r12： IF 轮胎需要更换 AND 你知道某人有这个技术 AND 他能够做这个事情 THEN 采取措施：请求他的帮助 r13： IF 轮胎需要更换 AND 你有一个扳手 AND 你有一个千斤顶 AND 你的状态良好 THEN 采取措施：自己更换它,2019/6/20,25,5.1.3 产生式工作过程（8）,规则集形成的部分推理网络：,2019/6/20,26,5.1.3 产生式工作过程（9）,已知初始事实： F1：轮胎瘪了 F2：空气很快泄出 F3：你要更换轮胎 F4：你离电话很近 目标条件：采取什么样的措施处理故障？ 采用正向推理回答采取的措施来处理故障

17、。,2019/6/20,27,5.1.3 产生式工作过程（10）,反向推理过程：,2019/6/20,28,5.2 专家系统概述,5.2.1 什么是专家系统 5.2.2 专家系统的类型 5.2.3 专家系统的发展,2019/6/20,29,5.2.1 什么是专家系统（1）,专家系统应该具备四个特征： （1）应用于某专门领域。 （2）拥有专家级知识。 （3）能模拟人类专家思维和决策过程。 （4）达到专家级水平。,2019/6/20,30,5.2.1 什么是专家系统（2）,专家系统的特点 解决那些不确定性的、非结构化的、没有算法解或虽有算法解但在现有的机器上无法实施的困难问题； 强调知识与推理的分

18、离，因而系统具有很好的灵活性和可扩充性； 还具有“自学习”能力，即不断对自己的知识进行扩充、完善和提炼 专家系统不会像人那样容易疲劳、遗忘，易受环境、情绪等的影响。,2019/6/20,31,5.2.2 专家系统的类型（1）,按解决问题性质分类 解释型 预测型 设计型 诊断型 规划型 监视型 控制型 调试型 教学型 修理型,2019/6/20,32,5.2.2 专家系统的类型（2）,按应用分类 典型化学专家系统。 典型电子学专家系统。 典型医学专家系统。 典型工程学专家系统。 典型地质学专家系统。 典型计算机专家系统。,2019/6/20,33,5.2.2 专家系统的类型（3）,按系统的体系结

19、构分类 集中式专家系统 分布式专家系统 人工神经网络专家系统 按知识表示形式 基于规则的专家系统 基于一阶谓词的专家系统 基于框架的专家系统 基于语义网的专家系统 按采用的技术 符号推理专家系统 神经网络专家系统,2019/6/20,34,5.2.3 专家系统的发展（1）,1.专家系统发展历史 第一代：这些专家系统具有高度专业化、求解专门问题的能力强等特点，但在体系结构的完整性、可移植性等方面存在缺陷，求解问题的能力弱 ； 第二代：专家系统属单学科专业型、应用型系统，其体系结构较完整，移植性方面也有所改善，而且在系统的人机接口、解释机制、知识获取技术、不确定推理技术、增强专家系统的知识表示和推

20、理方法的启发性、通用性等方面都有所改进； 第三代：多学科综合型系统，采用多种人工智能语言，综合采用各种知识表示方法和多种推理机制及控制策略，并开始运用各种知识工程语言、骨架系统及专家系统开发工具和环境来研制大型综合专家系统 ； 第四代：多专家协作、综合知识库、采用人工智能最新技术实现多Agent专家系统。,2019/6/20,35,5.2.3 专家系统的发展（2）,2.专家系统技术的发展 20世纪，50、60年代，产生式系统框架的提出； 20世纪70年代，领域知识的重要性，知识库与推理机的分离，MYCIN、EMYCIN出现； 20世纪80年代，各种开发语言应用于专家系统，出现各种开发工具。,2

21、019/6/20,36,5.3 专家系统结构及工作过程,5.3.1 专家系统的结构 5.3.2 专家系统工作过程,2019/6/20,37,5.3.1 专家系统的结构（1）,1.专家系统的概念结构,2019/6/20,38,5.3.1 专家系统的结构（2）,2.专家系统实际结构,图 5-10 专家系统实际结构示例,图5-11 黑板模型,2019/6/20,39,5.3.2 专家系统工作过程（1）,工作过程： 步1 根据用户提供的证据以及问题对知识库进行搜索，寻找可匹配的知识片段或知识网络； 步2 对同一问题可能会有多处知识片段或网络与之匹配，即形成知识操作算子序列，构成一个假设集合； 步3 根

22、据推理机提供的控制策略对形成的假设集合进行排序进入到推理机的议程中，并挑选其中在某些准则下为最优的假设方案； 步4 按照推理机提供的推理机制进行推理，求解具体问题； 步5 如果该推理过程不能解决问题，则回溯到假设方案序列中的下一个，重复求解问题； 步6 上述过程循环执行，直到问题已经解决或所有可能的求解方案都不能解决问题即本问题无解。,2019/6/20,40,5.3.2 专家系统工作过程（2）,图 5-12 基于规则的专家系统的相关技术,2019/6/20,41,5.3.2 专家系统工作过程（3）,PROSPECTOR中的不确定性处理-主观贝叶斯模型：,2019/6/20,42,PROSPE

23、CTOR中的不确定性处理,正向推理：将证据的不确定性传递给最终结论的不确定性： 用户输入证据E，在观察S下的确定性因子（-5，5）； 用证据匹配规则R，规则的不确定性用LS、LN表示 计算组合证据的不确定性 利用CP公式或EH公式计算结论H的不确定性 计算组合结论的不确定性 反向推理： 系统根据评判函数确定目标、子目标，根据用户提供的证据的可信度，转向正向推理，进行概率传播，直到到达可以由用户回答的证据为止。,2019/6/20,43,5.3.2 专家系统工作过程（4）,MYCIN中的不确定性处理 ： 以确定性理论为基础的可信度推理模型 在专家系统MYCIN中采用的推理方式就是反向链和深度优先

24、的搜索策略。 当MYCIN系统启动后，系统会自动生成一个包含 （姓名，年龄，性别，治疗方案） 的病人信息，其中前三项由系统向用户提出询问，要求用户输入，并存入数据库中。而治疗方法则是需要由系统自动推理得到，也是系统进行推理的最终目标。,2019/6/20,44,5.3.2 专家系统工作过程（5）,为了得到治疗方案，系统推理时，首先运用一条规则是RULE 092(目标规则)，其内容为： 如果：（1）有一种需要治疗的病原体，且 （2）可能还有其他需要治疗的病原体，尽管它们 还没有从当 前的培养物中被分离出来。 那么：（1）给出能有效抑制需治疗的病原体的治疗方案 （2）选择出最佳治疗方案 否则：指出

25、病人不需要治疗 要退出的目标需要的条件，可以直接询问用户，可以由其他的推理得到。,2019/6/20,45,5.4 专家系统的开发,5.4.1 开发步骤和方法 5.4.2 知识获取 5.4.3 推理机及解释机构设计 5.4.4 开发工具及开发环境,2019/6/20,46,5.4.1 开发步骤和方法,2019/6/20,47,5.4.2 知识获取,1.知识获取方式 人工知识获取：知识工程师、领域专家 半自动知识获取：知识工程师、领域专家、知识获取系统 自动知识获取：系统自身进行知识获取 2.知识获取的任务 抽取知识：挑选 知识的转换：形式化 知识的输入：输入知识库 知识的检测：等价、冗余、矛盾

26、、环路等的检验,2019/6/20,48,5.4.3 推理机及解释机构设计,1.推理机的设计 推理机的设计就是根据知识表达、知识推理方法和推理控制策略，设计具有求解专门领域的问题和自行推理的计算机软件系统。 2.解释结构的设计 预置本文方法 路径跟踪法，回答HOW和WHY问题 策略解释法 自动程序员解释方法,2019/6/20,49,5.4.4 开发工具及开发环境（1）,1.智能程序设计语言 LISP PROLOG OPS5、FRL 2.专家系统外壳 EMYCIN KAS EXPERT ,2019/6/20,50,5.4.4 开发工具及开发环境（2）,3.开发环境 AGE TEIRESIAS

27、CLIPS VPEXPERT ESTA,2019/6/20,51,5.5 专家系统的实例（1）,1知识表示,2019/6/20,52,5.5 专家系统的实例（2）,2019/6/20,53,5.5 专家系统的实例（3）,2.专家系统处理过程 不同的问题转向不同的问题节点，根据事实选择要执行的动作 3.推理的控制策略及解释 汽车故障诊断专家系统采用的是正向推理的方式，在知识库的节中的规则按照一定的顺序排列，当任一规则的条件得到满足后，则执行相应的动作,2019/6/20,54,5.6 新型专家系统,5.6.1 分布式专家系统 5.6.2 协同式专家系统 5.6.3 模糊专家系统 5.6.4 神经

28、网络专家系统,2019/6/20,55,5.6.1 分布式专家系统,分布式专家系统具有分布处理的特征，是把一个专家系统的功能分解到各个处理机上并行工作，以缩短问题求解的时间，提高专家系统的效率，设计一个分布式专家系统一般要考虑以下三方面的问题： 功能分布 知识分布 驱动分布 控制驱动 数据驱动 目标驱动 事件驱动,2019/6/20,56,5.6.2 协同式专家系统（1）,协同式专家系统也称为群专家系统，能够综合若干相近领域或一个领域的多个方面的分专家系统的相互协作，共同解决一个更广领域的问题。协同式专家系统与分布式专家系统有相似性，但协同式专家更强调各子专家系统之间的协同合作，它可以在同一个

29、处理机上实现各子专家系统。 1.协同方法 多智能体规划方法 功能化有效协同方法 谈判方法,2019/6/20,57,5.6.2 协同式专家系统（2）,2.协同式专家系统的结构 主从式 层次式 同僚式 广播式 网络式,2019/6/20,58,5.6.3 模糊专家系统（1）,模糊专家系统特点 （1）知识库中存放的规则的模糊性由模糊集以及模糊集之间的关系来表示，如果是基于模糊关系合成的运算，则知识库中存放的则是模糊关系矩阵。 （2）模糊数据库存放的是推理过程中的模糊证据和推理过程中的模糊的中间结论。 （3）模糊推理机则按照在第四章讲过的模糊推理的各种推理方法以及各种控制策略，推理出可以接受的模糊结

30、论。 （4）模糊知识获取则需要按照领域专家提供的自然语言描述的知识转化为相应的模糊语言值或者用模糊集合表示的模糊知识，这个过程称为模糊化，得到的结果存入模糊知识库中。 （5）解释模块则将得到的用模糊集合表示的知识解释为自然语言。 （6）人机接口则交换的是模糊的信息。,2019/6/20,59,5.6.3 模糊专家系统（2）,系统结构,2019/6/20,60,5.6.4 神经网络专家系统（1）,神经网络专家系统是将神经网络与传统专家系统集成所得到的一种新型专家系统。神经网络具有自组织、自学习、自适应、分布存储、并行处理等功能，比较适合模拟人类的低级感知智能。,2019/6/20,61,5.6.

31、4 神经网络专家系统（2）,（1）知识库，神经网络专家系统中的知识库由神经网络来实现，它实际上是一个经过训练达到稳定权值分布的神经网络，领域知识被隐式分布存储在神经网络的各个连接权值和阈值中，而神经网络专家系统知识库的建立过程实际上就是神经网络的学习过程。 （2）知识获取，神经网络专家系统的知识获取主要表现为训练样本的获取和神经网络的训练两个方面。 （3）推理机，神经网络专家系统的推理过程是一个非线性数值的计算过程，它是一种并行推理机制。推理的过程首先是将当前输入模式变化为神经网络的输入模式，然后由输入模式计算网络的输出模式。 （4）解释器，解释器的主要作用是对神经网络的输入模式进行解释，把数字表示的神经网络的输入模式变换为用户能够理解的自然语言模式。,2019/6/20,62,The End！,