標籤：

隱馬爾可夫模型（HMM）攻略

07-26

【本文轉自】http://blog.csdn.net/likelet/article/details/7056068

【一句話總結】馬爾科夫過程，每個狀態的轉移只依賴於之前的 n 個狀態，這個過程被稱為1個 n 階的模型，其中 n 是影響轉移狀態的數目。最簡單的馬爾科夫過程就是一階過程，每一個狀態的轉移只依賴於其之前的那一個狀態（一個含有 N 個狀態的一階過程有 N2個狀態轉移）。注意這和確定性系統不一樣，因為這種轉移是有概率的，而不是確定性的。但是，是可以計算的。

隱馬爾可夫模型(Hidden Markov Model) 是一種統計模型，用來描述一個含有隱含未知參數的馬爾可夫過程。其難點是從可觀察的參數中確定該過程的隱含參數，然後利用這些參數來作進一步的分析。

隱馬爾可夫模型(Hidden Markov Model，HMM) 最初由 L. E. Baum 和其它一些學者發表在一系列的統計學論文中，隨後在語言識別，自然語言處理以及生物信息等領域體現了很大的價值。平時，經常能接觸到涉及HMM的相關文章，一直沒有仔細研究過，都是蜻蜓點水，因此，想花一點時間梳理下，加深理解，在此特別感謝 52nlp 對 HMM 的詳細介紹。

　　考慮下面交通燈的例子，一個序列可能是紅-紅/橙-綠-橙-紅。這個序列可以畫成一個狀態機，不同的狀態按照這個狀態機互相交替，每一個狀態都只依賴於前一個狀態，如果當前的是綠燈，那麼接下來就是橙燈，這是一個確定性系統，因此更容易理解和分析，只要這些狀態轉移都是已知的。但是在實際當中還存在許多不確定性系統。

　　在日常生活當中，我們總是希望根據當前天氣的情況來預測未來天氣情況，和上面的交通燈的例子不同，我們不能依靠現有知識確定天氣情況的轉移，但是我們還是希望能得到一個天氣的模式。一種辦法就是假設這個模型的每個狀態都只依賴於前一個的狀態，這個假設被稱為馬爾科夫假設，這個假設可以極大簡化這個問題。顯然，這個假設也是一個非常糟糕的假設，導致很多重要的信息都丟失了。

　　當涉及到天氣的時候，馬爾科夫假設描述為，假設如果我們知道之前一些天的天氣信息，那麼我們就能預測今天的天氣。當然，這個例子也是有些不合實際的。但是，這樣一個簡化的系統可以有利於我們的分析，所以我們通常接受這樣的假設，因為我們知道這樣的系統能讓我們獲得一些有用的信息，儘管不是十分準確的。

　　談到HMM，首先簡單介紹一下馬爾可夫過程(Markov Process)，它因俄羅斯數學家安德烈·馬爾可夫而得名，代表數學中具有馬爾可夫性質的離散隨機過程。該過程中，每個狀態的轉移只依賴於之前的 n 個狀態，這個過程被稱為1個 n 階的模型，其中 n 是影響轉移狀態的數目。最簡單的馬爾科夫過程就是一階過程，每一個狀態的轉移只依賴於其之前的那一個狀態。注意這和確定性系統不一樣，因為這種轉移是有概率的，而不是確定性的。

　　馬爾可夫鏈是隨機變數X1, … ,Xn的一個數列。這些變數的範圍，即他們所有可能取值的集合，被稱為「狀態空間」，而Xn 的值則是在時間n的狀態。如果Xn+1對於過去狀態的條件概率分布僅是Xn的一個函數，則

　　這裡x為過程中的某個狀態。上面這個恆等式可以被看作是馬爾可夫性質。

　　馬爾可夫鏈的在很多應用中發揮了重要作用，例如，谷歌所使用的網頁排序演算法（PageRank）就是由馬爾可夫鏈定義的。

　　下圖展示了天氣這個例子中所有可能的一階轉移：

　　注意一個含有 N 個狀態的一階過程有 N2個狀態轉移。每一個轉移的概率叫做狀態轉移概率(state transition probability)，就是從一個狀態轉移到另一個狀態的概率。這所有的 N2個概率可以用一個狀態轉移矩陣來表示，其表示形式如下：

