产生式系统

《产生式系统》由会员分享，可在线阅读，更多相关《产生式系统（16页珍藏版）》请在装配图网上搜索。

1、产生式系统221 产生式系统1序1943年，Post首先提出了产生式系统。到目前为止，人工智能（AI） 领域中的产生式系统，无论在理论上还是在应用上都经历了很大发展， 所以现今AI中的产生式系统已与1943年Post提出的产生式系统有很 大不同。因果关系自然界各个知识元（事实，证据，命题，）之间存在着大量的因果关系，或者说前提和结论关系，用产生式（或称规则）表示这 些关系是非常方便的：模式动作”对偶条件结论”对偶 产生式系统把一组领域相关的产生式（或称规则）放在一起，让它们互相配合、 协同动作，一个产生式生成的结论一般可供另一个（或一些）产生式 作为前提或前提的一部分来使用，以这种方式求得问题

2、之解决，这样 的一组产生式被称为产生式系统。 产生式系统的历史a. 1943 年， Post 第一个提出产生式系统并把它用作计算手段。其目的是构造一种形式化的计算工具，并证明了它与图灵机具有同样的 计算能力。b1950年，Markov提出了一种匹配算法，利用一组确定的规则 不断置换字符串中的子串从而把它改造成一个新的字符串，其思想与Post 类似。c （大约在）1950 年， Chomsky 为研究自然语言结构提出了文 法分层概念，每层文法有一种特定的“重写规则”，也就是语言生成规 则。这种“重写规则”，就是特殊的产生式。上面b和c所给出的系统其计算能力都与图灵机等价。d 1960 年， Ba

3、ckus （译名为：巴克斯或巴科斯）提出了著名的BNF，即巴科斯范式，用以描写计算机语言的文法，首先用来描写ALGOL 60语言。不久即发现，BNF范式基本上是Chomsky的分层 系统中的上下文无关文法。由于和计算机语言挂上了钩，产生式系统的应用范围大大拓广了。2产生式系统产生式系统的构成 一组规则每条规则分为左部（或称前提、前件）和右部（或称结论、动作、 后件）。通常左部表示条件，核查左部条件是否得到满足一般采用匹配 方法，即查看数据基DB（Data Base）中是否存在左部所指明的情况, 若存在则认为匹配成功，否则认为匹配失败。一般说来，匹配成功则 执行右部所规定的动作，例如：添加、修改

4、和删除等。 数据基DB 中存放的数据既是产生式作用的对象，又是构成产生式（或称 规则）的基本元素。 一个推理程序（ Engine）它负责整个产生式系统的运行，包括：规则左部与 DB 匹配；从匹 配成功的规则中，选出一条将在下一步执行的规则疋，执行疋右部规 定的动作；掌握时间结束产生式系统的运行。产生式系统的特点 相对固定的格式任何产生式都由左部（LHS）和右部（RHS）组成，左部匹配，右部动作。匹配提供的信息只有两种，成功或失败。 知识的模块化a. 知识元 知识元集=知识库（KB）中所有产生式包含的知识元的集合知识元（或曰事实，证据，）是不能分解的最小知识片,b规则每条规则（或称每个产生式）指

5、明了知识元之间的关系，每条规则 都是由知识元和逻辑运算符组成的。规则（也称为知识片）存于 KB 中，规则间不能直接相互作用。c元知识还有如何使用规则的知识（例如，规则匹配的先后次序，匹配冲突 消解（即解决）等），我们称其为元知识（用于控制的元知识），元知 识也可以模块化并表成元规则，但只有少数产生式系统才能做到这一点。 KB 的 flexible知识的模块化，KB与推理机分离，使KB的扩充、修改变得十分 容易。但维持 KB 的一致性、无矛盾性、完备性不是一件容易的事情。 相互影响的间接性产生式系统一般采用“数据驱动”（也称为正向推理，前向链推理） 控制流是看不见的，一条规则的调用对其它规则之影

6、响不是直接传送 过去的，而是通过修改 DB 而间接实现的。 机器可读性A机器识别产生式语法检查和某种程度上的语义检查。语法检查包括矛盾、冗余、循环链等检验，例如，A-B, A- B （矛盾），AVB-C, A-C （冗余）等。语义检查则涉及产生式系统的具体领域。B.推理结论解释机器可读性的另一种含义是对产生式系统推出的结论进行解释。3非确定性匹配 部分匹配在一些情况下，激活一条规则并不要求产生式左部与 DB 中的数 据（知识元，事实，或证据）完全匹配上。换言之，在这种情况下只 需要某一产生式之左部与 DB 中的数据部分匹配上，即可触发该产生 式并推出某些结论性信息。 例 1. 北京市中医院中医

