第五章 隐马尔可夫模型

HMM基本理论依据来源于随机过程中马尔可夫过程理论。

如果有一个实际的物理过程，产生了一个可观察的序列，在此情况下，建立一个模型去描述该序列的特征非常重要。因为，如果能用一个模型描述该信号，则就有可能去识别它。

如果在分析的区间内，信号是平稳的，那么使用线性模型就可以了。比如，语音信号在短时（10~30ms）内被认为是平稳的，因而可以用一个全极点模型或极零点模型去模拟它，这就是线性预测模型。此外，短时谱、倒谱也都属于线性模型，人们关于这些模型技术的研究也已比较透彻。

如果在分析的区间内信号是时变的，那么上述线性模型的参数也就是时变的。此时，最简单的方法是：在极短的时间内用线性模型参数来表示；然后，再将许多线性模型在时间上串接起来。这就是马尔可夫链。但是，除非已经知道信号的时变规律，否则会存在一个问题：如何确定多长的时间模型就必须变换？显然，不可能准确地确定这个时长，或者不可能做到模型的变化与信号的变化同步，所以马尔可夫链虽然可以描述时变信号，但不是最佳和最有效的。

而隐马尔可夫模型既解决了用短时模型描述平稳段的信号，又解决了每个短时平稳段是如何转变到下一短时平稳段的问题。它利用概率及统计学理论成功地解决了如何辨识具有不同参数的短时平稳的信号段以及如何跟踪它们之间的转化等问题。由于语言的结构信息是多层次的，除了语音特性外，还涉及到音长、音调、能量等超音段信息以及语法、句法等高层次语言结构的信息。而HMM既可以描述瞬变的(随机过程)，又可以描述动态的(随机过程的转移)特性，所以它能够利用这些超音段和语言结构的信息。

1、马尔可夫及马尔可夫过程

马尔可夫(A.Markov，1856-1922)数学家，他开创了一种无后效随机过程的研究，即在已知当前状态的情况下，过程的未来状态与其过去状态无关，这就是现在所熟悉的马尔可夫过程。马尔可夫的工作极大丰富了概率论的内容，促使它成为自然科学和技术直接有关的最重要的数学领域之一。在工程技术方面目前已被广泛应用于通信、模式识别等方面。

2、与马尔可夫有关的概念

随机变量与随机过程 把随机现象的每个结果对应一个数，这种对应关系成为随机变量。例如某一时间内公共汽车站等车乘客的人数，电话交换台在一定时间内收到的呼叫次数等等，都是随机变量的实例。

随机过程 随机过程是一连串随机事件动态关系的定量描述，即和“时间”相关的随机变量。一般记为xt。比如在一天24小时，在每个整点时刻徐州火车站的旅客数量。 马尔可夫过程与马尔可夫链 设xt是一随机过程，过程在时刻t01所处的状态与时刻t0所处

的状态相关，而与过程在时刻t0之前的状态无关，这个特性成为无后效性。无后效性的随机过程成为马尔可夫过程。

举例：比如万恶旧社会流离失所的百姓每天的饥饿程度是一个随机过程。假如他们在t0(今天)的饥饿状态是五分饱，他们在t01(明天)的饥饿状态取决于t0时刻(今天)，而和t0时刻(今天)

之前(昨天、前天)无关，这样的一个随机过程就是一个马尔可夫过程。

马尔可夫过程中的时间和状态既可以是连续的，又可以是离散的。我们称时间离散、状态离散的马尔可夫过程为马尔可夫链。在实际应用中使用马尔可夫链较多。

从数学上可以给出如下定义。

随机序列Xt，在任一时刻t，它可以处在状态1,,N，且它在tk时刻所处的状态为qtk的概率，只与它在t时刻的状态qt有关，而与t时刻以前它所处的状态无关，即有：

PXtkqtkXtqt,Xt1qt1,,X1q1

PXtkqtkXtqt

式中，

q1,q2,,qt,qtk1,,N

则称Xt为马尔可夫链，并且称Pij为k步转移概率，表示如下：

