产生式系统课件.ppt

1、北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 1产产 生生 式式 系系 统统n引引 言：言：w 是AI的一个重要知识表示形式;w 常用于构建基于规则专家系统专家系统。n 要求：要求：w 掌握产生式模式产生式模式及专家系统专家系统的体系结构、体系结构、运行机制运行机制及基基本实现技术本实现技术 -模式匹配、触发规则、冲突解决策略、正向推理、逆向推理、不确定推理等。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 2产生式系统产生式系统n产生式认知模型产生式认知模型n产生式系统产生式系统 -基于规则

2、的知识系统架构基于规则的知识系统架构n产生式系统推理机的实现技术产生式系统推理机的实现技术n专家系统概述专家系统概述北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 3产生式认知模型产生式认知模型马亦可夫马亦可夫Markov（1954）提出提出控制产生式规则控制产生式规则的的执行算法：执行算法：将一组将一组产生式规则产生式规则按优先级次序作用按优先级次序作用输入串输入串；若较高优先级的规则不可用，则应用下一条规则，如此周而复始若较高优先级的规则不可用，则应用下一条规则，如此周而复始;直到直到 或规则集合中的规则都不可用，或系统使用了一条以句号结束

3、的规则，或规则集合中的规则都不可用，或系统使用了一条以句号结束的规则，算法结束。算法结束。n美国数学家美国数学家 PostPost（19431943）提出提出产生式规则计算模型产生式规则计算模型：w符号逻辑中构造的形式化计算工具，符号逻辑中构造的形式化计算工具，产生式规则产生式规则:-；w任何任何数学系统数学系统或或逻辑系统逻辑系统都可以写成某种类型的都可以写成某种类型的产生式系统产生式系统：任何：任何数学数学和和逻逻辑系统辑系统都可视为一个产生式规则集，指出如何将一串符号都可视为一个产生式规则集，指出如何将一串符号变换变换成另一串符号成另一串符号；计算机程序计算机程序、巴科斯范式巴科斯范式均

4、可视为一种产生式规则。均可视为一种产生式规则。w产生式系统产生式系统具有和具有和图灵机图灵机同样的计算能力。同样的计算能力。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 4产生式认知模型产生式认知模型规则：规则：（1）xy yx（2）（3）。希腊字母希腊字母、等代表专用符号串；等代表专用符号串；小写字母小写字母 x、y、z 等表示单个字符等表示单个字符的变量；的变量；专用字符专用字符 为空字符串。为空字符串。输入字符串输入字符串：“ABC”规则号规则号字符串字符串匹配匹配规则规则条件部分条件部分字符串的新状态字符串的新状态下一步工作下一步工作

5、（1）（2）（3）（1）（1）（1）（2）失败失败 失败失败 成功成功 成功成功 成功成功 失败失败 成功成功ABCABCABCBACBCABCABCA匹配下条规则匹配下条规则匹配匹配下条规则下条规则匹配头条规则匹配头条规则匹配头条规则匹配头条规则匹配头条规则匹配头条规则匹配下条规则匹配下条规则转换完毕，结束转换完毕，结束例例:用Markov算法算法作用于任意给定的字符串。作用于任意给定的字符串。执行算法过程：执行算法过程：规则自左向右地规则自左向右地作用作用输入字符串输入字符串。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 5产生式认知模型

6、产生式认知模型n 纽厄尔和西蒙纽厄尔和西蒙 Newell&SimonNewell&Simon（19721972）将将产生式模型产生式模型用于用于表示表示人类问题求解的人类问题求解的认知模型认知模型 ：长期记忆长期记忆 -大脑中积累的大脑中积累的各种知各种知识和经验（成块的、大容量知识）识和经验（成块的、大容量知识）短时记忆短时记忆 临时输入的求解某具体问题所需的信息（小容量的、动临时输入的求解某具体问题所需的信息（小容量的、动态变化的知识态变化的知识 ）；）；认知处理器认知处理器 -从长期记忆的成块知识中找出从长期记忆的成块知识中找出能能被当前输入信息激活被当前输入信息激活的那些知识，并有选择

