专栏首页深度学习自然语言处理哈工大学习笔记 | 图文并茂详解隐马尔可夫模型

哈工大学习笔记 | 图文并茂详解隐马尔可夫模型

作者:哈工大SCIR硕士生 乐远

来自:哈工大SCIR

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

说到隐马尔可夫模型(HMM),我们先来了解下马尔可夫模型(Markov模型),Markov模型是一种统计模型,广泛地应用在语音识别,词性自动标注,音字转换,概率文法等各个自然语言处理的应用领域。

一. 马尔可夫模型(Markov模型)

是随机变量序列,其中每个随机变量的取值在有限集

,称为状态空间。Markov特征是

  • 有限历史假设
  • 时间不变性

如果

具有这些特征,那么这个随机变量序列称为一个马尔可夫过程(链)。

Markov的形式化表示:一个马尔可夫模型是一个三元组

,其中

是状态的集合,

是初始状态的概率,

是状态间的转移概率。具体例子用图形表示如下,

相应的

分别是,

隐马尔可夫模型与马尔可夫模型不同的是各个状态(或者状态转移弧)都有一个输出,但是状态是不可见的

最简单的情形:不同的状态只能有不同的输出,

增加一点灵活性:不同的状态,可以输出相同的输出,

再增加一点灵活性:输出在状态转移中进行,

最大的灵活性:在状态转移中以特定的概率分布输出,

这就得到了我们要讲的隐马尔可夫模型。

二. 隐马尔可夫模型(HMM)

1.HMM的形式化定义

HMM是一个五元组

,其中

是状态的集合,

是输出字符的集合,

是初始状态的概率,

是状态转移的概率,

是状态转移时输出字符的概率。

一个HMM的例子用图形表示如下,

2. 隐马尔可夫模型的三个基本问题

  • 评估问题:给定一个模型

,如何高效地计算某一输出字符序列的概率

  • 解码问题:给定一个输出字符序列

,和一个模型

,如何确定产生这一序列概率最大的状态序列

  • 学习问题:给定一个输出字符的序列

,如何调整模型的参数使得产生这一序列的概率最大?

3. 评估问题的解法

已知

,计算

我们先来化简一下

  • 方案一:直接计算法

穷举所有可能的

的情况,求和得到

,但是时间复杂度太高,为

  • 方案二:前向算法(Forward algorithm)

使用动态规划使得算法更高效,定义一个前向变量表示到时刻

部分观测序列为

且状态为

的概率为向前概率,记为

,即

则可以递推得到,

前向过程算法如下,

一个简单的前向过程例子如下,

  • 方案三:向后算法(backward algorithm)

同样的道理,我们定义在时刻

状态为

的条件下,从

的部分观测序列为

的概率为后向概率,记作

,即

直接采用递推即可得到后向算法。

后向算法过程如下,

  • 1. 初始化

  • 2. 推导
  • 3. 总和

4. 解码问题的解法

给定一个输出字符序列

,和一个模型

,如何确定产生这一序列概率最大的状态序列?

我们定义

表示为在

时刻到达状态

,输出字符

时,输出前面

个字符的最可能路径的概率,

则有

这样我们就得到了维特比算法(Viterbi Algorithm),算法过程如下:

一个简单的viterbi算法举例如下,

5. 学习问题解法

给定一个输出字符的序列

,如何调整模型的参数使得产生这一序列的概率最大?

隐马尔可夫模型的学习,根据训练数据是包括观测数据和对应的状态序列还是只有观测序列,可以分为有监督学习和无监督学习,其中无监督的学习即是利用EM算法思想的Baum-Welch算法。

  • 方案一:有监督学习

假设训练数据包含

个长度相同的观测序列和对应的状态序列

,那么可以利用极大似然估计法来估计隐马尔可夫模型的参数

,具体估计方法如下:

  • 1. 转移概率

的估计

设样本中时刻

处于状态

时刻

处于状态

的频数为

,那么状态转移概率

的估计是

  • 2. 观测概率

的估计

设样本中状态为

并观测为

的频数是

,那么状态为

观测为

的概率

的估计是

  • 3. 初始状态概率

的估计

个样本中初始状态为

的概率

由于监督学习的方法需要使用训练数据,而人工标注的代价往往很高,有时会采用非监督学习的方法。

  • 方案二:无监督学习——Baum-Welch算法

假设给定的训练数据只包含

个长度为

的观测序列而没有对应的状态序列

,目标是学习隐马尔可夫模型

的参数。我们将观测序列数据看做观测数据

,状态序列数据看做不可观测数据

,那么隐马尔可夫模型事实上是一个包含隐变量的概率模型

