隐马尔可夫模型（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)$
$A$ 是状态转移概率矩阵：
$A=[a_{ij}]_{N\times N}$
其中
$a_{ij}=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=[b_j(k)]_{N\times M}$
其中
$b_j(k)=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$ 是初始状态概率向量：
$\pi=(\pi_i)$
其中
$\pi_i=P(i_1=q_i),\ \ i=1,2,\cdots,N$
是时刻 $t=1$ 处于状态 $q_i$ 的概率。

隐马尔可夫模型由初始状态概率向量 $\pi$ ，状态转移概率矩阵 $A$ 和观测概率矩阵 $B$ 决定。 $\pi$ 和 $A$ 决定状态序列， $B$ 决定观测序列。因此隐马尔可夫模型 $\lambda$ 可以用三元符号表示，即
$\lambda=(A,B,\pi)$
从定义可知，隐马尔可夫模型做了两个基本假设：

（1）齐次马尔可夫性假设，即假设隐藏的马尔可夫链在任意时刻 $t$ 的状态只依赖于其前一时刻的状态，与其他时刻的状态及观测无关，也与时刻 $t$ 无关。（当前状态只依赖上个状态，而与再前面的状态无关）
$P(i_t|i_1,o_1,\cdots,i_{t-1},o_{t-1})=P(i_t|i_{t-1}),\ \ t=1,2,\cdots,T$
（2）观测独立性假设，即假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态，与其他观测及状态无关。（每个时刻的观测只依赖于当前时刻的状态）
$P(o_t|i_1,o_1,\cdots,i_{t-1},o_{t-1},i_t,i_{t+1},i_{t+1},\cdots,i_T,o_T)=P(o_t|i_t)$

观测序列的生成过程

根据隐马尔可夫模型定义，可以将一个长度为 $T$ 的观测序列 $O=(o_1,o_2,\cdots,o_T)$ 的生成过程描述如下：

输入：隐马尔可夫模型 $\lambda=(A,B,\pi)$ ，观测序列长度 $T$ ；

输出：观测序列 $O=(o_1,o_2,\cdots,o_T)$ 。

（1）按照初始状态分布 $\pi$ 产生状态 $i_1$

（2）令 $t=1$

（3）按照状态 $i_t$ 的观测概率分布 $b_{i_t}(k)$ 生成 $o_t$

（4）按照状态 $i_t$ 的状态转移概率分布 $\{a_{i_ti_{t+1}}\}$ 产生状态 $i_{t+1}$ ， $i_{t+1}=1,2,\cdots,N$

（5）令 $t=t+1$ ；如果 $t\lt T$ ，转步(3)；否则终止。

隐马尔可夫模型的3个基本问题

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

（2）学习问题。已知观测序列 $O=(o_1,o_2,\cdots,o_T)$ ，估计模型 $\lambda=(A,B,\pi)$ 参数，使得在该模型下观测序列概率 $P(O|\lambda)$ 最大。即用极大似然估计的方法估计参数。

（3）预测问题，也称为解码问题。已知模型 $\lambda=(A,B,\pi)$ 和观测序列 $O=(o_1,o_2,\cdots,o_T)$ ，求对给定观测序列条件概率 $P(I|O)$ 最大的状态序列 $I=(i_1,i_2,\cdots,i_T)$ 。即给定观测序列，求最有可能的对应状态序列。

下面针对这三个问题给出解决问题的算法。

概率计算算法

解决的是第一个问题：概率计算问题。给定模型 $\lambda=(A,B,\pi)$ 和观测序列 $O=(o_1,o_2,\cdots,o_T)$ ，计算在模型 $\lambda$ 下观测序列 $O$ 出现的概率 $P(O|\lambda)$ 。通常的计算方法有直接计算法、前向-后向算法。

直接计算法

这个算法通过列举所有可能的长度为 $T$ 的状态序列 $I=(i_1,i_2,\cdots,i_T)$ ，求各个状态序列 $I$ 与观测序列 $O=(o_1,o_2,\cdots,o_T)$ 的联合概率 $P(O,I|\lambda)$ ，然后对所有可能的状态序列求和，得到 $P(O|\lambda)$ 。这个算法理论上可行，但是实际上计算量太大，所以一般不用。

