隐马尔可夫模型(HMM)及其三个基本问题

隐马尔可夫模型的定义[1]

隐马尔可夫模型(Hidden Markov Model,HMM)是关于时序的概率模型,描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列,再由各个状态生成一个观测而产生观测随机序列的过程。隐藏的马尔可夫链随机生成的状态的序列,称为状态序列;每个状态生成一个观测,而由此产生的观测的随机序列,称为观测序列,序列的每一个位置又可以看作是一个时刻。其形式定义如下:


$Q$是所有可能的状态的集合,$V$是所有可能的观测的集合:

其中,$N$是可能的状态数,$M$是可能的观测数。
$I$是长度为$T$的状态序列,$O$是对应的观测序列:

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

其中,$a_{ij}=P(i_{t+1}=q_j\vert i_t=q_i),\quad i=1,2,…,N;j=1,2,…,N$,表示在时刻$t$处于状态$q_i$的条件下在时刻$t+1$转移到状态$q_j$的概率。
$B$是观测概率矩阵

其中,$b_{jk}=P(o_t=v_k\vert i_t=q_j),\quad j=1,2,…N;k=1,2,…,M$,表示在时刻$t$处于状态$q_j$的条件下生成观测$v_k$的概率。
$\pi$是初始状态概率向量

其中,$\pi_i=P(i_1=q_i),\quad i=1,2,…,N$,表示时刻$t=1$时处于状态$q_i$的概率。
隐马尔可夫模型由初始状态概率向量$\pi$、状态转移概率矩阵$A$和观测概率矩阵$B$决定。$\pi$和$A$决定状态序列,$B$决定观测序列。因此,隐马尔可夫模型$\lambda$可以用三元符号表示,即:

$A,B,\pi$称为隐马尔可夫模型的三要素
从定义可知,隐马尔可夫模型作了两个基本假设

  1. 齐次马尔可夫性假设,即假设隐藏的马尔可夫链在任意时刻$t$的状态只依赖于其前一时刻的状态,与其他时刻的状态及观测无关,也与时刻$t$无关:
  2. 观测独立性假设,即假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态,与其他观测及状态无关:

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

  1. 概率计算问题:给定模型$\lambda=(A,B,\pi)$和观测序列$O=(o_1,o_2,…,o_T)$,计算在模型$\lambda$下观测序列$O$出现的概率$P(O\vert \lambda)$;
  2. 学习问题:已知观测序列$O=(o_1,o_2,…,o_T)$,估计模型$\lambda=(A,B,\pi)$参数,使得在该模型下观测序列概率$P(O\vert \lambda)$最大,即用极大似然估计的方法估计参数;
  3. 预测问题:也称为解码问题,已知模型$\lambda=(A,B,\pi)$和观测序列$O=(o_1,o_2,…,o_T)$,求对给定观测序列条件概率$P(I\vert O)$最大的状态序列$I=(i_1,i_2,…,i_T)$,即给定观测序列,求最有可能的对应状态序列。

概率计算问题

直接计算法

对于求$P(O\vert \lambda)$最直接的方法就是按照概率公式直接计算,即:

其中,$P(I\vert \lambda)$表示给定模型参数时,产生状态序列$I=(i_1,i_2,…,i_T)$的概率:

$P(O\vert I,\lambda)$表示给定模型参数且状态序列为$I=(i_1,i_2,…,i_T)$时,产生观测序列$O=(o_1,o_2,…,o_T)$的概率:

所以

其中,$\sum_{i_1,i_2,…,i_T}$共有$N^T$种可能,计算$\pi_{i_1}b_{i_1o_1}a_{i_1i_2}b_{i_2o_2}\cdots a_{i_{T-1}i_T}b_{i_To_T}$的时间复杂度为$O(T)$,所以上式整体的时间复杂度为$O(TN^T)$,显然这种算法是不可行的。

前向算法

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


根据前向概率的定义可推得:

于是求解$P(O\vert \lambda)$的问题被转化为了求解前向概率$\alpha_T(i)$的问题。由前向概率的定义可知:

依次此类推可得如下递推公式:

因此可以递推求得:

后向算法

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


由后向概率的定义可知:

依次类推可得递推公式:

根据递推公式可求得$\beta_1(i)$,又

所以也可求得$P(O\vert \lambda)$。

综上可以看出前向算法和后向算法都是先计算局部概率,然后递推到全局,每一时刻的概率计算都会用上前一时刻计算出的结果,整体的时间复杂度大约为$O(TN^2)$,明显小于直接计算法的$O(TN^T)$。

利用前向概率和后向概率,可以得到关于单个状态和两个状态概率的一些计算公式

  1. 给定模型参数$\lambda$和观测$O$,在时刻$t$处于状态$q_i$的概率,记可以通过前向概率和后向概率进行计算,推导如下:又由前向概率和后向概率的定义可知:所以
  2. 给定模型参数$\lambda$和观测$O$,在时刻$t$处于状态$q_i$且在时刻$t+1$处于状态$q_j$的概率,记可以通过前向后向概率进行计算,推导如下:所以

学习问题

监督学习方法