Pijt,tkPqtkjqti

式中，i和j是介于1和N之间的正整数，t是正整数。当Pijt,t夫链为齐次马尔可夫链，此时：

Pijt,tkPijk

k与t无关时，称这个马尔可

以后无特殊声明，马尔可夫链就是指齐次马尔可夫链。当k1时，Pij1称为

1步转移概

率，简称为转移概率，记为aij。所有转移概率aij,1a11AaN1i,jN可以构成一个转移概率矩阵，即：

a1NaNN

且有：

0aij1

Naj1ij1

由于k步转移概率Pijk可由转移概率aij得到，因此描述马尔可夫链的最重要的参数就是转移概率矩阵A。但A矩阵还决定不了初始分布，即由A求不出q1描述马尔可夫链除了A矩阵之外，还必须引进初始概率iPq1i1iN1,,i的概率，这样，完全

N，其中：

显然有：

0i1

ii1

一个例子：

为了形象说明“状态”和“状态转移”的概念，假设一个水池中有三片荷叶，一只青蛙在三片荷叶之间跳跃玩耍，见上图。

观察青蛙的活动会发现青蛙的动作是随意的，为了讨论方便，给荷叶进行编号，我们关心的是在一定时间内，它从一片荷叶跳到其他两片荷叶的转移结构。当青蛙在第一片荷叶上时，它下一步动作跳跃到第2，3片荷叶上或原地不动，只与现在的位置1有关，而与它以前跳过的路径无关。我们给出这只青蛙从各片荷叶上向另一片荷叶移动的转移图，见下图：

箭头表示跳跃的方向，数字表示跳跃的概率，白环表示青蛙保持不动。

此图表明：在一定时间内，

当青蛙开始时刻在第一片荷叶上，它保持不动的概率为0.3，它跳跃到第二片荷叶的概率为0.6，跳跃到第三片荷叶上的概率为0.1；

当青蛙开始时刻在第二片荷叶上，它保持不动的概率为0.4，它跳跃到第一片荷叶的概率为0.2，跳跃到第三片荷叶上的概率为0.4；

当青蛙开始时刻在第三片荷叶上，它保持不动的概率为0.5，它跳跃到第一片荷叶的概率为0.2，跳跃到第二片荷叶上的概率为0.3；

我们以xt表示青蛙跳跃t次后所处的位置，xt的取值叫做状态，S间，我们称xtt1,2,3叫做状态空

0为一个随机过程，当从x0到xt已知时，青蛙在t1时处在xt1状

态上的概率仅与t时刻状态有关，即满足以下关系式：

Pxt1jx0i0,x1i1,,xtiPxt1jxti

称满足上式的随机过程xttPxt1jxti为转移0为马尔可夫过程或马尔可夫链，

概率，由于这种转移概率不依赖于时间，因此具有稳定性，用常数表示，将各个状态之间的转移概率用一个矩阵表示出来，就得到一个马尔可夫链数学模型：

p11p21Ppn1p12p22pn2p1np2npnn

为一步概率转移矩阵，简称转移矩阵，由于转移矩阵的每行都是的分布，所有每行的元素满足如下性质： 且有：

0pij1i,j1,2,,n

nj1pij1i1,2,,n

由此，青蛙跳跃的一步转移矩阵为：

p11Pp21p31p12p22p32p130.3p230.2p330.20.60.40.30.10.40.5

实际中，马尔可夫链的每一状态对应于一个可观测到的物理事件，比如天气预测中的雨、晴、雪等，这时可称为天气预报的马尔可夫模型。根据这个模型，可以计算出各种天气(状态)在某一时刻出现的概率。

练习：

写出其状态转移矩阵A：

0.30.2A000.20.50.40.10.100.10.40.30.10000.50.50.20.100.10.30.6

1、 HMM的基本思想？

