第四章产生式系统

第四章产生式系统第一页，共五十七页，编辑于2023年，星期五引言：是AI的一个重要知识表示形式;

常用于构建基于规则专家系统。

要求：

掌握产生式模式及专家系统体系结构、运行机制及基本实现技术-模式匹配、触发规则、冲突解决策略、正向推理、逆向推理、不确定推理基本概念等。产生式知识表示及相关专家系统第二页，共五十七页，编辑于2023年，星期五产生式知识表示及相关专家系统

产生式认知模型产生式系统架构产生式系统推理机的实现技术专家系统概述第三页，共五十七页，编辑于2023年，星期五产生式认知模型马亦可夫Markov（1954）提出基于产生式的符号变换控制算法：

将一组产生式规则按优先级次序作用输入串；若较高优先级的规则不可用，则应用下一条规则，如此周而复始;直到或规则集合中的规则都不可用，或系统使用了一条以句号结束的规则，算法结束。美国数学家E.Post（1943）提出：用符号语言构造产生式计算模型： <前件>-><后件>指出:任何数学系统、逻辑系统都可视为一个产生式集合，规定如何将一个符号串变换成另一个符号串。(计算机程序、巴科斯范式也亦如此)证明:产生式计算模型具有和图灵机同样的计算能力。第四页，共五十七页，编辑于2023年，星期五产生式认知模型规则：（1）αxy→yαx

（2）α→^

（3）^→α。希腊字母α、β等代表专用符号串；小写字母x、y

、z

等表示单个字符的变量；专用字符^

为空字符串。输入字符串：“^ABC”规则号字符串匹配规则条件部分字符串的新状态下一步工作（1）（2）（3）（1）（1）（1）（2）失败失败成功成功成功失败成功^ABC^ABCαABCBαACBCαABCαABCA匹配下条规则匹配下条规则匹配头条规则匹配头条规则匹配头条规则匹配下条规则转换完毕，结束例:

用Markov算法作用于任意给定的字符串。执行算法过程：规则自左向右地作用输入字符串。第五页，共五十七页，编辑于2023年，星期五产生式认知模型纽厄尔和西蒙Newell&Simon（1972）：总结人类的认知模型：长期记忆-大脑中积累的知识和经验部分（大容量的、松散的、表现为认识-行为的知识块）短时记忆

–由感官输入的信息以及求解具体问题所需的、临时存放的知识块（小容量的动态变化的知识）；认知处理器–人类求解问题可视为从长期记忆的成块知识中找出由当前输入信息激活的那些知识块，并按优先级排序有选择地执行某个知识快的过程

产生式规则计算模型与人类认知模型相对应，成为AI的一种基本的知识表示形式–产生式系统。第六页，共五十七页，编辑于2023年，星期五

产生式认知模型产生式系统架构产生式系统推理机的实现技术专家系统概述产生式知识表示及相关专家系统第七页，共五十七页，编辑于2023年，星期五长期记忆

---短时记忆

---认知处理器

---工作存储器（事实库、工作库、综合数据库、….)规则库（长期知识库、….）推理机（控制系统、控制策略、解释程序、….)产生式系统架结构第八页，共五十七页，编辑于2023年，星期五推理机（控制系统）规则库事实库（综合数据库）产生式系统架结构第九页，共五十七页，编辑于2023年，星期五

规则库（长期记忆区）：

存放一系列规则（算子），用于描述状态的转换关系、前提与结论间的因果关系以及环境条件与执行操作的关系等。表现形式：IF前件THEN后件; IFLHSTHENRHS 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

打开空调；产生式系统架结构第十页，共五十七页，编辑于2023年，星期五事实库（短时记忆区

）：存放问题的初始状态、已知事实、推理的中间结果及结论等。表现形式：符号串、数组、向量、集合、谓词等例：“8数码”问题状态描述-矩阵

(Sij)；“猴子摘香蕉”问题状态描述-（a，0，b，0）；“祖孙关系”定理证明谓词描述–Parent(x，y)。产生式系统架结构第十一页，共五十七页，编辑于2023年，星期五