假设已给出训练数据包含$S$个长度相同的观测序列和对应的状态序列$\{(O_1,I_1),(O_2,I_2),…,(O_S,I_S)\}$,那么可以利用极大似然估计法来估计隐马尔可夫模型的参数,具体方法如下:

  • 转移概率$a_{ij}$的估计:其中,$A_{ij}$为样本中时刻$t$处于状态$q_i$而到时刻$t+1$转移到状态$q_j$的频数;
  • 观测概率$b_{jk}$的估计:其中,$B_{jk}$为样本中状态为$q_j$,其对应观测为$v_k$的频数;
  • 初始状态概率$\pi_i$的估计为$S$个样本中初始状态为$q_i$的频率

显然此训练数据中的状态序列数据通常是需要人工标注出来的,因此代价较高,所以非监督学习的方法更为实用,例如Baum-Welch算法。

Baum-Welch算法

如果只有观测序列数据$O=(o_1,o_2,…,o_T)$,而没有状态序列数据$I=(i_1,i_2,…,i_T)$,那么隐马尔可夫模型就是一个含有隐变量的概率模型:

如果要对它进行参数估计,则可以采用EM算法来实现,具体步骤如下:

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

此时观测数据为$O=(o_1,o_2,…,o_T)$,未观测数据为$I=(i_1,i_2,…,i_T)$,则完全数据为$(O,I)=(o_1,o_2,…,o_T,i_1,i_2,…,i_T)$,完全数据的对数似然函数为:

其中,$P(O,I\vert \lambda)=\pi_{i_1}b_{i_1o_1}a_{i_1i_2}b_{i_2o_2}\cdots a_{i_{T-1}i_T}b_{i_To_T}$,所以可以进一步推得:

2.EM算法E步:求$Q$函数$Q(\lambda,\bar{\lambda})$

其中,$\bar{\lambda}$是隐马尔可夫模型参数的当前估计值,$\lambda$是要极大化的隐马尔可夫模型参数。为了便于后续计算,$Q$函数还可以作如下恒等变形:

由于接下来仅极大化$\lambda$,所以$P(O\vert\bar{\lambda})$可以看做常数项进行略去,所以$Q$函数可以进一步化简为:

3.EM算法M步:极大化$Q$函数

由于要极大化的参数在上式中单独地出现在3个项中,所以只需对各项分别极大化。

  1. 上述$Q$函数中的第1项可以写成:由于$\pi_i$需要满足约束$\sum_{i=1}^N\pi_i=1$,利用拉格朗日乘子法,写出拉格朗日函数:对其关于$\pi_i$求偏导并令结果为0:对上式关于$i$求和可得:解得将其代回式(B.1)可得:其中,$\gamma_1(i)$由式(A.1)给出。
  2. 上述$Q$函数中的第2项可以写成:由于$a_{ij}$满足约束$\sum_{j=1}^Na_{ij}=1$,同样利用拉格朗日乘子法,写出拉格朗日函数:对其关于$a_{ij}$求偏导并令结果为0:对上式关于$j$求和可得:解得:将其代回式(B.2)可得:分子分母同时除以$P(O|\bar{\lambda})$,所以其中,$\xi_t(i,j)$由式(A.2)给出,$\gamma_t(i)$由式(A.1)给出。
  3. 上述$Q$函数中的第3项可以写成:由于$b_{jk}$满足约束$\sum_{k=1}^M b_{jk}=1$,同样利用拉格朗日乘子法,写出拉格朗日函数:对其关于$b_{jk}$求偏导并令结果为0:其中,$\mathbb{I}(o_t=v_k)$为指示函数。对上式关于$k$求和可得:解得:将其代回式(B.3)可得:分子分母同时除以$P(O|\bar{\lambda})$,所以其中,$\gamma_t(j)$由式(A.1)给出。

预测问题

近似算法

近似算法思想:在每个时刻$t$选择在该时刻最有可能出现的状态$i_t^*$,从而得到一个状态序列$I^*=(i_1^*,i_2^*,…,i_T^*)$,将它作为预测的结果。具体算法如下:

给定隐马尔可夫模型$\lambda$和观测序列$O$,在时刻$t$处于状态$q_i$的概率$\gamma_t(i)$是

在每一时刻$t$最有可能的状态$i_t^*$是

从而得到状态序列$I^*=(i_1^*,i_2^*,…,i_T^*)$。

近似算法的优点是计算简单,其缺点是不能保证预测的状态序列整体是最有可能的状态序列,因为预测的序列可能有实际不发生的部分,也即可能存在状态转移概率$a_{i^*j^*}=0$的相邻状态$i^*$和$j^*$出现。尽管如此,近似算法仍然是有用的。

维特比算法

维特比(Viterbi)算法实际是用动态规划解隐马尔可夫模型预测问题,即用动态规划求概率最大路径,这时一条路径对应着一个状态序列。具体算法如下:

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

由此定义可推得

依次此类推可得如下递推公式:

同时再定义在时刻$t$状态为$q_i$的所有单个路径$(i_1,i_2,…,i_t)$中概率最大的路径的第$t-1$个结点为

因此,取$i_T^*=\arg\max\limits_{1\leq i\leq N}[\delta_T(i)]$,则$i_{T-1}^*=\psi_T(i_T^*),i_{T-2}^*=\psi_{T-1}(i_{T-1}^*),…,i_1^*=\psi_2(i_2^*)$,具体例子参见[1]第10章例10.3。

参考文献

[1] 李航.《统计学习方法》