1、,隱馬爾可夫模型,2,隱馬爾科夫模型 馬爾可夫模型 隱馬爾可夫模型 隱馬爾可夫模型的三個基本問題 隱馬爾可夫模型的基本算法 隱馬爾可夫模型的應(yīng)用,隱馬爾可夫模型,3,馬爾可夫鏈 一個系統(tǒng)有 N 個狀態(tài) S1 , S 2 ,L, S N ，隨著時間推移，系統(tǒng)從 某一狀態(tài)轉(zhuǎn)移到另一狀態(tài)，設(shè) qt 為時間 t 的狀態(tài)，系統(tǒng)在時間 t 處 于狀態(tài) S j 的概率取決于其在時間1,2,L, t - 1 的狀態(tài)，該概率為： P(q t = S j | q t -1 = Si , q t -2 = Sk ,L) 如果系統(tǒng)在 t 時間的狀態(tài)只與其在時間 t 1的狀態(tài)相關(guān)，則該 系統(tǒng)構(gòu)成一個離散的一階馬爾可夫鏈

2、(馬爾可夫過程)： P(q t = S j | q t -1 = Si , q t -2 = Sk ,L) = P(q t = S j | q t -1 = Si ),隱馬爾可夫模型,4,馬爾可夫模型(Markov Model) 如果只考慮獨立于時間 t 的隨機過程： P(q t = S j | q t -1 = Si ) = a i, j , 1 i, j N 其中狀態(tài)轉(zhuǎn)移概率 a i, j 必須滿足 a i, j 0 且,則該隨機過程稱為馬爾可夫模型。,隱馬爾可夫模型,5,馬爾可夫模型可視為隨機有限狀態(tài)自動機 該有限狀 態(tài)自動機 的每一個 狀態(tài)轉(zhuǎn)換 都有一相 應(yīng)概率， 表示自動 機采用這

3、一狀態(tài)轉(zhuǎn) 換的可能 性,6,例 假定一段時間內(nèi)的氣象可由一三狀態(tài) 馬爾可夫模型 M 描述：S 1 ：雨，S 2 ：多云， S 3 ：晴，轉(zhuǎn)移概率矩陣為：,0 .3 0 .2 0 .8,0 .3 0 .6 0 .1,0 .4 A = a ij = 0 .2 0 .1 隱馬爾可夫模型,隱馬爾可夫模型,7,例（續(xù)） 如果第一天為晴天，根據(jù)這一模型，在今后七天中天氣為 O =晴晴雨雨晴云晴 的概率為： P(O | M ) = P(S 3 , S 3 , S 3 , S1 , S1 , S 3 , S 2 , S 3 | M ) = P(S 3 ) P(S 3 | S 3 ) P(S 3 | S 3 )

4、 P(S1 | S 3 ) P(S1 | S1 ) P(S 3 | S1 ) P(S 2 | S 3 ) P(S 3 | S 2 ) = 1 a33 a33 a31 a11 a13 a32 a23 = (0.8)(0.8)(0.1)(0.4)(0.3)(0.1)(0.2) = 1.536 10 4,隱馬爾可夫模型,8,隱馬爾可夫模型 (Hidden Markov Model, HMM) 在MM中，每一個狀態(tài)代表一個可觀察的 事件 在HMM中觀察到的事件是狀態(tài)的隨機函 數(shù)，因此該模型是一雙重隨機過程，其 中狀態(tài)轉(zhuǎn)移過程是不可觀察（隱蔽）的 (馬爾可夫鏈)，而可觀察的事件的隨機過 程是隱蔽的狀態(tài)轉(zhuǎn)

5、換過程的隨機函數(shù)(一 般隨機過程)。,HMM的應(yīng)用領(lǐng)域 語音識別 語言處理 機器視覺 人臉檢測 機器人足球 圖像處理 圖像去噪 圖像識別 生物醫(yī)學(xué)分析 DNA/蛋白質(zhì)序列分析,隱馬爾可夫模型,9,實例 一房間有 N 只盒子，每只甕中有 M 種不同顏色的球。 根據(jù)某一概率分布隨機地選擇一個初始盒子，根據(jù)不同顏色 球的概率分布從中隨機取出一個球，并報告球的顏色。然 后根據(jù)某一概率分布隨機地選擇另一只盒子，再根據(jù)不同顏 色球的概率分布從中隨機取出一個球，并報告球的顏 色，。對房間外的觀察者，可觀察的過程是不同顏色球 的序列，而盒子的序列是不可觀察的。 這里每只盒子對應(yīng) HMM 模型中的狀態(tài)，球的顏色

