機(jī)器學(xué)習(xí)9隱馬爾科夫模型版

1、隱馬爾科夫模型Hidden Markov Model(HMM)王成（副教授）計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院提 綱隱馬爾科夫模型的三個(gè)問題應(yīng)用領(lǐng)域14概率計(jì)算問題路徑預(yù)測(cè)問題3參數(shù)學(xué)習(xí)問題一階馬爾可夫模型（Markov Models）隱馬爾科夫模型Hidden Markov Model2數(shù)學(xué)類：概率論、組合數(shù)學(xué)、矩陣論計(jì)算機(jī)類：數(shù)據(jù)結(jié)構(gòu)、算法導(dǎo)論、MATLAB、Mathematica、C/C+等編程技術(shù)問題背景：基因遺傳學(xué)、遺傳病學(xué)、生態(tài)學(xué)、人口學(xué)與馬爾可夫模型(Markov Models)相關(guān)的課程1馬爾可夫模型馬爾可夫模型是數(shù)學(xué)中具有馬爾可夫性質(zhì)的離散時(shí)間隨機(jī)過程，是用于描述隨機(jī)過程統(tǒng)計(jì)特征的概率模型

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

3、Models）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-1qtq1q2q3t-1時(shí)刻t 時(shí)刻晴陰雨T=1T=2T=3一階馬爾科夫模型設(shè)有n個(gè)狀態(tài)，其中第i個(gè)狀態(tài)記作wi。在任意時(shí)刻t的狀態(tài)記作w(t)。一個(gè)長(zhǎng)度為T的狀態(tài)序列記作wT=w(1),w(2),w(T)。例如有一個(gè)狀態(tài)序列可能是：w6=w1

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

5、健康狀態(tài)隨著時(shí)間的推移會(huì)隨機(jī)地發(fā)生轉(zhuǎn)變 保險(xiǎn)公司要對(duì)投保人未來的健康狀態(tài)作出估計(jì), 以制訂保險(xiǎn)金和理賠金的數(shù)額 若某人投保時(shí)健康, 問10年后他仍處于健康狀態(tài)的概率Xn+1只取決于Xn和pij, 與Xn-1, 無關(guān)狀態(tài)與狀態(tài)轉(zhuǎn)移狀態(tài)轉(zhuǎn)移具有無后效性 120.80.20.30.7 n 0a2(n) 0 a1(n) 1設(shè)投保時(shí)健康給定a(0), 預(yù)測(cè) a(n), n=1,2設(shè)投保時(shí)疾病a2(n) 1 a1(n) 0 n時(shí)狀態(tài)概率趨于穩(wěn)定值，穩(wěn)定值與初始狀態(tài)無關(guā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 狀態(tài)與狀態(tài)轉(zhuǎn)移120

6、.80.20.30.710.80.220.780.221230.10.0210.80.250.180.65例2. 健康和疾病狀態(tài)同上，Xn=1 健康, Xn=2 疾病p11=0.8, p12=0.18, p13=0.02 死亡為第3種狀態(tài)，記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 設(shè)投保時(shí)處于健康狀態(tài)，預(yù)測(cè) a(n), n=1,2 不論初始狀態(tài)如何

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

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

9、RH1000011 / 21 / 200101 / 41 / 21 / 401 / 21 / 23種基因類型：dd優(yōu)種D, dr混種H, rr劣種R完全優(yōu)勢(shì)基因遺傳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隨機(jī)繁殖 設(shè)群體中雄性、雌性的比例相等，基因類型的分布相同（記作D:H:R） 每一雄性個(gè)體以D:H:R的概率與一雌性個(gè)體交配，其后代隨機(jī)地繼承它們的各一個(gè)基因 設(shè)初始一代基因類型比例D:H:R =a:2b:c （a+2b+c=1), 記p=a+b, q=b+c, 則群體中優(yōu)勢(shì)

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

11、2,3,4,5,6配對(duì)基因組合為DD,RR,DH,DR,HH,HR狀態(tài)轉(zhuǎn)移概率馬氏鏈模型I0RQ狀態(tài)1(DD), 2(RR)是吸收態(tài)，馬氏鏈?zhǔn)俏真湶徽摮跏既绾?，?jīng)若干代近親繁殖，將全變?yōu)閮?yōu)種或劣種.計(jì)算從任一非吸收態(tài)出發(fā)，平均經(jīng)過幾代被吸收態(tài)吸收。純種(優(yōu)種和劣種)的某些品質(zhì)不如混種，近親繁殖下大約56代就需重新選種.近親繁殖提 綱隱馬爾科夫模型的三個(gè)問題應(yīng)用領(lǐng)域14概率計(jì)算問題路徑預(yù)測(cè)問題3參數(shù)學(xué)習(xí)問題隱馬爾科夫模型Hidden Markov Model一階馬爾可夫模型（Markov Models）2引例假設(shè)你有一個(gè)住得很遠(yuǎn)的朋友，他每天跟你打電話告訴你他那天作了什么。你的朋友僅僅對(duì)三種活

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

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

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

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

16、3a33a32a11a12a22a21a23a33a32下時(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. 隱馬爾可夫模型(Hidden Markov Models,HMM)Q3Q4Q1Q1O2I-隱藏狀態(tài)轉(zhuǎn)移概率生成概率b2(Q3)b3(Q4)b1(Q1)b1(Q1)b2(Q2)II-觀察序列S2S3S1S1S2qt-1qtq1q2q3t-1時(shí)刻t 時(shí)刻T=1T=2T=3t=1t=2t=3t=T-1t=TS1S2S3S1S2SNS1S2SNS1S2SNS1S2SNO1O2O3OT-1S2SNS1S1S25. 隱馬爾可夫模型(Hid

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

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

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

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

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

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

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

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

25、最可能的一條隱藏狀態(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)畫演示：由Viterbi算法計(jì)算

26、產(chǎn)生觀測(cè)序列O的最可能的一條隱藏狀態(tài)序列QSkSkS1SNOtS1SNSkS1SN0t-1時(shí)刻OT t時(shí)刻T時(shí)刻0SkS1SN1時(shí)刻O1初始化階段(t = 1)中間遞歸階段（t = 2,T）結(jié)束階段Ot-1問題2：給定觀察序列O=O1,O2, ,OT,以及模型,如何推測(cè)最可能的狀態(tài)序列S ? MaxS1SNSkS1S？S？S？S1Max路徑回溯向量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，且其乘積最大的那個(gè)狀態(tài)對(duì)應(yīng)的標(biāo)記序號(hào)值。路徑回溯(

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

28、已知時(shí)的參數(shù)估計(jì) (監(jiān)督學(xué)習(xí)方法)情形2：路徑未知時(shí)的參數(shù)估計(jì) (非監(jiān)督學(xué)習(xí)方法)問題3：給定觀察值序列O,如何調(diào)整模型參數(shù)=(,A,B),使得P(O|)最大 ?2. 隱馬爾可夫模型-參數(shù)訓(xù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ǔ)(將乘積因子按定義展開)前向算法后向算法(將分子中的按其遞歸計(jì)算公式展開)令其為令其為前后向算法關(guān)系圖4. 參數(shù)訓(xùn)練算法：Baum

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