隱馬爾科夫模型學習總結(jié).pdf

1、隱馬爾科夫模型學習總結(jié)by terry_feng隱馬爾科夫模型，這個久違的老朋友。大三上學期在實驗室的時候，由于實驗室項目需用到語音識別，所以就使用了微軟的Microsoft Speech SDK，也關注了一下語音識別的原理，其中有以HMM作為模型進行識別的。后來實驗室的機器人項目中上位機的軟件使用到了人臉識別的功能。實驗室有關于識別的工程源代碼，但是工程龐大，結(jié)構(gòu)復雜，并且里面有很多沒有用到的功能，并且程序經(jīng)常莫名其妙的跑飛，還存在嚴重的內(nèi)存泄露問題。所以就自己另起爐灶，重新編寫上位機軟件。其中的人臉識別用到的核心算法的代碼就來源于這個工程。它使用到的技術不是PCA和LDA，而是HMM和DC

2、T。那時候為了看明白HMM實現(xiàn)的原理，在圖書館看了關于模式識別的書，但有基本都是工程相關的，所以說原理性的知識牽扯的不多，自己也就是學習了大概，只是摸熟了里面使用到的各種牛逼的算法，比如Forward-backward，Viterbi，Baum-Welch。但是各種算法原理的理解上就差得遠了。沒有什么理論的基礎，也不知如何學起，最終未能繼續(xù)。后來又通過吳軍老師的數(shù)學之美了解到隱馬爾科夫模型在語音識別中的重要作用。時隔快兩年了，從李航博士的統(tǒng)計學習方法中又看到了HMM模型的魅影，里面對其原理進行了深刻的剖析，能夠?qū)W習之內(nèi)心自是欣慰至極。于是便花了幾天的時間讀了關于HMM的幾章，現(xiàn)在算是有點收獲，

3、總結(jié)一下（大部分內(nèi)容來自對吳軍老師的數(shù)學之美和李航博士的統(tǒng)計學習方法的總結(jié)）。文章主要包括信息傳遞模型、HMM模型簡介，和對所使用的三個主要算法：前向后向算法、Baum-Welch算法和維特比算法進行了總結(jié)。由于公式比較的多所以生成pdf版的了。1、 信息傳遞的模型任何信息都是通過一定的媒介從一端傳遞到另一端。對于信息源的傳輸者來說，其所需傳輸?shù)男蛄锌杉僭O為S=s1,s2,s3,sn,而處于媒介另一端的觀測者觀測到的序列是O=o1,o2,o3,om。對于觀測者來說，他接收到序列O的目的是為了明白傳輸者的意圖，這樣才能達到信息交流的目的。也就是說，觀測者能夠做的事情就是使用觀測到的數(shù)據(jù)（即序列O

4、）去揣測傳輸者要傳輸?shù)臄?shù)據(jù)（即序列S）。但是僅僅根據(jù)序列O能夠揣測出來的序列S的可能性太多了，哪一個猜到的序列S是我們想要的呢？按照概率論的觀點，我們可以把上面的問題建立數(shù)學模型。P(S|O)=P(s1,s2,s3,sn|o1,o2,o3,om)上式的意思是：對于一個給定的觀測序列o1,o2,o3,om，它的原序列是s1,s2,s3,sn的概率。然而s1,s2,s3,sn的可能取值有很多，究竟哪一個才是自己想要的呢？所以便有了下面的式子：s1,s2,s3,sn=argmaxP(S|O) （1.1） all s1,s2,s3,sn也就是說找到概率最大的原序列，或者說是最有可能的原序列。利用貝葉斯

5、定理可以把上式轉(zhuǎn)化得：P(S|O)=P(o1,o2,o3,om|s1,s2,s3,sn)P(s1,s2,s3,sn)P(o1,o2,o3,om) （1.2）s1,s2,s3,sn=argmaxP(o1,o2,o3,om|s1,s2,s3,sn)P(s1,s2,s3,sn)all s1,s2,s3,sn（1.3）2、 隱馬爾科夫模型簡介2.1 馬爾科夫假設對于任意的狀態(tài)序列s1,s2,s3,sn，它的某一狀態(tài)出現(xiàn)的概率只與上一個狀態(tài)有關。就像預報天氣一樣，若要預報明天的天氣，就僅與今天的天氣作為參考，而不考慮昨天、前天或者更早的天氣情況（當然這樣不合理，但是確是簡化的模型），稱之為馬爾科夫假設。

