EM演算法學習(番外篇):HMM的參數估計

在上一篇文章中留下了個尾巴是關於EM演算法在HMM隱馬爾可夫模型的參數估計拓展上的應用.在學習EM演算法以後,我們再去學習HMM的Baum-Weich演算法就會相對的非常容易,Baum-Weich不過是EM演算法的一種特例而已,這個演算法是1972年提出的,Baum-Weich的出現甚至是早於EM演算法的,這兩者的關係有興趣的同學.可以看看Satistical Methodsfor Speech Recognition,這裡邊對於Baum- Welch和EM的關係有很完整的描述.

一:HMM的定義

隱馬爾科夫模型實際上是一個雙重的隨機過程,其中一重隨機過程不能直接被觀測到,通過狀態轉移概率矩陣描述,另一重隨機過程輸出可以觀測的觀測符號,這個是由輸出的概率來進行定義的.隱馬爾科夫的模型的參數」入」可以表示為一個五元組:

1;S是一組狀態的集合,S={1,2,.....N},而隨機序列X在t時刻所處的狀態為q(t),並且q(t)屬於S.

2:V是一組輸出符號組成的集合,V={v1,v2,........,v(m)},而觀測序列o(t)屬於{v1,v2,........,v(m)},並且t在[1,T]之間.

3:B=bj(k)是輸出符號的概率分布

bj(k)表示在狀態j時輸出符號v(k)的概率,即bj(k)=P(vk | j),k屬於[1,M],j屬於[1,N]

4:π=π(i)是初始概率分布,其中π = P(q1 = i)表示在時刻1時選擇狀態i的概率.

二:HMM研究的三個問題

1:估算問題:

2:解碼問題

在給定HMM的參數(S V A B π)和觀測序列O = (o1,o2,…..oT)的情況下,如何尋找一個狀態轉換序列q = (q1,q2,…..qT),使得該狀態轉換序列最有可能產生上述觀測序列?

3:學習問題

在模型參數未知或者不準確的情況下,如何根據觀測序列O = (o1,o2,…..oT)得到模型參數或者是調整模型參數,即如何確定一組模型參數』入*』使得P(O | 入*)達到最大?

解決思路:

第二個問題可以用Viterbi演算法解決

上述兩個問題不再贅述

第三個問題:使用Baum-Welch(EM演算法)來去解決HMM的第三個問題

三:Baum-Welch演算法的原理和步驟

根據EM演算法的基本思路:隨機初始化一組參數0(o),然後根據後驗概率模型P(Y | X,0(0) )來更新隱含變數Y的期望E(Y),然後用E(Y)代替Y求出新的模型參數0(1),就這樣迭代直到0趨於穩定就可以.

對於HMM的第三個問題(學習問題),隱含變數自然就是狀態的變數,要求狀態變數的期望值實際上就是求在t時刻隨機變數X所處狀態qt = i的概率,為了求這個概率,我們引入了向前變數和向後變數.

1:向前變數:

αt(i) = P(01,02,03,……0t,qt = i | 入),即給定模型參數」入」,在給定時間t的前提下,處在狀態i並且觀測序列為o1,o2,......ot的概率,那麼顯然有:

2:向後向量

βt(i) = P(o(t+1),o(t+2),…….o(T) | qt = i, 入).即給定模型參數入,在時刻t,處在狀態i並且觀測序列為o(t+1),o(t+2),…….o(T) 的概率,那麼顯然有:

3:E步

首先定義變數:

即給定參數模型」入」,和觀測序列O,在時刻t處在狀態i且時刻為t+1處在狀態為j的概率.進一步的話,可以寫成:

其次,定義變數:

表示的是在給定模型參數和觀測序列的前提下,t時刻處在狀態i的概率.

那麼將t帶入上式,就有表示為狀態i轉移出去的次數的期望值,後部分表示為從狀態i到狀態j的次數的期望值.

4:M步

π(i)是表示在初始時刻出現狀態i的頻率的期望值,即有:

則同理可得:

a(i,j)表示的是從狀態i到狀態j的次數的期望值除以從狀態i轉移出去的次數的期望值,既有:

bj(k)是在狀態為j的情況下觀察到輸出值為k的次數的期望值除以其他所有狀態轉移到狀態j的次數的期望值,即有:

並且有:

這樣就引入新的參數λ = (A,B,π)再來計算向前變數at(i),向後變數Bt(i),ξ(i,j),然後這樣如此的循環迭代,直到前後兩次參數的變化量小於某個值為止.

5:演算法的實現:

現在假設一個HMM的模型的參數結構是(S V A B π),其中S={1,2,3},V={1,2},π = (0,1,0),A,B如圖:

我們首先由這個HMM模型生成20個觀測值作為O:

O = (1,2,1,2,1,2,1,2,1,1,1,1,12,1,2,1,2,1,2)

然後根據上邊的公式得到,可以進行更新,然後用這個20個的觀測值來去訓練模型然後進行參數估計,估計結果如下:

通過比較真正的參數和估計的參數,效果還是可以的,但是這還不夠,為了進一步的提高估計的精確率,我們增加觀測值,這一次我們用1000個觀測值,反正都是隨機生成的,訓練下參數,結果如下:

效果還不錯的,所以根據結果可以看見,增加樣本訓練量真的可以提高參數估計的精度,並且增加樣本數還可以減少迭代的次數,這個演算法還是很有效的.

好的,在完成這個以後,這個EM演算法的系列就徹底結束了,也希望小夥伴們可以多多指教,感激不盡.

參考資料:

Little R J A，Rubin D B.Statistical Analysis with Missing Data[M】.New York:Wiley and Sons，Inc.1987.

Zhao Z，Huang B，Liu F.Parameter estimation in batch process using EM

algorithm with particle filter[J].Computers&Chemical Engineering，2013， 57:159-172.bibitembibl4 Delyon B，Lavielle M，Moulines E.Convergence of a stochastic approximation version of the EM algorithm[J]。Annals of Statistics，1999:94-128.

岳佳，王士同.高斯混合模型聚類中EM演算法及初始化的研究【J】.微計算 機信息，2006(1lX):244-246.

陳婷。基於EM演算法的含缺失數據的參數估計【D】.大連理工大學，2008.

孫大飛，劉文舉.基於EM演算法的極大似然參數估iJ-!屎iff[J].河南大學學 報:自然科學版，2002，32(4):35-41.

孟麗新，劉洪.基於EM演算法約束條件下參數的估計【J】.東北師大學報: 自然科學版，2009，40(4):28-32.

羅季.Monte Carlo EM加速演算法【J】.應用概率統計，2008，24(3):311—318.

張宏東 EM演算法及應用【J】.山東大學學報

推薦閱讀：