隱馬爾可夫模型有例子具體易懂

隱馬爾可夫模型

當(dāng)前第1頁\共有77頁\編于星期二\15點(diǎn)主要內(nèi)容馬爾可夫模型隱馬爾可夫模型隱馬爾可夫模型的三個(gè)基本問題三個(gè)基本問題的求解算法

1.前向算法

2.Viterbi算法

3.向前向后算法隱馬爾可夫模型的應(yīng)用隱馬爾可夫模型的一些實(shí)際問題隱馬爾可夫模型總結(jié)當(dāng)前第2頁\共有77頁\編于星期二\15點(diǎn)馬爾可夫鏈一個(gè)系統(tǒng)有N個(gè)狀態(tài)S1，S2，···，Sn，隨著時(shí)間推移，系統(tǒng)從某一狀態(tài)轉(zhuǎn)移到另一狀態(tài)，設(shè)qt為時(shí)間t的狀態(tài)，系統(tǒng)在時(shí)間t處于狀態(tài)Sj的概率取決于其在時(shí)間1，2，···，t-1的狀態(tài)，該概率為：

如果系統(tǒng)在t時(shí)間的狀態(tài)只與其在時(shí)間t-1的狀態(tài)相關(guān)，則該系統(tǒng)構(gòu)成一個(gè)離散的一階馬爾可夫鏈(馬爾可夫過程)：當(dāng)前第3頁\共有77頁\編于星期二\15點(diǎn)馬爾可夫模型如果只考慮獨(dú)立于時(shí)間t的隨機(jī)過程：其中狀態(tài)轉(zhuǎn)移概率aij必須滿足aij>=0,且，則該隨機(jī)過程稱為馬爾可夫模型。當(dāng)前第4頁\共有77頁\編于星期二\15點(diǎn)例假定一段時(shí)間的氣象可由一個(gè)三狀態(tài)的馬爾可夫模型M描述，S1：雨，S2：多云，S3：晴，狀態(tài)轉(zhuǎn)移概率矩陣為：當(dāng)前第5頁\共有77頁\編于星期二\15點(diǎn)例（續(xù)）

如果第一天為晴天，根據(jù)這一模型，在今后七天中天氣為O=“晴晴雨雨晴云晴”的概率為：當(dāng)前第6頁\共有77頁\編于星期二\15點(diǎn)隱馬爾可夫模型

（HiddenMarkovModel,HMM）在MM中，每一個(gè)狀態(tài)代表一個(gè)可觀察的事件在HMM中觀察到的事件是狀態(tài)的隨機(jī)函數(shù)，因此該模型是一雙重隨機(jī)過程，其中狀態(tài)轉(zhuǎn)移過程是不可觀察（隱蔽）的(馬爾可夫鏈)，而可觀察的事件的隨機(jī)過程是隱蔽的狀態(tài)轉(zhuǎn)換過程的隨機(jī)函數(shù)(一般隨機(jī)過程)。當(dāng)前第7頁\共有77頁\編于星期二\15點(diǎn)HMM的三個(gè)假設(shè)對于一個(gè)隨機(jī)事件，有一觀察值序列：O=O1,O2,…OT該事件隱含著一個(gè)狀態(tài)序列：Q=q1,q2,…qT。假設(shè)1：馬爾可夫性假設(shè)（狀態(tài)構(gòu)成一階馬爾可夫鏈）

P(qi|qi-1…q1)=P(qi|qi-1)假設(shè)2：不動性假設(shè)（狀態(tài)與具體時(shí)間無關(guān)）

P(qi+1|qi)=P(qj+1|qj)，對任意i，j成立假設(shè)3：輸出獨(dú)立性假設(shè)（輸出僅與當(dāng)前狀態(tài)有關(guān)）

p(O1,...,OT|q1,...,qT)=Πp(Ot|qt)當(dāng)前第8頁\共有77頁\編于星期二\15點(diǎn)HMM定義一個(gè)隱馬爾可夫模型(HMM)是由一個(gè)五元組描述的：

λ＝（N，M，A，B，π）其中：N={q1,...qN}：狀態(tài)的有限集合M={v1,...,vM}：觀察值的有限集合A={aij}，aij=P(qt=Sj|qt-1=Si)：狀態(tài)轉(zhuǎn)移概率矩陣B={bjk}，bjk

=P(Ot=vk|qt=Sj)：觀察值概率分布矩陣π={πi}，πi=P(q1=Si)：初始狀態(tài)概率分布當(dāng)前第9頁\共有77頁\編于星期二\15點(diǎn)觀察序列產(chǎn)生步驟給定HMM模型λ=(A，B，π)，則觀察序列O=O1,O2,…OT