　　對該矩陣有如下約束條件：

　　下面就是海藻例子的狀態轉移矩陣：

　　這個矩陣表示，如果昨天是晴天，那麼今天有50%的可能是晴天，37.5%的概率是陰天，12.5%的概率會下雨，很明顯，矩陣中每一行的和都是1。

　　為了初始化這樣一個系統，我們需要一個初始的概率向量：

　　這個向量表示第一天是晴天。

　　到這裡，我們就為上面的一階馬爾科夫過程定義了以下三個部分：

　　狀態：晴天、陰天和下雨

　　初始向量：定義系統在時間為0的時候的狀態的概率

　　狀態轉移矩陣：每種天氣轉換的概率

　　所有的能被這樣描述的系統都是一個馬爾科夫過程。

　　然而，當馬爾科夫過程不夠強大的時候，我們又該怎麼辦呢？在某些情況下，馬爾科夫過程不足以描述我們希望發現的模式。

　　例如，一個隱居的人可能不能直觀的觀察到天氣的情況，但是民間傳說告訴我們海藻的狀態在某種概率上是和天氣的情況相關的。在這種情況下我們有兩個狀態集合，一個可以觀察到的狀態集合（海藻的狀態）和一個隱藏的狀態（天氣狀況）。我們希望能找到一個演算法可以根據海藻的狀況和馬爾科夫假設來預測天氣的狀況。

　　一個更現實的例子是語音識別，我們聽到的聲音是聲帶、喉嚨和一起其他的發音器官共同作用的結果。這些因素相互作用，共同決定了每一個單詞的聲音，而一個語音識別系統檢測的聲音（可以觀察的狀態）是人體內部各種物理變化（隱藏的狀態、引申一個人真正想表達的意思）產生的。

　　某些語音識別設備把內部的發音機製作為一個隱藏的狀態序列，把最後的聲音看成是一個和隱藏的狀態序列十分相似的可以觀察到的狀態的序列。在這兩個例子中，一個非常重要的地方是隱藏狀態的數目和可以觀察到的狀態的數目可能是不一樣的。在一個有3種狀態的天氣系統（sunny、cloudy、rainy）中，也許可以觀察到4種潮濕程度的海藻（dry、dryish、damp、soggy）。在語音識別中，一個簡單的發言也許只需要80個語素來描述，但是一個內部的發音機制可以產生不到80或者超過80種不同的聲音。

　　在上面的這些情況下，可以觀察到的狀態序列和隱藏的狀態序列是概率相關的。於是我們可以將這種類型的過程建模為有一個隱藏的馬爾科夫過程和一個與這個隱藏馬爾科夫過程概率相關的並且可以觀察到的狀態集合。這就是本文重點介紹的隱馬爾可夫模型。

　　隱馬爾可夫模型(Hidden Markov Model) 是一種統計模型，用來描述一個含有隱含未知參數的馬爾可夫過程。其難點是從可觀察的參數中確定該過程的隱含參數，然後利用這些參數來作進一步的分析。下圖是一個三個狀態的隱馬爾可夫模型狀態轉移圖，其中x 表示隱含狀態，y 表示可觀察的輸出，a 表示狀態轉換概率，b 表示輸出概率。

　　下圖顯示了天氣的例子中隱藏的狀態和可以觀察到的狀態之間的關係。我們假設隱藏的狀態是一個簡單的一階馬爾科夫過程，並且他們兩兩之間都可以相互轉換。

　　對 HMM 來說，有如下三個重要假設，儘管這些假設是不現實的。

　　

　　假設1：馬爾可夫假設（狀態構成一階馬爾可夫鏈）

　　假設2：不動性假設（狀態與具體時間無關）

　　假設3：輸出獨立性假設（輸出僅與當前狀態有關）

　　隱藏的狀態和可觀察到的狀態之間有一種概率上的關係，也就是說某種隱藏狀態 H 被認為是某個可以觀察的狀態 O1 是有概率的，假設為 P(O1 | H)。如果可以觀察的狀態有3種，那麼很顯然P(O1 | H)+P(O2 | H)+ P(O3 | H) = 1。

