隐马尔可夫模型

Posted on 2020-01-25 Edited on 2021-10-26 In Algorithm

最近学习了一下 ASR 相关的知识，一个经典的算法就是隐马尔可夫模型，分两篇博客记录一下

马尔可夫链

马尔科夫链是一种离散状态的马尔可夫序列。其状态空间具有离散和有限性 $q_t \in \{s^{(j)},j=1,2,...,N\}$。每个离散值都表示一个状态。其转移概率定义为

\[P(q_t=s^{(j)}|q_{t-1}=s^{(i)})=a_{ij}(t),i,j=1,2,...,N\]

再加上初始状态发布概率，就可以确定一个马尔可夫链了。如果转移概率与时间无关，则得到的是齐次马尔可夫链。一般来说，齐次的转移概率会用矩阵表达

\[\boldsymbol{A}=[a_{ij}], a_{ij} \ge 0 \ \forall i,j;\sum^{N}_{j=1}a_{ij}=1 \ \ \forall i\]

这里的 $a_{ij}$ 指的是从状态 $s^{i}$ 转移到 $s^{j}$ 的概率。有个比较有意思的性质，即马尔可夫链的渐进收敛：$p_i(t) \rightarrow \pi(q^{(i)})$，当 $t $。它需要满足以下条件

\[\hat{\pi}(s^{(i)})=\sum^N_{j=1}a_{ij}\hat{\pi}(s^{(j)}),\forall i\]

隐马尔可夫链

刚刚提到的是可观测马尔可夫链，即它的输出和它的状态一一对应，观测和状态之间没有随机性。作为马尔可夫链的一种扩展，隐马尔可夫链用一个观测概率分布与每一个状态对应，这样其状态就不能直接观察，而只能通过观测概率分布函数表露。

这里要注意，如果各个状态之间的观测概率没有重叠，那么实际上就不叫隐马尔可夫模型了。因为尽管状态中有了随机性，但对一个特定的观测，总能找到一个确定的状态与之对应。

我们设齐次马尔可夫链（就是渐进收敛的）

转移概率矩阵 $\boldsymbol{A}=[a_{ij}],i,j=1,2,...N$ 共有 $N$ 个状态 $a_{ij}=P(q_t=j | q_{t-1}=i)$。
初始概率 $\pi=[\pi_{i}],i=1,2,...,N$，其中 $\pi_i=P(q_1=i)$
观测分布概率 $p(\boldsymbol{o}_t|s^{i}),i=1,2,...,N$ 如果 $\boldsymbol{o}_t$ 是离散的，则每个状态对应的概率分布用来描述观测 $\{\boldsymbol{v}_1,\boldsymbol{v}_2,...,\boldsymbol{v}_k\}$ 为 $b_i(k)=P(\boldsymbol{o}_t=\boldsymbol{v}_k|q_t=i)$。如果是连续的，则可以使用概率密度函数表达

典型的可以用多元混合高斯分布来作为观测概率的概率密度函数。下面是状态 $i$ 时的观测概率密度函数

\[b_i(\boldsymbol{o}_t)=\sum^M_{m=1}\frac{c_{i,m}}{(2\pi)^{D/2}|\Sigma_{i,m}|^{1/2}}\exp[-\frac12(\boldsymbol{o}_t-\boldsymbol{\mu}_{i,m})^T\Sigma_{i,m}^{-1}(\boldsymbol{o}_t-\boldsymbol{\mu}_{i,m})]\]

对于混合高斯 HMM（简写为 GMM-HMM），其参数集 $\Lambda_i$ 包括混合成分权重 $c_{i,m}$ ，均值向量 $\boldsymbol{\mu}_{i,m}$ 和高斯分布协方差矩阵 $\Sigma_{i,m}$

确定模型参数后，高斯 HMM 可以看作一个观察值序列 $\boldsymbol{o}_t,t=1,2,...,T$ 的生成器。这样，在 t 时刻，数据根据下面的公式生成，其中时刻 $t$ 的状态 $i$ 取决于马尔可夫链的演变，受 $a_{ij}$ 影响。

\[\boldsymbol{o}_t=\boldsymbol{\mu}_i+\boldsymbol{r}_t(\Sigma_i)\] \[\boldsymbol{r}_t(\Sigma_i)=N(0,\Sigma_i)\]

这里因为 $\boldsymbol{o}_t$ 是独立同分布，上面的 HMM 会生成一个局部平稳或者分段平稳的序列，称之为平稳状态 HMM。

有一个对平稳状态 HMM 的简单扩展如下

\[\boldsymbol{o}_t=\boldsymbol{g}_t(\Lambda_i)+\boldsymbol{r}_t(\Sigma_i)\]

把 $\boldsymbol{\mu}_i$ 替换成一个随时间变化的函数，我们便得到了趋势 HMM，它是一种非平稳状态的 HMM。

隐马尔可夫模型似然度计算

