隱馬爾可夫模型技術(shù)

1、第8章 隱馬爾可夫模型技術(shù),HMM: Hidden Markov ModelHMM的由來馬爾可夫性和馬爾可夫鏈HMM實(shí)例HMM的三個(gè)基本算法,,HMM的由來,1870年，俄國有機(jī)化學(xué)家Vladimir V. Markovnikov第一次提出馬爾科夫模型馬爾可夫模型馬爾可夫鏈 隱馬爾可夫模型,馬爾可夫性,如果一個(gè)過程的“將來”僅依賴“現(xiàn)在”而不依賴“過去”，則此過程具有馬爾可夫性,或稱此過程為馬爾可夫過程。X(t+1)

2、 = f( X(t) ),馬爾可夫鏈,時(shí)間和狀態(tài)都離散的馬爾可夫過程稱為馬爾可夫鏈記作{Xn = X(n), n = 0,1,2,…}在時(shí)間集T1 = {0,1,2,…}上對(duì)離散狀態(tài)的過程相繼觀察的結(jié)果鏈的狀態(tài)空間記做I = {a1, a2,…}, ai∈R. 條件概率Pij ( m ,m+n)=P{Xm+n = aj|Xm = ai} 為馬氏鏈在時(shí)刻m處于狀態(tài)ai條件下，在時(shí)刻m+n轉(zhuǎn)移到狀態(tài)aj的轉(zhuǎn)移概率。,轉(zhuǎn)移概率矩陣,,

3、陰 天,晴 天,下 雨,,,,,晴天 陰天 下雨晴天 0.50 0.25 0.25陰天 0.375 0.25 0.375下雨 0.25 0.125 0.625,轉(zhuǎn)移概率矩陣(續(xù)),由于鏈在時(shí)刻m從任何一個(gè)狀態(tài)ai出發(fā)，到另一時(shí)刻m+n，必然轉(zhuǎn)移到a1，a2…，諸狀態(tài)中的某一個(gè)，所以有當(dāng)P

4、ij(m,m+n)與m無關(guān)時(shí)，稱馬爾可夫鏈為齊次馬爾可夫鏈，通常說的馬爾可夫鏈都是指齊次馬爾可夫鏈。,,s1,s2,s3,N=3t=0,q0=s3,有N個(gè)狀態(tài)，S1,S2…SN,一階離散馬爾可夫模型,下一個(gè)時(shí)刻所處的狀態(tài)是隨機(jī)出現(xiàn)的,在每個(gè)時(shí)刻t，系統(tǒng)只能處于唯一一個(gè)狀態(tài)qt,存在一個(gè)離散的時(shí)間序列 t=0,t=1……,,,當(dāng)前狀態(tài),,當(dāng)前狀態(tài)qt只與前面相鄰的一個(gè)狀態(tài)qt-1有關(guān)，與其他狀態(tài)無關(guān),s1,s2,s3,一階離散馬

5、爾可夫模型,,1,,1/2,1/2,,,1/3,2/3,s1,s2,s3,一階離散馬爾可夫模型,,1,,1/2,1/2,,,1/3,2/3,aij--- 轉(zhuǎn)移概率并且滿足如下的標(biāo)準(zhǔn)隨機(jī)約束條件:,下雨---狀態(tài)1 多云---狀態(tài)2 晴天---狀態(tài)3,一階離散馬爾可夫模型,問題：連續(xù)8天的天氣狀況為“晴天-晴天-晴天-下雨-下雨-晴天-多云-晴天”的概率是多少？,一階離散馬爾可夫模型,晴天,晴天,晴天,下雨,下雨,晴天,多云,晴天

