Press "Enter" to skip to content

初学者也能看懂的隐马尔科夫模型介绍

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

隐马尔科夫模型是(hidden Markov model, HMM )是可用于标注问题的统计学习模型,描述由隐藏的马尔科夫链随机生成观测序列的过程。

 

隐马尔可夫模型(hidden Markov model, HMM )是时间序列的概率模型,常用于词性标注,语音识别,文本分析等领域。 HMM 是基于马尔科夫链进行标注的,我们对已经观察的数据序列 O 进行标注,标注序列 I 相当于不可观测序列(隐变量),如何求解概率最大的标注序列  I  是 HMM 的核心问题,我们以图解的方式形象的描述 HMM 问题。

 

已知观测序列 ,标注序列 , 其中观测序列是相互独立的且与对应的标注序列相关,标注序列符合马尔科夫链模型,如下图:

 

 

再次强调下隐马尔科夫模型假设的场景,1)观测序列是相互独立的, 2 )标注序列符合马尔科夫链模型, 3 )观测序列由标注序列决定。

 

HMM模型主要处理以下三个问题:

 

1)已知观测序列O,如何求解 HMM 模型参数 。

 

2)已知观测序列O和模型参数 ,如何求解最有可能的标注序列 I 。

 

3)已知观测序列O和模型参数 ,如何求解观测序列O出现的概率

 

下面给出大致的解决方案:

 

1) 已知观测序列 O ,如何求解模型参数。

 

 

其中I为标注序列,在上式中的含义为隐变量,因此可用 EM 算法求解上式的模型参数。

 

2) 已知观测序列 O 和模型参数,如何求解最有可能的标注序列 I

 

3) 已知观测序列O和模型参数,如何求解观测序列O出现的概率概率

 

后续内容会给出具体的算法和实例。

 

介绍到这里,相信大家对HMM有了初步的理解了吧,举一个例子来说明 HMM 的应用场景:

 

小明每天穿的服装为 , 假设小明穿的服装与前一天穿的服装是相互独立的,且服装的选择受精神状态的影响,当天的精神状态受到前一天精神状态的影响,精神状态为 , 已知观察序列 , 求对应的精神状态序列,这类问题我们可以用HMM来解决。

 

介绍到这里,相信大家对 HMM 的基本概念和应用场景有了一定的概念, 如果对 HMM 还不是很理解的话,先别慌,下面循环渐进的介绍 HMM ,数学要求不高的人也能很好的理解 。

 

1. 概率与随机过程的区别

 

概率是反映随机事件发生的可能性,大学课程《概率论与数理统计》全文内容是基于概率介绍的。若随机事件发生的概率随时间而改变,我们在考虑时间因素或空间因素的情况下去分析随机事件发生的概率,称为随机过程。

 

若我们每次抛掷硬币且正面向上的概率为0.5,正面向上的概率不随抛掷次数而改变,我们可以用概率来描述这一事件,如 P(X) ,其中 X 表示硬币正面向上的随机事件。

 

若我们每次抛掷硬币,硬币落在地上会导致形状的改变,正面向上的概率随抛掷次数的改变而改变,我们用随机过程来描述这一事件,如 ,其中 表示第i次抛掷硬币正面向上的随机事件。笼统的讲, 概率是分析一个随机变量,而随机过程是分析一组随机变量。

 

2. 马尔科夫过程的概念

 

当随机过程的变量满足马尔科夫性的无记忆性质时,则称为马尔科夫过程。

 

我们定义 为第i个时刻的随机变量,如下图的随机过程:

 

 

若随机变量满足:

 

上式的含义为t时刻的随机变量只依赖于 t-1 时刻的随机变量,与其他时刻无关,则称该过程为马尔科夫过程。

 

3. 马尔科夫模型与隐马尔科夫模型的区别

 

马尔科夫模型与隐马尔科夫模型的区别在于是否含有隐变量,本节还是用小明穿服装的例子来形象的说明马尔科夫模型与隐马尔可夫模型的区别:

 

若小明每天的服装只受到前一天所穿服装的影响, 下图为小明最近N天所穿服装的序列:

 

 

由上节介绍可知服装序列为马尔科夫过程,基于马尔科夫过程的统计模型则称为马尔科夫模型。

 

若小明每天的服装与前一天所穿服装是相互独立的,且每天所穿的服装是受到当天的精神状态影响,精神状态符合马尔科夫链原理,令服装序列为 , 精神状态序列为 , 用下图描述这一过程:

 

 

其中服装序列是可观测序列且观测变量是相互独立的,精神状态序列是不可观测序列(隐变量)且状态变量符合马尔科夫模型,基于上述过程的统计模型称为隐马尔科夫模型。

 

4. 隐马尔科夫模型参数介绍

 

由上节介绍可知,隐马尔科夫模型包含了观测序列和未观测的状态序列,其中状态序列由初始状态概率向量π和状态转移概率矩阵 A 决定,观测序列由观测概率矩阵 B 决定。

 

还是用小明作为例子,假设小明可选的服装为三件,分别为 。 小明的精神状态有两种,分别为

 

因此状态转移概率矩阵A表示为:

 

 

其中,

 

 

是在时刻t处于状态 的条件下在时刻t+1转移到 的概率。

 

观测概率矩阵B表示为:

 

 

其中,

 

 

是在时刻t处于状态 的条件下生成观测 的概率。

 

初始状态概率向量 表示为:

 

 

其中,

 

 

是时刻t=1处于状态 的概率。

 

我们用参数λ表示隐马尔科夫模型参数,即:

 

 