推理机的基本运行算法:1．DATA 初始事实库

2．untilDATA满足结束条件以前，do3.begin4．

在所有满足当前事实库

DATA的规则集合中，选择一条规则R5．

DATA 执行R后得到的结果

6.end产生式系统架结构第十二页，共五十七页，编辑于2023年，星期五产生式系统推理机工作流程事实库规则启用第十三页，共五十七页，编辑于2023年，星期五

产生式认知模型产生式系统架构产生式系统推理机的实现技术专家系统概述产生式知识表示及相关专家系统第十四页，共五十七页，编辑于2023年，星期五规则的匹配（规则的触发，变量的绑定–Bounding

）；规则的选择（规则的选择，冲突解决策略）；规则的应用（规则的执行，演绎–加入新断言，反应–执行规定操作）规则推理的不确定性（不确定性推理）规则推理的方向（正向推理–数据驱动，逆向推理–目标驱动）；规则应用的解释（解释问题类型，How,Why

）；记录问题求解过程中规则的应用顺序（输出，解径、解图）；控制系统运行的终止（正常终止，非正常终止）。

产生式系统推理机的实现技术第十五页，共五十七页，编辑于2023年，星期五规则的匹配从规则库的第一条规则开始，按排列顺序逐条用规则的前提条件与事实库中事实进行匹配；

R:IF(x,0,y,0)THEN(v,0,y,0)F:(a,0,b,0)------------------------------------

新状态:(v,0,b,0)常量置换变量;合一匹配成功.

由于一次搜索过程中，可能有多条规则同时为事实库中事实所匹配，需将所有的触发规则送冲突集，应用冲突解决策略选择启用规则。触发规则:前提条件为当前事实库所满足的规则.

冲突集:

所有触发规则构成的集合。第十六页，共五十七页，编辑于2023年，星期五规则的匹配（规则的触发，变量的绑定–Bounding

）；规则的选择（规则的选择，冲突解决策略）；规则的应用（规则的执行：演绎–加入新断言，反应–执行规定操作）规则推理的不确定性（不确定性推理）规则推理的方向（正向推理–数据驱动，逆向推理–目标驱动）；规则应用的解释（解释问题类型：How,Why

）；记录问题求解过程中规则的应用顺序（输出：解径、解图）；控制系统运行的终止（正常终止，非正常终止）。

产生式系统推理机的实现技术第十七页，共五十七页，编辑于2023年，星期五规则的选择及冲突解决策略启用规则：从冲突集中选择出的某条合适的可作为当前的执行规则。冲突解决策略：反应型系统(Reaction)演绎型系统(Deduction)规则排序：排在前面的规则优先执行；

专一性排序：条件越具体的规则优先执行；

就近排序：与事实库中最新加入事实匹配的规则优先执行………(参见：OPS5–

产生式系统语言)

上下文排序：特定时间段内只从某上下文有关规则组内选择执行第十八页，共五十七页，编辑于2023年，星期五规则的匹配（规则的触发，变量的绑定–Bounding

）；规则的选择（规则的选择，冲突解决策略）；规则的应用（规则的执行：演绎–加入新断言，反应–执行规定操作）规则推理的不确定性（不确定性推理）规则推理的方向（正向推理–数据驱动，逆向推理–目标驱动）；规则应用的解释（解释问题类型：How,Why

）；记录问题求解过程中规则的应用顺序（输出：解径、解图）；控制系统运行的终止（正常终止，非正常终止）。

产生式系统推理机的实现技术第十九页，共五十七页，编辑于2023年，星期五

概念的模糊性-模糊推理IF西红柿红了THEN西红柿熟了，西红柿非常红-----------------------------------------------

西红柿（？）熟11.61.751.91.78矮中等高0身高隶属度修饰量化：

非常高

不太高

…..不确定性推理-信息的不精确、不完整、模糊性第二十页，共五十七页，编辑于2023年，星期五

信息的不精确性：规则的不确定性–

IF

