产生式系统

产 生 式 系 统

2．2．1 产生式系统

1．序

1943年，Post 首先提出了产生式系统。到目前为止，人工智能（AI ）领域中的产生式系统，无论在理论上还是在应用上都经历了很大发展，所以现今AI 中的产生式系统已与1943年Post 提出的产生式系统有很大不同。

● 因果关系

自然界各个知识元（事实，断言，证据，命题， ）之间存在着大量的因果关系，或者说前提和结论关系，用产生式（或称规则）表示这些关系是非常方便的：

“模式——动作”对偶

“条件——结论”对偶

● 产生式系统

把一组领域相关的产生式（或称规则）放在一起，让它们互相配合、协同动作，一个产生式生成的结论一般可供另一个（或一些）产生式作为前提或前提的一部分来使用，以这种方式求得问题之解决，这样的一组产生式被称为产生式系统。

● 产生式系统的历史

a. 1943年，Post 第一个提出产生式系统并把它用作计算手段。其

目的是构造一种形式化的计算工具，并证明了它与图灵机具有同样的计算能力。

b. 1950年，Markov 提出了一种匹配算法，利用一组确定的规则不断置换字符串中的子串从而把它改造成一个新的字符串，其思想与Post 类似。

c. （大约在）1950年，Chomsky 为研究自然语言结构提出了文法分层概念，每层文法有一种特定的“重写规则”，也就是语言生成规则。这种“重写规则”，就是特殊的产生式。

上面b 和c 所给出的系统其计算能力都与图灵机等价。

d. 1960年，Backus （译名为：巴克斯或巴科斯）提出了著名的BNF ，即巴科斯范式，用以描写计算机语言的文法，首先用来描写ALGOL 60语言。不久即发现，BNF 范式基本上是 Chomsky 的分层系统中的上下文无关文法。由于和计算机语言挂上了钩，产生式系统的应用范围大大拓广了。

2．产生式系统

产生式系统的构成

△ 一组规则

每条规则分为左部（或称前提、前件）和右部（或称结论、动作、后件）。通常左部表示条件，核查左部条件是否得到满足一般采用匹配方法，即查看数据基DB （Data Base）中是否存在左部所指明的情况，若存在则认为匹配成功，否则认为匹配失败。一般说来，匹配成功则执行右部所规定的动作，例如：添加、修改和删除等。

△ 数据基

DB 中存放的数据既是产生式作用的对象，又是构成产生式（或称规则）的基本元素。

△ 一个推理程序（Engine ）

它负责整个产生式系统的运行，包括：规则左部与DB 匹配；从匹配成功的规则中，选出一条将在下一步执行的规则R *，执行R *右部规定的动作；掌握时间结束产生式系统的运行。

产生式系统的特点

△ 相对固定的格式

任何产生式都由左部（LHS ）和右部（RHS ）组成，左部匹配，右部动作。匹配提供的信息只有两种，成功或失败。

△ 知识的模块化

a. 知识元

知识元（或曰事实，证据，断言，…）是不能分解的最小知识片, 知识元集 = 知识库（KB ）中所有产生式包含的知识元的集合； b ．规则

每条规则（或称每个产生式）指明了知识元之间的关系，每条规则都是由知识元和逻辑运算符组成的。规则（也称为知识片）存于KB 中，规则间不能直接相互作用。

c ．元知识

还有如何使用规则的知识（例如，规则匹配的先后次序，匹配冲突消解（即解决）等），我们称其为元知识（用于控制的元知识），元知识也可以模块化并表成元规则，但只有少数产生式系统才能做到这一

点。

△ KB 的flexible

知识的模块化，KB 与推理机分离，使KB 的扩充、修改变得十分容易。但维持KB 的一致性、无矛盾性、完备性不是一件容易的事情。 △ 相互影响的间接性

产生式系统一般采用“数据驱动”（也称为正向推理，前向链推理），控制流是看不见的，一条规则的调用对其它规则之影响不是直接传送过去的，而是通过修改DB 而间接实现的。

△ 机器可读性

A ．机器识别产生式

语法检查和某种程度上的语义检查。语法检查包括矛盾、冗余、循环链等检验，例如， A →B ，A → B （矛盾），A ∨B →C ，A →C （冗余）等。语义检查则涉及产生式系统的具体领域。

B ．推理结论解释

机器可读性的另一种含义是对产生式系统推出的结论进行解释。

3．非确定性匹配

△ 部分匹配

在一些情况下，激活一条规则并不要求产生式左部与DB 中的数据（知识元，事实，或证据）完全匹配上。换言之，在这种情况下只需要某一产生式之左部与DB 中的数据部分匹配上，即可触发该产生式并推出某些结论性信息。

