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

隱馬爾可夫模型

現(xiàn)在是1頁(yè)\一共有77頁(yè)\編輯于星期三主要內(nèi)容馬爾可夫模型隱馬爾可夫模型隱馬爾可夫模型的三個(gè)基本問(wèn)題三個(gè)基本問(wèn)題的求解算法

1.前向算法

2.Viterbi算法

3.向前向后算法隱馬爾可夫模型的應(yīng)用隱馬爾可夫模型的一些實(shí)際問(wèn)題隱馬爾可夫模型總結(jié)現(xiàn)在是2頁(yè)\一共有77頁(yè)\編輯于星期三馬爾可夫鏈一個(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è)離散的一階馬爾可夫鏈(馬爾可夫過(guò)程)：現(xiàn)在是3頁(yè)\一共有77頁(yè)\編輯于星期三馬爾可夫模型如果只考慮獨(dú)立于時(shí)間t的隨機(jī)過(guò)程：其中狀態(tài)轉(zhuǎn)移概率aij必須滿足aij>=0,且，則該隨機(jī)過(guò)程稱為馬爾可夫模型?，F(xiàn)在是4頁(yè)\一共有77頁(yè)\編輯于星期三例假定一段時(shí)間的氣象可由一個(gè)三狀態(tài)的馬爾可夫模型M描述，S1：雨，S2：多云，S3：晴，狀態(tài)轉(zhuǎn)移概率矩陣為：現(xiàn)在是5頁(yè)\一共有77頁(yè)\編輯于星期三例（續(xù)）

如果第一天為晴天，根據(jù)這一模型，在今后七天中天氣為O=“晴晴雨雨晴云晴”的概率為：現(xiàn)在是6頁(yè)\一共有77頁(yè)\編輯于星期三隱馬爾可夫模型

（HiddenMarkovModel,HMM）在MM中，每一個(gè)狀態(tài)代表一個(gè)可觀察的事件在HMM中觀察到的事件是狀態(tài)的隨機(jī)函數(shù)，因此該模型是一雙重隨機(jī)過(guò)程，其中狀態(tài)轉(zhuǎn)移過(guò)程是不可觀察（隱蔽）的(馬爾可夫鏈)，而可觀察的事件的隨機(jī)過(guò)程是隱蔽的狀態(tài)轉(zhuǎn)換過(guò)程的隨機(jī)函數(shù)(一般隨機(jī)過(guò)程)?，F(xiàn)在是7頁(yè)\一共有77頁(yè)\編輯于星期三HMM的三個(gè)假設(shè)對(duì)于一個(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：不動(dòng)性假設(shè)（狀態(tài)與具體時(shí)間無(wú)關(guān)）

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

p(O1,...,OT|q1,...,qT)=Πp(Ot|qt)現(xiàn)在是8頁(yè)\一共有77頁(yè)\編輯于星期三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)概率分布現(xiàn)在是9頁(yè)\一共有77頁(yè)\編輯于星期三觀察序列產(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īng)顟B(tài)qt+1=Sj；5.設(shè)t=t+1,如果t<T，重復(fù)步驟3、4，否則結(jié)束?，F(xiàn)在是10頁(yè)\一共有77頁(yè)\編輯于星期三HMM的三個(gè)基本問(wèn)題令λ

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

0.80.2公平骰子灌鉛骰子現(xiàn)在是12頁(yè)\一共有77頁(yè)\編輯于星期三骰子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ū)別:現(xiàn)在是13頁(yè)\一共有77頁(yè)\編輯于星期三時(shí)間1234567骰子AAABAAA擲出點(diǎn)數(shù)3345162一次連續(xù)擲骰子的過(guò)程模擬

隱序列

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

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

本例中HMM的定義

賭場(chǎng)的例子中:隱狀態(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現(xiàn)在是18頁(yè)\一共有77頁(yè)\編輯于星期三HMM將兩個(gè)序列相聯(lián)系起來(lái)：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)所決定現(xiàn)在是19頁(yè)\一共有77頁(yè)\編輯于星期三賭場(chǎng)的例子中:隱狀態(tài)明觀察AAAABAAAAABAAAAAAAAAAAAAAAAAAAAAAABAABAAAAAAAAA…33454141553663441134625445334223332124225631341…q1q2q3q4qT...o1o2o3o4oT...觀察序列O狀態(tài)序列QHMMλ現(xiàn)在是20頁(yè)\一共有77頁(yè)\編輯于星期三本例中三個(gè)基本問(wèn)題1.評(píng)估問(wèn)題?給定觀察序列O和HMM

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

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

現(xiàn)在是23頁(yè)\一共有77頁(yè)\編輯于星期三算法過(guò)程

現(xiàn)在是24頁(yè)\一共有77頁(yè)\編輯于星期三HMM的網(wǎng)格結(jié)構(gòu)現(xiàn)在是25頁(yè)\一共有77頁(yè)\編輯于星期三前向算法過(guò)程演示t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1i=Ni=N-1i=5i=4i=3i=2i=1α(t,i)現(xiàn)在是26頁(yè)\一共有77頁(yè)\編輯于星期三t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法過(guò)程演示i=Ni=N-1i=5i=4i=3i=2i=1初始化α(1,i)=π(i)b(i,o1)現(xiàn)在是27頁(yè)\一共有77頁(yè)\編輯于星期三t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法過(guò)程演示i=Ni=N-1i=5i=4i=3i=2i=1現(xiàn)在是28頁(yè)\一共有77頁(yè)\編輯于星期三t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法過(guò)程演示i=Ni=N-1i=5i=4i=3i=2i=1現(xiàn)在是29頁(yè)\一共有77頁(yè)\編輯于星期三t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法過(guò)程演示i=Ni=N-1i=5i=4i=3i=2i=1現(xiàn)在是30頁(yè)\一共有77頁(yè)\編輯于星期三t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法過(guò)程演示i=Ni=N-1i=5i=4i=3i=2i=1現(xiàn)在是31頁(yè)\一共有77頁(yè)\編輯于星期三t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法過(guò)程演示i=Ni=N-1i=5i=4i=3i=2i=12.遞歸現(xiàn)在是32頁(yè)\一共有77頁(yè)\編輯于星期三t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

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

