对典隐马尔可夫模型学习算法改进

STUDIESINCOLLEGEMATHEMA

Vol.9,No.4Jul.,3杜世平(四川农业大学生命科学与理学院数学 四川雅 摘要改进经典隐马尔可夫模型HMM)的状态转移和输出观测值的假设条件,并在经典隐马尔可夫模型的基础上导出新模型的学习算法.新算法避免了经典隐马尔可夫模型中状态转移概率和输出观测值概率计算时只关键 隐马尔可夫模型(HMM);学习算法;前向2后向算 中图分类 O211.63;G242.隐马尔可夫模型(HMM)已在语言识别中得到广泛应用.80年代末,开始用于生物信息学,如DNA序列的比对,基因寻找(识别)及蛋白质二级结构的预测等通常一个经典的HMM由以下几S={s1s2,⋯sNtqtqt∈s1s2,⋯sNV={v1v2,⋯vM},M表示每一个状态可观测到的不同符号(观测值)数A={aijaij=P(qt+1=sj|qt=si)

aij=1 aij≥0 1≤i≤N j=i中可见符号(观测值)B={bikbi(k)=P(ot=vk|qt=si) 1≤i≤N 1≤k≤ 初始状态分布:π={πiπi=P(q1=si)

πi=1,πi i=一个隐马尔可夫模型可以由五元组SVABπ完整描述ABSV的说因此一个隐马尔可夫模型通常简记为λ=(π,AB.从(1)(2)式可以看出经典的HMM作了两个重要假设Markov假设:tt+1输出值的Markov假设:在t时输出观测值的概率,只取决于当前时刻t所处的状态而与以前事实上这两种假设并不十分合理,因为任一时刻出现的观测输出矢量概率不仅依赖于系统当,而且依赖于系统在前一时刻所处的状态,本文对经典隐马尔可夫模型HMM)的状态转移和输出观测值的Markov假设条件作了改进,并在经典隐马尔可夫模型的基础上导出了新模型的前向2后向算法.本文假设隐藏的状态序列是一个二阶Markov链:在t时刻的状态向t+13收稿日期:2004-07-第9卷第4 杜世平:对经典隐马尔可夫模型学习算法的改 t,t-1,即aijk=P(qt+1=sk|qt=sj,qt-1=si,qt-2=⋯)=P(qt+1=sk|qt=sj,qt-1=si N其 aijk=1,aijk≥0,1≤i,j≤N.N表示模型中状态个数.同样特征观测矢量的概率不仅依k=bij(l)=P(ot=vl|qt=sj,qt-1=si),1≤i,j≤N,1≤l≤ 本文在假设条件(4(5)HMM,2后向算法.前向2后向算法是计算在给定模型λ的条件下产生观测序列O=o1,o2,⋯,oT的概率,即PO|λ).由(4):给定模型λ产生某一状态序列Q=q1q2,⋯,qT:P(Q|λ)=P(q1|λ)P(q2|q1,λ)P(q3|q1,q2,λ)⋯P(qT|qT-2,qT-1,λ)=πq1aq1

t其中πit=1siaij表示状态siϖsj的概率由(5)在该状态Q条件下(模型已给定)O:P(O|Q,λ)=P(o1|q1,λ)P(o2|q1,q2,λ)⋯P(oT|qT-1,qT,λ)=bq1(o1由(6(7)QO

t=P(O,Q|λ)=P(O|Q,λ)P(Q|λ)=πq1bq1(o1)aq1q2bq1q2(o2所以在给定模型λO

aqt-2qt-1qtbqt-1qt(ot)t=Tπq t=PO|λ)其运算量非常大需寻求更为简捷的算法.前向2后向算法就是这样一种高效的算法.首先定义前向变量αtij)=Po1o2,⋯otqt-1=siqt=sj|λ它是指在给定模型λ的条件to1o2,⋯ott-1sitsj的概率.前向变量αtij)α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)aijbij(o2),1≤i,jα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=N∑P(o1,o2,⋯,ot,qt-1=si,qt=sj|λ)P(ot+1,qt+1=sk|qt-1=si,qt=sj,λ)∑i=Nαt(i,j)P(qt+1=sk|qt-1=si,qt=sj,λ)P(ot+1|qt=sj,qt+1=sk,λ)i=Nαt(i,j)aijkbjk(ot+1) 2≤t≤T-1 1≤j,k≤Ni= 20067定义后向变量βtij)=Pot+1ot+2,⋯oT|qt-1=siqt=sj,λ即在给定模型λt1sjtsjt+1可按如下步骤进行迭代计算: βT(i,j)=1 1≤i,j≤N β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,λ)∑k=N∑P(ot+1,qt+1=sk|qt-1=si,qt=sj,λ)P(ot+2,⋯,oT|qt=sj,qt+1=sk,λ)∑k=N∑P(qt+1=sk|qt-1=si,qt=sj,λ)P(ot+1|qt=sj,qt+1=sk,λ)βt+1(j,k)∑k=Naijkbjk(ot+1)βt+1(j,k) t=T-1,T-2,⋯, 1≤i,j≤Nk=在给定模型λ下产生观测序列O P(O|λ)=P(o1,o2,⋯,oT|λ)=∑∑P(o1,o2,⋯,ot,ot+1,⋯,oT,qt-1=si,qt=sj|λ)i=1j= 2≤t≤T-i=1j= PO|λ)=∑∑Po1o2,⋯otot+1,⋯oTqT-1=siqT=sj|λ)=∑∑αTiji=1j= i=1j=和输出观测值概率时只考虎当前状态而不考虑历史的简单假设,在实际问题中更具合理性.Jean2FrancoisMari,Jean-PaulHaton,AbdelazizKriouile.AutomaticwordRecognitionBasedon-orderHiddenMarkovModels[J].IEEETransactionsonspeechandAudioProcessing.vol.5,No.1-25,January,李海.二阶隐马尔可夫模型及其在计算语言学中的应用[J四川大学学报(自然科学版),200441(2):284-XiaLinLi,MarcParizeauandRejeanPlamondon.Training.HiddenMarkovModelswithMultiple—AcombinatorialMethod[J].IEEETransactiononPatternAnalysisandMachineIntelligence,Vol.22,No.4:371-377,April2000.L.R.Rabiner.AtutorialonHiddenMarkovModelsandselectedApplicationsinSpeech[J].ProcIEEE,Vol.77:257-286.Feb,BirneyE.HiddenMarkovModelsinBiologicalsequenceanylysis[J].IBM