揭秘马尔可夫模型神秘面纱4

1维特比算法解决HMM解码

维特比算法原理

维特比算法解决:问题2(解码问题):给定一个观察序列O和一个HMM λ=(A,B),找出最好的隐藏状态序列Q。

解码:使HMM这种包含隐藏变量的模型中,确定隐藏在某个观察序列后面变量序列的工作,叫做解码。

形式化描述:给定一个HMMλ=(A,B)和一个观察序列

作为输入,找出概率最大的状态序列

就是解码。

思想:使用前面算法找到隐藏在观察序列之后最好的状态序列,对于每个可能的隐藏状态序列,运用向前算法选出观察序列对隐藏序列的最大似然度的隐藏状态序列,从而完成解码工作,算法复杂度

,当状态序列很大时,指数级增长,计算量过大,由此采用一种动态规划算法降低算法复杂度:维特比算法。

解码:使HMM这种包含隐藏变量的模型中,确定隐藏在某个观察序列后面变量序列的工作,叫做解码 。

2 维特比算法实例解读

实例

例子:通过吃冰淇淋数量(观察序列状态)计算隐藏状态空间的最佳路径(维特比网格)如下:

其中:

:在时间步t的观察状态下,隐藏状态j的概率。

维特比(Viterbi)算法

Viterbi算法思想:按照观察序列由左向右顺序,每个

表示自动机λ,HMM在看了头t个观察并通过了概率最大的状态序列

之后,在状态j的概率,每个 的值递归计算,并找出最大路径。

Viterbi算法形式化描述:每一个单元表示如下概率:

V的计算公式如下:

在时刻t-1的时候使用扩充前面路径的方法计算维特比概率,计算时,把下面3个因素相乘:

案例分析

给定一个HMMλ=(A,B),HMM把最大似然度指派给观察序列,算法返回状态路径,从而找到最优的隐藏状态序列。上图是小明夏天吃冰淇淋‘3 1 3’,据此使用Viterbi算法推断最可能出现的天气状态(天气的热|冷)。

1)计算时间步1的维特比概率

计算时间步t=1和状态1的概率:

路径:start--C

计算时间步t=1和状态2的概率:

路径:start—H 较大

2)计算时间步2的维特比概率,在(1) 基础计算

计算时间步t=2和状态1的概率:

路径:start—H—C 较大

计算时间步t=2和状态2的概率:

路径:start—H--H

3)计算时间步3的维特比概率,在(2) 基础计算

计算时间步t=3和状态1的概率:

路径:start—H—C —C

计算时间步t=3和状态2的概率:

路径:start—H—C—H 较大

4)维特比反向追踪路径

路径为:start—H—C---H

综上所述可知:利用Viterbi算法我们知道小明夏天某天吃冰淇淋的观察值(3 1 3)推断出天气为(热 冷 热)。这也符合事实,天热吃3根,天冷吃一根。

维特比算法与向前算法的区别:

(1)维特比算法要在前面路径的概率中选择最大值,而向前算法则计算其总和,此外,维特比算法和向前算法一样。

(2)维特比算法有反向指针,寻找隐藏状态路径,而向前算法没有反向指针。

3 HMM和Viterbi解决词类标注

词类标注

上面例子根据小明吃冰淇淋成功推断出天气事件,但是读者不免意犹未尽,那么下面利用同样方法进行词类标注。在随机词类标注算法中,单词是观察序列,相当于冰淇淋的数量。词类标记是隐藏状态,相当于天气的热冷。因此可以进行随机词类标注如下:

对于一个给定的句子或者单词序列,我们使用HMM词类标注算法来选择使用下面公式为最大值标记序列:

在进行词类标注时,句子“Secretariat is expected to race tomorrow”中的race是一个动词VB或者名词NN,它可以标注VB也可以标注NN,我们利用Viterbi算法解决:

根据HMM标注算法的公式可知,选择概率比较大的一个作为race的标记。P(VB|TO)*P(race|VB) 和P(NN|TO)*P(race|NN) 两者最大值即race的标记。

假设转移概率已知为:

P(NN|TO)=0.021

P(VB|TO)=0.34

假设词汇的发射概率即似然度也是知道的:

P(race|NN)=0.00041

P(race|VB)=0.00003

我们把标记序列概率和词汇发射概率相乘得到以下结果:

P(VB|TO)*P(race|VB) = 0.034*0.00003=0.00001

P(NN|TO)*P(race|NN) =0.021*0.00041=0.000007

因此,我们把race的标记确定为VB,这就是正确的词类标记结果,本质上采用统计模型的方法。当然真正使用时,我们根据需求对整个句子或者整段话以至于整篇文章进行标注,原理是一样的。

4 维特比算法描述

Viterbi算法伪码

5 Viterbi解决中文句法标注

