漫谈马尔可夫模型

马尔可夫简介

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

马尔可夫链的基本概念

序列分类器

序列分类器或序列标号器是给序列中的某个单元指派类或者标号的模型。马尔可夫模型（又叫显马尔可夫模型VMM）和隐马尔可夫模型（HMM）都是序列分类器。诸如词类标注、语音识别、句子切分、字素音位转换、局部句法剖析、语块分析、命名实体识别、信息抽取等都属于序列分类。

随机过程的两层含义

• 随机过程是一个时间函数，其随着时间变化而变化；
• 随机过程在每个时刻上的函数值是不确定的、随机的，即每个时刻上函数值按照一定的概率进行分布。

独立链

随机过程中各个语言符号或者词是独立的、不相互影响，则称这种链是独立链。反之，各语言词或者符号彼此有关则是非独立链。

等概率独立链与非等概率独立链

在独立链中，各个语言符号或者词是等概率出现的是等概率独立链，各个语言词或者语言符号是非等概率出现的则为非等概率链。

马尔可夫链

• 马尔可夫过程：在独立链中，前面语言符号对后面的语言符号无影响，是无记忆没有后效的随机过程。在已知当前状态下，过程的未来状态与它的过去状态无关，这种形式就是马尔可夫过程。

• 马尔可夫链：在随机过程中，每个语言符号的出现概率不相互独立，每个随机试验的当前状态依赖于此前状态，这种链就是马尔可夫链。

  链的解析：链可以当做一种观察序列，诸如：“2016年是建党95周年”，就可以看成是一个字符串链。其中如果上述字符串中每个字符出现是随机、独立的就是独立链，如果每个字符出现与前面字符相关，即不独立并具有依赖性，我们称之为马尔可夫链。

• N元马尔可夫链：

  考虑前一个语言符号对后一个语言符号出现概率的影响，这样得出的语言成分的链叫做一重马尔可夫链，也是二元语法。

  考虑前两个语言符号对后一个语言符号出现概率的影响，这样得出的语言成分的链叫做二重马尔可夫链，也是三元语法。

  考虑前三个语言符号对后一个语言符号出现概率的影响，这样得出的语言成分的链叫做三重马尔可夫链，也是四元语法。

  类似的，考虑前（4,5，….,N-1）个语言符号对后一个语言符号出现概率的影响，这样得出的语言成分的链叫做（4,5，….,N-1）重马尔可夫链，也是（5，6，….,N）元语法。

有限自动机

马尔可夫链在数学上描述了自然语言句子的生成过程，是一个自然语言形式的早期模型。后来N元语法的研究，都是建立在马尔可夫模型的基础之上的。马尔可夫链和隐马尔可夫模型都是有限自动机（状态集合状态之间的转移集）的扩充。

加权有限状态机

加权有限状态机中每个弧与一个概率有关，这个概率说明通过这个弧的可能性，且某一个点出发的弧具有归一化的性质，即某点出发的弧概率之和为1。

注意：马尔可夫链不能表示固有歧义的问题，当概率指派没有歧义时，马尔可夫链才有用。

马尔可夫链描述

(1) 具有初始状态和终结状态的马尔可夫链描述如下表11-1所示：

表11-1 具有初始状态和终结状态的马尔可夫链 

(2) 没有初始状态和终结状态的马尔可夫链描述如下表11-2所示：

表11-2 没有初始状态和终结状态的马尔可夫链 

在一个一阶马尔可夫链中，我们假设一个特定的概率只与它前面一个状态有关，马尔可夫假设可以表示如下：

从一个状态i出发的所有弧的概率之和为1，即：

隐马尔可夫模型

形式化描述

爱依斯讷（Jason Eisner）对隐马尔可夫模型的描述

隐马尔可夫模型即一个隐藏马尔可夫链随机生成不可观察的随机序列，再由各个状态生成一个观测随机序列的过程。其中隐藏马尔可夫链随机生成的状态序列，称为状态序列；每个状态生成一个观测的随机序列，称为观测序列。序列的每个位置可以看成一个时刻，它可以被形式化的描述为一个五元组HMM= 。Jason Eisner对隐马尔可夫模型的描述如下表11-3所示：

表11-3 HMM形式化描述 

