課件收集人工智能hmm book ch

第8隱馬爾可夫模型HMM（HiddenMarkovModels）源于1970年代的研究，先在語(yǔ)音識(shí)別問(wèn)題中獲得成功應(yīng)用（[Rabiner1989]），后在其它如圖像處理、數(shù)字信號(hào)分析等研究領(lǐng)域中得到廣泛應(yīng)用。1990年代后，HMM模型在生物信息學(xué)研究領(lǐng)域中受到重視（[BaldiandBrunak2001]），在基HMMHMM序列變化的規(guī)律難以掌握，比如復(fù)雜的語(yǔ)音序列、混雜了多種有用信號(hào)和噪聲信號(hào)的數(shù)字信號(hào)序列等；又如，產(chǎn)機(jī)理和互作用律尚不分楚的列或蛋質(zhì)序列等等。HMM模型可以被視為一個(gè)字符序列發(fā)生器，模型中有許多狀態(tài)，狀態(tài)之間由有向線連“規(guī)律性”來(lái)自于狀態(tài)之間的連接方式（或稱(chēng)連接網(wǎng)絡(luò)），HMM模型的結(jié)構(gòu)，這一本章主要參考文獻(xiàn)為[Rabiner1989][BaldiandBrunak2001]HMMHMM的基本定HMM（1）N個(gè)狀態(tài)：S1,…,SNHMM的N個(gè)狀態(tài)，t時(shí)刻為當(dāng)前時(shí)刻，tqt就（2）M個(gè)字符：在t時(shí)刻，每個(gè)狀態(tài)都會(huì)從一個(gè)字符集{V1VM}中選擇一個(gè)字符發(fā)射出來(lái)，或稱(chēng)為觀測(cè)字符，記為ot。對(duì)蛋白質(zhì)序列分析問(wèn)題，這個(gè)字符集就是包含了20個(gè)氨基酸殘基符號(hào)的三字母字符集{Ala,Leu,Arg,Lys,Asn,Met,Asp,Phe,Cys,Pro,Gln,Ser,Glu,Thr,Gly,Trp,His,TyrIleVal}{AL,RKNM,D,FCPQSE,T,GWHYIV}

