2.3 产生式表示方法

产生式系统有着悠久的历史。最早提出产生式系统并把它作为计算手段的是美国数学家Post^[12]。早在1943年，他设计的Post系统就能构造出一种形式化的推理工具，可以匹敌图灵机的计算能力。几乎在同一时期，乔姆斯基在研究自然语言结构时提出了四层文法模型，并给出了“重写规则”，即语言生成规则^[15]。语言生成规则实际上是特殊的产生式。1960年，巴克斯提出了巴克斯范式，用来描述计算机语言的文法。实际上，巴克斯范式即为乔姆斯基上下文无关文法^[16]。

2.3.1 事实与规则的表示

产生式建立在因果关系的基础上，能够更好地描述事实、规则和不确定性度量。

1．事实的表示

事实可以看作多变量之间关系的断言。其中，变量的值或变量之间的关系可以是一个词。例如，乔布斯的性别是男性，语言变量是乔布斯，值是男性，关系是性别；亚里士多德的老师是柏拉图，语言变量是亚里士多德和柏拉图，关系是老师。一般知识库可以使用三元组来表达基本事实：（变量，关系，值），也就是（头实体，关系，尾实体）。这种表示在计算机内的实现是一个三列的表。例如，（乔布斯，性别，男性）或（亚里士多德，老师，柏拉图）。

2．规则的表示

规则用于表示事物之间的因果关系，以“如果，那么”的形式出现。实际上，在大部分系统内，规则是知识的基本单位。其中，“如果”部分的内容被称为条件或前件；“那么”部分的内容被称为动作、后件或结论。

产生式的一般形式为：前件→ 后件。前件和后件可以使用基本的逻辑运算符，如与（∧）、或（∨）、非。条件部分一般是事实的合取范式或析取范式，而结论部分一般是另一个事实。其基本含义是，如果前件满足，则可得到后件的结论或执行后件的动作，也就是触发后件。值得注意的是，一个产生式的结论可以作为另一个产生式的前提或语言变量使用，并进一步构成一组产生式，也就是产生式系统。

下面举几个产生式的例子：

矩阵M被奇异值分解 → 左奇异值矩阵、奇异值矩阵和右奇异值矩阵；

在常温常压下，把水加热到100摄氏度 → 沸腾；

天下雨∧外出 → 带伞∨带雨衣；

发烧∧头痛∧咳嗽 → 感冒；

x＞5∧y＞x→y＞5.

在知识表示中，所有的因果关系都可以转换为产生式表示。所以，产生式表示方法作为一种知识表示方法十分便利。

2.3.2 产生式系统的结构

一组产生式可以构成产生式系统。一般的产生式系统由三部分组成：数据库、规则库和推理机。

① 数据库可存放构成产生式系统的基本元素，也是产生式分析的对象，包括系统输入/输出、中间结果及最终结果。其中，数据的格式可以是多种形式的：常量、变量、多元组、谓词、表格和图像等。在推理过程中，当规则库某条规则的前提可以与数据库中已有事实相匹配时，这条规则就可被应用，相应的结论会被写入数据库。

② 规则库中存放的是求解有关产生式规则的集合。每个规则由前件和后件组成，包含将问题从初始状态转换为目标状态所需的所有变换规则。这些规则描述了问题域的一般客观规律。规则库是产生式系统的基础。其完整性、一致性、准确性、灵活性及合理性都对产生式系统的能力有影响。

③ 推理机是一个解释程序，控制协同规则库与数据库，负责整个产生式系统的运行，决定问题求解过程的推理路线，实现对问题的求解。推理机主要包括以下一些内容：

按一定策略从规则库中选择规则，与数据库中的已有事实进行匹配。

当匹配成功的规则多于一条时，需要从匹配成功的规则中选出一个执行，即根据一定的策略消解冲突。

解释执行规则后件的动作。

掌握结束产生式系统运行的条件。

其中包括推理方式、控制策略和动作的执行方式等。推理机是产生式系统的核心。推理机的性能决定了产生式系统的性能。

2.3.3 产生式系统的推理

产生式系统的推理方式有三种：正向推理、反向推理和双向推理。产生式系统的推理可以在与或图上进行。与或图是各个事实之间的逻辑关系图。

① 正向推理是从已知事实出发，通过规则库求得结论的，也称自底向上推理方式，或者数据驱动方式。这种推理方式是正向使用规则的，即将问题的初始状态作为初始数据库，且仅当数据库中的事实满足某条规则时，相应规则才被使用。正向推理的推理基础是逻辑演义的推理链，从一组事实出发，使用一组规则来证明目标的成立。例如，事实A，规则库中有规则A→B、B→C、C→D，正向规则表示为A→B→C→D。

② 反向推理是从目标出发，反向使用规则，求得已知事实的，也称自顶向下推理方式或目标驱动方式。反向推理的基本原理是从表示目标的谓词或命题出发，使用一组规则证明事实谓词或命题是成立的，即使用一组假设（目标），并逐一验证这些假设。反向推理的具体实现是首先假设一个系统试图证明的可能目标，然后分析这个目标是否在数据存储器中存在：若存在，则结论成立；否则，将查看相应目标的叶子节点（子目标），找出结论部分包含此目标的规则，把它们的前提作为新的目标，并重复。如此循环下去，直到所有目标都被证明为止。

③ 双向推理，即自底向上，又自顶向下，直到中间环节两个方向的结果相符，便成功结束推理。显然，这种方式的推理网络较小，效率也较高，也称正反向推理。这是为了克服正向推理和反向推理的缺点而提出的。