隱馬爾科夫模型

隱馬爾科夫模型

機(jī)器學(xué)習(xí)最重要的任務(wù)筑凫，是根據(jù)一些已觀察到的證據(jù)（例如訓(xùn)練樣本）來對感興趣的未知變量（例如類別標(biāo)記）進(jìn)行估計和推測。概率圖模型提供了一種描述框架，將學(xué)習(xí)任務(wù)歸結(jié)于計算變量的概率分布腺律，在概率模型中，利用已知變量推測未知變量的分布稱為推測宜肉。具體來說匀钧，假定所有關(guān)心的變量集合為Y，可觀測變量的集合為O谬返，其他變量的集合為R之斯，“生成式”模型考慮聯(lián)合概率分布P(Y,R,O),“判別式模型”考慮條件分布P(Y,R|O),給定以組觀測變量值，推斷就是由P(Y,R,O)或P(Y,R|O)得到條件概率分布P(Y|O)遣铝。

直接利用概率求和規(guī)則去消去變量R顯然是不可行佑刷，因為即使每個變量僅有兩種取值的簡單問題莉擒，其復(fù)雜度也是O(2^{|Y|+|R|})，另一方面瘫絮，屬性變量之間往往存在復(fù)雜的聯(lián)系涨冀。因此概率模型的學(xué)習(xí)，即基于訓(xùn)練來估計變量分布的參數(shù)往往相當(dāng)困難麦萤。為了便于研究高效的推斷和學(xué)習(xí)算法鹿鳖，需有一套能簡潔緊湊地表達(dá)變量之間的關(guān)系。

概率圖模型是一類用圖表達(dá)變量相關(guān)關(guān)系的概率模型壮莹，它以圖為表示工具翅帜，最常見的是用一個結(jié)點表示一個或一組隨機(jī)變量，結(jié)點之間的邊表示變量間的概率相關(guān)關(guān)系命满，即“變量關(guān)系圖”涝滴，根據(jù)邊的性質(zhì)不同，概率圖模型大致可分為良率：第一類是使用有向無環(huán)圖表示變量間的依賴關(guān)系胶台，稱為有向圖模型或貝葉斯網(wǎng)歼疮；第二類是使用無向圖表示變量間的相關(guān)關(guān)系，稱為無向圖模型或馬爾科夫網(wǎng)诈唬。

隱馬爾科夫模型(HMM)是結(jié)構(gòu)最簡單的動態(tài)貝葉斯網(wǎng)腋妙，這是一種著名的有向圖模型，主要用于時序數(shù)據(jù)建模讯榕，在語音識別骤素、自然語言處理等領(lǐng)域有廣泛應(yīng)用。

一愚屁、隱馬爾科夫模型的基本概念

1.隱馬爾科夫模型的定義

隱馬爾科夫模型是關(guān)于時序的概率模型济竹，描述由一個隱藏的馬爾科夫鏈隨機(jī)生成不可觀測的狀態(tài)的隨機(jī)序列，再由各個狀態(tài)生成一個觀測從而產(chǎn)生觀測隨機(jī)序列的過程霎槐。隱藏的馬爾科夫鏈隨機(jī)生成的狀態(tài)序列送浊，稱為狀態(tài)序列。每個狀態(tài)生成一個觀測丘跌，而由此產(chǎn)生的觀測的隨機(jī)序列袭景，稱為觀測序列。序列的每一個位置又可以看作是一個時刻闭树。

隱馬爾科夫模型由初始概率分布耸棒、狀態(tài)轉(zhuǎn)移概率分布以及觀測概率分布確定。

設(shè)Q是所有可能的狀態(tài)的集合报辱，V是所有可能的觀測集合：
Q= \{ q_1,q_2,\dots,q_N \},V=\{v_1,v_2,\dots,v_M \}
其中与殃，N是可能的狀態(tài)數(shù)，M是可能的觀測數(shù)