7、地处理执行。的那些知识，并有选择地处理执行。产生式认知模型产生式认知模型成为成为 AI 的一种基本的的一种基本的知识表示知识表示形式形式北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 6产生式系统产生式系统n产生式认知模型产生式认知模型n产生式系统产生式系统 -基于规则的知识系统架构基于规则的知识系统架构n产生式系统推理机的实现技术产生式系统推理机的实现技术n专家系统概述专家系统概述北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 7基于产生式认知模型的基于产生式认知模型的产生式系统体系结构产生式

8、系统体系结构长期记忆长期记忆-短时记忆短时记忆-认知处理器认知处理器-工作存储器（工作存储器（事实库事实库、工作库、综合工作库、综合数据库、数据库、.)规则库（长期知识库、规则库（长期知识库、.）推理机推理机（控制系统控制系统、控制策略控制策略、解解释程序、释程序、.).)北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 8n事实库事实库（短时记忆区短时记忆区）：）：w存放问题的存放问题的初始状态初始状态、已知事实已知事实、推理的、推理的中间结果中间结果及及结论结论等。等。w表现形式：符号串、数组、向量、集合、谓词等表现形式：符号串、数组、向量、

9、集合、谓词等基于产生式认知模型的基于产生式认知模型的产生式系统体系结构产生式系统体系结构例：例：“8 8数码数码”问题问题状态状态描述描述 -矩阵矩阵 (S(Sijij)；“猴子摘香蕉猴子摘香蕉”问题问题状态状态描述描述-（a，0，b，0）；“祖孙关系祖孙关系”定理证明定理证明谓词谓词描述描述 Parent(x，y)。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 9基于产生式认知模型的基于产生式认知模型的产生式系统体系结构产生式系统体系结构n 规则库规则库（长期记忆区长期记忆区 ）：）：u 存放一系列规则（算子），用于描述存放一系列规则（算子

10、），用于描述状态的转换状态的转换关系、关系、前提与结论前提与结论间的因果间的因果关系以及关系以及环境条件与执行操作环境条件与执行操作的关系等。的关系等。u 表现形式：表现形式：IFIF 前件前件 THENTHEN 后件后件;IFIF LHS LHS THENTHEN RHS RHS LHS:LHS:本规则触发应满足的条件；本规则触发应满足的条件；RHSRHS：本规则触发后可本规则触发后可产生的结果产生的结果（或应（或应执行的操作执行的操作）n 例例:w R1:IFIF(x,0,y,0(x,0,y,0)THENTHEN(v,0,y,0)(v,0,y,0)；u R2:IFIF likes(x,y)

11、&likes(y,x)likes(x,y)&likes(y,x)THENTHEN friend(x,y)friend(x,y)u R2:IFIF 天气太热天气太热 THENTHEN 打开空调打开空调；北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 10基于产生式认知模型的基于产生式认知模型的产生式系统体系结构产生式系统体系结构 推理机推理机（认知处理器认知处理器)的的基本基本运行算法运行算法:1DATA初始事实库初始事实库 2until DATA 满足结束条件以前，满足结束条件以前，do 3.begin 4 在在所有所有满足满足当前事实库当前事

12、实库 DATADATA 的的规则集合规则集合中，中，选择选择一条规则一条规则 R 5 DATA执行执行R 后得到的结果后得到的结果 6.end北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 11产生式系统推理机工作流程产生式系统推理机工作流程事实库事实库规则启用规则启用北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 12产生式系统产生式系统n产生式认知模型产生式认知模型n产生式系统产生式系统 -基于规则的知识系统架构基于规则的知识系统架构n产生式系统推理机的实现技术产生式系统推理机的实现技术n专

13、家系统概述专家系统概述北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 13u规则的匹配（规则的匹配（规则的规则的触发触发，变量的绑定，变量的绑定 Bounding）；）；u规则的选择（规则的选择（规则的规则的选择选择，冲突解决策略，冲突解决策略）；u规则的应用（规则的应用（规则的规则的执行执行：演绎演绎 加入新断言，加入新断言，反应反应 执行规定操作执行规定操作）u规则推理的不确定性（规则推理的不确定性（不确定性推理不确定性推理）u规则推理的方向（规则推理的方向（正向推理正向推理 数据驱动数据驱动，逆向推理逆向推理 目标驱动目标驱动）；）；u规

14、则应用的解释（规则应用的解释（解释问题类型解释问题类型：How,Why）；）；u记录问题求解过程中规则的应用顺序（输出：记录问题求解过程中规则的应用顺序（输出：解径解径、解图解图）；）；u控制系统运行的终止（控制系统运行的终止（正常正常终止，终止，非正常非正常终止终止）。）。产生式系统推理机的实现技术产生式系统推理机的实现技术北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 14规则的匹配规则的匹配n从从规则库规则库的第一条规则开始，按排列顺序逐条用的第一条规则开始，按排列顺序逐条用规则的前提条件规则的前提条件与与事事实库实库中中事实事实进行匹配

15、；进行匹配；u R:IF(x,0,y,0)THEN(v,0,y,0);F:(a,0,b,0)-新状态:(v,0,b,0)常量常量置换置换变量变量;匹配成功匹配成功.由于一次搜索过程中，可能有多条规则同时为事实库中事实所匹配，由于一次搜索过程中，可能有多条规则同时为事实库中事实所匹配，需将所有的需将所有的触发规则触发规则送送冲突集冲突集，应用冲突解决策略选择应用冲突解决策略选择启用规则启用规则。n触发规则触发规则:前提条件为当前事实库所满足的规则前提条件为当前事实库所满足的规则.n 冲突集冲突集:所有触发规则构成的集合。所有触发规则构成的集合。北京航空航天大学软件开发环境国家重点实验室北京航空航

16、天大学软件开发环境国家重点实验室 Slide 15u规则的匹配（规则的匹配（规则的规则的触发触发，变量的绑定，变量的绑定 Bounding）；）；u规则的选择（规则的选择（规则的规则的选择选择，冲突解决策略，冲突解决策略）；u规则的应用（规则的应用（规则的规则的执行执行：演绎演绎 加入新断言，加入新断言，反应反应 执行规定操作执行规定操作）u规则推理的不确定性（规则推理的不确定性（不确定性推理不确定性推理）u规则推理的方向（规则推理的方向（正向推理正向推理 数据驱动数据驱动，逆向推理逆向推理 目标驱动目标驱动）；）；u规则应用的解释（规则应用的解释（解释问题类型解释问题类型：How,Why）；

17、）；u记录问题求解过程中规则的应用顺序（输出：记录问题求解过程中规则的应用顺序（输出：解径解径、解图解图）；）；u控制系统运行的终止（控制系统运行的终止（正常正常终止，终止，非正常非正常终止终止）。）。产生式系统推理机的实现技术产生式系统推理机的实现技术北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 16规则的选择及冲突解决策略规则的选择及冲突解决策略n启用规则：启用规则：w从冲突集中选择出的某条合适的可作为当前的执行规则。从冲突集中选择出的某条合适的可作为当前的执行规则。n冲突解决策略冲突解决策略：反应型系统反应型系统(Reaction)(R

18、eaction)宽度优先：先进的规则先出（宽度优先：先进的规则先出（队队）；）；深度优先：后进的规则先出（深度优先：后进的规则先出（栈栈）；A,A*算法：最有希望达到目标的规则先出；算法：最有希望达到目标的规则先出；归结推理策略。归结推理策略。演绎型系统演绎型系统(Deduction)规则排序：排在前面的规则优先执行；规则排序：排在前面的规则优先执行；专一性排序：条件越具体的规则优先执行；专一性排序：条件越具体的规则优先执行；就近排序：就近排序：与事实库中最新加入事实匹配的规则优先执行与事实库中最新加入事实匹配的规则优先执行(参见：OPS5 产生式系统语言)北京航空航天大学软件开发环境国家重点

19、实验室北京航空航天大学软件开发环境国家重点实验室 Slide 17u规则的匹配（规则的匹配（规则的规则的触发触发，变量的绑定，变量的绑定 Bounding）；）；u规则的选择（规则的选择（规则的规则的选择选择，冲突解决策略，冲突解决策略）；u规则的应用（规则的应用（规则的规则的执行执行：演绎演绎 加入新断言，加入新断言，反应反应 执行规定操作执行规定操作）u规则推理的不确定性（规则推理的不确定性（不确定性推理不确定性推理）u规则推理的方向（规则推理的方向（正向推理正向推理 数据驱动数据驱动，逆向推理逆向推理 目标驱动目标驱动）；）；u规则应用的解释（规则应用的解释（解释问题类型解释问题类型：H

20、ow,Why）；）；u记录问题求解过程中规则的应用顺序（输出：记录问题求解过程中规则的应用顺序（输出：解径解径、解图解图）；）；u控制系统运行的终止（控制系统运行的终止（正常正常终止，终止，非正常非正常终止终止）。）。产生式系统推理机的实现技术产生式系统推理机的实现技术北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 18不确定性推理不确定性推理-知识的不精确、不完整、随机、模糊性知识的不精确、不完整、随机、模糊性.n 语义的模糊性语义的模糊性-模糊推理模糊推理IF 西红柿红红了 THEN 西红柿熟熟了，西红柿非常非常红红-西红柿（？）熟熟语义量

21、化，模糊推理。语义量化，模糊推理。11.61.751.91.78矮中等高0身高隶属度修饰量化：修饰量化：非常非常高高 不太不太高高 .北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 19不确定性推理不确定性推理n 信息的不确定性：信息的不确定性：w 规则的不确定性规则的不确定性 IF A流鼻涕&红眼睛THEN A患流感 （CF:0.67）A患鼻膜过敏（CF:0.06）IFIF 培养液是血液，细菌的类别不知道，细菌的染色体是革兰式阴性，细菌的外伤是杆状，THENTHEN 细菌的类别是假单菌（CF:0.4CF:0.4）u 事实事实的不确定性的不确定

22、性 A 流鼻涕(0.4)A 红眼睛 (0.8)北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 20推理的不确定性：推理的不确定性：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)产生式系统中的不确定性推理产生式系统中的不确定性推理北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 21产生式系统中的不确定性推理