△ 例1. 北京市中医院中医妇科钱伯煊大夫的经验

（腰背冷痛 ∇ 畏寒 ∇ 肢冷/1）∧（腹胀 ∇ 便溏 ∇ 泻泄 ∇ 倦怠乏力 ∇ 浮肿 ∇ 嗜睡 ∇ 白带稀薄 ∇ 舌质淡胖边有齿痕/2）∧（腰酸痛 ∇ 尿频 ∇ 五更泻泄/1）→ 脾肾阳虚

例1说明了：只要左边诸项中有部分项为真，规则便可被激活，右边项即为真。

△ 变上例为标准产生式

⎛3⎫⎛3⎫⎛3⎫ 例1产生式左部：第一对括号中共有 ⎪+ ⎪+ ⎪ = 7种可⎝1⎭⎝2⎭⎝3⎭

能，第2对括号中共有

⎛8⎫⎛8⎫⎛8⎫⎛8⎫⎛8⎫⎛8⎫⎛8⎫ ⎪+ ⎪+ ⎪+ ⎪+ ⎪+ ⎪+ ⎪ = 247 ⎝2⎭⎝3⎭⎝4⎭⎝5⎭⎝6⎭⎝7⎭⎝8⎭

种可能，第3对括号中有7种可能（同第一对括号），故总的组合数为12103种，即例1要变成标准产生式，则需变成12103个产生式，

这样做即不直观，又不经济，部分匹配的意义之一于此可见。 规则压缩：（把多条规则压缩成一条规则）直观易于理解。 扩大了产生式系统的求解能力。

△ 加权方法

上例中的方法有些缺点，即每一组症状中的各个症状间须是平等的。如果在同一组症状中，有些比较重要，有些则不那么重要，那么应如何解决呢？在每一症状后加一个参数权。

例2. 以例1中的第二组症状为例

（腹胀（0.8）∨便溏（1.7）∨泻泄（1.2）∨倦怠乏力（0.9）∨浮肿（1.5）∨嗜睡（0.5）∨白带稀薄（1.3）∨舌质淡胖边有齿痕（0.6））

∧（诸权之和 > 2）→脾肾阳虚第二证

匹配方法：若某症状出现则对它的权求和，否则不予计算。 权与可信度

令S = 产生式左边所有为真（或曰存在）的项的权之和，S 还可用来表示结论的可信度：S 愈大，结论就愈可信。

△ 两种权

A ．有时，人们采用两种权来确定知识元（事实，证据，断言，…）与规则之间的匹配程度。

B ．采用一种权时，权只说明当某事实为真时，它对该规则左部匹配成功所起的作用有多大，而完全没说明当某事实为假（即不存在）时，它对该规则左部匹配不成功所起的作用有多大。前一个权刻画了充分性，后一个权刻画了必要性。因此，采用一种权之方法没有考虑必要性。

例3. 在例2中增加一个必要性权

（腹胀（0.8，0.3）∨便溏（1.7，0.4）∨泻泄（1.2，1.1）∨倦怠乏力（0.9，1.9）∨浮肿（1.5，0.8）∨嗜睡（0.5，1.1）∨白带稀薄（1.3，0.9）∨舌质淡胖边有齿痕（0.6，1.2））∧（诸充分权之和减去诸必要权之和大于2） 脾肾阳虚第二证

例3中每个项都有两个权，第一个权表达了充分性，第二个权表达了必要性。这里：

诸充分性权之和 = 所有实际出现的症状的充分性权之和 诸必要性权之和 = 所有实际不出现的症状的必要性权之和

“必要性权”与“充分性权”之间没有必然联系，充分权性大者，必然性权不一定大，反之亦然。

4．匹配冲突消解

Ⅰ．序

在产生式系统运行过程中，要不断地用GDB 中的数据和产生式进行匹配。

△ 向前（或曰正向，前向链，数据驱动的）推理时，要使数据和产生式左部匹配，对匹配成功的产生式执行其右部。

△ 向后（或曰反向，逆向，反向链，目标驱动的，等等）推理时，要把子目标和GDB 中的数据或产生式右部匹配。与数据匹配成功者生成叶节点；与产生式右部匹配成功者，则使该产生式左部成为新的子目标。

△ 匹配冲突，在产生式系统进行推理的过程中，可能会在选择产生式和数据、子目标等方面产生二义性，这就是所谓的匹配冲突。 △ 向前推理时的匹配冲突

a. 有n>1 个产生式的左部都能和当前DB 中的数据匹配成功； b. 有m>1 组不同的数据都能和同一个产生式的左部匹配成功； 举出例子

c. a 与b 两种情况的复合。