I是觀測長度為T的狀態(tài)序列，O是對應(yīng)的觀測序列：
I = (i_1,i_2,\dots,i_T)幅疼，O =(o_1,o_2,\dots,o_T)
A是狀態(tài)轉(zhuǎn)移概率矩陣：
A=[a_{ij}]_{N*N}
其中
a_{ij} = P(i_{t+1} = q_j|i_t = q_i),i=1,2\dots,N;j=1,2,\dots,N
是時刻t處于狀態(tài)q_i的條件下載時刻t+1轉(zhuǎn)移到狀態(tài)q_j的概率
B是觀測概率矩陣:
B=[b_j(k)]_{N*N}
其中
b_j(k) = P(o_t = v_k | i_t = q_j),k=1,2,\dots,M,j=1,2,\dots,M

\pi是初始狀態(tài)概率向量：
\pi = (\pi_i)
其中
\pi_i = P(i_1 = q_i),i=1,2,\dots,N
是時刻t+1處狀態(tài)q_i的概率

隱馬爾科夫模型由初始狀態(tài)概率向量\pi米奸、狀態(tài)轉(zhuǎn)移概率矩陣A和觀測概率矩陣B決定狀態(tài)序列。其中\pi,A決定狀態(tài)序列爽篷，B決定觀測序列悴晰。因此，隱馬爾科夫模型\lambda可以用三元符號表示逐工。
\lambda(A,B,\pi)

A,B,\pi稱為隱馬爾科夫三要素：
狀態(tài)轉(zhuǎn)態(tài)概率矩陣A與初始狀態(tài)概率向量\pi確定了隱藏的馬爾科夫鏈膨疏，生成不可觀測的狀態(tài)序列。觀測概率矩陣B確定了如何從狀態(tài)生成觀測钻弄，與狀態(tài)序列綜合確定了如何查產(chǎn)生觀測序列。

隱馬爾科夫模型作了兩個基本假設(shè)：

  1. 齊次馬爾科夫假設(shè)者吁，假設(shè)隱藏的馬爾科夫鏈在任意時刻t的狀態(tài)值依賴于前一時刻的狀態(tài)窘俺，與其他時刻的狀態(tài)無關(guān)，也與時刻t無關(guān)
    p(i|i_{t-1},o_{t-1},\dots,i_1,o_1)=P(i_t|i_{t-1}),t=1,2\dots,T
  2. 觀測獨立性假設(shè)复凳，即假設(shè)任意時刻的觀測只依賴于該時刻的馬爾科夫鏈的狀態(tài)瘤泪，與其他觀測及狀態(tài)無關(guān)。
    p(o_t|i_T,o_T,i_{t-1},o_{T-1},\dots,i_1,o_1)=P(o_t|i_t)

下面看一個隱馬爾科夫的例子
盒子與球模型假設(shè)有4個盒子育八，每個盒子里都裝有紅对途、白兩種顏色的球，盒子里的紅髓棋、白球數(shù)由表給出

盒子 1 2 3 4
紅球數(shù) 5 3 6 8
白球數(shù) 5 7 4 2

按照下面的方法抽球实檀，產(chǎn)生一個球的顏色的觀測序列

  • 開始，從4個盒子里以等概率隨機(jī)選取1個盒子按声，從這個盒子里隨機(jī)抽出1個球膳犹，記錄其顏色，放回：
  • 然后签则，從當(dāng)前盒子隨機(jī)轉(zhuǎn)移到下一個盒子须床，規(guī)則是：如果當(dāng)前盒子1，那么下一個盒子一定是2渐裂；如果當(dāng)前盒子是2或3豺旬，那么分別概率0.4或0.6,轉(zhuǎn)移到左邊或右邊的盒子；如果當(dāng)前盒子是4柒凉，那么各自以0.5的概率停留在盒子4或者轉(zhuǎn)移到盒子3
  • 確定轉(zhuǎn)移的盒子后族阅，再從這個盒子里隨機(jī)抽取一個球，記錄其顏色膝捞，放回
  • 如此下去耘分，得到球的顏色觀測序列

在這個過程中，觀測者只能觀測到球的顏色序列，觀測不到球是從哪個盒子里取出的求泰，即觀測不到盒子的序列央渣。

