1、隐马尔可夫模型基本概念

隐马尔可夫模型是关于时序的概率模型，描述由一个隐藏的马尔科夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测从而产生观测随机序列的过程。

隐马尔可夫模型的形式定义如下：

设 $Q$ 是所有可能状态的集合， $V$ 是所有可能观测的集合：

$Q=\{q_1,q_2,\dots,q_N\}\quad V=\{v_1,v_2,\dots,v_M\}$

其中 $N$ 为可能状态数， $M$ 为可能观测数。

$I$ 是长度为 $T$ 的状态序列， $O$ 是对应的观测序列：

$I=(i_1,i_2,\dots,i_T)\quad O=(o_1,o_2,\dots,o_T)$

$A$ 是状态转移概率矩阵：

$A=[a_{ij}]_{N\times N}$

其中：

$a_{ij}=P(i_{t+1}=q_j|i_t=q_i)$

$B$ 是观测概率矩阵：

$B=[b_j(k)]_{N\times M}$

其中：

$b_j(k)=P(o_t=v_k|i_t=q_j)$

$\pi$ 是初始状态概率向量：

$\pi=(\pi_i)$

其中：

$\pi_i=P(i_1=q_i)$

隐马尔可夫模型由初始状态概率向量 $\pi$ 、状态转移概率矩阵 $A$ 和观测概率矩阵 $B$ 决定。因此隐马尔可夫模型 $\lambda$ 可表示为：

$\lambda=(A,B,\pi)$

具体来说，长度为 $T$ 的观测序列的生成过程如下：按照初始状态分布 $\pi$ 产生状态 $i_1$ ，按状态 $i_t$ 的观测概率分布 $b_{i_t}(k)$ 生成 $o_t$ ，按状态 $i_t$ 的状态转移概率分布 $\{a_{i_t i_{t+1}} \}$ 产生状态 $i_{t+1}$ ，依次递推。

由定义可知隐马尔可夫模型的两个基本假设：

（1）齐次马尔可夫性假设，即隐藏的马尔科夫链在任意时刻 $t$ 的状态只依赖于其前一时刻的状态，与其他时刻状态及观测无关，也与时刻 $t$ 无关。

（2）观测独立性假设，即任意时刻的观测只依赖于该时刻的马尔科夫链状态，与其它观测状态无关。

隐马尔可夫模型的三个基本问题如下：

（1）概率计算问题：给定模型 $\lambda=(A,B,\pi)$ 和观测序列 $O=(o_1,o_2,\dots,o_T)$ ，计算在模型 $\lambda$ 下序列 $O$ 出现的概率 $P(O|\lambda)$ 。

（2）学习问题：已知观测序列 $O=(o_1,o_2,\dots,o_T)$ ，估计模型 $\lambda=(A,B,\pi)$ 参数，使得在该模型下观测序列 $P(O|\lambda)$ 最大。

（3）预测问题：已知模型 $\lambda=(A,B,\pi)$ 和观测序列 $O=(o_1,o_2,\dots,o_T)$ ，求使得 $P(I|O)$ 最大的状态序列 $I=(i_1,i_2,\dots,i_T)$ 。

接下来分别阐述这三个问题的解决方法。

2、概率计算算法

2.1、直接计算法

状态 $I=(i_1,i_2,\dots,i_T)$ 的概率是：

$P(I|\lambda)=\pi_{i_1}a_{i_1 i_2}\dots,a_{i_{T-1}i_T}$

对固定的 $I=(i_1,i_2,\dots,i_T)$ 观测序列 $O=(o_1,o_2,\dots,o_T)$ 的概率是：

$P(O|I,\lambda)=b_{i_1}(o_1)b_{i_2}(o_2)\dots,b_{i_T}(o_T)$

$O,I$ 同时出现的联合概率为：

$P(O,I|\lambda)=P(O|I,\lambda)P(I|\lambda)$

从而：

$P(O|\lambda)=\sum_{I}P(O,I|\lambda)=\sum_{I}P(O|I,\lambda)P(I|\lambda)$

可以看到，上式是对所有可能的 $I$ 序列求和，而长度为 $T$ 的 $I$ 序列的数量是 $O(N^T)$ 数量级的，而 $P(O,I|\lambda)$ 的计算量是 $O(T)$ 级别的，因此计算量为 $O(TN^T)$ ，非常大，这种算法在实际中不可行。

