隱馬爾科夫模型

1、隱馬爾可夫簡介隱馬爾可夫簡介閆曉龍閆曉龍1什么是隱什么是隱馬爾可夫馬爾可夫 引例： 一個盲人可能不能直觀的觀察到天氣的情況，但是民間傳說告訴我們海藻的狀態(tài)在某種概率上是和天氣的情況相關的。在這種情況下我們有兩個狀態(tài)集合，一個可以觀察到的狀態(tài)集合（海藻的狀態(tài)）和一個隱藏的狀態(tài)（天氣狀況）2outlinel馬爾可夫過程馬爾可夫過程l隱隱馬爾可夫模型馬爾可夫模型l隱隱馬爾可夫模型的問題馬爾可夫模型的問題l參考文獻參考文獻3馬爾可夫過程馬爾可夫過程 馬爾可夫過程（Markov process）是一類隨機過程。它的原始模型馬爾可夫鏈，由俄國數(shù)學家A.A.馬爾可夫于1907年提出 馬爾可夫過程有兩個假設：

2、 系統(tǒng)在時刻t的狀態(tài)只與時刻t-1處的狀態(tài)相關 其中，t為大于1的任意數(shù)值，k為任意狀態(tài) 狀態(tài)轉移概率與時間無關 121|,.|tjtitktjtiP qS qS qSP qS qS11|tjtikjkiP qSqSP qSqS4馬爾可夫過程馬爾可夫過程馬爾可夫過程的三個部分：馬爾可夫過程的三個部分：1. 狀態(tài)狀態(tài)：晴天、陰天和雨天2. 狀態(tài)轉移矩陣狀態(tài)轉移矩陣：每種天氣轉換的概率3. 初始向量初始向量：定義系統(tǒng)在時間為0的時候的狀態(tài)的概率abc5隱馬爾可夫模型隱馬爾可夫模型 隱馬爾可夫模型（隱馬爾可夫模型（Hidden Markov Model，HMM）是統(tǒng)）是統(tǒng)計模型，它計模型，它用來描述

3、用來描述一個含有隱含未知參數(shù)的一個含有隱含未知參數(shù)的馬爾可夫過程馬爾可夫過程 在在MM中，每一個狀態(tài)代表一個可觀察事件中，每一個狀態(tài)代表一個可觀察事件 在在HMM中，存在著兩種狀態(tài)，一種為可觀察狀態(tài)，另一種中，存在著兩種狀態(tài)，一種為可觀察狀態(tài)，另一種為隱藏狀態(tài)為隱藏狀態(tài)6隱隱馬爾可夫馬爾可夫模型模型l 隱隱馬爾可夫過程是一個雙重馬爾可夫過程是一個雙重隨機過程隨機過程：1. 第一重隨機過程：為狀態(tài)之間的相互轉移。由狀態(tài)轉移概率矩陣描述2. 另一重隨機過程：狀態(tài)到輸出之間的轉移。這由輸出概率來定義7隱隱馬爾可夫馬爾可夫模型模型因馬爾可夫模型可由五元組因馬爾可夫模型可由五元組=（N,M,A,B,)表

4、示：表示： N：狀態(tài)數(shù)目：狀態(tài)數(shù)目 M：觀測樣本數(shù)目：觀測樣本數(shù)目 A：狀態(tài)轉移矩陣：狀態(tài)轉移矩陣 B：混淆矩陣：混淆矩陣 ：初始狀態(tài)概率：初始狀態(tài)概率8隱馬爾可夫隱馬爾可夫模型模型 三個重要假設：三個重要假設：1. 馬爾科夫性馬爾科夫性2. 穩(wěn)定性（時間無關性）穩(wěn)定性（時間無關性）3. 觀測觀測樣本獨立性樣本獨立性9隱馬爾可夫隱馬爾可夫模型模型 三個問題三個問題1.概率計算問題概率計算問題: 已知模型參數(shù)，計算某一給定可觀察狀態(tài)序列的概率2.學習問題：學習問題：根據(jù)觀察到的序列集來找到一個最有可能的 HMM模型3.預測問題：預測問題：根據(jù)可觀察狀態(tài)的序列找到一個最可能的隱藏狀態(tài)序列10隱馬爾

5、可夫模型隱馬爾可夫模型-問題一問題一 問題一問題一：給定模型 和觀測序列 ，計算在模型 下觀測序列O出現(xiàn)的概率 直接計算法：直接計算法： 假設長度為T的狀態(tài)序列為 ，已知觀測序列為 O 狀態(tài)序列 的概率為 對固定的狀態(tài)序列 ，觀測序列O的概率為=, ,A B12,.,oTOo o|P O12, ,.,TIi iiI11 2213|.TTii ii iiiP Iaaa 1212| ,.bTiiiTP O Ibo boo11隱馬爾可夫隱馬爾可夫模型模型-問題一問題一 O和 I同時出現(xiàn)的聯(lián)合概率為 對所有可能的狀態(tài)序列 求和，得到觀測序列O的概率： 111 22112, | ,|.TTTiii ii