　　這樣，我們也可以得到一個另一個矩陣，稱為混淆矩陣(confusion matrix)。這個矩陣的內容是某個隱藏的狀態被分別觀察成幾種不同的可以觀察的狀態的概率，在天氣的例子中，這個矩陣如下圖：

　　上邊的圖示都強調了HMM的狀態變遷。而下圖則明確的表示出模型的演化，其中綠色的圓圈表示隱藏狀態，紫色圓圈表示可觀察到狀態，箭頭表示狀態之間的依存概率，一個HMM可用一個5元組 { N, M, π，A，B} 表示，其中 N 表示隱藏狀態的數量，我們要麼知道確切的值，要麼猜測該值，M 表示可觀測狀態的數量，可以通過訓練集獲得，π={πi} 為初始狀態概率，A={aij} 為隱藏狀態的轉移矩陣Pr(xt(i)| xt-1(j))，B={bik} 表示某個時刻因隱藏狀態而可觀察的狀態的概率，即混淆矩陣，Pr(ot(i)| xt(j))。在狀態轉移矩陣和混淆矩陣中的每個概率都是時間無關的，即當系統演化時，這些矩陣並不隨時間改變。對於一個 N 和 M 固定的HMM來說，用 λ={ π, A,B} 表示 HMM 參數。

　　在正常的馬爾可夫模型中，狀態對於觀察者來說是直接可見的。這樣狀態的轉換概率便是全部的參數。而在隱馬爾可夫模型中，狀態並不是直接可見的，但受狀態影響的某些變數則是可見的。每一個狀態在可能輸出的符號上都有一概率分布。因此輸出符號的序列能夠透露出狀態序列的一些信息。

　　在HMM 中有三個典型問題：

　　（一） 已知模型參數，計算某一給定可觀察狀態序列的概率

　　

假設我們已經有一個特定的隱馬爾科夫模型 λ 和一個可觀察狀態序列集。我們也許想知道在所有可能的隱藏狀態序列下，給定的可觀察狀態序列的概率。當給定如下一個隱藏狀態序列：

　　那麼在 HMM 和這個隱藏狀態序列的條件下，可觀察狀態序列的概率為：

　　而隱藏狀態序列在 HMM 條件下的概率為：

　　因此，隱藏狀態序列和可觀察狀態序列的聯合概率為：

　　那麼所有可能的隱藏狀態序列上，可觀察狀態序列的概率為：

　　例如，我們也許有一個海藻的「Summer」模型和一個「Winter」模型，因為海藻在夏天和冬天的狀態應該是不同的，我們希望根據一個可觀察狀態（海藻的潮濕與否）序列來判斷現在是夏天還是冬天。

　　我們可以使用前向演算法來計算在某個特定的HMM 下一個可觀察狀態序列的概率，然後據此找到最可能的模型。

　　這種類型的應用通常出現在語音設別中，通常我們會使用很多 HMM，每一個針對一個特別的單詞。一個可觀察狀態的序列是從一個可以聽到的單詞向前得到的，然後這個單詞就可以通過找到滿足這個可觀察狀態序列的最大概率的HMM 來識別。

　　下面介紹一下前向演算法(Forward Algorithm)

　　如何計算一個可觀察序列的概率？

　　1. 窮舉搜索

　　給定一個HMM，我們想計算出某個可觀察序列的概率。考慮天氣的例子，我們知道一個描述天氣和海藻狀態的HMM，而且我們還有一個海藻狀態的序列。假設這個狀態中的某三天是（dry，damp，soggy），在這三天中的每一天，天氣都可能是晴朗，多雲或者下雨，我們可以用下圖來描述觀察序列和隱藏序列：

　　在這個圖中的每一列表示天氣的狀態可能，並且每個狀態都指向相鄰的列的每個狀態，每個狀態轉換在狀態轉移矩陣中都有一個概率。每一列的下面是當天的可觀察的海藻的狀態，在每種狀態下出現這種可觀察狀態的概率是由混淆矩陣給出的。

　　一個可能的計算可觀察概率的方法是找到每一個可能的隱藏狀態的序列，這裡有32= 27種，這個時候的可觀察序列的概率就是 Pr(dry, damp, soggy | HMM)=Pr(dry, damp, soggy | sunny, sunny, sunny) + . . . . + Pr(dry, damp, soggy | rainy, rainy, rainy)。

