四章产生式系统课件.ppt

第 四 章 产生式知识表示及相关专家系统教材： 第 2、 6-1、 10 章,第 四 章,引 言： 是 AI 的一个重要知识表示形式; 常用于构建基于规则专家系统。,要求： 掌握产生式模式及专家系统体系结构、运行机制及基本实现技术 - 模式匹配、触发规则、冲突解决策略、正向推理、逆向推理、不确定推理基本概念等。,产生式知识表示及相关专家系统,引 言： 要求：产生式知识表示及相关专家系统,产生式知识表示及相关专家系统,产生式认知模型 产生式系统架构 产生式系统推理机的实现技术 专家系统概述,产生式知识表示及相关专家系统 产生式认知模型,产生式认知模型,马亦可夫Markov（1954）提出基于产生式的符号变换控制算法： 将一组产生式规则按优先级次序作用输入串； 若较高优先级的规则不可用，则应用下一条规则，如此周而复始; 直到 或规则集合中的规则都不可用，或系统使用了一条以句号结束的规则， 算法结束。,美国数学家 E.Post（1943）提出：用符号语言构造产生式计算模型： - 指出:任何数学系统、逻辑系统都可视为一个产生式集合，规定如何将一个符号串变换成另一个符号串。(计算机程序、巴科斯范式也亦如此)证明:产生式计算模型具有和图灵机同样的计算能力。,产生式认知模型马亦可夫Markov（1954）提出基于产生式,产生式认知模型,规则：（1）xy yx（2） （3） 。,希腊字母、等代表专用符号串；小写字母 x、y 、z 等表示单个字符的变量；专用字符 为空字符串。,输入字符串 ： “ ABC ”,例: 用Markov算法作用于任意给定的字符串。,执行算法过程：规则自左向右地作用输入字符串。,产生式认知模型规则：（1）xy yx希腊字母、等,产生式认知模型,纽厄尔和西蒙 Newell & Simon（1972）：总结人类的认知模型：长期记忆 - 大脑中积累的知识和经验部分（大容量的、松散的、表现为认识-行为的知识块）短时记忆 由感官输入的信息以及求解具体问题所需的、临时存放的知识块（小容量的动态变化的知识 ）；认知处理器 人类求解问题可视为从长期记忆的成块知识中找出由当前输入信息激活的那些知识块，并按优先级排序有选择地执行某个知识快的过程,产生式规则计算模型与人类认知模型相对应，成为 AI 的一种基本的知识表示形式 产生式系统。,产生式认知模型纽厄尔和西蒙 Newell & Simon（1,产生式认知模型 产生式系统架构 产生式系统推理机的实现技术 专家系统概述,产生式知识表示及相关专家系统,产生式认知模型产生式知识表示及相关专家系统,长期记忆 -,短时记忆 -,认知处理器 -,工作存储器（事实库、工作库、综合数据库、. ),规则库（长期知识库、 . ）,推理机（控制系统、控制策略、解释程序、.),产生式系统架结构,长期记忆 -短时记忆 -认知处理器 -工作存储器,产生式系统架结构,推理机（控制系统）规则库事实库（综合数据库）产生式系统架结构,规则库（长期记忆区 ）： 存放一系列规则（算子），用于描述状态的转换关系、前提与结论间的因果关系以及环境条件与执行操作的关系等。 表现形式：IF 前件 THEN 后件;IF LHS THEN RHS LHS: 本规则触发应满足的条件； RHS：本规则触发后可产生的结果（或应执行的操作）,例: 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 )。,产生式系统架结构,事实库（短时记忆区 ）：例：“8数码”问题状态描述 - 矩,推理机的基本运行算法: 1DATA初始事实库 2until DATA 满足结束条件以前，do 3. begin 4在所有满足当前事实库 DATA 的规则集合中，选择一条规则 R 5DATA执行R 后得到的结果 6. end,产生式系统架结构,推理机的基本运行算法:产生式系统架结构,产生式系统推理机工作流程,产生式系统推理机工作流程事实库规则启用,产生式认知模型 产生式系统架构 产生式系统推理机的实现技术 专家系统概述,产生式知识表示及相关专家系统,产生式认知模型产生式知识表示及相关专家系统,规则的匹配（规则的触发，变量的绑定 Bounding ）；规则的选择（规则的选择，冲突解决策略） ；规则的应用（规则的执行，演绎 加入新断言，反应 执行规定操作） 规则推理的不确定性（不确定性推理）规则推理的方向（正向推理 数据驱动，逆向推理 目标驱动）；规则应用的解释（解释问题类型，How, Why ）；记录问题求解过程中规则的应用顺序（输出，解径、解图）；控制系统运行的终止（正常终止，非正常终止）。,产生式系统推理机的实现技术,产生式系统推理机的实现技术,规则的匹配,从规则库的第一条规则开始，按排列顺序逐条用规则的前提条件与事实库中事实进行匹配；,R: IF (x,0,y,0) THEN (v,0,y,0) F: (a,0,b,0) - 新状态: (v,0,b,0),常量置换变量;合一匹配成功.,由于一次搜索过程中，可能有多条规则同时为事实库中事实所匹配， 需将所有的触发规则送冲突集，应用冲突解决策略选择启用规则。,触发规则: 前提条件为当前事实库所满足的规则.,冲突集: 所有触发规则构成的集合。,规则的匹配从规则库的第一条规则开始，按排列顺序逐条用规则的前,规则的匹配（规则的触发，变量的绑定 Bounding ）；规则的选择（规则的选择，冲突解决策略） ；规则的应用（规则的执行：演绎 加入新断言，反应 执行规定操作） 规则推理的不确定性（不确定性推理）规则推理的方向（正向推理 数据驱动，逆向推理 目标驱动）；规则应用的解释（解释问题类型：How, Why ）；记录问题求解过程中规则的应用顺序（输出：解径、解图）；控制系统运行的终止（正常终止，非正常终止）。,产生式系统推理机的实现技术,产生式系统推理机的实现技术,规则的选择及冲突解决策略,启用规则：从冲突集中选择出的某条合适的可作为当前的执行规则。,冲突解决策略：,反应型系统(Reaction),演绎型系统(Deduction),规则排序：排在前面的规则优先执行；,专一性排序：条件越具体的规则优先执行；,就近排序：与事实库中最新加入事实匹配的规则优先执行, ( 参见： OPS5 产生式系统语言 ),上下文排序：特定时间段内只从某上下文有关规则组内选择执行,规则的选择及冲突解决策略启用规则：冲突解决策略：反应型系统演,规则的匹配（规则的触发，变量的绑定 Bounding ）；规则的选择（规则的选择，冲突解决策略） ；规则的应用（规则的执行：演绎 加入新断言，反应 执行规定操作） 规则推理的不确定性（不确定性推理）规则推理的方向（正向推理 数据驱动，逆向推理 目标驱动）；规则应用的解释（解释问题类型：How, Why ）；记录问题求解过程中规则的应用顺序（输出：解径、解图）；控制系统运行的终止（正常终止，非正常终止）。,产生式系统推理机的实现技术,产生式系统推理机的实现技术,概念的模糊性- 模糊推理,IF 西红柿红了 THEN 西红柿熟了， 西红柿非常红- 西红柿（？）熟,修饰量化： 非常高 不太高 .,不确定性推理- 信息的不精确、不完整、模糊性,概念的模糊性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流鼻涕&红眼睛IF 培,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),不确定性推理,1、组合证据的不确定性计算？,R1: if E1 then H,不确定性推理,2、推理过程的不确定性计算 ？ - 包括一步推理与推理链结 论的计算，例，E1，E2；3、多条规则的结论合成的不 确定性计算 ？ - 例，H。,0.30.90.60.70.30.80.71.00.70.9,一、组合证据的不确定性计算：,证据合取：从每个证据的可信度中获得证据总体的可信度。,不确定性推理,一、组合证据的不确定性计算：证据合取：从每个证据的可信度中获,不确定性推理,二、推理过程结论（一步推理）的不确定性计算：,结论可信度一般计算方法:规则条件可信度与结论可信度之间存在某种关系 规则的可信度（系数）,01.0CinCoutCin01.0Cout01.0CinC,基于模糊理论计算方法 取大 ( EXPERT),不确定性推理,三、多条规则结论合成的可信度计算：,H,基于模糊理论计算方法 取大0.90.250.9（a）不确,基于概率论方法 （1）,计算流程：1、由各规则的可信度 C 与不可信度 1-C 计算规则的可信比例 r；2、将各规则的可信比例相乘，获多条规则推得的结论的可信比例；3、再将可信比例转换成最终结论的可信度。,设 规则可信比例 ：,规则可信度：,不确定性推理,三、多条规则结论合成的可信度计算：,基于概率论方法 （1）计算流程：设 规则可信比例 ：规则可信,基于概率论方法 （1）,r: 可信比例 c: 可信度,不确定性推理,三、多条规则结论合成的可信度计算：,H,基于概率论方法 （1） r: 可信比例 c: 可信,常用的不确定性推理计算方法： 确定性因子法 ( MYCIN )； 主观Bayes法 ( Prospector ) ； D-S证据理论； 模糊可能性理论； ,不确定性推理,常用的不确定性推理计算方法：不确定性推理,规则的匹配（规则的触发，变量的绑定 Bounding ）；规则的选择（规则的选择，冲突解决策略） ；规则的应用（规则的执行：演绎 加入新断言，反应 执行规定操作） 规则推理的不确定性（不确定性推理）规则推理的方向（正向推理 数据驱动，逆向推理 目标驱动）；规则应用的解释（解释问题类型：How, Why ）；记录问题求解过程中规则的应用顺序（输出：解径、解图）；控制系统运行的终止（正常终止，非正常终止）。,产生式系统推理机的实现技术,产生式系统推理机的实现技术,正向推理的产生式系统,例：当前事实库： A ； 目标： G 规则集： R1: if A then B and 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 X 是食肉动物。R3： IF X 有毛发 THEN X 是哺乳动物,已知事实（事实库）： A有毛发； A有尖利的牙齿； A有爪子； A有前视眼； A毛发是深褐色； A有花斑点；,正向推理的产生式系统实例（1）动物识别产生式系统: G,推理方向： 事实 结论,正向推理的产生式系统实例（1）,猎豹深褐色毛发有花斑点食肉动物食肉哺乳动物外形特征有毛发尖利,正向推理的产生式系统,算法中的符号： DB: 存放事实和中间结果的事实库； KB: 存放知识的规则库； RS: 当前所有触发规则构成的冲突集合。,正向推理的产生式系统算法中的符号：,正向推理的产生式系统,正向推理的产生式系统初始事实放入事实库 DBDB 中有目标？,正向推理的产生式系统,正向推理的产生式系统按规定的冲突解决策略从 RS 中选择一条,逆向推理的产生式系统,例： 假设待证目标： G ； 事实证据库： 规则集： R1: if B and C 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 有爪子 X 有前视眼 ) THEN X 是食肉动物。R3： IF X 有毛发 THEN X 是哺乳动物,已知事实（事实库）： A有毛发； A有尖利的牙齿； A有爪子； A有前视眼； A毛发是深褐色； A有花斑点；,逆向推理的产生式系统实例（1）动物识别产生式系统: G,推理方向： 目标 事实,逆向推理的产生式系统实例（2）,推理方向：逆向推理的产生式系统实例（2）猎豹有花斑点食肉动物,逆向推理的产生式系统,算法中的符号： DB: 存放最终事实和中间证据的事实证据库； KB: 存放知识的规则库； RS: 当前所有触发规则构成的冲突集合。,逆向推理的产生式系统算法中的符号：,逆向推理的产生式系统,逆向推理的产生式系统假设待证目标DB有支持目标的事实KB中有,逆向推理的产生式系统,A选择规则的一个前提条件作为新的待证目标。B从 RS 中选择,正（逆）向产生式系统的比较,正（逆）向产生式系统的比较特点正向推理逆向推理推理驱动方式数,规则的匹配（规则的触发，变量的绑定 Bounding ）；规则的选择（规则的选择，冲突解决策略） ；规则的应用（规则的执行：演绎 加入新断言，反应 执行规定操作） 规则推理的不确定性（不确定性推理）规则推理的方向（正向推理 数据驱动，逆向推理 目标驱动）；规则应用的解释（解释问题类型：How, Why ）；记录问题求解过程中规则的应用顺序（输出：解径、解图）；控制系统运行的终止（正常终止，非正常终止）。,产生式系统推理机的实现技术,产生式系统推理机的实现技术,规则应用的解释,必要性： 解释推理过程，帮助使用者理解系统是如何得到结论的；,解释问题类型： How did you come to this result ? Why do you want know this fact ?,规则应用的解释 必要性： 解释问题类型：,规则应用的解释,How ?食肉动物正向推理,Why ?有利齿逆向推理,R2： IF X 是哺乳动物 X 有尖利的牙齿 X 有爪子 X 有前视眼 THEN X 是食肉动物。R3： IF X 有毛发 THEN X 是哺乳动物,规则应用的解释How ?Why ?R2： IF,产生式系统小结,产生式系统小结描 述优 点缺 点事实库 - 对所有规则操作的,产生式认知模型 产生式系统架构 产生式系统推理机的实现技术 专家系统概述,产生式知识表示及相关专家系统,产生式认知模型产生式知识表示及相关专家系统,何谓专家系统,专家系统是一种具有智能的计算机系统，它能使用某一问题领域的知识为该领域提供”专家级”的服务，能部分或全部地代替领域专家解决本领域的高难度问题。,何谓专家系统专家系统是一种具有智能的计算机系统，它能使用某一,专家系统的分类,按输出结果分类： 输出断言结论：诊断、解释、预测、决策； 输出可执行的方案：设计、规划、控制、调度。,按知识表示分类： 产生式规则，一阶谓词逻辑，框架系统，语义网络，过程型，,按推理模式分类： 精确推理、不确定性推理； 基于规则推理、基于模型推理，基于案例推理。,按规模分类： 大型协同综合型； 微型控制型。,专家系统的分类 按输出结果分类： 按知识表示分类： 按推理模,专家系统的分类,应用问题类型： 解释： 处理大量不完全、受干扰数据，正确解释结果(图象、语音分析) 预测： 根据对象过去和现在的情况，推断其将来演变结果。- 数据随时间变化 （气象、军事、交通、市场等预测） 诊断： 通过观察症状，确定对象的故障和缺陷- 现象与故障之间无严格的对应关系（医疗-MYCIN、机器故障等诊断） 设计： 根据给定性能指标和约束条件，形成方案和图样- 需满足多方约束，协调多种设计要求（XCON、程序自动设计 ） 规划： 根据给定目标，拟定对象的行动计划- 对未来的静态或动态行为作出预测 （机器人、军事行动） 监控： 完成实时检测和控制任务,需对数据快速分析处理 ,专家系统的分类应用问题类型：,专家系统结构,专家系统结构,专家系统设计与实现,专家系统设计与实现,专家系统设计与实现,领域专家: 拥有大量知识和技能、可高效地解决本领域问题的人。,知识工程师：通过抽取领域专家的有用知识，建造AI系统的人。,人工获取：根据最终用户的需求，知识工程师与领域专家合作，挖掘、分析、综合、整理领域知识和专家知识，将其存入知识库。,自动获取：开发机器学习系统，使机器自动从实际问题中获取知识，并填充知识库。,例：类比学习、基于神经网络的训练特性、数据挖掘、知识发现等。,知识获取方法：,最终用户：使用系统的人，决定系统的主要功能和约束指标。,专家系统设计与实现 领域专家: 拥有大量知识和技能、可高效地,专家系统设计与实现,知识管理系统设计：,知识的输入: 系统提供编辑软件或专用的知识编辑系统 知识的组织与维护： 知识库的组织 可按树型结构分层组织元知识、领域知识、专家知识；或分布式大规模知识库 知识的添加、删除、修改、查询、和统计等； 知识的检测: 知识输入时及时检测，发现知识的不一致性、不完整性以及矛盾性,专家系统设计与实现知识管理系统设计： 知识的输入: 系统提供,专家系统设计与实现,知识的一致性、完整性、冗余性检查：,知识的一致性检查 - 知识库中知识应相容，无矛盾：r1: if P then Qr2: if P then Q,知识的完整性检查 - 知识库中知识应满足完整约束条件： 例：F: 小王身高 x 米；约束条件： x 3米。,知识的冗余性检查 - 知识库中知识不应有重复、多余： 例： r1: if p then Q; r2: if Q then R; r3: if P then R.,专家系统设计与实现知识的一致性、完整性、冗余性检查： 知识,思考题,何为专家系统？ 专家系统由哪些部分构成? 各部分的作用如何? 主要实现技术? 将知识库与推理机相分离具有哪些优点?,思考题 何为专家系统？,