马尔可夫及隐马尔可夫模型的应用

黄岗

（西安体育学院 陕西 西安 710068）

马尔可夫模型是由Andrei A Markov于1913年提出来的，作为一种统计模型，广泛应用在语音识别，词性自动标注，音字转换，概率文法等各个自然语言处理等应用领域，到目前为止，它一直被认为是实现快速精确的语音识别系统的最成功的方法[1]。而隐马尔可夫模型是对马尔可夫模型的一种扩充，创立于20世纪60年代末70年代初。80年代得到了传播和发展，成为信号处理的一个重要方向，同时开始应用到生物序列尤其是DNA的分析中。从那时后起，在生物信息学领域HMM已经变得无从不在。到了90年代，HMM还被引入计算机文字识别和移动通信核心技术“多用户的检测”。20世纪90年代中期以后，隐马尔可夫模型被引入到图像处理和识别的研究中，并取得了一些初步的研究成果。HMM现已成功地用于语音识别，行为识别，文字识别以及故障诊断等领域[2]。目前的对于马尔科夫和隐马尔科夫模型的研究多为单一领域分析，尚不够全面。本文通过整理分析马尔科夫模型及隐马尔可夫模型，主要针对两个模型的应用进行分析，研究对比其在不同领域的应用，分析其优劣，进一步提出了相关改进建议和优化措施。

1 马尔可夫模型

马尔可夫链是由安德列·马尔可夫发现而得名的。在给定当前知识或信息的情况下，过去（即当期以前的历史状态）对于预测将来（即当期以后的未来状态）是无关的。一个简单?的例子，我们假设第二天的天气状况（晴天，阴天，雨天）只与今天的天气状况有关，与以前的状况无关。并且，在今天天气状态已知的情况下，明天的天气概率分布是确定的[3]。时间和状态都是离散的马尔可夫过程称为马尔可夫链，简记为Xn=X（n），n=0，1，2，…。马尔可夫链是随机变量X1，X2，X3…的一个数列。这些变量的范围，即他们所有可能取值的集合，被称为“状态空间”，而Xn的值则是在时间n的状态。如果Xn+1对于过去状态的条件概率分布仅是Xn的一个函数，则P（Xn+1=x|X0，X1，X2，…，Xn|）=P（Xn+1=x|Xn）这 里x为 过 程 中 的 某 个 状态。则这个恒等式可以被看作是马尔可夫性质。形式化地，我们可以认为马尔可夫链是满足下面两个假设的一种随机过程：

1）t+1时刻系统状态的概率分布只与t时刻的状态有关，与t时刻以前的状态无关；

2）从t时刻到t+1时刻的状态转移与t的值无关。一个马尔可夫链模型可表示为=（S，P，Q），其中各字母的含义如下：

1）S是系统所有可能的状态所组成的非空的状态集，有时也称之为系统的状态空间，它可以是有限的、可列的集合或任意非空集。文中假定S是可数集（即有限或可列）。用小写字母i，j（或Si，Sj）等来表示状态。

2）P=[Pij]n×n是系统的状态转移概率矩阵，其中Pij表示系统在时刻t处于状态i，在下一时刻t+1处于状态i的概率，N是系统所有可能的状态的个数。对于任意i∈s，有3）Q＝[q1，q2…qn]是系统的初始概率分布，qi是系统在初始时刻处于状态i的概率，满足

为了更明晰地了解这个模型的意义，我们可以想一个有限状态机，在不同状态之间转移有一个确定的概率分布。两个状态之间的概率就是在当前状态书籍的情况下，下一时间的状态变为另一个节点状态的概率。

2 隐马尔可夫模型

马尔可夫模型对日常的问题有一个比较好的模型化描述。但是，这样的模型研究价值并不大，因为所有状态都已知了。另一方面，在很多情况下，我们对状态是不能直接进行观测的，只能对状态反应出来的一部分性质进行观测，这就导致了隐马尔可夫模型（Hidden Markov Model）的提出。

隐马尔可夫模型是马尔可夫链的一种，它的状态不能直接观察到，但能通过观测向量序列观察到每个观测向量都是通过某些概率密度分布表现为各种状态，每一个观测向量是由一个具有响应概率密度分布的状态序列产生[4]。它是一种用参数表示的用于描述随机过程统计特性的概率模型，是一个双重随机过程，由两个部分组成：马尔可夫链和一般随机过程。其中马尔可夫链用来描述状态的转移，用转移概率描述。一般随机过程用来描述状态与观察序列间的关系，用观察值概率描述[5]。

对于HMM模型，其的状态转换过程是不可观察的，因而称之为“隐”马尔可夫模型。

HMM定义如下：