7、妇科钱伯煊大夫的经验（腰背冷痛V畏寒V肢冷/1）A（腹胀V便溏V泻泄V倦怠 乏力V浮肿V嗜睡V白带稀薄V舌质淡胖边有齿痕/2）A（腰 酸痛V尿频V五更泻泄/】）f 脾肾阳虚例 1 说明了：只要左边诸项中有部分项为真，规则便可被激活，右 边项即为真。 变上例为标准产生式（3例1产生式左部：第一对括号中共有.= 7 种可能，第 2对括号中共有= 247(8)+16丿种可能，第 3对括号中有 7种可能（同第一对括号），故总的组合数为 12103种，即例 1 要变成标准产生式，则需变成 12103个产生式， 这样做即不直观，又不经济，部分匹配的意义之一于此可见。 规则压缩：（把多条规则压缩成一条规则）

8、直观易于理解。扩大了产生式系统的求解能力。 加权方法上例中的方法有些缺点，即每一组症状中的各个症状间须是平等 的。如果在同一组症状中，有些比较重要，有些则不那么重要，那么 应如何解决呢？在每一症状后加一个参数权。例 2. 以例 1 中的第二组症状为例（腹胀（0.8）V便溏 （1.7）V泻泄（1.2）V倦怠乏力（0.9）V浮 肿（1.5） V嗜睡（05） V白带稀薄（1.3） V舌质淡胖边有齿痕（06）人（诸权之和 2）脾肾阳虚第二证匹配方法：若某症状出现则对它的权求和，否则不予计算。 权与可信度令S =产生式左边所有为真（或曰存在）的项的权之和，S还可 用来表示结论的可信度：S愈大，结论就愈可

9、信。 两种权A.有时，人们采用两种权来确定知识元（事实，证据, 与规则之间的匹配程度。B.采用一种权时，权只说明当某事实为真时，它对该规则左部匹 配成功所起的作用有多大，而完全没说明当某事实为假（即不存在） 时，它对该规则左部匹配不成功所起的作用有多大。前一个权刻画了 充分性，后一个权刻画了必要性。因此，采用一种权之方法没有考虑 必要性。例3. 在例2中增加一个必要性权（腹胀（0.8, 0.3）V便溏（17, 0.4）V泻泄（1.2, 11）V倦怠乏力（0.9, 1.9）V浮肿（1.5, 0.8）V嗜睡（0.5, 1.1）V 白带稀薄（1.3,0.9）V舌质淡胖边有齿痕（06, 1.2） A

10、（诸充分权之和减去诸必要 权之和大于 2）脾肾阳虚第二证例3中每个项都有两个权,第一个权表达了充分性,第二个权表达 了必要性。这里：诸充分性权之和 = 所有实际出现的症状的充分性权之和诸必要性权之和 = 所有实际不出现的症状的必要性权之和“必要性权”与“充分性权”之间没有必然联系，充分权性大 者，必然性权不一定大，反之亦然。4匹配冲突消解I序在产生式系统运行过程中，要不断地用 GDB 中的数据和产生式进 行匹配。 向前（或曰正向，前向链，数据驱动的）推理时，要使数据和产 生式左部匹配，对匹配成功的产生式执行其右部。 向后（或曰反向，逆向，反向链，目标驱动的，等等）推理时， 要把子目标和 GDB

11、 中的数据或产生式右部匹配。与数据匹配成功者 生成叶节点；与产生式右部匹配成功者，则使该产生式左部成为新的 子目标。 匹配冲突，在产生式系统进行推理的过程中，可能会在选择产生 式和数据、子目标等方面产生二义性，这就是所谓的匹配冲突。 向前推理时的匹配冲突a. 有 n1 个产生式的左部都能和当前 DB 中的数据匹配成功；b. 有 m1 组不同的数据都能和同一个产生式的左部匹配成功； 举出例子c. a 与 b 两种情况的复合。 逆向推理时的匹配冲突a）有 n1 个产生式的右部都能和一个子目标匹配成功；b）有 m1 个数据都能和同一个子目标匹配成绩。c）有L1个子目标都能找到相应的数据或产生式右部且