6、所以可以得到：P(s1,s2,s3,sn)=n （2.1） tP(st|st1)2.2 獨立輸出假設對于任何一個可以觀測到的狀態(tài)ot，它只與一個st的狀態(tài)有關，而與其他的狀態(tài)s無關，稱之為獨立輸出假設。所以可以得到：P(o1,o2,o3,om|s1,s2,s3,sn)=n （2.2） tP(ot|st)由式1.3,2.1,2.2可得：s1,s2,s3,sn=argmaxP(o1,o2,o3,om|s1,s2,s3,sn)P(s1,s2,s3,sn) all s1,s2,s3,snn=P(st|st1)P(ot|st)t2.3 隱含馬爾科夫“隱”的含義2.4 隱含馬爾科夫模型的例子（選自李航博士

7、的統(tǒng)計學習方法P173，稍作修改）假設有4個盒子，Boxes=box1，box2，box3，box4，每個盒子里都裝有紅白兩種顏色的球，Colors=color1，color2，有兩個實驗者A和B（假設兩個實驗者未曾見面，只能通過電話聯(lián)系）。每個盒子里面球的個數(shù)為：Step1：實驗者A從4個盒子里面以等可能的概率隨機選取1個盒子，記錄其盒子s1；接著從這個盒子里抽取一個球，然后通過電話告知B所抽取的球的顏色，B記錄其顏色o1后，A將球放回原盒子中；Step2：A從當前的盒子轉(zhuǎn)移到下一個盒子，按照下面的概率矩陣轉(zhuǎn)移：st；接著從這個盒子里抽取一個球，然后通過電話告知B所抽取的球的顏色，B記錄其顏

8、色ot后，A將球放回原盒子中； Step3：繼續(xù)step2，直到記錄到的球數(shù)達到n。經(jīng)過以上的三個步驟，對于A來說，得到了盒子的序列S=s1,s2,s3,sn;對于B來說，得到了球的觀測序列O=o1,o2,o3,on。我們現(xiàn)在的就假設站在B的立場上分析這個問題。我們只得到了序列O（稱為觀測序列），而序列S（稱為狀態(tài)序列）對于我們來說是不知道的，所以我們稱之為隱含的。但是我們可以通過一定的模型來推斷序列S的分布，繼而求出最有可能的序列S，而這樣的一個模型可以有很多種，但是一種簡單的、容易計算的并且預測精度高的模型就非隱含馬爾科夫模型莫屬了。3、 隱馬爾科夫模型接下來就來總結(jié)一下關于隱馬爾科夫模型

9、的定義。3.1 定義隱馬爾科夫模型是關于時序的概率模型，描述由一個隱藏的馬爾科夫鏈隨機生成不可觀測的狀態(tài)隨機序列，再由各個狀態(tài)生成一個觀測而產(chǎn)生觀測隨機序列的過程。由隱馬爾科夫鏈生成的狀態(tài)隨機序列稱為狀態(tài)序列（state sequence）；每個狀態(tài)生成一個觀測，而由此產(chǎn)生的隨機序列，稱為觀測序列（observation sequence）。序列的每一個位置可以認為是一個時刻。隱馬爾科夫模型可以由初始概率分布、狀態(tài)轉(zhuǎn)移概率分布和觀測概率分布確定。隱馬爾科夫模型的形式定義如下：設Q是所有可能的狀態(tài)集合(N個狀態(tài))，V是所有可能的觀測的集合（M個觀測）。I是狀態(tài)序列（長度T），O是對應的觀測序列（