盒子對應(yīng)狀態(tài)，狀態(tài)集合是
Q = \{盒子1渴频，盒子2芽丹，盒子3，盒子4\}卜朗，N=4
球的顏色對應(yīng)觀測序列拔第，觀測的集合是
V= \{紅、白\},M=2
初始概率分布為
\pi = (0.25,0.25,0.25,0.25)
狀態(tài)概率分布為
A = \begin{bmatrix} 0 & 1 & 0 &0 \\[0.3em] 0.4 & 0 &0.6 & 0 \\[0.3em] 0 & 0.4 & 0 & 0.6 \\[0.3em] 0 & 0 &0.5 & 0.5 \end{bmatrix}
觀測概率分布為
B= \begin{bmatrix} 0.5 & 0.5 \\[0.3em] 0.3 & 0.7 \\[0.3em] 0.7 & 0.3 \\[0.3em] 0.8 & 0.2 \end{bmatrix}

2.觀測序列生成過程

輸入：隱馬爾科夫模型\lambda =(A,B,\pi)场钉，觀測序列長度T
輸出：觀測序列O=(o_1,o_2,\dots,o_T)

  1. 按照初始狀態(tài)分布\pi產(chǎn)生狀態(tài)i_1
  2. 令t=1
  3. 按照狀態(tài)i_t的觀測概率分布b_{i_t}(k)生成o_t
  4. 按照狀態(tài)i_t的狀態(tài)轉(zhuǎn)移概率分布\{a_{i_t},i_{t+1}\}產(chǎn)生狀態(tài)i_{t+1}蚊俺，i_{t+1} = 1,2,\dots,N
  5. 令t=t+1,如果t < T，轉(zhuǎn)步3,否則終止逛万。

3.隱馬爾科夫3個基本問題

  1. 概率計算問題泳猬。給定模型\lambda=(A,B,\pi)和觀測序列O=(o_1,o_2,\dots,o_T)，計算在模型\lambda下觀測O出現(xiàn)的概率P(O|\lambda)
  2. 學(xué)習(xí)問題宇植。已知預(yù)測序列O=（o_1,o_2,\dots,o_T)得封，估計模型\lambda = （A,B,\pi）參數(shù)，使得在該模型下觀測序列概率P(O|\lambda)最大指郁，即用最大似然估計的方法估計參數(shù)
  3. 預(yù)測問題忙上，也稱解碼(decoding)參數(shù)。已知模型\lambda = (A,B,\pi)和觀測序列O=(o_1,o_2,\dots,o_T)闲坎，求給定觀測序列條件概率P(I|O)最大狀態(tài)序列I=(i_1,i_2,\dots,i_T)疫粥。即給定觀測序列，求最有可能的對應(yīng)的狀態(tài)序列

二腰懂、概率計算算法

1.前向算法

前向概率給定隱馬爾科夫模型\lambda手形，定義到時刻t部分觀測序列為o_1,o_2,\dots,o_t且狀態(tài)為q_i的概率為向前概率，記作
a_t(i) = P(o_1,o_2,\dots,o_t,i_t = q_i|\lambda)
可以遞推地求得前向概率a_t(i)及觀測序列概率P(O\lambda)

算法
輸入：隱馬爾科夫模型\lambda悯恍，觀測序列O
輸出：觀測序列概率P(O|\lambda)

  1. 初值 a_1(i) = \pi_ib_i(o_1),i=1,2,\dots,N
  2. 遞推,對t=1,2,\dots,T-1库糠，a_{t+1}(i) = \bigg[\sum_{j=1}^N a_t(j)a_{ji}\bigg]b_i(o_{t+1}),i=1,2,\dots,N
  3. 終止P(O|\lambda)=\sum_{i=1}^N a_T(i)

案例考慮盒子和球模型\lambda = (A,B,\pi)，狀態(tài)集合Q=\{1,2,3\}涮毫，觀測集合V=\{紅瞬欧，白\}
A = \begin{bmatrix} 0.5 & 0.5 & 0.3 \\[0.3em] 0.3 & 0.5 &0.2 \\[0.3em] 0.2 & 0.3 & 0.5 \end{bmatrix}
B = \begin{bmatrix} 0.5 & 0.5 \\[0.3em] 0.4 & 0.6 \\[0.3em] 0.7 & 0.3 \end{bmatrix}
\pi = \begin{bmatrix} 0.2 \\[0.3em] 0.4 \\[0.3em] 0.4 \end{bmatrix}

