1、隱馬爾科夫模型Hidden Markov Model(HMM)王成（副教授）計算機科學與技術學院提 綱隱馬爾科夫模型的三個問題應用領域14概率計算問題路徑預測問題3參數學習問題一階馬爾可夫模型（Markov Models）隱馬爾科夫模型Hidden Markov Model2數學類：概率論、組合數學、矩陣論計算機類：數據結構、算法導論、MATLAB、Mathematica、C/C+等編程技術問題背景：基因遺傳學、遺傳病學、生態學、人口學與馬爾可夫模型(Markov Models)相關的課程1馬爾可夫模型馬爾可夫模型是數學中具有馬爾可夫性質的離散時間隨機過程，是用于描述隨機過程統計特征的概率模型

2、。S2S3S1SNS1t=1t=2t=3t=T-1t=TS1S2S3SNS1S2S3SNS1S2S3SNS1S2S3SNS1S2S3SNS1S2S3SN系統狀態數目(N個)S2S3S1S1SN一條馬爾可夫鏈狀態序列=觀測序列馬氏鏈模型 系統在每個時期所處的狀態是隨機的 從一時期到下時期的狀態按一定概率轉移 下時期狀態只取決于本時期狀態和轉移概率 已知現在，將來與過去無關（無后效性）描述一類重要的隨機動態系統（過程）的模型馬氏鏈 (Markov Chain)時間、狀態均為離散的隨機轉移過程t=1t=2t=3t=4t=5S1S2S3S1S2S3系統狀態數目(N=3)一階馬爾可夫模型（Markov

3、Models）S1S2S3S1S2S3S1S2S3S1S2S3a11a12a13a22a21a23a31a33a32a11a12a22a21a23a33a32a11a12a22a21a23a33a32a11a12a22a21a23a33a32下時期狀態只取決于當前時期狀態和轉移概率從某時刻狀態到下時刻的狀態按一定概率轉移t-1時刻t時刻qt-1qtqt-1qtq1q2q3t-1時刻t 時刻晴陰雨T=1T=2T=3一階馬爾科夫模型設有n個狀態，其中第i個狀態記作wi。在任意時刻t的狀態記作w(t)。一個長度為T的狀態序列記作wT=w(1),w(2),w(T)。例如有一個狀態序列可能是：w6=w1

