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

2、 = f( X(t) ),馬爾可夫鏈,時間和狀態(tài)都離散的馬爾可夫過程稱為馬爾可夫鏈記作{Xn = X(n), n = 0,1,2,…}在時間集T1 = {0,1,2,…}上對離散狀態(tài)的過程相繼觀察的結(jié)果鏈的狀態(tài)空間記做I = {a1, a2,…}, ai∈R. 條件概率Pij ( m ,m+n)=P{Xm+n = aj|Xm = ai} 為馬氏鏈在時刻m處于狀態(tài)ai條件下，在時刻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ù)),由于鏈在時刻m從任何一個狀態(tài)ai出發(fā)，到另一時刻m+n，必然轉(zhuǎn)移到a1，a2…，諸狀態(tài)中的某一個，所以有當P

4、ij(m,m+n)與m無關(guān)時，稱馬爾可夫鏈為齊次馬爾可夫鏈，通常說的馬爾可夫鏈都是指齊次馬爾可夫鏈。,,s1,s2,s3,N=3t=0,q0=s3,有N個狀態(tài)，S1,S2…SN,一階離散馬爾可夫模型,下一個時刻所處的狀態(tài)是隨機出現(xiàn)的,在每個時刻t，系統(tǒng)只能處于唯一一個狀態(tài)qt,存在一個離散的時間序列 t=0,t=1……,,,當前狀態(tài),,當前狀態(tài)qt只與前面相鄰的一個狀態(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)移概率并且滿足如下的標準隨機約束條件:,下雨---狀態(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,,馬爾可夫鏈,信號統(tǒng)計理論模型 起源于60年代后期 Baum和他的同事首先提出 Baker(CMU)和Jelinek(IBM)在70年代早期 實現(xiàn)在語音處理上的應(yīng)用,隱馬爾可夫鏈（HMM）理論,HMM實例,,最后得到一個描述球的

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

8、每次選取哪個缸由一組轉(zhuǎn)移概率決定,什么是 HMM?,綠圈表示隱含狀態(tài)－－隱僅依賴于前一個狀態(tài)－－齊次給定當前狀態(tài)，過去與將來無關(guān)－－馬爾可夫紫圈是輸出觀察序列的狀態(tài)僅依賴于各自對應(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是一個雙重隨機過程，兩個組成部分： 馬爾可夫鏈：描述狀態(tài)的轉(zhuǎn)移，用轉(zhuǎn)移概率描述。 一般隨機過程：描述狀態(tài)與觀察序列間的關(guān)系，用觀察值概率描述

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

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

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

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

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

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

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

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

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

19、,J);(2)分別計算Qj與觀察序列O 的聯(lián)合概率 P(O, Qj|λ)；(2)取各聯(lián)合概率P(O,Qj|λ)的和，即： J P(O|λ)=∑P(O,Qj|λ) j=1,HMM 模型的例子觀察符號序列：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,模型評估問題的解法(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(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算法實現(xiàn)中的問題,初始模型的選取多個觀察值序列訓練數(shù)據(jù)下溢問題馬爾可夫鏈的形狀以及HMM類型,幾種典型形狀的馬爾科夫鏈,左－右形式的Markov鏈,全連接模型鏈,離散的HMM（DHMM）：離散的符號作為觀測量,連續(xù)的HMM（CHMM）： 觀測量為連續(xù)概率密度函數(shù) 每個狀態(tài)有不同的一組概率密度函數(shù),半連續(xù)的HMM（SCHMM