現(xiàn)在是33頁(yè)\一共有77頁(yè)\編輯于星期三t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

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

現(xiàn)在是34頁(yè)\一共有77頁(yè)\編輯于星期三t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

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

現(xiàn)在是35頁(yè)\一共有77頁(yè)\編輯于星期三t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

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

現(xiàn)在是36頁(yè)\一共有77頁(yè)\編輯于星期三t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

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

現(xiàn)在是37頁(yè)\一共有77頁(yè)\編輯于星期三t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

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

現(xiàn)在是38頁(yè)\一共有77頁(yè)\編輯于星期三

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

現(xiàn)在是39頁(yè)\一共有77頁(yè)\編輯于星期三前向算法過(guò)程演示t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1i=Ni=N-1i=5i=4i=3i=2i=1

現(xiàn)在是40頁(yè)\一共有77頁(yè)\編輯于星期三t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法過(guò)程演示i=Ni=N-1i=5i=4i=3i=2i=1現(xiàn)在是41頁(yè)\一共有77頁(yè)\編輯于星期三t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法過(guò)程演示i=Ni=N-1i=5i=4i=3i=2i=1現(xiàn)在是42頁(yè)\一共有77頁(yè)\編輯于星期三t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法過(guò)程演示i=Ni=N-1i=5i=4i=3i=2i=1現(xiàn)在是43頁(yè)\一共有77頁(yè)\編輯于星期三t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法過(guò)程演示i=Ni=N-1i=5i=4i=3i=2i=1現(xiàn)在是44頁(yè)\一共有77頁(yè)\編輯于星期三t=1t=2t=3t=4t=5t=Tt=7t=6t=T-1

前向算法過(guò)程演示i=Ni=N-1i=5i=4i=3i=2i=1現(xiàn)在是45頁(yè)\一共有77頁(yè)\編輯于星期三t=1t=2t=3t=4t=5t=Tt=T-1t=6t=7

前向算法過(guò)程演示i=Ni=N-1i=5i=4i=3i=2i=1現(xiàn)在是46頁(yè)\一共有77頁(yè)\編輯于星期三t=1t=2t=3t=4t=5t=Tt=T-1t=6t=7

前向算法過(guò)程演示i=Ni=N-1i=5i=4i=3i=2i=1現(xiàn)在是47頁(yè)\一共有77頁(yè)\編輯于星期三前向算法過(guò)程演示t=1t=2t=3t=4t=5t=Tt=T-1t=6t=7i=Ni=N-1i=5i=4i=3i=2i=13.計(jì)算P(O|λ)現(xiàn)在是48頁(yè)\一共有77頁(yè)\編輯于星期三t=1t=2t=3t=4t=5t=Tt=T-1t=6t=7

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

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

。解法如下：

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

現(xiàn)在是51頁(yè)\一共有77頁(yè)\編輯于星期三例（續(xù)）2.當(dāng)t=2時(shí)：3.當(dāng)t=3時(shí)：

現(xiàn)在是52頁(yè)\一共有77頁(yè)\編輯于星期三例（續(xù)）4.當(dāng)t=4時(shí)：所以最終有：

P(O|λ)=4(1)+4(2)+4(3)=0.0717696即觀察序列O由HMM模型產(chǎn)生的概率現(xiàn)在是53頁(yè)\一共有77頁(yè)\編輯于星期三例（續(xù)）最后將其計(jì)算過(guò)程示意圖表示如下：現(xiàn)在是54頁(yè)\一共有77頁(yè)\編輯于星期三問(wèn)題2—解碼問(wèn)題

所求的Q應(yīng)當(dāng)在某個(gè)準(zhǔn)則下是“最優(yōu)”的,因此也稱Q為最優(yōu)路徑,解碼問(wèn)題即是確定最優(yōu)路徑的問(wèn)題?，F(xiàn)在是55頁(yè)\一共有77頁(yè)\編輯于星期三

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

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

狀態(tài)集Q｛S1,S2,S3｝觀察序列集O={A,B}現(xiàn)在是59頁(yè)\一共有77頁(yè)\編輯于星期三例（續(xù)）

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

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

現(xiàn)在是60頁(yè)\一共有77頁(yè)\編輯于星期三例（續(xù)）2.當(dāng)t=2時(shí)：3.當(dāng)t=3時(shí)：現(xiàn)在是61頁(yè)\一共有77頁(yè)\編輯于星期三例（續(xù)）4.當(dāng)t=4時(shí)：

現(xiàn)在是62頁(yè)\一共有77頁(yè)\編輯于星期三例（續(xù)）其遞推結(jié)果為：可以看出，最有可能的狀態(tài)序列是：

S1，S2，S2，S2.現(xiàn)在是63頁(yè)\一共有77頁(yè)\編輯于星期三例（續(xù)）其計(jì)算結(jié)果示意圖如下所示：綠色的箭頭表示最有可能的狀態(tài)序列

現(xiàn)在是64頁(yè)\一共有77頁(yè)\編輯于星期三問(wèn)題3—學(xué)習(xí)問(wèn)題也稱訓(xùn)練問(wèn)題、參數(shù)估計(jì)問(wèn)題

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

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

，aij

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