1、,山東大學高性能計算與大數(shù)據(jù)處理學科組 High Performance Computing and Big Data Processing Group,張慶科,隱馬爾可夫模型原理圖解,Hidden Markov Models,提 綱,Hidden Markov Model,隱馬爾科夫模型的三個問題,總結,1,3,2,Hidden Markov Model,1馬爾可夫模型,馬爾可夫模型是數(shù)學中具有馬爾可夫性質(zhì)的離散時間隨機過程，是用于描述隨機過程統(tǒng)計特征的概率模型。,t=1,t=2,t=3,t=T-1,t=T,S1,S2,S3,SN,S1,S2,S3,SN,S1,S2,S3,SN,S1,S2,

2、S3,SN,S1,S2,S3,SN,系統(tǒng)狀態(tài)數(shù)目(N個),狀態(tài)序列=觀測序列,2. 一階馬爾可夫模型概念,t=1,t=2,t=3,t=4,t=5,S1,S2,S3,S1,S2,S3,系統(tǒng)狀態(tài)數(shù)目(N=3),一階馬爾可夫模型（Markov Models）,S1,S2,S3,S1,S2,S3,S1,S2,S3,S1,S2,S3,a11,a12,a13,a22,a21,a23,a31,a33,a32,a11,a12,a22,a21,a23,a33,a32,a11,a12,a22,a21,a23,a33,a32,a11,a12,a22,a21,a23,a33,a32,下時期狀態(tài)只取決于當前時期狀態(tài)和轉

3、移概率,從某時刻狀態(tài)到下時刻的狀態(tài)按一定概率轉移,t-1時刻,t時刻,qt-1,qt,q1,q2,q3,t-1時刻,t 時刻,晴,陰,雨,T=1,T=2,T=3,3. 隱馬爾可夫模型,t=1,t=2,t=3,t=T-1,t=T,S1,S2,S3,SN,S1,S2,S3,SN,S1,S2,S3,SN,S1,S2,S3,SN,S1,S2,S3,SN,S1,S2,S3,SN,隱藏狀態(tài),t=1,t=2,t=3,t=T-1,t=T,觀測狀態(tài),隱藏狀態(tài)序列,觀察狀態(tài)序列,HMM,狀態(tài)序列觀測序列,一般隨機過程,馬兒科夫過程,t=1,t=2,t=3,t=4,t=5,S1,S2,S3,一階隱馬爾可夫模型（Hi

4、dden Markov Models）圖解,S1,S2,S3,S1,S2,S3,S1,S2,S3,S1,S2,S3,a11,a12,a13,a22,a21,a23,a31,a33,a32,a11,a12,a22,a21,a23,a33,a32,a11,a12,a22,a21,a23,a33,a32,a11,a12,a22,a21,a23,a33,a32,下時期狀態(tài)只取決于當前時期狀態(tài)和轉移概率,從某時刻狀態(tài)到下時刻的狀態(tài)按一定概率轉移,t-1時刻,t時刻,qt-1,qt,4. 隱馬爾可夫模型(Hidden Markov Models,HMM),I-隱藏狀態(tài),轉移概率,生成概率,b2(Q3),b

5、3(Q4),b1(Q1),b1(Q1),b2(Q2),II-觀察序列,q1,q2,q3,t-1時刻,t 時刻,T=1,T=2,T=3,t=1,t=2,t=3,t=T-1,t=T,S1,S2,S3,S1,S2,SN,S1,S2,SN,S1,S2,SN,S1,S2,SN,OT-1,5. 隱馬爾可夫模型(Hidden Markov Models,HMM),HMM模型五元組表示： （ N, M, , A, B）用來描述HMM，或簡寫為 =( , A, B),一階隱馬爾可夫模型（Hidden Markov Models）數(shù)學定義,OT,N,M,提 綱,Hidden Markov Model,隱馬爾科夫模

6、型的三個問題,總結,1,3,2,t=1,t=2,t=3,t=T-1,t=T,S1,S2,S3,S1,S2,SN,S1,S2,SN,z,S1,S2,SN,S1,S2,SN,a11,a12,a13,a22,a21,a23,aN1,aNN,aN2,a11,a12,a22,a21,a23,a33,a32,a11,a12,a22,a21,a23,a33,a32,問題1：給定觀察序列O=O1,O2, ,OT,以及模型=(,A,B),計算P(O|)？,a01,a02,a0N,：初始概率向量,1. 隱馬爾可夫模型-全概率計算,S2,問題本質(zhì)：計算產(chǎn)生觀測序列O的所有可能的狀態(tài)序列對應的概率之和,共 N T 個