　　很顯然，這種計算的效率非常低，尤其是當模型中的狀態非常多或者序列很長的時候。事實上，我們可以利用概率不隨時間變化這個假設來降低時間的開銷。

　　2. 使用遞歸來降低複雜度

　　我們可以考慮給定HMM的情況下，遞歸的計算一個可觀察序列的概率。我們可以首先定義一個部分概率，表示達到某個中間狀態的概率。接下來我們將看到這些部分概率是如何 在time=1 和 time = n (n > 1) 的時候計算的。

　　假設一個T時間段的可觀察序列是：

　　1) 部分概率

　　下面這張圖表示了一個觀察序列（dry，damp，soggy）的一階轉移

　　我們可以通過計算到達某個狀態的所有路徑的概率和來計算到達某個中間狀態的概率。比如說，t=2時刻，cloudy的概率用三條路徑的概率之和來表示：

　　我們用 αt(j) 來表示在 t 時刻是狀態 j 的概率，αt(j)=Pr(觀察狀態 | 隱藏狀態 j ) x Pr(t 時刻到達狀態 j 的所有路徑)。

　　最後一個觀察狀態的部分概率就表示了整個序列最後達到某個狀態的所有可能的路徑的概率和，比如說在這個例子中，最後一列的部分狀態是通過下列路徑計算得到的：

　　因為最後一列的部分概率是所有可能的路徑的概率和，所以就是這個觀察序列在給定HMM下的概率了。

　　2) 計算 t=1時候的部分概率

　　當 t=1 的時候，沒有路徑到某個狀態，所以這裡是初始概率，Pr(狀態 j | t=0) = π(狀態 j )，這樣我們就可以計算 t=1 時候的部分概率為：

　　因為在初始的時候，狀態 j 的概率不僅和這個狀態本身相關，還和觀察狀態有關，所以這裡用到了混淆矩陣的值，k1表示第一個觀察狀態，bjk1表示隱藏狀態是 j，但是觀察成 k1的概率。

　　3) 計算 t>1 時候的部分概率

　　還是看計算部分概率的公式是：αt(j)= Pr(觀察狀態 | 隱藏狀態 j) x Pr(t 時刻到達狀態 j 的所有路徑)。 這個公式的左邊是從混淆矩陣中已知的，我只需要計算右邊部分，很顯然右邊是所有路徑的和：

　　需要計算的路徑數是和觀察序列的長度的平方相關的，但是 t 時刻的部分概率已經計算過了之前的所有路徑，所以在 t+1 時刻只需要根據 t 時刻的概率來計算就可以了：

　　這裡簡單解釋下，bjk(t+1)就是在 t+1 時刻的第 j 個隱藏狀態被認為是當前的觀察狀態的概率，後面一部分是所有t時刻的隱藏狀態到 t+1 時候的隱藏狀態j的轉移的概率的和。這樣我們每一步的計算都可以利用上一步的結果，節省了很多時間。

　　4) 公式推導

　　5) 降低計算複雜度

　　我們可以比較窮舉和遞歸演算法的複雜度。假設有一個HMM，其中有 n 個隱藏狀態，我們有一個長度為 T 的觀察序列。

　　窮舉演算法的需要計算所有可能的隱藏序列：

　　需要計算：

　　很顯然窮舉演算法的時間開銷是和 T 指數相關的，即 NT，而如果採用遞歸演算法，由於我們每一步都可以利用上一步的結果，所以是和 T 線性相關的，即複雜度是 N2T。

　　這裡我們的目的是在某個給定的HMM下，計算出某個可觀察序列的概率。我們通過先計算部分概率的方式遞歸的計算整個序列的所有路徑的概率，大大節省了時間。在 t=1 的時候，使用了初始概率和混淆矩陣的概率，而在t時刻的概率則可以利用 t-1 時刻的結果。

　　這樣我們就可以用遞歸的方式來計算所有可能的路徑的概率和，最後，所有的部分概率的計算公式為

　　使用天氣的例子，計算 t=2 時刻的 cloudy 狀態的概率方法如圖：

