第五章-隱馬爾可夫模型

第五章隱馬爾可夫模型

(HiddenMarkovModel)王俠徐州師范大學(xué)物理與電子工程學(xué)院2008年5月18日一、HMM的由來(lái)二、馬爾可夫性和馬爾可夫鏈三、HMM實(shí)例四、HMM的三個(gè)基本算法1、馬爾可夫鏈2、馬爾可夫模型1870年，俄國(guó)有機(jī)化學(xué)家VladimirV.Markovnikov3.隱馬爾可夫模型60年代末70年代初Baum等人建立的一、HMM的由來(lái)二、馬爾可夫性和馬爾可夫鏈三、HMM實(shí)例四、HMM的三個(gè)基本算法馬爾可夫性如果一個(gè)過(guò)程的“將來(lái)”僅依賴“現(xiàn)在”而不依賴“過(guò)去”,則此過(guò)程具有馬爾可夫性,或稱(chēng)此過(guò)程為馬爾可夫過(guò)程X(t+1)=f(X(t))馬爾科夫鏈時(shí)間和狀態(tài)都離散的馬爾科夫過(guò)程稱(chēng)為馬爾科夫鏈記作{Xn=X(n),n=0,1,2,…}在時(shí)間集T1={0,1,2,…}上對(duì)離散狀態(tài)的過(guò)程相繼觀察的結(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)移概率矩陣陰天晴天下雨

晴天陰天下雨晴天0.500.250.25陰天0.3750.250.375下雨0.250.1250.625轉(zhuǎn)移概率矩陣(續(xù))

由于鏈在時(shí)刻m從任何一個(gè)狀態(tài)ai出發(fā),到另一時(shí)刻m+n,必然轉(zhuǎn)移到a1,a2…,諸狀態(tài)中的某一個(gè),所以有當(dāng)Pij(m,m+n)與m無(wú)關(guān)時(shí),稱(chēng)馬爾科夫鏈為齊次馬爾科夫鏈,通常說(shuō)的馬爾科夫鏈都是指齊次馬爾科夫鏈。HMM的由來(lái)馬爾可夫性和馬爾可夫鏈HMM實(shí)例HMM的三個(gè)基本算法HMM是一個(gè)輸出符號(hào)序列的統(tǒng)計(jì)模型，具有Ｎ個(gè)狀態(tài)S1,S2,…SN,它按一定的周期從一個(gè)狀態(tài)轉(zhuǎn)移到另一個(gè)狀態(tài)，每次轉(zhuǎn)移時(shí)，輸出一個(gè)符號(hào).轉(zhuǎn)移到哪一個(gè)狀態(tài)，轉(zhuǎn)移時(shí)輸出什么符號(hào)，分別由轉(zhuǎn)移概率和轉(zhuǎn)移時(shí)的輸出概率來(lái)決定.S1S2S3a110.3ab0.80.2a220.4ab0.30.7a120.5ab10a230.6ab0.50.5a130.2ab01例一S1S2S3a110.3ab0.80.2a120.5ab10a230.6ab0.50.5a130.2ab01S1→S1→S2→S30.3*0.8*0.5*1.0*0.6*0.5=0.036a220.4ab0.30.7S1S2S3a110.3ab0.80.2a120.5ab10a230.6ab0.50.5a130.2ab01S1→S2→S2→S30.5*1.0*0.4*0.3*0.6*0.5=0.018a220.4ab0.30.7S1S2S3a110.3ab0.80.2a120.5ab10a230.6ab0.50.5a130.2ab01S1→S1→S1→S30.3*0.8*0.3*0.8*0.2*1.0=0.01152所以ＨＭＭ輸出aab的總概率是:0.036+0.018+0.01152=0.06552a220.4ab0.30.7