A, B ,π称为隐马尔可夫模型的三要素。

 

5. 隐马尔可夫模型参数求解算法

 

上节我们介绍了隐马尔可夫模型参数的含义,如何仅通过观测序列 ,求解模型参数 。

 

我们知道隐马尔可夫过程包含了隐变量 I,那幺隐马尔可夫模型事实上是一个含有隐变量的概率模型:

 

 

当构建包含隐变量的模型参数时,我们首先想到用EM(期望最大值)算法实现,算法可参考文章( 一文让你完全入门EM算法

 

模型参数求解步骤:

 

1)初始化隐马尔可夫模型参数

 

2) 确定模型完全数据的对数似然函数,隐马尔可夫模型的完全数据包含了观测数据

 

和隐数据 ,完全数据是

 

因此完全数据的对数似然函数为:

 

3) EM算法的 E 步,即求完全对数似然函数下隐变量的期望,称为 Q 函数

 

有:

 

 

其中 是隐马尔科夫模型的当前估计值, 是马尔科夫模型参数。

 

根据上节介绍的隐马尔可夫模型参数的含义,完全数据的似然函数可展开为:

 

因此Q函数 可写成:

 

 

4) EM算法的 M 步,求 Q 函数的最大值,得到模型参数,由上节可知模型参数

 

 

即令:

 

 

 

 

约束条件为初始状态概率分布的和等于1,即:

 

 

状态已知的情况下,观测概率分布的和等于1,即:

 

 

由上面的等式得到模型参数 , 即更新了模型参数的值。具体计算过程这里不再详细描述了,具体可参考李航老师的《统计学习方法》,若有不懂欢迎交流。

 

5) 重复步骤(3)( 4 ),直到函数 收敛,得到最终的模型参数

 

6.观测序列概率计算算法

 

上一节介绍了如何通过观测序列去估计模型参数,当模型参数已知时,隐马尔可夫模

 

型也相应的确定了,观测序列的概率可以通过模型参数计算出来。下面介绍两种观测序列概

 

率计算算法:

 

1 )枚举法

 

给定模型 和观测序列 , 计算观测序列O出现的概率 。 假设状态序列 , 可能的状态数是N,因此每个观测变量都可能由N个状态生成,且模型参数已知,我们就能算出每个可能的状态序列生成观测序列的概率。如下图:

 

 

这种列举所有可能的状态数来计算观测序列的概率理论上是可行的,但是计算量非常大,如上图对于长度为T的观测序列,复杂度达到了

 

2)递推法

 

隐马尔科夫具有时间序列的特点,因此我们可以用递推的方法去计算观测序列出现的概率。 给定马尔科夫模型 ,定义到时刻t部分观测序列为 且状态为 的 前向概率为

 

 

1)时刻 t=1 时刻的观测概率为:

 

 

2)递推,对于 ,有:

 

 

3) 当t=T时,

 

 

算法复杂度研究:因为该算法考虑的是用递推关系求观测序列的概率,递推过程如下图:

 

 

方程表示为:

 

 

由上式可知,计算 t+1 时刻状态为  i  的计算量为 N 次相乘求和,且 t+1 时刻状态的可能数为 N , 因此由t时刻递推到 t+1 时刻的计算量为   阶,观测序列的长度为T,那幺计算量为 阶,与之前枚举法相比,计算量大大降低了。

 

7. 状态序列预测算法

 

给定模型参数   和观测序列 , 如何预测最有可能的状态序列,这是隐马尔科夫模型的应用最广的场景,如词性标注,给定一个句子,标注每个单词的特性;

 

本节介绍维特比算法(Viterbi algorithm)来预测状态序列。维特比算法是一种动态规划算法,用于寻找最有可能产生的状态序列。

 

通过节点

 

算法的核心思想是 :若 t 时刻最有可能的状态序列 通过节点 ( 为t时刻的状态 ), 那幺从t时刻到 T 时刻的最优路径一定包括。我们利用这一思想确定了最优状态序列的最后一个时刻的状态 , 然后利用该状态回溯时刻 的最优状态。用一个例子说明维特比算法:

 

已知模型 , 观测集合V={红,白 } ,状态集合 Q={1 , 2 , 3} ,其中

 

 

若观测序列O=(红,白,红 ) ,求最优状态序列

 

解:定义 为时刻t状态为  i  的所有单个路径 中概率的最大值,含义为给定前t-1时刻的状态和前 t 时刻的观测序列,求最优路径 t 时刻的状态,即:

 

定义 为时刻t状态为  i  的所有单个路径 中概率最大路径的第t-1个节点为:

 

 

根据维特比算法的核心思想,我们计算观测序列下的最优路径:

 

1) t=1 时,令 是观测为 状态为i的概率,由题目可知为红色,有:

 

代入已知条件得:

 

 

 

2) t=2 时,

 

 

由上面两式得:

 

 

 

2) t=3 时,

 

 

得:

 

 

以 表示最优路径的概率,最优路径的终点 :

 

 

 

因此最优状态序列:

 

 

8.小结

 

本文首先用一个例子通俗的讲解了隐马尔可夫模型的适用场景以及隐马尔可夫模型的三个主要处理问题,然后循序渐进的介绍了隐马尔可夫模型的概念和相关问题的解决方法,所用的例子选取了《统计学习方法》的内容。后续文章会介绍另一种相似的算法——条件随机场以及两者的区别,希望对初学者能有所帮助。

Be First to Comment

发表评论

邮箱地址不会被公开。 必填项已用*标注