隱馬爾科夫模型(原理圖解)

山東大學(xué)高性能計算與大數(shù)據(jù)處理學(xué)科組HighPerformanceComputingandBigDataProcessingGroup張慶科隱馬爾可夫模型原理圖解HiddenMarkovModels提綱HiddenMarkovModel隱馬爾科夫模型的三個問題總結(jié)13概率計算問題路徑預(yù)測問題2參數(shù)學(xué)習(xí)問題HiddenMarkovModel1馬爾可夫模型馬爾可夫模型是數(shù)學(xué)中具有馬爾可夫性質(zhì)的離散時間隨機過程，是用于描述隨機過程統(tǒng)計特征的概率模型。S2S3S1……SNS1t=1t=2t=3t=T-1t=T……………S1S2S3SNS1S2S3SNS1S2S3SNS1S2S3SNS1S2S3SN……………S1S2S3SN系統(tǒng)狀態(tài)數(shù)目(N個)S2S3S1S1SN一條馬爾可夫鏈狀態(tài)序列=觀測序列2.一階馬爾可夫模型概念t=1t=2t=3t=4t=5S1S2S3S1S2S3系統(tǒng)狀態(tài)數(shù)目(N=3)一階馬爾可夫模型（MarkovModels）S1S2S3S1S2S3S1S2S3S1S2S3a11a12a13a22a21a23a31a33a32a11a12a22a21a23a33a32a11a12a22a21a23a33a32a11a12a22a21a23a33a32下時期狀態(tài)只取決于當前時期狀態(tài)和轉(zhuǎn)移概率從某時刻狀態(tài)到下時刻的狀態(tài)按一定概率轉(zhuǎn)移t-1時刻t時刻qt-1qtqt-1qt…q1q2q3t-1時刻t時刻晴陰雨T=1T=2T=33.隱馬爾可夫模型t=1t=2t=3t=T-1t=T……………S1S2S3SNS1S2S3SNS1S2S3SNS1S2S3SNS1S2S3SN……………S1S2S3SN隱藏狀態(tài)S2S3S1S1SNt=1t=2t=3t=T-1t=T…觀測狀態(tài)Q1Q2QM…Q1Q2QM…Q1Q2QM…Q1Q2QM…Q1Q2QM…Q1Q2隱藏狀態(tài)序列觀察狀態(tài)序列Q1QMQ2QM…………HMM狀態(tài)序列≠觀測序列Q1QM一般隨機過程馬兒科夫過程t=1t=2t=3t=4t=5S1S2S3一階隱馬爾可夫模型（HiddenMarkovModels）圖解S1S2S3S1S2S3S1S2S3S1S2S3a11a12a13a22a21a23a31a33a32a11a12a22a21a23a33a32a11a12a22a21a23a33a32a11a12a22a21a23a33a32下時期狀態(tài)只取決于當前時期狀態(tài)和轉(zhuǎn)移概率從某時刻狀態(tài)到下時刻的狀態(tài)按一定概率轉(zhuǎn)移t-1時刻t時刻qt-1qt4.隱馬爾可夫模型(HiddenMarkovModels,HMM)Q3Q4Q1Q1O2I-隱藏狀態(tài)轉(zhuǎn)移概率生成概率b2(Q3)b3(Q4)b1(Q1)b1(Q1)b2(Q2)II-觀察序列S2S3S1S1S2qt-1qt…q1q2q3t-1時刻t時刻T=1T=2T=3t=1t=2t=3t=T-1t=TS1S2S3S1S2SNS1S2SNS1S2SNS1S2SNO1O2O3OT-1S2SNS1S1S25.隱馬爾可夫模型(HiddenMarkovModels,HMM)HMM模型五元組表示：λ

＝（N,M,π,A,B）用來描述HMM，或簡寫為λ=(π,A,B)一階隱馬爾可夫模型（HiddenMarkovModels）數(shù)學(xué)定義

………………OT………A轉(zhuǎn)移概率矩陣OMOMOMOMOM……………B生成概率矩陣πNM提綱HiddenMarkovModel隱馬爾科夫模型的三個問題總結(jié)13概率計算問題路徑預(yù)測問題2參數(shù)學(xué)習(xí)問題概率計算問題t=1t=2t=3t=T-1t=TS1S2S3S1S2SNS1S2SNzS1S2SNS1S2SNa11a12a13a22a21a23aN1aNNaN2a11a12a22a21a23a33a32a11a12a22a21a23a33a32O1O2O3OT-1……………OT…A轉(zhuǎn)移概率矩陣B生成概率矩陣問題1：給定觀察序列O=O1,O2,…,OT,以及模型λ=(π,A,B),計算P(O|λ)？πa01a02a0N…Π：初始概率向量1.隱馬爾可夫模型-全概率計算S2…問題本質(zhì)：計算產(chǎn)生觀測序列O的所有可能的狀態(tài)序列對應(yīng)的概率之和共NT個可能路徑（指數(shù)級計算）N=5,T=100,=>計算量10^72t=1t=2t=3S1S2S1S2S1S2BES4S4S4S5S5S5S3S3S3t=4S1S2S4S5S3a01a02a03a04a05aT1aT2aT3aT4aT5O1O2O3O4前向算法后向算法問題1：給定觀察序列O=O1,O2,…,OT,以及模型λ=(π,A,B),如何計算P(O|λ)？SkSkS1SNOt……S1……SNSkS1SN0t-1OT