6、iiiTP O IP O IP Ibo a boaboII 111 2211212,.,i| ,|.TTTIiii iiiiTi iP OP O IP Ibo a boabo12隱馬爾可夫隱馬爾可夫模型模型-問題一問題一 前向算法前向算法： 給定因馬爾可夫模型，定義到時刻t部分觀測序列為o1,o2,ot且狀態(tài)為qi的概率為前向概率，記作 初值 遞推 終止 12,.,|tttiiP o oo iq 11,1,2,.,iiib oiN 111,1,2,.NNttjiitjij ab oi 1|NTiP Oi13隱馬爾可夫模型隱馬爾可夫模型-問題一問題一l 前向算法前向算法示意圖：示意圖：14隱馬爾

7、可夫隱馬爾可夫模型模型-問題二問題二 學習問題學習問題 給定一系列觀察序列樣本O，估計模型的參數(shù) ，使得在該模型下觀測序列概率最大 已知觀察序列樣本 ，要求模型參數(shù)的值，我們用EM算法來實現(xiàn) 最大似然估計法一種有效的參數(shù)估計法若總體X屬于離散型，其分布律 的形式為已知，為待估參數(shù)， 是可能取值的范圍。設 是來自X的樣本，則它的聯(lián)合分布律為又設 是對應于樣本 的一個樣本值。易知樣本 取到觀察值 的概率，亦即事件 發(fā)生的概率為, ,A B;,P Xxp x12,.,nXXX1;niip x12,.,nx xx1122,.,nnXx XxXx 121,.,;,nniiLL x xxp x15隱隱馬爾

8、可夫馬爾可夫模型模型-問題二問題二EM算法：算法：我們將觀測序列數(shù)據(jù)看作觀測數(shù)據(jù)O，狀態(tài)序列數(shù)據(jù)看作不可觀測的隱數(shù)據(jù) I ，em算法可以在含有隱數(shù)據(jù)的情況下迭代的求出模型的參數(shù)設O為觀測變量、I為隱藏變量，為需要求解的參數(shù)。則：等式兩邊同時乘以q(I),并對I求和，有由于I與P(O|)相互獨立,且 ,則 , |,ln|ln, |ln|,ln, |lnlnp|,lnq, |,lnlnp O Ip Op I Op Op O Ip I Op O Iq II OIp O Ip I Oq Iq I , |I|,ln|lnlnIIp O IpOq Ip Oq Iq Iq Iq I , |,lnO|lnln

9、, |lnln|,IIIp O Ip I Opq Iq Iq Iq Ip O Iq Iq Iq Iq Ip I O 1Iq I 16隱隱馬爾可夫馬爾可夫模型模型-問題二問題二我們的目的是使似然函數(shù)lnp(O|)最大化，引入相對熵的定義設p(x)和q(x)為隨機變量x的兩個不同的分布密度，則他們的相對熵定義為： 的取值始終非負，當且僅當 p(x)=q(x)時取值為零我們記則有 logxp xD pqp xq xD pq ,|,lnln|,IIp O IL qq Iq Iq ID pqq Ip I OlnO|,pL qD pq17隱隱馬爾可夫馬爾可夫模型模型-問題二問題二 EM算法的兩個步驟： 步

10、驟一固定一個，求一個分布q(I)使得 最大化得 步驟二固定q(I),求一個，使得下界 最大化EM算法不斷重復E步驟和M步驟，直到 收斂lnO|,pL qD pq,L q |,q Ip I OlnO|p , |,ln,|,ln, |,ln, |,IIIp O IL qq Iq IL qp I Op O Ip I Op O IL q 18隱隱馬爾可夫馬爾可夫模型模型-問題三問題三 預測問題預測問題:已知模型和觀測序列O，求對給定觀測序列條件概率P(I|O)最大的隱藏狀態(tài)序列 I 解決方法解決方法-Viterbi算法算法圖（a）圖b19隱隱馬爾可夫馬爾可夫模型模型-問題三問題三 首先引入兩個變量和

11、定義在時刻t狀態(tài)為i的所有單個路徑 中概率最大值為 遞推公式 定義在時刻t狀態(tài)為i的所有單個路徑 中概率最大的路徑的第t-1個結點為12, ,.,ti ii 121111, ,.,max,., ,.,|,1,2,.,ttttti iiiP ii ii ooiN 11argmax,1,2,.,ttjij Nij aiN 1211111, ,.,11max, ,., ,.,|maxb,1,2,.,;1,2,.,1ttttti iitjiitj NiP ii ii ooj aoiN tT 20隱隱馬爾可夫馬爾可夫模型模型-問題三問題三 算法： 初始化 遞推，對t=2,3,T 終止最優(yōu)回溯。對t=T-1,T-2,1得到最優(yōu)路徑 111,1,2,.,0,1,2,.,iiib oiNiiN *1*1maxargmaxTi NTTi NPiii *12, ,.,TIi ii*11tttii21 1111max,1,2,.,argmax,1,2,.,ttjiitj Nttjij Nij ab