23、产生式系统中的不确定性推理0.30.90.60.70.30.80.71.00.70.9-0.8v E4-E8：原始证据 或观察的事实；判断规则前提条件成立的依据 综合证据的可信度？综合证据的可信度？v E1-E3：规则推得的规则推得的结论的结论的可信度？可信度？v H：综合多条规则推得的综合多条规则推得的最最终结论的可信度？终结论的可信度？北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 22产生式系统中的不确定性推理产生式系统中的不确定性推理综合证据综合证据的可信度计算：的可信度计算：0.90.51.00.51、基于模糊集计算方法、基于模糊集计

24、算方法 取小取小 (MYCIN)0.90.51.00.452、基于概率论计算方法、基于概率论计算方法 乘积乘积 (PROSPECTOR)从每个证据的可信度从每个证据的可信度中获得规则中获得规则总输入的总输入的可信度。可信度。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 23产生式系统中的不确定性推理产生式系统中的不确定性推理规则推得规则推得结论结论的可信度：的可信度：01.0CinCoutCin01.0Cout01.0CinCout先验值先验值其它的结论可信度计算方法其它的结论可信度计算方法:0.8CinCout0.50.4北京航空航天大学软

25、件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 24综合多条规则推得结论的可信度：综合多条规则推得结论的可信度：产生式系统中的不确定性推理产生式系统中的不确定性推理基于模糊理论计算方法基于模糊理论计算方法 取大取大(EXPERT)0.90.250.9（a）北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 25基于概率论方法基于概率论方法（1）综合多条规则推得结论的可信度：综合多条规则推得结论的可信度：产生式系统中的不确定性推理产生式系统中的不确定性推理1crc计算流程：计算流程：1、将各规则的可信度 C 计算规则的