10、長度T）。A是狀態(tài)轉(zhuǎn)移矩陣A=aij，其中aij=P(it+1=qj|it=qi),i=N×N1,2,N;j=1,2,N是在時刻t處于qi狀態(tài)而在下一時刻t+1時刻處于qj的概率。B是觀測概率矩陣B=bj(k)N×M，其中bj(k)=P(ot=vk|it=qj),k=1,2,M;j=1,2,N是在時刻t狀態(tài)為qj的條件下生成觀測vk的概率。是初始狀態(tài)概率向量：=(i)，其中i=P(i1=qi),i=1,2,N是時刻t=1時處于狀態(tài)qi的概率。隱馬爾科夫模型就是有初始狀態(tài)、狀態(tài)轉(zhuǎn)移概率矩陣A和觀測概率矩陣B決定的。前兩者確定了隱馬爾科夫鏈，生成不可觀測的狀態(tài)序列，后者確定了如

11、何從狀態(tài)生成觀測序列。使用=(A,B,)表示隱馬爾科夫模型的參數(shù)。例如2.4中提到的例子里面，狀態(tài)集合Q為四個盒子Boxes，共4個狀態(tài)；觀測集合即為Colors，共2個觀測值；狀態(tài)轉(zhuǎn)移矩陣A可由表2所得A=3.2 3個基本問題1、概率計算問題給定模型=(A,B,)和觀測序列O=(o1,o2,oT)，計算在模型下觀測序列O出現(xiàn)的概率P(O|)。2、學習問題已知觀測序列O=(o1,o2,oT)，估計模型參數(shù)=(A,B,)使得在該模型的參數(shù)下觀測序列概率P(O|)最大。即用極大似然估計的方法估計參數(shù)。3、預測問題已知模型參數(shù)=(A,B,)和觀測序列O=(o1,o2,oT)，求在給定觀測序列的情況下

12、條件概率P(I|O)最大的狀態(tài)序列I=(i1,i2,iT)，即給定觀測序列，求最有可能對應的狀態(tài)序列。4、 概率計算問題我們首要的事情就是要解決概率計算的問題。4.1 直接計算法此方法比較的簡單，可以由下面的公式直接求得。P(O|)=P(O,I|)=P(O|I,)P(I|)其中P(O|I,)=bi1(o1)bi2(o2)biT(oT)、P(I|)=i1ai1i2ai2i3aiT1iT 所以最終上式為： IIP(O|)=i1ai1i2bi1(o1)ai2i3bi2(o2)aiT1iTbiT(oT)i1,i2,iT但是此公式計算量大，因為I的狀態(tài)共有N中，然后排列成長度為T的序列,排法共有NT，再

13、加上式子之前的取和運算符，時間復雜度為O(TNT)，所以這種算法不可行。4.2 前向算法這個算法將時刻t的狀態(tài)保存下來，然后利用遞推的原理計算出地t+1時刻的狀態(tài)，既而求出時刻T的狀態(tài)。前向概率的定義：給定隱馬爾科夫模型參數(shù)，定義到時刻t部分觀測序列o1,o2,ot且狀態(tài)為qi的概率為前向概率，記作：t(i)=P(o1,o2,ot,it=qi|)由上式可得，t+1時刻的前向概率為：Nt+1(i)=t(j)ajibi(ot+1)j=1其中中括號里面表示的是時刻t部分觀測序列o1,o2,ot且狀態(tài)為qj而時刻t+1時狀態(tài)為qi的聯(lián)合概率，而乘以觀測概率得到前向概率。這樣遞推可以得到T時刻的前向概率

14、為T(i)。而最終的概率公式是：NP(O|)=T(i)由于在t+1時刻的前向概率計算時用到了t時刻的前向概率，所以避免了重復計算，時間復雜度降低。時間復雜度為O(TN2)。 i=14.3 后向概率后向概率的定義：給定隱馬爾科夫模型參數(shù)，定義在時刻t且狀態(tài)為qi的前提下，從t+1到T的部分觀測序列為ot+1,ot+2,oT的概率為后向概率，記作：t(i)=P(ot+1,ot+2,oT|it=qi,)對t=T-1，T-2，1時刻：Nt(i)=aijbj(ot+1)t+1(j)j=1最終的概率公式是：NP(O|)=1b1(o1)1(i)常用概率計算：1、給定模型和觀測序列O，在時刻t處于狀態(tài)qi的概