可由以下步驟產(chǎn)生：1.根據(jù)初始狀態(tài)概率分布π=πi,選擇一初始狀態(tài)q1=Si；2.設(shè)t=1；3.根據(jù)狀態(tài)Si的輸出概率分布bjk,輸出Ot=vk；4.根據(jù)狀態(tài)轉(zhuǎn)移概率分布aij,轉(zhuǎn)移到新狀態(tài)qt+1=Sj；5.設(shè)t=t+1,如果t<T，重復(fù)步驟3、4，否則結(jié)束。當(dāng)前第10頁\共有77頁\編于星期二\15點(diǎn)HMM的三個(gè)基本問題令λ

={π，A，B}為給定HMM的參數(shù)，令O=O1,...,OT為觀察值序列，則有關(guān)于隱馬爾可夫模型（HMM）的三個(gè)基本問題：1.評估問題：對于給定模型，求某個(gè)觀察值序列的概率P(O|λ)；2.解碼問題：對于給定模型和觀察值序列，求可能性最大的狀態(tài)序列maxQ{P(Q|O,λ)}；3.學(xué)習(xí)問題：對于給定的一個(gè)觀察值序列O，調(diào)整參數(shù)λ，使得觀察值出現(xiàn)的概率P(O|λ)最大。當(dāng)前第11頁\共有77頁\編于星期二\15點(diǎn)例:賭場的欺詐某賭場在擲骰子根據(jù)點(diǎn)數(shù)決定勝負(fù)時(shí),暗中采取了如下作弊手段:在連續(xù)多次擲骰子的過程中,通常使用公平骰子AB0.90.1A,偶而混入一個(gè)灌鉛骰子B.

0.80.2公平骰子灌鉛骰子當(dāng)前第12頁\共有77頁\編于星期二\15點(diǎn)骰子A骰子B1點(diǎn)1/602點(diǎn)1/61/83點(diǎn)1/61/84點(diǎn)1/63/165點(diǎn)1/63/166點(diǎn)1/63/8公平骰子A與灌鉛骰子B的區(qū)別:當(dāng)前第13頁\共有77頁\編于星期二\15點(diǎn)時(shí)間1234567骰子AAABAAA擲出點(diǎn)數(shù)3345162一次連續(xù)擲骰子的過程模擬

隱序列

明序列查封賭場后,調(diào)查人員發(fā)現(xiàn)了一些連續(xù)擲骰子的記錄,其中有一個(gè)骰子擲出的點(diǎn)數(shù)記錄如下:

…當(dāng)前第14頁\共有77頁\編于星期二\15點(diǎn)問題1–評估問題給定一個(gè)骰子擲出的點(diǎn)數(shù)記錄124552646214614613613666166466163661636616361651561511514612356234問題會出現(xiàn)這個(gè)點(diǎn)數(shù)記錄的概率有多大?求P(O|λ)當(dāng)前第15頁\共有77頁\編于星期二\15點(diǎn)問題2–解碼問題給定一個(gè)骰子擲出的點(diǎn)數(shù)記錄124552646214614613613666166466163661636616361651561511514612356234問題點(diǎn)數(shù)序列中的哪些點(diǎn)數(shù)是用骰子B擲出的?求maxQ{P(Q|O,λ)}當(dāng)前第16頁\共有77頁\編于星期二\15點(diǎn)問題3–學(xué)習(xí)問題給定一個(gè)骰子擲出的點(diǎn)數(shù)記錄124552646214614613613666166466163661636616361651561511514612356234問題作弊骰子擲出各點(diǎn)數(shù)的概率是怎樣的?公平骰子擲出各點(diǎn)數(shù)的概率又是怎樣的?賭場是何時(shí)換用骰子的?當(dāng)前第17頁\共有77頁\編于星期二\15點(diǎn)骰子B

本例中HMM的定義

賭場的例子中:隱狀態(tài)集:S={骰子A,骰子B}明字符集:V={1,2,3,4,5,6}b21=0,b22=b23=1/8,b24=b25=3/16,b26=3/81/61/61/61/61/61/601/81/83/163/163/8初始狀態(tài)概率:π1=1,π2=0隱狀態(tài)轉(zhuǎn)移概率:

a11=0.9,a12=0.1

a21=0.8,a22=0.2

初始狀態(tài)明字符生成概率:

b11=b12=…=b16=1/61.00

1: 2: 3: 4: 5:骰子A6:

0.1

1: 2: 3: 4: 5: 6:0.80.90.2當(dāng)前第18頁\共有77頁\編于星期二\15點(diǎn)HMM將兩個(gè)序列相聯(lián)系起來：1.由離散隱狀態(tài)組成的狀態(tài)序列(路徑)Q=(q1,…,qT),每個(gè)qt∈S均是一個(gè)狀態(tài)由初始狀態(tài)概率及狀態(tài)轉(zhuǎn)移概率(π,A)所決定2.由明字符組成的觀察序列O=(o1,…,oT),每個(gè)ot∈V均為一個(gè)離散明字符由狀態(tài)序列及各狀態(tài)的明字符生成概率(Q,B)所決定當(dāng)前第19頁\共有77頁\編于星期二\15點(diǎn)賭場的例子中:隱狀態(tài)明觀察AAAABAAAAABAAAAAAAAAAAAAAAAAAAAAAABAABAAAAAAAAA…33454141553663441134625445334223332124225631341…q1q2q3q4qT...o1o2o3o4oT...觀察序列O狀態(tài)序列QHMMλ當(dāng)前第20頁\共有77頁\編于星期二\15點(diǎn)本例中三個(gè)基本問題1.評估問題?給定觀察序列O和HMM

=(π,A,B),判斷O是由產(chǎn)生出來的可能性有多大?計(jì)算骰子點(diǎn)數(shù)序列的確由“作弊”模型生成的可能性2.解碼問題?給定觀察序列O和HMMλ=(π,A,B),計(jì)算與序列O相對應(yīng)的狀態(tài)序列是什么?在骰子點(diǎn)數(shù)序列中,判斷哪些點(diǎn)數(shù)是用骰子B擲出的3.學(xué)習(xí)問題?給定一系列觀察序列樣本,確定能夠產(chǎn)生出這些序列的模型λ=(π,A,B)?如何從大量的點(diǎn)數(shù)序列樣本中學(xué)習(xí)得出“作弊模型”的參數(shù)當(dāng)前第21頁\共有77頁\編于星期二\15點(diǎn)三個(gè)基本問題的求解算法評估問題：前向算法定義前向變量采用動態(tài)規(guī)劃算法，復(fù)雜度O(N2T)解碼問題：韋特比（Viterbi）算法采用動態(tài)規(guī)劃算法，復(fù)雜度O(N2T)學(xué)習(xí)問題：向前向后算法EM算法的一個(gè)特例，帶隱變量的最大似然估計(jì)當(dāng)前第22頁\共有77頁\編于星期二\15點(diǎn)解決問題一—前向算法定義前向變量為：“在時(shí)間步t,得到t之前的所有明符號序列,且時(shí)間 步t的狀態(tài)是Si”這一事件的概率， 記為

(t,i)=P(o1,…,ot,qt=Si|λ)則

當(dāng)前第23頁\共有77頁\編于星期二\15點(diǎn)算法過程

當(dāng)前第24頁\共有77頁\編于星期二\15點(diǎn)HMM的網(wǎng)格結(jié)構(gòu)當(dāng)前第25頁\共有77頁\編于星期二\15點(diǎn)前向算法過程演示t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1i=Ni=N-1i=5i=4i=3i=2i=1α(t,i)當(dāng)前第26頁\共有77頁\編于星期二\15點(diǎn)t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法過程演示i=Ni=N-1i=5i=4i=3i=2i=1初始化α(1,i)=π(i)b(i,o1)當(dāng)前第27頁\共有77頁\編于星期二\15點(diǎn)t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法過程演示i=Ni=N-1i=5i=4i=3i=2i=1當(dāng)前第28頁\共有77頁\編于星期二\15點(diǎn)t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法過程演示i=Ni=N-1i=5i=4i=3i=2i=1當(dāng)前第29頁\共有77頁\編于星期二\15點(diǎn)t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法過程演示i=Ni=N-1i=5i=4i=3i=2i=1當(dāng)前第30頁\共有77頁\編于星期二\15點(diǎn)t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法過程演示i=Ni=N-1i=5i=4i=3i=2i=1當(dāng)前第31頁\共有77頁\編于星期二\15點(diǎn)t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法過程演示i=Ni=N-1i=5i=4i=3i=2i=12.遞歸當(dāng)前第32頁\共有77頁\編于星期二\15點(diǎn)t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法過程演示i=Ni=N-1i=5i=4i=3i=2i=1

