【NLP】揭秘马尔可夫模型神秘面纱系列文章（五）

2016-07-11 609

向前向后算法解决隐马尔可夫模型机器学习问题

2016年7月12日14:28:10

摘要：最早接触马尔可夫模型的定义源于吴军先生《数学之美》一书，起初觉得深奥难懂且无什么用场。直到学习自然语言处理时，才真正使用到隐马尔可夫模型，并体会到此模型的妙用之处。马尔可夫模型在处理序列分类时具体强大的功能，诸如解决：词类标注、语音识别、句子切分、字素音位转换、局部句法剖析、语块分析、命名实体识别、信息抽取等。另外广泛应用于自然科学、工程技术、生物科技、公用事业、信道编码等多个领域。本文写作思路如下：第一篇对马尔可夫个人简介和马尔科夫链的介绍；第二篇介绍马尔可夫链（显马尔可夫模型）和隐马尔可夫模型以及隐马尔可夫模型的三大问题（似然度、编码、参数学习）；第三至五篇逐一介绍三大问题相关算法：（向前算法、维特比算法、向前向后算法）；最后非常得益于冯志伟先生自然语言处理教程一书，冯老研究自然语言几十余载，在此领域别有建树。（本文原创，转载注明出处：向前向后算法解决隐马尔可夫模型机器学习问题 )

马尔可夫个人简介

安德烈·马尔可夫，俄罗斯人，物理-数学博士，圣彼得堡科学院院士，彼得堡数学学派的代表人物，以数论和概率论方面的工作著称，他的主要著作有《概率演算》等。1878年，荣获金质奖章，1905年被授予功勋教授称号。马尔可夫是彼得堡数学学派的代表人物。以数论和概率论方面的工作著称。他的主要著作有《概率演算》等。在数论方面，他研究了连分数和二次不定式理论，解决了许多难题。在概率论中，他发展了矩阵法，扩大了大数律和中心极限定理的应用范围。马尔可夫最重要的工作是在1906～1912年间，提出并研究了一种能用数学分析方法研究自然过程的一般图式——马尔可夫链。同时开创了对一种无后效性的随机过程——马尔可夫过程的研究。马尔可夫经多次观察试验发现，一个系统的状态转换过程中第n次转换获得的状态常取决于前一次（第（n-1）次）试验的结果。马尔可夫进行深入研究后指出：对于一个系统，由一个状态转至另一个状态的转换过程中，存在着转移概率，并且这种转移概率可以依据其紧接的前一种状态推算出来，与该系统的原始状态和此次转移前的马尔可夫过程无关。马尔可夫链理论与方法在现代已经被广泛应用于自然科学、工程技术和公用事业中。

1 向前向后算法概述

向前向后算法解决：问题3（学习问题）：给定一个观察序列O和一个HMM中的状态集合，自动学习HMM的参数A和B。

此算法涉及机器学习，较为复杂，笔者不打算深入讲解，感兴趣的同学可以参考冯志伟《自然语言处理简明教程》P594—602，本文只是做为了解方面讲解。

鲍姆-韦尔奇算法（Baum-Welch algorithm）：训练HMM的标准算法是向前向后算法，这是期望最大化算法或者叫鲍姆-韦尔奇算法，这个算法帮助我们训练HMM的转移概率B和发射概率A。

鲍姆-韦尔奇算法思路：

（1）反复的估计所得的计数，从转移概率和观察概率的一个估计值开始，反复的使用这些估计概率来推出越来越好的概率。

（2）对于一个观察，计算它向前概率，从而得到我们估计的概率。然后把这个估计的概率量，在对于这个向前概率有贡献的所有不同路径上进行分摊。

向后概率：向后概率记住 β是对于给定自动机 λ，在状态i和时刻t观察下一个时刻t+1到终点的观察概率，用公式表示如下：

计算向前概率相似的归纳法来计算向后概率：

2 向后归纳的步骤

3 计算在时刻t和状态j的向后概率：公式较多，采用笔记如下

4 算法推导过程：公式较多，笔记如下

5 迭代向前向后算法核心：

6 参考文献

【1】统计自然语言处理基础 Christopher.Manning等著宛春法等译

【2】自然语言处理简明教程冯志伟著

【3】数学之美吴军著

【4】Viterbi算法分析文章王亚强

声明：关于此文各个篇章，本人采取梳理扼要，顺畅通明的写作手法。一则参照相关资料二则根据自己理解进行梳理。避免冗杂不清，每篇文章读者可理清核心知识，再找相关文献系统阅读。另外，要学会举一反三，不要死盯着定义或者某个例子不放。诸如：此文章例子冰淇淋数量（观察值）与天气冷热（隐藏值）例子，读者不免问道此有何用？我们将冰淇淋数量换成中文文本或者语音（观察序列），将天气冷热换成英文文本或者语音文字（隐藏序列）。把这个问题解决了不就是解决了文本翻译、语音识别、自然语言理解等等。解决了自然语言的识别和理解，再应用到现在机器人或者其他设备中，不就达到实用和联系现实生活的目的了？本文原创，转载注明出处：向前向后算法解决隐马尔可夫模型机器学习问题

