专家系统-2哈尔滨工业大学管理学院阎相斌xbyan@产生式规则专家系统•产生式系统（Production System）是1943年Post提出的一种计算形式体系里所使用的术语，主要是使用类似于文法的规则，对符号串作替换运算。

从60年代开始，成为认知心理学研究人类心理活动中信息加工过程的基础，并用它来建立人类认知模型。

产生式系统形式上很简单，但在一定意义上模仿了人类思考的过程，因此它成为了专家系统的最基本的结构单元或基本模式。

产生式系统的基本组成•组成三要素：–一个综合数据库(Globle Database）—存放信息–一组产生式规则(Rules) —知识–一个控制系统(Control System/ControlStrategies) —规则的解释或执行程序，即控制策略•综合数据库：–是人工智能产生式系统所使用的主要数据结构，它用来表述问题状态或有关事实，即它含有所求解问题的信息。

•产生式规则：–其一般形式为“条件-> 行动”或“前提->结论”即表示成“if...then...”的形式；–“前提”规定了规则可应用的先决条件，“结论”描述了应用这条规则所采取的行动或得出的结论。

–一条产生式规则满足了应用的先决条件之后，就可对综合数据库进行操作，使其发生变化。

•控制系统或控制策略：–是规则的解释程序，规定了如何选择一条可应用的规则对综合数据库进行操作，即决定问题求解过程控制策略控制策略其作用是说明下一步应该选用什么规则，也就是如何应用规则。

通常从选择规则到执行操作分3步：匹配、冲突解决和操作。

(1) 匹配(2) 冲突解决当有一条以上规则的条件部分和当前数据库相匹配时，就需要决定首先使用哪一条规则，这称为冲突解决。

(3) 操作操作就是执行规则的操作部分，经过操作以后，当前数据库将被修改。

然后，其他的规则有可能被使用。

产生式系统的优点•在研究人类进行问题求解过程时，完全可以用一个产生式系统来模拟求解过程，即作为描述搜索的一种有效方法。

•可以用来模拟任一可计算过程，特别适合于模拟强数据驱动特点的智能行为：当一些新的数据输入时，系统的行为就改变•易于添加新规则去适应新的情况，而不破坏系统的其它部分产生式系统应用示例:传教士与野人问题•传教士与野人问题（M-C问题）问题：N个传教士，N个野人，一条船，可同时乘坐k个人乘渡。

问：传教士为安全起见，应如何规定摆渡方案，使得任何时刻，河两岸以及船上的野人数目总是不超过传教士的数目。

•以N=3，k=2为例求解。

图中L和R表示左岸和右岸，B=1或0表示有船或无船，约束条件是：两岸上M>=C,船上M+C<=2：左岸右岸L R L R m 3 0 m 0 3c 3 0 c 0 3B 1 0 B 0 1（初始状态）（目标状态）1，综合数据库（m, c, b)，其中：c≤m, c≤3, b ∈{0, 1}2，初始状态（3，3，1）3，目标状态（结束状态）（0，0，0）4，规则集IF (m, c, 1) THEN (m-1, c, 0) IF (m, c, 1) THEN (m, c-1, 0) IF (m, c, 1) THEN (m-1, c-1, 0) IF (m, c, 1) THEN (m-2, c, 0) IF (m, c, 1) THEN (m, c-2, 0)IF (m, c, 0) THEN (m+1, c, 1)IF (m, c, 0) THEN (m, c+1, 1)M-C问题（续４）IF (m, c, 0) THEN (m+1, c+1, 1)IF (m, c, 0) THEN (m+2, c, 1)IF (m, c, 0) THEN (m, c+2, 1)也可以定义为：IF (m, c, 1) AND 1 ≤i+j≤2 THEN (m-i, c-j, 0)IF (m, c, 0) AND 1 ≤i+j≤2 THEN (m+i, c+j, 0)M-C问题（续5）N＝3的M-C问题，状态空间的总状态数为4X4X2＝32，根据约束条件的要求，可以看出只有20个合法状态。