6、,0.8,0.8,0.1,0.4,0.3,0.1,0.2,晴天,晴天,一階離散馬爾可夫鏈,晴天,下雨,下雨,t,t+1,晴天-晴天-晴天-下雨-下雨-晴天-多云-晴天,晴天,多云,晴天,t-1,,馬爾可夫鏈,信號(hào)統(tǒng)計(jì)理論模型 起源于60年代后期 Baum和他的同事首先提出 Baker(CMU)和Jelinek(IBM)在70年代早期 實(shí)現(xiàn)在語音處理上的應(yīng)用,隱馬爾可夫鏈（HMM）理論,HMM實(shí)例,,最后得到一個(gè)描述球的

7、顏色的序列O1, O2,…，稱為觀察值序列O,設(shè)有N個(gè)缸，每個(gè)缸中裝有很多彩球，球的顏色由一組概率分布描述。實(shí)驗(yàn)方式如下:,根據(jù)初始概率分布，隨機(jī)選擇N個(gè)缸中的一個(gè)開始實(shí)驗(yàn),根據(jù)缸中球顏色的概率分布,隨機(jī)選擇一個(gè)球,記球的顏色為O1 ,并把球放回缸中,根據(jù)描述缸的轉(zhuǎn)移的概率分布，隨機(jī)選擇下一口缸，重復(fù)以上步驟。,,HMM實(shí)例——約束,在上述實(shí)驗(yàn)中，有幾個(gè)要點(diǎn)需要注意：不能直接觀察缸間的轉(zhuǎn)移從缸中所選取的球的顏色和缸并不是一一對(duì)應(yīng)的

8、每次選取哪個(gè)缸由一組轉(zhuǎn)移概率決定,什么是 HMM?,綠圈表示隱含狀態(tài)－－隱僅依賴于前一個(gè)狀態(tài)－－齊次給定當(dāng)前狀態(tài)，過去與將來無關(guān)－－馬爾可夫紫圈是輸出觀察序列的狀態(tài)僅依賴于各自對(duì)應(yīng)的隱狀態(tài),,,,,HMM 模型,{N,M, , A, B}S : {s1…sN } 隱狀態(tài)的值，共有N種可能值K : {k1…kM } 觀察的值，共有M種可能值 隱狀態(tài)初始概率A = {aij} 隱狀態(tài)

9、轉(zhuǎn)移概率，N×NB = {bjk} 觀察狀態(tài)的概率，N×M,A,B,A,A,A,B,B,S,S,S,K,K,K,,,,,S,K,S,K,HMM的基本要素,用模型五元組 來描述HMM，或簡寫為,HMM組成,HMM是一個(gè)雙重隨機(jī)過程，兩個(gè)組成部分： 馬爾可夫鏈：描述狀態(tài)的轉(zhuǎn)移，用轉(zhuǎn)移概率描述。 一般隨機(jī)過程：描述狀態(tài)與觀察序列間的關(guān)系，用觀察值概率描述