12、匹配成 功。d）a）、b）、c） 的复合II.匹配冲突消解（或解决）策略产生式系统的推理机必须具备某种选择功能，以便能有效解决上面 列举的二义性（或称匹配冲突）。已有许多匹配冲突消解策略，下面着 重介绍其中的几组：A组：按事先排好的固定顺序 策略 SA1 把所有产生式（一个产生式系统中所包含的）排成 一个全序，发生匹配冲突时按顺序选择产生式； 策略 SA2 把所有产生式排成一个有向图，图中每个顶点代表 一个产生式，如果从顶点a有弧通向顶点b,那么顶点a所代表的产 生式应先于顶点b所代表的产生式被选择。 比较 SA1 与 SA2 由策略 SA1 选择的产生式是唯一的,但由策 略 SA2 选择的产

13、生式却不见得是唯一的,因为从一个顶点可以有多条 弧伸向不同的顶点。此外，策略SA2中的有向图也不一定是连通的， 它可能由几个不连通的子图组成。向前推理的策略SA1 （LHS.代表第i个产生式之左部，RHS. ii 代表第i个产生式之右部）L: if LHS匹配成功 then begin 执行 RHS1，然后 goto L end;if LHS2 匹配成功 then begin 执行 RHS2，然后 goto L end;22if LHSn 匹配成功 then begin 执行 RHSn，然后 goto L end; 何时并且如何确定产生式的优先次序a. 当有明确的解题步骤时，可按解题设置产生式

14、的次序；b. 把匹配成功之可能性大的产生式排在前面，这可以在总体上节省匹配时间；c. 把匹配尝试花费时间少的产生式排在前面；d. 当某些产生式的匹配成功显著地有利于整个问题（总目标）的 解决，则可把这些产生式排在前面。B组：按数据的新鲜性排序数据的新鲜性就是数据产生的先后次序，后生成的数据比先生成 的数据具有更多的新鲜性。批量标准：凡是由同一个产生式在同一次激发中所生成的数据， 都具有相同的新鲜性，后激发的产生式生成的数据比之先激发的产生 式所生成的数据更新鲜。个别标准：它先按批量标准来区分数据的新鲜性，然后，对同一 个产生式在同一次激发中所生成之数据数据再加以新鲜性区分，规定 后生成之数据比

15、先生成之数据有更大的新鲜性。例：有一个被激发的产生式如下：A1 gA.Aa f AboNNb1 2 n 1 2 nB . 1的新鲜性都大于B .的新鲜性。i 1 i策略SB1：如果数据组甲能激发某个产生式A,数据组乙能激发 某个产生式B但数据组甲中按批量标准为最新之数据比数据组乙中 按批量标准为最新之数据还要新，则优先用数据组甲去激发产生式 A （注意：A和B可以是同一个产生式）；策略SB2：同策略SB1，但需把批量标准改为个别标准。策略SB3：如果数据组甲能激发某个产生式A，数据组乙能激发 某个产生式B,但数据组甲中按批量标准为最旧的数据比之数据组乙 中按批量标准为最旧的数据要新一些，则优先

16、选数据组甲激发产生式 A。策略SB4：同策略SB3,但要把批量标准改为个别标准。采用这种策略最基本的出发点是：向前推理的产生式系统的特征是：只有通过修改 GDB 才能实现 各产生式之间的相互影响，才能实现某种程度的控制机制。因此，要 实现灵活的控制，就必须对 GDB 中发生的任何变化都十分敏感，并 迅速作出反应。新数据的产生正是反映了这种变化。策略SB5：同策略SB2,但它考虑的不只是数据组甲数据组乙中 的最新数据，而是把整组数据的新旧及它们在匹配中的应用情况一起 考虑进去：假定数据组甲能激发产生式A,数据组乙能激发产生式B。SB51 set X-甲组中的最新数据（按个别标准）setY乙组中的

17、最新数据（按个别标准）SB52若X比Y新，则选甲和A并终止本算法；若 Y 比 X 新，则选乙和 B 并终止本算法；set mX与A之左部匹配上的左部知识元数；set n-Y 与 B 之左部匹配上的左部知识元数；若mn,则选甲和A并终止本算法；若mvn,则选乙和B并终止本算法。SB53 若 X 是甲中之最旧的数据且 Y 是乙组中最旧数据，则本算 法以失败告终。若甲中有仅次于X的最新数据，则set X甲中仅次于X的 最新数据；若乙中有仅次于Y的最新数据，则set Y乙中仅次于Y的 最新数据；go back to SB52 小结：该组策略与 A 组不同，它是动态的，不能事先把产生式 的次序排好，因而