状态序列 $I=(i_1,i_2,\cdots,i_T)$ 的概率
$P(I|\lambda)=\pi_{i_1}a_{i_1i_2}a_{i_2i_3}\cdots a_{i_{T-1}i_T}$
对于固定的状态序列 $I=(i_1,i_2,\cdots,i_T)$ ，观测序列 $O=(o_1,o_2,\cdots,o_T)$ 的概率是 $P(O|I,\lambda)$
$P(O|I,\lambda)=b_{i_1}(o_1)b_{i_2}(o_2)\cdots b_{i_T}(o_T)$
$O$ 和 $I$ 同时出现的联合概率为
$P(O,I|\lambda)=P(O|I,\lambda)P(I|\lambda)=\pi_{i_1}b_{i_1}(o_1)a_{i_1i_2}b_{i_2}(o_2)\cdots a_{i_{T-1}i_T}b_{i_T}(o_T)$
然后对所有可能的状态序列 $I$ 求和，得到观测序列 $O$ 的概率 $P(O|\lambda)$ ，即
$P(O|\lambda)=\sum_IP(O,I|\lambda)$
计算复杂度是 $O(TN^T)$ 阶的。

前向算法

首先定义前向概率。

前向概率

给定隐马尔可夫模型参数 $\lambda$ ，定义到 $t$ 时刻部分观测序列为 $o_1,o_2,\cdots,o_t$ 且时刻 $t$ 状态 $i_t$ 为 $q_i$ 的概率为前向概率，记做
$\alpha_t(i)=P(o_1,o_2,\cdots,o_t,i_t=q_i|\lambda)$
根据可以从 $t=0$ 递推得到各个时刻 $t$ 前向概率 $\alpha_t(i)$ ，最后得到 $P(O|\lambda)=\sum_{i=1}^N\alpha_T(i)$ 。

观测序列概率的前向算法

输入：隐马尔科夫模型参数 $\lambda$ ，观测序列 $O$ ；

输出：观测序列概率 $P(O|\lambda)$

（1）初值
$\alpha_1(i)=P(o_1,i_1=q_i)=\pi_ib_i(o_1),\ \ i=1,2,\cdots,N$
（2）递推，对 $t=1,2,\cdots,T-1$ ，
$\alpha_{t+1}(i)=\bigg[\sum_{j=1}^N\alpha_t(j)a_{ji}\bigg]b_i(o_{t+1}),\ \ i=1,2,\cdots,N\tag1$
（3）终止
$P(O|\lambda)=\sum_{i=1}^N\alpha_T(i)\tag2$
算法结束。

在步骤(2)中
$\begin{align} \alpha_{t+1}(i)=P(o_1,o_2,\cdots,o_{t+1},i_{t+1}=q_i|\lambda)&=P(o_1,o_2,\cdots,o_t,i_{t+1}=q_i|\lambda)P(o_{t+1}|i_{t+1}=q_i,\lambda)\\ &=P(v_{t+1}=o_{t+1}|i_{t+1}=q_i)\sum_{j=1}^N\bigg[P(o_1,o_2,\cdots,o_t,i_t=q_j|\lambda)P(i_{t+1}=q_i|i_t=q_j)\bigg]\\ &=b_i(o_{t+1})\bigg[\sum_{j=1}^N\alpha_t(j)a_{ji}\bigg] \end{align}$
其中 $N$ 是状态的状态总数。中括号内对当前状态 $q_i$ 的所有上个状态 $q_j$ 进行了全部的列举，并乘上了状态转移概率，所以计算的是概率 $P(o_1,o_2,\cdots,o_t,i_{t+1}=q_i|\lambda)$ 。最后对联合概率 $\alpha_T(i)=P(o_1,o_2,\cdots,o_T,i_T=q_i|\lambda)$ 求边缘概率，列举状态 $N$ 个所有可能取值，得到 $P(O|\lambda)$ 。由于是通过递归计算的，每一步都用到了上一步的结果，所以大大减少了计算量。

后向算法

后向算法与前向算法相反，是从序列最后向前递归的，首先定义后向概率。

后向概率

