生成式艺术和算法创作04-规则系统

实战系列

规则系统

In computer science, rule-based systems are used as a way to store and manipulate knowledge to interpret information in a useful way. --Wiki

规则系统（rule-based systems）的类型：

• 生成语法和乔姆斯基等级（乔姆斯基在20世纪50年代提出）

• 形式逻辑系统和逻辑程序：推理规则，定理求解程序，论证系统，案例推理系统

• 专家系统：将特定领域的专业知识，编码在可以执行演绎和归纳的框架中

• 跃迁过程网络（Transition-based networks）：有限状态自动机（finite state automata）和扩展随机系统（extension stochastic systems）如马尔可夫模型，马尔可夫链，以及隐马尔可夫模型

乔姆斯基（C.Chomsky）最初从产生语言的角度研究语言；他将语言 L 形式地定义为由一个字母表中的字母 ∑ 组成的一些串的集合   ，可以在字母表上按照一定的规则定义一个方法，该文法产生的所有句子组成的集合，就是该文法产生的语言。形式语言是模拟这些语言的一类数学语言，它采用数学符号，按照严格的语法规则构成。

那么，到底什么是规则呢？

α→β

α 和 β 是由终结符（terminal symbol 如名词、动词等）或非终结符（如句子、动词短语、名词短语等）组成的表达式。

生成文法

生成文法（generative grammar）尝试给出一套规则，能正确的预测在一种语言中怎样的词汇组合能成为正确的句子，这些规则通常也能预测句子中的构词法。生成文法可以借助乔姆斯基等级来描述和比较。

文法 G 是一个四元组：G =（V, T, P, S）

• V：变量/非终结符号的非空有穷集；

• T：终结符的非空有穷集，V∩T=Ø；

• P：生成式的非空有穷集合；

• S：开始符号，S 是 V 中的元素。

P 生成式的基本形式是 α→β，这里 α 和 β 都是（V∪T）中的元素，即它们都是由变元和终结符组成的符号串，但要求 α 至少含有一个非终结符；在形式文法定义中 P 至关重要，它决定了语言是如何构造出来的。

根据 P 中生成式 α→β 的特点，可以将形式文法及其产生的形式语言分类，构成形式语言谱系，对应四种自动机：

• 0 型文法，又称为短语文法：对生成式 α→β 不作特殊限制，α 和 β 可以是任意的文法符号串，当然 α 不能是空字符串；0 型文法是形式语言谱系中最大的文法类，是图灵机所识别的语言类，即递归可枚举语言。

• 1 型文法，又称为上下文有关文法：要求生成式 α→β 满足 |α|≤|β|，即 β 要至少和 α 一样长；由 1 型文法产生的语言称为 1 型语言或上下文有关语言，是非确定型线性有界自动机所识别的语言类。

• 2 型文法，又称为上下文无关文法（context-free grammars ）：要求生成式 α→β 中的 α 必须是变元；由 2 型文法产生的语言称为 2 型语言或上下文无关语言，是由下推自动机所识别的语言类。

• 3 型文法，又称为正则文法，这种文法分为两种类型：生成式的形式必须是 A→ωB 或 A→ω，其中 A，B 都是变元，ω 是终结符串（可以是空串），这种特殊的正则文法称为右线性文法；第二类正则文法称为左线性文法，它要求生成式必须是 A→Bω，或 A→ω 的形式。由正则文法生成的语言称为正则语言，它是有穷自动机所识别的语言类。

上述定义的 4 种语言类具有依次包含关系，即对于 i＝0，1，2，在不考虑空字符串时，i 型语言都真包含 i＋1 型语言。

通过这种语法推导出的句子可以用派生树描述。相邻的单词被组合成成分，可以进一步与其他单词或成分组合以创建分层树结构。

看着很晕吧？…… 我们还是来看一些艺术创作领域的例子吧！

法国诗人雷蒙·格诺 (Raymond Queneau) 是国际文学团体乌力波（Oulipo, Ouvroir de littérature potentielle, 潜在文学工场）的创始人，其会员中名气较大的有意大利作家卡尔维诺（Italo Calvino），法国作家乔治·佩雷克（Georges Perec），此外还有一些成员是和文学不搭边的数学家。

Raymond Queneau 的诗集「百万亿首诗」(Cent mille milliards de poèmes) 是一本不寻常的诗集：表面上看这本书是由 10 首十四行诗构成，10 首诗的同一行都押同一个韵，实际上它能排列组合成一百万亿首诗。首行诗句有 10 种选择，第二行诗句也有 10 种选择，十四行诗组合在一起也就得到了 10 的 14 次方首各不相同的诗了。

诗集的设计也很特别，每一行都被剪成纸条，读完第一首诗的第一行，然后把第二行的纸条折过去读第二首诗的第二行，以此类推……这便是一个语法生成系统了。

自动机

最简单的来说，自动机（Automaton）就是具有离散输入输出的数学模型，接受一定的输入，执行一定的动作，产生一定的结果。

状态是一个标识，能区分自动机在不同时刻的状况。可以使用状态迁移描述整个工作过程。有限状态系统具有任意有限数目的内部状态。自动机的本质是，根据状态、输入和规则决定下一个状态，即

状态 ＋ 输入（激励）＋ 规则 → 状态迁移

可能的状态、运行的规则都是事先确定的。一旦开始运行，就按照事先确定的规则工作，因此叫自动机。

根据结构不同，自动机又可分为：

• 有限自动机，可以认为是由一个带有读头的有限控制器和一条写有字符的输入带组成；

• 下推自动机，可以看作是由一条输入带、一个有限控制器和一个下推栈组成；

• 基本图灵机，由一个具有读写头的有限控制器和一条无限带组成

在这个系列的后续文章中，还会单独来讲讲元胞自动机。

Transition network

Transition Networks 是一系列有限状态自动机。

如果用有向图表示，节点表示状态，边缘表示转换过程。每一个自动机表示一个非终结符；每一个转换过程产生一个非终结符或终结符。

Augmented transition networks (ATN) 是一种形式语言操作化定义的图论结构。ATN 建立在使用有限状态机来解析句子的基础上，它理论上可以分析任何句子的结构，无论多么复杂。ATN 的一个优点是延迟决策——当模糊性出现时，许多语法会在对句子的了解还不够时进行猜测。而 ATN 使用递归来推迟决定，直到对句子了解得更多。

算法作曲的先驱 David Cope 创作的 EMI 是著名的和开创新的系统。EMI 使用了 ATN，由系统分析和分割给定的语料库，然后重新组合元素。

在这里，终结符是各种音乐片段，非终结符元素则捕捉各种层级的片段结构。

Ref

- [Rule-based system - Wikiwand](https://www.wikiwand.com/en/Rule-based_system)

- [Generative grammar - Wikiwand](https://www.wikiwand.com/en/Generative_grammar)

- [Context-free grammar - Wikiwand](https://www.wikiwand.com/en/Context-free_grammar)

- [Oulipo - Wikiwand](https://www.wikiwand.com/en/Oulipo)

- [Automaton - Wikiwand](https://www.wikiwand.com/en/Automaton)

- [乌力波（2） (豆瓣)](https://book.douban.com/subject/24089566/)

- [形式语言与自动机](https://zhuanlan.zhihu.com/p/28624160)

- [EMI](http://artsites.ucsc.edu/faculty/cope/experiments.htm)

HackYourself 创造者系列

👓 👓 👓