隐马尔可夫模型

隐马尔可夫模型(Hidden Markov Model,HMM)是可用于标注问题的统计学习模型,描述由隐藏的马尔可夫链随机生成观测序列的过程,属于生成模型。隐马尔可夫模型在语音识别、自然语言处理、生物信息、模式识别等领域有着广泛的应用。

原理

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

image

隐马尔可夫模型由初始概率分布$\Pi$、状态转移概率分布A以及观测概率分布B确定。隐马尔可夫的形式定义如下:

因此,隐马尔可夫模型$\lambda$可以用三元符号表示,即:

状态概率矩阵A与初始状态概率矩阵$\Pi$确定了隐马可夫链,生成不可观测的状态序列,观测概率矩阵B确定了如何从状态生成观测,与状态序列综合确定了如何产生观测序列。

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

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

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

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

第一个问题可用前向-后向算法(Forward-Backword Algorithm)解决,第二个问题是模型训练问题,第三个问题可用维特比算法(Viterbi Algorithm)解决。接下来,我们将对这些算法逐一进行介绍。

概率计算问题

已知:模型$\lambda=(A,B,\Pi)$和观测序列$O=(o_1,o_2,\ldots,o_T)$

求:$P(O|\lambda)$

直接计算法

通过列举所有可能的长度为T的状态序列$I=(i_1,i_2,\ldots,i_T)$,求各个状态序列$I$与观测序列$O=(o_1,o_2,\ldots,o_T)$的联合概率$P(O,I|\lambda)$,然后对所有可能的状态序列求和,得到$P(O|\lambda)$。

但是,这个公式的计算量很大,是$O(TN^T)$阶的,显然不可行。

下面将介绍前向-后向算法,通过递推地计算前向-后向概率,可以高效地进行隐马尔可夫模型的概率计算。

前向算法

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

可以递推得求得前向概率$\alpha_t(i)$及观测序列概率$P(O|\lambda)$。

一个观测:

image

两个观测:

image

三个观测:

image

通过上面的推导,可以发现一些规律:

image


算法:观测序列概率的前向算法

输入:模型$\lambda$,观测序列$O$

输出:$P(O|\lambda)$

(1)初始值

(2)递推,$t=1,2,\ldots,T-1$

(3)终止


后向算法

后向概率:给定隐马尔可夫模型$\lambda$,定义在时刻t状态为$qi$的条件下,从t+1到T的部分观测序列为$o{t+1},o{t+2},\ldots,o{T}$的概率为后向概率,记作:

可以用递推的方法求得后向概率$\beta_t(i)$及观测序列概率$P(O|\lambda)$。

将概率公式$P(O)=P(O_1,O_2,\ldots,O_T)$展开,得到:

通过上面的推导,可以发现一些规律:

其中,$i=1,2,\ldots,N,t=T-1,T-2,\ldots,1$。

image


算法:观测序列概率的后向算法

输入:模型$\lambda$,观测序列$O$

输出:$P(O|\lambda)$

(1)初始值

(2)递推,$t=T-1,T-2,\dots,1$

(3)终止


预测问题(解码问题)

已知:模型$\lambda=(A,B,\Pi)$和观测序列$O=(o_1,o_2,\ldots,o_T)$

求:$I^*=argmax_IP(I|O,\lambda)$

近似算法

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

在每一时刻t,最优可能的状态$i_t^*$为:

近似算法的优点是计算简单,但是存在以下两个问题:

  • 不能保证预测的状态序列是整体最优的;
  • 状态序列中可能存在转移概率为0的相邻状态。

尽管如此,近似算法仍然是有用的。下面将介绍更为精确的维特比算法。

维特比算法

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

一个观测:

image

两个观测:

image

三个观测:

image


算法:维特比算法

输入:模型$\lambda$,观测序列$O$

输出:最优路径$P(I|O,\lambda)$

(1)初始值

(2)递推,对$t=2,\ldots,T$

(3)终止

(4)最优路径回溯,对$t=T-1,T-2,\ldots,1$

求得最优路径$I^=(i_1^,i_2^,\ldots,i_r^)$。


评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×