26、可信比例 r；2、将各规则的可信比例相乘，获多条规则推得的结论的可信比例；3、再将可信比例转换成最终结论的可信度。1rcr设设 规则可信比例规则可信比例：规则可信度：规则可信度：北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 26基于概率论方法基于概率论方法（1）综合多条规则推得结论的可信度：综合多条规则推得结论的可信度：产生式系统中的不确定性推理产生式系统中的不确定性推理10.9r91 0.920.2511 0.25 3r 121933r r r 30.751 3 1rcr1crc1rcr r:可信比例可信比例 c:可信度可信度0.90.75

27、0.25可信度可信度可信度比例可信度比例9 1/3=30.90.250.75北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 27产生式系统中的不确定性推理产生式系统中的不确定性推理常用的推理链计算方法：常用的推理链计算方法：确定性因子法(MYCIN)；主观Bayes法(Prospector)；D-S证据理论；模糊可能性理论；。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 28u规则的匹配（规则的匹配（规则的规则的触发触发，变量的绑定，变量的绑定 Bounding）；）；u规则的选择（规则的选择

28、（规则的规则的选择选择，冲突解决策略，冲突解决策略）；u规则的应用（规则的应用（规则的规则的执行执行：演绎演绎 加入新断言，加入新断言，反应反应 执行规定操作执行规定操作）u规则推理的不确定性（规则推理的不确定性（不确定性推理不确定性推理）u规则推理的方向（规则推理的方向（正向推理正向推理 数据驱动数据驱动，逆向推理逆向推理 目标驱动目标驱动）；）；u规则应用的解释（规则应用的解释（解释问题类型解释问题类型：How,Why）；）；u记录问题求解过程中规则的应用顺序（输出：记录问题求解过程中规则的应用顺序（输出：解径解径、解图解图）；）；u控制系统运行的终止（控制系统运行的终止（正常正常终止，终