π：π={π1,…,πi=P{q1=Si} 1iπiq1iSi

A=aij=P{qt+1=Sj|qt=Si 1i,jaijtSiSjSi都有自己的狀態(tài)轉(zhuǎn)移概率分布{ai1,…,aiN}。這里的時(shí)間為離散時(shí)間。

B={bjbj(k)=P{ot=Vk|qt=Sj 1j 1kbj(k)表示狀態(tài)Sj每次發(fā)生字符Vk的概率，即每個(gè)狀態(tài)Sj都有自己的字符發(fā)生概率分布{t(1bj(Mj、k未知的情況下，bj(k)亦可寫(xiě)為bq(ot。由此，HMM模型可以簡(jiǎn)記為：tλ=(NMπ,AB 或λπ,ABHMM的運(yùn)（1）置t=πq1qt=Si的字符發(fā)生概率分布{bj(1),…,bj(M)}otqt=Si{ai1,…,aiN}qt+1=tt1tT，轉(zhuǎn)（3），否則結(jié)束。THMM的三個(gè)基本可能性問(wèn)題已知模型λ和觀列O，求由模型λ產(chǎn)生出序列O的概率P{O|λ}最佳路徑問(wèn)題已知模型λ和觀列O，求最有可能產(chǎn)生出序列O的狀態(tài)轉(zhuǎn)移序列問(wèn)題的前提假設(shè)：對(duì)于一個(gè)確定的HMM模型λ=(π,A,B)，給定一個(gè)觀O=(o1,o2,…,λOP{O|λ}解法一：理論概率計(jì)算根據(jù)前面介紹的HMM運(yùn)行過(guò)程可知，HMM可能會(huì)有許多不同的運(yùn)行狀態(tài)轉(zhuǎn)移序列Q產(chǎn)生出相同的觀列O，某一特定的狀態(tài)轉(zhuǎn)移序列Q=(q1,q2,…,qT)產(chǎn)生出觀列O=(o1,o2,…,oT)的概率為：P{O|Q}P{Q|λOP{O|λ}

P{O|Q}P{Q|T其中的P{O|Q}為狀態(tài)序列Q產(chǎn)生出觀列O的條件概率TtP{Q|λ}為HMMλQP{Q|}qaqqaq11

T1P{O|λ}

12,,,qqqT

1

(2T-1)QNT(2T-1NT，加法總次數(shù)為(NT-1)，可見(jiàn)全概率P{O|λ}具有指數(shù)級(jí)的計(jì)算量。解法二：前向αt(i)HMMλ，tSit個(gè)字符的觀列為O(1,t)=(o1,o2,…,ot)的概率，t(i)P{O(1,t)(o1,o2,,ot),qtSi|N其中，O(m,n)表示觀列從第m個(gè)字符到第n個(gè)字符的連續(xù)子序列，則全概NP{O|}TTαT(i)注意，前向變量αt(i)定義式中的t時(shí)刻的觀列O(1,t)=(o1,o2,…,ot)為給定觀列Oo1o2oT)t(1tT)i(1iN)為前向變量αt(i)的參變量，遞推方式計(jì)算前向變量αt(i)的步驟。1(i)ibi(o1

1i該式計(jì)算當(dāng)t=1時(shí)刻，各狀態(tài)發(fā)出給定觀列O第一個(gè)字符o1的概率 (j)

b(o

1jN

t1,2,,Tt

i

ij

tαt+1(j)表示t+1時(shí)刻，當(dāng)前狀態(tài)為Sj，觀列為O(1,t+1)=(o1,o2,…,ot,ot+1)的概率；當(dāng)前（t+1時(shí)刻）Sj的前一個(gè)（t時(shí)刻）N個(gè)狀態(tài)中的任何一個(gè)，假設(shè)為SiSi轉(zhuǎn)移到Sj前t個(gè)字符的觀列為(o1,o2,…,ot)的概率為αt(i)aij；若Sj是從哪個(gè)狀態(tài)轉(zhuǎn)移來(lái)，只保達(dá)Sj時(shí)的前t個(gè)字符的 列為(o1,o2,…,ot)，這個(gè)概率NNtSjt+1ot+1bj(ot+1)αt+1j)NNP{O|}TN2TN(N+1)(T-1)+N次乘法，N(N-1)(T-1)解法三：后向定義后向變量βt(i)，表示對(duì)于給定HMM模型λ，在t時(shí)刻，當(dāng)前狀態(tài)為Si的條件下，從t+1時(shí)刻到終止T時(shí)刻的觀測(cè)子序列為O(t+1,T)=(ot+1,ot+2,…,t(i)P{O(t1,T)(ot1,ot2,,oT)|qtSi,前向算法的思想是求出每個(gè)狀態(tài)到t時(shí)刻為止時(shí)保證前t個(gè)輸出字符序列為O(1,t)=(o1,o2,…,ot)tt+1時(shí)刻開(kāi)始到終止時(shí)刻T，保證后T-t個(gè)輸出字符序列為O(t+1,T)=(ot+1,ot+2,…,oT)的概率。T(i) 1iNNt(i)aij[bj(ot1)t1(j

1i

tT1,T后向變量βt+1(j)為在t+1時(shí)刻，當(dāng)前狀態(tài)為Sj的條件下，保證從t+2時(shí)刻到終止T時(shí)刻的觀O(t+2,T)=(ot+2ot+3,…,oT)的概率，這時(shí)，要求在t+1Sjot+1，來(lái)保證O(t+1,T)=(ot+1,ot+2,…,oT)，這個(gè)概率為bj(ot+1)βt+1(j)。即在t時(shí)刻，當(dāng)前狀態(tài)為Si的條件下，Si的后繼狀態(tài)（t+1時(shí)刻）為Sj并且從t+1時(shí)刻到終止T時(shí)刻的觀列為O(t+1,T)ot+1ot+2oT)的概率為bj(ot+1)βt+1(j)Si的后繼狀態(tài)（t+1時(shí)刻）也可以為其它狀態(tài)，所βt(i)Si的后繼狀態(tài)（t+1時(shí)刻）t+1T時(shí)刻的觀列為(ot+1,ot+2,…,oT)的概率，為將bj(ot+1)βt+1(j)以Si到Sj的狀態(tài)轉(zhuǎn)移概率aij為權(quán)按j=1,…,N求和。NNP{O|}ibi(o1)11(

NNj

ij

j)bai

3

1

β1(i)Si（t1時(shí)刻的當(dāng)前狀態(tài)）的后繼狀態(tài)（t2時(shí)刻）為何狀態(tài)，只要保證從t=2時(shí)刻到終止T時(shí)刻的觀列為O(2,T)=(o2,o3,…,oT)的概率；到這一步時(shí)，距離得到整個(gè)觀列O(1,T)=(o1,o2,…,oT)還差第1個(gè)字符o1，這第1個(gè)字符為t=1時(shí)刻的當(dāng)前狀態(tài)q1=Si發(fā)出的，字符發(fā)出概率為bi(o1)；而當(dāng)前狀態(tài)q1=Si是按初始狀態(tài)概率分布π：π={π1,…,πN}，πi=P{q1=Si} 1i{S1SN}P{O|}P{O(1,T)(o1,o2,,oT)|NP{q1Si}P{O(1,T)(o1,o2,,oT)|q1Si,NiNP{q1Si}P{O(1,1)(o1)|q1Si,NNi1P{O(2,T)(o2,,oT)|q1Si,Nibi(o1)1iViterbi前提假設(shè)：對(duì)于一個(gè)確定的HMM模型λ=(π,A,B)，給定一個(gè)觀O=(o1,o2,…,λOQP{QO|λ}取Q*(q*,q*,,q* tSi，已產(chǎn)生的序列為O(1,to1o2ot)的最可能路徑的概率定義為δt(i)：t(i)

Q(1,t1)(q1,,qt1qtSiO(1,t)(o1,,ot)|δt(i)計(jì)算的要點(diǎn)在于前t-1個(gè)狀態(tài)序列Q(1,t-1)的選擇，并且這個(gè)序列不是得到的，而t從小到大的次序遞推得到的。其中，Q(mn)Qmn個(gè)t-1Siδt-1(i)tSjδt(j(j)max

ab(o Spre[S

t

ij 其中，preSj]表示狀態(tài)Sj的前導(dǎo)狀態(tài)集。上式不但可以求出δt(j)t時(shí)刻Sjt-1時(shí)刻前導(dǎo)狀態(tài)Sipre[Sj]Q(1,t-1)=(q1,q2,…,qt-1)產(chǎn)生出δt(j)，記這個(gè)特別的前導(dǎo)狀態(tài)為ψt(Sj)：t(Sj){Sk

t1(k)akj

Sipre[Sj

t1(i)ψtSj)Viterbi1(i)ibi(o1)

1(Si)

1i2tTδt(j)ψt(Sj(j)max

(i)ab(o Spre[S

t

ij t(Sj){Sk

t1(k)akj

Sipre[Sj

t1(i)aij

1jP{Q*,O|}maxP{Q,O|}max

Tkq*{STk

allTT(k)maxTT1i

1i tq*t

t

)t)

tT1,TBaum-Welch前提假設(shè)：給定一個(gè)觀列O=(o1,o2,…,oT)HMMλπAB)P{O|λ}HMM模型的所有參數(shù)比如第9章中Marli的HMM模型有202個(gè)參（[Marlietal.2002]），一種能夠根據(jù)訓(xùn)練數(shù)據(jù)（這里為給定觀列O）對(duì)現(xiàn)有的模型參數(shù)進(jìn)行局部調(diào)整的計(jì)算程序，每執(zhí)行一次程序，目標(biāo)值都要更優(yōu)化一些，即P{O|λ}值更大一些，直到參數(shù)調(diào)整程序的執(zhí)行不解法：定義t(i,j)為在給定模型λ和觀列O的條件下，在t時(shí)刻模型狀態(tài)為Si，t+1Sjt(i,j)P{qtSi,qt1Sj|O,t(i,j)P{O|P{qtSi,qt1Sj|O,}P{O|P{qtSi,qt1Sj,O|P{O(1,t)(o1,,ot),O(t1,T)(ot1,,oT),qtSi,qt1Sj|P{O(1,t)(o1,,ot),qtSi|P{O(t1,T)(ot1,,oT),qt1Sj|O(1,t)(o1,,ot),qtSi,P{O(1,t)(o1,,ot),qtSi|P{O(t1,T)(ot1,,oT),qt1Sj|qtSi,P{O(1,t)(o1,,ot),qtSi|}P{qt1Sj|qtSi,P{O(t1,T)(ot1,,oT)|qt1Sj,qtSi,P{O(1,t)(o1,,ot),qtSi|}P{qt1Sj|qtSi,P{O(t1,T)(ot1,,oT)|qt1Sj,P{O(1,t)(o1,,ot),qtSi|}P{qt1Sj|qtSi,P{O(t1,t1)(ot1)|qt1Sj,P{O(t2,T)(ot2,,oT)|qt1Sj,t(i)aijbj(ot1)t1(t(i)P{O(1,t)(o1,o2,,ot),qtSi|t1(j)P{O(t2,T)(ot2,,oT)|qt1Sj,P{A,B|}P{A|B,}P{B|P{O(t1,T)(ot1,,oT),qt1Sj|O(1,t)(o1,,ot),qtSiP{O(t1,T)(ot1,,oT),qt1Sj|qtSiP{O(t1,T)(ot1,,oT)|qt1Sj,qtSiP{O(t1,T)(ot1,,oT)|qt1SjNi1jNt(i)aijbj(ot1)t1(i1j

(i,j)P{qtSi,qt1Sj,O| t(i)aijbj(ot1)t1(Nt(i)aijbj(ot1)t1(i1jt(ij)的計(jì)算原理如圖8.1aijbjt-αttβt+1(8.1t(ij)的計(jì)算示意圖（自[Rabiner定義γt(i)為在給定模型λ和觀列O的條件下，在t時(shí)刻模型狀態(tài)為Si的概率t(i)P{qtSi|O