EP42

EP42: Chord Recognition — From Chroma Vectors to Viterbi Decoding

从色度向量到Viterbi解码

▶ 5:51 Statistics/MLSignal ProcessingAbstract Algebra

前置知识

EP04 All-Interval Rows and ℤ₁₂ EP21 From Markov to Diffusion — Sixty Years of AI Composition EP35 The Phase Vocoder — Mathematics of Pitch Shifting EP41 The Mathematics of Source Separation — NMF to Demucs

概述

你播放一首歌，App 在零点一秒内报出和弦名。这不是凭感觉猜测，也不是查数据库。背后是一个隐马尔可夫模型（Hidden Markov Model, HMM），和一个格形图上的最短路径算法（Viterbi）。

本集从信号处理（STFT 色度向量）出发，经过模板匹配，建立 HMM 的三要素，最终用 Viterbi 动态规划在 $O(T \cdot N^2)$ 时间内精确解码最优和弦序列。

前置知识

STFT 与相位声码器（EP35） — 短时傅里叶变换
全音程列与 $\mathbb{Z}_{12}$ （EP04） — 十二音类循环群结构
马尔可夫链与 AI 作曲（EP21） — 离散 Markov 链
人声分离（EP41） — 上游信号分离流程

定义

Definition 42.1 (色度特征向量)

设音频帧的短时傅里叶变换幅度谱为 $|X[k]|$ ， $k = 0, 1, \ldots, K-1$ 。 色度向量 $\mathbf{c} \in \mathbb{R}^{12}$ 的第 $p$ 分量（ $p \in \mathbb{Z}_{12}$ ）定义为

c_p = \sum_{\substack{k : \, \text{pitch-class}(k) = p}} |X[k]|^2

其中 $\text{pitch-class}(k) = \lfloor 12 \log_2(f_k / f_{\text{ref}}) \rfloor \bmod 12$ ， $f_k$ 为第 $k$ 个频率箱的中心频率， $f_{\text{ref}}$ 为参考频率（通常取 C0 = 16.35 Hz）。

色度向量将所有八度的能量折叠到 $\mathbb{Z}_{12} = \{0, 1, \ldots, 11\}$ 上，实现八度等价： $c_p$ 汇聚了 C4、C5、C6 等所有八度上音名为 $p$ 的能量。

Definition 42.2 (余弦相似度模板匹配)

设 24 个和弦模板为 $\{\mathbf{t}_j\}_{j=1}^{24}$ （12 个大调 + 12 个小调），每个模板 $\mathbf{t}_j \in \{0,1\}^{12}$ ，在和弦包含的音名处取 1，其余取 0（大三和弦取 3 个音名，小三和弦取 3 个音名）。

帧 $x$ 属于和弦 $j$ 的模板匹配得分定义为

\text{sim}(\mathbf{c}, \mathbf{t}_j) = \frac{\mathbf{c} \cdot \mathbf{t}_j}{\|\mathbf{c}\| \cdot \|\mathbf{t}_j\|}

逐帧识别结果为 $\hat{j} = \arg\max_j \, \text{sim}(\mathbf{c}, \mathbf{t}_j)$ 。

Definition 42.3 (隐马尔可夫模型（HMM）)

一个隐马尔可夫模型 $\lambda = (A, B, \pi)$ 由三部分组成：

转移矩阵 $A \in \mathbb{R}^{N \times N}$ ： $A_{ij} = P(q_t = j \mid q_{t-1} = i)$ ，其中 $N = 24$ （和弦数），满足 $A_{ij} \geq 0$ ， $\sum_j A_{ij} = 1$ 。
发射概率 $B = \{b_j(\mathbf{o})\}$ ：给定隐状态 $j$ ，观测 $\mathbf{o}$ （色度向量）的概率。常用 12 维高斯模型：
$b_j(\mathbf{o}) = \mathcal{N}(\mathbf{o} \mid \boldsymbol{\mu}_j, \boldsymbol{\Sigma}_j)$ 其中 $\boldsymbol{\mu}_j$ 为和弦 $j$ 的理想色度模板。
初始概率 $\pi \in \mathbb{R}^N$ ： $\pi_j = P(q_1 = j)$ ，满足 $\sum_j \pi_j = 1$ 。实践中常取均匀分布 $\pi_j = 1/24$ ，或从语料统计得到。

隐状态序列 $q_1, q_2, \ldots, q_T$ 对应 $T$ 帧音频的真实和弦标签，不可直接观测；观测序列 $\mathbf{o}_1, \mathbf{o}_2, \ldots, \mathbf{o}_T$ 为色度向量序列。

主要定理

Theorem 42.1 (Viterbi 最优性)

给定 HMM $\lambda = (A, B, \pi)$ 和观测序列 $\mathbf{o}_{1:T}$ ，定义 Viterbi 变量