拉宾纳（Rabiner）关于隐马尔可夫模型思想的三个问题

问题1（似然度问题）：给一个HMM λ=（A,B） 和一个观察序列O，确定观察序列的似然度问题 P(O|λ) 。

问题2（解码问题）：给定一个观察序列O和一个HMM λ=（A,B），找出最好的隐藏状态序列Q。

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

根据隐马尔可夫模型的描述，可以将一个长度为T的观测序列的生成过程描述为下表11-4所示的算法：

表11-4 隐马尔可夫模型算法描述 

综上所述，一个已知的HMM模型由参数(N，T)、观测序列和三个概率(A，B，π )构成，下文皆用 =(A，B， π )表示完整HMM模型参数。

数学形式描述

在命名实体识别过程中，序列标注是一个重要的子任务。利用HMM模型去解决类似序列标注这样的问题，给定一个观测序列 ，为求得最佳标记序列为 ，要求条件概率 最大。由朴素贝叶斯公式可知：

在命名实体识别中， X 是给定的一个文本序列，文本粒度可以是一个句子或者一段话，待观测的值 到 为词，而P(X)对于所有类别都是一样的，可以看成是一个常量从而忽略不考虑。则上式可以简化为：

隐马尔可夫模型本质上就是求解联合概率。则由上式可得：

其中 给出了非独立假设情况下的求解命名实体识别的概率模型。命名实体识别任务就转化为求解 ，期望P(Y|X)值最大。

公式假设理想状态下的命名实体识别的概率模型，实际这种参数估计是不科学的。故而，我们给出上文提到两个独立假设：

(1) 马尔可夫假设

假设求解状态只是跟它前面的状态N-1有关即：

(2) 输出独立假设

一个输出观察 的概率只与产生该观察的状态 有关，而与其他状态无关即：

可知一阶HMM公式可以化简为：

其中， 为发射概率， 为转移概率。

向前算法解决HMM似然度

向前算法定义

向前算法的递归定义如表11-5所示：

表11-5 向前算法形式化描述 

向前算法原理

向前算法解决：问题1（似然度问题）：给一个HMM λ=（A,B） 和一个观察序列O，确定观察序列的似然度问题 P=(O|λ) 。对于马尔可夫链，表面观察和实际隐藏是相同的，只需要标记吃冰淇淋数目“3 1 3”的状态，并把加权（弧上）的对应概率相乘即可。而隐马尔可夫模型就不那么简单了，因为状态是隐藏的，所以我们并不知道隐藏的状态序列是什么。

简化下问题：假如我们知道天气冷热状况，并且知道小明吃冰淇淋的数量，然后我们去观察序列似然度。如：对于给定的隐藏状态序列“hot hot cold”我们来计算观察序列“3 1 3”的输出似然度。

如何进行计算？首先，隐马尔可夫模型中，每个隐藏状态只产生一个单独的观察即一一映射。隐藏状态序列与观察序列长度相同，即：给定这种一对一的映射以及马尔可夫假设，对于一个特定隐藏状态序列 以及一个观察序列 观察序列的似然度为：

故从隐藏状态“hot hot cold”到所吃冰淇淋观察序列“3 1 3”的向前概率为：

P(3 1 3|hot hot cold)=P(3|hot) P(1|hot) P(3|cold)=0.4 0.2 0.1=0.008

实际上，隐藏状态序列“hot hot cold”是我们的假设，因为我们并不知道隐藏状态序列，我们要考虑的是所有可能的天气序列。如此一来，我们将计算所有可能的联合概率，但这样的计算特别复杂。我们来计算天气序列Q生产一个特定的冰淇淋事件序列O的联合概率：

如果隐藏序列只有一个是“hot hot cold”，那么我们的冰淇淋观察“3 1 3”和一个可能的隐藏状态“hot hot cold”的联合概率为：

P(313|hot hot cold)=P(hot|start) P(hot|hot) P(hot|cold) P(3|hot) P(1|hot) P(3|cold)=0.8 0.7 0.30.4 0.2*0.1=0.001344

P(3 1 3)= P(313| cold cold cold)+ P(313| cold cold hot) + P(313| hot hot cold ) + P(313| cold hot cold) + P(313|hot cold cold) + P(313| hot hot hot) + P(313| hot cold hot) + P(313| cold hot hot)

