四章产生式系统课件

1、第 四 章 产生式知识表示及相关专家系统教材： 第 2、 6-1、 10 章第 四 章 引 言： 是 AI 的一个重要知识表示形式; 常用于构建基于规则专家系统。 要求： 掌握产生式模式及专家系统体系结构、运行机制及基本实现技术 - 模式匹配、触发规则、冲突解决策略、正向推理、逆向推理、不确定推理基本概念等。产生式知识表示及相关专家系统引 言： 要求：产生式知识表示及相关专家系统产生式知识表示及相关专家系统 产生式认知模型 产生式系统架构 产生式系统推理机的实现技术 专家系统概述产生式知识表示及相关专家系统 产生式认知模型产生式认知模型马亦可夫Markov（1954）提出基于产生式的符号变换控

2、制算法： 将一组产生式规则按优先级次序作用输入串； 若较高优先级的规则不可用，则应用下一条规则，如此周而复始; 直到 或规则集合中的规则都不可用，或系统使用了一条以句号结束的规则， 算法结束。美国数学家 E.Post（1943）提出：用符号语言构造产生式计算模型： - 指出:任何数学系统、逻辑系统都可视为一个产生式集合，规定如何将一个符号串变换成另一个符号串。(计算机程序、巴科斯范式也亦如此)证明:产生式计算模型具有和图灵机同样的计算能力。产生式认知模型马亦可夫Markov（1954）提出基于产生式产生式认知模型规则：（1）xy yx（2） （3） 。希腊字母、等代表专用符号串；小写字母 x、

3、y 、z 等表示单个字符的变量；专用字符 为空字符串。输入字符串 ： “ ABC ”规则号字符串匹配规则条件部分字符串的新状态下一步工作（1）（2）（3）（1）（1）（1）（2） 失败 失败 成功 成功 成功 失败 成功ABCABCABCBACBCABCABCA匹配下条规则匹配下条规则匹配头条规则匹配头条规则匹配头条规则匹配下条规则转换完毕，结束例: 用Markov算法作用于任意给定的字符串。执行算法过程：规则自左向右地作用输入字符串。产生式认知模型规则：（1）xy yx希腊字母、等产生式认知模型纽厄尔和西蒙 Newell & Simon（1972）：总结人类的认知模型：长期记忆 - 大脑中积

4、累的知识和经验部分（大容量的、松散的、表现为认识-行为的知识块）短时记忆 由感官输入的信息以及求解具体问题所需的、临时存放的知识块（小容量的动态变化的知识 ）；认知处理器 人类求解问题可视为从长期记忆的成块知识中找出由当前输入信息激活的那些知识块，并按优先级排序有选择地执行某个知识快的过程 产生式规则计算模型与人类认知模型相对应，成为 AI 的一种基本的知识表示形式 产生式系统。产生式认知模型纽厄尔和西蒙 Newell & Simon（1 产生式认知模型 产生式系统架构 产生式系统推理机的实现技术 专家系统概述产生式知识表示及相关专家系统 产生式认知模型产生式知识表示及相关专家系统长期记忆 -

5、短时记忆 -认知处理器 -工作存储器（事实库、工作库、综合数据库、. )规则库（长期知识库、 . ）推理机（控制系统、控制策略、解释程序、.)产生式系统架结构长期记忆 -短时记忆 -认知处理器 -工作存储器推理机（控制系统）规则库事实库（综合数据库）产生式系统架结构推理机（控制系统）规则库事实库（综合数据库）产生式系统架结构 规则库（长期记忆区 ）： 存放一系列规则（算子），用于描述状态的转换关系、前提与结论间的因果关系以及环境条件与执行操作的关系等。 表现形式：IF 前件 THEN 后件;IF LHS THEN RHS LHS: 本规则触发应满足的条件； RHS：本规则触发后可产生的结果（或