\delta_t(j) = \max_{q_1, \ldots, q_{t-1}} P(q_1, \ldots, q_{t-1}, q_t = j, \mathbf{o}_{1:t} \mid \lambda)

则 $\delta_t(j)$ 满足递推关系

\delta_t(j) = \left[\max_{i=1}^{N} \delta_{t-1}(i) \cdot A_{ij}\right] \cdot b_j(\mathbf{o}_t), \quad t = 2, \ldots, T

初始条件 $\delta_1(j) = \pi_j \cdot b_j(\mathbf{o}_1)$ 。

令 $\psi_t(j) = \arg\max_{i} \delta_{t-1}(i) \cdot A_{ij}$ 为反向指针。最优和弦序列由回溯得到：

q_T^* = \arg\max_j \delta_T(j), \qquad q_t^* = \psi_{t+1}(q_{t+1}^*), \quad t = T-1, \ldots, 1

该序列 $q_{1:T}^*$ 最大化联合概率 $P(q_{1:T}, \mathbf{o}_{1:T} \mid \lambda)$ ，时间复杂度为 $O(T \cdot N^2)$ 。

Proof.

正确性（最优子结构）：

设 $q_{1:T}^*$ 是最优序列。对任意 $t < T$ ，子序列 $q_{1:t}^*$ 必是到达 $q_t^*$ 的最优路径。若否，设存在更优路径 $q_{1:t}'$ 到达 $q_t^*$ ，则将 $q_{1:t}'$ 与 $q_{t+1:T}^*$ 拼接，得到比 $q_{1:T}^*$ 更优的序列，矛盾。

因此， $\delta_t(j)$ 确实是到达 $(t, j)$ 的最优路径的概率，递推正确。

复杂度：

对每个时刻 $t$ 和每个状态 $j$ ，计算 $\max_i \delta_{t-1}(i) \cdot A_{ij}$ 需 $O(N)$ 。共 $T$ 个时刻、 $N$ 个状态，总复杂度 $O(T \cdot N^2)$ 。

对比暴力枚举所有路径： $N^T$ 条路径，对 $N = 24$ 、 $T = 100$ 即 $24^{100} \approx 10^{138}$ ，远超宇宙原子数（ $\approx 10^{80}$ ），计算不可行。动态规划将复杂度从指数降为多项式。 $\square$

Theorem 42.2 (对数空间等价性)

设 $\delta_t(j) > 0$ （排除零概率情形）。令 $\tilde{\delta}_t(j) = \log \delta_t(j)$ ，则

\tilde{\delta}_t(j) = \left[\max_{i} \tilde{\delta}_{t-1}(i) + \log A_{ij}\right] + \log b_j(\mathbf{o}_t)

该递推与原始 Viterbi 递推产生完全相同的最优路径： $\arg\max_j \tilde{\delta}_t(j) = \arg\max_j \delta_t(j)$ 。

Proof.

对数函数 $\log: (0, +\infty) \to (-\infty, +\infty)$ 是严格单调递增函数，因此

\arg\max_j f(j) = \arg\max_j \log f(j)

对任何正值函数 $f$ 成立。

又因 $\log(a \cdot b) = \log a + \log b$ ， $\log(\max_i a_i) = \max_i \log a_i$ （严格单调性），原始递推

\delta_t(j) = \max_i [\delta_{t-1}(i) \cdot A_{ij}] \cdot b_j(\mathbf{o}_t)

取对数后恰好变为

\tilde{\delta}_t(j) = \max_i [\tilde{\delta}_{t-1}(i) + \log A_{ij}] + \log b_j(\mathbf{o}_t)

乘法变加法，max 保持不变。 $\square$

实际意义： $T = 100$ 帧时概率连乘可达 $\sim 10^{-138}$ ，超出 float64 下溢阈值（ $\approx 10^{-308}$ ），对数空间操作完全避免此问题。零概率存储为 $-\infty$ （Python float('-inf')），不影响 $\max$ 操作的正确性。

Prop 42.1 (色度折叠保留音名信息)

色度向量 $\mathbf{c}$ 是 $\mathbb{Z}_{12}$ -等变的：对频谱的整数倍频移（即移调 $k$ 个半音），色度向量循环移位 $k$ 位。形式地，若 $\mathbf{c}(\mathbf{x})$ 是信号 $\mathbf{x}$ 的色度向量， $\mathbf{x}_k$ 是 $\mathbf{x}$ 移调 $k$ 个半音后的信号，则

\mathbf{c}(\mathbf{x}_k)_p = \mathbf{c}(\mathbf{x})_{(p - k) \bmod 12}

Proof.

移调

k

个半音将频率

f

映射到

f \cdot 2^{k/12}

