隐Markov 模型及其在自然语言处理中的应用

隐Markov 模型及其在自然语言处理中的应用中科院计算所96博王斌1998 8 20Markov模型是Andrei A. Markov 提出来的现在用途十分广泛的一个统计模型。

在它基础上，又发展了各种不同的Markov模型。

隐Markov 模型(Hidden Markov Model,HMM)是Markov模型的一种，它在语言建模，特别是语音识别(Speech Recognition)中应用特别广泛。

尽管有些限制，但HMM在这个领域仍被认为是最成功的模型之一。

在自然语言处理的其它领域，例如词性标注(Part-of-speech Tagging)，应用HMM也取得了一定的进展。

本文首先介绍一般Markov模型的概念，然后介绍隐Markov模型的概念及相关问题处理算法，最后介绍其在自然语言处理中的应用。

一、一般Markov模型假设存在这样一个随机变量序列(通常与时间有关)，它满足这样的条件：每个随机变量之间并非相互独立，并且每个随机变量只依赖序列中前面的随机变量。

在很多类似的系统中，我们可以做出这样的假设：我们可以基于现在的状态预测将来的状态而不需要考虑过去的状态。

也就是说，序列中将来的随机变量与过去的随机变量无关，它条件地依赖于当前的随机变量，这样的随机变量序列，通常称为一个Markov链，或者说这个序列具有Markov 性质。

形式地，假设一个取值为S={s1,s2, …,s N}的随机变量序列X={X1,X2,…,X T}，当该序列具有以下性质：(i) P(X t+1=k|X1,X2, …,X t)=P(X t+1=k|X t)(ii) P(X t+1=k|X t)=P(X2=k|X1)时，我们就称该随机变量序列为Markov链、或者一个Markov 过程，这样一个模型就称为Markov模型。

一个Markov 模型由以下几个部分组成：状态空间 S={s1,s2, …,s N}={1,2, …,N}(为方便起见，我们用状态下标代表相应的状态)状态转移概率矩阵 A={a ij}, 1≤i≤N,1≤j≤N开始状态向量 Π={πi =P(X 1=s i )},1≤i ≤N随机状态序列变量 X={X 1,X 2,…,X T }其中，a ij =P(X t+1=s j |X t =s i ) 表示在序列中，前一个随机状态变量为s i 时后一个随机变量为s j 的概率，即状态s i 转移到状态s j 的转移概率。

显然，1a i,且0,a j,i,jij ij =∀≥∀∑ Markov 模型也可以用一个状态转换图来表示。

在这个状态转换图中，每个状态转移用一个转换箭头表示，每个状态用一个结点表示。

每个箭头从转换前状态结点指向转换后的状态结点，箭头上标有状态的转换概率。

每个结点的所有出箭头上的概率之和为1，概率为0的转换箭头省略。

很显然地，我们可以把Markov 模型看成一个不确定的有穷状态自动机。

经过T 次转换后的状态向量为：A T×∏一个Markov 随机变量序列X 1,X 2,…,X T 的概率很容易通过下式求得：P(X 1,X 2,…, X T )=P(X 1)P(X 2|X 1)P(X 3|X 1,X 2) …P(X T |X 1,X 2, …,X T-1)=P(X 1)P(X 2|X 1)P(X 3|X 2) …P(X T |X T-1)∏=+=T1t X X X 1t t i a π对于一个n 元(n-gram)模型，当n ≥3时，由于其转移概率依赖于序列中前面的多个状态，按照Markov 模型的定义，n 元模型似乎不是个Markov 模型。

然而，只要把Markov 模型中的状态集合扩充为一般状态集的笛卡尔积，就可以把n 元模型看成一个Markov 模型。

在这种情况下，我们把考虑前面n 个状态的Markov 模型称为n 阶Markov 模型，与其对应的是n+1元模型。

Markov 模型常常用于市场预测等方面，由于它与n 元模型之间是等价的，因此在统计语言学中也有着广泛的应用。

二、隐Markov 模型(HMM)隐Markov 模型(Hidden Markov Model ，HMM)是由基本Markov模型发展而来的，它由以下几个部分组成：状态集合 S={s1,s2, ...,s N}={1,2, ...,N}输出字母表 K={k1,k2, ...,k M}={1,2, ...,M}起始概率向量Π={πi=P(X1=s i)},1≤i≤N状态转移概率矩阵A={a ij}, 1≤i≤N,1≤j≤N符号发生概率矩阵B={b ik},1≤i≤N, 1≤k≤M状态序列X={X1,X2, ...,X T}输出序列O={O1,O2, ...,O T}其中S、A、X、Π与基本Markov模型中的概率一致，HMM 多出一个输出序列O、一个输出字母表K和一个符号发生概率矩阵B。

b ik表示处于状态S i时输出符号k k的概率。

实际上，HMM 是一个二重Markov 随机过程，它包括了状态转移的随机过程和观察值输出的随机过程，其中状态转移的随机过程是隐式的(这就是为什么称为隐Markov模型即Hidden Markov Model的来源)，它通过观察序列的随机过程表现出来。

HMM的意义在于可以通过可以观察到的表层事件来反映深层事件。

为了理解HMM的概念，举一个例子来说明：假设有一个人在一间密闭的屋子里掷三个硬币，我们看不到他掷硬币的过程，更不用说他掷硬币的次序了。