10、。,8.4 HMM的三個(gè)基本問題,問題1：給定觀察序列O=O1,O2,…OT,以及模型 如何計(jì)算P(O|λ)？(概率計(jì)算）,問題2：給定觀察序列O=O1,O2,…OT以及模型λ,如何找出一 個(gè)最佳狀態(tài)序列？（HMM識(shí)別）,問題3：如何調(diào)整模型參數(shù) ,使得P(O|λ)最大？,？,估計(jì)問題－－前后向算法,？,解碼問題－－Viterbi算法,？,訓(xùn)練問題－－ Baum Welch算法,7.4.2

11、 HMM基本算法,定義前向變量：,表示模型 下，在時(shí)刻t，觀測事件為Ot，狀態(tài)為i的概率。,s1,s2,sN,,sj,,,,時(shí)刻t,t+1,a1j,a2j,aNj,,估計(jì)問題—前向算法,估計(jì)問題—前向算法,遞歸求解：初始：遞歸：終止：,,?2(1),?2(2),?2(3),?2(N),?3(1),估計(jì)問題—后向算法,定義后向變量：,表示從終止時(shí)刻T到時(shí)刻t+1的觀測事件序列是并且時(shí)刻t的狀態(tài)是i的概率,s1,s2,sN,,si

12、,,,,時(shí)刻t,t+1,ai1,ai2,aiN,,,估計(jì)問題—后向算法,遞歸求解：初始：遞歸：,2、解碼問題—Viterbi算法,找一個(gè)狀態(tài)序列，這個(gè)狀態(tài)序列在t時(shí)狀態(tài)為i，并且狀態(tài)i與前面t-1個(gè)狀態(tài)構(gòu)成的狀態(tài)序列的概率值最大,s1,s2,sN,,sj,,,,時(shí)刻t,t+1,a1j,a2j,aNj,,,3、學(xué)習(xí)問題－－Baum-Welch算法(模型訓(xùn)練算法),算法步驟：1. 初始模型（待訓(xùn)練模型） l0,2. 基于l0 以

13、及觀察值序列O，訓(xùn)練新模型l;3. 如果 log P(X|l) - log(P(X|l0) < Delta，說明訓(xùn)練已經(jīng)達(dá)到預(yù)期效果，算法結(jié)束。4. 否則，令l0 ＝ l ，繼續(xù)第2步工作,Baum-Welch算法(續(xù)),參數(shù)估計(jì)：定義給定模型λ和觀察序列O，在時(shí)刻t 處在狀態(tài)i，時(shí)刻t+1 處在狀態(tài)j 的概率ξt(i, j)，即： ξt(i, j) = P(qt= i, qt+1= j |O, λ)

14、,,使用統(tǒng)計(jì)意義上用頻率近似概率的方法 反復(fù)進(jìn)行上面的過程，逐步改進(jìn)模型參數(shù)，直到 收斂，即不再明顯增大，此時(shí)的 就是HMM的最大相似性評(píng)估。,,,,Baum-Welch算法(續(xù)),Baum-Welch討論,利用上述三個(gè)估算公式，計(jì)算得到一組新的模型參數(shù)，這組新的模型參數(shù)又可以作為一個(gè)新的估算過程的開始點(diǎn)，再次進(jìn)行估算，如此反復(fù)進(jìn)行，直到參數(shù)值收斂。Baum 等人證明要么估算值λ 和估算

15、前的參數(shù)值λ相等，要么估算值λ 比估算前的參數(shù)值λ更好的解釋了觀察序列O。參數(shù)最終的收斂點(diǎn)并不一定是一個(gè)全局最優(yōu)值，但一定是一個(gè)局部最優(yōu)值。Baum-Welch 算法是一類稱為EM (Estimation-Maximisation:估計(jì)-最大化)算法的一個(gè)例子，這類算法均可保證收斂于一個(gè)局部最優(yōu)值。,1. 前向后向算法計(jì)算P(O|λ) ；2. Baum-Welch 算法求出最優(yōu)解λ*= argmax{P(O|λ) }；3. Vi

16、terbi算法解出最佳狀態(tài)轉(zhuǎn)移序列；4. 根據(jù)最佳狀態(tài)序列對(duì)應(yīng)的λ給出候選音節(jié)或聲韻母5. 通過語言模型形成詞和句子,經(jīng)典HMM語音識(shí)別一般過程,基于HMM的語音識(shí)別方案,判決規(guī)則,VITERBI計(jì)算,,,,,,VQ,碼本,,,,,訓(xùn)練,識(shí)別,X,X:特征矢量的時(shí)間序列O:基于VQ的觀察符號(hào)序列,HMM(3),HMM(2),HMM(1),,O,·,·,聲學(xué)參數(shù)分析,預(yù)處理,,語音信號(hào)輸入,,,基于HMM

17、的觀察符號(hào)序列的生成方式,,,當(dāng)給定模型λ(A, B,π)后，就可將該模型看成 一個(gè)符號(hào)生成器(或稱信號(hào)源)，由它生成觀察 序列 O= o1o2 … oT。其生成過程(也稱HMM過程)是： (1)初始狀態(tài)概率分布π，隨機(jī)選擇一個(gè)初始狀態(tài) q1 = Si； (2)置 t = 1； (3)按狀態(tài) Si 的符號(hào)概率分布bi(k)，隨機(jī)產(chǎn)生一個(gè)輸出符號(hào) ot = Vk； (4)按狀態(tài) Si 的狀態(tài)轉(zhuǎn)移概率分布aij，隨機(jī)轉(zhuǎn)移

18、至一個(gè)新的狀態(tài) qt+1 = Sj (5)令t = t + 1，若 t≤ T，則返回步驟（3），否則結(jié)束過程。,模型評(píng)估問題的解法(1),當(dāng)給定模型λ(A, B,π)以及觀察序列 O =o1o2…oT時(shí)，計(jì)算模型λ對(duì)觀察序列 O 的 P(O|λ)概率的思路是(窮舉法)：(1)對(duì)長度為T 的觀察序列O，找出所有 可能產(chǎn)生該觀察序列O 的狀態(tài)轉(zhuǎn)移序 列 Qj =qj1 qj2 qj3 …qjT(j=1,2,…

19、,J);(2)分別計(jì)算Qj與觀察序列O 的聯(lián)合概率 P(O, Qj|λ)；(2)取各聯(lián)合概率P(O,Qj|λ)的和，即： J P(O|λ)=∑P(O,Qj|λ) j=1,HMM 模型的例子觀察符號(hào)序列：abba所有可能的路徑：(1) S1-S1-S1-S2-S3(2) S1-S1-S2-S2-S3(3) S1-S1-S2-S3-S3(4) S1-S2-S2

20、-S2-S3(5) S1-S2-S2-S3-S3(6) S1-S2-S3-S3-S3,模型評(píng)估問題的解法(2),P(O|λ)的一般解法：∵ P(O,Qj|λ)= P(Qj|λ)P(O|Qj,λ) P(Qj|λ)= P(qj1)P(qj2|qj1)P(qj3|qj2) … P(qjT-1|qjT) = aj0,1 aj1,2 aj2,3 …ajT-1,T P(O|Qj,λ)= P(o1|qj1)P

21、(o2|qj2) … P(oT|qjT) = b1j(o1) b2j(o2) b3j(o3) … bTj(oT)∴ P(O,Qj|λ) = aj0,1b1j(o1) aj1,2 b2j(o2) … ajT-1,T bTj(oT) J J T P(O|λ)=∑P(O,Qj|λ)=∑{∏ ajt,tbtj(ot) } j=1

22、 j=1 t=1,HMM 模型的例子,模型評(píng)估問題的前向算法,,采用前向算法求解P(abba|λ)概率的格型圖,Q: q1 q2 q3 q4O: a b b a,,t,最佳路徑問題的解法,,,,,0.5x0.2,0.5x0.8,0.2x1.0,0.6x0.5,0.5x0.2,0.5x0.2

23、,0.5x0.2,0.5x0.8,0.5x0.8,0.5x0.8,0.4x0.5,0.4x0.5,0.4x0.5,0.4x0.5,0.4x0.5,0.6x0.5,0.6x0.5,,,,,,,,,,,,0.8x1.0,0.8x1.0,0.2x1.0,采用Viterbi算法求解產(chǎn)生觀察序列abba最佳路徑的格型圖,Q: q1 q2 q3 q4O: a

24、b b a,,t,最佳路徑：S1-S2-S3-S3-S3,8.5 HMM算法實(shí)現(xiàn)中的問題,初始模型的選取多個(gè)觀察值序列訓(xùn)練數(shù)據(jù)下溢問題馬爾可夫鏈的形狀以及HMM類型,幾種典型形狀的馬爾科夫鏈,左－右形式的Markov鏈,全連接模型鏈,離散的HMM（DHMM）：離散的符號(hào)作為觀測量,連續(xù)的HMM（CHMM）： 觀測量為連續(xù)概率密度函數(shù) 每個(gè)狀態(tài)有不同的一組概率密度函數(shù),半連續(xù)的HMM（SCHMM