如果我们有N个隐藏状态和T个观察序列，那么之后我们将得到 个可能隐藏序列。在实际中T往往很大，比如文本处理中可能有数万几十万个词汇，计算量将是指数上升的。在隐含马尔可夫模型中有种向前算法可以有效代替这种指数增长的复杂算法，大大降低复杂度。实验证明向前算法的复杂度是 。

现实应用：预测成都天气冷热

向前算法是一种动态规划算法，当得到观察序列的概率时，它使用的是一个表来存储中间值。向前算法也使用对于生成观察序列，所有可能的隐藏状态路径上的概率求和方法来计算观察概率。在向前算法中横向表示观察序列，纵向表示状态序列。对于给定的隐藏状态序列“hot hot cold”计算观察序列“3 13 ”的似然度的向前网格的例子。

每个单元 表示对于给定的自动机λ，在前面t个观察之后，在状态j的概率： ，其中 表示第t个状态是状态j的概率。如：表示状态1即数3时，q1的概率。

上面公式的3个因素如表11-6所示：

表11-6 公式参数解释 

向前网格如下图11-1 所示：

 图11-1 计算成都天气冷热事件“3 1 3”的向前网络

(1) 在时间1和状态1的向前概率：

从状态cold开始吃3根冰淇淋的似然度0.02

(2) 在时间1和状态2的向前概率：

从状态hot始吃3根冰淇淋的似然度0.32

(3) 在时间2和状态1的向前概率：

从开始到cold再到cold以及从开始到hot再到cold的天气状态，吃冰淇淋3 1 的观察似然度0.54

(4) 在时间2和状态2的向前概率：

从开始到cold再到hot以及从开始到hot再到hot的天气状态，吃冰淇淋3 1 的观察似然度0.0464

用同样方法，我们可以计算时间步3和状态步1的向前概率以及时间步3和状态步2的概率等等，以此类推，直到结束。显而易见，使用向前算法来计算观察似然度可以表示局部观察似然度。这种局部观察似然度比使用联合概率表示的全局观察似然度更有用。

文本序列标注案例：Viterbi算法

Viterbi算法

给定HMM 和观察序列 ，求解最大概率的状态序列 就是Viterbi算法解码问题。采用维特比算法求解隐藏序列后面的最大序列，针对可能的每一个隐藏状态序列，运用向前算法求解最大似然度的隐藏状态序列，从而完成解码工作，算法复杂度 ，状态序列很大时呈现指数级别增长，造成过大的计算量，由此采用一种动态规划Viterbi算法降低算法复杂度。

按照观察序列由左向右顺序，每个 表示自动机λ，HMM观察了前t个状态之后，每个 的值递归计算，并找出最大路径。Viterbi算法如表11-7所示：

表11-7 Viterbi算法 

维特比算法实例解读

例子：通过吃冰淇淋的数量（观察序列状态）计算隐藏状态空间的最佳路径（维特比网格）如下图11-2所示:

 图11-2 计算隐藏状态空间的最佳路径网络图

其中：

• 圆圈：隐藏状态
• 方框：观察状态
• 虚线圆圈：非法转移
• 虚线：计算路径
• q：隐藏空间状态

• o：观察时间序列状态

• ：在时间步t的观察状态下，隐藏状态j的概率。

给定一个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

 图11-3 维特比反向追踪路径图

综上所述可知：利用Viterbi算法我们可以通过小明夏季某天吃冰淇淋的观察值（3 1 3）推断出天气为（热 冷 热）。其实这个结果是符合客观事实的，人们天热吃3根冰淇淋，天冷吃一根。

参考文献

1. 数据挖掘十大算法： https://wizardforcel.gitbooks.io/dm-algo-top10/content/apriori.html
2. 中文维基百科： https://zh.wikipedia.org/wiki/%E5%85%88%E9%AA%8C%E7%AE%97%E6%B3%95
3. GitHub： https://github.com/BaiNingchao/MachineLearning-1
4. 图书：《机器学习实战》
5. 图书：《自然语言处理理论与实战》

完整代码下载

源码请进【机器学习和自然语言QQ群：436303759】文件下载：