HMM是在马尔可夫链的基础上发展起来的。由于实际问题比马尔可夫链模型所描述的更为复杂，观察到的事件并不是与状态一一对应的，而是通过一组概率分布相联系，这样的模型就称为HMM。HMM是一个输出符号序列的统计模型，具有N个状态S1,S2,,SN，它按一定的周期从一个状态转移到另一个状态，每次转移时，输出一个符号。转移到哪一个状态，转移时输出什么符号，分别由状态转移概率和转移时的输出概率来决定。因为只能观测到输出符号序列，不能观测到状态转移序列(即模型输出符号序列时，是通过了哪些状态路径，不能知道)。因而称之为“隐”马尔可夫模型。

下再看一个著名的说明HMM概念的球和缸(ball and urn)的实验,，如下图所示。

举例：

上图为一个简单的HMM例子，它具有三个状态，S1为起始状态，S3为终了状态。只能输出a,b两个符号。每条弧上有一个状态转移概率以及该弧发生转移时输出符号a,b的概率。从一个状态转移出去的概率和为1，每次转移时输出符号a和b的概率之和也为1.图中aij表

示从Si状态转移到Sj状态的概率，每个转移弧上输出概率矩阵中a和b两个符号对应的数字，分别表示了该弧发生转移时该符号的输出概率值。

设初始分布为0.50.50，输出的符号序列是aab，求其输出概率。

输出aab，可能的路径只有S1S1S2S3，S2S2S2S1S1,S1S1S2，S1S1S3，S1S2S2S2S3，

，S2。每一种路径输出aab的概率分别为：

P1：S1P2：S1P3：S1P4：S1P5：S1P6：S2P7：S2S1S1 0.50.80.30.80.30.20.00576S1S2 0.50.80.30.80.50.70.0336S1S3 0.50.80.30.80.20.50.0096S2S20.50.80.50.30.40.70.0096S2S30.50.80.50.30.60.50.018

S2S20.50.30.40.30.40.70.00504S2S30.50.30.40.30.60.50.00因为是隐HMM模型，不知输出aab时，到底是经过了哪一条不同状态组成的路径，因此求aab的输出概率时，把每一种可能的概率相加作为总的概率，所以该HMM输出aab的总概率为PO再看一个例子：

0.005760.0360.00960.016800180.005040.000.0942。

2、 HMM的定义？

有了前面讨论的马尔可夫链以及对HMM思想的理解，现在可以给出HMM的定义。一个HMM可以由下列参数描述：

(1)

N：模型中状态的数目。状态的集合SS1,S2,,SN。记N个状态为1,,N，记t时刻马尔可夫链所处状态为qt，显然qt1,,N。在球与缸实验中的缸就相当于状态。 (2) (3)

MT：每个状态对应的可能的观察值数目。观测符号集合V：观测符号序列的长度，观测符号序列Ov1,v2,,vM。

O1,O2,,OT.记M个观察值为

V1,,VM，记t时刻观察到的观察值为ot，其中otV1,,VM。在球与缸实验中所选

择彩球的颜色，就是观察值。 (4) ：初始状态概率1,,N，式中

iPq1i1iN在球与缸实验中指开始时选取某个缸的概率。

(5)

A：状态转移概率矩阵，aijNN，式中

aijPqt1jqti1i,jN

在球与缸实验中，描述在当前缸的条件下选取下个缸的概率。

(6)

B：观察值概率矩阵，bjkNN，式中

bjkPotVkqtj1jN,1kM

在球与缸的实验中，bjk就是第j个缸中球的颜色k出现的概率。这样就可以记一个HMM为：

N,M,,A,B

或简写为

,A,B

更形象地说，HMM可分为两部分：一部分是马尔可夫链，由,A描述，产生的输出为状态序列；另一部分是一个随机过程，由B描述，产生的输出为观察值序列，如下图所示，其中T为观察值时间长度。

HMM基本元素实例：

在A,B,这三个模型参数中，(初始概率分布)最不重要，B(某状态下系统输出的概率分布)最为重要，因为它就是外界观察到的系统输出的概率。而A(状态转移概率分布)的重要性要差一些。

HMM模型的假设： 假设1：有限历史假设

