当前位置博文首页 > Yunlord的博客：从零开始学NLP（八）隐马尔科夫模型（超详细）

最大化缩小

Yunlord的博客：从零开始学NLP（八）隐马尔科夫模型（超详细）

作者：[db:作者] 时间：2021-09-11 10:53

前言

一、HMM基础

二、HMM定义

三、HMM的三个基本问题

1.概率计算问题

2. 学习问题

3.预测问题

四、HMM中的参数估计

1.前向算法

2.后向算法

五、HMM实例

总结

前言

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

一、HMM基础

HMM作为经典的序列模型，广泛应用在各类AI场景中。其中，HMM的最成名之作可以认为是语音识别领域。在深度学习流行之前，绝大部分语音识别系统都基于HMM模型，也算是经典中的经典了。另外，HMM在文本领域也有着很多的应用如中文分词。

除此之外，理解HMM对于后续学习RNN模型来说有着比较大的意义，因为这两者很类似，你可以简单地认为HMM是传统的序列模型，RNN为基于深度学习的序列模型。

首先我们来看看什么样的问题解决可以用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，如图所示：

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

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

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

二、HMM定义

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

隐马尔科夫模型是关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列，再由各个状态生成一个可观测的随机序列的过程，隐藏的马尔可夫链随机生成的状态序列，称为状态序列(也就上面例子中的D6，D8等)；每个状态生成一个观测，而由此产生的观测随机序列，称为观测序列(也就上面例子中的1，6等)。序列的每个位置又可以看作是一个时刻。
?

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

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

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

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

$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)$ 。

通俗来说，就是知道骰子有几种（隐含状态数量），每种骰子是什么（转换概率），根据掷骰子掷出的结果（观测序列），得到掷出这个结果的概率。
看似这个问题意义不大，因为掷出来的结果很多时候都对应了一个比较大的概率。这个问题的目的其实是检测观察到的结果和已知的模型是否吻合。如果很多次结果都对应了比较小的概率，那么就说明我们已知的模型参数很有可能是错的。 N^T

2. 学习问题

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

通俗来说，就是知道骰子有几种（隐含状态数量），不知道每种骰子是什么（转换概率），观测到很多次掷骰子的结果（观测序列），想反推出每种骰子是什么（转换概率）。
这个问题很重要，因为这是最常见的情况。很多时候我们只有可见结果，不知道HMM模型里的参数，我们需要从可见结果估计出这些参数，这是建模的一个必要步骤。

3.预测问题

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

通俗来说，就是知道骰子有几种（隐含状态数量），每种骰子是什么（转换概率），根据掷骰子掷出的结果（观测序列），想知道每次掷出来的都是哪种骰子（隐含状态链）。
这个问题，在语音识别领域呢，叫做解码问题。该解法就是求最大似然状态路径，说通俗点呢，就是求一串骰子序列，使得这串骰子序列产生观测结果的概率最大。举例来说，我知道我有三个骰子，六面骰，四面骰，八面骰。我也知道我掷了十次的结果（1 6 3 5 2 7 3 5 2 4），我不知道每次用了那种骰子，我想知道最有可能的骰子序列。其实最简单而暴力的方法就是穷举所有可能的骰子序列，然后把每个序列对应的概率算出来，最后我们从里面把对应最大概率的序列挑出来就行了。如果马尔可夫链不长，当然可行。如果长的话，穷举的数量太大，我们的预测状态有种组合，算法的时间复杂度是 O(TN^T) 阶的。

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

四、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$ 时各个隐藏状态的前向概率。

从上图可以基于时刻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)$ ，现在我们需要递推出时刻时各个隐藏状态的后向概率。

从上图，可以计算出观测状态的序列为 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)

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

上一篇：Yunlord的博客：从零开始学NLP（九）无向图模型与标记偏置

下一篇：没有了

立即下载 - IIS7 站长工具包

Yunlord的博客：从零开始学NLP（八）隐马尔科夫模型（超详细）

作者：[db:作者] 时间：2021-09-11 10:53

前言

一、HMM基础

二、HMM定义

三、HMM的三个基本问题

1.概率计算问题

2. 学习问题

3.预测问题

四、HMM中的参数估计

1.前向算法

2.后向算法

五、HMM实例

总结

最新 更多<<

推荐 更多<<

Yunlord的博客：从零开始学NLP（八） 隐马尔科夫模型（超详细）

作者：[db:作者] 时间：2021-09-11 10:53

前言

一、HMM基础

二、HMM定义

三、HMM的三个基本问题

1.概率计算问题

2. 学习问题

3.预测问题

四、HMM中的参数估计

1.前向算法

2.后向算法

五、HMM实例

总结

最新 更多<<

推荐 更多<<

Yunlord的博客：从零开始学NLP（八）隐马尔科夫模型（超详细）

最新更多<<

推荐更多<<