。于是 pitch-class

(f \cdot 2^{k/12}) = (\text{pitch-class}(f) + k) \bmod 12

。色度折叠将各频率箱按 pitch-class 累加，故移调后每个分量的索引增加

k \pmod{12}

，等价于向量循环移位

k

位。

\square

数值示例

暴力搜索的不可行性：

24^{100} = (2^3 \cdot 3)^{100} = 2^{300} \cdot 3^{100}

\log_{10}(24^{100}) = 100 \log_{10} 24 = 100 \times 1.3802 \approx 138.0

即 $24^{100} \approx 10^{138}$ ，而宇宙可观测粒子数 $\approx 10^{80}$ 。

Viterbi 规模： $N = 24$ ， $T = 100$ ，需要存储 $24 \times 100 = 2400$ 个 $\delta$ 值和同等数量的反向指针，总空间 $O(TN)$ ，时间 $O(TN^2) = O(100 \times 576) = O(57600)$ 次运算——实时可行。

音乐联系

音乐语法的数学编码

HMM 转移矩阵 $A$ 将调性引力（tonal gravity）量化为概率。在 C 大调语境下， $A_{\text{C→G}} \gg A_{\text{C→F\sharp}}$ ，因为 G 大调（属和弦）是 C 大调最强的功能和声解决，而 F♯ 大调（三全音关系）在古典和声中极少出现。

通过从巴赫众赞歌或流行歌曲数据集统计 $A$ ，模型自动学到和声语法规则。这正是 EP21 中 Markov 链的直接推广：原 Markov 链建模可观测音符序列， HMM 在此之上增加了"隐层"——和声功能（属、主、下属）不可直接听到，只能从声音特征（色度向量）推断。

识别局限与乐理边界

HMM 基于大/小三和弦的 24 个模板，无法处理：

异名同音：E♯ 与 F 色度位置相同，但在 B 大调（功能：增八度）和 C 大调（功能：自然四度）中作用不同
副属和弦：如 C 大调中的 D7（属于 G 的属和弦），激活两个模板
爵士变音：Cm(maj9)♯11 等高叠和弦激活 8 个以上音名位置

这些局限来自模型的生成假设：HMM 假定观测条件独立于过去，而人类和声感知实际上对上下文高度敏感。条件随机场（CRF）的判别框架可部分缓解此问题，但代价是失去 Viterbi 解码的精确性。

局限性与开放问题

调内识别 vs 调性识别：本集仅识别逐帧和弦，未处理全局调性（key）。调性识别需要在更长时间尺度（整首曲子）上建模，Krumhansl-Schmuckler (1990) 用轮廓相关系数定义调性中心，这是 EP43 的主题。
多声部叠置：交响乐中多个声部同时演奏不同和弦，色度向量叠加，单和弦 HMM 无法分解。需要多和弦联合 HMM 或源分离（EP41）前处理。
实时系统延迟：Viterbi 需要完整序列后向回溯。实时系统需改用在线 Viterbi（滑窗回溯）或前向算法（给出边际概率，无需回溯），代价是识别精度下降。
深度神经网络发射估计：现代系统（如 ACE-Chroma, 2022）用 CNN 估计 $b_j(\mathbf{o}_t)$ ，取代高斯模型，精度显著提升，但丢失了 Viterbi 解码的可解释性。

Conjecture (神经 HMM 的 Viterbi 最优性保持)

若用神经网络估计的发射对数概率

\log \hat{b}_j(\mathbf{o}_t)

替换高斯

\log b_j(\mathbf{o}_t)

， Viterbi 递推在形式上仍然正确，且仍给出在

\hat{b}

下的最优序列。 开放问题：神经估计的

\hat{b}

是否满足与真实分布的充分近似条件，使得最优序列与人类标注一致？目前缺乏理论保证，依赖经验验证。

参考文献

Rabiner, L. R. (1989). A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of the IEEE, 77(2), 257–286.
Viterbi, A. J. (1967). Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Transactions on Information Theory, 13(2), 260–269.
Müller, M. (2015). Fundamentals of Music Processing. Springer. Ch. 5 (Chord Recognition).
Bello, J. P., & Pickens, J. (2005). A robust mid-level representation for harmonic content in music signals. Proceedings of ISMIR, 304–311.
Harte, C., Sandler, M., Abdallah, S., & Gómez, E. (2005). Symbolic representation of musical chords: A proposed syntax for text annotations. Proceedings of ISMIR.
Krumhansl, C. L. (1990). Cognitive Foundations of Musical Pitch. Oxford University Press.
Cho, T., & Bello, J. P. (2014). On the relative importance of individual components of chord recognition systems. IEEE/ACM Transactions on Audio, Speech, and Language Processing, 22(2), 477–492.