ObservedBallSequenceUrn3Urn1Urn2Veil例二設(shè)有N個(gè)缸,每個(gè)缸中裝有很多彩球,球的顏色由一組概率分布描述。實(shí)驗(yàn)進(jìn)行方式如下根據(jù)初始概率分布,隨機(jī)選擇N個(gè)缸中的一個(gè)開(kāi)始實(shí)驗(yàn)根據(jù)缸中球顏色的概率分布,隨機(jī)選擇一個(gè)球,記球的顏色為O1,并把球放回缸中根據(jù)描述缸的轉(zhuǎn)移的概率分布,隨機(jī)選擇下一口缸,重復(fù)以上步驟。最后得到一個(gè)描述球的顏色的序列O1,O2,…,稱(chēng)為觀察值序列O。在上述實(shí)驗(yàn)中，有幾個(gè)要點(diǎn)需要注意:不能被直接觀察缸間的轉(zhuǎn)移從缸中所選取的球的顏色和缸并不是一一對(duì)應(yīng)的每次選取哪個(gè)缸由一組轉(zhuǎn)移概率決定HMM概念HMM的狀態(tài)是不確定或不可見(jiàn)的，只有通過(guò)觀測(cè)序列的隨機(jī)過(guò)程才能表現(xiàn)出來(lái)觀察到的事件與狀態(tài)并不是一一對(duì)應(yīng)，而是通過(guò)一組概率分布相聯(lián)系HMM是一個(gè)雙重隨機(jī)過(guò)程，兩個(gè)組成部分:馬爾可夫鏈:描述狀態(tài)的轉(zhuǎn)移，用轉(zhuǎn)移概率描述。一般隨機(jī)過(guò)程:描述狀態(tài)與觀察序列間的關(guān)系，用觀察值概率描述。Markov鏈（

,A）隨機(jī)過(guò)程（B）狀態(tài)序列觀察值序列q1,q2,...,qTo1,o2,...,oTHMM的組成示意圖HMM的組成HMM的基本要素用模型五元組＝（S,O,π,A,B）用來(lái)描述HMM,或簡(jiǎn)寫(xiě)為=(π,A,B)參數(shù)含義實(shí)例S模型中狀態(tài)的有限集合缸O每個(gè)狀態(tài)可能的觀察值數(shù)目彩球顏色數(shù)目A與時(shí)間無(wú)關(guān)的狀態(tài)轉(zhuǎn)移概率矩陣在選定某個(gè)缸的情況下，選擇另一個(gè)缸的概率B給定狀態(tài)下，觀察值概率分布每個(gè)缸中的顏色分布p初始狀態(tài)空間的概率分布初始時(shí)選擇某口缸的概率HMM可解決的問(wèn)題問(wèn)題1：給定觀察序列O=O1,O2,…OT,以及模型,如何計(jì)算P(O|M)？問(wèn)題2：給定觀察序列O=O1,O2,…OT以及模型M,如何選擇一個(gè)對(duì)應(yīng)的狀態(tài)序列S=S1,S2,…ST，使得S能夠最為合理的解釋觀察序列O？問(wèn)題3：如何調(diào)整模型參數(shù),使得P(O|M)最大？解決問(wèn)題1前向方法輸出的觀察符號(hào)序列首先明確下列定義：給定模型入時(shí)，輸出符號(hào)序列O的概率從狀態(tài)Si到狀態(tài)Sj的轉(zhuǎn)移概率從狀態(tài)Si到狀態(tài)Sj發(fā)生轉(zhuǎn)移時(shí)輸出ot的概率輸出部分符號(hào)序列,并且達(dá)到狀態(tài)Sj的概率前向概率解決問(wèn)題1前向法定義前向變量初始化:遞歸:終結(jié):計(jì)算步驟如下:(1)給每個(gè)狀態(tài)準(zhǔn)備一個(gè)數(shù)組變量初始化時(shí)令初始狀態(tài)S1的數(shù)組變量為1,其他狀態(tài)數(shù)組變量為0(2)根據(jù)t時(shí)刻輸出的觀察符號(hào)ot計(jì)算:

當(dāng)狀態(tài)Si到Sj沒(méi)有轉(zhuǎn)移時(shí),=0(3)當(dāng)t≠T時(shí),轉(zhuǎn)移到(2),否則執(zhí)行(4)(4)把這時(shí)的終了狀態(tài)的數(shù)組變量?jī)?nèi)的值取出,則:前向法示意圖

1 ... t-1 t ...a1jat1qN.qi.qj...q1atNatiaNjaijN=5,M=100,=>計(jì)算量3000計(jì)算量:乘法N(N+1)(T-1)+N

加法N(N-1)(T-1)狀態(tài)1狀態(tài)2狀態(tài)3a1(1)=0.24a1(2)=0.5a1(3)=0a2(1)=0.00576a2(2)=0.18a2(3)=0.15a3(3)=0.0655aab0.50.50.200.120.240.240.30.3輸出的觀察符號(hào)序列首先明確下列定義:給定模型入時(shí),輸出符號(hào)序列O的概率從狀態(tài)Si到狀態(tài)Sj的轉(zhuǎn)移概率從狀態(tài)Si到狀態(tài)Sj發(fā)生轉(zhuǎn)移時(shí)輸出ot的概率從狀態(tài)Si開(kāi)始到狀態(tài)SN結(jié)束時(shí)輸出部分符號(hào)序列的概率,即后向概率解決問(wèn)題1后向法與前向法類(lèi)似初始化:遞推公式:最后結(jié)果:后向算法的計(jì)算量大約在N^2T數(shù)量級(jí)根據(jù)前向和后向概率:Viterbi算法目的：給定觀察序列O以及模型λ,如何選擇一個(gè)對(duì)應(yīng)的狀態(tài)序列S，使得S能夠最為合理的解釋觀察序列O？Viterbi算法敘述:(1)初始化(2)遞推公式(3)最后結(jié)果Viterbi算法(續(xù))Viterbi算法求取最佳狀態(tài)序列的步驟(1)給每個(gè)狀態(tài)準(zhǔn)備一個(gè)數(shù)組變量，初始化時(shí)令初始狀態(tài)S1的數(shù)組變量為1，其他數(shù)組狀態(tài)的數(shù)組變量為0；(2)根據(jù)t時(shí)刻輸出的觀察符號(hào)ot計(jì)算:(3)當(dāng)t≠T時(shí)，轉(zhuǎn)移到(2),否則執(zhí)行(4)(4)把這時(shí)的終了狀態(tài)寄存器內(nèi)的值取出，則:按照前向在t時(shí)刻從狀態(tài)SiBaum-Welch算法:給定一個(gè)觀察值序列以及一個(gè)初始模型后向算法,對(duì)于符號(hào)序列概率為則可表示如下:同時(shí)對(duì)于符號(hào)序列在t時(shí)Markov鏈處于狀態(tài)Si的概率為:轉(zhuǎn)移到狀態(tài)Sj的轉(zhuǎn)移狀態(tài)Si轉(zhuǎn)移到狀態(tài)Sj的轉(zhuǎn)移次數(shù)的這樣對(duì)于符號(hào)序列而從狀態(tài)Si轉(zhuǎn)移出去的次數(shù)的期望值為由此可以推導(dǎo)出Baum-Welch算法中的重估公式:期望值為:用Bauum-Welch算法訓(xùn)練HMM的步驟:(1)適當(dāng)?shù)倪x擇的初始值A(chǔ):給予從狀態(tài)i轉(zhuǎn)移出去的每條弧相等的轉(zhuǎn)移概率B:給予每個(gè)輸出觀察符號(hào)相等的輸出概率初始值并且每條弧上(2)給定一個(gè)(訓(xùn)練)觀察值符號(hào)序列由初始模型計(jì)算由重估公式計(jì)算和給予相同的輸出概率矩陣(3)再給定一個(gè)(訓(xùn)練)觀察值符號(hào)序列把前一次的和作為初始模型計(jì)算由重估公式重新計(jì)算和如此反復(fù),直到和收斂為止說(shuō)明:語(yǔ)音識(shí)別一般采用從左到