18、执行效率要低一点。优先选用新产生的数据是许多产生式系统都采用的策略。注意它仅仅适用于向前推理，这是因 为向后推理不产生新数据。C组：按子目标的新鲜性排序向前推理时考虑数据的新鲜性，与此相应逆向推理时要考虑子 目标的新鲜性。与或树每向前伸展一节，就要产生一批新的子目标。 后生成的子目标比先生成的子目标具有更大的新鲜性。在同一批生成 的子目标中，排在右边的子目标比之排在左边的子目标，具有更大的 新鲜性。注意在逆向推理时，却不一定使用最新的子目标。策略SC1：使用最新一层靠左边的子目标。该策略称为深度优 先捜索策略，PROLOG语言就使用它。策略SC2：使用最旧的子目标。 分析：SC1 有时效率较高

19、，但好犯“钻牛尖”的毛病，有时在某个方向 上根本没有成功的可能，但它却因为总是使用最新的子目标而一个劲 的往前钻，这个过程不一定能终止，即有时会陷入“无穷”推理，以 致虽有答案而不能求得。SC2 的优点是只要答案存在，它就一定在有限步内把它求出来。 若答案不止一个，则不论其数目多少，则它总可以一个个地把它们求 出来。缺点：它每一步都要穷尽一切可能，因之悬而未决的子目标个 数，可能会膨胀很快，造成所谓组合爆炸，使得无论在时间上还是在 空间上都会使人无法忍受。D 组：按匹配程度排序策略SD1：按产生式左部中条件成立的多少排序例:(AuVA12VVAini/ L i )A (*1)A)A(Am1VA

20、m2Vg mn L)Am(*1) 产生式中每对小括弧包含的部分被称为一个与式，故 (*1) 产 生式中共有 m 个与式。有一组数据Aj能与(*1)产生式的左部匹配，即对每个k(1WkW ijm),在第k个与式中有Sk (SkNLk )个或式匹配成功。还有另一组数据Aj也能与产生式(*1)之左部匹配，即对每个k(1 ijWkWm)，在第k个与式中有Tk(TkMLk)个或式被匹配成功。若对于每个k都有SkMTk，我们就说Aj的匹配成功度高，并优 k kij先选取Aj进行匹配。 ij策略SD2：在用加权(这里指充分性权)方法进行条件匹配时， 本策略优先选择匹配后的总权数大的产生式和数据组。策略SD3

21、：签于策略SD1只能把数据组排成偏序，而且只能应用于同一个产生式和不同数据组匹配的情形，本策略把 SD1 和 SD2结合起来，给产生式(笃)中的每个A.(A下标的含义：i表示第i个与 1 ij ij式， 表示第 i 个与式中的第 个条件或知识元)赋一个权。这些权对每个i是规范化的，即若W.是A.的权，W.0,则对每个i应有：i ii Wij = 1(*2)j=1这样似乎就可以对任何产生式和数据组一律选取总权数最高的匹配。 与式个数规范化当把(*2)应用于不同产生式时，还应对每个产生式左部的与式个数实行规范化，即把总权数除以左部与式之个数，否则不能进行公平比 较，故变(*2)为(*3)(*3)m

22、 那 * Xj mp (Xf ) i=1 j=1l 丿mp 是产生式中的与式总数这里有一个假定：即每一个与式皆被满足.也就是说Wij * Xij Wi(i = 1,2,m) oj=1 区分各与式的相对重要性对一个产生式的每个与式也应赋予一个权g，诸g.满足规范化条件: gi = 1, gi 0(*4)i=1对产生式系统中 的每个产 生式即（ 对所有的产生式 p） 用作比较的匹配权弋g （ Wij * Xj（*5）i=1 j=1策略SD4：如果产生式带有可信度，则本策略优先选择可信度 高（规则强度）的产生式。5结语在产生式系统中使用的策略绝不止这些。在这些策略中也并非每个 都有很大实用价值。在设计产生式系统时可以根据具体情况灵活选择 组合、加强、改进。