2.2、前向算法

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

$\alpha_t(i)=P(o_1,o_2,\dots,o_t,i_t=q_i|\lambda)$

观测序列概率的前向算法如下：

（1）初值：

$\alpha_1(i)=\pi_i b_i(o_1),\quad i=1,2,\dots,N$

（2）递推，对 $t=1,2,\dots,T-1$ ：

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

（3）终止：

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

前向算法高效的关键是局部计算前向概率，然后利用路径结构将前向概率递推到全局，得到 $P(O|\lambda)$ 。前向概率算法计算量是 $O(TN^2)$ 级别的。

2.3、后向算法

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

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

观测序列概率的后向算法如下：

（1）初值：

$\beta_T(i)=1,\quad i=1,2,\dots,N$

（2）递推，对 $t=T-1,T-2,\dots,1$ ：

$\beta_t(i)=\sum_{j=1}^N a_{ij}b_j (o_{t+1})\beta_{t+1}(j)$

（3）终止：

$P(O|\lambda)=\sum_{i=1}^N \pi_i b_i(o_1)\beta_1(i)$

3、学习算法

3.1、监督学习方法

若有 $S$ 个长度相同观测序列和对应状态序列 $\{(O_1,I_1),(O_2,I_2),\dots,(O_S,I_S) \}$ 则可利用极大似然估计得到隐马尔可夫模型参数：

设样本中时刻 $t$ 处于状态 $i$ 时刻 $t+1$ 转移到状态 $j$ 的频数为 $A_{ij}$ ，那么状态转移概率 $a_{ij}$ 的估计为：

$\hat{a}_{ij}=\frac{A_{ij}}{\sum_{j=1}^N A_{ij}}$

设样本中状态为 $j$ 观测为 $k$ 的频数为 $B_{jk}$ ，那么观测概率 $b_j(k)$ 的估计为：

$\hat{b}_j(k)=\frac{B_{jk}}{\sum_{k=1}^M B_{jk}}$

初始状态 $\pi_i$ 的估计 $\hat{\pi}_i$ 为 $S$ 个样本中初始状态为 $q_i$ 的频率。

3.2、无监督学习方法（Baum-Welch算法）

假设给定训练数据只包含 $S$ 个长度为 $T$ 的观测序列 $\{O_1,O_2,\dots,O_S \}$ 而没有对应状态序列，我们可以把状态数据看作不可观测的隐数据 $I$ ，则隐马尔可夫模型事实上是一个含有隐变量的概率模型：

$P(O|\lambda)=\sum_I P(O|I,\lambda)P(I|\lambda)$

其参数可由EM算法实现。

4、预测算法

4.1、近似算法

近似算法的思想是，在每个时刻 $t$ 选择在该时刻最有可能出现的状态 $i_t^*$ ，从而得到一个状态序列 $I^*=(i_1^*,i_2^*,\dots,i_T^*)$ 。

近似算法的优点是计算简单，缺点是不能保证预测的状态序列整体是最有可能的状态序列，因为预测的状态序列可能有实际不发生的部分，比如存在转移概率为0的相邻状态。尽管如此，近似算法还是有用的。

4.2、维特比算法

维特比算法实际上是用动态规划解隐马尔可夫模型预测问题，即用动态规划求概率最大路径（最优路径），此路径对应一个状态序列。

定义在时刻 $t$ 状态为 $i$ 的所有单个路径 $(i_1,i_2,\dots,i_t)$ 中概率最大值为：

$\delta_t(i)=\max_{i_1,i_2,\dots,i_{t-1}}P(i_t=i,i_{t-1},\dots,i_1,o_t,o_{t-1},\dots,o_1|\lambda),\quad i=1,2,\dots,N$

由定义得递推式：

$\begin{aligned} \delta_{t+1}(i)&=\max_{i_1,i_2,\dots,i_{t-1}}P(i_{t+1}=i,i_{t-1},\dots,i_1,o_t,o_{t-1},\dots,o_1|\lambda)\\ &=\max_{1\leq j\leq N}[\delta_t(j)a_{ji}]b_i(o_{t+1}) \end{aligned}$