给定隐马尔可夫模型参数 $\lambda$ ，定义在时刻 $t$ 状态 $i_t$ 为 $q_i$ 的条件下，从 $t+1$ 到 $T$ 的部分观测序列为 $o_{t+1},o_{t+2},\cdots,o_T$ 的概率为后向概率，记做
$\beta_t(i)=P(o_{t+1},o_{t+2},\cdots,o_T|i_t=q_i,\lambda)$
同样可以用递推的方法求得每个时刻 $t$ 的后向概率 $\beta_t(i)$ 及观测序列概率 $P(O|\lambda)$ 。

观测序列概率的后向算法

输入：隐马尔科夫模型参数 $\lambda$ ，观测序列 $O$ ；

输出：观测序列概率 $P(O|\lambda)$

（1）
$\beta_T(i)=1,\ \ i=1,2,\cdots,N$
（2）对 $t=T-1,T-2,\cdots,1$
$\beta_t(i)=\sum_{j=1}^Na_{ij}b_j(o_{t+1})\beta_{t+1}(j),\ \ i=1,2,\cdots,N\tag3$
（3）
$P(O|\lambda)=\sum_{i=1}^N\pi_ib_i(o_1)\beta_1(i)\tag4$
算法结束。

步骤(1)中概率 $\beta_T(i)=1$ 是直接定义的。

对于步骤(2)

因为
$b_j(o_t)\beta_t(j)=P(v_t=o_t|i_t=q_j)P(o_{t+1},o_{t+2},\cdots,o_T|i_t=q_j,\lambda)=P(o_t,o_{t+1},\cdots,o_T|i_t=q_j,\lambda)$
所以
$\begin{align} \alpha_{ij}b_j(o_t)\beta_t(j)&=P(i_t=q_j|i_{t-1}=q_i)P(o_t,o_{t+1},\cdots,o_T|i_t=q_j,\lambda)\\ &=P(i_t=q_j,o_t,o_{t+1},\cdots,o_T|i_{t-1}=q_i,\lambda) \end{align}$
列举时刻 $t$ 所有的状态 $q_j$
$\sum_{j=1}^N\alpha_{ij}b_j(o_t)\beta_t(j)=\sum_{j=1}^NP(i_t=q_j,o_t,o_{t+1},\cdots,o_T|i_{t-1}=q_i,\lambda)=P(o_t,o_{t+1},\cdots,o_T|i_{t-1}=q_i,\lambda)=\beta_{t-1}(i)$
令 $t=t+1$ ，即可得到步骤(2)中的递推公式(3)。

由前向概率的定义 $\alpha_{t}(i)=P(o_1,o_2,\cdots,o_{t},i_{t}=q_i|\lambda)$ 和后向概率的定义 $\beta_{t+1}(j)=P(o_{t+2},o_{t+3},\cdots,o_T|i_{t+1}=q_j,\lambda)$ ，可以得到观测概率 $P(O|\lambda)$ 的公式
$\begin{align} P(O|\lambda)&=\sum_{i=1}^N\sum_{j=1}^NP(o_1,o_2,\cdots,o_{t},i_{t}=q_i|\lambda)P(i_{t+1}=q_j|i_t=q_i)P(v_{t+1}=o_{t+1}|i_{t+1}=q_j)P(o_{t+2},o_{t+3},\cdots,o_T|i_{t+1}=q_j,\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 \end{align}$
当 $t=1$ 和 $t=T-1$ 时，分别为公式(4)和公式(2)。

一些概率和期望值的计算（用于预测问题）

1.给定模型 $\lambda$ 和观测 $O$ ，在时刻 $t$ 处于状态 $q_i$ 的概率，记
$\gamma_t(i)=P(i_t=q_i|O,\lambda)=\frac{\alpha_t(i)\beta_t(i)}{\sum_{j=1}^N\alpha_t(j)\beta_t(j)}\tag5$
推导：
$\gamma_t(i)=P(i_t=q_i|O,\lambda)=\frac{P(i_t=q_i,O|\lambda)}{P(O|\lambda)}=\frac{P(o_1,o_2,\cdots,o_t,i_t=q_i|\lambda)P(o_{t+1},o_{t+2},\cdots,o_T|i_t=q_i,\lambda)}{\sum_{j=1}^NP(i_t=q_i,O|\lambda)}=\frac{\alpha_t(i)\beta_t(i)}{\sum_{j=1}^N\alpha_t(j)\beta_t(j)}$
2.给定模型 $\lambda$ 和观测 $O$ ，在时刻 $t$ 处于状态 $q_t$ 且在时刻 $t+1$ 处于状态 $q_j$ 的概率，记
$\xi_t(i,j)=P(i_t=q_i,i_{t+1}=q_j|O,\lambda)=\frac{\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)}{\sum_{i=1}^N\sum_{j=1}^N\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)}\tag6$
推导略。