我们只能在物外的一个显示屏幕上看到掷硬币的结果TTHTHTT.....，T表示反面朝上，H表示正面朝上。

假设掷第三块硬币时，正面朝上的可能性大。

而掷其它两块硬币时，两面朝上的机会均等。

于是，我们可以想到，在显示屏幕上有可能出现的H比较多。

但事实并非仅仅如此，因为那个人有可能根本不扔第三块硬币。

这里存在一个转移概率的问题，掷第一块、掷第二块、掷第三块硬币之间相互转移的概率也影响着最后的结果，如果掷第一块或掷第二块硬币后掷第三块硬币的可能性较大的话，最后的结果中出现H的可能性也较大。

同样还有一个选择开始硬币的问题，如果一开始就选择第三块硬币的话，则在结果上出现H的可能性较大(特别是在观察数目较少的情况下)。

于是，综上，我们知道掷硬币的结果与三个因素有关：起始概率、转移概率、符号发生概率有关。

这里，掷第一块、掷第二块、掷第三块硬币可以看成HMM中不同的三个状态，掷不同硬币出现H或T的概率就是符号发生的概率，掷前一块和掷后一块之间的概率就是转移概率，最初开始选择硬币的概率就是起始概率，这就是一个典型的HMM 。

▲ HMM 的三个基本问题：1、给出一个HMM μ=(A,B,П)，如何高效率地计算某个输出序列O 的概率 P(O|μ)？以上面的例子为例，就是在模型已知的情况下，计算某个输出结果(假设为TTHTHHTT)的概率。

2、给出输出序列O 及模型μ，如何选择状态序列，使得它最符合输出序列？对上例而言，就是在模型已知的情况下，当知道某个输出结果(假设为TTHTHHTT)，求最有可能的掷硬币次序。

3、给出一个输出序列O ，以及可能的模型空间(不同的模型具有不同的模型参数)，如何找出最能解释输出序列的模型(即找出模型参数)？对上例而言，就是当模型未知的情况下，知道某个输出结果，求最可能的模型参数。

第一个问题可以用于判断哪个模型更好。

第二个问题可以用于猜测哪条路径最有可能，此时，该模型可用于分类，如词性标注。

第三个问题可以用于从已有数据中估计模型的参数。

▲ HMM 的三个问题的解决：1、计算输出序列的概率已知一个输出序列O={O 1,O 2, …,O T }和模型μ=(A,B,П)，求P(O|μ)。

一个直接计算的算法如下：对于任一状态序列X=(X 1,X 2, …,X T )，有)μ|)P(X μX,|P(O )μ|X P(O,=T1-T 32211X X X X X X X a a a π)μ|P(X L =T T O X O X O X b b b L C 2211)μ,X |P(o )μX,|P(O T1t t t ===于是，∑∑∑=−===T 21T T t 1t 111X X X T2t O X X X O X X XX b a b π)μ|)P(X μX,|P(O )μ|X P(O,)μ|P(O L C X 1,X 2,…,X T 的不同状态序列共有N T 种，每种状态序列需2T-1次乘法运算，该计算的复杂度为 O((2T-1)N T )个乘法运算。

假设N=5，T=100，则乘法的次数约为1072次，假设一台每秒能完成1万亿乘法运算的超级计算机，需要运行52年半！以上算法的症结在于重复计算太多，一个更有效的方法称为Forward-backword 过程，它采用了动态规划中的技术思路，即记录子路径的部分结果，避免重复运算。

动态规划(Dynamic Programming)也称为动态时间弯曲(Dynamic Time-Wraping)，常用于有序数字的最优求解问题，例如无向图中两点之间的最短距离问题或者语料库对齐中基于长度的对齐都采用了动态规划算法。

HMM 的动态规划问题可以用网格(trellises)图来表示。

如下图所示，网格图纵向1，2，…，N 表示N 个状态，横向表示1，2，…，T 个不同时刻，每个结点表示在某个时刻处于某个状态。

有向箭头一个状态向另一个状态的转移。

该图显示了Markov 模型随时间的状态变化图。

到达每个网格结点的概率可以用其前面的子路径概率来计算。

从图中可以看出，每个状态都可以到达任一状态，即从时刻t 到时刻t+1的某结点可能的路径有N 条。

将这N 条路径的概率相加即可得到到达此结点的概率。

也就是说，到达某一结点的概率可以通过前一时刻N 个结点的概率表示出来。

这样就通过已经保存了的子路径结果来计算新路径结果，避免了大量的重复运算从而大大提高了计算速度。

Forward-Backward 过程具体如下：(1) 向前过程(Forward Procedure)定义向前变量)μ|i X ,O O P(O (i)αt t 21t ==L 它定义了模型t 时刻状态为i 并且输出为O 1，O 2，…，O t的概率。

于是向前变量可以如下计算：① 初始化Ni ,1b π(i)α1iO i 1≤≤=②归纳N j 1,1-T t (j)α1t ≤≤≤≤+)i (α1i t =∑=N1,b a 1t jO ij +1状 23态N12 3 T 时间 t图：隐Markov 模型的网格结构③总计算∑==N1i T (i)α)μ|P(O 上述算法中的归纳部分需要2N(T-1)N 次乘法运算，约O(2N 2T)次乘法运算，大大减小了运算复杂度。