它的参数学习可以由EM算法实现。

(算法推导过程)

(1) 确定完全数据的对数似然函数 所有观测数据写成

,所有的隐数据写成

,完全数据是

。完全数据的对数似然函数是

。 (2) EM算法的E步:求

函数的

其中

是隐马尔可夫模型参数的当前估计值,

是要极大化的隐马尔可夫模型参数。因为,

所以

函数可以拆分写成

式中求和都是对所有训练数据的序列总长度

进行的。 (3) EM算法的M步:极大化

函数

,求模型参数

。 由于要极大化的参数在

函数式子中单独的出现在三个项中,所以只需要对各项分别极大化。第一项可以写成,

注意到

满足

,利用拉格朗日乘子法,写出拉格朗日函数

对其求导数并令结果为0,

得到

求和得到

,

再代入上式子得到,

第二项可以写成

类似于第一项,利用具有约束条件

的拉格朗日乘子法恶意求出

第三项可以写成,

同样利用拉格朗日乘子法,约束条件是

,注意只有在

的偏导数才不为0,以

表示,得到,

----- 为了简便,我们使用一下式子简化, 给定模型

和观测

,在时刻

处于状态

的概率记

有如下公式:

给定模型

和观测

,在时刻

处于状态

的概率记 :

有如下推倒:

我们结合上文以及EM算法可以推导如下公式

Baum-Welch算法过程:

输入:观测数据

输出:隐马尔可夫模型参数

1. 初始化。对

,选取

得到模型

2. 递推。对

3. 终止。得到模型参数


参考资料

[1]公式参考李航《统计学习方法》

[2]图片选自哈尔滨工业大学关毅教授《自然语言处理》课程PPT

本期责任编辑:丁 效

本期编辑:刘元兴

本文分享自微信公众号 - 深度学习自然语言处理(zenRRan)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-04-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 时间序列分析及应用--模型诊断

    最近忙着考证和学习专业课,还要帮导师做一个小项目,时间好紧张,感觉很久没有更新了,这是我们上时间序列分析要交的作业,大家相互交流学习。

    统计学家
  • Python机器学习资源菜单,选库找工具不愁,吐血整理!

    来源商业新知网,原标题:Python机器学习资源菜单,选库找工具不愁,GitHub精选列表都在这里了

    商业新知
  • 【彩票】白话贝叶斯理论及在足球比赛结果预测中的应用

    贝叶斯是一名1702年出生于伦敦的英国数学家,他首先将归纳推理法用于概率论基础理论,并创立了贝叶斯统计理论,对于统计决策函数、统计推断、统计的估算等做出了贡献...

    统计学家
  • 【2015-9-6学习笔记】贝叶斯统计和金融市场

    上午上了四节课,全是《贝叶斯统计》,贝叶斯学派和频率学派一直论战不断,焦点就在于先验分布的问题,百度百科有云:先验分布是总体分布参数θ的一个概率分布。贝叶斯学派...

    统计学家
  • 【R语言进行数据挖掘】决策树和随机森林

    这一节学习使用包party里面的函数ctree()为数据集iris建立一个决策树。属性Sepal.Length(萼片长度)、Sepal.Width(萼片宽度)、...

    统计学家
  • 【温习统计学】曼-惠特尼U检验

    曼-惠特尼U检验又称“曼-惠特尼秩和检验”,是由H.B.Mann和D.R.Whitney于1947年提出的。它假设两个样本分别来自除了总体均值以外完全相同的两个...

    统计学家
  • 《spss统计分析与行业应用案例详解》时间序列分析(上)----实例38 39

    预处理是指定义时间序列和对时间序列平稳化处理。他是进行时间序列分析前必须进行的一个环节,因为SPSS无法自动识别时间序列数据并且在处理的过程中必须明确考虑时间序...

    统计学家
  • 【温习统计学】方差分析的三种模型

    固定效应模型,表示你打算比较的就是你现在选中的这几组。例如,我想比较3种药物的疗效,我的目的就是为了比较这三种药的差别,不想往外推广。这三种药不是从很多种药中抽...

    统计学家
  • R in action读书笔记(19)第十四章 主成分和因子分析

    主成分分析(PCA)是一种数据降维技巧,它能将大量相关变量转化为一组很少的不相关变量,这些无关变量称为主成分。探索性因子分析(EFA)是一系列用来发现一组变量的...

    统计学家
  • Duke@coursera 数据分析与统计推断 unit4 inference for numerical variables

    estimating the difference between pairedmeans:

    统计学家

扫码关注云+社区

领取腾讯云代金券