产生式

定义

产生式规则简称产生式，是一条形如 α → β 或 IF α THEN β 的规则，其中 α 称左部或前件，β 称右部或后件^[1]。按两端内容划分，它有两种类型：左部是需要注视的条件、右部为条件成立时应采取行动的，称条件-行动型产生式；左部是前提、右部为相应结论的，称前提-结论型产生式^[1]。

在形式语言领域，产生式被用作重写规则，规定某些符号组合如何被另一些符号组合替换，这是 形式文法 描述形式语言的基本手段^[3]。一个形式文法由非终结符集合、终结符集合、产生式规则集合与起始符号四部分组成，它所生成的语言，是从起始符号出发反复应用规则后能得到的所有终结符号串的集合^[3]。

在认知心理学中，产生式指以「如果—那么」形式表征的程序性知识单元，由条件与动作两部分构成，条件被满足时相应动作随即被执行^[4]。多条产生式联系起来组成 产生式系统，用于表征复杂技能的完成过程^[2]。

原理

产生式系统一般由产生式集合、全局数据库和控制程序三部分组成^[1]。产生式集合对应长期记忆，存放相对稳定的知识，构成规则库；全局数据库对应短期记忆，保存随求解过程不断变化的动态数据；控制程序则负责规则的选用并控制整个系统的运行^[1]。

系统的一轮工作通常包含匹配、选优、行动 3 个阶段：规则的条件部分先与全局数据库中的数据比对，比对成功的规则汇成竞争集，再按选优策略从中挑出一条执行；执行之后数据库还要被修改，以反映新的环境^[1]。产生式何时执行并不由事先排定的次序决定，各条规则之间一般也不互相调用，因此有文献把它比作「伺机而动」的守护神^[1]。

按推理方向可分正向与逆向两类：正向推理从已知条件出发逐步逼近目标，逆向推理从目标出发回溯到条件^[1]。其基本形式可写作 $P \rightarrow Q$，含义是前提 P 成立时得到结论 Q 或执行 Q 所规定的操作^[1]。

flowchart LR

W[全局数据库] --> M[匹配: 规则条件与数据比对]

M --> S[选优: 在竞争集中选定一条规则]

S --> A[行动: 执行规则并更新数据库]

A --> W

上图给出产生式系统常见的匹配—选优—行动循环^[1]。

发展历程

1943 年，美国数学家 波斯特 在一种基于符号串替换的计算模型中首次使用「产生式」这一术语，模型里的每条替换规则就是一条产生式，该模型即波斯特机^[2]。波斯特机被用于考察形式体系的计算能力^[2]。

20 世纪 50 年代，乔姆斯基(Noam Chomsky)通过给产生式附加不同限制，把文法划成 4 类，从约束最弱的无限制文法，经上下文相关文法、上下文无关文法，到限制最严的正规文法，构成乔姆斯基谱系^[5]。1960 年前后，人们用上下文无关文法描述算法语言 ALGOL 的语法，巴科斯范式(BNF)此后成为书写这类文法的常用方式^[6][5]。

20 世纪 50 年代末，纽厄尔与西蒙在研究人类问题求解的认知模型时引入了产生式系统这一术语；到 1972 年，两人开发出基于规则的产生式系统^[2]。产生式系统由此成为研制人工智能系统时常用的体系结构之一，也被大量专家系统用作知识表示手段。

1976 年，安德森(John Anderson)提出思维适应性控制模型(ACT)，其中程序性知识以产生式系统表征、陈述性知识以命题网络表征，该模型经修订后发展为 ACT-R^[7]。20 世纪 90 年代以来，产生式系统越来越多地与综合认知架构研究联系在一起^[8]。

应用

在人工智能领域，产生式表示法用于知识表示，不少专家系统直接以产生式系统作为体系结构^[1]。由于它在表达和运用不精确知识方面较为灵活，带有置信度的产生式也被用来处理经验性推理^[1]。

在形式语言与编译领域，上下文无关文法 被用来定义大多数程序设计语言的语法，巴科斯范式是其常见书写形式^[5]。乔姆斯基谱系中的 4 类文法，分别与图灵机、线性有界自动机、下推自动机以及有限状态自动机的计算能力相对应^[3]。

在认知建模方面，产生式系统被用于模拟算术、阅读、下棋、医学诊断等认知技能，并适合对学习与认知发展过程建模^[8]。以 ACT 认知架构为基础的产生式模型还被用于智能教学系统，覆盖代数、几何与 Lisp 编程等科目^[9]。

迁移的产生式理论认为，前后两项学习任务之所以发生迁移，原因在于两者的产生式存在重叠，重叠越多迁移量越大^[2]。

局限

产生式系统的执行效率较低，规则之间的联系要借助综合数据库建立，求解过程是反复进行的匹配、冲突消解与执行循环^[1]。每条产生式都是独立的程序单元，彼此一般不能直接调用或相互包含，控制不够方便，因此不适宜求解理论性强的难题^[1]。

以产生式为基础的认知教学系统也有明显限制：反馈以产生式为最小单位，有时过于细碎；学生一旦出错便被立即干预，无法沿错误路径看到后果；这类系统对非程序性知识支持较弱，也难以讲授概念^[9]。

在 ACT 一类理论中，经编译得到的产生式最初只针对特定任务，向类似情境的迁移能力相当有限^[10]。

也有实证研究对迁移的估计提出修正：实验显示子任务之间的实际迁移明显多于产生式迁移模型的预测，说明对知识「用途专一性」的强调可能被高估^[11]。

参见

• 产生式系统 —— 由多条产生式按层次组织而成的规则集合，是本词条所述规则的主要组织形式。

• 专家系统 —— 以产生式规则表示领域知识并据此推理的一类人工智能程序。

• 形式文法 —— 把产生式作为重写规则、用于刻画形式语言结构的数学工具。

• 上下文无关文法 —— 产生式左部限定为单个非终结符的文法，常用于定义程序设计语言的语法。

• ACT-R —— 以产生式系统建模人类认知过程与技能获得的认知架构。

• 图灵机 —— 与无限制文法计算能力相当的计算模型，可用于比较产生式系统的表达能力。