A流鼻涕&红眼睛THENA患流感（CF:0.67）

A患鼻膜过敏（CF:0.06）IF

培养液是血液， 细菌的类别不知道， 细菌的染色体是革兰式阴性，细菌的外伤是杆状，THEN

细菌的类别是假单菌（CF:0.4）

事实的不确定性–

A流鼻涕(0.4)A红眼睛(0.8)不确定性推理-信息的不精确、不完整、模糊性第二十一页，共五十七页，编辑于2023年，星期五

R1:ifE1thenH (0.9)R2:ifE2thenH (0.7)R3:ifE3thenH (0.8)R4:ifE4&E5thenE1 (0.7)R5:ifE6&(E7ORE8)thenE2(1.0)不确定性推理事实证据:

E3

E4(0.9)E5(0.6)E6(0.7)E7(0.3)E8(0.8)原始证据或观察的事实是判断规则前提条件成立的依据–例，E4，E51、组合证据的不确定性计算？第二十二页，共五十七页，编辑于2023年，星期五0.30.90.60.70.30.80.71.00.70.9-0.8不确定性推理2、推理过程的不确定性计算？

-包括一步推理与推理链结论的计算，例，E1，E2；3、多条规则的结论合成的不确定性计算？-例，H。第二十三页，共五十七页，编辑于2023年，星期五一、组合证据的不确定性计算：证据合取：从每个证据的可信度中获得证据总体的可信度。0.90.51.00.51）、基于模糊集计算方法–取小

(MYCIN-6.3节)0.90.51.00.452）、基于概率论计算方法–

乘积

(PROSPECTOR–6.4节)不确定性推理第二十四页，共五十七页，编辑于2023年，星期五01.0CinCoutCin01.0Cout01.0CinCout先验值先验值

0.8CinCout0.50.4不确定性推理二、推理过程结论（一步推理）的不确定性计算：结论可信度一般计算方法:规则条件可信度与结论可信度之间存在某种关系–规则的可信度（系数）第二十五页，共五十七页，编辑于2023年，星期五基于模糊理论计算方法–取大

(EXPERT)0.90.250.9（a）不确定性推理三、多条规则结论合成的可信度计算：H第二十六页，共五十七页，编辑于2023年，星期五基于概率论方法（1）计算流程：1、由各规则的可信度C与不可信度1-C计算规则的可信比例r；2、将各规则的可信比例相乘，获多条规则推得的结论的可信比例；3、再将可信比例转换成最终结论的可信度。设规则可信比例：规则可信度：

不确定性推理三、多条规则结论合成的可信度计算：第二十七页，共五十七页，编辑于2023年，星期五基于概率论方法（1）

r:可信比例c:可信度0.90.750.25可信度可信度比例9×1/3=30.90.250.75不确定性推理三、多条规则结论合成的可信度计算：H第二十八页，共五十七页，编辑于2023年，星期五常用的不确定性推理计算方法：

确定性因子法(MYCIN)；主观Bayes法(Prospector)

；

D-S证据理论；模糊可能性理论；

……不确定性推理第二十九页，共五十七页，编辑于2023年，星期五规则的匹配（规则的触发，变量的绑定–Bounding

）；规则的选择（规则的选择，冲突解决策略）；规则的应用（规则的执行：演绎–加入新断言，反应–执行规定操作）规则推理的不确定性（不确定性推理）规则推理的方向（正向推理–数据驱动，逆向推理–目标驱动）；规则应用的解释（解释问题类型：How,Why

）；记录问题求解过程中规则的应用顺序（输出：解径、解图）；控制系统运行的终止（正常终止，非正常终止）。

产生式系统推理机的实现技术第三十页，共五十七页，编辑于2023年，星期五正向推理的产生式系统例：当前事实库： {A}；目标：G

规则集： {R1:ifAthenBandC, R2:ifBthenD,……}

推理后事实库：{A,B,C}；{A,B,C,D}；…；{…，G}

特点： 数据驱动。规则形式：<前件>-><后件>

