生成式艺术和算法创作08-马尔可夫模型

马尔可夫模型 Markov Model

开始的开始，有必要来认识一下主人公，俄国数学家安德雷·安德耶维齐·马尔可夫。

1874 年，18 岁的马尔可夫考入圣彼得堡大学，师从切比雪夫（著名的切比雪夫定理提出者）。他是物理-数学博士，圣彼得堡大学教授，圣彼得堡科学院院士。在概率论、数论、函数逼近论和微分方程等方面卓有成就。

总的来说，马尔可夫模型是一种统计模型，可以用于计算条件概率分布，为一系列的离散事件建模。这就应用很广泛了，哪些是「离散事件」呢？句子中的词汇，音乐中的音符，通过交通灯的车辆数，女票每个月购物的次数……

以「马尔可夫」开头的术语有很多，先来熟悉一下最重要的几个：

• 马尔可夫性质：当一个随机过程在给定现在状态及所有过去状态情况下，其未来状态的条件概率分布仅依赖于当前状态。

• 马尔可夫过程：是一个具备了马可夫性质的随机过程，不具备记忆特质（memorylessness）。换言之，马可夫过程的条件概率仅仅与系统的当前状态相关，而与过去历史或未来状态，都是独立、不相关的。

• 马尔可夫链：具备离散状态的马可夫过程，通常使用离散的时间集合定义。

• 马尔可夫模型：用马尔科夫过程生成序列的算法模型

它们之间的关系大概可以这样划分：

在马尔可夫模型中

• Xt 是时间 t 时表示音符的随机变量

• P(Xt) 是随机事件 Xt 的概率分布

马尔可夫模型可以基于「上文」做出判断和预测，未来状态只取决于当前状态或者限定范围的过去状态。

实现马尔可夫模型的学习算法有几个步骤：

• 构建一个 transition count table (state transition matrix)，计算每一种可能的上下文的频率分布

• 用每一种组合的 count 除以所有的组合总数，即下表中每一行加起来为 1

• 随机选择一个起始值，根据概率表格选择下一个序列值

马尔可夫模型生成算法其实也是一种random walk，根据转换概率分布，基于目前已经生成的序列，随机选择下一个序列值。

以一段乐曲为例，它由音符 B2,C4#,D4,E4,F4#,G4,G4#,A4,B4,C5#,D5,E5 组成。计算每一个音符后面紧跟着的音符的出现概率。例如，最后一个音符 E5，出现在它后面的音符只有 A4 和 C5#，出现概率分别是 6/16 和 10/16。当生成新的序列时，如果当前音符是 E5，那么根据表格，下一个音符只可能是 A4 或 C5#。

再来看一个三节点的马尔可夫链：

这首马尔可夫旋律以 state_0 开始，播放一个八分音符 Eb。然后选择一个新的状态。选择 state_0，state_1 或 state_2 的概率相等，都是 1/3。假设选择了 state_2，则播放下加二间的十六分音符 G。从 state_2 开始，state_0 被选择的概率是 1/10，state_1 是 2/10，state_2 是 7/10。

因为马尔可夫模型状态是离散的，可以用有限状态的自动机 (automata) 来表示。

变量马尔可夫模型

在随机过程中，变量马尔可夫（Variable order Markov Models, VOM）模型是一类重要的模型，它扩展了马尔可夫模型。

马尔可夫模型中，具有马尔可夫性质的序列中的每个随机变量，取决于固定数量的随机变量；在 VOM 模型中，该数量的调节随机变量可以基于观察到的特定实现而变化。

这个实现序列通常被称为上下文 ; 因此 VOM 模型也称为上下文树。调节随机变量数量的灵活性对于许多应用来说是非常有利的，例如统计分析、分类和预测。

变量马尔可夫模型一般由三部分组成：

• Counting：建立转换表，这是预测的来源

• Smoothing：处理未见过的事件/序列

• Variable length modeling:

• A transition matrix

• Probabilistic suffix tree

• Factor Oracle, and Context Tree Weighting method (CTW)

• Lempel-Ziv 78 and its improvement LZ-MS

• Prediction by partial match

它的缺点之一是难以产生语料之外的内容。

隐马尔科夫模型

隐马尔可夫模型（Hidden Markov Model，HMM）是统计模型，它用来描述一个含有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数，然后利用这些参数来作进一步的分析，例如模式识别。

