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

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

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

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

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

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

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