隐馬爾科夫模型HMM的前向算法和後向算法

最近重新看了一遍《統計學習方法》中第十章《隐馬爾可夫模型》，更加覺得這本書有淺有深，簡潔深刻。HMM模型有三個基本問題：機率計算問題，學習問題和預測問題。今天我就來将其中的機率計算問題的一些細節思考總結一下，就當是筆記吧！主要就是機率計算的前向算法和後向算法。

HMM簡介

隐馬爾可夫模型的參數一般稱為其三要素，包括初始狀态機率，轉移機率和觀測機率。其模型的定義建立在兩個基本假設的前提上。分别是齊次馬爾科夫假設和觀測獨立性假設。這兩個假設是HMM的重點，必須要說一下。

齊次馬爾科夫假設：通俗地說就是HMM的任一時刻t某一狀态隻依賴于其前一時刻的狀态，與其它時刻的狀态及觀測無關，也與時刻t無關。

觀測獨立性假設：通俗地說就是任一時刻的觀測隻依賴于該時刻的馬爾科夫鍊的狀态，與其他觀測及狀态無關。

這兩個假設是HMM的核心，之後的公式推導都是依賴這兩個假設成立的基礎上進行的。

機率計算問題

HMM的機率計算問題是HMM三大問題之一。所謂機率計算就是給定一個模型參數已知的HMM和一組觀測序列，求這組觀測序列由這個HMM所生成的機率。機率計算問題其實評價了模型的好壞，試想如果有兩個HMM和一組觀測序列，第一個HMM給出的 P(O|θ1) 是0.8，第二個HMM給出的 P(O|θ2) 是0.9。如果給定多組測試觀測資料都是這樣，那麼顯然第二個HMM模型更準确一些，性能也更好。HMM的機率計算算法主要有前向算法和後向算法。直接計算法雖然理論上可行但計算複雜度過高實際中不可行，我們直接省略掉，下面先介紹前向算法，然後介紹後向算法。

前向算法

前向算法定義了一個概念，叫前向機率：給定隐馬爾科夫模型 λ ，定義到時刻t部分觀測序列為 o1,o2,...ot 且狀态為 qi 的機率為前向機率，記作：

αt(i)=P(o1,o2,...ot,it=qi|λ)

有了前向機率，我們就可以遞推地求得前向機率 αt(i) 及觀測序列機率 P(O|λ) 。具體遞推過程為：

αt+1(i)=⎡⎣∑j=1Nαt(j)aji⎤⎦bi(ot+1)

其中， aji 是轉移機率，具體為：

aji=P(it+1=qi|it=qj)

而根據前向機率的定義：

αt(j)=P(o1,o2,...ot,it=qj|λ)

根據上面提到的 齊次馬爾科夫假設，有：

aji=P(it+1=qi|it=qj)=P(it+1=qi|o1,o2,...ot,it=qj)

是以可以将 αt(j)aji 合并為：

P(o1,o2,...ot,it=qj,it+1=qi|λ)

在經過求和符号處理之後，有：

∑j=1Nαt(j)aji=P(o1,o2,...ot,it+1=qi|λ)

然後遞推式中的 bi(ot+1) 是觀測機率，具體為：

bi(ot+1)=P(ot+1|it+1=qi)=P(ot+1|o1,o2,...ot,it+1=qi)

後面的連等成立是因為應用了前面提到的 觀測獨立性假設。這樣，最終 αt+1(i) 就可以用機率表示為：

αt+1(i)=P(o1,o2,...ot,ot+1,it+1=qi|λ)

這與我們之前對前向機率的定義是一緻的。最後，為了得到 P(O|λ) ，我們隻要把馬爾科夫狀态序列的最後一個狀态的所有前向機率進行求和便可以了，具體為：

P(O|λ)=∑i=1NαT(i)=P(o1,o2,...ot,ot+1,...,oT|λ)

後向算法

後向算法與前向算法類似，它定義了一個概念叫後向機率：給定隐馬爾科夫模型 λ ，定義在時刻t狀态為 qi 的條件下，從t+1到T的部分觀測序列為 ot+1,ot+2,...,oT 的機率為後向機率，記作

βt(i)=P(ot+1,ot+2,...,oT|it=qi,λ)

同樣也可以用遞推的方法求得後向機率 βt(i) 及觀測機率 P(O|λ) ，由于和前向算法類似，也用到了HMM的齊次馬爾科夫假設和觀測獨立假設，這裡就不詳細推導了。

前向機率和後向機率的應用

有了前向機率和後向機率的基礎，我們就可以利用它們來表示一些HMM機率計算的小問題。比如可以将觀測序列機率 P(O|λ) 統一寫成：

P(O|λ)=∑i=1N∑j=1Nαt(i)aijbj(ot+1)βt+1(j)

兩個求和符号中的 αt(i)aijbj(ot+1)βt+1(j) 其實經過機率表示等價于：

αt(i)aijbj(ot+1)βt+1(j)=P(o1,o2,...,oT,it=qi,it+1=qj|λ)

兩次求和其實就是将狀态 qi 和狀态 qj 的所有可能取值都取一遍，N是所有可能的狀态數。

下面給出一些機率和期望值的計算。

在時刻t處于狀态 qi 的機率

γt(i)=P(it=qi|O,λ)=P(it=qi,O|λ)P(O|λ)=αt(i)βt(i)∑Nj=1αt(j)βt(j)

在時刻t處于狀态 qi 且在時刻t+1處于狀态 qj 的機率

ξt(i,j)=P(it=qi,it+1=qj|O,λ)=P(it=qi,it+1=qj,O|λ)P(O|λ)=αt(i)aijbj(ot+1)βt+1(j)∑Ni=1∑Nj=1αt(i)aijbj(ot+1)βt+1(j)

利用 γt(i) 和 ξt(i,j) 對各個時刻求和得到有用的期望值

（1）在觀測O下狀态i出現的期望值為

∑t=1Tγt(i)

解釋：出現一次的機率是 γt(i) ，那麼長度為T的觀測下出現的機率就是對T求和。

（2）在觀測O下由狀态i轉移的期望值為

∑t=1T−1γt(i)

解釋：即除去目前被轉移到的狀态剩下T-1個長度。

（3）在觀測O下由狀态i轉移到狀态j的期望值為

∑t=1T−1ξt(i,j)

解釋：隻能有T-1個由狀态i轉移到狀态j的機會。

總結

通過這些機率和期望值的計算，可以為後面HMM的其它兩個問題即學習問題和預測問題提供友善。