NLP-HMM

https://www.cnblogs.com/pinard/p/6945257.html

简介

隐马尔科夫模型（Hidden Markov Model，以下简称HMM）是的机器学习模型，在语言识别，自然语言处理，模式识别等领域得到广泛的应用。当然，随着目前深度学习的崛起，尤其是RNN，LSTM等神经网络序列模型的火热，HMM的地位有所下降。但是作为一个经典的模型，学习HMM的模型和对应算法，对我们解决问题建模的能力提高以及算法思路的拓展还是很好的。

使用HMM模型时的问题一般有两个特征：１）问题是基于序列的，比如时间序列，或者状态序列。２）我们的问题中有两类数据，一类序列数据是可以观测到的，即观测序列；而另一类数据是不能观察到的，即隐藏状态序列，简称状态序列。有了这两个特征，那么这个问题一般可以用HMM模型来尝试解决。

例子：1）我现在在打字写博客，我在键盘上敲出来的一系列字符就是观测序列，而我实际想写的一段话就是隐藏序列，输入法的任务就是从敲入的一系列字符尽可能的猜测我要写的一段话，并把最可能的词语放在最前面让我选择，这就可以看做一个HMM模型了；2）我在和你说话，我发出的一串连续的声音就是观测序列，而我实际要表达的一段话就是状态序列，你大脑的任务，就是从这一串连续的声音中判断出我最可能要表达的话的内容。

定义：

Q是所有可能的隐藏状态的集合，V是所有可能的观测状态的集合，即

$Q = {q_1,q_2,...,q_N}, ; V ={v_1,v_2,...v_M}$

其中，N是可能的隐藏状态数，M是所有的可能的观察状态数。对于一个长度为T的序列，I对应的隐藏状态序列, O是对应的观察序列，即：

$I = {i_1,i_2,...,i_T}, ; O ={o_1,o_2,...o_T}$

其中，任意一个隐藏状态 $i_t in Q$ ，任意一个观察状态 $o_t in V$

假设

HMM模型做了两个很重要的假设如下：

　　　1） 齐次马尔科夫链假设。即任意时刻的隐藏状态只依赖于它前一个隐藏状态，这样假设有点极端，因为很多时候我们的某一个隐藏状态不仅仅只依赖于前一个隐藏状态，可能是前两个或者是前三个。但是这样假设的好处就是模型简单，便于求解。如果在时刻t的隐藏状态是 $i_t= q_i$ ，在时刻t+1的隐藏状态是 $i_{t+1} = q_j$ ，则从时刻t到时刻t+1的HMM状态转移概率 $a_{ij}$ 可表示为：

$a_{ij} = P(i_{t+1} = q_j | i_t= q_i)$ ，

这样 $a_{ij}$ 可以组成马尔科夫链的状态转移矩阵A:

$A=Big [a_{ij}Big ]_{N imes N}$ （状态集有Q有N个不同的状态，任意一个之间都可能状态转移，所以是NxN）

2） 观测独立性假设。即任意时刻的观察状态只仅仅依赖于当前时刻的隐藏状态，这也是一个为了简化模型的假设。如果在时刻t的隐藏状态是 $i_t= q_j$ ，而对应的观察状态为 $o_t = v_k$ ，则该时刻观察状态 $v_k$ 在隐藏状态 $q_j$ 下生成的概率为 $b_j(k)$ ,满足： $b_j(k) = P(o_t = v_k | i_t= q_j)$

则 $b_j(k)$ 可以组成观测状态生成的概率矩阵B:

$B = Big [b_j(k) Big ]_{N imes M}$ ,(N个不同的状态的任意一个都可能生成观测集V中M个的任意一个观测状态，所以是NxM)

除此之外，我们需要一组在时刻t=1的隐藏状态概率分布Π

$Pi = Big [ pi(i)Big ]_N ; 其中 ;pi(i) = P(i_1 = q_i)$ 其中 $;pi(i) = P(i_1 = q_i)$ ,（状态集合Q中N个状态的概率）

一个HMM模型，可以由隐藏状态初始概率分布Π, 状态转移概率矩阵A和观测状态概率矩阵B决定。Π,A决定状态序列，B决定观测序列。因此，HMM模型可以由一个三元组λλ表示如下：