15、率為：(i)(i)t(i)=t(t)() j=1tjtji=1 (4.1)2、給定模型和觀測序列O，在時刻t處于狀態(tài)qi而在時刻t+1處于qj的概率為：t(i,j)=t(i)aijbj(ot+1)t+1(i)i=1j=1t(i)aijbj(ot+1)t+1(i) (4.2)5、學習算法有兩種學習策略，一種是監(jiān)督式學習，另一種是非監(jiān)督式學習。其中監(jiān)督式學習比較的簡單，但是需要大量的人工標注訓練數(shù)據(jù)，代價高?，F(xiàn)在主要總結(jié)一下非監(jiān)督式學習。5.1 Baum-Welch算法對于隱馬爾科夫模型來說，我們能夠獲得的只是得到一連串的觀測序列O1,O2,OS，我們無法獲得狀態(tài)序列I（稱為隱變量I），而整個的學

16、習過程是要確定此模型的參數(shù)=(A,B,)。對于如此的含有隱變量的非監(jiān)督式學習一般使用EM算法。具體的推理過程可以參考統(tǒng)計學習方法第九章。下面給出Baum-Welch算法。輸入：觀測數(shù)據(jù)O=(o1,o2,oS)；輸出：=(A,B,)。Step1：初始化(0)對n=0，選取aij,bj(k)0,i0，得到模型(0)=(A(0),B(0),(0)；Step2：遞推。對n=1,2，T1(n+1)t=1t(i,j)aij=t=1tT1t=1,ot=vkt(j)bj(k)(n+1)=(j)t=1t(n+1)i=1(i)Step3：終止。得到模型參數(shù)(n+1)=(A(n+1),B(n+1),(n+1)。6、

17、預測算法有兩種預測的算法，近似算法和維特比算法。6.1 近似算法：近似算法的思想是：在每個時刻t選擇在該時刻對應的最有可能出現(xiàn)的狀態(tài)，然后將這樣的狀態(tài)組成狀態(tài)序列即為預測的結(jié)果。此算法計算簡單，但是有兩點問題：1、因為只是選擇了t時刻選擇了最優(yōu)可能性的狀態(tài)，但是未必能夠保證這整個狀態(tài)序列是最優(yōu)的；2、得到的狀態(tài)序列中可能兩個狀態(tài)中間的轉(zhuǎn)移概率為0。6.2 維特比算法維特比算法是現(xiàn)代數(shù)字通信中使用最頻繁的算法，同時也是很多自然語言處理的解碼算法。比如說拼音轉(zhuǎn)漢字和導航中尋找最短路徑算法。動態(tài)規(guī)劃的思想在維特比算法中體現(xiàn)的淋漓盡致，很好的解決了隱馬爾科夫模型預測的問題。維特比算法的思想可以概括為三

18、點：1、如果概率最大的路徑P（或者說最短路徑）經(jīng)過某個點xij，那么這條路徑上從起點S到xij的路徑Q，一定是S到xij的最短路徑。否則，則存在從S到xij的最短路徑R替代Q，然后從S到終點E就可以得到一個新的比P更短的路徑，這與之前的條件相矛盾；2、從S到E的路徑必定進過第t時刻的某個狀態(tài)，假定第t時刻有N個狀態(tài)，那么如果記錄了從S到第t個狀態(tài)的所有N個節(jié)點的最短路徑，最終的最短路徑必經(jīng)過其中的一條。這樣，在任何時刻t，只需要考慮非常有限條最短路徑即可。3、結(jié)合以上的兩點，假定當我們從狀態(tài)t進入狀態(tài)t+1時，從S到狀態(tài)t上各個節(jié)點的最短路徑已經(jīng)找到，并且記錄在這些節(jié)點上，那么在計算從起點S到第t+1狀態(tài)的某個節(jié)點xt+1j的最短路徑時，只要考慮從S到狀態(tài)t所有的N個節(jié)點的最短路徑，以及從這N個節(jié)點到xt+1j的距離即可?，F(xiàn)在引入兩個變量和。定義在時刻t狀態(tài)為i的所有單個路徑(i1,i2,it)中概率最大值為：t(i)=maxP(it=i,it1,i1,ot,o1|) i1,i2,it1由定義可得變量的遞推公式：t+1(i)=maxP(it+1=i,it,i1,ot+1,o1|)i1,i2