再进一步分析后，又发现有4个合法状态实际上是不可能达到的。

因此实际的问题空间仅由16个状态构成。

(0 0 1)达不到/(1 2 1)不合法问题状态空间图产生式规则知识允许有如下的特点：⒈相同的条件可以得出不同的结论。

⒉相同的结论可以由不同的条件来得到。

⒊条件之间可以是“与”（AND ）连接和“或”（OR ）连接⒋一条规则中的结论，可以是另一条规则中的条件。

if A then B , 简化为: A →B 产生式规则知识:由以上特点，规则集能做到：⒈能描述和解决各种不同的灵活的实际问题。

（由前三点特点形成）⒉能把规则集中的所有规则连成一棵“与、或”推理树（知识树）。

即这些规则集之间是有关联的（由后二个特点形成）。

产生式规则专家系统基本原理（1）正向推理正、反向推理过程一种简单的产生式系统基本原理正、反向推理过程（2）逆(反)向推理逆向推理是从目标开始，寻找以此目标为结论的规则，并对该规则的前提进行判断，若该规则的前提中某个子项是另一规则的结论时，再找以此结基本原理推理树（知识树）一棵树“与”“或”“与或”推理树。

3.1 基本原理3.1.2 推理树（知识树）“与、或”推理树。

GA B CI J K L M EX F W Z P Q基本原理反向推理过程1）推理树的深度优先搜索在计算机中实现时，利用规则栈来完成。

当调用此规则时，把它压入栈内（相当于对树的搜索），当此规则的结论已求出（yes或no）时，需要将此规则退栈（相当于对树的回溯）。

利用规则栈的压入和退出的过程，相当于完成了推理树的深度优先搜索和回溯过程。

基本原理反向推理过程2）结点的否定yes和no。

或条件中间结点只有所有“或”分枝的回溯值均为no时，才能最后确定该中间结点为no。

2 不确定性推理(1) 事实的不确定性(2) 规则的不确定性(3)推理的不确定性2.1 可信度的计算公式1) 前提中AND（与）连接时CF(R)结论H的可信度为：2.1 可信度的计算公式2) 前提中OR（或）连接时:CF(R)把它转化成等价的两条规则，即CF(R)CF(R)则结论H的可信度计算分别有：合并为：对于多OR连接：依次分解、滚动式合并3.2 不确定性推理3.2.2 不确定性推理和确定性推理的区别•可信度的差别•推理过程的差别对于不确定性推理，当某个结论的可信度不为1时（即CF≠1），对于相同结论的其它规则仍然要进行推理，求该结论的可信度，并和已计算出该结论的可信度进行合并。

3.2 不确定性推理3.2.2 不确定性推理和确定性推理的区别对于确定性推理过程为：不确定性推理3.2.2 不确定性推理和确定性推理的区别对于不确定性推理时，该两规则均含可信度。

R1：A→G CF(0.8)；R2：B∧C→G CF(0.9)CF1(G)＝0.8×0.7＝0.56由于G的可信度不为1，还必须对结论G的其它规则进行推理。

再引用规则R，提问B和C？2CF2(G)＝0.9×MIN{0.7，0.8}＝0.63CF(G)＝CF1(G)+CF2(G)－CF1(G)×CF2(G)＝0.56+0.63－0.56×0.63＝0.843.3 解释机制解释机制有两种实现方法：•推理过程的全部解释•推理过程中正确路径的解释3.4 元知识元知识概念：关于知识的知识是元知识。

它包含概括性知识、总结性知识、关联性知识。

也即是对领域知识进行描述、说明、处理的知识。

领域级知识：特定领域的知识。

元级知识：说明如何运用领域知识的知识。

