隐马尔科夫模型（HMM）是一种有向图模型，是结构最简单的动态贝叶斯网，是可用于标注问题的统计学习模型，描述由隐藏的马尔科夫链随机生成观测序列的过程，属于“生成式模型”。本文介绍HMM的基本概念和三个基本问题的算法推导。

1、HMM是什么

如图所示是HMM的基本结构。它有两组变量，上面是不可观测的状态变量，表示某一时刻的系统状态；下面是可以被观测到的观测变量，表示某一时刻的观测值。一般地，系统状态变量是离散的，观测变量是离散或连续的，这里仅讨论离散的情况。

HMM的基本结构

图中的箭头表示了隐马尔科夫模型的依赖关系，也是马尔科夫链的基本特点：系统下一时刻的状态仅与前一时刻的状态有关，系统当前时刻的观测值仅与当前时刻的状态有关。这是研究HMM问题的大前提。基于这种依赖关系，可以得到所有变量的联合概率分布：

$P(X,Y)=P(x_1,y_1,...,x_n,y_n)=P(y_1)P(x_1|y_1)\prod_{i=2}^n P(y_i|y_{i-1})P(x_i|y_i)\\$

设状态集合 $S=(s_1,s_2,...,s_N)$ ，所有可观测变量的集合 $X=(o_1,o_2,...,o_M)$ 。要确定一个HMM结构，需要以下关键的三组参数，也称为HMM的三要素：

① 状态转移概率：在图中表示为 $y_i$ 之间的转换概率，记为矩阵 $A=[a_{ij}]_{N×N}$ ，其中

$a_{ij}=P(y_{t+1}=s_j|y_t=s_i)\\$

② 输出观测概率：在图中表示为某一时刻纵向的推测概率，即根据当前状态得到各个观测值的概率，记为矩阵 $B=[b_{ij}]_{N×M}$ ，其中

$b_{ij}=P(x_t=o_j|y_t=s_i)\\$

③ 初始状态概率：表示初始状态即 $y_1$ 的各种取值出现的概率，记为 $\pi =(\pi_1,\pi_2,...,\pi_N)$ ，其中

$\pi_i=P(y_1=s_i)\\$

如果已知了状态空间、观测空间、三组参数，就可以确定一个HMM模型了。首先根据初始状态概率 $\pi$ 确定 $y_1$ ，再根据 $B$ 向下确定当前时刻观测值，根据 $A$ 向右确定转移状态，一直反复进行直到最后。

在HMM中，人们关心三个问题，这三个问题分别代表三种应用的角度，对应若干解决该问题的算法：

① 概率计算问题：给定模型的参数 $\lambda =(A,B,\pi)$ 和某一个观测到的序列 $O=(o_1,o_2,...,o_T)$ ，计算该观测序列出现的概率 $P(O|\lambda )$ 。涉及到前向算法和后向算法。

② 学习问题：给定观测序列 $O=(o_1,o_2,...,o_T)$ ，估计模型参数 $\lambda =(A,B,\pi)$ ，使得产生该观测序列的概率 $P(O|\lambda )$ 最大。涉及到监督学习算法和EM算法。

③ 预测问题（解码问题）：给定模型参数 $\lambda =(A,B,\pi)$ 和观测序列 $O=(o_1,o_2,...,o_T)$ ，求最匹配的状态序列 $I=(i_1,i_2,...,i_T)$ ，即最大化 $P(I|O)$ 。涉及到近似算法和维特比算法。

二、概率计算问题

2.1 前向算法

定义前向概率：给定HMM模型的参数 $\lambda$ ，定义从开始到时刻 $t$ 的观测序列为 $o_1,o_2,...,o_t$ ，并且此时状态为 $q_i$ 的概率为前向概率，记为：

$\alpha _i(i)=P(o_1,o_2,...,o_t,i_t=q_i|\lambda)\\$

计算方法如下：

① 计算初值：

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

② 递推公式：

$\alpha _{t+1}(i)=[\sum_{j=1}^N \alpha _t(j)a_{ji}]*b_i(o_{t+1}),\\其中i=1,2,...,N,t=1,2,...,T-1\\$

③ 终止：

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

