隱馬爾科夫模型hiddenmarkovmodel

1、第九講 隱馬爾可夫模型初步Chapter 9 Hidden Markov Model (Part A),徐從富xucongfu@zju.edu.cn浙江大學(xué)人工智能研究所2003年10月第一稿2005年9月修改補(bǔ)充,浙江大學(xué)計(jì)算機(jī)學(xué)院《人工智能引論》課件,目 錄,HMM的由來(lái)馬爾可夫性和馬爾可夫鏈HMM實(shí)例HMM的三個(gè)基本算法主要參考文獻(xiàn),HMM的由來(lái),1870年，俄國(guó)有機(jī)化學(xué)家Vladimir V.

2、Markovnikov第一次提出馬爾科夫模型馬爾可夫模型馬爾可夫鏈 隱馬爾可夫模型,馬爾可夫性,如果一個(gè)過(guò)程的“將來(lái)”僅依賴“現(xiàn)在”而不依賴“過(guò)去”，則此過(guò)程具有馬爾可夫性,或稱此過(guò)程為馬爾可夫過(guò)程X(t+1) = f( X(t) ),馬爾科夫鏈,時(shí)間和狀態(tài)都離散的馬爾科夫過(guò)程稱為馬爾科夫鏈記作{Xn = X(n), n = 0,1,2,…}在時(shí)間集T1 = {0,1,2,…}上對(duì)離散狀態(tài)的過(guò)程相繼觀察的結(jié)果鏈的狀態(tài)

3、空間記做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.50 0.25 0.25陰天 0.375 0.25 0.

4、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)Pij(m,m+n)與m無(wú)關(guān)時(shí)，稱馬爾科夫鏈為齊次馬爾科夫鏈，通常說(shuō)的馬爾科夫鏈都是指齊次馬爾科夫鏈。,HMM實(shí)例,,HMM實(shí)例——描述,設(shè)有N個(gè)缸，每個(gè)缸中裝有很多彩球，球的顏色由一組概率分布描述。實(shí)驗(yàn)進(jìn)行方式如下根據(jù)初

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

6、狀態(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, ..., qT,o1, o2, ..., oT,HMM的組成示

7、意圖,HMM組成,HMM的基本要素,用模型五元組 ＝（ N, M, π ，A，B）用來(lái)描述HMM，或簡(jiǎn)寫(xiě)為 =(π ，A，B),HMM可解決的問(wèn)題,問(wèn)題1：給定觀察序列O=O1,O2,…OT,以及模型 , 如何計(jì)算P(O|λ)？問(wèn)題2：給定觀察序列O=O1,O2,…OT以及模型λ,如何選擇一個(gè)對(duì)應(yīng)的狀態(tài)序列 S = q1,q2,…qT，使得S能夠最為合理地解釋觀察序列O？問(wèn)

8、題3：如何調(diào)整模型參數(shù) , 使得P(O|λ)最大？,解決問(wèn)題1—— 基礎(chǔ)方法,給定一個(gè)固定的狀態(tài)序列S=(q1，q2，q3…) 表示在qt狀態(tài)下觀測(cè)到Ot的概率 N=5, M=100, 其計(jì)算量為1072！,,,,,解決問(wèn)題1—— 前向法,動(dòng)態(tài)規(guī)劃定義前向變量初始化：遞歸：終結(jié)：,,,,前向法示意圖,,,1 ... t

9、 t+1 ...,,,,,,a1j,,,at1,qN.qi.qj....q1,,,atN,ati,aNj,aij,當(dāng)N=5, M=100時(shí), 其計(jì)算量為3000！,解決問(wèn)題1 ——后向法,與前向法類似定義后向變量初始化：遞歸：終結(jié)：,,,,Viterbi算法,目的：給定觀察序列O以及模型λ,如何選擇一個(gè)對(duì)應(yīng)的狀態(tài)序列S ，使得S能夠最為合理的解釋觀察序列O？N和T分別為狀態(tài)個(gè)數(shù)和序列長(zhǎng)度

10、定義：我們所要找的，就是T時(shí)刻最大的 所代表的那個(gè)狀態(tài)序列,Viterbi算法(續(xù)),初始化：遞歸：終結(jié)：求S序列：,Baum-Welch算法(模型訓(xùn)練算法),目的：給定觀察值序列O，通過(guò)計(jì)算確定一個(gè)模型l ， 使得P(O| l)最大。算法步驟：1. 初始模型（待訓(xùn)練模型） l0,2. 基于l0 以及觀察值序列O，訓(xùn)練新模型 l；3. 如果 log P(X|l) - lo

11、g(P(X|l0) < Delta，說(shuō)明訓(xùn)練已經(jīng)達(dá)到預(yù)期效果， 算法結(jié)束。4. 否則，令l0 ＝ l ，繼續(xù)第2步工作,Baum-Welch算法(續(xù)),定義：,Baum-Welch算法(續(xù)2),參數(shù)估計(jì)：,幾種典型形狀的馬爾科夫鏈,a. A矩陣沒(méi)有零值的Markov鏈b. A矩陣有零值的Markov鏈c./d. 左－右形式的Markov鏈,HMM的應(yīng)用領(lǐng)域,語(yǔ)音識(shí)別機(jī)器視覺(jué)人臉檢測(cè)機(jī)器人足球圖像處理圖像去噪

12、圖像識(shí)別生物醫(yī)學(xué)分析DNA/蛋白質(zhì)序列分析,主要參考文獻(xiàn),1. Lawrence R. Rabiner, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. Proceedings 1989.ftp://10.11.11.111/課件/徐從富_AI/補(bǔ)充材料/隱Markov模型.pdf或ftp://10.214.1