隱馬爾科夫算法通俗解釋

HMM介紹（通俗易懂版）HiddenMarkovModels是一種統(tǒng)計信號處理方法，模型中包含2個序列和3個矩陣:狀態(tài)序列S、觀察序列0、初始狀態(tài)矩陣P、狀態(tài)轉(zhuǎn)移矩陣A、混淆矩陣B。舉個例子來說明。Examplel：你一個異地的朋友只做三種活動：散步、看書、做清潔。每天只做一種活動。假設天氣只有兩種狀態(tài)：晴和兩。每天只有一種天氣。你的朋友每天告訴你他做了什么，但是不告訴你他那里的天氣。某一周從周一到周五每天的活動分別是｛讀書，做清潔，散步，做清潔，散步｝----這就是觀察序列0,因為你可以觀察得到。從周一到周五的天氣依次是｛晴，兩，晴，晴，晴｝ 這就是狀態(tài)序列S，狀態(tài)序列是隱藏的，你不知道。根據(jù)長期統(tǒng)計，某天晴的概率是0.6,兩的概率是0.4。則P=[°-6°-4-O從晴轉(zhuǎn)晴的概率是0.7，從晴轉(zhuǎn)兩的概率是0.3。從兩轉(zhuǎn)晴的概率是0.4，從兩轉(zhuǎn)兩的概率是a—r0.70.3i0.6。貝U天氣晴時，散步的概率是0.4，看書的概率是0.3,做清潔的概率是0.3。天氣兩時，散步的概B—r0.40.30.3]率是0.1,看書的概率是0.4，做清潔的概率是0.5。則匸―該模型和實際情況有明顯不符的地方：用一簡單的狀態(tài)轉(zhuǎn)移矩陣A來表示狀態(tài)的轉(zhuǎn)移概率的前提是t時刻的狀態(tài)只跟t-1時刻的狀態(tài)有關(guān)，而實際上今天的天氣跟過去幾天的天氣都有關(guān)系，而且跟過去幾天的晴朗程度、兩量大小都有關(guān)系；混淆矩陣B認為今天的活動只跟今天的天氣有關(guān)系，實際上今天的活動跟過去幾天的活動也有關(guān)系，比如過去一周都沒有打掃房間，那今天做清潔的概率就大大增加。模型介紹完了。評估問題隱馬爾可夫模型中包含一個評估問題：已知模型參數(shù)，計算某一特定輸出序列的概率。通常使用forward算法解決。比如計算活動序列{讀書，做清潔，散步，做清潔，散步}出現(xiàn)的概率，就屬于評估問題。如果窮舉的話，觀察序列會有2人5種，需要分別計算它們出現(xiàn)的概率，然后找出概率最大的。窮舉法中有很多重復計算，向前算法就是利用已有的結(jié)果，減少重復計算。算法借助于一個矩陣Q[LEN][M],其中M是所有狀態(tài)的種數(shù)，Q[i][j]表示從第0天到第i天,滿足觀察序列，且第i天隱藏狀態(tài)為Sj的所有可能的隱藏序列的概率之和。最終所求結(jié)果為Q[LEN-1][0]+…+Q[LEN-1][M-1],即最后一天，所有隱藏狀態(tài)下，分別滿足觀察序列的概率值之和。比如Q[0][0]=p（第一天做衛(wèi)生且第一天晴）=p（天晴）*p（做衛(wèi)生|天晴）=P[0]*B[0][2]=0.6*0.3=0.18Q[0][1]=p（第一天做衛(wèi)生且第一天下雨）=p（下雨）*p（做衛(wèi)生|下雨）=P[1]*B[1][2]=0.4*0.5=0.2Q[1][0]=p（第一天做衛(wèi)生且第二天晴且第二天做衛(wèi)生）=p（第一天做衛(wèi)生且第二天晴）*p（天晴的情況下做衛(wèi)生）=p{p（第一天做衛(wèi)生且第一天晴）*p（從天晴轉(zhuǎn)天晴）+p（第一天做衛(wèi)生且第一天下雨）*p（從下雨轉(zhuǎn)天晴）}*p（天晴的情況下做衛(wèi)生）={Q[0][0]*A[0][0]+Q[0][1]*A[1][0]}*B[0][2]Q[1][1]=……可以看到計算Q矩陣的每i行時都用到了第i-1行的結(jié)果。解碼問題解碼問題是：已知模型參數(shù)，尋找最可能的能產(chǎn)生某一特定輸出序列O（LEN）的隱含狀態(tài)的序列。通常使用Viterbi算法解決。觀察序列長度為LEN，則隱藏狀態(tài)序列長度也是LEN，如果采用窮舉法，就有M^LEN種可能的隱藏狀態(tài)序列，我們要計算每一種隱藏狀態(tài)到指定觀察序列的概率，最終選擇概率最大的。窮舉法中有很多重復計算，Viterbi算法就是利用已有的結(jié)果，減少重復計算。跟評估問題非常相似，不同點在于評估算的是和，解碼算的是最大值。Viterbi算法主要就是在計算一個矩陣Q[LEN][M],其中Q[i][j]表示從第0天到第i天，滿足觀察序列，且第i天隱藏狀態(tài)為Sj的所有可能的隱藏序列的概率的最大值。另外還要建立一個矩陣Path[LEN][M],用來記錄狀態(tài)序列中某一狀態(tài)之前最可能的狀態(tài)。舉個例子，假如指定觀察序列是{讀書，做衛(wèi)生，散步，做衛(wèi)生，散步}求出現(xiàn)此觀察序列最可能的狀態(tài)序列是什么。Q[0][0]=P（第一天讀書且第一天晴）=P（天晴）*p（讀書|天晴）Path[0][0]=-1;Q[0][1]=p（第一天讀書且第一天下雨）=p（下雨）*p（讀書|下雨）Path[0][1]=-1;關(guān)鍵是從第二天開始，Q[1][0]表示：滿足'第一天讀書且第二天做衛(wèi)生且第二天晴”的所有可能的隱藏序列的概率的最大值。那么滿足''第一天讀書且第二做衛(wèi)生且第二天晴”的所有可能的隱藏序列有哪些呢？第二天是必須滿足晴天的，第二天之前的狀態(tài)可以任意變。則所有可能的隱藏序列就是''晴晴”和“雨晴”。實際上考慮第三天（及第三天以后）時，并不需要考慮''所有”可能的隱藏序列，而只需要考慮第二天的不同狀態(tài)取值，這是因為馬氏過程有無后效性--tm時刻所處狀態(tài)的概率只和tm-1時刻的狀態(tài)有關(guān)，而與tm-1時刻之前的狀態(tài)無關(guān)。Q[1][0]=max{p（第一天晴且第一天讀書且第二天晴且第二天做衛(wèi)生），p（第一天下雨且第一天讀書且第二天晴且第二天做衛(wèi)生）}=max{p（第一天讀書且第一天晴）*p（天晴轉(zhuǎn)天晴），p（第一天讀書且第一天下雨）*p（下雨轉(zhuǎn)天晴）}*p（做衛(wèi)生|天晴）=max{Q[0][0]*A[0][0]，Q[0][1]*A[1][0]}*B[0][2]假如Q[0][0]*A[0][0]<Q[0][1]*A[1][0],則Path[1][0]=1；假如Q[0][0]*A[0][0]>Q[0][1]*A[1][0]，則Path[1][0]=0。Q[1][1]=……可以看到計算Q矩陣的每i行時都用到了第i-1行的結(jié)果。Example2：(l自行練習用)這里設狀態(tài)數(shù)目為N；每個狀態(tài)有M個觀測值；n=(n1,n2,…，nN)為各狀態(tài)初始向量；A=(aij)NXN為狀態(tài)轉(zhuǎn)移概率矩陣；B-(bij)NXM為狀態(tài)觀測概率矩陣；0={o1,o2,…，oT}為觀測值序列；Q={q1,q2,…，qT}為狀態(tài)序列。要針對狀態(tài)觀測概率矩陣?圖7中在最初始HMM中和都采用隨機陣列表示且滿足下式條件^0<?r3<1且工戲=1￥0<5<1且另說=1事i=l (上傳者ps。Bij也滿足這個aij的這個條件)在假設狀態(tài)種類數(shù)和觀測種類數(shù)都為3的前提下。O:a,c,b,b,c,b,a,c,bA： ?：a20a60a20a25a25asoa25a50(X25a20a30asoa35a15asoa45a05aso7T：asoa25a25根據(jù)上述的HMM中viterbi算法可得:Q：1,2,2,2,2,222,2通過結(jié)合O（觀測）和Q（狀態(tài)）矩陣可發(fā)現(xiàn)B中在狀態(tài)1,2產(chǎn)生a,b,c的觀測值的概率與初試矩陣不符。O:a,c,b,b,c,b,a,c,bQ：1,2,2,2,2,2,2,2,2可見B中p（a/1）=1,p（b/1）=0,p（c/1）=0,p（a/2）=1/8=0.125,p（b/2）=4/8=0.5,p（c/2）=3/8=0.375,修正得:1.000aoooaooo125a5ooa375Cl450a050a5oo將新的矩陣B結(jié)合上述的OA口?作為初始值?通過Baum—Welch多序列訓練算法并結(jié)合前向一后向算法判斷＞u的收斂性即可得出模型參數(shù)ABn的最終估計值?從原理上可看出該方法要求樣本的觀測序列要盡量充分.后面的實驗會發(fā)現(xiàn)在較充分的樣本下該訓練方法得到使得對應的＞O接近全局最大的比較精確的HMM.F面給出兩種算法的Java代碼：（尚未測試，請自行驗證）packagehmm;/**@authorOrisundate2011-10-20*/importjava.util.ArrayList;importjava.util.Collections;publicclassHMM{ArrayListvString>state;ArrayListvString>observation;double]]P;double[][]A;double]]]]B;intM;intN;HMM(){//天氣只有兩種狀態(tài)：晴和兩。每天只有一種天氣。state=newArrayListvString>();state.add("sunny");state.add("rain");M=state.size();//活動只有三種：散步、看書、做清潔。每天只做一種活動。observation=newArrayList<String>();observation.add("walk");observation.add("read");observation.add("clear");N=observation.size();//初始狀態(tài)矩陣。某天晴的概率是0.6，兩的概率是0.4。P=newdouble]]{0.6,0.4};//狀態(tài)轉(zhuǎn)移矩陣。A=newdouble[M][];//從晴轉(zhuǎn)晴的概率是0.7，從晴轉(zhuǎn)兩的概率是0.3A[0]=newdouble]]{0.7,0.3};//從兩轉(zhuǎn)晴的概率是0.4，從兩轉(zhuǎn)兩的概率是0.61]=newdouble]]{0.4,0.6};//混淆矩陣B=newdouble]M]]];//天氣晴時，散步的概率是0.4，看書的概率是0.3，做清潔的概率是0.3。0]=newdouble]]{0.4,0.3,0.3};//天氣兩時，散步的概率是0.1,看書的概率是0.4,做清潔的概率是0.5。B[1]=newdouble]]{0.1,0.4,0.5};}publicdoubleforward(ArrayListvString>observe){doublerect=0.0;intLEN=observe.size();double[][]Q=newdouble[LEN][];//第一天計算，狀態(tài)的初始概率，乘上隱藏狀態(tài)到觀察狀態(tài)的條件概率。Q[0]=newdouble[M];for(intj=0;j<M;j++){Q[0][j]=P[j]*B[j][observation.indexOf(observe.get(0))];}//第一天以后的計算，首先從前一天的每個狀態(tài)，轉(zhuǎn)移到當前狀態(tài)的概率求和，然后乘上隱藏狀態(tài)到觀察狀態(tài)的條件概率。for(inti=1;i<LEN;i++){Q[i]=newdouble[M];for(intj=0;j<M;j++){doublesum=0.0;for(intk=0;k<M;k++){sum+=Q[i-1][k]*A[k][j];}Q[i][j]=sum*B[j][observation.indexOf(observe.get(i))];}}for(inti=0;i<M;i++)rect+=Q[LEN-1][i];returnrect;}publicArrayList<String>viterbi(ArrayList<String>observe){ArrayList<String>sta=newArrayList<String>();intLEN=observe.size();double]]]]Q=newdouble[LEN][];int[][]Path=newint[LEN][];//第一天計算，狀態(tài)的初始概率，乘上隱藏狀態(tài)到觀察狀態(tài)的條件概率。Q[0]=newdouble[M];Path[0]=newint[M];for(intj=0;j<M;j++){Q[0][j]=P[j]*B[j][observation.indexOf(observe.get(0))];Path[0][j]=-1;}〃第一天以后的計算，首先從前一天的每個狀態(tài)，轉(zhuǎn)移到當前狀態(tài)的概率的最大值,然后乘上隱藏狀態(tài)到觀察狀態(tài)的條件概率。for(inti=1;i<LEN;i++){Q[i]=newdouble[M];Path[i]=newint[M];for(intj=0;j<M;j++){doublemax=0.0;intindex=0;for(intk=0;k<M;k++){if(Q[i-1][k]*A[k][j]>max){max=Q[i-1][k]*A[k][j];index=k;}}Q[i][j]=max*B[j][observation.indexOf(observe.get(i))];Path[i][j]=index;}}//找到最后一天天氣呈現(xiàn)哪種狀態(tài)的概率最大doublemax=0;intindex=0;for(inti=0;i<M;i++){if(Q[LEN-1][i