操作： 用已知事实去匹配规则的前件，正向地运用规则， 求证目标成立的过程。概念： 被正向使用的规则称为F规则。

第三十一页，共五十七页，编辑于2023年，星期五正向推理的产生式系统实例（1）动物识别产生式系统:G=“A是猎豹？”

已有知识（规则库）：R1：

IF

X是食肉动物∧X毛发是深褐色∧X有花斑点

THENX是猎豹。R2：

IF(X是哺乳动物)∨(X食肉)∨(X有尖利的牙齿∧X有爪子∧X有前视眼)THENX是食肉动物。R3：IFX有毛发

THENX是哺乳动物

已知事实（事实库）：

A有毛发；A有尖利的牙齿；A有爪子；A有前视眼；

A毛发是深褐色；A有花斑点；第三十二页，共五十七页，编辑于2023年，星期五猎豹深褐色毛发有花斑点食肉动物食肉哺乳动物外形特征有毛发尖利的牙齿有爪子前视眼R3R2R1深褐色毛发有花斑点有毛发尖利的牙齿有爪子前视眼推理方向：

事实结论正向推理的产生式系统实例（1）第三十三页，共五十七页，编辑于2023年，星期五正向推理的产生式系统算法中的符号：

DB:存放事实和中间结果的事实库；

KB:存放知识的规则库；

RS:当前所有触发规则构成的冲突集合。

第三十四页，共五十七页，编辑于2023年，星期五正向推理的产生式系统初始事实放入事实库DBDB

中有目标？KB中有前件为DB满足的规则？匹配，将所有触发规则放入冲突集RS

RS

为空？成功，退出失败，退出用户要补充新事实？

新事实加入事实库DB是否是是否是否否第三十五页，共五十七页，编辑于2023年，星期五正向推理的产生式系统按规定的冲突解决策略从RS中选择一条规则执行。执行结果加入事实库DBAB第三十六页，共五十七页，编辑于2023年，星期五逆向推理的产生式系统例：假设待证目标： {G}；事实证据库：{}

规则集： {R1:ifBandCthenG, R2:ifDthenB,……}

推理后事实证据库：

{B,C}；{C,D}；……

特点： 目标驱动：规则形式：<前件>-><后件>

操作： 用假设的待证目标去匹配规则的后件，逆向地运用规则， 求证所有支持目标所需的前提条件均成立的过程。概念：被逆向使用的规则称为B规则。

第三十七页，共五十七页，编辑于2023年，星期五逆向推理的产生式系统实例（1）动物识别产生式系统:G=“A是猎豹？”

已有知识（规则库）：R1：

IF

X是食肉动物∧X毛发是深褐色∧X有花斑点

THENX是猎豹。R2：

IF(X是哺乳动物)∨(X食肉)∨(X有尖利的牙齿∧X有爪子∧X有前视眼)THENX是食肉动物。R3：IFX有毛发

THENX是哺乳动物

已知事实（事实库）：

A有毛发；A有尖利的牙齿；A有爪子；A有前视眼；

A毛发是深褐色；A有花斑点；第三十八页，共五十七页，编辑于2023年，星期五推理方向：

目标事实逆向推理的产生式系统实例（2）猎豹有花斑点食肉动物食肉哺乳动物外形特征有毛发尖利的牙齿有爪子前视眼R3R2R1深褐色毛发深褐色毛发有花斑点有毛发尖利的牙齿有爪子前视眼第三十九页，共五十七页，编辑于2023年，星期五逆向推理的产生式系统算法中的符号：

DB:存放最终事实和中间证据的事实证据库；

KB:存放知识的规则库；

RS:当前所有触发规则构成的冲突集合。

第四十页，共五十七页，编辑于2023年，星期五逆向推理的产生式系统假设待证目标DB有支持目标的事实KB中有后件支持(子)目标的规则？匹配，将所有触发规则放入冲突集RS目标成立，退出事实支持假设目标，事实送DB用户补充新事实？

询问用户是否是否是否AB

目标不成立,退出

RS