1）X代表一组状态的集合，其中X＝{S1，S2，…，SN}，状态数为N，并用qt来表示t时刻的状态。虽然状态是隐藏的，但对于很多应用来说，有一些物理的意义都和状态或者状态集相关。状态内部的联系就是从一个状态可以到其它状态。

2）O代表一组可观察符号的集合O＝{V1，V2，…，VM}，M是从每一状态可能输出的不同的观察值的数目。

3）状态转移概率分布A＝{aij}，这里aij＝P{qi+1＝Sj|qt＝Si}，1＜i，j≤N。特殊情况下，每个状态都可以一步到达其它任何状态，这时对任意（i，j）有aij＞0。对于其他的HMM，可能有aij＝0（对于一对或多对i，j）。

4）状态j的观察概率分布B＝{bj（k）}，表示状态j输出相应观察值的概率，其中bj（k）＝P{Ot＝Vk|qt＝Sj}，1≤j≤N，1≤k≤M。

5）初始化状态分布π＝{πi}，πi＝P{q1＝Si}，1≤i≤N。

由上，HMM可以定义为一个五元组λ：

λ＝（X，O，π，A，B）

或简写为

λ＝（π，A，B）

上面所述HMM的3个关键元素实际可以分成两部分，其一为Markov链，由π、A描述，另一部分是一个随机过程，由B描述。

利用隐马尔可夫模型，一般可以解决以下几类经典的问题。

1）估值问题。

给定观察序列O＝O1O2…OT和模型λ＝（A，B，π），计算P（O|λ）。即给定模型和输出观察序列，如何计算从模型生成观察序列的概率。可以把它看作是评估一个模型和给定观察输出序列的匹配程度，由此可以用来在一系列候选对象中选取最佳的匹配。例如我们要预测未来足球比赛的胜负，我们会收集现在的信息，并找出以后一系列比赛最可能的结果。隐马尔可夫模型可以给出每种可能结果出现的概率。

2）解码问题。

给定观察序列O＝O1O2…OT和模型λ＝（A，B，π），求在某种有意义的情况下最优的相关状态序列Q＝q1q2…qT。该可以理解为对输出观察的最佳“解释”，它试图揭示模型的隐藏部分，比如说查找“正确”的状态序列，在应用中，通常都使用一个优化策略来最大可能的解决这个问题。在智能电网的监控中，我们想知道每个用电器的使用情况，但又不能对每一个用电器都安装一个传感器，成本太高，而且有的地方不适合安装传感器。因此只能压缩采样。这里采集的数据就可以看作实际情况——用电器开关状态的一个性质反应。如果传感器数量多，我们就可以利用马尔可夫模型，以较高的精确度恢复用电器开关情况这一原始状态。

3）学习问题。

如何调整模型参数λ＝（A，B，π），对于一个给定的观察序列O＝O1O2…OT，使得P（O|λ）最大。它试图优化模型的参数来最佳的描述一个给定的观察序列是如何得来的。这里，我们有了所有的数据，但是想要一个马尔可夫模型来简单地描述它。就需要求出相应的参数。当然，我们可以用这个模型来匹配已有的数据，来看它是否合理地拟合了现在有数据。一般情况下，我们会用一部分数据训练，用一部分数据来测试，防止一些简单的高次拟合产生。

3 隐马尔可夫模型的应用

隐马尔可夫模型有以下特点：

1）HMM具有强有力的时间序列建模能力，在应用与模式识别时具有一些独特的优势，主要体现在整体和局部都具备平移不变性。HMM的核心是有限状态自动机，这赋予了它解决局部平移问题的能力[6]。

2）HMM体现了类似结构方法的一些特点，从而可能具备结构方法的部分优点。作为一种统计模型，隐马尔可夫模型仍然是基于特征以及贝叶斯决策进行判别，但是与一般统计方法和模型不同，它需要根据先验知识和对随机信号结构的分析构造一个合适的有限状态自动机作为其隐含层的拓扑结构，这种有限状态自动机实际上描述了信号的发生机制，因此，它的拓扑结构包含了信号的部分结构信息。

因此，它在许多领域，多括模式识别，天气预测，文字识别，语言翻译等领域有广泛的用途[7]。几个典型的应用如下：

1）语音识别

已知标准语音序列w1，w2，…，wn，求待测序列c1，c2，…，cn的含义

HMM模型：将每句话为理解为状态；将输入的待测样本为理解为观测值。

训练：统计状态转移矩阵和语言序列到观测序列的输出矩阵。

求解：采用Viterbi算法

步骤：声音采样——傅立叶到频域——频域特征向量提取——输入样本——构造HMM——输入声音——求解模型

2）疾病分析

已知疾病序列w1，w2，…，wn，求表征序列c1，c2，…，cn对应状态转移过程。

HMM模型：将每种疾病为理解为状态；将输入的表征现象为理解为观测值。