3.其他一些期望：

（1）在观测 $O$ 下状态 $i$ 出现的期望值
$\sum_{t=1}^T\gamma_t(i)$
（2）在观测 $O$ 下由状态 $i$ 转移的期望值
$\sum_{t=1}^{T-1}\gamma_t(i)$
（2）在观测 $O$ 下由状态 $i$ 转移到状态 $j$ 的期望值
$\sum_{t=1}^{T-1}\xi_t(i,j)$

学习算法

解决的是第二个问题：学习问题。已知观测序列 $O=(o_1,o_2,\cdots,o_T)$ ，估计模型 $\lambda=(A,B,\pi)$ 参数，使得在该模型下观测序列概率 $P(O|\lambda)$ 最大。即用极大似然估计的方法估计参数。

如果知道状态序列 $I=(i_1,i_2,\cdots,i_T)$ ，那么只需要通过监督学习的方法，就可以得到模型的参数，方法略。但是情况通常是不知道状态序列，这时候就需要通过无监督学习的方式，估计模型参数。无监督学习的算法叫做Baum-Welch算法。

Baum-Welch算法

隐马尔可夫模型是含有隐变量的模型，可以通过EM算法进行参数估计，EM算法在隐马尔可夫模型中的具体应用就是Baum-Welch算法。

（1）确定完全数据的对数似然函数

所有观测数据写成 $O=(o_1,o_2,\cdots,o_T)$ ，所有隐数据写成 $I=(i_1,i_2,\cdots,i_T)$ ，完全数据是 $(O,I)=(o_1,o_2,\cdots,o_T,i_1,i_2,\cdots,i_T)$ 。完全数据的对数似然函数是 $\log P(O,I|\lambda)$ 。

（2）EM算法的E步：求 $Q$ 函数 $Q(\lambda,\bar\lambda)$
$Q(\lambda,\bar\lambda)=\sum_I\log P(O,I|\lambda)P(O,I|\bar\lambda)$
其中， $\bar\lambda$ 是隐马尔可夫模型参数的当前估计值， $\lambda$ 是要极大化的隐马尔可夫模型参数。
$P(O,I|\lambda)=\pi_{i_1}b_{i_1}(o_1)a_{i_1i_2}b_{i_2}(o_2)\cdots a_{i_{T-1}i_T}b_{i_T}(o_T)$
所以，
$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}^T\log b_{i_t}(o_t))P(O,I|\bar\lambda)\tag7$
3.EM算法的M步：极大化 $Q$ 函数 $Q(\lambda,\bar\lambda)$ 求模型参数 $A,B,\pi$

极大化 $Q(\lambda,\bar\lambda)$ 可以通过对公式(7)的三部分分别极大化实现，具体为对参数求偏导等于0，过程略。得到参数的更新公式：
$\pi_i=\gamma_1(i)$

$a_{ij}=\frac{\sum_{t=1}^{T-1}\xi_t(i,j)}{\sum_{t=1}^{T-1}\gamma_t(i)}$

$b_j(k)=\frac{\sum_{t=1,o_t=v_k}^T\gamma_t(j)}{\sum_{t=1}^T\gamma_t(j)}$

$b_j(k)$ 分子中是对观测到 $v_k$ 的时刻 $t$ 求和 $\gamma_t(j)$ 。

Baum-Welch算法的描述

输入：观测数据 $O=(o_1,o_2,\cdots,o_T)$ ；

输出：隐马尔可夫模型参数

（1）初始化

对 $n=0$ ，选取 $a_{ij}^{(0)}$ ， $b_j(k)^{(0)}$ ， $\pi_i^{(0)}$ ，得到模型 $\lambda^{(0)}=(A^{(0)},B^{(0)},\pi^{(0)})$ 。