29、止，非正常非正常终止终止）。）。产生式系统推理机的实现技术产生式系统推理机的实现技术北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 29正向推理的产生式系统正向推理的产生式系统n 特点特点 -数据驱动：数据驱动：w 从已知事实或命题出发，正向地运用规则，求证目标成从已知事实或命题出发，正向地运用规则，求证目标成立。立。w 被正向使用的规则称为被正向使用的规则称为F F规则规则。例：例：当前事实库：当前事实库：A A ；目标：目标：G G 规则集：规则集：R1:R1:ifif A A thenthen B and C,B and C,R2:R2:

30、ifif B B thenthen D,D,推理后事实库：推理后事实库：A A,B B,C C ；A,A,B B,C C,D D ；，G G 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 30正向推理的产生式系统实例（正向推理的产生式系统实例（1 1）n动物识别产生式系统动物识别产生式系统:G=“A:G=“A是猎豹？是猎豹？”w 已有知识（规则库）：已有知识（规则库）：R1R1：IFIF X X 是食肉动物是食肉动物 X X 毛发是深褐色毛发是深褐色 X X 有花斑点有花斑点 THEN X THEN X 是猎豹。是猎豹。R2R2：IF (X

31、IF (X 是哺乳动物是哺乳动物 )(X)(X 食肉食肉 )(X (X 有尖利的牙齿有尖利的牙齿 X X 有爪子有爪子 X X 有前视眼有前视眼 )THEN X THEN X 是食肉动物。是食肉动物。R3R3：IF X IF X 有毛发有毛发 THEN X THEN X 是哺乳动物是哺乳动物u 已知事实（事实库）：已知事实（事实库）：A A有毛发；有毛发；A A有尖利的牙齿；有尖利的牙齿；A A有爪子；有爪子；A A有前视眼；有前视眼；A A毛发是深褐色；毛发是深褐色；A A有花斑点；有花斑点；北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 3

32、1演绎型演绎型(正向正向)产生式系统产生式系统猎豹猎豹深褐色毛发深褐色毛发有花斑点有花斑点食肉动物食肉动物食肉食肉哺乳动物哺乳动物外形特征外形特征有毛发有毛发尖利的牙齿尖利的牙齿有爪子有爪子前视眼前视眼R3R2R1深褐色毛发深褐色毛发有花斑点有花斑点有毛发有毛发尖利的牙齿尖利的牙齿有爪子有爪子前视眼前视眼推理方向：推理方向：事实事实 结论结论北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 32正向推理的产生式系统正向推理的产生式系统算法中的符号：算法中的符号：DB:存放事实和中间结果的事实库事实库；KB:存放知识的规则库规则库；RS:当前所有触

33、发规则触发规则构成的冲突集合冲突集合。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 33正向推理的产生式系统正向推理的产生式系统初始事实放入事实库 DBDBDB DB 中有目标？KB中有适用适用规则？匹配，将所有触发规则放入冲突集RSRS RS 为空？成功，退出成功，退出失败，退出失败，退出用户要补充新事实？新事实加入事实库 DBDB是否是是否是否否北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 34正向推理的产生式系统正向推理的产生式系统按规定的冲突解决策略从 RS 中选择一条规则执行。执行

34、结果加入事实库 DBAB北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 35逆向推理的产生式系统逆向推理的产生式系统n 特点特点 -目标驱动：目标驱动：w 从假设的待证目标出发，逆向地运用规则，求证所有支从假设的待证目标出发，逆向地运用规则，求证所有支持目标所需的条件是否成立。持目标所需的条件是否成立。w 被逆向使用的规则称为被逆向使用的规则称为B B规则规则。例：例：假设待证目标：假设待证目标：G G ；事实证据库：事实证据库：规则集：规则集：R1:R1:ifif B B and C and C thenthen G G,R2:R2:ifif

35、 D D thenthen B B,推理后事实证据库：推理后事实证据库：B B,C,C ；C,C,D D ；北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 36逆向推理的产生式系统实例（逆向推理的产生式系统实例（1 1）n动物识别产生式系统动物识别产生式系统:G=“A:G=“A是猎豹？是猎豹？”w 已有知识（规则库）：已有知识（规则库）：R1R1：IFIF X X 是食肉动物是食肉动物 X X 毛发是深褐色毛发是深褐色 X X 有花斑点有花斑点 THEN X THEN X 是猎豹。是猎豹。R2R2：IF (X IF (X 是哺乳动物是哺乳动物

36、)(X)(X 食肉食肉 )(X (X 有尖利的牙齿有尖利的牙齿 X X 有爪子有爪子 X X 有前视眼有前视眼 )THEN X THEN X 是食肉动物。是食肉动物。R3R3：IF X IF X 有毛发有毛发 THEN X THEN X 是哺乳动物是哺乳动物u 已知事实（事实库）：已知事实（事实库）：A A有毛发；有毛发；A A有尖利的牙齿；有尖利的牙齿；A A有爪子；有爪子；A A有前视眼；有前视眼；A A毛发是深褐色；毛发是深褐色；A A有花斑点；有花斑点；北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 37推理方向：推理方向：目标目标 事

37、实事实逆向推理的产生式系统实例（逆向推理的产生式系统实例（2 2）猎豹猎豹有花斑点有花斑点食肉动物食肉动物食肉食肉哺乳动物哺乳动物外形特征外形特征有毛发有毛发尖利的牙齿尖利的牙齿有爪子有爪子前视眼前视眼R3R2R1深褐色毛发深褐色毛发深褐色毛发深褐色毛发有花斑点有花斑点有毛发有毛发尖利的牙齿尖利的牙齿有爪子有爪子前视眼前视眼北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 38逆向推理的产生式系统逆向推理的产生式系统算法中的符号：算法中的符号：DB:存放最终事实和中间证据的事实证据库事实证据库；KB:存放知识的规则库规则库；RS:当前所有触发规则

38、触发规则构成的冲突集合冲突集合。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 39逆向推理的产生式系统逆向推理的产生式系统假设待证目标DBDB有支持目标的事实KB中有支持目标的规则匹配，将所有触发规则放入冲突集RSRS目标成立，退出目标成立，退出事实支持假设目标，事实送 DBDB 用户补充新事实？询问用户是否是否是否AB 目标不成立目标不成立,退出退出 RS 为空？是否北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 40A选择规则的一个前提条件作为新的待证目标。B从 RS 中选择一条触发规则逆

39、向推理的产生式系统逆向推理的产生式系统北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 41正（逆）向产生式系统的比较正（逆）向产生式系统的比较特点特点正向推理正向推理逆向推理逆向推理推理驱动方式推理驱动方式数据驱动目标驱动优点优点算法简单，易于实现搜索目的性强，推理效率高 缺点缺点1、搜索目的性弱，可能求解出多个无关的结论；2、匹配时，要遍历整个规则库，推理效率低。1、确定目标的时候，具有盲目性，可能产生假目标2、当规则的后件是操作而非断言时，即反应型系统，不宜使用此法 用途用途主要用于已知初始数据，不知目标的推理；或是解解空间空间大的一类推理

40、。主要用于结论单一或已知目标求证的一类推理。应用应用监控、预测、规划、设计等选择、分类、故障诊断等北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 42u规则的匹配（规则的匹配（规则的规则的触发触发，变量的绑定，变量的绑定 Bounding）；）；u规则的选择（规则的选择（规则的规则的选择选择，冲突解决策略，冲突解决策略）；u规则的应用（规则的应用（规则的规则的执行执行：演绎演绎 加入新断言，加入新断言，反应反应 执行规定操作执行规定操作）u规则推理的不确定性（规则推理的不确定性（不确定性推理不确定性推理）u规则推理的方向（规则推理的方向（正向推

41、理正向推理 数据驱动数据驱动，逆向推理逆向推理 目标驱动目标驱动）；）；u规则应用的解释（规则应用的解释（解释问题类型解释问题类型：How,Why）；）；u记录问题求解过程中规则的应用顺序（输出：记录问题求解过程中规则的应用顺序（输出：解径解径、解图解图）；）；u控制系统运行的终止（控制系统运行的终止（正常正常终止，终止，非正常非正常终止终止）。）。产生式系统推理机的实现技术产生式系统推理机的实现技术北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 43规则应用的解释规则应用的解释n 必要性：必要性：w 解释推理过程，帮助使用者理解系统是如何得到

42、解释推理过程，帮助使用者理解系统是如何得到结论的；结论的；n 解释问题类型：解释问题类型：w How did you come to this result?How did you come to this result?w Why do you want know this fact?Why do you want know this fact?北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 44规则应用的解释规则应用的解释How?食肉动物食肉动物Why?有毛发有毛发R2R2：IF IF X X 是哺乳动物是哺乳动物 X X 有尖利的牙齿有尖

43、利的牙齿 X X 有爪子有爪子 X X 有前视眼有前视眼 THENTHEN X X 是食肉动物是食肉动物。R3R3：IFIF X X 有毛发有毛发 THENTHEN X X 是哺乳动物是哺乳动物食肉动物食肉动物哺乳动物哺乳动物有毛发有毛发前视眼前视眼爪子爪子利齿利齿R3R2北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 45产生式系统产生式系统工作流程小结事实库事实库规则启用规则启用北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 46产生式系统产生式系统小结小结描描 述述优优 点点缺缺 点点事实

44、库事实库 -对所有规则操对所有规则操作的唯一场所。作的唯一场所。系统结构简单明了，易于理解。规则之间无直接调用关系，相互关系不清楚，系统功能不易把握。规则规则 经验知识块经验知识块 同一表示形式，容易理解、定义。规则之间相互独立，具有高度模块化。推理推理推理机制简单、推理步骤独立，便于跟踪、解释。需对所有规则进行模式匹配，搜索效率低下。推理控制方式单一，缺乏灵活性。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 47产生式系统产生式系统n产生式认知模型产生式认知模型n产生式系统产生式系统 -基于规则的知识系统架构基于规则的知识系统架构n产生式系

45、统推理机的实现技术产生式系统推理机的实现技术n专家系统概述专家系统概述北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 48何谓专家系统何谓专家系统w 专家系统专家系统是一种具有智能的是一种具有智能的计算机系统计算机系统，它能，它能使用某一问题领域的知识为该领域提供使用某一问题领域的知识为该领域提供”专家级专家级”的服务，能部分或全部地代替的服务，能部分或全部地代替领域专家领域专家解决本解决本领域的高难度问题。领域的高难度问题。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 49专家系统的分类专家

46、系统的分类w 按按输出结果输出结果分类：分类：输出输出断言断言结论结论：诊断、解释、预测、决策；诊断、解释、预测、决策；输出可执行的输出可执行的方案方案：设计、规划、控制、调度。设计、规划、控制、调度。u 按按知识表示知识表示分类：分类：产生式规则，一阶谓词逻辑，框架系统，语义网络，过程型，产生式规则，一阶谓词逻辑，框架系统，语义网络，过程型，u 按按推理模式推理模式分类：分类：精确推理、不确定性推理；精确推理、不确定性推理；基于规则基于规则推理推理、基于模型推理，基于案例基于模型推理，基于案例推理。推理。u 按按规模规模分类：分类：大型协同综合型；大型协同综合型；微型控制型。微型控制型。北京

47、航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 50w 应用问题类型：应用问题类型：w 解释：解释：分析大量原始数据，分析大量原始数据，从中推出结果并给出正确解释从中推出结果并给出正确解释。w 预测：预测：根据对象过去和现在的情况，推断其将来演变结果。根据对象过去和现在的情况，推断其将来演变结果。w 诊断：诊断：根据观察的症状确定对象的故障和缺陷根据观察的症状确定对象的故障和缺陷w 设计：设计：根据给定性能指标和约束条件形成所需的方案和图样根据给定性能指标和约束条件形成所需的方案和图样w 规划：规划：根据给定目标拟定对象的行动计划根据给定目标拟定对

48、象的行动计划w 监控：监控：完成实时的检测和控制任务完成实时的检测和控制任务,需对数据快速分析处理需对数据快速分析处理w 。专家系统的分类专家系统的分类北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 51专家系统结构专家系统结构北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 52专家系统设计与实现专家系统设计与实现北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 53专家系统设计与实现专家系统设计与实现w 领域专家领域专家:拥有大量拥有大量知识和技

49、能、可高效地知识和技能、可高效地解决本领域问题的人。解决本领域问题的人。w 知识工程师知识工程师：通过通过抽取领域专家的有用知识，建造抽取领域专家的有用知识，建造AIAI系统的人。系统的人。w 人工获取：人工获取：根据根据最终用户最终用户的需求，的需求，知识工程师知识工程师与与领域专家领域专家合作，合作，挖掘、分析、综合、整理挖掘、分析、综合、整理领域知识领域知识和和专家知识专家知识，将其存入知识库。，将其存入知识库。w 自动获取：自动获取：开发机器学习系统，使机器自动从实际问题中获取知开发机器学习系统，使机器自动从实际问题中获取知识，并填充知识库。识，并填充知识库。w 例：例：类比学习、基于

50、神经网络的训练特性、数据挖掘、知识发现等。类比学习、基于神经网络的训练特性、数据挖掘、知识发现等。知识获取方法：知识获取方法：w 最终用户最终用户：使用系统的人，决定系统的主要功能和约束指标使用系统的人，决定系统的主要功能和约束指标。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 54专家系统设计与实现专家系统设计与实现知识管理系统知识管理系统设计：设计：w 知识的输入知识的输入:系统提供的编辑软件系统提供的编辑软件;专用的知识编辑系统专用的知识编辑系统w 知识的组织与维护：知识的组织与维护：w 知识库的组织知识库的组织 可按树型结构分层组织可