隐马尔可夫模型及其应用(1)简介&解码问题

隐马尔可夫模型(Hidden Markov Model, HMM)是统计模型,它用来描述一个含有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数。然后利用这些参数来作进一步的分析,例如模式识别。

先举一个简单的例子以直观地理解HMM的实质——韦小宝的骰子。

hmm-2

假设韦小宝有两个骰子,一个正常的骰子A,A以1/6的概率均等的出现每个点;一个不正常的骰子B,B出现5,6点数的概率为0.3,出现其他点数的概率为0.1。显然投掷B更容易出现大的点数。每次试验第一次投掷时,韦小宝会以0.4的概率出千(即投掷B)。但是在一次试验中,韦小宝不太可能一直出千,所以骰子会在A、B之间转换,比如这次投了B,下次可能会以0.1的概率投A。A、B之间的转移概率如下图。

hmm-1

某一次试验,我们观察到韦小宝掷出的骰子序列为$O=(1,3,4,5,5,6,6,3,2,6)$,请问韦小宝什么时候出千了。这个问题就可以通过HMM求解。

HMM有2个状态:

  1. 观测状态。我们观察到的骰子序列称为观测状态$\mathbf{Y}=\{y_1,y_2,…,y_T\}$
  2. 隐状态。隐含在每个观测状态里面的是隐状态$\mathbf{X}=\{x_1,x_2,…,x_T\}$

T是时间,也可以认为是观测的次数。HMM有3个参数:

  1. 初始分布$\mathbf{\mu}=(\mu_i)$,$\mu_i=Pr(x_1=i)$,即第一次观测时,每个隐状态出现的概率
  2. 转移概率矩阵$A=(a_{ij})$,$a_{ij}=Pr(x_{t+1}=j|x_t=i)$,即t时刻的隐状态为i,t+1时刻转移到隐状态j的概率
  3. 发射概率矩阵$B=(b_{il})$,$b_{il}=Pr(y_t=l|x_t=i)$,即t时候隐状态为i的情况下,观测到状态为l的概率

参数$\mathbf{\lambda=\{\mu,A,B\}}$称为HMM的模型参数。具体到上面的例子,我们有初始分布和转移概率为:

hmm-3

发射概率为:

hmm-4

观测状态为$\mathbf{Y}=(1,3,4,5,5,6,6,3,2,6)$,问题就是求解出隐状态$\mathbf{X}$,此问题被称为HMM的解码问题,可以由著名的维特比算法(Viterbi algorithm)解决。

解码问题是要求出使得观测状态$Y$出现概率最大的隐状态$X$,假设有N个隐状态(本例为2),共有T个时刻(本例为10),则每个时刻有N个取值可能,则共有$N^T$条可能的隐状态链(本例为$2^{10}$)。我们需要求出每一条隐状态链下T个发射概率的乘积,然后取最大值,这是指数时间复杂度的($O(N^T)$)。

hmm-5

但是Viterbi算法是一个动态规划算法,只需多项式时间即可解决该问题。该算法的原理很好理解,假设我们求得到$s_{i2}$的最大概率路径为下图中的红线$s_{11}\rightarrow s_{22}\rightarrow … s_{i2}$,则在求经过$s_{i2}$到$s_{(i+1)1}$的最大概率路径时,不需要再测试$s_{13}\rightarrow s_{21}\rightarrow s_{i2}\rightarrow s_{(i+1)1}$这条路径(下图蓝线),因为显然已经知道红线概率大于蓝线概率了。图中还有很多类似蓝线的路径都可以不用计算了,大大提高了求解速度。

因为计算第$i+1$时刻的累积概率只和第$i$时刻的概率有关,每次至多计算$N*N$个概率乘积(可以从$i$时刻的$N$个状态到达$i+1$时刻的某个状态,$i+1$时刻共有$N$个状态),最多计算T次(共T个时刻),所以时间复杂度降到了$O(N^2T)$。

hmm-6

下面我们形式化的描述Viterbi算法

假设$\delta_t(i)$为$t$时刻取到隐状态$i$,且1~t的观测状态都符合观测值$Y$的各个路径的最大概率,即