（2）递推，对 $n=1,2,\cdots,$
$a_{ij}^{(n+1)}=\frac{\sum_{t=1}^{T-1}\xi_t(i,j)}{\sum_{t=1}^{T-1}\gamma_t(i)}$

$b_j(k)^{(n+1)}=\frac{\sum_{t=1,o_t=v_k}^T\gamma_t(j)}{\sum_{t=1}^T\gamma_t(j)}$

$\pi_i^{(n+1)}=\gamma_1(i)$

右端各值按观测 $O=(o_1,o_2,\cdots,o_T)$ 和模型 $\lambda^{(n)}=(A^{(n)},B^{(n)},\pi^{(n)})$ 计算。式中
$\gamma_t(i)=P(i_t=q_i|O,\lambda)=\frac{\alpha_t(i)\beta_t(i)}{\sum_{j=1}^N\alpha_t(j)\beta_t(j)}$

$\xi_t(i,j)=P(i_t=q_i,i_{t+1}=q_j|O,\lambda)=\frac{\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)}{\sum_{i=1}^N\sum_{j=1}^N\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)}$

（3）终止。得到模型参数 $\lambda^{(n+1)}=(A^{(n+1)},B^{(n+1)},\pi^{(n+1)})$

预测算法

解决的是第二个问题：预测问题，也称为解码问题。已知模型 $\lambda=(A,B,\pi)$ 和观测序列 $O=(o_1,o_2,\cdots,o_T)$ ，求对给定观测序列条件概率 $P(I|O)$ 最大的状态序列 $I=(i_1,i_2,\cdots,i_T)$ 。即给定观测序列，求最有可能的对应状态序列。

近似算法

每个时刻 $t$ 取最有可能的状态。根据前面定义， $\gamma_t(i)$ 为给定模型 $\lambda$ 和观测 $O$ ，在时刻 $t$ 处于状态 $q_i$ 的概率 $P(i_t=q_i|O,\lambda)$ ：
$\gamma_t(i)=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^*$ 为
$i_t^*=\arg\max_{1\leq i\leq N}[\gamma_t(i)],\ \ t=1,2,\cdots,T$
该算法的缺点是没有考虑整个序列，如果存在转移概率 $a_{ij}=0$ ，序列 $q_j,q_i$ 是不可能出现的，但是依然会存在这样的预测。尽管如此，近似算法仍然是有用的。

维特比算法

维特比算法通过动态规划解隐马尔可夫模型预测问题。

首先导入两个变量 $\delta$ 和 $\psi$ 。定义在时刻 $t$ 状态为 $i$ 的所有单个路径 $(i_1,i_2,\cdots,i_t)$ 中概率最大值
$\delta_t(i)=\max_{i_1,i_2,\cdots i_{t-1}}P(i_1,o_1,\cdots,i_{t-1},o_{t-1},i_t=i,o_t|\lambda),\ \ i=1,2,\cdots N$
由定义可得变量 $\delta$ 的递推公式
$\begin{align} \delta_{t+1}(i)&=\max_{i_1,i_2,\cdots i_t}P(i_1,o_1,\cdots,i_t,o_t,i_{t+1}=i,o_{t+1}|\lambda)\\ &=\max_{1\leq j\leq N}[\delta_t(j)a_{ji}]b_i(o_{t+1}),\ \ i=1,2,\cdots,N;\ \ t=1,2,\cdots,T-1\tag8 \end{align}$
定义在时刻 $t$ 状态为 $i$ 的所有单个路径 $(i_1,i_2,\cdots,i_{t-1},i)$ 中概率最大的路径的第 $t-1$ 个结点为
$\psi_t(i)=\arg\max_{1\leq j\leq N}[\delta_{t-1}(j)a_{ji}],\ \ i=1,2,\cdots,N\tag9$
维特比算法的思路就是通过 $\delta_t(i)$ 从时刻 $t=1$ 递推到时刻 $t=T$ ，得到概率最大状态序列的概率，同时在每个时刻 $t$ 通过 $\psi_t(i)$ 记录路径。在 $T$ 时刻，得到概率最大的 $\delta_T(i^*)$ 之后，通过 $\psi_{T-1}(i^*)$ 得到概率最大路径的第 $T-1$ 个结点，往前推到时刻 $t=1$ ，最终得到完整状态序列。