當(dāng)前第33頁\共有77頁\編于星期二\15點(diǎn)t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法過程演示i=Ni=N-1i=5i=4i=3i=2i=1

當(dāng)前第34頁\共有77頁\編于星期二\15點(diǎn)t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法過程演示i=Ni=N-1i=5i=4i=3i=2i=1

當(dāng)前第35頁\共有77頁\編于星期二\15點(diǎn)t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法過程演示i=Ni=N-1i=5i=4i=3i=2i=1

當(dāng)前第36頁\共有77頁\編于星期二\15點(diǎn)t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法過程演示i=Ni=N-1i=5i=4i=3i=2i=1

當(dāng)前第37頁\共有77頁\編于星期二\15點(diǎn)t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法過程演示i=Ni=N-1i=5i=4i=3i=2i=1

當(dāng)前第38頁\共有77頁\編于星期二\15點(diǎn)

前向算法過程演示i=Nt=1t=2t=3t=4t=5t=Tt=6t=7t=T-1i=N-1i=5i=4i=3i=2i=1

當(dāng)前第39頁\共有77頁\編于星期二\15點(diǎn)前向算法過程演示t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1i=Ni=N-1i=5i=4i=3i=2i=1

當(dāng)前第40頁\共有77頁\編于星期二\15點(diǎn)t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法過程演示i=Ni=N-1i=5i=4i=3i=2i=1當(dāng)前第41頁\共有77頁\編于星期二\15點(diǎn)t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法過程演示i=Ni=N-1i=5i=4i=3i=2i=1當(dāng)前第42頁\共有77頁\編于星期二\15點(diǎn)t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法過程演示i=Ni=N-1i=5i=4i=3i=2i=1當(dāng)前第43頁\共有77頁\編于星期二\15點(diǎn)t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法過程演示i=Ni=N-1i=5i=4i=3i=2i=1當(dāng)前第44頁\共有77頁\編于星期二\15點(diǎn)t=1t=2t=3t=4t=5t=Tt=7t=6t=T-1

前向算法過程演示i=Ni=N-1i=5i=4i=3i=2i=1當(dāng)前第45頁\共有77頁\編于星期二\15點(diǎn)t=1t=2t=3t=4t=5t=Tt=T-1t=6t=7

前向算法過程演示i=Ni=N-1i=5i=4i=3i=2i=1當(dāng)前第46頁\共有77頁\編于星期二\15點(diǎn)t=1t=2t=3t=4t=5t=Tt=T-1t=6t=7

前向算法過程演示i=Ni=N-1i=5i=4i=3i=2i=1當(dāng)前第47頁\共有77頁\編于星期二\15點(diǎn)前向算法過程演示t=1t=2t=3t=4t=5t=Tt=T-1t=6t=7i=Ni=N-1i=5i=4i=3i=2i=13.計(jì)算P(O|λ)當(dāng)前第48頁\共有77頁\編于星期二\15點(diǎn)t=1t=2t=3t=4t=5t=Tt=T-1t=6t=7

前向算法過程演示i=Ni=N-1i=5i=4i=3i=2i=1

當(dāng)前第49頁\共有77頁\編于星期二\15點(diǎn)例子（前向算法應(yīng)用）HMM模型如下，試根據(jù)前向算法計(jì)算產(chǎn)生觀察符號序列O={ABAB}的概率。狀態(tài)集Q={S1,S2,S3}觀察序列集O={A,B}當(dāng)前第50頁\共有77頁\編于星期二\15點(diǎn)例（續(xù)）初始概率矩陣π=(1,0,0),即開始處于狀態(tài)1。按照前向算法公式，我們依次遞推解出t(i)

。解法如下：

1.當(dāng)t=1時(shí)：

當(dāng)前第51頁\共有77頁\編于星期二\15點(diǎn)例（續(xù)）2.當(dāng)t=2時(shí)：3.當(dāng)t=3時(shí)：

當(dāng)前第52頁\共有77頁\編于星期二\15點(diǎn)例（續(xù)）4.當(dāng)t=4時(shí)：所以最終有：

P(O|λ)=4(1)+4(2)+4(3)=0.0717696即觀察序列O由HMM模型產(chǎn)生的概率當(dāng)前第53頁\共有77頁\編于星期二\15點(diǎn)例（續(xù)）最后將其計(jì)算過程示意圖表示如下：當(dāng)前第54頁\共有77頁\編于星期二\15點(diǎn)問題2—解碼問題