Pqiqi1q1Pqiqi1

假设2：齐次性假设(状态与具体时间无关)

Pqi1qiPqj1qj 对任意i,j成立

Poqt

假设3：输出性假设(输出仅与当前状态有关)

Po1,,oTq1,,qTt假设一个HMM模型从n1时刻开始运行，在n1~N诸时刻所给出的N个随机矢量yn

构成一个广义N维行向量即矩阵Yy1,y2,,yN。对于HMM模型，其每一次运行过程中

产生的马尔可夫链X是外界看不见的，可观测的只是Y。

HMM的过程是：

1. 根据初始状态分布概率，选择一个初始状态。置时刻n2. 根据B，得出Sin1。

1状态下输出的概率分布bm1n1时。

n1时为S3. 根据A，由n时刻的Si状态转移到n态，并置n4. 如果n

3、 HMM三项问题的求解？

Nn1。

j状态的转移概率分布确定下一个状

，则回到第②步，否则结束。

HMM 用于进行识别时，有三个问题必须解决： (1) 已知模型输出O(2) 已知模型输出Oo1,o2,,oTo1,o2,,oT及模型及模型,A,B，怎样计算产生O的概率PO/;

时最可能

,A,B，怎样估计模型产生此O经历的状态So1,o2,,oT。它可以被认为是所有可能的路径中概率最大的路径。这是一个识别问题，即对于给定的输出O计算出所有模型输出它的概率，而以输出概率最大者判定为对应于O的模型。

(3) 如何根据模型的若干输出O来不断修正模型参数，优化模型参数PO最大。

,A,B，使

4、 HMM基本算法？

一个HMM模型可以用5个元素来描述，包括2个状态集合和3个概率矩阵，分别为：隐含状态S，可观测状态O，初始状态概率矩阵n，隐含状态转移矩阵A，观测状态转移概率矩阵B。

1、前向-后向算法(解决问题1) 该算法用于计算给定一个观察值序列O型产生出O的概率PO。

前向算法

对于一个固定的状态序列Qq1,q2,,qTTo1,o2,,oT以及一个模型,A,B时，由模

，有：

POQ,Potqt,bqo1bqo2bqoTt112T

其中，bqot表示在qt状态下观测到ot的概率。

tbqtotbjkqtj,otVk

1tT

对于给定，产生Q的概率为：

PQq1aq1q2aq2q3aqT1qT

因此，所求概率为：

POPO,QPOQ,PQ PABPAPB/A

QQQq1bq1o1aq1q2bq2o2aq2q3aqT1qTbqToT

由此可以看见其计算复杂度非常大，为2TNT。当N=5，T=100，计算量达到1072。为此，提出了前向-后向算法，其运算量大大减少。在后续算法中为方便表示，将i的形式简记为i。首先定义一个前向变量，表示从1到t，输出符号o序列，t时刻处于状态i的累计输出概率。

tiPo1,o2,,ot,qti

因为前向变量有如下性质： 初值：

1iPo1,q1iibio1，1iN

递推： %PO,QNPOQ,PQ

t1jtiaijbjot1 2tT1,1jNi1

最后有：

PONi

Ti1bjot1bjkot1Vk

通过该方法可以简化计算复杂度，原因在于，每一次ti，都可以用t1i来计算，不用重复计算。

前向算法即按输出观察值序列的时间，从前向后递推计算输出概率。首先说明下列符号的定义：

Oo1,o2,,oTP(O/)

输出的观察符号序列

给定模型时，输出符号序列O的概率

aij 从状态Si到状态Sj的转移概率

从状态Si到状态Sj发生转移时输出ot的概率

输出部分符号序列o1,o2,,ot并且到达状态Sj的概率，

bij(ot)t(j)

即前向概率

由上面符号的定义，则t(j)可有下面的递推公式计算得到： （1）初始化 0(1)1，0(j)0 (j1)

（2）递推公式 t(j)（3）最后结果

it1(i)aijbij(ot) （t1,2,,T；i,j1,2,,N）

P(O/)T(N)