http://www.cnblogs.com/baiboy

微信关注我们

原文链接：https://yq.aliyun.com/articles/628343

转载内容版权归作者及来源网站所有！

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

【NLP】揭秘马尔可夫模型神秘面纱系列文章（四）

维特比算法解决隐马尔可夫模型解码问题（中文句法标注）作者：白宁超 2016年7月12日14:08:28 摘要：最早接触马尔可夫模型的定义源于吴军先生《数学之美》一书，起初觉得深奥难懂且无什么用场。直到学习自然语言处理时，才真正使用到隐马尔可夫模型，并体会到此模型的妙用之处。马尔可夫模型在处理序列分类时具体强大的功能，诸如解决：词类标注、语音识别、句子切分、字素音位转换、局部句法剖析、语块分析、命名实体识别、信息抽取等。另外广泛应用于自然科学、工程技术、生物科技、公用事业、信道编码等多个领域。本文写作思路如下：第一篇对马尔可夫个人简介和马尔科夫链的介绍；第二篇介绍马尔可夫链（显马尔可夫模型）和隐马尔可夫模型以及隐马尔可夫模型的三大问题（似然度、编码、参数学习）；第三至五篇逐一介绍三大问题相关算法：（向前算法、维特比算法、向前向后算法）；最后非常得益于冯志伟先生自然语言处理教程一书，冯老研究自然语言几十余载，在此领域别有建树。（本文原创，转载注明出处：维特比算法解决隐马尔可夫模型解码问题（中文句法标注） ) 目录【自然语言处理：马尔可夫模型（一）】：初识马尔可夫和马尔可夫链【自然语言...

2016-07-12

505

统计角度窥视模型概念作者：白宁超 2016年7月18日17:18:43 摘要：写本文的初衷源于基于HMM模型序列标注的一个实验，实验完成之后，迫切想知道采用的序列标注模型的好坏，有哪些指标可以度量。于是，就产生了对这一专题进度学习总结，这样也便于其他人参考，节约大家的时间。本文依旧旨在简明扼要梳理出模型评估核心指标，重点达到实用。本文布局如下：第一章采用统计学习角度介绍什么是学习模型以及如何选择，因为现今的自然语言处理方面大都采用概率统计完成的，事实证明这也比规则的方法好。第二章采用基于数据挖掘的角度探讨模型评估指标和选择。第三章采用统计自然语言处理的方法看看模型评价方法。第四章以R语言为实例，进行实战操作，更深入了解模型的相关问题。（本文原创，转载请注明出处：统计角度窥视模型概念。) 目录【自然语言处理：谈谈学习模型的评估（一）】：统计角度窥视模型概念【自然语言处理：谈谈学习模型的评估（二）】：基于Data Mining角度的模型评估与选择【自然语言处理：谈谈学习模型的评估（三）】：基于NLP角度的模型评价方法【自然语言处理：谈谈学习模型的评估（四）】：基于R语言的模型案例...

2016-07-18

553

资源下载

更多资源

Mario

马里奥是站在游戏界顶峰的超人气多面角色。马里奥靠吃蘑菇成长，特征是大鼻子、头戴帽子、身穿背带裤，还留着胡子。与他的双胞胎兄弟路易基一起，长年担任任天堂的招牌角色。

腾讯云软件源

为解决软件依赖安装时官方源访问速度慢的问题，腾讯云为一些软件搭建了缓存服务。您可以通过使用腾讯云软件源站来提升依赖包的安装速度。为了方便用户自由搭建服务架构，目前腾讯云软件源站支持公网访问和内网访问。

Spring

Spring框架（Spring Framework）是由Rod Johnson于2002年提出的开源Java企业级应用框架，旨在通过使用JavaBean替代传统EJB实现方式降低企业级编程开发的复杂性。该框架基于简单性、可测试性和松耦合性设计理念，提供核心容器、应用上下文、数据访问集成等模块，支持整合Hibernate、Struts等第三方框架，其适用范围不仅限于服务器端开发，绝大多数Java应用均可从中受益。

Rocky Linux

Rocky Linux（中文名：洛基）是由Gregory Kurtzer于2020年12月发起的企业级Linux发行版，作为CentOS稳定版停止维护后与RHEL（Red Hat Enterprise Linux）完全兼容的开源替代方案，由社区拥有并管理，支持x86_64、aarch64等架构。其通过重新编译RHEL源代码提供长期稳定性，采用模块化包装和SELinux安全架构，默认包含GNOME桌面环境及XFS文件系统，支持十年生命周期更新。