隐马尔科夫模型（HMM）详解
隐马尔科夫模型（HMM）详解
前言
本文主要介绍隐马尔科夫模型（HMM）的基本概念及其在语音识别中的应用。HMM是近代语音识别（ASR）任务的重要基石，本文将从基本概念出发，详细讲解其概率计算、学习和预测算法。
一、HMM的基本概念
隐马尔科夫模型是关于时序的概率模型，描述由一个隐藏的马尔科夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测从而产生观测随机序列的过程。隐藏的马尔科夫链随机生成的状态的序列，称为状态序列；每个状态生成一个观测，而由此产生的观测的随机序列，称为观测序列。
设Q是所有可能的状态的集合，V是所有可能的观测的集合：
$$
Q = {q_1, q_2, \cdots, q_N}, V= {v_1, v_2, \cdots, v_M }
$$
其中，N是状态数，M是观测数。
I是长度为T的状态序列，O是对应的观测序列：
$$
I = (i_1, i_2, \cdots, i_T}, O= {o_1, o_2, \cdots, o_T }
$$
HMM由3个概率矩阵建模：
状态转移概率矩阵A：
$$
a_{ij} = \mathbb{P}(i_{t+1} = q_j | i_t = q_i),\ \ \ \ \ \ i = 1,2,\cdots,N; j = 1,2,\cdots,N
$$
是在时刻t处于状态$q_i$的条件下在时刻$t + 1$转移到状态$q_j$的概率。观测概率矩阵B：
$$
b_{j}(o_t) = \mathbb{P}(o_{t} = v_k | i_t = q_j),\ \ \ \ \ \ k = 1,2,\cdots,M; j = 1,2,\cdots,N
$$
是在时刻t处于状态$q_j$的条件下生成观测$v_k$的概率。初始状态概率向量π：
$$
\pi_{i} = \mathbb{P}(i_1 = q_i),\ \ \ \ \ \ i = 1,2,\cdots,N
$$
是时刻$t = 1$处于状态$q_i$的概率。
隐马尔科夫模型λ由π、A、B这3个矩阵构成。
举个例子，假设一个语音识别任务，将语音转写成文字，状态有5个，分别是{"打"，"开"，"灯"，"光"，"架"}，初始5个状态服从均匀分布，即：
$$
\pi^* = (0.2, 0.2, 0.2, 0.2, 0.2)^T
$$
状态转移概率矩阵A：
$$
A^* = \begin{pmatrix}
0 & 0.6 & 0 & 0.1 & 0.3 \
0.2 & 0.2 & 0.4 & 0.2 & 0 \
0 & 0 & 0 & 0.8 & 0.2 \
0.2 & 0 & 0 & 0.8 & 0 \
0 & 0.5 & 0.4 & 0.1 & 0 \
\end{pmatrix}
$$
观测概率矩阵B：
$$
B^* = \begin{pmatrix}
0.5 & 0.5\
0.2 & 0.8\
0.6 & 0.4\
0.65 & 0.35\
0.4 & 0.6\
\end{pmatrix}
$$
于是得到一个隐马尔科夫模型：
$$
\lambda^* = (\pi^, A^, B^*)
$$
得到模型之后，我们提出下面3个问题：
- 概率计算问题：给定模型λ和观测序列O，计算概率P(O|λ)。
- 学习问题：已知观测序列O，估计模型λ的参数。
- 预测问题：已知模型λ和观测序列O，求使P(I|O)最大的状态序列I。即给定观测序列，求最有可能的对应的状态序列。
以上3个问题被称为隐马尔可夫模型的3个基本问题。
二、概率计算算法
2.1 直接计算法
给定模型λ和观测序列O，计算概率P(O|λ)：
$$
\mathbb{P}(O|\lambda) = \sum_I\mathbb{P}(O,I| \lambda) = \sum_I{\color{red} \mathbb{P}(O|I,\lambda) }{\color{blue} \mathbb{P}(I|\lambda) }
$$
直接计算的时间复杂度为O(TN^T)，太过复杂，不可行。
2.2 前向算法
前向算法使用动态规划的方法，降低计算复杂度。
定义前向概率α：
$$
\alpha_t(i)= \mathbb{P}(o_1, o_2, \cdots, o_t, i_t = q_i | \lambda)
$$
（1）初始化：
$$
\alpha_1(i) = \pi_ib_i(o_1), \ \ \ \ \ \ i = 1,2,\cdots, N
$$
（2）递推公式：
$$
\alpha_{t+1}(i) = \sum_{j=1}^N \alpha_{t}(i)a_{ji}b_{i}(o_{t+1}), \ \ \ \ \ \ i = 1,2,\cdots, N
$$
（3）终止：
$$
\mathbb{P}(O|\lambda) = \sum_{i=1}^N \alpha_{T}(i)
$$
计算复杂度变为O(TN^2)。
2.3 后向算法
后向算法是从后向前遍历。
定义后向概率β：
$$
\beta_t(i) = \mathbb{P}(o_{t+1}, o_{t+2}, \cdots, o_T | i_t = q_i , \lambda)
$$
（1）初始化：
$$
\beta_T(i) = 1, \ \ \ \ \ \ i = 1,2,\cdots, N
$$
（2）递推公式：
$$
\beta_{t}(i) = \sum_{j=1}^Na_{ij}b_{j}(o_{t+1}) \beta_{t+1}(j), \ \ \ \ \ \ i = 1,2,\cdots, N
$$
（3）终止：
$$
\mathbb{P}(O|\lambda) = \sum_{i=1}^N \pi_ib_i(o_1)\beta_{1}(i)
$$
2.4 一些特性
利用前向概率和后向概率：
$$
\mathbb{P}(O|\lambda) = \sum_{i=1}^N \sum_{j=1}^N \alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j) \ \ \ \ \ \ t = 1,2,\cdots, T - 1
$$
计算时刻t处于状态$q_i$的概率：
$$
\gamma_t(i) = \frac{ \alpha_t(i)\beta_{t}(i)}{\sum_{j=1}^N \alpha_t(j)\beta_{t}(j)}
$$
三、学习算法
在语音识别中，很少有状态与观测序列的有监督标注，算λ的参数，基本都是用Baum-Welch（EM 算法），如果是 GMM-HMM 模型，由于是用 GMM 来拟合观测概率矩阵，所以 EM 算法要作用在 GMM 的参数上，这种训练方法称为维特比训练。
四、预测算法
4.1 近似算法
近似算法的想法是在每个时刻t选择在该时刻最有可能出现的状态$i_t^$，从而得到一个状态序列$I = (i_1^, i_2^, \cdots, i_T^)$。由 2.4 节知道：
$$
\gamma_t(i) = \mathbb{P}(i_t = q_i|O, \lambda) = \frac{ \alpha_t(i)\beta_{t}(i)}{\sum_{j=1}^N \alpha_t(j)\beta_{t}(j)}
$$
在每一时刻t最有可能的状态：
$$
i_t^* = \arg\max\limits_{1≤i≤N}[\gamma_t(i)], \ \ \ \ \ \ t = 1, 2, \cdots,T
$$
从而得到状态序列$I^* = (i_1^, i_2^, \cdots, i_T^*)$。
4.2 维特比算法
Viterbi 算法仍然是采用动态规划解决预测问题，即求最优路径。
定义递推变量δ：
$$
\delta_t^{i} = \max\limits_{i_1,i_2,\cdots,i_{t-1}} \mathbb{P}(i_t = q_i, i_{t-1}, \cdots, i_1, o_t, \cdots, o_1)
$$
定义保存路径的Ψ：
$$
\Psi_t(i) = \arg\max\limits_{1\le j \le N}[\delta_{t-1}(j)a_{ji}]
$$
（1）初始化：
$$
\delta_1(i) = \pi_ib_i(o_1), \ \ \ \ \ \ i = 1, 2, \cdots, N
$$
$$
\Psi_1(i) = 0, \ \ \ \ \ \ i = 1, 2, \cdots, N
$$
（2）递推公式：
$$
\delta_t(i) = \max\limits_{1\le j \le N} \delta_{t-1}(j) a_{ji} b_i(o_t), \ \ \ \ \ \ i = 1, 2, \cdots, N
$$
$$
\Psi_t(i) = \arg\max\limits_{1\le j \le N}[\delta_{t-1}(j)a_{ji}], \ \ \ \ \ \ i = 1, 2, \cdots, N
$$
（3）终止：
$$
P^* = \max\limits_{1\le i \le N}\delta_T(i)
$$
$$
i_T^* = \arg\max\limits_{1\le i \le N}\delta_T(i)
$$
（4）最优路径回溯：
$$
i_t^* = \Psi_{t+1}(i_{t+1}^)
$$
求得最优路径$I^ = (i_1^, i_2^, \cdots, i_T^*)$。
下面是书上的一个例子，按照 Viterbi 算法，时刻3的最优路径是上面一条线，即（3,3,3）。但是如果按照4.1节近似算法来做的话，结果就会是（3,2,3），到达某一时刻的概率值最大，并不能说明到T时刻概率最大。
五、总结
本文介绍了隐马尔可夫模型的基本概念，和3个基本问题的解决方法。对 HMM 做语音识别感兴趣的读者可以看看 Kaldi的代码。