viterbi算法_HMM（一）：Graphical Model，HMM，Viterbi

HMM是一類時序模型，在說HMM之前先簡單介紹一下Graphical Model 以便于更好了解HMM。

一、Graphical Models

從上圖可以看到HMM其可以了解為一個Bayesian Network的一個特例。

1. 有向圖的機率表示

對于有向圖而言，使用條件機率表示起來比較容易，寫成公式如下：

這樣每個節點都可以用條件機率的形式表示出來， 整個圖就是所有節點的 Joint Probablity。

2. 無相圖的機率表示

無向圖的機率表示就不那麼直覺了，主要原因是你并不知道節點之間誰和誰到底是什麼關系，你隻知道他們之間是有關系的。是以就需要一組函數作用在圖中的 Clique上表示他們的關系， 這組函數也被成為

Compatibility Function

或者

Potential Function。 假設表示下圖：

每個紅圈表示一個

Clique，

整個機率圖表示形式如下：

Z

: 表示為normalization term, 由于每一個

得到的隻是一個

Clique

關系緊密程度的打分，并不是真正意義上的機率值，需要一個全局的歸一化，把這一切變成機率值，滿足下面兩個條件。

: 表示一個

Compatibility Function

用來衡量一個

Clique

中節點之間的關系， 需要自行定義。

由此可見， 機率圖事實上表示的是一個關系， 無論有向圖還是無向圖都是用各種手段來表示這個關系。

二、HMM 相關的四個問題

之前在學習EM算法時候提到了投硬币實驗，當時為了簡化問題， 把A，B兩枚硬币投擲的次序當是互相獨立的事件。 在HMM中，重新看一下這個例子。 假設我們有A，B兩個硬币，他們正反面的機率分别為

。 這個過程如下圖表示， H，T 表示正反面：

在這個過程中，存在着幾組需要關注的值和參數：

變量

：

（1）Z: 隐變量（狀态)， 這裡表示到底是A硬币還是B硬币。

（2）X: 可觀測資料， 這裡代表硬币正反面。

模型參數

（3）

：2x2 狀态轉移矩陣， 兩個狀态A，B之間兩兩轉移機率分布。

（4）

： 表示兩個狀态A，B生成T，H的機率矩陣。

對于模型中變量和參數， 在使用HMM的過程中可能遇到下面三個問題：

1. 模型參數

   

   已知， X可觀測時， 求Z，就是個 Inference 問題， 使用Viterbi算法。
2. 模型參數

   

   已知，Z已知， 求

   

   ， 需要使用DP算法得到

   

3. 模型參數

   

   未知，X，Z 已知時， 可以通過 MLE 進行模型參數估計。
4. 模型參數

   

   未知，X已知， Z未知時， 由于隐變量Z未知，需要使用 EM-style 進行參數估計。

HMM 本質上是一個生成模型，用硬币的例子來說， 如果A， B 抛出順序可知， 參數可知， 那麼生成觀察值的分布就可知了。 用模型的參數可以采樣出符合這個分布的各種觀察值序列。

三、 Viterbi算法，使用訓練好的HMM參數，預測最好的隐變量Z

HMM在應用過程中其中一個比較重要的問題就是在觀測值已知的情況下使用訓練好的模型參數來預測隐變量Z，比較經典的應用是NLP領域中詞性标注。 給定句子的每個詞通過HMM來預測每個詞的詞性标簽。 而這個過程用到的算法就是Viterbi算法。 再說Viterbi算法之前，先重新定義一下HMM參數的結構。

1. 模型和參數

變量定義：

： 隐藏狀态， 假設有

個狀态，

: 可觀測到的序列資料， 共有

中可能性，序列長度為

參數定義：

：狀态機率轉移矩矩陣，次元

：發射機率轉移矩陣，次元

: 初始狀态機率矩陣, 次元

2. Viterbi 算法的原理和應用場景。

假如我們的應用是一個詞性标注任務，使用上面定義好的模型HMM模型 ， 參數

已經訓練好，

是詞性，

是詞表大小，

是詞性的個數。給定一個長度為

新的詞序列

，如何找到最優的詞性序列

呢？ 如果使用暴力窮舉的方法，我們可以通過參數找到所有的可能的狀态

到給定

的機率，并找到最大的那個

的組合。 由于我們有

中可能的狀态，長度有

個詞，需要周遊的搜尋空間就是

這麼多。

除此之外我們有更好的方法解決這個問題，那就是Viterbi算法。 Viterbi算法本質上就是一種動态規劃方法， 我們在搜尋空間中尋找最優解的過程等同于尋找一條符合要求的最優路徑。 如下圖所示：

是每一種可能的狀态生成這目前時間步驟的可能性,

是序列長度， 目标是找一條序列穿越

個時間步驟，并且機率得分最大， 機率得分為機率值取

，防止underflow的問題， 動态規劃算法最重要的是定義子問題， 那麼這裡的子問題就是每個格子的得分和計算方法。

上圖定義了任意一個格子的得分函數，第

得分定義為：

， 它有

種方式獲得， 即為前一個狀态有

種可能性。 即為：

其中

可以從

轉移矩陣中找到，

可以再發射矩陣

中找到。第一列由于是起始狀态，直接可以用發射機率填補。

按照上面的結構把表格裡的每個元素填完整并且，存儲從哪一個狀态轉移過來的資訊，類似下面的形式。

這樣就可以追溯到任意一個末端的路徑， 這就可以序列結束的時候整體找到最優路徑。 這個算法的算法複雜度為

，要比暴力搜尋要快很多。

OK第一篇HMM就整理這麼多， 後續在陸續整理，參數估計，CRF等内容。