1时刻的所有状

图5-3说明了在递推过程中t1(i)与t(j)的关系，t时刻的t(j)等于t态的t1(i)aijbij(ot)之和，当然如果当状态Si到状态Sj没有转移时aij有状态Sj

(j1,2,,N)0。这样在t时刻对所

的t(j)都计算一次，则每个状态的前向概率都更新了一次，然后进

入t1时刻的递推过程。图5-4以上面计算aab的输出概率为例子，说明了利用前向递推算法计算输出概率的全过程，图中虚线表示没有转移。从图5-3和图5-4可以理解利用前向递推算法计算模型骤如下：

（1）给每个状态准备一个数组变量t(j)，初始化时令初始状态S1的数组变量0(1)为1，其它状态数组变量0(j)为0；

（2）根据t时刻输出的观察符号ot计算t(j)：

t(j){A,B,}对于输出观察符号序列Oo1,o2,,oT的输出概率P(O/)的步

it1(i)aijbij(ot)t1(1)a1jb1j(ot)t1(2)a2jb2j(ot)(j1,2,,N)

t1(N)aNjbNj(ot)当状态Si到状态Sj没有转移时aij（3）当tT0；

时转移到（2），否则执行（4）；

（4）把这时的终了状态的数组变量T(N)内的值取出，则

P(O/)T(N)

%a1iibiO1 1it1(j)N 初始状态Si和初始观测O1的联合概率；，

i1t(i)aijbij(ot1)t(1)a1jb1j(ot1)t(2)a2jb2j(ot1)(j1,2,,N,1tT1)t(N)aNjbNj(ot1)无论t时刻处于哪个状态，它都会以一定概率在t+1时刻转移到Sj

tiaij表示t时刻的观测符号序列O1,O2,,Ot，并由t时刻Si转移到t+1时刻的状态Sj发观测到的符号序列O1,O2,,Ot在t+1时刻处于状态Sj发生的概率；

t生的概率。

i1t(i)aijt1(j)i1(i)aijbij(ot1)给定模型下，产生

t+1以前的部分观测符号序列(包括t+1在内)

O1,O2,,Ot,Ot1，且时刻又处于状态Sj的概率。

NP(O/)ai1T(i)将所有aT(i)对i求和

1T1，总加数为NN1T1

所需总乘数为NN用前向算法重做前面的例子 计算前向变量示意图：

例题：如下所示一个HMM模型，试用前向算法计算产生观察符号序列O个时刻的ti和总概率。

ABAB时每

当然初始概率矩阵nti。解法如下：

1,0,0，即开始处于状态

1.按照上面的公式，可以递推依次解出

t1时：

111b1A10.70.7

t2时：

2111a11b1B0.70.40.30.0842211a12b2B0.70.60.60.252t3时：

3121a11b1A0.0840.40.70.02352

3221a1222a22b2A0.0840.60.2520.80.40.10083322a23b3A0.2520.20.80.04032t4

时：

4131a11b1B0.023520.40.30.000282244231a1232a22b2B0.023520.60.10080.80.60.05685124332a2333a33b3B0.10080.20.0403210.20.012096

所以最后的结果：

PO4142430.0717696

计算过程示意图如下所示：

后向算法

与前向法类似 定义后向变量

tiPot1,ot2,,oT,qti

1tT1

初始化：

Ti1 1tT

递归：

Ntiai1ijbjot1t1j tT1,T2,,1,1iN

终结：

PONi

1i1与前向算法类似，后向算法即按输出观察值序列的时间，从后向前递推计算输出概率的方法。首先说明下列符号的定义：

Oo1,o2,,oTP(O/M) aij 输出的观察符号序列

给定模型M时，输出符号序列O的概率

从状态Si到状态Sj的转移概率

从状态Si到状态Sj发生转移时输出ot的概率 从状态Si开始到状态SN结束输出部分符号序列

ot1,ot2,,oTbij(ot)t(i)

的概率，即后向概率

t(i)可由下面的递推公式计算得到：