設(shè)T = 3,O=(紅，白罢防，紅)艘虎，試用前向算法計算P(O|\lambda)

  1. 計算初值
    a_1(1) = \pi_1b_1(o_1) = 0.2*0.5 = 0.10 \\ a_1(2) = \pi_1b_2(o_1) = 0.4*0.4 = 0.16 \\ a_1(3) = \pi_1b_3(o_1) = 0.4*0.7
  2. 遞推計算
    a_2(1) =\bigg[ \sum_{i=1}^3a_1(i)a_i1\bigg]b_1(o_2) = (0.10*0.5+0.16*0.3+0.28*0.2)*0.5 = 0.077 \\ a_2(2) = \bigg[\sum_{i=1}^3 a_1(i)a_{i2}\bigg]b_2(o_2) = (0.10*0.2+0.16*0.5+0,28*0.3)*0.6 = 0.1104 \\ a_2(3) = \bigg[\sum_{i=1}^3a_1(i)a_{i3}b_3(o_2)\bigg]=(0.10*0.3+0.16*0.2+0.28*0.5)*0.3 = 0.0606 \\ a_3(1) = \bigg[\sum_{i=1}^3a_2(i)a_{i2}\bigg]b_1(o_3) = (0.077*0.5+0.1104*0.3+0.0606*0.2)*0.5 = 0.4187 \\ a_3(2) = \bigg[\sum_{i=1}^3 a_2(i)a_{i2}\bigg]b_2(o_3) = (0.077*0.2+0.1104*0.5+0.0606*0.3)*0.4 = 0.3551 \\ a_3(3) = \bigg[\sum_{i=1}^3 a_2(i)a_{i3}\bigg]b_3(o_3) = (0.077*0.3+0.1104*0.2+0.0606*0.5)*0.7 = 0.05284
  3. 終止 P(O\lambda) = \sum_{i=1}^3 a_3(i) = 0.04187+0.03551+0.05284 = 0.13022

2.后向算法

后向算法給定隱馬爾科夫模型\lambda，定義在t時刻狀態(tài)為q_i的條件下咒吐，從t+1到T的部分觀測序列為o_{t+1},o_{t+2},\dots,T的概率為后向概率野建，記作
\beta_t(i) = P(o_{t+1},o_{t+2},\dots,o_T|i_t=q_i,\lambda)
可以引用遞歸的方法得到后向概率\beta_t(i)以及觀測序列概率P(O|\lambda)
算法
輸入：隱馬爾科夫模型\lambda属划，觀測序列O
輸出：觀測序列概率P(O|\lambda)

  1. \beta_T(i) = 1,i =1,2,\dots,N
  2. 對t = T-1,T-2,\dots,1 ,\beta_t(i) = \sum_{j=1}^Na_{ij}b_j(o_{t+1})\beta_{t+1}(j),i=1,2,\dots,N
  3. P(O|\lambda) = \sum_{i=1}^N\pi_ib_i(o_1)\beta_1(i)
前后向概率的關(guān)系.png

利用前向概率和后向概率的定義可以將觀測序列概率P(O|\lambda)統(tǒng)一寫成
P(O|\lambda) = \sum_{i=1}^N\sum_{j=1}^Na_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j),t=1,2,\dots,T-1

3.一些概率與期望的計算

利用前向概率\lambda和后向概率，可以得到關(guān)于單個狀態(tài)和兩個狀態(tài)概率的計算公式

(1) 給定模型\lambda和觀測O候生，在時刻t處于狀態(tài)q_i的概率

記為\Upsilon_t(i) = P(i_t = q_i|O,\lambda)
可以通過前向后向概率計算
\Upsilon_t(i) = P(i_t=q_i|O,\lambda) = \frac{P(i_t = q_i,O|\lambda)}{P(O|\lambda)}

由向前概率a_t(i)和向后概率\beta_t(i)定義可知
a_t(i)\beta_t(i) = P(i_t = q_i,O|\lambda)
于是得到
\Upsilon_t(i) = \frac{a_t(i)\beta_t(i)}{P(O|\lambda) } = \frac{a_t(i)\beta_t(i)}{\sum_j=1^N a_t(j)\beta_t(j)}

(2).給定模型\lambda和觀測O同眯，在時刻t處于狀態(tài)q_i且時刻t+1處于狀態(tài)q_j的概率