为空？是否第四十一页，共五十七页，编辑于2023年，星期五A选择规则的一个前提条件作为新的待证目标。B从RS中选择一条触发规则逆向推理的产生式系统第四十二页，共五十七页，编辑于2023年，星期五正（逆）向产生式系统的比较特点正向推理逆向推理推理驱动方式数据驱动目标驱动优点算法简单，易于实现搜索目的性强，推理效率高

缺点1、搜索目的性弱，可能求解出多个无关的结论；2、匹配时，要遍历整个规则库，推理效率低。1、确定目标的时候，具有盲目性，可能产生假目标2、当规则的后件是操作而非断言时，即反应型系统，不宜使用此法

用途主要用于已知初始数据，不知目标的推理；或是解空间大的一类推理。主要用于结论单一或已知目标求证的一类推理。应用监控、预测、规划、设计等选择、分类、故障诊断等第四十三页，共五十七页，编辑于2023年，星期五规则的匹配（规则的触发，变量的绑定–Bounding

）；规则的选择（规则的选择，冲突解决策略）；规则的应用（规则的执行：演绎–加入新断言，反应–执行规定操作）规则推理的不确定性（不确定性推理）规则推理的方向（正向推理–数据驱动，逆向推理–目标驱动）；规则应用的解释（解释问题类型：How,Why

）；记录问题求解过程中规则的应用顺序（输出：解径、解图）；控制系统运行的终止（正常终止，非正常终止）。

产生式系统推理机的实现技术第四十四页，共五十七页，编辑于2023年，星期五规则应用的解释

必要性：

解释推理过程，帮助使用者理解系统是如何得到结论的；

解释问题类型：

Howdidyoucometothisresult?Whydoyouwantknowthisfact?第四十五页，共五十七页，编辑于2023年，星期五规则应用的解释How?食肉动物正向推理Why?有利齿逆向推理R2：IFX是哺乳动物∧X有尖利的牙齿∧

X有爪子∧X有前视眼

THENX是食肉动物。R3：IFX有毛发

THENX是哺乳动物食肉动物哺乳动物有毛发前视眼爪子利齿R3R2第四十六页，共五十七页，编辑于2023年，星期五产生式系统小结描述优点缺点事实库-对所有规则操作的唯一场所。系统结构简单明了，易于理解。规则–

经验知识块

具有统一的表示形式，容易理解、定义。规则之间无直接调用关系，相互关系不清楚，系统功能不易把握。对某些规则的修改、扩充，可能造成与其它规则的矛盾，规则库的一致性维护困难。

规则之间相互独立，具有高度模块化。

推理机-控制推理机制简单、推理步骤独立，便于跟踪、解释。需对所有规则进行模式匹配，搜索效率低下。推理控制方式单一，缺乏灵活性。第四十七页，共五十七页，编辑于2023年，星期五

产生式认知模型产生式系统架构产生式系统推理机的实现技术专家系统概述产生式知识表示及相关专家系统第四十八页，共五十七页，编辑于2023年，星期五何谓专家系统专家系统是一种具有智能的计算机系统，它能使用某一问题领域的知识为该领域提供”专家级”的服务，能部分或全部地代替领域专家解决本领域的高难度问题。第四十九页，共五十七页，编辑于2023年，星期五专家系统的分类

按输出结果分类：输出断言结论： 诊断、解释、预测、决策；

输出可执行的方案：设计、规划、控制、调度。

按知识表示分类：产生式规则，一阶谓词逻辑，框架系统，语义网络，过程型，……

按推理模式分类：精确推理、不确定性推理；基于规则推理、基于模型推理，基于案例推理。

按规模分类：大型协同综合型；微型控制型。第五十页，共五十七页，编辑于2023年，星期五专家系统的分类应用问题类型：

解释：处理大量不完全、受干扰数据，正确解释结果(图象、语音分析)

预测：根据对象过去和现在的情况，推断其将来演变结果。- 数据随时间变化（气象、军事、交通、市场等预测）诊断：通过观察症状，确定对