隐马尔可夫模型综述.doc

隐马尔可夫模型综述
于江德
摘　要：隐马尔可夫模型是一种有着广泛应用的统计模型，它是在马尔可夫模型基础上发展起来的。本文首先简要介绍了马尔可夫模型，然后对隐马尔可夫模型的基本概念、一般形式、三个基本问题及其解决算法进行了详细介绍，最后就隐马尔可夫模型的应用及当前研究的热点、难点进行了论述。
关键字：马尔可夫模型；隐马尔可夫模型；前向算法；后向算法；韦特比算法

1 引言
隐马尔可夫模型（Hidden Markov Model，简称HMM）是一种用参数表示，用于描述随机过程统计特性的概率模型，它是在马尔可夫模型基础上发展起来的。早在20世纪的60年代末和70年代初，HMM的基本理论就由Baum等人建立起来了，并由卡耐基－梅隆大学（CMU）的Baker和IBM的Jelinek等人将其应用到语音识别之中，取得了很大的成功[1]。但是，HMM引起世界各国从事语音处理研究的学者们广泛关注，并成为语音识别系统中构建统计模型的重要手段，却是20世纪80年代中期以后的事情，究其原因主要有两个[1]：首先，HMM理论起先发表在数学杂志上，并未被很多从事语音处理研究的工程技术人员获悉。其次，HMM首次应用于语音处理时，并没有提供足够的一般性介绍，从而使得多数研究人员无法理解其基本理论并将其应用到自己所从事的研究中去。直到1983年以后，Bell实验室的Rabiner等人发表了很有影响的一系列系统介绍HMM的理论和应用的文章[1]上述状况才得以根本改变。从上世纪80年代末开始，马尔可夫模型和隐马模型除了在语音识别领域继续得到广泛应用外，从上世纪90年代初到现在，HMM开始用到许多新的领域，如：自然语言处理领域的词性标注（Part-of-speech Tagging）[2～7]、命名实体识别[8]、特定信息抽取[9,10]、词法分析等；生物信息学中HMM被广泛用来分析基因序列[2,11]等。
由于HMM是建立在马尔可夫模型基础之上的，因此，本文首先简要介绍马尔可夫模型，然后对隐马尔可夫模型的基本概念、一般形式、三个基本问题及其解决算法进行详细介绍，最后就隐马尔可夫模型的应用及当前研究的热点、难点进行论述。
2 马尔可夫模型
马尔可夫模型最早是由Andrei A. Markov于1913年提出的[2],它的最初始目的是为了语言上的应用，即为俄国文学作品中的字母序列建模，随后马尔可夫模型发展成了一个通用的统计模型。为了区别于HMM，一般把马尔可夫模型称为显马尔可夫模型（Visible Markov Model，简称VMM）。
马尔可夫模型描述了一类重要的随机过程，该过程对应了一个随机变量序列（通常与时间有关），该序列满足这样的条件：序列中的随机变量值只依赖于它前面的随机变量。这样的随机变量序列，通常称为一个马尔可夫链。在实际工作中有很多类似的系统，该系统有N个状态S1，S2，……,SN,随着时间的推移，该系统从某一状态转移到另一状态。我们将在时间t的状态记为qt。对该系统的描述通常需要给出系统的当前状态（时间为t的状态）及其之前的所有状态，这些状态序列就构成了随机变量序列。
综上所述，我们可以给出马尔可夫模型如下形式定义：
假设一个取值为S={s1,s2, .,sN}的随机变量序列X={X1,X2,.,XT}，当该序列具有以下性质：
（1）有限视野性：即当前状态只与前n个状态有关,如公式2.1所示。
P(qt=sj|qt-1=si,qt-2=s,……)= P(qt=sj|qt-1=si,qt-2=s,…,qt-n) （2.1）
如果在特定情况下，系统在时间t的状态只与其在时间t-1的状态相关，则该系统构成一个离散的一阶马尔可夫链，公式2.1就简化为2.2：
P(qt=sj|qt-1=si,qt-2=s,……)= P(qt=sj|qt-1=si) （2.2）
（2）时间不变性：即只考虑公式2.2独立于时间t的随机过程，也就是说对任何时间t该公式都成立。
P(qt=sj|qt-1=si,qt-2=s,……)= P(qt=sj|qt-1=si)=aij 1≤i，j≥N （2.3）
该概率aij就称为状态转移概率。我们就称该随机变量序列为马尔可夫链、或者一个马尔可夫过程，这样一个模型就称为马尔可夫模型。
显而易见一个马尔可夫模型由以下几个部分组成：
状态空间S={s1,s2, .,sN}
随机状态序列变量X={X1,X2,.,XT}
状态转移概率矩阵A={aij}, 1≤i≤N,1≤j≤N
开始状态向量Π={πi=P(X1=si)},1≤i≤N
这样，可以记一个马尔可夫模型为一个四元组：
λ＝{S，X，П，A}
或简写为一个二元组：
λ＝{П，A}
马尔可夫模型也可以用状态转换图来表示[2]。在这个状态转换图中，每个状态转移用一个转换箭头表示，每个状态用一个结点表示。每个箭头从转换前状态结点指向转换后的状态结点，箭头上标有状态间转换概率。每个结点的所有出箭头上的概率之和为1，概率为0的转换箭头省略。很显然，还可以把马尔可夫模型看成一个不确定的有穷状态自动机[2]。
3 隐马尔可夫模型
3.1 隐马模型的基本概念
马尔可夫模型中，每一个状态代表一个可观察的事件，这限制了模型的适用范围。由于实际问题更为复杂，观察到的事件并不是与状态一一对应，而是状态的随机函数，这样的模型就称为隐马尔可夫模型。它是一个双重随机过程，其中之一是马尔可夫链，这是基本随机过程，它描述状态的转移，该过程是不可观察（隐蔽）的。另一个随机过程是隐蔽的状态转移过程的随机函数，描述状态和观察值之间的统计对应关系。这样，站在观察者的角度，只能看到观察值，不像马尔可夫模型中的观察值和状态一一对应，因此，不能直接看到状态，而是通过一个随机过程（观察值序列）去感知状态的存在及其特性。因而称之为隐马尔可夫模型。下面来看一个著名的说明HMM概念的例子——球和瓮（Ball and Urn）实验[1,6]：
假定在一房间中有N只瓮，每只瓮中有M中不同颜色的球。一个实验员根据某一概率分布随机地选择一个初始瓮，从其中根据不同颜色的球的概率分布，随机地取出一个球，并报告该球的颜色，记为O1，再把球放回瓮中。然后，根据某一概率分布，随机地选择另一只瓮，再从其中根据不同颜色球的概率分布，随机地取出一个球，并报告该球的颜色，记为O2……。对房间外的观察者，可观察的过程是不同颜色的球的序列：O1， O2，……，而瓮的序列是不可观察的。
这里，每只瓮对应于HMM中的状态，球的颜色对应于隐马尔可夫模型中的状态的输出符号。从一只瓮转向另一只瓮对应于状态转换，从一只瓮中取球对应于从一状态输出观察符号。
3.2隐马模型的形式描述
从上面球和瓮的例子可以看出，隐马尔可夫模型有如下的组成部分：
（1）模型中的状态数目N，状态集合记为S={s1,s2, ...,sN}。在球和瓮的实验中的瓮就相当于状态，状态数目就是瓮的数目。
（2）从每一状态可能输出的不同符号数M，符号集合记为K={k1,k2, ...,kM}。在球和瓮的实验中球的颜色就相当于输出符号，符号数就是球的颜色数。
（3）初始状态概率分布Π={π1，π2，……，πN}，其中
πi=P(X1=si)},1≤i≤N
πi≥0
在球和瓮的实验中，初始概率就是第一次选择某个瓮的概率。
（4）状态转移概率矩阵A={aij}, 1≤i≤N,1≤j≤N。在球和瓮的实验中，aij为实验员从一只瓮（状态si）转向另一只瓮（状态sj）的概率。其中
aij＝P（qt＝sj| qt-1＝si） 1≤i≤N,1≤j≤N
aij≥0
（5）符号输出概率矩阵B={bik},1≤i≤N, 1≤k≤M。在球和瓮的实验中，bik为实验员从一只瓮（状态si）取出第k种颜色的球的概率。其中
bik＝P（Ot＝vk | qt＝si） 1≤i≤N,1≤k≤M
bik≥0
这样，可以记一个隐马尔可夫模型为一个五元组：
λ＝{S，K，П，A，B}
或简写为一个三元组：
λ＝{П，A，B}
更形象地说，HMM可以分为两部分，一个是马尔可夫链，由П，A描述，产生的输出为状态序列，另一个是一个随机过程，由B描述，产生的输出为观察值序列，如图1所示。T为观察值时间长度。
马尔可夫链
（П，A）
随机过程
（B）
q1,q2,……,qT
状态序列
O1,O2,……,OT
观察值序列
图1 HMM组成示意图
3.3 隐马模型的三个基本问题
在上述给定的模型框架下，要用HMM解决实际问题，首先需要解决三个基本问题，它们是：
1、给定一个观察序列O＝O1O2……OT和模型λ＝{П，A，B}，如何高效率地计算概率P(O|λ)，也就是在给定模型λ的情况下观察序列O的概率。
2、给定一个观察序列O＝O1O2……OT和模型λ＝{П，A，B}，如何快速地选择在一定意义下“最优”的状态序列Q＝q1q2……qT，使得该状态序列“最好地解释”观察序列。
3、给定一个观察序列O＝O1O2……OT，以及可能的模型空间(不同的模型具有不同的模型参数)，如何来估计模型参数，也就是说，如何调节模型λ＝{П，A，B}的参数，使得P(O|λ)最大。
对上面的三个问题而言，第一个问题是评估问题，可以用于判断最佳模型。第二个问题是解码问题，可以用于寻找最有可能生成这个观察序列的状态序列。第三个问题是训练问题，可以用于从已有数据中估计模型的参数。
4 HMM的三个问题的解决
4.1 概率P(O|λ)的计算
在隐马尔可夫模型中，已知一个输出序列O＝O1O2……OT和模型λ＝{П，A，B}，要求P(O|λ)，最直接的办法可以把在所有状态序列下观察到序列O的概率相加，即：
从图1对HMM的组成示意中很容易理解以上的公式，其中P(Q|λ)是在给定模型λ＝{П，A，B}的情况下输出状态序列Q＝q1q2……qT的概率，P(O|Q, λ)是给定状态序列Q＝q1q2……qT和模型λ＝{П，A，B}的情况下观察序列O＝O1O2……OT的概率。它们可分别写成：
这样求解P(O|λ)的困难是，我们必须穷尽所有可能的状态序列。如果λ＝{П，A，B}中有N个不同状态，时间长度为T，我们就有NT个可能的状态序列。这样的算法会造成“指数爆炸”，当T很大时，几乎没有计算机能够有效地执行这个算法。
以上算法的症结在于重复计算太多，一个更有效的方法称为前向算法，它采用了动态规划中的技术思路，即记录子路径的部分结果，避免重复运算，这样使得原来指数爆炸的问题可以在O（N2T）的时间内解决。该算法使用了前向变量：
定义1：前向变量是在时间t，隐马尔可夫模型输出了序列O＝O1O2……Ot，并且位于状态Si概率：
前向算法的主要思想是，如果可以高效地计算前向变量，我们就能由此求得P(O|λ)。这是因为P(O|λ)是在所有状态下观察到序列O＝O1O2……OT的概率，即：
前向算法运用动态规划计算前向变量。该算法是基于如下的观察：在时间t＋1的前向变量可根据在时间t的前向变量，，……，的值来归纳计算：
从过程起始到时间t＋1，HMM到达状态Sj，并输出了观察序列O1O2……Ot＋1的过程，可分解为以下两个步骤：
步骤1：从起始到时间t，HMM到达状态Si，并输出了观察序列O1O2……Ot。
步骤2：从状态Si转移到状态Sj并在Sj输出Ot＋1。
这里Si可以是HMM的任意状态。这个过程的第一步，即HMM在时间t到达状态Si，并输出了观察序列O1O2……Ot的概率，根据定义，正是前向变量。这个过程第二步的概率为aij×bj（Ot＋1）。因而整个过程的概率为aij×bj（Ot＋1）。由于HMM可以从不同的Si 转移到Sj，我们必须将所有可能的路径的概率相加，由此得到上面公式。
从公式给出的归纳关系，我们可以按照从前到后的顺序计算前向变量序列。由此，我们得到前向算法的归纳过程：
1、初始化：
2、归纳计算：
3、终止：
前向算法的时间复杂度不难计算，它的总时间复杂度为O(N2T)。
对应于前向变量，我们在此定义后向变量，它将被运用在对HMM的第三个问题的求解中。
定义2：后向变量是在给定了模型λ＝{П，A，B}和假定在时间t状态为Si的条件下，HMM将输出观察序列Ot＋1Ot＋2……OT的概率，即：
和前向变量一样，我们可以运用动态规划计算后向变量。类似地，在时间t和状态为Si的条件下，HMM输出观察序列Ot＋1Ot＋2……OT的过程可以分解成两步：
步骤1：从时间t到时间t＋1，HMM由状态Si转移到状态Sj，并在Sj输出Ot＋1。
步骤2：从时间t＋1，状态Sj的条件下，HMM输出观察序列Ot＋2Ot＋3……OT。
从公式给出的归纳关系，我们可以按照从后到前的顺序计算后向变量序列。由此，我们得到后向算法的归纳过程：
1、初始化：
2、归纳计算：
和前向算法一样，后向算法的总时间复杂度也为O(N2T)。
4.2 最佳状态链的确定
给定一个观察序列O＝O1O2……OT和模型λ＝{П，A，B}，如何快速地选择在一定意义下“最优”的状态序列Q＝q1q2……qT，使得该状态序列“最好地解释”观察序列呢？
这个问题的解答不是唯一的，而是取决于如何理解“最优的状态序列”。通常的理解是在给定一个观察序列O和模型λ的条件下概率最大的状态序列[1,2,4,6]。

