1、第 四 章 产生式认知模型及其系统,产 生 式 系 统,引 言： 是AI的一个重要知识表示形式; 常用于构建基于规则专家系统。,要求： 掌握产生式模式及专家系统的体系结构、运行机制及基本实现技术 - 模式匹配、触发规则、冲突解决策略、正向推理、逆向推理、不确定推理等。,产生式系统,产生式认知模型产生式系统 - 基于规则的知识系统架构产生式系统推理机的实现技术专家系统概述,产生式认知模型,马亦可夫Markov（1954）提出控制产生式规则的执行算法： 将一组产生式规则按优先级次序作用输入串； 若较高优先级的规则不可用，则应用下一条规则，如此周而复始; 直到 或规则集合中的规则都不可用，或系统使用
2、了一条以句号结束的规则， 算法结束。,美国数学家 Post（1943）提出产生式规则计算模型：符号逻辑中构造的形式化计算工具，产生式规则: - ；任何数学系统或逻辑系统都可以写成某种类型的产生式系统：任何数学和逻辑系统都可视为一个产生式规则集，指出如何将一串符号变换成另一串符号；计算机程序、巴科斯范式均可视为一种产生式规则。产生式系统具有和图灵机同样的计算能力。,产生式认知模型,规则：（1）xy yx（2） （3） 。,希腊字母、等代表专用符号串；小写字母 x、y 、z 等表示单个字符的变量；专用字符 为空字符串。,输入字符串 ： “ ABC ”,例: 用Markov算法作用于任意给定的字符串
3、。,执行算法过程：规则自左向右地作用输入字符串。,产生式认知模型,纽厄尔和西蒙 Newell & Simon（1972）将产生式模型用于表示人类问题求解的认知模型 ：长期记忆 - 大脑中积累的各种知识和经验（成块的、大容量知识）短时记忆 临时输入的求解某具体问题所需的信息（小容量的、动态变化的知识 ）；认知处理器 - 从长期记忆的成块知识中找出能被当前输入信息激活的那些知识，并有选择地处理执行。,产生式认知模型成为 AI 的一种基本的知识表示形式,产生式系统,产生式认知模型产生式系统 - 基于规则的知识系统架构产生式系统推理机的实现技术专家系统概述,基于产生式认知模型的产生式系统体系结构,长期
4、记忆 -,短时记忆 -,认知处理器 -,工作存储器（事实库、工作库、综合数据库、. ),规则库（长期知识库、 . ）,推理机（控制系统、控制策略、解释程序、.),事实库（短时记忆区 ）：存放问题的初始状态、已知事实、推理的中间结果及结论等。表现形式：符号串、数组、向量、集合、谓词等,基于产生式认知模型的产生式系统体系结构,例：“8数码”问题状态描述 - 矩阵 (Sij)；,“猴子摘香蕉”问题状态描述 - （a，0，b，0）；,“祖孙关系”定理证明谓词描述 Parent ( x，y )。,基于产生式认知模型的产生式系统体系结构,规则库（长期记忆区 ）： 存放一系列规则（算子），用于描述状态的转换
5、关系、前提与结论间的因果关系以及环境条件与执行操作的关系等。 表现形式：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 打开空调；,基于产生式认知模型的产生式系统体系结构,产生式系统推理机工作流程,产生式系统,产生式认知模型产生式系统 - 基于规则的知识系统架构产生式系统推理机的实现技术专家系统概
6、述,规则的匹配（规则的触发，变量的绑定 Bounding ）；规则的选择（规则的选择，冲突解决策略） ；规则的应用（规则的执行：演绎 加入新断言，反应 执行规定操作） 规则推理的不确定性（不确定性推理）规则推理的方向（正向推理 数据驱动，逆向推理 目标驱动）；规则应用的解释（解释问题类型：How, Why ）；记录问题求解过程中规则的应用顺序（输出：解径、解图）；控制系统运行的终止（正常终止，非正常终止）。,产生式系统推理机的实现技术,规则的匹配,从规则库的第一条规则开始，按排列顺序逐条用规则的前提条件与事实库中事实进行匹配；,R: IF (x,0,y,0) THEN (v,0,y,0) ;
7、F: (a,0,b,0) - 新状态: (v,0,b,0),常量置换变量;匹配成功.,由于一次搜索过程中，可能有多条规则同时为事实库中事实所匹配， 需将所有的触发规则送冲突集，应用冲突解决策略选择启用规则。,触发规则: 前提条件为当前事实库所满足的规则.,冲突集: 所有触发规则构成的集合。,规则的匹配（规则的触发，变量的绑定 Bounding ）；规则的选择（规则的选择，冲突解决策略） ；规则的应用（规则的执行：演绎 加入新断言，反应 执行规定操作） 规则推理的不确定性（不确定性推理）规则推理的方向（正向推理 数据驱动，逆向推理 目标驱动）；规则应用的解释（解释问题类型：How, Why ）；
8、记录问题求解过程中规则的应用顺序（输出：解径、解图）；控制系统运行的终止（正常终止，非正常终止）。,产生式系统推理机的实现技术,规则的选择及冲突解决策略,启用规则：从冲突集中选择出的某条合适的可作为当前的执行规则。,冲突解决策略：,反应型系统(Reaction),宽度优先：先进的规则先出（队）；深度优先：后进的规则先出（栈） ；A, A*算法：最有希望达到目标的规则先出；归结推理策略。,演绎型系统(Deduction),规则排序：排在前面的规则优先执行；,专一性排序：条件越具体的规则优先执行；,就近排序：与事实库中最新加入事实匹配的规则优先执行, ( 参见： OPS5 产生式系统语言 ),规则
9、的匹配（规则的触发，变量的绑定 Bounding ）；规则的选择（规则的选择，冲突解决策略） ；规则的应用（规则的执行：演绎 加入新断言，反应 执行规定操作） 规则推理的不确定性（不确定性推理）规则推理的方向（正向推理 数据驱动，逆向推理 目标驱动）；规则应用的解释（解释问题类型：How, Why ）；记录问题求解过程中规则的应用顺序（输出：解径、解图）；控制系统运行的终止（正常终止，非正常终止）。,产生式系统推理机的实现技术,不确定性推理- 知识的不精确、不完整、随机、模糊性.,语义的模糊性- 模糊推理,IF 西红柿红了 THEN 西红柿熟了， 西红柿非常红- 西红柿（？）熟,语义量化，模糊
10、推理。,修饰量化： 非常高 不太高 .,不确定性推理,信息的不确定性： 规则的不确定性 ,IF A流鼻涕&红眼睛THEN A患流感 （CF : 0.67） A患鼻膜过敏（CF : 0.06）,IF 培养液是血液， 细菌的类别不知道， 细菌的染色体是革兰式阴性， 细菌的外伤是杆状，THEN 细菌的类别是假单菌（CF :0.4）,事实的不确定性 A 流鼻涕 ( 0.4 ) A 红眼睛 ( 0.8 ),推理的不确定性： 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 E
11、1 (0.7) R5: IF E6 & (E7 OR E8) THEN E2 (1.0),产生式系统中的不确定性推理,产生式系统中的不确定性推理,E4-E8：原始证据 或观察的事实；判断规则前提条件成立的依据 综合证据的可信度？ E1-E3 ：规则推得的结论的可信度？ H：综合多条规则推得的最终结论的可信度？,产生式系统中的不确定性推理,综合证据的可信度计算：,1、基于模糊集计算方法 取小 ( MYCIN ),从每个证据的可信度中获得规则总输入的可信度。,产生式系统中的不确定性推理,规则推得结论的可信度：,综合多条规则推得结论的可信度：,产生式系统中的不确定性推理,基于模糊理论计算方法 取大
12、( EXPERT),基于概率论方法 （1）,综合多条规则推得结论的可信度：,产生式系统中的不确定性推理,计算流程：1、将各规则的可信度 C 计算规则的可信比例 r ；2、将各规则的可信比例相乘，获多条规则推得的结论的可信比例；3、再将可信比例转换成最终结论的可信度。,设 规则可信比例 ：,规则可信度：,基于概率论方法 （1）,综合多条规则推得结论的可信度：,产生式系统中的不确定性推理,r: 可信比例 c: 可信度,产生式系统中的不确定性推理,常用的推理链计算方法： 确定性因子法 ( MYCIN )； 主观Bayes法 ( Prospector ) ； D-S证据理论； 模糊可能性理论； 。,规
13、则的匹配（规则的触发，变量的绑定 Bounding ）；规则的选择（规则的选择，冲突解决策略） ；规则的应用（规则的执行：演绎 加入新断言，反应 执行规定操作） 规则推理的不确定性（不确定性推理）规则推理的方向（正向推理 数据驱动，逆向推理 目标驱动）；规则应用的解释（解释问题类型：How, Why ）；记录问题求解过程中规则的应用顺序（输出：解径、解图）；控制系统运行的终止（正常终止，非正常终止）。,产生式系统推理机的实现技术,正向推理的产生式系统,特点 - 数据驱动： 从已知事实或命题出发，正向地运用规则，求证目标成立。 被正向使用的规则称为F规则。,例：当前事实库： A ； 目标： G
14、规则集： R1: if A then B and C, R2: if B then D, 推理后事实库： A,B,C ； A,B,C,D ；，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毛发
15、是深褐色； A有花斑点；,演绎型(正向)产生式系统,推理方向： 事实 结论,正向推理的产生式系统,算法中的符号： DB: 存放事实和中间结果的事实库； KB: 存放知识的规则库； RS: 当前所有触发规则构成的冲突集合。,正向推理的产生式系统,正向推理的产生式系统,逆向推理的产生式系统,特点 - 目标驱动： 从假设的待证目标出发，逆向地运用规则，求证所有支持目标所需的条件是否成立。 被逆向使用的规则称为B规则。,例： 假设待证目标： G ； 事实证据库： 规则集： R1: if B and C then G, R2: if D then B, 推理后事实证据库： B,C ； C,D ；,逆向推
16、理的产生式系统实例（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有花斑点；,推理方向： 目标 事实,逆向推理的产生式系统实例（2）,逆向推理的产生式系统,算法中的符号： DB: 存放最终事实和中间证据的
17、事实证据库； KB: 存放知识的规则库； RS: 当前所有触发规则构成的冲突集合。,逆向推理的产生式系统,逆向推理的产生式系统,正（逆）向产生式系统的比较,规则的匹配（规则的触发，变量的绑定 Bounding ）；规则的选择（规则的选择，冲突解决策略） ；规则的应用（规则的执行：演绎 加入新断言，反应 执行规定操作） 规则推理的不确定性（不确定性推理）规则推理的方向（正向推理 数据驱动，逆向推理 目标驱动）；规则应用的解释（解释问题类型：How, Why ）；记录问题求解过程中规则的应用顺序（输出：解径、解图）；控制系统运行的终止（正常终止，非正常终止）。,产生式系统推理机的实现技术,规则应用
18、的解释,必要性： 解释推理过程，帮助使用者理解系统是如何得到结论的；,解释问题类型： 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 是哺乳动物,产生式系统工作流程小结,产生式系统小结,产生式系统,产生式认知模型产生式系统 - 基于规则的知识系统架构产生式系统推理机的实现技术专家系统概述,何谓专家系统,专家系统是一种具
19、有智能的计算机系统，它能使用某一问题领域的知识为该领域提供”专家级”的服务，能部分或全部地代替领域专家解决本领域的高难度问题。,专家系统的分类,按输出结果分类： 输出断言结论：诊断、解释、预测、决策； 输出可执行的方案：设计、规划、控制、调度。,按知识表示分类： 产生式规则，一阶谓词逻辑，框架系统，语义网络，过程型，,按推理模式分类： 精确推理、不确定性推理； 基于规则推理、基于模型推理，基于案例推理。,按规模分类： 大型协同综合型； 微型控制型。,应用问题类型： 解释： 分析大量原始数据，从中推出结果并给出正确解释。 预测： 根据对象过去和现在的情况，推断其将来演变结果。 诊断： 根据观察的
20、症状确定对象的故障和缺陷 设计： 根据给定性能指标和约束条件形成所需的方案和图样 规划： 根据给定目标拟定对象的行动计划 监控： 完成实时的检测和控制任务,需对数据快速分析处理 。,专家系统的分类,专家系统结构,专家系统设计与实现,专家系统设计与实现,领域专家: 拥有大量知识和技能、可高效地解决本领域问题的人。,知识工程师：通过抽取领域专家的有用知识，建造AI系统的人。,人工获取：根据最终用户的需求，知识工程师与领域专家合作，挖掘、分析、综合、整理领域知识和专家知识，将其存入知识库。,自动获取：开发机器学习系统，使机器自动从实际问题中获取知识，并填充知识库。,例：类比学习、基于神经网络的训练特
21、性、数据挖掘、知识发现等。,知识获取方法：,最终用户：使用系统的人，决定系统的主要功能和约束指标。,专家系统设计与实现,知识管理系统设计：,知识的输入: 系统提供的编辑软件; 专用的知识编辑系统 知识的组织与维护： 知识库的组织 可按树型结构分层组织元知识、领域知识、专家知识；或分布式大规模知识库 知识的添加、删除、修改、查询、和统计等； 知识的检测: 知识输入时及时检测，发现知识的不一致性、不完整性以及矛盾性,专家系统设计与实现,知识的一致性、完整性、冗余性检查：,知识的一致性检查 - 知识库中知识应相容，无矛盾：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.,