所求的Q應(yīng)當(dāng)在某個(gè)準(zhǔn)則下是“最優(yōu)”的,因此也稱Q為最優(yōu)路徑,解碼問題即是確定最優(yōu)路徑的問題。當(dāng)前第55頁\共有77頁\編于星期二\15點(diǎn)

qt=Si產(chǎn)生出o1,…ot的最大概率，即：

解決問題二—Viterbi算法Viterbi算法也是類似于前向算法的一種網(wǎng)格結(jié)構(gòu)當(dāng)前第56頁\共有77頁\編于星期二\15點(diǎn)Viterbi算法（續(xù)）目標(biāo)：給定一個(gè)觀察序列和HMM模型，如何有效選擇“最優(yōu)”狀態(tài)序列，以“最好地解釋”觀察序列“最優(yōu)”→概率最大：Viterbi變量：遞歸關(guān)系：記憶變量：記錄概率最大路徑上當(dāng)前狀態(tài)的前一個(gè)狀態(tài)當(dāng)前第57頁\共有77頁\編于星期二\15點(diǎn)Viterbi算法（續(xù)）初始化：遞歸：終結(jié)：路徑回溯：當(dāng)前第58頁\共有77頁\編于星期二\15點(diǎn)例子（Viterbi算法應(yīng)用）HMM模型如下，試根據(jù)Viterbi算法計(jì)算產(chǎn)生觀察符號序列O={ABAB}的最優(yōu)狀態(tài)序列Q。

狀態(tài)集Q｛S1,S2,S3｝觀察序列集O={A,B}當(dāng)前第59頁\共有77頁\編于星期二\15點(diǎn)例（續(xù)）

初始概率矩陣π=(1,0,0),即開始時(shí)處于狀態(tài)1。按照上面的公式，我們依次遞推解出，以及。解法如下：

1.當(dāng)t=1時(shí)：

當(dāng)前第60頁\共有77頁\編于星期二\15點(diǎn)例（續(xù)）2.當(dāng)t=2時(shí)：3.當(dāng)t=3時(shí)：當(dāng)前第61頁\共有77頁\編于星期二\15點(diǎn)例（續(xù)）4.當(dāng)t=4時(shí)：

當(dāng)前第62頁\共有77頁\編于星期二\15點(diǎn)例（續(xù)）其遞推結(jié)果為：可以看出，最有可能的狀態(tài)序列是：

S1，S2，S2，S2.當(dāng)前第63頁\共有77頁\編于星期二\15點(diǎn)例（續(xù)）其計(jì)算結(jié)果示意圖如下所示：綠色的箭頭表示最有可能的狀態(tài)序列

當(dāng)前第64頁\共有77頁\編于星期二\15點(diǎn)問題3—學(xué)習(xí)問題也稱訓(xùn)練問題、參數(shù)估計(jì)問題

化準(zhǔn)則，使得觀察序列的概率P(O|λ)最大。當(dāng)前第65頁\共有77頁\編于星期二\15點(diǎn)狀態(tài)序列已知情況可以由最大似然估計(jì)來估計(jì)HMM的參數(shù)：當(dāng)前第66頁\共有77頁\編于星期二\15點(diǎn)EM(Expectation-Maximization)算法由于HMM中的狀態(tài)序列是觀察不到的（隱變量），以上的最大似然估計(jì)不可行。EM算法可用于含有隱變量的統(tǒng)計(jì)模型的最大似然估計(jì)。EM算法是一個(gè)由交替進(jìn)行的“期望(E過程)”和“極大似然估計(jì)(M過程)”兩部分組成的迭代過程：

·對于給定的不完全數(shù)據(jù)和當(dāng)前的參數(shù)值，“E過程”從條件期望中相應(yīng)地構(gòu)造完全數(shù)據(jù)的似然函數(shù)值，“M過程”則利用參數(shù)的充分統(tǒng)計(jì)量，重新估計(jì)概率模型的參數(shù)，使得訓(xùn)練數(shù)據(jù)的對數(shù)似然最大。EM算法的每一次迭代過程必定單調(diào)地增加訓(xùn)練數(shù)據(jù)的對數(shù)似然值，于是迭代過程漸進(jìn)地收斂于一個(gè)局部最優(yōu)值。當(dāng)前第67頁\共有77頁\編于星期二\15點(diǎn)向前向后算法(Baum-Welch算法)1.初始化：隨機(jī)地給πi

，aij

，bjk賦值（滿足概率條件），得到模型λ0，設(shè)i=0；2.EM