Return to site

隐马尔可夫模型HMM

「统计学习」系列

· 统计学习

今天我开始学习HMM (Hidden Markov model, 隐马尔可夫模型)。

HMM是可用于标注问题的统计学习模型,描述由潜在的马尔可夫链(Markov chain)随机生成预测序列的过程 ── 属于生成模型。

HMM在语音识别、NLP、生物信息表达(特别,基因研究)、模式识别等领域有着广泛应用。

定义

HMM由几个核心组成要求, 第一部分是序列信息:

  • 状态序列:隐藏的Markov chain随机生成的状态序列;    state sequence
  • 观测序列:每个状态会生成一个观测,由此产生一连串的观测记录, 叫做观测序列;  observation sequence
  • 位置标号:序列的每一个位置可以视作为一个时刻, 可以是等间距的时间序列, 也可以相隔不同分/时/秒的序列。
第二部分是概率变化信息, 「Cause」
  • 初始概率分布 
  • 状态转移概率分布
  • 观测概率分布

Q 是所有可能的状态集合, V 是所有可能的观测的集合:

Q = {q1,q2, ...qN}

V = {v1,v2, ...vM}

N 是状态集的状态数, M是所有可能的观测数。

以上面的取值空间, 状态序列I和对应的观测序列O:

I = (i1, i2, ... , iT)

O = (o1, o2, ... , oT)

A是状态转移概率矩阵:

A = [aij] N*N

其中 aij是 在t时刻 状态值是 qi 而在下一时间(t+1)状态值是 qj 的概率, 简称状态转移概率。

B是观测概率矩阵:

B = [bj(k)] N*M

bj(k)表示 状态在qj下生成观测的vk概率, k = 1,2, ... M, j = 1,2, ..., N

π 表示初始状态概率向量(初始条件):

π = (π i)

π i = P(i1=qi), i = 1, 2, ... N

即在时间t=1处于状态qi的概率

以上就是HMM的组成框架, 一个HMM由初始状态概率向量π、状态转移概率矩阵A、观测概率矩阵B三部分决定。 π和A决定状态序列, B决定观测序列。

λ= (A, B, π)

 

从定义可知, HMM作了两个基本假设:

(1) 齐次假设

假设隐藏的Markov Chain 在任意时刻t的状态只依赖于前一时刻的状态, 与历史无关, 也与时刻t无关。

(2)观测独立假设

假设任意时刻的观测只依赖于该时间的Markov状态, 与其他观测及状态无关。

HMM可以用于标注, 这时状态对应着标记。 标注问题是给定观测的序列, 预测其对应的标记序列。

可以假设标注问题是由HMM生成的, 这样我们可以利用HMM的学习与预测算法进行标注。

HMM的例子 - 盒子与球模型

假设有4个盒子, 各装有若干个红球和白球, 数目见下图:

按下面方法抽球: 产生一个球的颜色的观测序列: 开始,

从4个盒子随机选择一个, 从中抽出一个球, 记录其颜色后放回;

从当前盒子随机转移到下一个盒子, 转移规则是: 如果当前盒子是1号, 则下一个一定是盒子2, 如果当前盒子是2或3, 则分别以0.4和0.6概率转移到左边或右边的盒子, 如果是盒子4, 那么以0.5概率停留盒子4和转移到盒子3; 确定转移的盒子后, 再从中抽一个球, 记录其颜色并放回, 如此下去, 重复进行5次, 得到一个球的观测序列:

O = {红,红,白,白,红}

在这个过程中,观察者只能观测到球颜色的序列,不知道球分别是从哪个盒子取出来的,观测不到盒子序列。

首先拆解HMM中的三要素: 状态集合是

Q = 『盒子1, 盒子2, 盒子3,盒子4』 N=4

观测集合是

V=『红,白』, M=2

初始概率分布

π = 『0.25, 0.25, 0.25, 0.25』 T 

状态转移概率分布为

观测概率分布为

HMM的3个基本问题

(1) 概率计算问题

给定模型

λ= (A, B, π)

和观测序列『O = (o1, o2, ... , oT)』 计算在模型λ 下观测序列O出现的概率 P(O|λ)

(2)学习问题

已知O = (o1, o2, ... , oT),估计模型λ= (A, B, π)参数, 使得在该模型下观测

『O = (o1, o2, ... , oT)』概率P(O|λ)最大。 即用极大似然方法估计参数

(3)预测问题

也称为解码问题(decoding)。 已知模型λ= (A, B, π) 和观测『O = (o1, o2, ... , oT)』, 求给定观测序列条件概率 P(I|O)最大的状态序列I = (i1, i2, ... , iT) , 即以上面的盒子为例,预测出五个时刻的盒子来源。

HMM 计算与学习

1.概率计算方法

考虑有一个村庄,所有村民都有两种身体状态:健康或者发烧。 医生通过询问患者感受来确定是否健康。 村民只能回答自己的身体现象:正常没事、头晕及感冒。

医生认为,他的患者的健康可作为离散的Markov chain。 “健康”和“发烧”有两个状态--就像上面隐藏的未知盒子,但医生只能观察到表象。

问题求解, 给定模型下, 求某种观测序列出现的概率。

比如, 在上面的参数下, 求 『 头晕, 感冒, 正常』的概率是多少?

围绕这个问题, 先简单介绍『直接计算法』。

通过列出所有可能长度为T的状态序列,求各状态序列I与观测序列的联合概率, 然后对所有可能的状态序列法度和, 得到 P(O|λ)。

但这样做会有极大的计算量, 理论可行,而实践不允许。 (阶数是 O(TN^T)

2.前向算法

(1)输入:模型λ, 观测序列O

(2)输出:观测序列概率 P(O|λ)

根据初值 不断向后进行概率加权运算。

3.后向算法

在此处添加文本段落。

学习算法

Baum-Welch算法

以EM算法的视角, HMM模型事实上是一个含有隐变量的概率模型。

 

P(O|λ) = Sigma · P(O|I,λ) P(I|λ)

以EM算法的视角, HMM模型事实上是一个含有隐变量的概率模型。

All Posts
×

Almost done…

We just sent you an email. Please click the link in the email to confirm your subscription!

OK