　　我們使用前向演算法在給定的一個HMM下計算某個可觀察序列的概率。前向演算法主要採用的是遞歸的思想，利用之前的計算結果。有了這個演算法，我們就可以在一堆HMM中，找到一個最滿足當前的可觀察序列的模型（前向演算法計算出來的概率最大）。

　　（二） 根據可觀察狀態的序列找到一個最可能的隱藏狀態序列

　　和上面一個問題相似的並且更有趣的是根據可觀察序列找到隱藏序列。在很多情況下，我們對隱藏狀態更有興趣，因為其包含了一些不能被直接觀察到的有價值的信息。比如說在海藻和天氣的例子中，一個隱居的人只能看到海藻的狀態，但是他想知道天氣的狀態。這時候我們就可以使用Viterbi 演算法來根據可觀察序列得到最優可能的隱藏狀態的序列，當然前提是已經有一個HMM。

　　另一個廣泛使用Viterbi 演算法的領域是自然語言處理中的詞性標註。句子中的單詞是可以觀察到的，詞性是隱藏的狀態。通過根據語句的上下文找到一句話中的單詞序列的最有可能的隱藏狀態序列，我們就可以得到一個單詞的詞性（可能性最大）。這樣我們就可以用這種信息來完成其他一些工作。

　　下面介紹一下維特比演算法(Viterbi Algorithm)

　　一．如何找到可能性最大的隱藏狀態序列？

　　通常我們都有一個特定的HMM，然後根據一個可觀察狀態序列去找到最可能生成這個可觀察狀態序列的隱藏狀態序列。

　　1. 窮舉搜索

　　我們可以在下圖中看到每個隱藏狀態和可觀察狀態的關係。

　　通過計算所有可能的隱藏序列的概率，我們可以找到一個可能性最大的隱藏序列，這個可能性最大的隱藏序列最大化了 Pr(觀察序列 | 隱藏狀態集)。比如說，對於上圖中的可觀察序列 (dry damp soggy)，最可能的隱藏序列就是下面這些概率中最大的：

　　Pr(dry, damp, soggy | sunny, sunny, sunny), ……，Pr(dry, damp, soggy | rainy, rainy, rainy)

　　這個方法是可行的，但是計算代價很高。和前向演算法一樣，我們可以利用轉移概率在時間上的不變性來降低計算的複雜度。

　　2. 使用遞歸降低複雜度

　　在給定了一個可觀察序列和HMM的情況下，我們可以考慮遞歸的來尋找最可能的隱藏序列。我們可以先定義一個部分概率 δ，即到達某個中間狀態的概率。接下來我們將討論如何計算 t=1 和 t=n (n>1) 的部分概率。

　　注意這裡的部分概率和前向演算法中的部分概率是不一樣的，這裡的部分概率表示的是在t時刻最可能到達某個狀態的一條路徑的概率，而不是所有概率之和。

　　1) 部分概率和部分最優路徑

　　考慮下面這個圖以及可觀察序列 (dry, damp, soggy) 的一階轉移

　　對於每一個中間狀態和終止狀態 (t=3) 都有一個最可能的路徑。比如說，在 t=3 時刻的三個狀態都有一個如下的最可能的路徑：

　　我們可以稱這些路徑為部分最優路徑。這些部分最優路徑都有一個概率，也就是部分概率δ。和前向演算法中的部分概率不一樣，這裡的概率只是一個最可能路徑的概率，而不是所有路徑的概率和。

　　我們可以用 δ(i, t) 來表示在t時刻，到狀態i的所有可能的序列（路徑）中概率最大的序列的概率，部分最優路徑就是達到這個最大概率的路徑，對於每一個時刻的每一個狀態都有這樣一個概率和部分最優路徑。

　　最後，我們通過計算 t=T 時刻的每一個狀態的最大概率和部分最優路徑，選擇其中概率最大的狀態和它的部分最優路徑來得到全局的最優路徑。

　　2) 計算 t=1 時刻的部分概率

　　當 t=1 時刻的時候，到達某個狀態最大可能的路徑還不存在，但是我們可以直接使用在 t=1 時刻某個狀態的概率和這個狀態到可觀察序列 k1的轉移概率：

　　3) 計算 t>1 時刻的部分概率