4、,w4,w2,w2,w1,w4。從狀態t遷移到狀態t+1的概率：P(wj(t+1)|wi(t)記作aij。比如：馬氏鏈模型 系統在每個時期所處的狀態是隨機的 從一時期到下時期的狀態按一定概率轉移 下時期狀態只取決于本時期狀態和轉移概率 已知現在，將來與過去無關（無后效性）描述一類重要的隨機動態系統（過程）的模型馬氏鏈 (Markov Chain)時間、狀態均為離散的隨機轉移過程通過有實際背景的例子介紹馬氏鏈的基本概念和性質例1. 人的健康狀況分為健康和疾病兩種狀態，設對特定年齡段的人，今年健康、明年保持健康狀態的概率為0.8, 而今年患病、明年轉為健康狀態的概率為0.7，1. 健康與疾病 人的

5、健康狀態隨著時間的推移會隨機地發生轉變 保險公司要對投保人未來的健康狀態作出估計, 以制訂保險金和理賠金的數額 若某人投保時健康, 問10年后他仍處于健康狀態的概率Xn+1只取決于Xn和pij, 與Xn-1, 無關狀態與狀態轉移狀態轉移具有無后效性 120.80.20.30.7 n 0a2(n) 0 a1(n) 1設投保時健康給定a(0), 預測 a(n), n=1,2設投保時疾病a2(n) 1 a1(n) 0 n時狀態概率趨于穩定值，穩定值與初始狀態無關3 0.778 0.222 7/9 2/9 0.7 0.77 0.777 0.3 0.23 0.223 7/9 2/9 狀態與狀態轉移120

6、.80.20.30.710.80.220.780.221230.10.0210.80.250.180.65例2. 健康和疾病狀態同上，Xn=1 健康, Xn=2 疾病p11=0.8, p12=0.18, p13=0.02 死亡為第3種狀態，記Xn=3健康與疾病 p21=0.65, p22=0.25, p23=0.1 p31=0, p32=0, p33=1 n 0 1 2 3 a2(n) 0 0.18 0.189 0.1835 a3(n) 0 0.02 0.054 0.0880 a1(n) 1 0.8 0.757 0.7285 設投保時處于健康狀態，預測 a(n), n=1,2 不論初始狀態如何

7、，最終都要轉到狀態3 ； 一旦a1(k)= a2(k)=0, a3(k)=1, 則對于nk, a1(n)=0， a2(n)=0, a3(n)=1, 即從狀態3不會轉移到其它狀態。狀態與狀態轉移00150 0.1293 0.0326 0.8381 馬氏鏈的基本方程基本方程馬氏鏈的兩個重要類型 1. 正則鏈 從任一狀態出發經有限次轉移能以正概率到達另外任一狀態（如例1）。w 穩態概率馬氏鏈的兩個重要類型 2. 吸收鏈 存在吸收狀態（一旦到達就不會離開的狀態i, pii=1）,且從任一非吸收狀態出發經有限次轉移能以正概率到達吸收狀態（如例2）。有r個吸收狀態的吸收鏈的轉移概率陣標準形式R有非零元素y

8、i 從第 i 個非吸收狀態出發，被某個吸收狀態吸收前的平均轉移次數。2. 基因遺傳背景 生物的外部表征由內部相應的基因決定。 基因分優勢基因d 和劣勢基因r 兩種。 每種外部表征由兩個基因決定，每個基因可以是d, r 中的任一個。形成3種基因類型：dd 優種D, dr 混種H, rr 劣種R。 基因類型為優種和混種, 外部表征呈優勢；基因類型為劣種, 外部表征呈劣勢。生物繁殖時后代隨機地（等概率地）繼承父、母的各一個基因，形成它的兩個基因。父母的基因類型決定后代基因類型的概率完全優勢基因遺傳父母基因類型決定后代各種基因類型的概率父母基因類型組合后代各種基因類型 的概率DDRRDHDRHHHRD

9、RH1000011 / 21 / 200101 / 41 / 21 / 401 / 21 / 23種基因類型：dd優種D, dr混種H, rr劣種R完全優勢基因遺傳P(DDH)=P(dddd,dr)=P(ddd)P(ddr)P(RHH)=P(rrdr,dr)=P(rdr)P(rdr)=11/2=1/2=1/21/2=1/4隨機繁殖 設群體中雄性、雌性的比例相等，基因類型的分布相同（記作D:H:R） 每一雄性個體以D:H:R的概率與一雌性個體交配，其后代隨機地繼承它們的各一個基因 設初始一代基因類型比例D:H:R =a:2b:c （a+2b+c=1), 記p=a+b, q=b+c, 則群體中優勢

10、基因和劣勢基因比例 d:r=p:q (p+q=1)。假設建模狀態Xn=1,2,3 第n代的一個體屬于D, H, R狀態概率 ai(n) 第n代的一個體屬于狀態i(=1,2,3)的概率。討論基因類型的演變情況基因比例 d:r=p:q轉移概率矩陣狀態轉移概率隨機繁殖馬氏鏈模型自然界中通常p=q=1/2穩態分布D:H:R=1/4:1/2:1/4基因類型為D和H, 優勢表征綠色，基因類型為R, 劣勢表征黃色。解釋“豆科植物的莖，綠色:黃色=3:1”(D+H):R=3:1隨機繁殖近親繁殖在一對父母的大量后代中, 雄雌隨機配對繁殖，討論一系列后代的基因類型的演變過程。狀態定義為配對的基因類型組合Xn=1,

11、2,3,4,5,6配對基因組合為DD,RR,DH,DR,HH,HR狀態轉移概率馬氏鏈模型I0RQ狀態1(DD), 2(RR)是吸收態，馬氏鏈是吸收鏈不論初始如何，經若干代近親繁殖，將全變為優種或劣種.計算從任一非吸收態出發，平均經過幾代被吸收態吸收。純種(優種和劣種)的某些品質不如混種，近親繁殖下大約56代就需重新選種.近親繁殖提 綱隱馬爾科夫模型的三個問題應用領域14概率計算問題路徑預測問題3參數學習問題隱馬爾科夫模型Hidden Markov Model一階馬爾可夫模型（Markov Models）2引例假設你有一個住得很遠的朋友，他每天跟你打電話告訴你他那天作了什么。你的朋友僅僅對三種活

12、動感興趣:公園散步，購物以及清理房間。他選擇做什么事情只憑天氣。你對于他所住的地方的天氣情況并不了解。在他告訴你每天所做的事情基礎上，你想要猜測他所在地的天氣情況。 你認為天氣的運行就像一個馬爾可夫鏈。其有兩個狀態雨和晴，但是你無法直接觀察它們，也就是說，它們對于你是隱藏的。每天你的朋友有一定的機率進行下列活動：散步，購物，或清理。因為你朋友告訴你他的活動，所以這些活動就是你的觀察數據。這整個系統就是一個隱馬爾可夫模型HMM。 引例states = (Rainy, Sunny)observations = (walk, shop, clean)天氣變化概率= Rainy : Rainy: 0.