1 对文本数据清洗的预处理操作。代码略

2 对清洗后的文本,采用有监督方法对古文献BIO标记(B表示句子开始I表示句子中间O表示句子结尾)代码略

3 统计文本的转移矩阵B。 代码略

4 统计文本的发射矩阵A。 代码略

5 维特比解码算法找出观察序列O的最后的隐藏状态序列Q

5.1 隐马尔可夫模型中维特比解码算法序列标注

String observationStr="病有发热恶寒者;发于阳也,无热恶寒者;发于阴也。";//观察序列 String[] states={"B","I","O"};//状态序列 double start_probability=0.3333;//初始状态概率 String str="书名:伤寒论。作者:张仲景。朝代:东汉。"; String stateStr=MethodUilt.Vitrerbi(str, start_probability, Amatrixpath, Bmatrixpath);//隐藏状态序列,即隐含马尔科夫模型的词类标注 System.out.println("观察序列:\t"+str.replaceAll("", "\t")+"\n标注序列:\t\t"+stateStr);

5.2 针对马尔科夫模型中第二个问题,采用维特比算法进行句子标注,其中主要还是动态规划思想

/** * 针对马尔科夫模型中第二个问题,采用维特比算法进行句子标注,其中主要还是动态规划思想 * @param observationStr 观察序列 * @param states 状态序列 * @param start_probability 初始化状态,即π * @param Amatrixpath 发射矩阵路径 * @param Bmatrixpath 转移矩阵路径 * start_probability, transititon_probability, emission_probability * @return */

6 实验结果:

6 参考文献

  1. 统计自然语言处理基础 Christopher.Manning等 著 宛春法等 译
  2. 自然语言处理简明教程 冯志伟 著
  3. 数学之美 吴军 著
  4. Viterbi算法分析文章 王亚强

文末:文章来源机器学习和自然语言处理(ID:datathinks),作者:机器学习和自然语言处理。本公众号旨在技术传播与分享,未经授权不能转载发布。

原文发布于微信公众号 - 机器学习和自然语言处理(datathinks)

原文发表时间:2017-09-21

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小小挖掘机

残差网络ResNet网络原理及实现

论文地址:https://arxiv.org/pdf/1512.03385.pdf

3633
来自专栏数据派THU

一文读懂支持向量积核函数(附公式)

来源:jerrylead 本文通过多个例子为你介绍支持向量积核函数,助你更好地理解。 核函数(Kernels) 考虑我们最初在“线性回归”中提出的问题,特征是房...

73714
来自专栏自然语言处理

谈谈学习模型的评估2

评估度量:(其中P:正样本数 N:负样本数 TP:真正例 TN:真负例 FP:假正例 FN:假负例)

812
来自专栏大数据挖掘DT机器学习

比较R语言机器学习算法的性能

原文:Compare The Performance of Machine Learning Algorithms in R 译文:http://g...

3486
来自专栏数据科学与人工智能

【Python环境】Python分类现实世界的数据

引入 一个机器可以根据照片来辨别鲜花的品种吗?在机器学习角度,这其实是一个分类问题,即机器根据不同品种鲜花的数据进行学习,使其可以对未标记的测试图片数据进行分类...

3046
来自专栏AI研习社

深度学习岗位面试问题一览

本笔记主要问题来自以下两个问题,以及我自己面试过程中遇到的问题。 深度学习相关的职位面试时一般会问什么?会问一些传统的机器学习算法吗?(http://t.cn/...

6705
来自专栏腾讯技术工程官方号的专栏

机器学习在HEVC 视频编码中的实践

背景与目标 当前视频编码中应用最广泛的是AVC(H.264),而HEVC(H.265)作为下一代的视频编码算法,在压缩性能上可以再节省40%的码率,优势很明显,...

3428
来自专栏企鹅号快讯

详解各种随机算法

转自:JarvisChu 之前将的算法都是确定的,即对于相同的输入总对应着相同的输出。但实际中也常常用到不确定的算法,比如随机数生成算法,算法的结果是不确定的,...

5989
来自专栏Hadoop数据仓库

HAWQ + MADlib 玩转数据挖掘之(十二)——模型评估之交叉验证

一、交叉验证概述         机器学习技术在应用之前使用“训练+检验”的模式,通常被称作“交叉验证”,如图1所示。 ? 图1 1. 预测模型的稳定性    ...

1.7K7
来自专栏marsggbo

DeepLearning.ai学习笔记(四)卷积神经网络 -- week2深度卷积神经网络 实例探究

一、为什么要进行实例探究? 通过他人的实例可以更好的理解如何构建卷积神经网络,本周课程主要会介绍如下网络 LeNet-5 AlexNet VGG ResNet ...

2358

扫码关注云+社区

领取腾讯云代金券