　　接下來我們可以根據 t-1 時刻的部分概率來求 t 時刻的部分概率

　　我們可以計算所有到狀態 X 的路徑的概率，找到其中最可能的路徑，也就是局部最優路徑。注意到這裡，到達X的路徑必然會經過 t-1 時刻的 A、B 和 C，所以我們可以利用之前的結果。達到X的最可能的路徑就是下面三個之一：

　　(狀態序列)，. . .，A，X (狀態序列)，. . .，B，X (狀態序列)，. . .，C，X

　　我們需要做的就是找到以 AX、BX 和 CX 結尾的路徑中概率最大的那個。

　　根據一階馬爾科夫的假設，一個狀態的發生之和之前的一個狀態有關係，所以X在某個序列的最後發生的概率只依賴於其之前的一個狀態：

Pr (到達A的最優路徑) . Pr (X | A) . Pr (觀察狀態 | X)

　　有個了這個公式，我們就可以利用t-1時刻的結果和狀態轉移矩陣和混淆矩陣的數據：

　　將上面這個表達式推廣一下，就可以得到 t 時刻可觀察狀態為 kt的第 i 個狀態的最大部分概率的計算公式：

　　其中 aji表示從狀態 j 轉移到狀態 i 的概率，bikt表示狀態i被觀察成 kt的概率。

　　4) 後向指針

　　考慮下圖

　　在每一個中間狀態和結束狀態都有一個部分最優概率δ(i, t)。但是我們的目的是找到最可能的隱藏狀態序列，所以我們需要一個方法去記住部分最優路徑的每一個節點。

　　考慮到要計算 t 時刻的部分概率，我們只需要知道 t-1 時刻的部分概率，所以我們只需要記錄那個導致了 t 時刻最大部分概率的的狀態，也就是說，在任意時刻，系統都必須處在一個能在下一時刻產生最大部分概率的狀態。如下圖所示：

　　我們可以利用一個後向指針 φ來記錄導致某個狀態最大局部概率的前一個狀態，即

　　這裡 argmax 表示能最大化後面公式的j值，同樣可以發現這個公式和 t-1 時刻的部分概率和轉移概率有關，因為後向指針只是為了找到「我從哪裡來」，這個問題和可觀察狀態沒有關係，所以這裡不需要再乘上混淆矩陣因子。全局的行為如下圖所示：

　　5) 優點

　　使用viterbi演算法對一個可觀察狀態進行解碼有兩個重要的優點：

　　a) 通過使用遞歸來減少複雜度，這點和之前的前向演算法是一樣的

　　b) 可以根據可觀察序列找到最優的隱藏序列，這個的計算公式是：

其中

　　這裡就是一個從左往右翻譯的過程，通過前面的翻譯結果得到後面的結果，起始點是初始向量 π。

　　3. 補充

　　但在序列某個地方有雜訊干擾的時候，某些方法可能會和正確答案相差的較遠。但是Viterbi演算法會查看整個序列來決定最可能的終止狀態，然後通過後向指針來找到之前的狀態，這對忽略孤立的雜訊非常有用。

　　Viterbi演算法提供了一個根據可觀察序列計算隱藏序列的很高效的方法，它利用遞歸來降低計算複雜度，並且使用之前全部的序列來做判斷，可以很好的容忍雜訊。

　　在計算的過程中，這個演算法計算每一個時刻每一個狀態的部分概率，並且使用一個後向指針來記錄達到當前狀態的最大可能的上一個狀態。最後，最可能的終止狀態就是隱藏序列的最後一個狀態，然後通過後向指針來查找整個序列的全部狀態。

　　（三） 根據觀察到的序列集來找到一個最有可能的 HMM。

　　在很多實際的情況下，HMM不能被直接的判斷，這就變成了一個學習問題，因為對於給定的可觀察狀態序列 O 來說，沒有任何一種方法可以精確地找到一組最優的HMM 參數λ 使 P(O | λ) 最大，於是人們尋求使其局部最優的解決辦法，而前向後向演算法（也稱為Baum-Welch演算法）就成了HMM學習問題的一個近似的解決方法。