训练：统计从一种疾病转变到另一种疾病的概率转移矩阵和某一疾病呈现出某一症状的概率矩阵。

求解：采用Viterbi算法。

3）词性标注

已知单词序列w1，w2，…，wn，求词性序列c1，c2，…，cn。

HMM模型：将词性为理解为状态；将单词为理解为输出值。

训练：统计词性转移矩阵和词性到单词的输出矩阵。

求解：Viterbi算法。

4 结束语

马尔可夫模型还是有很多局限性的。它的一些假设忽略了实际的细节。具体来说，以下几个方面：

1）HMM在默认的情况下仅指一阶隐马尔可夫模型，一阶隐马尔可夫模型中有3个重要假设：①状态转移的Markov假设：系统在当前时刻的状态向下一时刻所处的状态转移的状态转移概率仅仅与当前时刻的状态有关，而与以前的历史无关。②不动性假设，即状态与具体时间无关。③输出值的Markov假设：系统在当前时刻输出观测值的概率，只取决于当前时刻的状态而与当前时刻以前的时刻所处的状态无关。而在实际应用中，这样假设并不十分合理，因为任一时刻出现的观测值的概率不仅仅依赖于系统当前所处的状态，也可能依赖于系统在之前时刻所处的状态[8]。

2）经典隐马尔可夫模型理论具有状态集固定的缺陷，这种缺陷影响了隐马尔可夫模型对随机信号建模的能力，并限制了基于隐马尔可夫模型的分类器的性能。利用隐马尔可夫模型对任何信号建模都存在这样的问题，被建模的信号比较简单或者包含信息量比较一致（如语音），基于先验知识预先定义状态集或者通过多次实验选择一种比较合适的固定状态集基本上就能描述所有的模式。而图像则不同，图像包含的信息量非常丰富，这就导致不同图像之间的信息量差距相应的不可避免的要大，因此这个问题在图像处理中就暴露得比较明显。因此，在实际应用中，隐马尔可夫模型有很多的改进模型，使其能更了的匹配实际状态。例如，在用电器监测中，我们假设同一时间开关的用电器数目有一个上界，那么许多状态转移是不可能发生的。又如，我们对一个用电器的开关时间长短作一个简单的统计，那么在某一状态的概率中，我们还要考虑这一状态中用电器开关时间的概率，可以对这一状态的发生概率作一次修正。这是传统的的马尔可夫模型所不能做到的。

[1]李相勇，张南，蒋葛夫.道路交通事故灰色马尔可夫预测模型[J].公路交通科技，2003，20（4）：98－100.LI Xiang-yong，ZHANG Nan，JIANG Ge-fu.Grey-markov model for forecasting road accidents[J].Journal of Highway and Transportation Research and Development，2003，20（4）：98－100.

[2]刘克.实用马尔可夫决策过程[M].清华大学出版社，2004.

[3]施程，桑广书.基于加权马尔可夫链的杭州市年降水量预测[J].浙江水利科技，2012（15）：21－23，44.SHI Cheng，SANG Guang-shu.An annual precipitation prediction based on weighted markov Chain in hangzhou[J].Zhejiang Hydrotechnics，2012（15）：21－23，44.

[4]罗宇，杜利民.基于隐马尔可夫模型局部最优状态路径的数据重建算法[J].电子与信息学报，2004（5）：722－726.LUO Yu，DU Li-min.HMM local optimal state path-based data imputation[J].Journal of Electronics and Information Technology，2004（5）：722－726.

[5]何彦斌，杨志义，马荟，等.一种基于HMM的场景识别方法[J].计算机科学，2011（4）：254－256.HE Yan-bin，YANG Zhi-yi，MA Hui，et al.Method of situation recognition based on hidden markov model[J].Computer Science，2011（4）：254－256.

[6]潘奇明，程咏梅.基于隐马尔可夫模型的运动目标轨迹识别[J].计算机应用研究，2008（7）：1988－1991.PAN Qi-ming，CHENG Yong-mei.Trajectory recognition of moving objects basedon hidden Markov model[J].Application Research of Computers，2008（7）：1988－1991.

[7]李楠，姬光荣.基于不同隐马尔科夫模型的图像识别方法[J].现代电子技术，2012（8）：54－56，60.LI Nan，JI Guang-rong.Image recognition algorithms based on different hidden Markov models[J].Modern Electronics Technique，2012（8）：54－56，60.

[8]刘云中，林亚平，陈治平.基于隐马尔可夫模型的文本信息抽取[J].系统仿真学报，2004（3）：507－510.LIU Yun-zhong，LIN Ya-ping，CHEN Zhi-ping.Text information extraction based on hidden markov model[J].Acta Simulata Systematica Sinica，2004（3）：507－510.