P( o1 , o2 , …, ot , ot+1 , …, oT , qt- 1 = si , qt = sj | λ) =
i =1 j =1
NN
∑∑αt ( i , j)βt ( i , j) , 2 ≤t ≤ T - 1.
i =1 j =1
NN
NN
∑∑ ∑∑ 特别地 , P( O | λ) =
T
∏ P ( O , Q | λ) = P ( O | Q ,λ) P ( Q | λ) = πq1 bq1 ( o1 ) aq1 q2 bq1 q2 ( o2 )
a b ( o ) . qt- 2 qt- 1 qt qt- 1 qt
t
t =3
所以在给定模型λ下产生给定序列 O 的概率 :
T
∑ ∑ ∏ P( O | λ) =
k =1
N
∑aijk bjk ( ot+1 )βt+1 ( j , k) , t = T - 1 , T - 2 , …, 2. 1 ≤ i , j ≤ N .
k =1
31 3 在给定模型λ下 ,产生观测序列 O 的概率
根据前向变量和后向变量的定义可得
NN
∑∑ P(O | λ) = P( o1 , o2 , …, oT | λ) =
关键词 隐马尔可夫模型 ( HMM) ;学习算法 ;前向 2 后向算法 中图分类号 O211. 63 ; G242. 28
1 引言
隐马尔可夫模型 ( HMM) 已在语言识别中得到广泛应用. 80 年代末 ,开始用于生物信息学 ,如
DNA 序列的比对 ,基因寻找 (识别) 及蛋白质二级结构的预测等. 通常一个经典的 HMM 由以下几
(2)
5) 初始状态分布 :π = {πi } ,其中
N
∑ πi = P( q1 = si ) , πi = 1 , πi ≥0.
(3)
i =1
这样 ,一个隐马尔可夫模型可以由五元组 ( S ,V , A , B ,π) 完整描述. 由于 A , B 中包含了对 S ,V 的说
明 ,因此一个隐马尔可夫模型通常简记为λ = (π, A , B) .
序列 Q 条件下 (模型已给定) 产生观测序列 O 的概率 :
T
∏ P( O | Q ,λ) = P( o1 | q1 ,λ) P( o2 | q1 , q2 ,λ) …P( oT | qT- 1 , qT ,λ) = bq1 ( o1 ) bqt- 1 qt ( ot) .
(7)
t =2
由 (6) 、(7) 式可得状态序列 Q 与观测序列 O 同时发生的概率 :
N
∑ aij = P( qt+1 = sj | qt = si ) , aij = 1 , aij ≥0 , 1 ≤ i ≤ N .
(1)
j =1
4) 状态 i 中可见符号 (观测值) 的概率分布 :B = { bi ( k) } ,其中
bi ( k) = P( ot = vk | qt = si ) , 1 ≤i ≤ N , 1 ≤ k ≤ M .
2) 迭代计算 αt+1 ( j , k) = P ( o1 , o2 , …, ot , ot+1 , qt = sj , qt+1 = sk | λ) =
N
∑P ( o1 , o2 , …, ot , ot+1 , qt- 1 = si , qt = sj , qt+1 = sk | λ) =
i =1 N
第 9 卷第 4 期 杜世平 : 对经典隐马尔可夫模型学习算法的改进
59
态转移概率不仅依赖于 t 时刻的状态 ,而且依赖于 t - 1 时刻的状态 ,即 :
aijk = P ( qt+1 = sk | qt = sj , qt- 1 = si , qt- 2 = …) = P ( qt+1 = sk | qt = sj , qt- 1 = si )
的历史无关
事实上这两种假设并不十分合理 ,因为任一时刻出现的观测输出矢量概率不仅依赖于系统当 前所处的状态 ,而且依赖于系统在前一时刻所处的状态. 为了弥补这一缺点 ,本文对经典隐马尔可 夫模型 ( HMM) 的状态转移和输出观测值的 Markov 假设条件作了改进 ,并在经典隐马尔可夫模型 的基础上导出了新模型的前向 2 后向算法.
参考文献
[ 1 ] J ean2Francois Mari , J ean - Paul Haton , Abdelaziz Krio uile. A utom atic w ord Recognition B ase d on S econ d - or der H i d den M a rkov M odels [J ] . IEEE Transactions o n speech and Audio Processing. vol. 5 ,No . 1 :22 - 25 ,J anuary 1997.
31 1 前向算法
首先定义前向变量αt ( i , j) = P( o1 , o2 , …, ot , qt- 1 = si , qt = sj | λ) . 它是指在给定模型λ的条件
下 ,产生 t 以前的部分观测序列 o1 , o2 , …, ot ,且在 t - 1 时状态为 si , t 时状态为 sj 的概率. 前向变量αt ( i , j) 可按下列步骤进行迭代计算 :
(4)
N
∑ 其中 aijk = 1 , aijk ≥0 ,1 ≤i , j ≤N . N 表示模型中状态个数. 同样特征观测矢量的概率不仅依赖 k =1
于系统当前所处的状态 ,而且依赖于系统前一时刻所处的状态 ,即 :
bij ( l) = P( ot = vl | qt = sj , qt- 1 = si ) , 1 ≤ i , j ≤ N , 1 ≤ l ≤ M .
如下步骤进行迭代计算 :
1) 初始化 βT ( i , j) = 1 , 1 ≤i , j ≤ N .
2) 迭代计算
βt ( i , j) = P ( ot+1 , ot+2 , …, oT | qt- 1 = si , qt = sj ,λ) =
n
∑P ( ot+1 , ot+2 , …, oT , qt+1 = sk | qt- 1 = si , qt = sj ,λ) =
i =1 N
∑αt ( i , j) aijk bjk ( ot+1 ) , 2 ≤ t ≤ T - 1 , 1 ≤ j , k ≤ N .
i =1
© 1994-2007 China Academic Journal Electronic Publishing House. All rights reserved.
(5)
3 改进的学习算法
本文在假设条件 (4) 、(5) 的基础上对改进 HMM 的学习算法进行了研究 ,得出了改进的前向 2 后向算法. 前向 2后向算法是计算在给定模型λ的条件下产生观测序列 O = o1 , o2 , …, oT 的概率 ,即 P( O | λ) . 由 (4) 式可知 :给定模型λ,产生某一状态序列 Q = q1 , q2 , …, qT 的概率 :
P ( o1 , o2 , …ot , ot+1 , …, oT , qT- 1 = si , qT = sj | λ) =
αT ( i , j) .
i =1 j =1
i =1 j =1
以上方法可以推广到 Viterbi 算法 、Baum2Welch 算法. 这些新算法避免了在计算状态转移概率
和输出观测值概率时只考虎当前状态而不考虑历史的简单假设 ,在实际问题中更具合理性.
60
高等数学研究 2006 年 7 月
31 2 后向算法
与前向算法相类似 ,定义后向变量βt ( i , j) = P( ot+1 , ot+2 , …, oT | qt- 1 = si , qt = sj ,λ) . 即在给定
模型λ和 t - 1 时状态为 sj , t 时状态为 s j 的条件下 ,从 t + 1 时到最后的部分观测序列的概率 ,可按
58
S TUD IES
IN
高等数学研究 COLL EGE MA T H EMA TICS
Vo l . J ul.
9 ,
,No . 4 2006
对经典隐马尔可夫模型学习算法的改进3
杜世平 (四川农业大学生命科学与理学院数学系 四川雅安 625014)
摘 要 改进经典隐马尔可夫模型 ( HMM) 的状态转移和输出观测值的假设条件 ,并在经典隐马尔可夫模型 的基础上导出新模型的学习算法. 新算法避免了经典隐马尔可夫模型中状态转移概率和输出观测值概率计算时只 考虑当前状态而不考虑历史的简单做法.
1) 初始化 α2 ( i , j) = P(o1 , o2 , q1 = si , q2 = sj | λ) = P(o1 , q1 = si | λ) P(o2 , q2 = sj | q1 = si λ, ) =
πibi (o1 ) P(q2 = sj | q1 = si λ, ) P(o2 | q1 = si , q2 = sj λ, ) = πibi (o1 ) aij bij (o2 ) , 1 ≤i , j ≤N.
2 问题的描述
本文假设隐藏的状态序列是一个二阶 Markov 链 :在 t 时刻的状态向 t + 1 时刻的状态转移的状
3 收稿日期 :2004 - 07 - 09 © 1994-2007 China Academic Journal Electronic Publishing House. All rights reserved.
P ( O , Q | λ) = πq1 bq1 ( o1 ) aq1 q2 ( o2 )