语音识别笔记(3)-隐马尔可夫模型(HMM)

基本概念

定义

• 隐马尔可夫模型是关于时间序列的概率模型
• 由隐藏的马尔可夫链生成不可观测的隐藏状态序列，再由每个状态生成一个观测而产生观测序列的过程。

组成

符号	含义
$Q=\{q_1, q_2, ... q_N\}$	状态的集合（共N个）
$V=\{v_1, v_2, ... v_M\}$	观测的集合（共M个）
$I=\{i_1, i_2, ... i_T\}$	长度为T的状态序列
$O=\{o_1, o_2, ... o_T\}$	长度为T的观测序列
$A = [a_{ij}]_{N*N}$	状态转移概率矩阵，其中，$a_{ij} = P(i_{t+1} = q_j
$B = [b_{j}(o_t)]_{N*M}$	状态转移概率矩阵，其中，$b_{ij} = P(o_{t} = v_t
$\pi = (\pi_i) $	初始状态概率相量，其中，$\pi_i = P(i_1 = q_i)$，描述在t=1时刻，状态为i的概率

$\lambda = (A, B, \pi)$ 称为HMM的三要素

基本假设

HMM模型有两个基本假设

1. 齐次马尔可夫性假设，隐藏的马尔可夫链在t时刻的状态只与t-1时刻的有关，与其他时刻以及观测状态无关，即：

$$P(i_t|i_{t-1}, o_{t-1}, i_{t-2}, o_{t-2}, ... , i_1, o_1) = P(i_t|i_{t-1}) \\ t=1,2,...,T$$

2. 观测独立性假设，观测值只和当前状态有关，即：

$$P(o_t|i_{t}, i_{t-1}, o_{t-1}, ... , i_1, o_1) = P(o_t|i_{t}) \\ t=1,2,...,T$$

分类

HMM根据观测值是否是离散值，分为离散HMM和连续HMM两类:

离散HMM

离散HMM的观测值是离散的，每个观测有其对应的概率值

连续HMM

连续HMM的观测值是实数或者实数向量，可以用概率密度函数描述观测值的概率分布，例如：

观测值服从单高斯分布：

$$b_j(\boldsymbol{o_t}) = \mathcal{N}(\boldsymbol{o_t}|\boldsymbol{\mu_{j}},\boldsymbol{\Sigma_{j}})$$

观测值服从高斯混合分布：

$$b_j(\boldsymbol{o_t}) = \sum_{k=1}^{K} \pi_{jk} \mathcal{N}(\boldsymbol{o_t}|\boldsymbol{\mu_{jk}},\boldsymbol{\Sigma_{jk}})$$

当HMM的观测概率分布由高斯混合模型（GMM）表示时，合称为GMM-HMM

基本问题

HMM模型有3个基本问题，分别是：

• 概率计算问题
• 预测问题（解码问题）
• 学习问题

概率计算问题

简述

• 已知HMM模型$\lambda = (A, B, \pi) $和观测序列$O={o_1, o_2, …, o_t}$
• 计算产生观测序列$O$的概率，$P(O|\lambda)$

算法

直接计算法

直接计算法通过遍历HMM所有可能产生的隐藏状态，计算各个状态序列下，产生所求观测序列的概率，再将他们相加，从而得到合计的观测序列的概率，即：

$$P(O|\lambda) = \sum_{I} P(O|I, \lambda) * P(I|\lambda) \\ = \sum_{i_1, i_2, ..., i_T} \pi_{i_1} b_{i_1}(o_1)a_{i_1i_2} b_{i_2}(o_2)a_{i_2i_3}... a_{i_{T-1}i_T}b_{i_T}(o_T)$$

由于要计算每个可能的隐藏状态，因此该算法的时间复杂度为：$O(TN^T)$，N是可能的状态数量

前向算法

前向算法通过按时序计算每个状态下产生对应观测的前向概率，并基于当前时刻的前向概率，计算下一时刻的前向概率，避免了重复计算，可以大大降低时间复杂度。

前向概率

前向概率的定义是：给定隐马尔可夫模型$\lambda$，定义到时刻$t$产生部分观测序列为$o_1, o_2, ..., o_t$ 且时刻$t$状态为$q_i$的
概率为前向概率，记作:

$$\alpha_t(i) = P(o_1, o_2, ... o_t, i_t=q_i)$$

计算方法

1. 初值

$$\alpha_1(i) = \pi_ib_i(o_1) , i=1,2...,N$$

2. 递推

$$\alpha_{t+1}(i) = \sum_{j=1}^{N}(\alpha_t(j)a_{ji}) b_i(o_{t+1}) , i=1,2...,N$$

3. 结束

$$P(O|\lambda) = \sum_{j=1}^{N}(\alpha_T(j))$$

时间复杂度降为了$O(TN^2)$

后向算法

后向算法与前向算法类似，区别在于是从时刻T开始，计算产生相应后缀观测序列的概率

后向概率
后向概率的定义是：给定隐马尔可夫模型$\lambda$，在时刻$t$状态的为$q_i$的条件下，从$t+1$到从$T$所产生的部分观测序列为$o_{t+1}, o_{t+2}, ..., o_T$ 的概率称为后向概率，记作:

$$\beta_t(i) = P(o_{t+1}, o_{t+2}, ..., o_T|i_t=q_i)$$

计算方法

1. 初值

$$\beta_T(i) = 1 , i=1,2...,N$$

2. 递推

$$\beta_{t}(i) = \sum_{j=1}^Na_{ij}\beta_{t+1}(j) b_j(o_{t+1}) , i=1,2...,N$$

3. 结束

$$P(O|\lambda) = \sum_{i=1}^N\pi_{i}\beta_{1}(i)b_j(o_{1})$$

预测问题（解码问题）

简述

• 已知HMM模型$\lambda = (A, B, \pi) $和观测序列$O={o_1, o_2, …, o_t}$
• 计算使概率$P(O|I)$最大的状态序列$I=\{i_1, i_2, ..., i_t\}$

算法

维特比算法（Viterb算法）

用动态规划求概率最大的路径（最优路径），一个路径对应一个状态序列

概率最大路径满足以下特点：若概率最大路径在t时刻经过状态i，则从t时刻到T时刻（结束）所对应的路径也是最优路径。即基于t时刻经过状态i的最优路径，计算从t时刻到结束的最优路径，即可获得全局最优路径。

根据这一特点，可以通过从t=1时刻开始，基于前一时刻的最优路径，依次计算每个时刻的各个状态产生对应观测的概率，取最大概率对应的状态作为最优路径，直至得到时刻t=T的最优路径。

计算方法

输入：模型$\lambda = (A, B, \pi) $和观测$O={o_1, o_2, …, o_t}$输出：最优路径$I^={i_1^, i_2^, …, i_t^}$

1. 初始化

$$\delta_1(i) = \pi_ib_i(o_1), i=1,2,...,N \\ \psi_1(i) = 0, i=1,2,...,N$$

2. 递推

$$\delta_t(i) = \mathop{\max}\limits_{1\le j \le N} [\delta_{t-1}(j)a_{ji}]b_i(o_t), i=1,2,...,N \\ \psi_t(i) = \mathop{\arg\max}\limits_{1\le j \le N}[\delta_{t-1}(j)a_{ji}], i=1,2,...,N$$

3. 终止

$$\delta_t(i) = \mathop{\max}\limits_{1\le i \le N} \delta_{T}(i) \\ i_T^* = \mathop{\arg\max}\limits_{1\le i \le N}\delta_{T}(i)$$

4. 最优路径回溯
   从t=T时刻开始，依次求T-1,T-2,…,1时刻，最优路径的状态：

$$i_t^* = \psi_{t+1}(i_{t+1}^*)$$

得到最优路径：$I^*=\{i_1^*, i_2^*, ..., i_t^*\}$

比较

维特比算法和前向算法相比，都是从t=1时刻开始，依次计算各个时刻产生对应观测序列的概率值，不同之处在于，维特比算法基于t-1时刻的概率$\delta$，计算到t时刻状态的概率最大路径，而前向算法则是对能到达当前状态的所有路径的概率求和。

学习问题

概述

• 已知观测序列$O=\{o_1, o_2, ..., o_t\}$
• 估计模型$\lambda$,使$P(O|\lambda)$最大

算法

Viterbi学习算法

Viterbi学习算法将每个观测对齐到某个状态中，使用这些观测值去更新该状态对应的GMM模型参数，然后再更新HMM的参数、用Viterbi算法重新对齐，重复这个过程，直到收敛。

1. 初始化GMM-HMM参数$\lambda = (\pi_i, a_{ij}, \alpha_{jm}, \mu_{jm}, \Sigma_{jm}) $ （后三个为GMM的参数,每个状态j对应一个GMM模型，m表示GMM模型的第m个分量）

2. 基于GMM-HMM参数$\lambda$和Viterbi算法得到状态-观测对齐，得到每个观测对应的隐藏状态

3. 更新参数$\lambda$

• $\hat{\pi_i}=\frac{C(i)}{\sum_k C(k)}$ 其中，$C(i)$表示初始状态为i的次数
• $\hat{a_{ij}}=\frac{C(i->j)}{\sum_k C(i->k)}$，其中，$C(i->j)$表示从状态i转移到状态j的次数
• 根据每个观测对应的状态，使用EM算法计算各个状态所对应的GMM模型的参数$(\alpha_{jm}, \mu_{jm}, \Sigma_{jm}) $

4. 重复2，3步，直到收敛

Baum-Welch学习算法

Baum-Welch学习算法不把观测值和状态一一对应，而是计算观测值对应某个状态的概率，是一种“软对齐”。基于“软对齐”的结果，使用EM算法去更新HMM-GMM模型的参数。

1. 初始化GMM-HMM参数$\lambda = (\pi_i, a_{ij}, (\alpha_{jm}, \mu_{jm}, \Sigma_{jm})) $

2. E步：
   对所有时刻t和状态i，计算：

   1）前向概率$\alpha_t(i)$和后向概率$\beta_{t}(i)$

   2）计算：

$$\zeta_{t}(j, k)=\frac{\sum_{i} \alpha_{t-1}(i) a_{i j} c_{j k} b_{j k}\left(o_{t}\right) \beta_{t}(j)}{\sum_{i=1}^{N} \alpha_{T}(i)} \xi_{t}(i, j)=\frac{\alpha_{t}(i) a_{i j} b_{j}\left(o_{t+1}\right) \beta_{t+1}(j)}{\sum_{i=1}^{N} \alpha_{T}(i)} \gamma_{t}(i)=\sum_{k=1}^{N} \xi_{t}(i, k)$$

其中，$\gamma_{t}$表示状态占用概率，给定模型$\lambda$ ，在时刻$t$处于状态$q_i$的概率为:

$$\gamma_{t}(i)=P\left(i_{t}=q_{i} \mid O, \lambda\right)=\frac{\alpha_{t}(i) \beta_{t}(i)}{\sum_{i=1}^{N} \alpha_{T}(i)}$$

3. M步：

$$\begin{aligned} \hat{\mu}_{j k}=& \frac{\sum_{t=1}^{T} \zeta_{t}(j, k) o_{t}}{\sum_{t=1}^{T} \zeta_{t}(j, k)} \\ \hat{\Sigma}_{j k}=& \frac{\sum_{t=1}^{T} \zeta_{t}(j, k)\left(o_{t}-\hat{\mu}_{j k}\right)\left(o_{t}-\hat{\mu}_{j k}\right)^{T}}{\sum_{t=1}^{T} \zeta_{t}(j, k)} \\ \hat{c}_{j k}=& \frac{\sum_{t=1}^{T} \zeta_{t}(j, k)}{\sum_{t=1}^{T} \sum_{k} \zeta_{t}(j, k)} \\ \hat{a}_{i j}=& \frac{\sum_{t=1}^{T-1} \xi_{t}(i, j)}{\sum_{t=1}^{T-1} \sum_{k=1}^{N} \xi_{t}(i, k)}=\frac{\sum_{t=1}^{T-1} \xi_{t}(i, j)}{\sum_{t=1}^{T-1} \gamma_{t}(i)} \\ \hat{\pi}_{i}=& \gamma_{1}(i) \end{aligned}$$

4. 重复2，3步，直到收敛