$$\begin{equation}\delta_t(i)=\underset{i_1,…,i_{t-1}}{\max}Pr(X_t=i,X_{t-1}=i_{t-1},…,X_1=i_1,Y_t=y_t,…,Y_1=y_1|\mathbf{\lambda})\end{equation}$$

联系上图,可认为$\delta_t(i)$为红线。则递推公式为:

$$\begin{equation}\delta_{t+1}(i)=b_{iy_{t+1}}\underset{j}{\max}(\delta_t(j)a_{ji})\end{equation}$$

由$j$到$i$的转移概率,再乘上$i$发射$y_{t+1}$的概率。

在初始时刻$t=1$,有:

$$\begin{equation}\delta_1(i)=\mu_ib_{iy_1}\end{equation}$$

最后的全局最大概率为$\underset{j}{\max}\delta_T(j)$。为了得到完整路径,我们保留每一隐状态取得最大概率时的上一隐状态,即:

$$\begin{equation}\psi_{t+1}(i)=j^*\end{equation}$$

其中$j^*$要满足

$$\begin{equation}\delta_{t+1}(i)=b_{iy_{t+1}}\delta_t(j^*)a_{j^*i}\end{equation}$$

最后使用如下回溯法得到所有最佳隐状态:

$$\begin{equation}X_T=i^*\in\{i:\delta_T(i)=\underset{j}{\max}\delta_T(j)\}\end{equation}$$

$$\begin{equation}X_t=\psi_{t+1}(X_{t+1})\end{equation}$$

下面我们利用Viterbi算法来求解韦小宝的骰子这个例子。

$t=1$时,$y_1=1$,有$\delta_1(A)=0.6*1/6=0.1$,$\delta_1(B)=0.4*0.1=0.04$。

$t=2$时,$y_2=3$,有:

  1. 隐状态为A:a)A->A有$\delta_2(A)=(1/6)*0.1*0.8=1.33*10^{-2}$;b)B->A有$\delta_2(A)=(1/6)*0.04*0.1=6.6*10^{-4}$。所以A->A,$\psi_2(A)=A$。
  2. 隐状态为B:a)A->B有$\delta_2(B)=0.1*0.1*0.2=2*10^{-3}$;b)B->B有$\delta_2(B)=0.1*0.04*0.9=3.6*10^{-3}$。所以B->B,$\psi_2(B)=B$。

如此计算下去,可以得到如下表:

hmm-7

$t=10$时最大概率为$\delta_{10}(B)$,经过回溯得到最佳隐状态为:

hmm-8

所以HMM很神奇吧,可以抓住韦小宝从第5次开始就一直在出千,而且出千之后,掷出的点数大部分为5和6。

Viterbi算法还可用于解决语音识别或者拼音输入法。我们知道中文的一个拼音可以对应多个汉字,连续的一段拼音就能组成成千上万种可能的句子,哪一个句子才是最佳候选呢?我们可以把每个拼音当成观测状态,同音的汉字当成可能的隐状态。通过背景语料库统计得到每个汉字出现在词首的概率、汉字之间的转移概率和汉字与拼音之间的发射概率,这样我们就能得到模型参数,然后利用Viterbi算法求解出一个最佳的隐状态序列,这样就能完成一个简易的拼音输入法。

HMM在实际中主要有3个方面的应用,分别是:

  1. 从一段观测序列$\mathbf{Y}$及已知模型$\mathbf{\lambda=(\mu,A,B)}$出发,估计出隐状态$\mathbf{X}$的最佳值,称为解码问题,这是状态估计问题。这篇博客讨论的就是这个问题。
  2. 从一段观测序列$\mathbf{Y}$出发,估计模型参数组$\mathbf{\lambda=(\mu,A,B)}$,称为学习问题,就是参数估计问题。
  3. 对于一个特定的观测链$\mathbf{Y}$,已知它可能是由已经学习好的若干模型之一所得的观测,要决定此观测究竟是得自其中哪一个模型,这称为识别问题,就是分类问题。

关于HMM的学习问题和识别问题,请听下回分解。

1 thought on “隐马尔可夫模型及其应用(1)简介&解码问题

  1. Pingback: 随机矩阵及其特征值 | bitJoy

Leave a Reply

Your email address will not be published. Required fields are marked *