3.4 元知识3.4.1 元知识的作用1）指导规则的选择有一条以上规则的前提部分和当前事实匹配时，选择规则策略：MR1：如果某一规则的前提比另一规则的前提更专门，且两条规则冲突，则先选用更专门的规则。

MR2：按规则排列顺序，先选用前一条规则。

MR3：优先选用被满足的条件较多的规则。

MR4：首先选择执行代价小的规则。

如有两条规则A→H，A∧B→K，若A，B成立，应先选第2条。

3.4 元知识3.4.1 元知识的作用2 ）记录与领域知识有关的事实¾记录某种处理方法的平均运行时间；¾统计一个程序在运行过程中询问用户的次数；¾统计规则的成功与失败的比率等，提供有关与领域知识的信息。

3.4 元知识3.4.1 元知识的作用3）规则的论证指出某些规则存在的理由，如：R1：如果溢出液是硫酸，则用石灰。

4）检查规则中的错误……MR4：如果经过长期运行，一条规则从没有被触发，则询问专家该规则是否有用3.4 元知识3.4.2 元知识在专家系统中的应用1）元知识推理、两级推理专家系统元级推理机用户提出领域子目标元知识库结束领域推理机子目标完成领域事实推理结果领域知识库3.4 元知识3.4.2 元知识在专家系统中的应用2）黑板模型结构的专家系统黑板模型把一个问题的解空间组织成多个依赖于应用的的层次结构，层次结构中每一层上的信息都是部分解。

BBM对需要多方面专家参与的复杂问题求解特别有效。

各子任务之间的调度程序，是一种元级推理3.4 元知识3.4.2 元知识在专家系统中的应用2）黑板模型结构的专家系统知识源：应用领域的专门知识被划分成若干相互独立的知识源，每个知识源完成一种特定任务。

黑板：问题的解空间，以层次结构方式组织起来的动态库。

控制：动态地选择和激活适用的知识源，使之适时地响应黑板的变化。

——元级推理机3.4 元知识3.4.2 元知识在专家系统中的应用2）黑板模型结构的专家系统元级推理机独立知识源例：火灾原因分析：勘察现场、查找火源点；电气原因分析；易燃、易爆品；误操作；人为纵火……3.4 元知识3.4.2 元知识在专家系统中的应用2）黑板模型结构的专家系统优点：（1）将多种知识源组合在一起，实现问题求解。

（2）黑板结构适合于在多重抽象级上描述与处理问题。

（3）允许知识源共享黑板中各个层次的部分解，这对事先无法确定问题求解次序的复杂问题尤为有效。

（4）知识源相互独立并以数据驱动方式使用。

（5）适用于并行处理。

……3.5 应用举例例：有如下规则集和可信度：R1：A∧B∧C→G CF(0.8）R2：D∨E→A CF(0.7）R3：J∧K→B CF(0.8）R4：P∨Q→C CF(0.9）R5：F∨（R∧S）→D CF(0.6）已知事实及可信度F(0.4)，R(0.5)，S(0.6)，E(n)，J(0.4)，K(0.6)，P(n)，Q(0.4)。

对目标G进行推理求解。

3.5 应用举例解：第一步：把规则分解为只含AND(∧)连接的规则，消去OR(∨)连接的规则：R1 : A∧B∧C→G CF(0.8)R21: D→A CF(0.7)R22: E→A CF(0.7)R3: J∧K→B CF(0.8)R41: P→C CF(0.9)R42: Q→C CF(0.9)R51: F→D CF(0.6)R52: R∧S→D CF(0.6)3.5 应用举例方法1：用知识树推理GCB APKJEDQSRF 0.80.90.90.80.70.70.60.6(0.4)(0.6)(0)(0.4)(0.6)(0)(0.4)(0.5)产生式规则专家系统3.5 应用举例方法2：用规则栈推理定义逆向推理的规则栈和事实数据库• 1.专家系统的建造步骤(1) 设计初始知识库。