隐马尔可夫模型_刘秉权.pdf

隐马尔可夫模型

刘秉权

哈工大智能技术与自然语言处理研究室
2006年11月
主要内容

„马尔可夫模型

„隐马尔可夫模型

„隐马尔可夫模型的三个基本问题

„隐马尔可夫模型的基本算法

„隐马尔可夫模型的应用

隐马尔可夫模型2
马尔可夫链

一个系统有个状态，随着时间推移，系统从
NS1,S2,L,SN

某一状态转移到另一状态，设qt为时间t的状态，系统在时间t处

于状态的概率取决于其在时间的状态，该概率为：
Sj1,2,L,t-1

P(qt=Sj|qt-1=Si,qt-2=Sk,L)
如果系统在t时间的状态只与其在时间t−1的状态相关，则该
系统构成一个离散的一阶马尔可夫链(马尔可夫过程)：

P(qt=Sj|qt-1=Si,qt-2=Sk,L)=P(qt=Sj|qt-1=Si)

隐马尔可夫模型3
马尔可夫模型(MarkovModel)

如果只考虑独立于时间t的随机过程：

P(qt=Sj|qt-1=Si)=ai,j,1≤i,j≤N

其中状态转移概率ai,j必须满足ai,j≥0且

N
，则该随机过程称为马尔可夫模型。
∑ai,j=1
j=1

隐马尔可夫模型4
马尔可夫模型可视为随机有限状态自动机

„该有限状
态自动机
的每一个
状态转换
都有一相
应概率，
表示自动
机采用这
一状态转
换的可能
性

隐马尔可夫模型5
例

假定一段时间内的气象可由一三状态

马尔可夫模型M描述：S1：雨，S2：多云，

S3：晴，转移概率矩阵为：

0.40.30.3

A=[aij]=0.20.60.2
0.10.10.8

隐马尔可夫模型6
例（续）

如果第一天为晴天，根据这一模型，在今后七天中天气为

O="晴晴雨雨晴云晴"的概率为：
P(O|M)

=P(S3,S3,S3,S1,S1,S3,S2,S3|M)

=P(S3)⋅P(S3|S3)⋅P(S3|S3)⋅P(S1|S3)⋅P(S1|S1)⋅

P(S3|S1)⋅P(S2|S3)⋅P(S3|S2)

=1⋅a33⋅a33⋅a31⋅a11⋅a13⋅a32⋅a23
=(0.8)(0.8)(0.1)(0.4)(0.3)(0.1)(0.2)
=1.536×10−4

隐马尔可夫模型7
隐马尔可夫模型
(HiddenMarkovModel,HMM)

„在MM中，每一个状态代表一个可观察的
事件

„在HMM中观察到的事件是状态的随机函
数，因此该模型是一双重随机过程，其
中状态转移过程是不可观察（隐蔽）的
(马尔可夫链)，而可观察的事件的随机过
程是隐蔽的状态转换过程的随机函数(一
般随机过程)。

隐马尔可夫模型8
实例

一房间有N只瓮，每只瓮中有M种不同颜色的球。
根据某一概率分布随机地选择一个初始瓮，根据不同颜色
球的概率分布从中随机取出一个球，并报告球的颜色。然
后根据某一概率分布随机地选择另一只瓮，再根据不同颜
色球的概率分布从中随机取出一个球，并报告球的颜
色，⋯。对房间外的观察者，可观察的过程是不同颜色球
的序列，而瓮的序列是不可观察的。
这里每只瓮对应HMM模型中的状态，球的颜色对应
于状态的输出符号，从一只瓮转向另一只瓮对应于状态转

换，从一只瓮中取球对应于从一状态输出观察符号。

隐马尔可夫模型9
实例（续）

Urn3

Urn2
Urn1

Veil

ObservedBallSequence

隐马尔可夫模型10
实验中的几个要点

„不能直接观察瓮间的转移

„从瓮中所选取的球的颜色和瓮并不是一
一对应的

„每次选取哪个瓮由一组转移概率决定

隐马尔可夫模型11
HMM的组成

五元组：λ=(N,M,A,B,π)

简记为：λ=(A,B,π)

N：状态数目
M：可能的观察值数目
A：与时间无关的状态转移概率矩阵
B：给定状态下，观察值概率分布
π：初始状态空间的概率分布

隐马尔可夫模型12
状态转移概率矩阵

A=aij

aij=P(qt=Sj|qt−1=Si)，1≤i,j≤N

N
，
aij≥0∑aij=1
j=1

隐马尔可夫模型13
观察值概率分布矩阵

从状态Sj观察到符号vk的概率分布矩阵：

B=bj(k)

bj(k)=P(Ot=vk|qt=Sj)，1≤j≤N，1≤k≤M

M
，
bj(k)≥0∑bj(k)=1
k=1

隐马尔可夫模型14
初始状态概率分布

π=πi

πi=P(q1=Si)，1≤i≤N

N
，
πi≥0∑πi=1
i=1

隐马尔可夫模型15
观察序列产生步骤

给定模型，观察序列可由
λ=(A,B,π)O=O1,O2,L,OT

以下步骤产生：

1.根据初始状态概率分布π=πi选择一初始状态q1