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

• 生成式艺术和算法创作01-概述
• 生成式艺术和算法创作02-随机和噪声
• 生成式艺术和算法创作03-混沌和分形
• 生成式艺术和算法创作04-规则系统
• 生成式艺术和算法创作05-Tessellation
• 生成式艺术和算法创作06-形状语法
• 生成式艺术和算法创作07-向自然致敬的 L-system

马尔可夫模型 Markov Model

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

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

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

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

• 马尔可夫性质：当一个随机过程在给定现在状态及所有过去状态情况下，其未来状态的条件概率分布仅依赖于当前状态。
• 马尔可夫过程：是一个具有了马可夫性质的随机过程，不具有记忆特质（memorylessness）。换言之，马可夫过程的条件概率仅仅与系统的当前状态相关，而与过去历史或者未来状态，都是独立、不相关的。
• 马尔可夫链：具有离散状态的马可夫过程，通常使用离散的时间集合定义。
• 马尔可夫模型：用马尔科夫过程生成序列的算法模型

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

在马尔可夫模型中

• 是时间 t 时表示音符的随机变量
• 是随机事件 的概率分布

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

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

• 构建一个 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/VMM/VOMM）模型是一类重要的模型，它扩展了马尔可夫模型。

马尔可夫模型中，具备马尔可夫性质的序列中的每个随机变量，取决于固定数量的随机变量；在 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

隐马尔可夫模型（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），这也是历史上第一支完全由计算机生成的音乐作品。首先使用马尔可夫链模型来产生有限控制的随机音符，之后利用和声与复调的规则测试这些音符，最后选择符合规则的材料，修改、组合成传统音乐记谱的弦乐四重奏。

[图片上传失败...(image-ecba91-1543588728051)]

Lejaren Hiller - Illiac Suite for String Quartet [4/4] - YouTube

该作品分为四个乐章：

• 第一乐章：计算机生成的不同长度的固定主题旋律
• 第二乐章：使用变奏的规则生成的四声部音乐
• 第三乐章：通过计算机对节奏、动态和演奏法的不同解决生成的音乐
• 第四乐章：通过衍生算法和马尔可夫链的不同模型及概率生成的音乐（pitch, intervals and textures）

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

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

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

Ref

• Markov model - Wikiwand
• 马尔可夫性质 - Wikiwand
• 马可夫过程 - Wikiwand
• 隐马尔可夫模型 - Wikiwand
• Variable-order Markov model - Wikiwand
• Markov Chains explained visually
• Three Node Markov Chain
• 算法作曲历险记01-简史 | 00's Adventure
• Iannis Xenakis - Wikiwand
• Harmonic Progression
• Realtime Generation of Harmonic Progressions Using Controlled Markov Selection | PDF

00 的文集

• HackYourself
• Art & Code
• 产品设计思维训练营
• FabAcademy 创客炼成记
• Make Noise
• 历史大杂烩