記作
\xi_t(i,j) = P(i_t=q_i,i_{t+1}=q_j) |O,\lambda)
可以通過前向后向概率基色
\xi_t(i,j) = frac{P(i_t = q_i,i_{t+1} = q_j,O|\lambda)}{P(O|\lambda)} = \frac{P(i_t=q_i,i_{t+1}=q_j,O|\lambda}{\sum_{i=1}^N\sum_{j=1}^N P(i_t = q_i,i_{t+1}=q_j,O|\lambda}
而
P(i_t = q_i,i_{t+1}=q_j,O|\lambda) = a_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)
所以
\Upsilon_t(i,j) = \frac{ a_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)}{\sum_{i=1}^N\sum_{j=1}^N a_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)}

(3).將\Upsilon_t(i)和\xi_t(i,j)對對各時刻t求和可以得到一些有用的概率

  1. 在觀測O下狀態(tài)i出現(xiàn)的期望
    \sum_{t=1}^T \Upsilon_t(i)
  2. 在觀測O下狀態(tài)i轉(zhuǎn)移的期望
    \sum_{t=1}^{T-1}\Upsilon_t(i)
  3. 在觀測O下狀態(tài)i轉(zhuǎn)移到狀態(tài)j的期望
    \sum_{t=1}^{T-1}\xi_t(i,j)

三、學(xué)習(xí)算法

隱馬爾科夫模型的學(xué)習(xí)唯鸭，根據(jù)訓(xùn)練數(shù)據(jù)包括預(yù)測序列和對應(yīng)的狀態(tài)序列還是只有預(yù)測序列须蜗，可分別由監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)實現(xiàn)。

1.監(jiān)督學(xué)習(xí)方法

假設(shè)已給訓(xùn)練數(shù)據(jù)包含S個長度相同的觀測序列和對應(yīng)的狀態(tài)序列\{(O_1,I_1),(O_2,I_2),\dots,(O_s,I_s)\}目溉，那么可以利用極大似然估計法來看估計隱馬爾科夫模型的參數(shù)

（1）轉(zhuǎn)移概率a_{ij}的估計

設(shè)樣本中時刻t處于狀態(tài)i時刻t+1轉(zhuǎn)移到狀態(tài)j的頻數(shù)為A_{ij}明肮，那么狀態(tài)狀態(tài)轉(zhuǎn)移的概率a_{ij}的估計是
\hat a_{ij}=\frac{A_{ij}}{\sum_{i=1}^N A_{ij}},i=1,2,\dots,N;j=1,2,\dots,N

(2)觀測概率b_j(k)的估計

設(shè)樣本中狀態(tài)為j并觀測為k的頻數(shù)是B_{jk}，那么狀態(tài)為j觀測為k的概率b_j(k)的估計是
\hat b_j(k) = \frac{B_{jk}}{\sum_{k=1}^M B_{jk}},j=1,2,\dots,N;k=1,2,\dots,N

(3)初始狀態(tài)概率\pi_i的估計\hat \pi_i為S個樣本初始狀態(tài)為q_i的頻率

由于監(jiān)督學(xué)習(xí)需要使用標(biāo)注的訓(xùn)練數(shù)據(jù)缭付，而人工標(biāo)注訓(xùn)練數(shù)據(jù)往往代價很高柿估，有時就會利用無監(jiān)督學(xué)習(xí)方法

2.Baum-Welch算法

假設(shè)給定訓(xùn)練數(shù)據(jù)只包含S個長度為T的觀測序列\{O_1,O_2,\dots,O_s\}
而沒有對應(yīng)的狀態(tài)序列，目標(biāo)是學(xué)習(xí)隱馬爾科夫模型\lambda = (A,B,\pi)的參數(shù)陷猫。我們將觀測序列數(shù)據(jù)看作觀測數(shù)據(jù)O秫舌，狀態(tài)序列數(shù)據(jù)看作不可觀測的隱數(shù)據(jù)I，那么隱馬爾科夫模型事實上是一個含有一個隱變量的概率模型
P(O|\lambda) = \sum_I P(O|I,\lambda)P(I|\lambda)
它的參數(shù)學(xué)習(xí)可由EM算法實現(xiàn)

(1)確定完全數(shù)據(jù)的對數(shù)似然函數(shù)