　　前向後向演算法首先對於HMM 的參數進行一個初始的估計，但這個很可能是一個錯誤的猜測，然後通過對於給定的數據評估這些參數的的有效性並減少它們所引起的錯誤來更新HMM 參數，使得和給定的訓練數據的誤差變小，這其實是機器學習中的梯度下降的思想。

　　對於網格中的每一個狀態，前向後向演算法既計算到達此狀態的「前向」概率，又計算生成此模型最終狀態的「後向」概率，這些概率都可以通過前面的介紹利用遞歸進行高效計算。可以通過利用近似的 HMM 模型參數來提高這些中間概率從而進行調整，而這些調整又形成了前向後向演算法迭代的基礎。

　　另外，前向後向演算法是EM 演算法的一個特例，它避免了EM 演算法的暴力計算，而採用動態規劃思想來解決問題，Jelinek 在其書《Statistical Methods for Speech Recognition》中對前向後向演算法與EM 演算法的關係進行了詳細描述，有興趣的讀者可以參考這本書。

　　類似於上面講到的前向演算法，我們也可以定義後向變數 βt(i) 來計算給定當前隱藏狀態 i 時，部分觀察序列 ot+1，ot+2，…，oT的概率，即：

　　與前向演算法類似，我們也可以通過迭代演算法有效計算 βt(i)，計算公式如下：

　　其中

　　進一步我們可以發現

　　因此

　　下面開始介紹前向後向演算法。

　　首先我們需要定義兩個輔助變數，這兩個變數可以用前文介紹過的前向變數和後向變數進行定義。

　　第一個變數定義為 t 時狀態 i 和 t+1 時狀態 j 的概率，即

　　該變數在網格中所代表的關係如下圖所示：

　　

　　該等式等價於

　　利用前向變數和後向變數，上式可以表示為

　　第二個變數定義為後驗概率，也就是在給定觀察狀態序列和HMM的情況下，t 時狀態 i 的概率，即

　　利用前向變數和後向變數，上式可以表示為

　　因此，下式為在任意時刻狀態 i 的期望，也就是從狀態 i 轉移到觀察狀態 o 的期望

　　同樣，下式也就是從狀態 i 轉移到狀態 j 的期望

　　我們可以發現定義的這兩個變數之間的關係為

　　下面介紹前向後向演算法的參數學習過程，在學習的過程中，不斷更新HMM 的參數，從而使得 P(O | λ) 最大。我們假設初始的HMM參數為λ={ π,A, B}，首先計算前向變數 α 和後向變數 β，再根據剛剛介紹的公式計算期望 ξ 和 ζ，最後，根據下面的3個重估計公式更新 HMM 參數。

　　如果我們定義當前的HMM 模型為λ={ π，A，B}，那麼可以利用該模型計算上面三個式子的右端；我們再定義重新估計的HMM 模型為

，那麼上面三個式子的左端就是重估的HMM 模型參數。Baum 及他的同事在70年代證明了

，因此如果我們迭代地計算上面三個式子，由此不斷地重新估計HMM 的參數，那麼在多次迭代後可以得到HMM 模型的一個最大似然估計。不過需要注意的是，前向後向演算法所得的這個最大似然估計是一個局部最優解。

　　參考資料：

　　1. http://blog.csdn.net/eaglex/article/details/6376826

　　2. http://en.wikipedia.org/wiki/Markov_chain

　　3. http://en.wikipedia.org/wiki/Hidden_Markov_model

　　4. Lawrence R. Rabiner, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition.Proceedings of the IEEE, 77 (2), p. 257–286, February 1989.

　　5. L. R. Rabiner and B. H. Juang, 「An introduction to HMMs,」IEEE ASSP Mag., vol. 3, no. 1, pp. 4-16, 1986.

　　6.http://jedlik.phy.bme.hu/~gerjanos/HMM/node2.html

　　7.http://www.cs.brown.edu/research/ai/dynamics/tutorial/Documents/HiddenMarkovModels.html

　　8. 隱馬爾可夫模型簡介，劉群


推薦閱讀：

※標本中氣（四）時空模型 - 吳門國醫學院
※攝影精選：53張創意的鐵路模型攝影照片(上)
※坦克模型如何做舊？
※產品經理需要了解的溝通過程模型
※科學模型表明，生活就是不公平的

TAG:模型 | 攻略 | 馬爾可夫 |