13、7, Sunny: 0.3, Sunny : Rainy: 0.4, Sunny: 0.6, 不同天氣下進行各種活動的概率= Rainy : walk: 0.1, shop: 0.4, clean: 0.5, Sunny : walk: 0.6, shop: 0.3, clean: 0.1, 引例隱馬爾可夫模型簡介X1X2XTO1O2OT假設對于一個隨機事件，有一個觀察值序列：O1,.,OT該事件隱含著一個狀態序列：X1,.,XT假設1：馬爾可夫假設（狀態構成一階馬爾可夫鏈） p(Xi|Xi-1X1) = p(Xi|Xi-1)假設2：不動性假設（狀態與具體時間無關） p(Xi+1|Xi) =

14、p(Xj+1|Xj)，對任意i,j成立假設3：輸出獨立性假設（輸出僅與當前狀態有關） p(O1,.,OT | X1,.,XT) = p(Ot | Xt) 定義一個隱馬爾可夫模型 (HMM) 是一個五元組： (X , O, A, B, )其中： X = q1,.qN：狀態的有限集合 O = v1,.,vM：觀察值的有限集合 A = aij，aij = p(Xt+1 = qj |Xt = qi)：轉移概率 B = bik，bik = p(Ot = vk | Xt = qi)：輸出概率 = i， i = p(X1 = qi)：初始狀態分布3. 隱馬爾可夫模型t=1t=2t=3t=T-1t=TS1S2

15、S3SNS1S2S3SNS1S2S3SNS1S2S3SNS1S2S3SNS1S2S3SN隱藏狀態S2S3S1S1SNt=1t=2t=3t=T-1t=T觀測狀態Q1Q2QMQ1Q2QMQ1Q2QMQ1Q2QMQ1Q2QMQ1Q2隱藏狀態序列觀察狀態序列Q1QMQ2QMHMM狀態序列觀測序列Q1QM一般隨機過程馬兒科夫過程t=1t=2t=3t=4t=5S1S2S3一階隱馬爾可夫模型（Hidden Markov Models）圖解S1S2S3S1S2S3S1S2S3S1S2S3a11a12a13a22a21a23a31a33a32a11a12a22a21a23a33a32a11a12a22a21a2