韦特比算法是运用动态规划搜索这种最优状态序列的算法。和前向算法与后向算法一样，韦特比算法定义了一个韦特比变量：
定义3：韦特比变量是在时间t隐马尔可夫模型沿着某一条路径到达状态Si，并输出观察序列O1O2……Ot的最大概率，即：

和前向变量相似，有如下的递归关系，使得我们能够应用动态规划：

除了外，韦特比算法利用变量来记忆在时间t隐马尔可夫模型是通过哪一条概率最大的路径到达状态Si的。实际上，记录了该路径上状态Si的前面一个（在时间t-1的）状态。
韦特比算法的归纳过程如下：
1、初始化：

2、归纳计算：

3、终止：

4、路径（状态序列）回溯：从变量回溯得到输出观察值序列的最优路径，即最优状态序列。
不难推断，韦特比算法的时间复杂度和前向算法、后向算法的时间复杂度一样，也是O(N2T)。
4.3 HMM中的参数估计
前向后向算法被用于解决HMM的第三个问题，即HMM的参数估计问题。也就是给定一个观察序列O＝O1O2……OT，以及可能的模型空间(不同的模型具有不同的模型参数)，如何来估计模型参数，也就是说，如何调节模型λ＝{П，A，B}的参数，使得P(O|λ)最大。这是一种最大似然估计。
由于HMM中的状态序列是观察不到的（隐变量），直接进行最大似然估计是不可行的。所幸的是，EM（Expectation Maximaization）算法可用于含有隐变量的统计模型的参数最大似然估计。其基本思想是，初始时随机地给模型的参数赋值（该赋值必须遵守模型对参数的限制，如从一状态出发的所有转移概率的总和为1），得到模型λ0。有λ0，我们可以得到模型中隐变量的期望值。以隐马尔可夫模型为例，我们可从λ0得到从某状态转移到另一状态的期望次数。以期望次数来代替公式中的实际次数，我们便可以得到模型参数的新的估计，由此得到新的模型λ1。从λ1，我们又可得到模型中隐变量的期望值，由此又可重新估计模型参数。循环以上过程，就可以使模型参数收敛于最大似然估计值。前向后向算法（Baum-Welch算法）就是EM算法在HMM中的具体应用。
5 隐马尔可夫模型的应用
隐马模型由于算法成熟，所以它是一种用途十分广泛的统计模型。目前绝大多数比较成功的语音识别系统都是基于HMM的，特别是在连续语音识别领域，HMM是声学模型部分的主流方法[12]。从上世纪90年代初到现在，HMM开始用到许多新的领域，如：自然语言处理领域的词性标注（Part-of-speech Tagging）[2～7]、命名实体识别[8]、特定信息抽取[9,10]、词法分析等；生物信息学中HMM被广泛用来分析基因序列[2,11]等。下面主要从HMM在语音识别、词性标注方面的应用进行展开叙述，并对它在解决问题中的局限性以及研究的难点与研究热点进行了论述。
5.1 隐马模型在语音识别中的应用
语音识别技术是以语音信号处理为研究对象，涉及语言学、计算机科学、信号处理、生理学、心理学等诸多领域，是模式识别的重要分支。孤立词识别，是语音识别中最基本的一个研究课题[2]。基于HMM的孤立词识别系统的基本思想是：在训练阶段，用HMM的训练算法（例如Baum-Welch算法），建立系统词汇表中每个词Wi对应的HMM，记为λi；在识别阶段，用前向-后向算法或韦特比算法求出各个概率；后处理阶段就是选取最大概率值对应的词为O的识别结果。
目前绝大多数比较成功的语音识别系统都是基于HMM的，特别是在连续语音识别领域，HMM是声学模型部分的主流方法。尽管如此，HMM仍然是有缺点和局限性的，总的说来，主要有以下3个方面[12]：
（1）常规HMM的状态驻留分布与语音信号的实际特性不符，因而引出了计算复杂度和存储代价较高的显式状态驻留HMM。
（2）对应给定的状态，它假定个观察矢量是相互独立的，即假设各帧之间是互不相关的，这也是不大符合实际的。
（3）基于短时帧为基础的特征提取的限制。
HMM这些缺点或称局限性，本质原因在于语音信号及语音识别问题的复杂性，人们为了研究的方便作了附加条件的假设。
5.2 隐马模型在词性标注中的应用
词性是词的一个重要属性。某些词只有一种词性，这种词无论出现在文本的什么位置，其词性都相同，如“我们”总是代词。而有些词有两种或两种以上的词性，这些词在文本的不同位置有不同的词性。为词标明其在上下文中的词性就是所谓的词性标注，词性标注是自然语言处理的重要一步。
词性标注的难点主要在于：（1）某些单词有多个词性，在不同的上下文中取不同的值，因此，对这些词标注需要考察其所在的上下文；（2）新词的出现，由于新词没有在词典中出现，不知道其词性，需要用特别的技术来处理。
用HMM对词性标注的任务建模就是寻找一个隐藏在幕后的词性标注序列T=t1t2…tn使得它对于可见的词序列W＝w1w2…wn是最优的。即已知词序列W（观测序列）和模型λ的情况下，求使得条件概率p(T|W，λ)值最大的那个T*，一般记作：。
如果假设词性序列是一个马尔可夫链，这个马尔可夫链在每次进行状态转移时都产生一个单词，具体产生哪个单词由其所处的状态决定。这样，可以很容易把词性标注和上述的隐马尔可夫模型联系起来。词性序列T=t1t2…tn对应于模型的状态序列，而标注集对应于状态集，词性之间的转移对应于模型的状态转移。
6 小结
隐马尔可夫模型在统计学中是一个十分重要的模型，有着广泛的应用。以上我们综述了HMM以及与其相关的几个算法，既是对这个模型的介绍，也是对有关HMM的一个总结。并对HMM的应用进行了简要论述，在具体应用中，HMM还有许多变种，但基本上都采用与基本HMM相似的处理算法和过程。

10