文档介绍：隐马尔可夫模型简介
刘群
2001-6-11
X1
X2
XT
…………
O1
O2
OT
…………
假设
对于一个随机事件,有一个观察值序列:O1,...,OT
该事件隐含着一个状态序列:X1,...,XT
假设1:马尔可夫假设(状态构成一阶马尔可夫链) p(Xi|Xi-1…X1) = p(Xi|Xi-1)
假设2:不动性假设(状态与具体时间无关)
p(Xi+1|Xi) = p(Xj+1|Xj),对任意i,j成立
假设3:输出独立性假设(输出仅与当前状态有关) p(O1,...,OT | X1,...,XT) = Π p(Ot | Xt)
定义
一个隐马尔可夫模型(HMM) 是一个五元组:
(ΩX , ΩO, A, B, π)
其中:
ΩX = {q1,...qN}:状态的有限集合
ΩO = {v1,...,vM}:观察值的有限集合
A = {aij},aij = p(Xt+1 = qj |Xt = qi):转移概率
B = {bik},bik = p(Ot = vk | Xt = qi):输出概率
π= {πi}, πi = p(X1 = qi):初始状态分布
问题
令λ= {A,B,π} 为给定HMM的参数,
令σ= O1,...,OT 为观察值序列,
隐马尔可夫模型(HMM)的三个基本问题:
评估问题:对于给定模型,求某个观察值序列的概率p(σ|λ) ;
解码问题:对于给定模型和观察值序列,求可能性最大的状态序列;
学习问题:对于给定的一个观察值序列,调整参数λ,使得观察值出现的概率p(σ|λ)最大。
算法
评估问题:向前算法
定义向前变量
采用动态规划算法,复杂度O(N2T)
解码问题:韦特比(Viterbi)算法
采用动态规划算法,复杂度O(N2T)
学习问题:向前向后算法
EM算法的一个特例,带隐变量的最大似然估计
算法:向前算法(一)
定义前向变量为HMM在时间t输出序列O1…Ot,并且位于状态Si的概率:
算法:向前算法(二)
迭代公式为:
结果为:
变化
连续输出模型
输出矩阵变为某种概率分布,如高斯分布
多阶转移矩阵
例子:病情转化
假设:某一时刻只有一种疾病,且只依赖于上一时刻疾病一种疾病只有一种症状,且只依赖于当时的疾病
症状(观察值):发烧,咳嗽,咽喉肿痛,流涕
疾病(状态值):感冒,肺炎,扁桃体炎
转移概率:从一种疾病转变到另一种疾病的概率
输出概率:某一疾病呈现出某一症状的概率
初始分布:初始疾病的概率
解码问题:某人症状为:咳嗽→咽喉痛→流涕→发烧请问:其疾病转化的最大可能性如何?
例子:词性标注
问题:
已知单词序列w1w2…wn,
HMM模型:
将词性为理解为状态
将单词为理解为输出值
训练:
统计词性转移矩阵[aij]和词性到单词的输出矩阵[bik]
求解:Viterbi算法