tT0SkS1SN……1O1……………………………………初始化階段(t=1)中間遞歸階段（t=2,…,T）結(jié)束階段2.概率計算問題：前向算法（ForwardAlgorithm）前進Ot-1前進N=5,T=100,=>計算量3000SkOt+1S1……SNSkS1SN0OT

tT0SkS1SN……1O1...……………問題1：給定觀察序列O=O1,O2,…,OT,以及模型λ=(π,A,B),如何計算P(O|λ)？3.概率計算問題：后向算法（ForwardAlgorithm）OtSkS1SN……t+1……...…...……………后退后退初始化階段(t=T)中間遞歸階段（t=T-1,…,2,1）結(jié)束階段提綱HiddenMarkovModel隱馬爾科夫模型的三個問題總結(jié)13概率計算問題路徑預(yù)測問題2參數(shù)學(xué)習(xí)問題路徑預(yù)測問題1.隱馬爾可夫模型-路徑預(yù)測問題2：給定觀察序列O=O1,O2,…,OT,以及模型λ,如何推測最可能的狀態(tài)序列S?t=1t=2t=3t=T-1t=TS1S2SNS1S2SNS1S2SNzS1S2SNS1S2SNaN1……………A轉(zhuǎn)移概率矩陣B生成概率矩陣πa01a02a0N…Π：初始概率向量S2…問題本質(zhì)：計算產(chǎn)生觀測序列O的最可能的一條隱藏狀態(tài)序列QO1O2O3OT-1OT…已知觀察序列？解決方法：Viterbi算法S2SNS1S1S2viterbi算法t=1t=2t=3S1S2S1S2S1S2BES4S4S4S5S5S5S3S3S3t=4S1S2S4S5S3a01a02a03a04a05a1-0a2-0a3-0a4-0a5-0O1O2O3O42.隱馬爾可夫狀態(tài)路徑預(yù)測：Viterbi算法t=1t=2t=3S1S2S1S2S1S2BES4S4S4S5S5S5S3S3S3t=4S1S2S4S5S3a01a02a03a04a05a1-0a2-0a3-0a4-0a5-0O1O2O3O4動畫演示：由Viterbi算法計算產(chǎn)生觀測序列O的最可能的一條隱藏狀態(tài)序列QSkSkS1SNOt……S1……SNSkS1SN0t-1時刻OT

t時刻T時刻0SkS1SN……1時刻O1…………………………………初始化階段(t=1)中間遞歸階段（t=2,…,T）結(jié)束階段Ot-1問題2：給定觀察序列O=O1,O2,…,OT,以及模型λ,如何推測最可能的狀態(tài)序列S?Max……S1SNSkS1S？S？S？S1……Max路徑回溯向量3.預(yù)測隱馬爾可夫狀態(tài)路徑：Viterbi算法表示t時刻，沿狀態(tài)路徑{q1,q2,…,qt},且qt=Sk時，產(chǎn)生已知的觀察序列的前面t個子序列{o1,o2,…,ot}的最大概率值表示t時刻，到達隱狀態(tài)sk，且其<dela概率*轉(zhuǎn)移概率>乘積最大的那個狀態(tài)對應(yīng)的標記序號值。路徑回溯提綱HiddenMarkovModel隱馬爾科夫模型的三個問題總結(jié)13概率計算問題路徑預(yù)測問題2參數(shù)訓(xùn)練問題參數(shù)訓(xùn)練問題1.隱馬爾可夫模型-參數(shù)訓(xùn)練問題問題3：給定觀察值序列O,如何調(diào)整模型參數(shù)λ=(π,A,B),使得P(O|λ)最大?t=1t=2t=3t=T-1t=TS1S2SNS1S2SNS1S2SNzS1S2SNS1S2SNaN1……………A轉(zhuǎn)移概率矩陣B生成概率矩陣πa01a02a0N…Π：初始概率向量S2…問題本質(zhì)：參數(shù)λ=(π,A,B)的估值問題O1O2O3OT-1OT…已知觀察序列O？？？情形1：路徑已知時的參數(shù)估計

(監(jiān)督學(xué)習(xí)方法)情形2：路徑未知時的參數(shù)估計(非監(jiān)督學(xué)習(xí)方法)問題3：給定觀察值序列O,如何調(diào)整模型參數(shù)λ=(π,A,B),使得P(O|λ)最大?2.隱馬爾可夫模型-參數(shù)訓(xùn)練問題即：由最大似然估計法對HMM的參數(shù)進行估計S2S3S1S5S2S2S3S1S5V1V3V2V2V1V4V3V4V1?????V1V3V2V2V1V4V3V4V1????Baum-Welch算法（EM算法特例）對HMM參數(shù)估計轉(zhuǎn)移概率生成概率3.參數(shù)訓(xùn)練算法：Baum-Welch算法基礎(chǔ)(將乘