（1）初始化 T(N)（2）递推公式 t(i)（3）最后结果

1，T(j)0

(jN)

）

jt1(j)aijbij(ot1)N （tT,T1,,1；i,j1,2,,NP(O/M)i11(i)i0(1)

后向算法的计算量大约在N率，有如下关系成立：

2T数量级，也是一种格型结构。显然，根据定义的前向和后向概

NNtP(O/)i1j1(i)aijbij(ot1)t1(j)，1tT1 （5-14）

2、Viterbi算法(解决问题2) 给定观察序列Oo1,o2,,oT以及一个模型,A,B时，怎样寻找满足这种观察序列

意义最优的隐含状态序列Q。

首先，引入3个符号：

tj，表示在观察时刻

t正处在状态j，且沿一条路径q1q2qt，产生出的o1o2ot最大

概率；

tj，表示的是一个状态值，该状态值产生了上面的，也就是说计算时是由上一次哪个

状态产生的；

qt*，表示在观察时刻t中所有的内最大的哪个状态，所以其也是一个状态值。

由上面的解释可以得出这3个符号的数学表达式如下：

tjmaxt1iaijbjot1iN

tjargmaxt1iaij

1iNqtt1qt1

**所以说当已知观察序列，要用Viterbi算法求解最优状态序列时与前面讲求最大观察值概率的算法相似，只是在求概率时，不再是将其来源相加，而是取其中最大的那个。

还针对刚才的问题：

如下所示一个HMM模型，试用前向算法计算产生观察符号序列O的ti和总概率。

ABAB时每个时刻

当然初始概率矩阵ntj，tj，qt*1,0,0，即开始处于状态1.按照上面的公式，可以递推依次解出

。解法如下：

第一次观察时：

t1

111b1A10.70.7,110

第二次观察：

t1

2111a11b1B0.70.40.30.084,211

2211a12b2B0.70.60.60.252,221

第三次观察时：

3121a11b1A0.0840.40.70.02352,311

32max21a12,22a22b2Amax0.0840.6,0.2520.80.40.080,322 3322a23b3A第四次观察时：

0.2520.20.80.0403,2332

4131a11b1B0028224,411

42max31a12,22a22b2Bmax0.014112,0.05120.60.0387072,422

43max32a23,33a33b3Bmax0.080*0.2,0.04032*10.20.00806,4433其递推结果为：

Pmax4imax0.0028224,0.0387042,0.0080*1i3*0.0387042

q4argmax4i21i3

q34q4422

**q23q3322****

q12q2221

所以最后得结果状态序列为o1,o2,o3,o4。其计算结果示意图如下所示：

浅绿色箭头表示最有可能的状态序列。

3、Baum-Welch算法

该算法是对HMM第三个问题的求解，它是HMM模型参数的训练问题，即求取，使得PO最大，这是一个泛函极值问题。由于给定的序列有限，因此不存在一种最佳方法来估计，Baum-Welch算法利用递归的思想，使得PO局部最大，最后得到模型参数

A,B,。

定义ti,j为给定训练观察序列O和参数模型时，时刻t马尔可夫链处于状态i，而时刻t1处于状态j的概率：

ti,jPSti,St1jO,

根据前向和后向变量的定义：

tiPo1,o2,,ot,sti tiPot1,ot2,,oTsti,

ti,jPSti,St1j,OPOtiaijbjot1t1jPOtiaijbjot1t1jNNtij

iai1j1bjot1t1j定义ti为给定观察序列O和模型参数，t时刻处于状态i的概率：

tiPStiO,Ni,j

tj1TT显然，ti就是从状态i发出的状态转移数的期望值；ti,j是从状态i到j的状态

t1t1转移数的期望值。推导HMM的模型为：

1i

T1i,jtaiji1T1

iti1Ti,jtbjkt1s,t,otvkT

tii1HMM参数的求取过程为根据观察序列O和初始模型一组参数,aij,bjk，即新的模型要好。

A,B,A,B,，由重估公式得到新的

,，即由重估公式得到的要比在观察值O上