从零开始学NLP（八）隐马尔科夫模型（超详细）

前言

一、HMM基础

前言

上一章已经介绍了语言模型，提到了马尔科夫假设，而本章重点介绍的隐马尔科夫模型，是用来解决参数估计的问题。隐马尔可夫模型(Hidden Markov model, HMM)是一种结构最简单的动态贝叶斯网的生成模型，它也是一种著名的有向图模型。它是典型的自然语言中处理标注问题的统计机器学模型，本章将重点介绍这种经典的机器学习模型。

一、HMM基础

我们的问题是基于序列的，比如时间序列，如股票、文本、气温等等，或者状态序列。
我们的问题中有两类数据，一类序列数据是可以观测到的，即观测序列；而另一类数据是不能观察到的，即隐藏状态序列，简称状态序列。

有了这两个特征，那么这个问题一般可以用HMM模型来尝试解决。这样的问题在实际生活中是很多的。比如：说话人说出的声波就是观测序列，而实际表达的意思就是状态序列，那对于听者的任务就是从这一系列声波中判断说话人所要表达的内容。

举一个经典的例子就是投掷不确定骰子。

假设手里有三个不同的骰子。第一个骰子是我们平常见的骰子（称这个骰子为D6），6个面，每个面（1，2，3，4，5，6）出现的概率是1/6。第二个骰子是个四面体（称这个骰子为D4），每个面（1，2，3，4）出现的概率是1/4。第三个骰子有八个面（称这个骰子为D8），每个面（1，2，3，4，5，6，7，8）出现的概率是1/8，如图所示：

从零开始学NLP（八）隐马尔科夫模型（超详细）

隐马尔可夫模型示意图如下所示：

从零开始学NLP（八）隐马尔科夫模型（超详细）

图中，箭头表示变量之间的依赖关系，说明如下所示：

从零开始学NLP（八）隐马尔科夫模型（超详细）

也就是说在任意时刻，观测变量(骰子)仅依赖于状态变量(哪类骰子)，同时时刻的状态 z_t 仅依赖于 t-1 时刻的状态 $z_{t-1}$ 。这就是马尔科夫链，即系统的下一时刻仅由当前状态（无记忆）决定。

二、HMM定义

根据上面的例子，可以得到隐马尔可夫模型的定义。

隐马尔可夫模型由初始的概率分布、状态转移概率分布以及观测概率分布确定。具体的形式如下，这里设是所有可能的状态的集合，是所有可能的观测的集合，即有：

$Q=\{q_1,q_2,...,q_N\}$

$V=\{v_1,v_2,...,v_M\}$

其中，N是可能的状态数，M是可能观测的数。另外设是长度为的状态序列，是对应的观测序列：

从零开始学NLP（八）隐马尔科夫模型（超详细）

$Z=\{z_1,z_2,...,z_k\}$
$X=\{x_1,x_2,...,x_k\}$

很自然的推导出，在隐马尔可夫模型中，有3个矩阵变量，分别是状态转移概率矩阵，观测概率矩阵，以及初始状态概率向量 $\pi$ 。

状态转移概率矩阵为：

$A=\{a_{ij}\}_{N\times N}$

其中，

$a_{ij}=p(z_{k+1}=q_i|z_{k}=q_j),i=1,2...,N,j=1,2,...,N$

是在时刻处于状态 q_i 的条件下生成状态 q_j 的概率。

观测概率矩阵为：

$B=\{b_{ij}\}_{N\times M}$

其中，

$b_{ij}=p(x_{k}=v_j|z_{k}=q_i),i=1,2...,N,j=1,2,...,N$

是在时刻处于状态 q_i 的条件下生成状态 q_j 的概率。

初始状态概率向量为：

$\pi=(\pi_i),\pi_i=P(z_1=q_i),i=1,2,..,N$

$\pi_i$ 为时刻 t=1 处于状态 q_i 的概率。

由此，可以推导出初始状态概率向量 $\pi$ ，状态转移概率矩阵和观测概率矩阵就能决定一个隐马尔可夫模型。 $\pi$ 和决定状态序列，决定观测序列，也被称为隐马尔科夫模型的三要素。因此HMM可以用三元符号表示为：

$\lambda =\{\pi,A,B\}$

从定义中，可以发现隐马尔可夫模型作了两个基本假设：

马尔可夫齐次性假设，即假设隐藏的马尔可夫链在任意时刻t的状态只依赖于其前一时刻的状态，与其它时刻的状态及观测无关，也与时刻无关。
观测独立性假设，即假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态，与其他观测及状态无关。

三、HMM的三个基本问题

基于上述经典的例子——投掷不确定骰子，介绍隐马尔科夫模型相关的三类算法以及三种基本问题。