所有觀測數(shù)據(jù)寫成O=(o_1,o_2,\dots,o_0)烙丛，所有隱數(shù)據(jù)寫成I=(i_1,i_2,\dots,i_T)。完全數(shù)據(jù)是(O,T) = (o_1,o_2,\dots,o_T,i_1,i_2,\dots,i_T)羔味。完全數(shù)據(jù)的對數(shù)似然函數(shù)是
log P(O,I|\lambda)

(2)EM算法的E步河咽，求Q函數(shù)Q(\lambda,\bar \lambda)

Q(\lambda,\bar \lambda) = \sum_I log P(O,I|\lambda)P(O,I|\bar \lambda)
其中,\bar \lambda是隱馬爾科夫模型參數(shù)的當(dāng)前估計值,\lambda是要極大化隱馬爾科夫模型參數(shù)

P(O,I|\lambda)=\pi_{1}b_{i_1}(o_1)a_{i_1,i_2}b_{i_2}(o_2)\dots a_{i_{T-1},i_T}b_{i_T} (O_T)
于是函數(shù)Q(\lambda,\bar \lambda)可以寫成
Q(\lambda,\bar \lambda) = \sum_I log\, \pi_{i_1}P(O,I|\bar \lambda) + \sum_I\bigg(\sum_{t=1}^{T-1}log \,a_{i_t,i_{t+1}}\bigg)P(O,I|\bar \lambda+\sum_I \bigg( \sum_{t=1}^T log \,b_{i_t}(o_t)\bigg) P(O,I|\bar \lambda)\space(1)

式中求和項都是對所有數(shù)據(jù)的序列總長度T進(jìn)行的。

(3)EM算法的M步：極大化Q函數(shù)Q(\lambda,\bar \lambda)求模型參數(shù)A,B,\pi

由于要極大化式(1)中但丟地出現(xiàn)在3個項中所以只需對各項分別極大化

  1. 式(1)的第一項可以寫成
    \sum_I log \,\pi_{i_1}P(O,I|\bar \lambda) = \sum_{i=1}^N log \,\pi_iP(O,i_1 = i|\bar \lambda)
    注意到\pi滿足約束條件\sum_{i=1}^N \pi_i = 1赋元，利用拉格朗日橙子法忘蟹，寫出拉格朗日函數(shù)
    \sum_{i=1}^N log \, \pi_iP(O,i_1 = i|\bar \lambda) + \gamma\bigg(\sum_{i=1}^N \pi_i -1\bigg)
    對其求偏導(dǎo)數(shù)并令結(jié)果為0
    \frac{\partial}{\partial \pi_i} \bigg[\sum_{i=1}^N log\,\pi_iP(O,i_1=i|\bar \lambda)+\gamma\bigg(\sum_{i=1}^N \pi_i -1\bigg)\bigg]=0
    有
    P(O,i_1 = i|\bar \lambda) + \gamma \pi=0
    對i求和得到\gamma
    \gamma = - P(O|\bar \lambda)
    則
    \pi_i = \frac{P(O,i_1 = i|\bar \lambda)}{P(O|\bar \lambda)}

  2. 式(1)的第二項可以寫成
    \sum_I\bigg(\sum_{t=1}^{T-1} log\,a_{i_t,i_{t+1}}\bigg)P(O,I|\bar\lambda)=\sum_{i=1}^N\sum_{j=1}^N\sum_{t=1}^{T-1}log\,a_{ij}P(O,i_t=i,i_{t+1}=j|\bar\lambda)
    應(yīng)用約束條件\sum_{j=1}^Na_{ij} = 1的拉格朗日乘子法可以求出
    a_{ij}=\frac{\sum_{t=1}^TP(O,i_t=i,i_{t+1}=j|\bar \lambda)}{\sum_{t=1}^{T-1}P(O,i_t=i|\bar \lambda)}

3.式(1)的第3項為
\sum_I \bigg(\sum_{t=1}^Tlog\,b_{i_t}(o_t)\bigg)P(O,I|\bar \lambda) = \sum_{j=1}^N\sum_{t=1}^Tlog \,b_j(o_t)P(O,i_t =j|\bar \lambda)
同樣用拉格朗日乘子法，約束條件\sum_{k=1}^M b_j(k) = 1搁凸，注意媚值，只有在o_t = v_k時b_j(o_t)對b_j(k)的偏導(dǎo)才不為0，以I(o_t=v_k)表示
b_j(k) = \frac{\sum_{t=1}^TP(O,i_t=j|\bar \lambda)I(o_t = v_k)}{\sum_{t=1}^T P(O,i_t=j|\bar \lambda)}

四护糖、預(yù)測算法

1.近似算法

近似算法的想法是褥芒，在每個時刻t選擇在該時刻最有可能出現(xiàn)的狀態(tài)i_t^*，從而得到一個狀態(tài)序列I^*=(i_1^*,i_2^*,\dots,i_T^*)嫡良，并將它作為預(yù)測的結(jié)果
給定隱馬爾科夫模型\lambda和觀測序列O锰扶，在時刻t處于狀態(tài)q_i的概率\gamma_t(i)是
\gamma_t(i) = \frac{a_t(i)\beta_t(i)}{P(O|\lambda)}=\frac{a_t(i)\beta_t(i)}{\sum_{j=1}^Na_t(j)\beta_t(j)}
在每一時刻t最有可能的狀態(tài)i_t^*是
i_t^* = \mathop{arg \,max}_{1 \le i \le N}[\gamma_t(i)],i=1,2\dots,N

從而得到狀態(tài)序列i_t^* = (i_1^*,i_2^*,\dots,i_T^*)
近似算法的一個優(yōu)點是計算簡單，其缺點是不能保證預(yù)測狀態(tài)整體上是最有可能的狀態(tài)序列寝受，因為預(yù)測的狀態(tài)序列可能有實際不發(fā)生的部分坷牛。事實上，上述辦法得到的狀態(tài)序列中可能存在轉(zhuǎn)移概率為0的相鄰狀態(tài)很澄，即對某些i,j,a_{ij}=0時京闰。盡管如此颜及，近似算法仍然是有用的

2.維特比算法

維特比算法實際上是用動態(tài)規(guī)劃(dynamic programming)解隱馬爾科夫模型預(yù)測問題，即用動態(tài)規(guī)劃求解概率最大路徑(最優(yōu)路徑）蹂楣。這時一條路徑對應(yīng)著一個狀態(tài)序列俏站。

根據(jù)動態(tài)規(guī)劃原理，最優(yōu)路徑有這樣的特性：如果最優(yōu)路徑在時刻t通過結(jié)點i_t^*捐迫，那么這一條路徑從結(jié)點i_t^*到終點i_T^*的部分路徑乾翔，對于從i_t^*到i_T^*的所有可能的部分路徑來說，必須是最優(yōu)的施戴。因為假如不是這樣反浓，那么從i_t^*到i_T^*就有另一條更好的部分路徑存在，如果把它和從i_1^*到達(dá)i_t^*的部分路徑連起來赞哗，就會形成一條比原來的路徑更優(yōu)的路徑雷则，這是矛盾的。依據(jù)這一原理肪笋，我們只需從時刻t=1開始月劈，遞推地計算時刻t狀態(tài)為i各部分路徑的最大概率，直至得到時刻t=T狀態(tài)為i各條路徑的最大概括藤乙。時刻t=T的最大概率即為最優(yōu)路徑的概率P^*猜揪，最優(yōu)路徑的終結(jié)點i_T^*也同時得到，之后坛梁，為了找出最優(yōu)路徑的各個結(jié)點而姐，從終結(jié)點i_T^*開始，由后向前逐步得到結(jié)點i_{T-1}^*划咐，得到最優(yōu)路徑I^* = (i_1^*,i_2^*,\dots,i_T^*)拴念。這就是維特比算法

維特比算法
輸入：模型\lambda=（A,B,\pi)和觀測序列O(o_1,o_2,\dots,o_T)
輸出：最優(yōu)路徑I^*=（i_1^*,i_2^*,\dots,i_T^*)
1.初始化
\delta_1(i) = \pi_ib_i(o_1),i=1,2,\dots,N
\psi_1(i) = 0,i=1,2,\dots,N
2.遞推，對t=2,3,\dots,T
\delta_t(i) = \mathop{max}_{1 \le j \le N}[\delta_{t-1}(j)a_{ji}]b_i(o_t),i=1,2,\dots,N \\ \psi_t(i) =\mathop{arg \,max}_{1 \le j \le N}[\delta{t-1}(j)a_{ji}],i=1,2,\dots,N
3.終止
p^* = \mathop{max}_{1 \le i \le N}\delta_T(i) \\ i_T^* = \mathop{arg max}_{1 \le i \le N}[\delta_T(i)]
4.最優(yōu)路徑回溯褐缠，對t=T-1,T-2,\dots,1
i_t^* =\psi_{t+1}(i_{t+1}^*)
求得最優(yōu)路徑I^*=（i_1^*,i_2^*,\dots,i_T^*)

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 人面猴
    序言：七十年代末政鼠，一起剝皮案震驚了整個濱河市，隨后出現(xiàn)的幾起案子队魏，更是在濱河造成了極大的恐慌公般，老刑警劉巖，帶你破解...
    沈念sama閱讀 216,544評論 6贊 501
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件胡桨，死亡現(xiàn)場離奇詭異俐载，居然都是意外死亡，警方通過查閱死者的電腦和手機(jī)登失，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,430評論 3贊 392
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門遏佣，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人揽浙，你說我怎么就攤上這事状婶∫饬玻” “怎么了？”我有些...
    開封第一講書人閱讀 162,764評論 0贊 353
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵膛虫，是天一觀的道長草姻。 經(jīng)常有香客問我，道長稍刀，這世上最難降的妖魔是什么撩独？ 我笑而不...
    開封第一講書人閱讀 58,193評論 1贊 292
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任，我火速辦了婚禮账月，結(jié)果婚禮上综膀，老公的妹妹穿的比我還像新娘。我一直安慰自己局齿，他們只是感情好鸠珠，可當(dāng)我...
    茶點故事閱讀 67,216評論 6贊 388
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布负拟。 她就那樣靜靜地躺著熬荆，像睡著了一般悔醋。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上谣妻，一...
    開封第一講書人閱讀 51,182評論 1贊 299
  • 城市分裂傳說
    那天萄喳，我揣著相機(jī)與錄音，去河邊找鬼蹋半。 笑死他巨，一個胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的湃窍。 我是一名探鬼主播闻蛀，決...
    沈念sama閱讀 40,063評論 3贊 418
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼匪傍，長吁一口氣：“原來是場噩夢啊……” “哼您市！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起役衡，我...
    開封第一講書人閱讀 38,917評論 0贊 274
  • 萬榮殺人案實錄
    序言：老撾萬榮一對情侶失蹤茵休，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后手蝎，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體榕莺，經(jīng)...
    沈念sama閱讀 45,329評論 1贊 310
  • ?護(hù)林員之死
    正文 獨居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,543評論 2贊 332
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年棵介，在試婚紗的時候發(fā)現(xiàn)自己被綠了钉鸯。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 39,722評論 1贊 348
  • 活死人
    序言：一個原本活蹦亂跳的男人離奇死亡邮辽，死狀恐怖唠雕，靈堂內(nèi)的尸體忽然破棺而出贸营，到底是詐尸還是另有隱情，我是刑警寧澤岩睁，帶...
    沈念sama閱讀 35,425評論 5贊 343
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布钞脂，位于F島的核電站，受9級特大地震影響捕儒，放射性物質(zhì)發(fā)生泄漏冰啃。R本人自食惡果不足惜，卻給世界環(huán)境...
    茶點故事閱讀 41,019評論 3贊 326
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一刘莹、第九天 我趴在偏房一處隱蔽的房頂上張望阎毅。 院中可真熱鬧，春花似錦栋猖、人聲如沸净薛。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,671評論 0贊 22
  • 一樁弒父案蒲拉，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽肃拜。三九已至，卻和暖如春雌团，著一層夾襖步出監(jiān)牢的瞬間燃领，已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 32,825評論 1贊 269
  • 情欲美人皮
    我被黑心中介騙來泰國打工锦援， 沒想到剛下飛機(jī)就差點兒被人妖公主榨干…… 1. 我叫王不留猛蔽，地道東北人。 一個月前我還...
    沈念sama閱讀 47,729評論 2贊 368
  • 代替公主和親
    正文 我出身青樓灵寺，卻偏偏與公主長得像曼库，于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子略板，可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 44,614評論 2贊 353

推薦閱讀更多精彩內(nèi)容