在一般的马尔可夫模型中，状态对于观察者来说是直接可见的。这样状态的转换概率便是全部的参数。

而在隐马尔可夫模型中，状态并不是直接可见的，但受状态影响的某些变量是可见的。每一个状态在可能输出的符号上，都有一定的概率分布。因此输出符号的序列能够透露出状态序列的一些信息。

也就是说，HMM 系统的实际状态是隐藏的，只能观察到 emission probilities。

HMM 常用来学习两个耦合的内容语料。例如，在语音识别中，可见的信息是音频信号，隐藏的信息是语音词汇。又例如，旋律是可见信息，伴奏/ 和声 是隐藏的信息。

最常见的三种 Hidden Markov Model 算法：

• the forward algorithm: 计算特定序列的概率，假设已知 transitions and observation 概率和初始状态

• the Baum-Welch algorithm：找出被观测序列中最常见的参数

• the Viterbi algorithm：维特比算法，基于观测序列计算隐藏状态最可能的序列（viterbi path）

隐马尔科夫模型的优势：

• 是学习和生成离散序列最有效和使用广泛的算法

• 可以对横轴和纵轴的相关性都建模，HMM 是随机耦合过程

• 比马尔可夫模型更好保留原始的数据结构

劣势：

• 需要有很好的领域知识来调整模型结构和参数

• 需要相对大的训练数据集

马尔可夫模型在音乐中的应用

Lejaren Hiller 在 1957 年完成了算法生成的弦乐四重奏「依利亚克组曲」（Illiac Suite），这也是历史上第一支完全由计算机生成的音乐作品。首先使用马尔可夫链模型来产生有限控制的随机音符，之后利用和声与复调的规则测试这些音符，最后选择符合规则的材料，修改、组合成传统音乐记谱的弦乐四重奏。

该作品分为四个乐章：

• 第一乐章：计算机生成的不同长度的固定主题旋律

• 第二乐章：使用变奏的规则生成的四声部音乐

• 第三乐章：通过计算机对节奏、动态和演奏法的不同处理生成的音乐

• 第四乐章：通过衍生算法和马尔可夫链的不同模型及概率生成的音乐（pitch, intervals and textures）

Iannis Xenakis在他 1958 年的专辑 Analogique 中就使用了马尔可夫链来作曲。

在他的著作 Formalized Music: Thought and Mathematics in Composition 里详细描述了使用马尔可夫模型的算法。

用马尔可夫模型生成音乐的优势，包括符合直觉、容易理解，以及计算量小。但也存在一些问题。例如，输出相当随机、缺乏整体结构；抽象层级有限，容易重复语料库中的片段；限于一维符号序列；限于风格模仿等等。

Ref

- [Markov model - Wikiwand](https://www.wikiwand.com/en/Markov_model)

- [马尔可夫性质 - Wikiwand](https://www.wikiwand.com/zh-hans/%E9%A9%AC%E5%B0%94%E5%8F%AF%E5%A4%AB%E6%80%A7%E8%B4%A8)

- [马可夫过程 - Wikiwand](https://www.wikiwand.com/zh-hans/%E9%A6%AC%E5%8F%AF%E5%A4%AB%E9%81%8E%E7%A8%8B)

- [隐马尔可夫模型 - Wikiwand](https://www.wikiwand.com/zh-hans/%E9%9A%90%E9%A9%AC%E5%B0%94%E5%8F%AF%E5%A4%AB%E6%A8%A1%E5%9E%8B)

- [Variable-order Markov model - Wikiwand](https://www.wikiwand.com/en/Variable-order_Markov_model)

- [Markov Chains explained visually](http://setosa.io/ev/markov-chains/)

- [Three Node Markov Chain](http://codehop.com/three-node-markov-chain/)

- [算法作曲历险记01-简史 | 00's Adventure](https://www.uegeek.com/170713-algorithmic-composition-1.html)

- [Iannis Xenakis - Wikiwand](https://www.wikiwand.com/en/Iannis_Xenakis)

- [Harmonic Progression](http://metacreation.net/project_1/)

- [Realtime Generation of Harmonic Progressions Using Controlled Markov Selection | PDF](http://www.sfu.ca/~eigenfel/ControlledMarkovSelection.pdf)

HackYourself 创造者系列

👓 👓 👓