隐马尔可夫模型 Hidden Markov Model
目录

1. 一个例子

首先还是看吴军的例子:数学之美 系列三 -- 隐含马尔可夫模型在语言处理中的应用

2. 隐马尔可夫模型

在正常的马尔可夫模型中,状态(x(t))对于观察者来说是直接可见的。 而在隐马尔可夫模型中,状态(x(t))并不是直接可见的,但受状态影响的某些观察序列(y(t))则是可见的。

上图中,随机过程x(t)是一个马尔可夫链,但不可见。 隐含状态x(t)决定了观察状态y(t),第i时刻的y(ti)只由x(ti)决定,它们之间是独立输出关系。

因此隐马尔可夫模型是一个双重随机过程,有两个组成部分:

  • 马尔可夫链:描述状态(x(t))的转移,用隐含状态转移概率描述。
  • 一般随机过程:描述状态与观察序列间(y(t))的关系,用观察状态转移概率描述。

定义隐含状态转移概率矩阵为A,观察状态转移概率矩阵为B,初始状态概率矩阵为π, 那么可以用λ=(A,B,π)三元组来简洁的表示一个隐马尔可夫模型。

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

3.1 评估问题

已知模型参数λ=(A,B,π),计算某一观察序列Y=y1,y2,...,yt的概率。

直观地去解这个问题的想法是,列出所有可能的隐含序列$X_i=x_{i1},x_{i2},...,x_{it},i=1...N^t$,N为隐含状态类型个数。 然后根据λ计算每一个$X_i$出现的概率$P(X_i|\lambda)$和$X_i$情况下$Y$出现的概率$P(Y|X_i,\lambda)$,最后加和。即

$P(Y|\lambda) = \sum_{1}^{N^t}P(X_i,Y|\lambda) = \sum_1^{N^t}P(Y|X_i,\lambda)P(X_i|\lambda)$

这样的话计算量太大,隐层序列共有$N^t$种排列可能,需要$N^t$次计算,于是采用动态规划的思想解这个问题:前向法(forward algorithm)。

定义t时刻在隐含状态为$x_{t,k}$(k=N种可能性)时,观察状态为$y_t$(确定的)时的概率:

$\alpha_t(x_{t,k}) = P(y_t,x_{t,k}) = P(y_t|x_{t,k})P(x_{t,k}) = P(y_t|x_{t,k})\sum_{i=1}^N\alpha_{t-1}(x_{t-1,i})P(x_{t,k}|x_{t-1,i})$

这样递归地去计算,每一时刻t需计算N次,共需计算$N*t$次。

最后计算观察序列Y出现的概率:

$P(Y) = \sum_{i=1}^N\lambda_t(x_{t,i})$

最后注意的是每个观察序列出现的概率是个定值。

3.2 解码问题

已知模型参数λ=(A,B,π),寻找最可能产生某一观察序列Y=y1,y2,...,yt的隐含状态序列。

上面问题就是P(X|Y)最大化问题,又因为P(X|Y)=P(X,Y)P(Y)且上一节说明P(Y)是一个常数, 那么P(X|Y)最大化问题等价于P(X,Y)最大化问题,即求P(X,Y)最大化的序列X。

在观察序列为Y的情况下,t时刻隐含状态$x_t$为i(i=1...M)的概率为$P(x_t=i,y_{1:t})$, 那么定义$P(x_t=i,y_{1:t})$的最大值就是:

$\delta_t(k) = \max_{x_{1:t-1}} P(x_{1:t-1},x_t=k,y_{1:t})$

显然,t=1时:

$\delta_t(k) = \pi_ib_{iy_1}$,

当 t >= 2时:

$\delta_t(k) = \max_j(\delta_{t-1}(j)a_{ji})b_{iy_t}$

通过t不停地迭代,直到达到T时刻结束,就求得了最大值。 迭代过程中还有$\delta_t(k)$的最大化参数:

$psi_t(k)=\arg \max_k (\delta_{t-1}(j)a_{ji})$

这就是Viterbi算法的一般思路。

3.3 学习问题

已知观察序列Y=y1,y2,...,yt,寻找模型参数λ=(A,B,π)使观察序列Y的概率最大。

通常使用Baum-Welch算法以及Reversed Viterbi算法解决。

参考

发表评论