在上一篇文章中留下了個尾巴是關于EM算法在HMM隱馬爾可夫模型的參數估計拓展上的應用.在學習EM算法以后,我們再去學習HMM的Baum-Weich算法就會相對的非常容易,Baum-Weich不過是EM算法的一種特例而已,這個算法是1972年提出的,Baum-Weich的出現甚至是早于EM算法的,這兩者的關系有興趣的同學.可以看看Satistical Methodsfor Speech Recognition,這里邊對于Baum- Welch和EM的關系有很完整的描述.
一:HMM的定義
隱馬爾科夫模型實際上是一個雙重的隨機過程,其中一重隨機過程不能直接被觀測到,通過狀態(tài)轉移概率矩陣描述,另一重隨機過程輸出可以觀測的觀測符號,這個是由輸出的概率來進行定義的.隱馬爾科夫的模型的參數”入”可以表示為一個五元組:
1;S是一組狀態(tài)的集合,S={1,2,.....N},而隨機序列X在t時刻所處的狀態(tài)為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)表示在狀態(tài)j時輸出符號v(k)的概率,即bj(k)=P(vk | j),k屬于[1,M],j屬于[1,N]
4:π=π(i)是初始概率分布,其中π = P(q1 = i)表示在時刻1時選擇狀態(tài)i的概率.
二:HMM研究的三個問題
1:估算問題:
在給定HMM的參數(S V A B π)和觀測序列O = (o1,o2,…..oT)的情況下,如何有效的計算出觀測序列的概率,即P(O | 入)?
2:解碼問題
在給定HMM的參數(S V A B π)和觀測序列O = (o1,o2,…..oT)的情況下,如何尋找一個狀態(tài)轉換序列q = (q1,q2,…..qT),使得該狀態(tài)轉換序列最有可能產生上述觀測序列?
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趨于穩(wěn)定就可以.
對于HMM的第三個問題(學習問題),隱含變量自然就是狀態(tài)的變量,要求狀態(tài)變量的期望值實際上就是求在t時刻隨機變量X所處狀態(tài)qt = i的概率,為了求這個概率,我們引入了向前變量和向后變量.
1:向前變量:
αt(i) = P(01,02,03,……0t,qt = i | 入),即給定模型參數”入”,在給定時間t的前提下,處在狀態(tài)i并且觀測序列為o1,o2,......ot的概率,那么顯然有:
2:向后向量
βt(i) = P(o(t+1),o(t+2),…….o(T) | qt = i, 入).即給定模型參數入,在時刻t,處在狀態(tài)i并且觀測序列為o(t+1),o(t+2),…….o(T) 的概率,那么顯然有:
3:E步
首先定義變量:
即給定參數模型”入”,和觀測序列O,在時刻t處在狀態(tài)i且時刻為t+1處在狀態(tài)為j的概率.進一步的話,可以寫成:
其次,定義變量:
表示的是在給定模型參數和觀測序列的前提下,t時刻處在狀態(tài)i的概率.
那么將t帶入上式,就有表示為狀態(tài)i轉移出去的次數的期望值,后部分表示為從狀態(tài)i到狀態(tài)j的次數的期望值.
4:M步
π(i)是表示在初始時刻出現狀態(tài)i的頻率的期望值,即有:
則同理可得:
a(i,j)表示的是從狀態(tài)i到狀態(tài)j的次數的期望值除以從狀態(tài)i轉移出去的次數的期望值,既有:
bj(k)是在狀態(tài)為j的情況下觀察到輸出值為k的次數的期望值除以其他所有狀態(tài)轉移到狀態(tài)j的次數的期望值,即有:
并且有:
這樣就引入新的參數λ = (A,B,π)再來計算向前變量at(i),向后變量Bt(i),ξ(i,j),然后這樣如此的循環(huán)迭代,直到前后兩次參數的變化量小于某個值為止.
5:算法的實現:
在這個部分,引用上邊的Baum-Welch算法,來做一個關于HMM的參數估計的例子.
現在假設一個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】.應用概率統(tǒng)計，2008伙窃，24(3):311—318.
張宏東 EM算法及應用【J】.山東大學學報