解释一下，第一步初始化前向概率，实际上根据定义求的是联合概率，第二步递推公式中，中括号内计算了前一时刻所有可能的状态转移为当前时刻状态的概率和。实际上前向概率算法是计算了状态转移过程中所有的可能路径的前向概率并求和，其计算量是 $O(N^2T)$ 。

2.2 后向算法

定义后向概率：给定HMM模型的参数 $\lambda$ ，定义时刻 $t$ 状态为 $q_i$ 的条件下，从下一时刻开始到最后时刻的观测序列为 $o_{t+1},o_{t+2},...,o_T$ 的概率为后向概率，记为

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

计算方法如下：

① 初始化规定：

$\beta _T(i)=1,i=1,2,...,N\\$

② 递推公式，对 $t=T-1,T-2,...,1$ 有：

$\beta _t(i)=\sum_{j=1}^N a_{ij}b_j(o_{t+1})\beta _{t+1}(j),i=1,2,...,N\\$

③ 终止：

$P(O|\lambda )=\sum_{i=1}^N \pi_ib_i(o_1)\beta _1(i)\\$

解释一下，第一步初始化所有的后向概率为1是规定，第二步与前向概率的递归思路相似，将后一时刻所有可能的状态乘以状态转换概率 $a_{ij}$ 和输出观测概率 $b_{ij}$ 并累加，第三步也是如此，记得用 $\pi _i$ 代替 $a_{ij}$ 。

三、学习问题

学习问题是给定观测序列，求参数的估计，即参数值是多少的时候该观测序列出现的概率最大。

3.1 监督学习方法

假设给定了S个长度相同的观测序列和对应的状态序列，即 $(O_1,I_1),(O_2,I_2),...,(O_S,I_S)$ ，那么利用极大似然法估计参数，也就是根据频数估计参数：

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

$\hat{\pi} _i$ 是根据不同初始状态出现的频率求得的相应概率。

这种方法需要大量的训练数据，代价较高，所以更实际的方案是非监督学习方法--EM算法。

3.2 EM算法

假设给定的数据只有S个长度相同的观测序列 $(O_1,O_2,...,O_S)$ ，对应的状态序列不可见并记为 $I$ ，那么HMM是一个含有隐变量的概率模型：

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

它的参数学习由EM算法实现。EM算法的推导过程很复杂，涉及到很多数学知识，这里直接用EM算法的模板来推导。步骤如下：

① 确定完全数据的对数似然函数。完全数据就是把观测数据和状态变量拼接（concat）起来，其似然函数表示为 $logP(O,I|\lambda )$ 。

② EM算法的E步。首先写出Q函数，已知Q函数的定义

$Q(\lambda ,\bar{\lambda } )=E_I[logP(O,I|\lambda )|O,\bar{\lambda } ]\\$

写出此问题的Q函数：

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

其中， $\bar{\lambda }$ 是当前的参数估计值， $\lambda$ 是要极大化的参数。观察到对数函数的第一项是可以拆分细化的，先把它拆开：

$Q(\lambda ,\bar{\lambda } )=\sum_{I}log\pi _{i_1}P(O,I| \bar{\lambda } )+\sum_{I}(\sum_{t=1}^{T-1}log a_{i_ti_{t+1}} )P(O,I| \bar{\lambda } )+\sum_{I}(\sum_{t=1}^Tlog b_{i_t}(o_t) )P(O,I| \bar{\lambda } )\\$

③ EM算法的M步。Q函数由三项组成，由于三个参数分别在三个加式中，故三个参数的估计分别求出。分别找到相应的约束条件使用拉格朗日数乘法，对拉格朗日函数求偏导，解得：

$\pi_i=\frac{P(O,i_1=i|\bar{\lambda }) }{P(O|\bar{\lambda })} \\a_{ij}=\frac{\sum_{t=1}^{T-1} P(O,i_t=i,i_{t+1}=j|\bar{\lambda })}{\sum_{t=1}^{T-1} P(O,i_t=i,|\bar{\lambda })} \\b_j(k)=\frac{\sum_{t=1}^T P(O,i_t=j|\bar{\lambda }) I (o_t=v_k)}{\sum_{t=1}^T P(O,i_t=j|\bar{\lambda })}$