6、對應(yīng) 于狀態(tài)的輸出符號，從一只盒子轉(zhuǎn)向另一只盒子對應(yīng)于狀態(tài)轉(zhuǎn) 換，從一只盒子中取球?qū)?yīng)于從一狀態(tài)輸出觀察符號。,隱馬爾可夫模型,10,實例（續(xù)） Urn 3 Urn 2 Urn 1 Veil Observed Ball Sequence,隱馬爾可夫模型,11,實驗中的幾個要點 不能直接觀察盒子間的轉(zhuǎn)移 從盒子中所選取的球的顏色和盒子并不是一 一對應(yīng)的 每次選取哪個盒子由一組轉(zhuǎn)移概率決定,隱馬爾可夫模型,12,HMM的組成 五元組： = ( N , M , A, B, ) 簡記為： = ( A, B, ) N ：狀態(tài)數(shù)目 M ：可能的觀察值數(shù)目 A ：與時間無關(guān)的狀態(tài)轉(zhuǎn)移概率矩陣 B ：給定狀態(tài)

7、下，觀察值概率分布 ：初始狀態(tài)空間的概率分布,隱馬爾可夫模型,13,狀態(tài)轉(zhuǎn)移概率矩陣,隱馬爾可夫模型,14,觀察值概率分布矩陣,隱馬爾可夫模型,15,初始狀態(tài)概率分布 = i i = P(q1 = S i ) ，1 i N,隱馬爾可夫模型,16,觀察序列產(chǎn)生步驟 給定模型 = ( A, B , ) ，觀察序列 O = O1 , O 2 ,., OT 可由 以下步驟產(chǎn)生： 1.根據(jù)初始狀態(tài)概率分布 = i 選擇一初始狀態(tài) q1 = S i ； 2.設(shè) t = 1 ； 3.根據(jù)狀態(tài) S i 的輸出概率分布 b j (k ) ，輸出 Ot = v k ； 4.根據(jù)狀態(tài)轉(zhuǎn)移概率分布 a ij ，轉(zhuǎn)移到

8、新狀態(tài) q t +1 = S j ； 5.設(shè) t = t + 1 ，如果 t T ，重復(fù)步驟 3、4，否則結(jié)束。,隱馬爾可夫模型,17,HMM中的三個基本問題 問題 1：給定觀察序列 O = O1 , O2 , OT ，以及模型 = ( A, B, ) ， 如何計算 P(O | ) ？ 問題 2：給定觀察序列 O = O1 , O2 , OT 及模型 = ( A, B, ) ，如 何選擇一個對應(yīng)的狀態(tài)序列 S = q1 , q 2 ,., qT ，使得 S 能夠最為合理地 解釋觀察序列 O ？ 問題 3：如何調(diào)整模型參數(shù) = ( A, B, ) ，使得 P(O | ) 最大？,18,解決問題1

9、,直接計算是不現(xiàn)實的，因為假定所有的概率都是非零的，那么就有 個狀態(tài)序列 有效方法：向前算法，動態(tài)規(guī)劃,max P(q1 , q2 , qt = S i , O1 , O2 ,Ot | ),隱馬爾可夫模型,25,解決問題2：Viterbi算法 目標：給定一個觀察序列和 HMM 模型，如何有效選擇“最優(yōu)”狀態(tài)序 列，以“最好地解釋”觀察序列？ “最優(yōu)”概率最大： Q* = arg max P(Q | O, ) Q,Viterbi 變量： t (i) =,q1 ,q2 ,qt 1,遞歸關(guān)系： t +1 (i) = max t ( j) aji bi (Ot +1 ) i 其中，aji為在t時刻的q

10、j狀態(tài)到t+1時刻的qj的狀態(tài)轉(zhuǎn)移的概率 記憶變量：t (i) 紀錄概率最大路徑上當前狀態(tài)的前一個狀態(tài),隱馬爾可夫模型,27,解決問題3：HMM參數(shù)估計 給定觀察序列 O = O1 , O2 ,., OT 作 為訓(xùn)練數(shù)據(jù)，參數(shù)估計的目的是估計模型 中的i ，aij ，b j (k ) ，使得觀察序列 O 的概率 P(O | ) 最大。,隱馬爾可夫模型,28,狀態(tài)序列已知情況 可以由最大似然估計來估計 HMM 的參數(shù)：,在很多實際的情況下，HMM不能被直接的判斷，這就變成了一個學(xué)習(xí)問題，因為對于給定的可觀察狀態(tài)序列 O 來說，沒有任何一種方法可以精確地找到一組最優(yōu)的 HMM 參數(shù) 使 P(O | ) 最大，于是人們尋求使其局部最優(yōu)的解