6、应执行的操作） 例: R1: IF (x,0,y,0) THEN (v,0,y,0)； R2: IF likes(x,y) & likes(y,x) THEN friend(x,y) R2: IF 天气太热 THEN 打开空调；产生式系统架结构 规则库（长期记忆区 ）： 例: R2: IF likes(事实库（短时记忆区 ）：存放问题的初始状态、已知事实、推理的中间结果及结论等。表现形式：符号串、数组、向量、集合、谓词等例：“8数码”问题状态描述 - 矩阵 (Sij)；“猴子摘香蕉”问题状态描述 - （a，0，b，0）；“祖孙关系”定理证明谓词描述 Parent ( x，y )。产生式系统架结

7、构事实库（短时记忆区 ）：例：“8数码”问题状态描述 - 矩 推理机的基本运行算法: 1DATA初始事实库 2until DATA 满足结束条件以前，do 3. begin 4在所有满足当前事实库 DATA 的规则集合中，选择一条规则 R 5DATA执行R 后得到的结果 6. end产生式系统架结构 推理机的基本运行算法:产生式系统架结构产生式系统推理机工作流程事实库规则启用产生式系统推理机工作流程事实库规则启用 产生式认知模型 产生式系统架构 产生式系统推理机的实现技术 专家系统概述产生式知识表示及相关专家系统 产生式认知模型产生式知识表示及相关专家系统规则的匹配（规则的触发，变量的绑定 B

8、ounding ）；规则的选择（规则的选择，冲突解决策略） ；规则的应用（规则的执行，演绎 加入新断言，反应 执行规定操作） 规则推理的不确定性（不确定性推理）规则推理的方向（正向推理 数据驱动，逆向推理 目标驱动）；规则应用的解释（解释问题类型，How, Why ）；记录问题求解过程中规则的应用顺序（输出，解径、解图）；控制系统运行的终止（正常终止，非正常终止）。 产生式系统推理机的实现技术产生式系统推理机的实现技术规则的匹配从规则库的第一条规则开始，按排列顺序逐条用规则的前提条件与事实库中事实进行匹配； R: IF (x,0,y,0) THEN (v,0,y,0) F: (a,0,b,0)

9、 - 新状态: (v,0,b,0) 常量置换变量;合一匹配成功. 由于一次搜索过程中，可能有多条规则同时为事实库中事实所匹配， 需将所有的触发规则送冲突集，应用冲突解决策略选择启用规则。触发规则: 前提条件为当前事实库所满足的规则. 冲突集: 所有触发规则构成的集合。规则的匹配从规则库的第一条规则开始，按排列顺序逐条用规则的前规则的匹配（规则的触发，变量的绑定 Bounding ）；规则的选择（规则的选择，冲突解决策略） ；规则的应用（规则的执行：演绎 加入新断言，反应 执行规定操作） 规则推理的不确定性（不确定性推理）规则推理的方向（正向推理 数据驱动，逆向推理 目标驱动）；规则应用的解释（

10、解释问题类型：How, Why ）；记录问题求解过程中规则的应用顺序（输出：解径、解图）；控制系统运行的终止（正常终止，非正常终止）。 产生式系统推理机的实现技术产生式系统推理机的实现技术规则的选择及冲突解决策略启用规则：从冲突集中选择出的某条合适的可作为当前的执行规则。冲突解决策略：反应型系统(Reaction)演绎型系统(Deduction)规则排序：排在前面的规则优先执行； 专一性排序：条件越具体的规则优先执行； 就近排序：与事实库中最新加入事实匹配的规则优先执行 ( 参见： OPS5 产生式系统语言 ) 上下文排序：特定时间段内只从某上下文有关规则组内选择执行规则的选择及冲突解决策略启

11、用规则：冲突解决策略：反应型系统演规则的匹配（规则的触发，变量的绑定 Bounding ）；规则的选择（规则的选择，冲突解决策略） ；规则的应用（规则的执行：演绎 加入新断言，反应 执行规定操作） 规则推理的不确定性（不确定性推理）规则推理的方向（正向推理 数据驱动，逆向推理 目标驱动）；规则应用的解释（解释问题类型：How, Why ）；记录问题求解过程中规则的应用顺序（输出：解径、解图）；控制系统运行的终止（正常终止，非正常终止）。 产生式系统推理机的实现技术产生式系统推理机的实现技术 概念的模糊性- 模糊推理IF 西红柿红了 THEN 西红柿熟了， 西红柿非常红- 西红柿（？）熟11.6

12、1.751.91.78矮中等高0身高隶属度修饰量化： 非常高 不太高 .不确定性推理- 信息的不精确、不完整、模糊性 概念的模糊性IF 西红柿红了 THEN 西红柿熟了， 信息的不精确性： 规则的不确定性 IF A流鼻涕&红眼睛THEN A患流感 （CF : 0.67） A患鼻膜过敏（CF : 0.06）IF 培养液是血液， 细菌的类别不知道， 细菌的染色体是革兰式阴性， 细菌的外伤是杆状，THEN 细菌的类别是假单菌（CF :0.4） 事实的不确定性 A 流鼻涕 ( 0.4 ) A 红眼睛 ( 0.8 )不确定性推理- 信息的不精确、不完整、模糊性 信息的不精确性： IF A流鼻涕&红眼睛I

13、F 培 R1: if E1 then H (0.9) R2: if E2 then H (0.7) R3: if E3 then H (0.8) R4: if E4 & E5 then E1 (0.7) R5: if E6 & (E7 OR E8) then E2 (1.0)不确定性推理事实证据: E3 E4 ( 0.9 ) E5 ( 0.6 ) E6 ( 0.7 ) E7 ( 0.3 ) E8 ( 0.8 )原始证据或观察的事实是判断规则前提条件成立的依据 例，E4，E51、组合证据的不确定性计算？ R1: if E1 then H 0.30.90.60.70.30.80.71.00.70.

14、9- 0.8不确定性推理2、推理过程的不确定性计算 ？ - 包括一步推理与推理链结 论的计算，例，E1，E2；3、多条规则的结论合成的不 确定性计算 ？ - 例，H。0.30.90.60.70.30.80.71.00.70.9一、组合证据的不确定性计算：证据合取：从每个证据的可信度中获得证据总体的可信度。0.90.51.00.51）、基于模糊集计算方法 取小 ( MYCIN - 6.3节 )0.90.51.00.452）、基于概率论计算方法 乘积 ( PROSPECTOR 6.4节 )不确定性推理一、组合证据的不确定性计算：证据合取：从每个证据的可信度中获01.0CinCoutCin01.0C

15、out01.0CinCout先验值先验值 0.8CinCout0.50.4不确定性推理二、推理过程结论（一步推理）的不确定性计算：结论可信度一般计算方法:规则条件可信度与结论可信度之间存在某种关系 规则的可信度（系数）01.0CinCoutCin01.0Cout01.0CinC基于模糊理论计算方法 取大 ( EXPERT)0.90.250.9（a）不确定性推理三、多条规则结论合成的可信度计算：H基于模糊理论计算方法 取大0.90.250.9（a）不确基于概率论方法 （1）计算流程：1、由各规则的可信度 C 与不可信度 1-C 计算规则的可信比例 r；2、将各规则的可信比例相乘，获多条规则推得的

16、结论的可信比例；3、再将可信比例转换成最终结论的可信度。设 规则可信比例 ：规则可信度： 不确定性推理三、多条规则结论合成的可信度计算：基于概率论方法 （1）计算流程：设 规则可信比例 ：规则可信基于概率论方法 （1） r: 可信比例 c: 可信度0.90.750.25可信度可信度比例9 1 / 3 = 30.90.250.75不确定性推理三、多条规则结论合成的可信度计算：H基于概率论方法 （1） r: 可信比例 c: 可信常用的不确定性推理计算方法： 确定性因子法 ( MYCIN )； 主观Bayes法 ( Prospector ) ； D-S证据理论； 模糊可能性理论； 不确定性推理常用的

17、不确定性推理计算方法：不确定性推理规则的匹配（规则的触发，变量的绑定 Bounding ）；规则的选择（规则的选择，冲突解决策略） ；规则的应用（规则的执行：演绎 加入新断言，反应 执行规定操作） 规则推理的不确定性（不确定性推理）规则推理的方向（正向推理 数据驱动，逆向推理 目标驱动）；规则应用的解释（解释问题类型：How, Why ）；记录问题求解过程中规则的应用顺序（输出：解径、解图）；控制系统运行的终止（正常终止，非正常终止）。 产生式系统推理机的实现技术产生式系统推理机的实现技术正向推理的产生式系统例：当前事实库： A ； 目标： G 规则集： R1: if A then B and

18、 C, R2: if B then D, 推理后事实库： A,B,C ； A,B,C,D ；，G 特点： 数据驱动。 规则形式： - 操作： 用已知事实去匹配规则的前件，正向地运用规则， 求证目标成立的过程。 概念： 被正向使用的规则称为 F 规则。 正向推理的产生式系统例：当前事实库： A ； 目正向推理的产生式系统实例（1）动物识别产生式系统: G = “ A是猎豹？” 已有知识（规则库）：R1： IF X 是食肉动物 X 毛发是深褐色 X 有花斑点 THEN X 是猎豹。R2： IF ( X 是哺乳动物 ) ( X 食肉 ) ( X 有尖利的牙齿 X 有爪子 X 有前视眼 ) THEN

19、X 是食肉动物。R3： IF X 有毛发 THEN X 是哺乳动物 已知事实（事实库）： A有毛发； A有尖利的牙齿； A有爪子； A有前视眼； A毛发是深褐色； A有花斑点； 正向推理的产生式系统实例（1）动物识别产生式系统: G 猎豹深褐色毛发有花斑点食肉动物食肉哺乳动物外形特征有毛发尖利的牙齿有爪子前视眼R3R2R1深褐色毛发有花斑点有毛发尖利的牙齿有爪子前视眼推理方向： 事实 结论正向推理的产生式系统实例（1）猎豹深褐色毛发有花斑点食肉动物食肉哺乳动物外形特征有毛发尖利正向推理的产生式系统算法中的符号： DB: 存放事实和中间结果的事实库； KB: 存放知识的规则库； RS: 当前所有

20、触发规则构成的冲突集合。 正向推理的产生式系统算法中的符号：正向推理的产生式系统初始事实放入事实库 DBDB 中有目标？KB中有前件为DB满足 的规则？匹配，将所有触发规则放入冲突集RS RS 为空？成功，退出失败，退出用户要补充新事实？ 新事实加入事实库 DB是否是是否是否否正向推理的产生式系统初始事实放入事实库 DBDB 中有目标？正向推理的产生式系统按规定的冲突解决策略从 RS 中选择一条规则执行。执行结果加入事实库 DBAB正向推理的产生式系统按规定的冲突解决策略从 RS 中选择一条逆向推理的产生式系统例： 假设待证目标： G ； 事实证据库： 规则集： R1: if B and C

21、then G, R2: if D then B, 推理后事实证据库： B,C ； C,D ； 特点： 目标驱动： 规则形式： - 操作： 用假设的待证目标去匹配规则的后件，逆向地运用规则， 求证所有支持目标所需的前提条件均成立的过程。 概念： 被逆向使用的规则称为 B 规则。 逆向推理的产生式系统例： 假设待证目标： G ； 事逆向推理的产生式系统实例（1）动物识别产生式系统: G = “ A是猎豹？” 已有知识（规则库）：R1： IF X 是食肉动物 X 毛发是深褐色 X 有花斑点 THEN X 是猎豹。R2： IF ( X 是哺乳动物 ) ( X 食肉 ) ( X 有尖利的牙齿 X 有爪子

22、 X 有前视眼 ) THEN X 是食肉动物。R3： IF X 有毛发 THEN X 是哺乳动物 已知事实（事实库）： A有毛发； A有尖利的牙齿； A有爪子； A有前视眼； A毛发是深褐色； A有花斑点； 逆向推理的产生式系统实例（1）动物识别产生式系统: G 推理方向： 目标 事实逆向推理的产生式系统实例（2）猎豹有花斑点食肉动物食肉哺乳动物外形特征有毛发尖利的牙齿有爪子前视眼R3R2R1深褐色毛发深褐色毛发有花斑点有毛发尖利的牙齿有爪子前视眼推理方向：逆向推理的产生式系统实例（2）猎豹有花斑点食肉动物逆向推理的产生式系统算法中的符号： DB: 存放最终事实和中间证据的事实证据库； KB:

23、 存放知识的规则库； RS: 当前所有触发规则构成的冲突集合。 逆向推理的产生式系统算法中的符号：逆向推理的产生式系统假设待证目标DB有支持目标的事实KB中有后件支持(子)目 标的规则？匹配，将所有触发规则放入冲突集RS目标成立，退出事实支持假设目标，事实送 DB 用户补充新事实？ 询问用户是否是否是否AB 目标不成立,退出 RS 为空？是否逆向推理的产生式系统假设待证目标DB有支持目标的事实KB中有A选择规则的一个前提条件作为新的待证目标。B从 RS 中选择一条触发规则逆向推理的产生式系统A选择规则的一个前提条件作为新的待证目标。B从 RS 中选择正（逆）向产生式系统的比较特点正向推理逆向推

24、理推理驱动方式数据驱动目标驱动优点算法简单，易于实现搜索目的性强，推理效率高缺点1、搜索目的性弱，可能求解出多个无关的结论；2、 匹配时，要遍历整个规则库，推理效率低。1、确定目标的时候，具有盲目性，可能产生假目标2、当规则的后件是操作而非断言时，即反应型系统，不宜使用此法用途主要用于已知初始数据，不知目标的推理；或是解空间大的一类推理。主要用于结论单一或已知目标求证的一类推理。应用监控、预测、规划、设计等选择、分类、故障诊断等正（逆）向产生式系统的比较特点正向推理逆向推理推理驱动方式数规则的匹配（规则的触发，变量的绑定 Bounding ）；规则的选择（规则的选择，冲突解决策略） ；规则的应

25、用（规则的执行：演绎 加入新断言，反应 执行规定操作） 规则推理的不确定性（不确定性推理）规则推理的方向（正向推理 数据驱动，逆向推理 目标驱动）；规则应用的解释（解释问题类型：How, Why ）；记录问题求解过程中规则的应用顺序（输出：解径、解图）；控制系统运行的终止（正常终止，非正常终止）。 产生式系统推理机的实现技术产生式系统推理机的实现技术规则应用的解释 必要性： 解释推理过程，帮助使用者理解系统是如何得到结论的； 解释问题类型： How did you come to this result ? Why do you want know this fact ?规则应用的解释 必要性

26、： 解释问题类型：规则应用的解释How ?食肉动物正向推理Why ?有利齿逆向推理R2： IF X 是哺乳动物 X 有尖利的牙齿 X 有爪子 X 有前视眼 THEN X 是食肉动物。R3： IF X 有毛发 THEN X 是哺乳动物食肉动物哺乳动物有毛发前视眼爪子利齿R3R2规则应用的解释How ?Why ?R2： IF 产生式系统小结描 述优 点缺 点事实库 - 对所有规则操作的唯一场所。系统结构简单明了，易于理解。规则 经验知识块 具有统一的表示形式，容易理解、定义。规则之间无直接调用关系，相互关系不清楚，系统功能不易把握。对某些规则的修改、扩充，可能造成与其它规则的矛盾，规则库的一致性维

27、护困难。规则之间相互独立，具有高度模块化。推理机 - 控制推理机制简单、推理步骤独立，便于跟踪、解释。需对所有规则进行模式匹配，搜索效率低下。推理控制方式单一，缺乏灵活性。产生式系统小结描 述优 点缺 点事实库 - 对所有规则操作的 产生式认知模型 产生式系统架构 产生式系统推理机的实现技术 专家系统概述产生式知识表示及相关专家系统 产生式认知模型产生式知识表示及相关专家系统何谓专家系统专家系统是一种具有智能的计算机系统，它能使用某一问题领域的知识为该领域提供”专家级”的服务，能部分或全部地代替领域专家解决本领域的高难度问题。何谓专家系统专家系统是一种具有智能的计算机系统，它能使用某一专家系统

28、的分类 按输出结果分类： 输出断言结论：诊断、解释、预测、决策； 输出可执行的方案：设计、规划、控制、调度。 按知识表示分类： 产生式规则，一阶谓词逻辑，框架系统，语义网络，过程型， 按推理模式分类： 精确推理、不确定性推理； 基于规则推理、基于模型推理，基于案例推理。 按规模分类： 大型协同综合型； 微型控制型。专家系统的分类 按输出结果分类： 按知识表示分类： 按推理模专家系统的分类应用问题类型： 解释： 处理大量不完全、受干扰数据，正确解释结果(图象、语音分析) 预测： 根据对象过去和现在的情况，推断其将来演变结果。- 数据随时间变化 （气象、军事、交通、市场等预测） 诊断： 通过观察症状，确定对象的故障和缺陷- 现象与故障之间无严格的对应关系（医疗-MYCIN、机器故障等诊断） 设计：