△ 逆向推理时的匹配冲突

a) 有n>1个产生式的右部都能和一个子目标匹配成功； b) 有m>1个数据都能和同一个子目标匹配成绩。

c) 有L>1个子目标都能找到相应的数据或产生式右部且匹配成 功。

d) a) 、b) 、c) 的复合

Ⅱ．匹配冲突消解（或解决）策略

产生式系统的推理机必须具备某种选择功能，以便能有效解决上面列举的二义性（或称匹配冲突）。已有许多匹配冲突消解策略，下面着重介绍其中的几组：

A 组：按事先排好的固定顺序

△ 策略SA1 把所有产生式（一个产生式系统中所包含的）排成一个全序，发生匹配冲突时按顺序选择产生式；

△ 策略SA2 把所有产生式排成一个有向图，图中每个顶点代表一个产生式，如果从顶点a 有弧通向顶点b ，那么顶点a 所代表的产生式应先于顶点b 所代表的产生式被选择。

△ 比较SA1与SA2 由策略SA1选择的产生式是唯一的，但由策略SA2选择的产生式却不见得是唯一的，因为从一个顶点可以有多条弧伸向不同的顶点。此外，策略SA2中的有向图也不一定是连通的，它可能由几个不连通的子图组成。

△ 向前推理的策略SA1 （LHS i 代表第i 个产生式之左部，RHS i 代表第i 个产生式之右部）

L: if LHS1 匹配成功 then begin 执行 RHS 1，然后 goto L end;

if LHS2 匹配成功 then begin 执行 RHS 2，然后 goto L end; •„

•„

•„

if LHSn 匹配成功 then begin 执行 RHS n ，然后 goto L end;

△ 何时并且如何确定产生式的优先次序

a. 当有明确的解题步骤时，可按解题设置产生式的次序；

b. 把匹配成功之可能性大的产生式排在前面，这可以在总体上节省匹配时间；

c. 把匹配尝试花费时间少的产生式排在前面；

d. 当某些产生式的匹配成功显著地有利于整个问题（总目标）的解决，则可把这些产生式排在前面。

B 组：按数据的新鲜性排序

数据的新鲜性就是数据产生的先后次序，后生成的数据比先生成的数据具有更多的新鲜性。

批量标准：凡是由同一个产生式在同一次激发中所生成的数据，都具有相同的新鲜性，后激发的产生式生成的数据比之先激发的产生式所生成的数据更新鲜。

个别标准：它先按批量标准来区分数据的新鲜性，然后，对同一个产生式在同一次激发中所生成之数据数据再加以新鲜性区分，规定后生成之数据比先生成之数据有更大的新鲜性。

例：有一个被激发的产生式如下：

A 1∧A 2∧…∧A n →B 1∧B 2∧…∧B n

B i 1的新鲜性都大于B i 的新鲜性。

△策略SB1：如果数据组甲能激发某个产生式A ，数据组乙能激发某个产生式B ，但数据组甲中按批量标准为最新之数据比数据组乙中按批量标准为最新之数据还要新，则优先用数据组甲去激发产生式A （注意：A 和B 可以是同一个产生式）；

△策略SB2：同策略SB1，但需把批量标准改为个别标准。

△策略SB3：如果数据组甲能激发某个产生式A ，数据组乙能激发某个产生式B ，但数据组甲中按批量标准为最旧的数据比之数据组乙中按批量标准为最旧的数据要新一些，则优先选数据组甲激发产生式A 。

△策略SB4：同策略SB3，但要把批量标准改为个别标准。

采用这种策略最基本的出发点是：

向前推理的产生式系统的特征是：只有通过修改GDB 才能实现各产生式之间的相互影响，才能实现某种程度的控制机制。因此，要实现灵活的控制，就必须对GDB 中发生的任何变化都十分敏感，并迅速作出反应。新数据的产生正是反映了这种变化。

△策略SB5：同策略SB2，但它考虑的不只是数据组甲数据组乙中的最新数据，而是把整组数据的新旧及它们在匹配中的应用情况一起考虑进去：

假定数据组甲能激发产生式A ，数据组乙能激发产生式B 。

SB51 set X←甲组中的最新数据（按个别标准）

set Y←乙组中的最新数据（按个别标准）

SB52 若X 比Y 新，则选甲和A 并终止本算法；

若Y 比X 新，则选乙和B 并终止本算法；

set m←X 与A 之左部匹配上的左部知识元数；

set n←Y 与B 之左部匹配上的左部知识元数；

若m>n，则选甲和A 并终止本算法；

若m

SB53 若X 是甲中之最旧的数据且Y 是乙组中最旧数据，则本算

法以失败告终。