$lambda = (A, B, Pi)$

例子：

假设我们有3个盒子，每个盒子里都有红色和白色两种球，这三个盒子里球的数量分别是：

盒子	1	2	3
红球数	5	4	7
白球数	5	6	3

按照下面的方法从盒子里抽球，开始的时候，从第一个盒子抽球的概率是0.2，从第二个盒子抽球的概率是0.4，从第三个盒子抽球的概率是0.4。以这个概率抽一次球后，将球放回。然后从当前盒子转移到下一个盒子进行抽球。规则是：如果当前抽球的盒子是第一个盒子，则以0.5的概率仍然留在第一个盒子继续抽球，以0.2的概率去第二个盒子抽球，以0.3的概率去第三个盒子抽球。如果当前抽球的盒子是第二个盒子，则以0.5的概率仍然留在第二个盒子继续抽球，以0.3的概率去第一个盒子抽球，以0.2的概率去第三个盒子抽球。如果当前抽球的盒子是第三个盒子，则以0.5的概率仍然留在第三个盒子继续抽球，以0.2的概率去第一个盒子抽球，以0.3的概率去第二个盒子抽球。如此下去，直到重复三次，得到一个球的颜色的观测序列:

O={红，白，红}

在这个过程中，观察者只能看到球的颜色序列，却不能看到球是从哪个盒子里取出的。

那么按照我们上一节HMM模型的定义，我们的观察集合是:V={红，白}，M=2

我们的状态集合是：Q={盒子1，盒子2，盒子3}，N=3，而观察序列和状态序列的长度为3.

初始状态分布为： $Pi = (0.2,0.4,0.4)^T$

状态转移概率分布矩阵为：

$A = left( egin{array} {ccc} 0.5 & 0.2 & 0.3 \ 0.3 & 0.5 & 0.2 \ 0.2 & 0.3 &0.5 end{array} ight)$

观测状态概率矩阵为：

$B = left( egin{array} {ccc} 0.5 & 0.5 \ 0.4 & 0.6 \ 0.7 & 0.3 end{array} ight)$

我们也可以抽象出HMM观测序列生成的过程。输入的是HMM的模型 $lambda = (A, B, Pi)$ ,观测序列的长度T，输出是观测序列 $O ={o_1,o_2,...o_T}$ ，生成的过程如下：

1）根据初始状态概率分布Π生成隐藏状态 $i_1$

2) for t from 1 to T

a. 按照隐藏状态 $i_t$ 的观测状态分布 $b_{i_t}(k)$ 生成观察状态 $o_t$

b. 按照隐藏状态 $i_t$ 的状态转移概率分布 $a_{i_t;;i_{t+1}}$ 产生隐藏状态 $i_{t+1}$

所有的 $o_t$ 一起形成观测序列 $O ={o_1,o_2,...o_T}$

HMM模型一共有三个经典的问题需要解决：

1）评估观察序列概率。即给定模型λ=(A,B,Π)和观测序列O={o1,o2,...oT}，计算在模型λ下观测序列O出现的概率P(O|λ)。这个问题的求解需要用到前向后向算法。

2）模型参数学习问题。即给定观测序列O={o1,o2,...oT}，估计模型λ=(A,B,Π)的参数，使该模型下观测序列的条件概率P(O|λ)最大。这个问题的求解需要用到基于EM算法的鲍姆-韦尔奇算法，这个问题是HMM模型三个问题中最复杂的。

3）预测问题，也称为解码问题。即给定模型λ=(A,B,Π)和观测序列O={o1,o2,...oT}，求给定观测序列条件下，最可能出现的对应的状态序列，这个问题的求解需要用到基于动态规划的维特比算法，这个问题是HMM模型三个问题中复杂度居中的算法。

1）用前向算法求HMM观测序列的概率

例子：

　而观察序列和状态序列的长度为3.

初始状态分布为： $Pi = (0.2,0.4,0.4)^T$

状态转移概率分布矩阵为：

$A = left( egin{array} {ccc} 0.5 & 0.2 & 0.3 \ 0.3 & 0.5 & 0.2 \ 0.2 & 0.3 &0.5 end{array} ight)$

观测状态概率矩阵为：