16、3a33a32a11a12a22a21a23a33a32下時期狀態只取決于當前時期狀態和轉移概率從某時刻狀態到下時刻的狀態按一定概率轉移t-1時刻t時刻qt-1qt4. 隱馬爾可夫模型(Hidden Markov Models,HMM)Q3Q4Q1Q1O2I-隱藏狀態轉移概率生成概率b2(Q3)b3(Q4)b1(Q1)b1(Q1)b2(Q2)II-觀察序列S2S3S1S1S2qt-1qtq1q2q3t-1時刻t 時刻T=1T=2T=3t=1t=2t=3t=T-1t=TS1S2S3S1S2SNS1S2SNS1S2SNS1S2SNO1O2O3OT-1S2SNS1S1S25. 隱馬爾可夫模型(Hid

17、den Markov Models,HMM)HMM模型五元組表示： （ N, M, , A, B）用來描述HMM，或簡寫為 =( , A, B)一階隱馬爾可夫模型（Hidden Markov Models）數學定義 OTA轉移概率矩陣OMOMOMOMOMB生成概率矩陣NM一階隱馬爾科夫模型在任意時間t，系統在狀態是w(t)時，發出可見信號v(t)。設有n個可見狀態，其中第i個狀態記作vi。定義一個可見的狀態序列記作：vT=v(1),v(2),v(T)。例如有一個可見狀態序列可能是：v6=v5,v1,v3,v4,v1,v4。一個狀態可能產生多個可見狀態，設在狀態wj(t)的時候發出可見狀態vk(

18、t)的概率是：P(vk(t)|wj(t)記作bjk。比如：可以看到對于隱馬爾科夫模型，有兩個特性：提 綱隱馬爾科夫模型Hidden Markov Model應用領域14概率計算問題路徑預測問題3參數學習問題隱馬爾科夫模型的三個問題一階馬爾可夫模型（Markov Models）2問題令 = A,B, 為給定HMM的參數，令 = O1,.,OT 為觀察值序列，隱馬爾可夫模型（HMM）的三個基本問題： 評估問題：對于給定模型，求某個觀察值序列的概率p(|) ；解碼問題：對于給定模型和觀察值序列，求可能性最大的狀態序列；學習問題：對于給定的一個觀察值序列，調整參數，使得觀察值出現的概率p(|)最大。算

19、法評估問題：向前算法定義向前變量采用動態規劃算法，復雜度O(N2T)解碼問題：韋特比（Viterbi）算法采用動態規劃算法，復雜度O(N2T)學習問題：向前向后算法EM算法的一個特例，帶隱變量的最大似然估計算法：向前算法（一）定義前向變量為HMM在時間t輸出序列O1Ot，并且位于狀態Si的概率：算法：向前算法（二）迭代公式為：結果為：變化連續輸出模型輸出矩陣變為某種概率分布，如高斯分布多階轉移矩陣3.1概率計算問題(1)概率計算問題：已知一個HMM的aij，bjk。根據一個可見狀態序列VT，求解它是由這個HMM產生的概率。例如：你建立了一個馬爾科夫模型，你朋友告訴你連續5天他的活動是：購物、清

20、理、清理、散步、購物，求解它是由這個HMM產生的概率。注：其它模型包括：修改這個模型參數；修改這個模型結構；由周六周日作為隱含狀態等等。已知一個HMM的aij，bjk。根據一個可見狀態序列VT，求解它是由這個HMM產生的概率。 這個模型產生一個可見狀態序列VT的概率是：設有rmax個可能的隱含狀態序列，r表示其中第r個序列。求和符號里面的含義是，對于第r個隱含狀態序列，這個隱含狀態序列T產生的概率*這個隱含狀態序列T發出可見狀態VT的概率。 3.1概率計算問題其中： 因此：3.1概率計算問題這樣需要計算的次數很多，有的算法可以很大程度上提高計算速度。估值問題的一個應用是：在語音識別里，根據語音

21、識別到底是那個單詞？比如有兩個HMM：cat，dog。看哪個模型產生這個語音的概率大。 3.1概率計算問題t=1t=2t=3t=T-1t=TS1S2S3S1S2SNS1S2SNzS1S2SNS1S2SNa11a12a13a22a21a23aN1aNNaN2a11a12a22a21a23a33a32a11a12a22a21a23a33a32O1O2O3OT-1OTA轉移概率矩陣B生成概率矩陣問題1：給定觀察序列O=O1,O2, ,OT,以及模型=(,A,B),計算P(O|)？a01a02a0N：初始概率向量1. 隱馬爾可夫模型-全概率計算S2問題本質：計算產生觀測序列O的所有可能的狀態序列對應的

22、概率之和共 N T 個可能路徑（指數級計算）N=5, T=100, = 計算量1072t=1t=2t=3S1S2S1S2S1S2BES4S4S4S5S5S5S3S3S3t=4S1S2S4S5S3a01a02a03a04a05aT1aT2aT3aT4aT5O1O2O3O4前向算法后向算法問題1：給定觀察序列O=O1,O2, ,OT,以及模型=(,A,B),如何計算P(O|)？SkSkS1SNOtS1SNSkS1SN0t-1OT tT0SkS1SN1O1初始化階段(t = 1)中間遞歸階段（t = 2,T）結束階段2. 概率計算問題：前向算法（Forward Algorithm）前進Ot-1前進N

23、=5, T=100, = 計算量3000SkOt+1S1SNSkS1SN0OT tT0SkS1SN1O1.問題1：給定觀察序列O=O1,O2, ,OT,以及模型=(,A,B),如何計算P(O|)？3. 概率計算問題：后向算法（Forward Algorithm）OtSkS1SNt+1.后退后退初始化階段(t = T)中間遞歸階段（t = T-1, 2,1）結束階段(2) 路徑預測問題：已知一個HMM的aij，bjk。根據一個可見狀態序列VT，求解最可能的隱藏狀態序列。例如：你朋友告訴你連續5天他的活動是：購物、清理、清理、散步、購物。你猜測這5天最可能的天氣。3.2路徑預測問題3.2路徑預測問

24、題已知一個HMM的aij，bjk。根據一個可見狀態序列VT，求解最可能的隱藏狀態序列。一個簡單方法是，列出這個HMM所有可能的隱含狀態序列T，每個隱含狀態序列產生VT的概率是： 具有最大概率的隱含狀態序列T就是要求的結果。可以看到這個速度更慢。同樣也有算法可以在很大程度上提高計算速度。 1.隱馬爾可夫模型-路徑預測問題2：給定觀察序列O=O1,O2, ,OT,以及模型,如何推測最可能的狀態序列S ? t=1t=2t=3t=T-1t=TS1S2SNS1S2SNS1S2SNzS1S2SNS1S2SNaN1A轉移概率矩陣B生成概率矩陣a01a02a0N：初始概率向量S2問題本質：計算產生觀測序列O的

25、最可能的一條隱藏狀態序列QO1O2O3OT-1OT已知觀察序列？解決方法：Viterbi算法S2SNS1S1S2viterbi算法t=1t=2t=3S1S2S1S2S1S2BES4S4S4S5S5S5S3S3S3t=4S1S2S4S5S3a01a02a03a04a05a1-0a2-0a3-0a4-0a5-0O1O2O3O42. 隱馬爾可夫狀態路徑預測：Viterbi算法t=1t=2t=3S1S2S1S2S1S2BES4S4S4S5S5S5S3S3S3t=4S1S2S4S5S3a01a02a03a04a05a1-0a2-0a3-0a4-0a5-0O1O2O3O4動畫演示：由Viterbi算法計算

26、產生觀測序列O的最可能的一條隱藏狀態序列QSkSkS1SNOtS1SNSkS1SN0t-1時刻OT t時刻T時刻0SkS1SN1時刻O1初始化階段(t = 1)中間遞歸階段（t = 2,T）結束階段Ot-1問題2：給定觀察序列O=O1,O2, ,OT,以及模型,如何推測最可能的狀態序列S ? MaxS1SNSkS1S？S？S？S1Max路徑回溯向量3. 預測隱馬爾可夫狀態路徑：Viterbi算法表示t時刻，沿狀態路徑q1, q2, ,qt,且qt=Sk時，產生已知的觀察序列的前面t個子序列o1,o2,ot的最大概率值表示t時刻，到達隱狀態sk，且其乘積最大的那個狀態對應的標記序號值。路徑回溯(

27、3)參數學習問題：已知一個HMM的大致結構，包括各種狀態數量。根據一些可見狀態序列，求各種狀態轉移參數aij，bjk。例如：你朋友告訴你很多連續5天他的活動。你猜測天氣轉換概率和在不同天氣下他進行各種活動的概率。3.3參數學習問題1. 隱馬爾可夫模型-參數訓練問題問題3：給定觀察值序列O,如何調整模型參數=(,A,B),使得P(O|)最大 ?t=1t=2t=3t=T-1t=TS1S2SNS1S2SNS1S2SNzS1S2SNS1S2SNaN1A轉移概率矩陣B生成概率矩陣a01a02a0N：初始概率向量S2問題本質：參數=(,A,B)的估值問題O1O2O3OT-1OT已知觀察序列O？情形1：路徑

28、已知時的參數估計 (監督學習方法)情形2：路徑未知時的參數估計 (非監督學習方法)問題3：給定觀察值序列O,如何調整模型參數=(,A,B),使得P(O|)最大 ?2. 隱馬爾可夫模型-參數訓練問題即：由最大似然估計法對HMM的參數進行估計S2S3S1S5S2S2S3S1S5V1V3V2V2V1V4V3V4V1?V1V3V2V2V1V4V3V4V1?Baum-Welch算法（EM算法特例）對HMM參數估計轉移概率生成概率3. 參數訓練算法：Baum-Welch算法基礎(將乘積因子按定義展開)前向算法后向算法(將分子中的按其遞歸計算公式展開)令其為令其為前后向算法關系圖4. 參數訓練算法：Baum

29、-Welch算法（單觀測序列）但在實際應用中,訓練一個HMM用到的觀測值序列往往不止一個,那么,對于多個觀測值序列訓練時,要對BW算法的重估公式進行修正.A轉移概率矩陣B生成概率矩陣初始概率矩陣A轉移概率矩陣B生成概率矩陣0-初始概率矩陣5. 參數訓練算法：Baum-Welch算法（多觀測序列）這種多觀測序列正好適用于蛋白質家族序列中相關問題的解決：如多序列比對情形1：路徑已知時的參數估計 (監督學習方法)情形2：路徑未知時的參數估計 (非監督學習方法)6. 參數訓練算法：Baum-Welch算法過程縱覽S2S3S1S5S2S2S3S1S5V1V3V2V2V1V4V3V4V1?V1V3V2V2V1V4V3V4V1?Baum-Welch算法轉移概率生成概率初始概率極大似然統計法轉移概率生成概率初始概率提 綱隱馬爾科夫模型Hidden Markov Model隱馬爾科夫模型的三個問題14概率計算問題路徑預測問題3參數學習問題應用領域一階馬爾可夫模型（Markov Models）2例子：病情轉化假設：某一時刻只有一種疾病，且只依賴于上一時刻疾病一種疾病只有一種癥狀，且只依賴于當時的疾病癥