7、可能路徑（指數(shù)級計算）,N=5, T=100, = 計算量1072,t=1,t=2,t=3,B,E,t=4,a01,a02,a03,a04,a05,aT1,aT2,aT3,aT4,aT5,前向算法,后向算法,問題1：給定觀察序列O=O1,O2, ,OT,以及模型=(,A,B),如何計算P(O|)？,Sk,Sk,S1,SN,S1,SN,Sk,S1,SN,0,t-1,t,T,0,Sk,S1,SN,1,初始化階段(t = 1),中間遞歸階段（t = 2,T）,結束階段,2. 概率計算問題：前向算法（Forward Algorithm）,前進,前進,N=5, T=100, = 計算量3000,Sk,S

8、1,SN,Sk,S1,SN,0,t,T,0,Sk,S1,SN,1,.,問題1：給定觀察序列O=O1,O2, ,OT,以及模型=(,A,B),如何計算P(O|)？,3. 概率計算問題：后向算法（Forward Algorithm）,Sk,S1,SN,t+1,.,.,后退,后退,初始化階段(t = T),中間遞歸階段（t = T-1, 2,1）,結束階段,提 綱,Hidden Markov Model,隱馬爾科夫模型的三個問題,總結,1,3,2,1.隱馬爾可夫模型-路徑預測,t=1,t=2,t=3,t=T-1,t=T,S1,S2,SN,S1,S2,SN,S1,S2,SN,z,S1,S2,SN,S1

9、,S2,SN,aN1,a01,a02,a0N,：初始概率向量,S2,問題本質(zhì)：計算產(chǎn)生觀測序列O的最可能的一條隱藏狀態(tài)序列Q,已知觀察序列,解決方法：Viterbi算法,viterbi算法,t=1,t=2,t=3,B,E,t=4,a01,a02,a03,a04,a05,a1-0,a2-0,a3-0,a4-0,a5-0,2. 隱馬爾可夫狀態(tài)路徑預測：Viterbi算法,t=1,t=2,t=3,S1,S2,S1,S2,S1,S2,B,E,S4,S4,S4,S5,S5,S5,S3,S3,S3,t=4,S1,S2,S4,S5,S3,a01,a02,a03,a04,a05,a1-0,a2-0,a3-0,

10、a4-0,a5-0,O1,O2,O3,O4,動畫演示：由Viterbi算法計算產(chǎn)生觀測序列O的最可能的一條隱藏狀態(tài)序列Q,Sk,Sk,S1,SN,S1,SN,Sk,S1,SN,0,t-1時刻,t時刻,T時刻,0,Sk,S1,SN,1時刻,初始化階段(t = 1),中間遞歸階段（t = 2,T）,結束階段,路徑回溯,向量,3. 預測隱馬爾可夫狀態(tài)路徑：Viterbi算法,路徑回溯,提 綱,Hidden Markov Model,隱馬爾科夫模型的三個問題,總結,1,3,2,1. 隱馬爾可夫模型-參數(shù)訓練問題,問題3：給定觀察值序列O,如何調(diào)整模型參數(shù)=(,A,B),使得P(O|)最大 ?,t=1,

11、t=2,t=3,t=T-1,t=T,S1,S2,SN,S1,S2,SN,S1,S2,SN,z,S1,S2,SN,S1,S2,SN,aN1,a01,a02,a0N,：初始概率向量,S2,問題本質(zhì)：參數(shù)=(,A,B)的估值問題,已知觀察序列O,情形1：路徑已知時的參數(shù)估計 (監(jiān)督學習方法),情形2：路徑未知時的參數(shù)估計 (非監(jiān)督學習方法),問題3：給定觀察值序列O,如何調(diào)整模型參數(shù)=(,A,B),使得P(O|)最大 ?,2. 隱馬爾可夫模型-參數(shù)訓練問題,即：由最大似然估計法對HMM的參數(shù)進行估計,S2,S3,S1,S5,S2,S2,S3,S1,S5,?,?,?,?,?,?,?,?,?,Baum-

12、Welch算法（EM算法特例）對HMM參數(shù)估計,轉移概率,生成概率,3. 參數(shù)訓練算法：Baum-Welch算法基礎,(將乘積因子按定義展開),前向算法,后向算法,(將分子中的按其遞歸計算公式展開),前后向算法關系圖,4. 參數(shù)訓練算法：Baum-Welch算法（單觀測序列）,但在實際應用中,訓練一個HMM用到的觀測值序列往往不止一個,那么,對于多個觀測值序列訓練時,要對BW算法的重估公式進行修正.,A轉移概率矩陣,B生成概率矩陣,初始概率矩陣,A轉移概率矩陣,B生成概率矩陣,0-初始概率矩陣,5. 參數(shù)訓練算法：Baum-Welch算法（多觀測序列）,這種多觀測序列正好適用于蛋白質(zhì)家族序列中相關問題的解決：如多