若甲中有仅次于X 的最新数据，则set X ←甲中仅次于X 的

最新数据；

若乙中有仅次于Y 的最新数据，则 set Y←乙中仅次于Y 的

最新数据；

go back to SB52

△ 小结：该组策略与A 组不同，它是动态的，不能事先把产生式的次序排好，因而执行效率要低一点。优先选用新产生的数据是许多

产生式系统都采用的策略。注意它仅仅适用于向前推理，这是因为向后推理不产生新数据。

C 组：按子目标的新鲜性排序

向前推理时考虑数据的新鲜性，与此相应逆向推理时要考虑子目标的新鲜性。与或树每向前伸展一节，就要产生一批新的子目标。后生成的子目标比先生成的子目标具有更大的新鲜性。在同一批生成的子目标中，排在右边的子目标比之排在左边的子目标，具有更大的新鲜性。

注意在逆向推理时，却不一定使用最新的子目标。

△ 策略SC1：使用最新一层靠左边的子目标。该策略称为深度优先搜索策略，PROLOG 语言就使用它。

△ 策略SC2：使用最旧的子目标。

△ 分析：

SC1有时效率较高，但好犯“钻牛尖”的毛病，有时在某个方向上根本没有成功的可能，但它却因为总是使用最新的子目标而一个劲的往前钻，这个过程不一定能终止，即有时会陷入“无穷”推理，以致虽有答案而不能求得。

SC2的优点是只要答案存在，它就一定在有限步内把它求出来。若答案不止一个，则不论其数目多少，则它总可以一个个地把它们求出来。缺点：它每一步都要穷尽一切可能，因之悬而未决的子目标个数，可能会膨胀很快，造成所谓组合爆炸，使得无论在时间上还是在空间上都会使人无法忍受。

D 组：按匹配程度排序

△ 策略SD1：按产生式左部中条件成立的多少排序

例：（A 11∨A 12∨…∨A 1n1/L 1）∧

（A 21∨A 22∨…∨A 2n2/L 2）∧

„ „•

（A m1∨A m2∨…∨A m n m /L m ）→ (*1) 产生式中每对小括弧包含的部分被称为一个与式，故 (*1) 产生式中共有m 个与式。

△ 有一组数据A ij 能与(*1)产生式的左部匹配，即对每个k(1≤k ≤m) ，在第k 个与式中有S k （S k ≥L k ）个或式匹配成功。

△ 还有另一组数据A ij 也能与产生式(*1)之左部匹配，即对每个k(1≤k ≤m) ，在第k 个与式中有T k (Tk ≥L k ) 个或式被匹配成功。

' △ 若对于每个k 都有S k ≥T k ，我们就说A ij 的匹配成功度高，并优' ' '

先选取A ij 进行匹配。

△ 策略SD2：在用加权（这里指充分性权）方法进行条件匹配时，本策略优先选择匹配后的总权数大的产生式和数据组。

△ 策略SD3：签于策略SD1只能把数据组排成偏序，而且只能应'

用于同一个产生式和不同数据组匹配的情形，本策略把SD1和SD2结合起来，给产生式(*1) 中的每个A ij (Aij 下标的含义：i 表示第i 个与式，j 表示第i 个与式中的第j 个条件或知识元) 赋一个权。这些权对每个i 是规范化的，即若W ij 是A ij 的权，W ij >0，则对每个i 应有:

j =1∑Wi j =1 (*2) ni

这样似乎就可以对任何产生式和数据组一律选取总权数最高的匹配。

△ 与式个数规范化

当把(*2)应用于不同产生式时，还应对每个产生式左部的与式个数实行规范化，即把总权数除以左部与式之个数，否则不能进行公平比较，故变(*2)为(*3)

⎧0⎫∑∑W ij *X ij /mp (Xij =⎨⎬) (*3)

i =1j =1⎩1⎭mp ni

mp 是产生式中的与式总数

这里有一个假定：即每一个与式皆被满足. 也就是说：

j =1∑W ij *X ij >W i (i =1, 2,... m ) 。 ni

△ 区分各与式的相对重要性

对一个产生式的每个与式也应赋予一个权g i ，诸g i 满足规范化条件： ∑g i =1,

i =1mp g i >0 (*4)

对产生式系统中的每个产生式即（对所有的产生式p ） △ 用作比较的匹配权

mp

i =1∑g i (∑W ij *X ij ) (*5) j =1ni

△ 策略SD4：如果产生式带有可信度，则本策略优先选择可信度高（规则强度）的产生式。

5．结语

在产生式系统中使用的策略绝不止这些。在这些策略中也并非每个都有很大实用价值。在设计产生式系统时可以根据具体情况灵活选择、组合、加强、改进。