$B = left( egin{array} {ccc} 0.5 & 0.5 \ 0.4 & 0.6 \ 0.7 & 0.3 end{array} ight)$

球的颜色的观测序列:O={红，白，红}

按照我们上一节的前向算法。首先计算时刻1三个状态的前向概率：

时刻1是红色球，隐藏状态是盒子1的概率为： $alpha_1(1) = pi_1b_1(o_1) = 0.2 imes 0.5 = 0.1$

隐藏状态是盒子2的概率为： $alpha_1(2) = pi_2b_2(o_1) = 0.4 imes 0.4 = 0.16$

隐藏状态是盒子3的概率为： $alpha_1(3) = pi_3b_3(o_1) = 0.4 imes 0.7 = 0.28$

现在我们可以开始递推了，首先递推时刻2三个状态的前向概率：

时刻2是白色球，隐藏状态是盒子1的概率为：

$alpha_2(1) = Big[sumlimits_{i=1}^3alpha_1(i)a_{i1}Big]b_1(o_2) = [0.1*0.5+0.16*0.3+0.28*0.2 ] imes 0.5 = 0.077$

（1时刻为盒子1--2时刻为盒子1；1时刻盒子2--2时刻盒子1；1时刻盒子3--2时刻盒子1；3个概率和为2时刻盒子1的前向概率，2时刻，盒子1观测状态为白球概率为0.5）

隐藏状态是盒子2的概率为：

$alpha_2(2) = Big[sumlimits_{i=1}^3alpha_1(i)a_{i2}Big]b_2(o_2) =[0.1*0.2+0.16*0.5+0.28*0.3 ] imes 0.6 = 0.1104$

（1时刻为盒子1--2时刻为盒子2；1时刻盒子2--2时刻盒子2；1时刻盒子3--2时刻盒子2；3个概率和为2时刻盒子2的前向概率，2时刻，盒子2观测状态为白球概率为0.6）

隐藏状态是盒子3的概率为：

$alpha_2(3) = Big[sumlimits_{i=1}^3alpha_1(i)a_{i3}Big]b_3(o_2) = [0.1*0.3+0.16*0.2+0.28*0.5 ] imes 0.3 = 0.0606$

（1时刻为盒子1--2时刻为盒子3；1时刻盒子2--2时刻盒子3；1时刻盒子3--2时刻盒子3；3个概率和为2时刻盒子3的前向概率，2时刻，盒子3观测状态为白球概率为0.3）

继续递推，现在我们递推时刻3三个状态的前向概率：

时刻3是红色球，隐藏状态是盒子1的概率为：

$alpha_3(1) = Big[sumlimits_{i=1}^3alpha_2(i)a_{i1}Big]b_1(o_3) = [0.077*0.5+0.1104*0.3+0.0606*0.2 ] imes 0.5 = 0.04187$

（2时刻为盒子1--3时刻为盒子1；2时刻盒子2--3时刻盒子1；2时刻盒子3--3时刻盒子1；3个概率和为3时刻盒子1的前向概率，3时刻，盒子1观测状态为红球概率为0.5）

隐藏状态是盒子2的概率为：

$alpha_3(2) = Big[sumlimits_{i=1}^3alpha_2(i)a_{i2}Big]b_2(o_3) = [0.077*0.2+0.1104*0.5+0.0606*0.3 ] imes 0.4 = 0.03551$

（2时刻为盒子1--3时刻为盒子2；2时刻盒子2--3时刻盒子2；2时刻盒子3--3时刻盒子2；3个概率和为3时刻盒子1的前向概率，3时刻，盒子2观测状态为红球概率为0.4）

隐藏状态是盒子3的概率为：

$alpha_3(3) = Big[sumlimits_{i=1}^3alpha_2(i)a_{i3}Big]b_3(o_3) = [0.077*0.3+0.1104*0.2+0.0606*0.5 ] imes 0.7 = 0.05284$

最终我们求出观测序列:O={红，白，红}的概率为：

$P(O|lambda) = sumlimits_{i=1}^3alpha_3(i) = 0.13022$

2）后向算法求HMM观测序列概率

后向概率的定义是：当第t个时刻的状态为i时，后面的时刻分别观测到yt+1,yt+2, ..., yT的概率，即：