隐马尔可夫模型及其应用(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}

ji的转移概率,再乘上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的学习问题和识别问题,请听下回分解。

Leave a Reply

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