1.概率计算问题

给定模型 $\lambda =\{\pi,A,B\}$ 和观测序列 $X=\{x_1,x_2,...,x_k\}$ ，计算在该模型下观测序列出现的概率 $P(X|\lambda)$ 。

2. 学习问题

已知观测序列 $X=\{x_1,x_2,...,x_k\}$ ，估计模型 $\lambda =\{\pi,A,B\}$ 参数，使得在该模型下观测序列概率 $P(X|\lambda)$ 最大，即用极大似然估计的方法估计参数。

3.预测问题

已知模型 $\lambda =\{\pi,A,B\}$ 和观测序列 $X=\{x_1,x_2,...,x_k\}$ ，求对给定观测序列条件概率 P(Z|X) 最大的状态序列 $Z=\{z_1,z_2,...,z_k\}$ ，即给定观测序列，求最有可能的对应的状态序列。

所以我们得出结论，暴力算法在这里并不实用，于是就引出了前向后向算法。它们都是基于动态规划思想求解。

四、HMM中的参数估计

Forward/Backward算法在估计HMM参数中扮演很重要的角色。换句话说，在估计HMM参数过程中，会用到Forward/Backward算法的结果。所以，在这里首先给大家介绍什么是前向后向算法。

1.前向算法

前向算法本质上属于动态规划的算法，也就是我们要通过找到局部状态递推的公式，这样一步步的从子问题的最优解拓展到整个问题的最优解。

我们首先定义一下前向概率。

前向概率：给定隐马尔科夫模型 $\lambda$ ，定义时，观测序列为且隐藏状态为 q_i 的概率为前向概率，记为：

$a_t(i)=P(x_1,x_2,...,x_t,z_t=q_i|\lambda)$

既然是动态规划，可以假设已经得到在时刻时各个隐藏状态的前向概率，现在我们就可以递推的出时刻 t+1 时各个隐藏状态的前向概率。

从零开始学NLP（八）隐马尔科夫模型（超详细）

从上图可以基于时刻t时各个隐藏状态的前向概率，再乘以对应的状态转移概率，即 $a_t(j)a_{ji}$ 就是在时刻观测到 x_1,x_2,...,x_t ，并且时刻隐藏状态 $q_{i}$ 的概率，由此可以递推地求得前向概率 $a_{t+1}(i)$ 及观测序列概率。计算的步骤为：

（1）根据前向概率公式，先设定 t=1 的初值：

$a_{1}(i)=\pi_ib_i(x_1),i=1,2,...,N$

（2）根据前向概率公式对前向概率进行递推，因此对 t=1,2,...,K-1 ，有：

$a_{t+1}(i)=[\sum_{j=1}^{N}a_{t}(j)a_{ji}]b_i(x_{t+1}),i=1,2,...,N$

（3）最后对所有的前向概率进行求和得到最终的结果，即为：

$P(x|a)=\sum_{i=1}^{N}a_K(i)$

由于到了时间T，一共有N种状态发射了最后那个观测，所以最终的结果要将这些概率加起来（因为每个隐状态都可能产生我们需要的观测值，所以都要加起来）。由于每次递推都是在前一次的基础上进行的，所以降低了复杂度（计算只存在于相邻的俩个时间点）。每个时间点都有种状态，所以相邻两个时间之间的递推消耗 N^2 次计算。而每次递推都是在前一次的基础上做的，所以只需累加次，所以总体复杂度是。这比起之前提到的暴力算法的指数级复杂度已经好了许多。

2.后向算法

后向概率与前向概率非常类似，也是基于动态规划的思想，唯一的区别是选择的局部状态不同，后向算法用的是“后向概率”，那么后向概率是如何定义的呢？下面介绍一下：

首先给出后向概率定义：

后向概率：给定隐马尔可夫模型 $\lambda$ ，定义在时刻状态为 q_i 的条件下，从 t+1 到的部分观测序列为
x_t+1,x_t+2,...,x_K 的概率为后向概率，记作:

$\beta _t(i)=P(x_t+1,x_t+2,...,x_K|z_t=q_i,\lambda)$

后向概率的动态规划递推公式和前向概率是相反的。假设已经得到在 t+1 时各个隐藏状态的后向概率 $\beta _{t+1}(j)$ ，现在我们需要递推出时刻时各个隐藏状态的后向概率。

从零开始学NLP（八）隐马尔科夫模型（超详细）

从上图，可以计算出观测状态的序列为 x_t+2,x_t+3,...,x_K ，时隐藏状态为 q_i ，时刻 t+1 隐藏状态为 q_j 的概率为 $a_{ij}\beta _{t+1}(j)$ 。由此可以用递推的方法求得后向概率 $\beta _t(i)$ ，及观测序列概率 $p(x|\lambda)$ ，下面给出后向算法的算法流程:

输入：隐马尔可夫模型,观测序列

输出：观测序列概率

（1）初始化时刻的各个隐藏状态后向概率：

$\beta _{K}(i)=1,i=1,2,...,N$

（2）根据后向概率公式对后向概率进行递推，因此对 t=K-1,K-2,...,1 ，有：

$\beta_{t}(i)=\sum_{j=1}^{N}a_{ij}b_{j}(x_{t+1})\beta _{t+1}(j),i=1,2,...,N$

（3）最后对所有的前向概率进行求和得到最终的结果，即为：

$P(x|\lambda)=\sum_{i=1}^{N}\pi_ib_i(x_1)\beta _1(i)$

五、HMM实例

下面我们用一个简单的实例来描述上面抽象出的HMM模型。这是一个盒子与球的模型，例子来源于李航的《统计学习方法》。

假设我们有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的概率去第二个盒子抽球。如此下去，直到重复三次，得到一个球的颜色的观测序列: X={红，白，红}。

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

所以按照上述内容的介绍：

观测集合是：V={红，白}，M=2

状态集合是：Q={1,2,3}，N=3

而观测序列和状态序列长为3。

初始状态向量： $\pi=(0.2,0.4,0.4)^T$

状态转移矩阵：

$A=\begin{pmatrix} 0.5 &0.2 &0.3 \\ 0.3 &0.5 &0.2 \\ 0.2&0.3 &0.5 \end{pmatrix}$

观测状态矩阵：

$B=\begin{pmatrix} 0.5 &0.5 \\ 0.4 &0.6 \\ 0.7 &0.3 \end{pmatrix}$

现在我们解决概率计算问题。

按照之前所说的算法，首先计算时刻1三个状态的前向概率：

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

$a_{1}(1)=\pi_1b_1(x_1)=0.2\times0.5=0.1$

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

$a_{1}(2)=\pi_2b_2(x_1)=0.4\times0.4=0.16$

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

$a_{1}(3)=\pi_3b_3(x_1)=0.4\times0.7=0.28$

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

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

$a_{2}(1)=[\sum_{j=1}^{3}a_{1}(j)a_{j1}]b_1(x_{2})=0.077$

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

$a_{2}(2)=[\sum_{j=1}^{3}a_{1}(j)a_{j2}]b_2(x_{2})=0.1104$

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

$a_{2}(3)=[\sum_{j=1}^{3}a_{1}(j)a_{j3}]b_3(x_{2})=0.0606$

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

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

$a_{3}(1)=[\sum_{j=1}^{3}a_{2}(j)a_{j1}]b_1(x_{3})=0.04187$

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

$a_{3}(2)=[\sum_{j=1}^{3}a_{2}(j)a_{j2}]b_2(x_{3})=0.03551$

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

$a_{3}(2)=[\sum_{j=1}^{3}a_{2}(j)a_{j3}]b_3(x_{3})=0.05284$

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

$P(x|a)=\sum_{i=1}^{3}a_3(i)=0.13022$

总结

在HMM中，有两类变量，一种是模型本身的参数，另外一种是隐变量。而且很难同时对这两类参数求估计，所以采用的一种方法是：把其中一组变量看作是常量(constant)，从而估计另外一组变量，以此类推。具体来讲，把模型参数看作是常量，估计变量；把看作是常量，估计模型参数；把模型参数看作是常量，估计变量；把看作是常量，估计模型参数…。一直循环到收敛为止。

关于HMM，做个简单的总结:

HMM是很流行的序列模型，广泛应用在语音识别等领域
HMM也可以用在词性标注、实体识别等文本问题中
HMM的inference过程实际上是对于序列的预测过程，要用到维特比算法
维特比算法实际上是动态规划算法
HMM的参数估计实际上是模型训练过程，需要估计三类不同的参数
HMM的参数估计过程要用到EM算法，而且EM算法的结果依赖于初始化结果。不同的初始化很可能带来不一样的效果
HMM的参数估计中，有几个关键的模块如F/B算法，Forward算法，Backward算法等

从下一章开始，将会介绍另外一种流行的序列模型叫作条件随机场(CRF)，在文本领域用得非常多。

参考：

贪心学院nlp

隐马尔可夫模型(HMM)详解

隐马尔可夫模型最详细讲解 HMM(Hidden Markov Model)

李航老师-《统计学习方法》

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/215166.html原文链接：https://javaforall.net

从零开始学NLP（八）隐马尔科夫模型（超详细）

前言

一、HMM基础

二、HMM定义