设 $\boldsymbol{q}_1^T={q_1,...,q_T}$ 是 GMM-HMM 中的一个有限长度状态序列， $P(\boldsymbol{o}_1^T,\boldsymbol{q}_1^T)$ 是观察序列 $\boldsymbol{o}_1^T={\boldsymbol{o}_1,...,\boldsymbol{o}_T}$ 和状态序列 $\boldsymbol{q}_1^T$ 的联合概率，我们有

\[\begin{aligned} P(\boldsymbol{o}_1^T|\boldsymbol{q}_1^T)&= \prod_{t=1}^Tb_i(\boldsymbol{o}_t) \\ &= \prod^T_{t=1}\sum^M_{m=1} \frac{c_{i,m}}{(2\pi)^{D/2}|\Sigma_{i,m}|^{1/2}}\exp [-\frac12(\boldsymbol{o}_t-\boldsymbol{\mu}_{i,m})^T\Sigma_{i,m}^{-1}(\boldsymbol{o}_t-\boldsymbol{\mu}_{i,m})] \end{aligned}\]

另一方面，状态序列 $\boldsymbol{q}_1^T$ 的概率为转移概率的乘积

\[P(\boldsymbol{q}_1^T)=\pi_{q_1} \prod ^{T-1}_{t=1}a_{q_tq_{t+1}}\]

因此，联合概率分布为

\[P(\boldsymbol{o}_1^T,\boldsymbol{q}_1^T)=P(\boldsymbol{o}_1^T|\boldsymbol{q}_1^T)P(\boldsymbol{q}_1^T)\]

理论上我们可以通过累加所有可能的状态序列的联合概率，来计算总体的似然度 $P(\boldsymbol{o}_1^T)$。但因为长度 $T$ 的观察序列有 $N^T$ 种可能性（$N$ 为状态数目），这个计算复杂度直接到了 $O(N^T)$，算不出来的。下面介绍一种前向算法，可以做到 $O(T)$ 的时间复杂度。

我们先定义每个状态的前向概率（$t$ 时刻以及之前的观测为$\boldsymbol{o}_1^t=[\boldsymbol{o}_1,...,\boldsymbol{o}_t]$，$t$ 时刻的状态为$i$ 的概率）为

\[\alpha_t(i)=P(q_t=i,\boldsymbol{o}_1^t)\]

后向概率（在 $t$ 时刻状态为 $i$ 的情况下，余下的观测序列为 $\boldsymbol{o}_{t+1}^T=[\boldsymbol{o}_{t+1},...,\boldsymbol{o}_T]$ 的概率）

\[\beta_t(i)=P(\boldsymbol{o}_{t+1}^T|q_t=i)\]

注意这里$\boldsymbol{o}_1^t$ 指的是时刻1到 $t$ 观测序列，而$\boldsymbol{o}_t^T$ 指的是从时刻 $t$ 到 $T$ 的。简单文字说明一下上面的公式推算：上一个时刻的前/后向概率可能是从任意状态演变到当前状态的，所以需要累加所有的上一个时刻的前/后向概率乘以转移概率再乘以观测概率密度函数。

$\alpha$ 的初始值为

\[\alpha_1(i)=P(q_1=i,\boldsymbol{o}_1)=P(q_1=i)P(\boldsymbol{o}_1|q_1)=\pi_ib_i(\boldsymbol{o}_1)\]

$\beta$ 的初值则都设为1

\[\beta_T(i)=1\]

对于每个状态 $i$ 与 $t=1,2,...,T$ 计算

\[\begin{aligned} P(q_t=i,\boldsymbol{o}_1^T)&=P(q_t=i,\boldsymbol{o}_1^t,\boldsymbol{o}_{t+1}^T) \\ &=P(q_t=i,\boldsymbol{o}_1^t)P(\boldsymbol{o}_{t+1}^T|q_t=i,\boldsymbol{o}_1^t) \\ &=P(q_t=i,\boldsymbol{o}_1^t)P(\boldsymbol{o}_{t+1}^T|q_t=i) \\ &=\alpha_t(i)\beta_t(i) \end{aligned}\]

这里因为观察值在给定的状态下是独立同分布的，所以 $P(\boldsymbol{o}_{t+1}^T|q_t=i,\boldsymbol{o}_1^t)=P(\boldsymbol{o}_{t+1}^T|q_t=i)$

现在我们可以计算

\[P(\boldsymbol{o}_q^T)=\sum^N_{i=1}P(q_t=i,\boldsymbol{o}_1^T)=\sum^N_{i=1}\alpha_t(i)\beta_t(i)\]

其实我们可以取任意的 $t$ 值来计算 $P(\boldsymbol{o}_q^T)$ ，但为了方便起见我们可以直接取$T$，我们就有

\[P(\boldsymbol{o}_q^T)=\sum^N_{i=1}\alpha_T(i)\]