隱馬爾科夫模型學習總結之Viterbi演算法應用

05-06

本章將描述總結隱馬爾科夫模型的最後一個問題，即已知觀測序列和模型參數集，求該觀測序列對應的最有可能出現的隱狀態序列是什麼樣的？即找到出現概率最大的隱狀態序列。這個問題常見於NLP中的分詞、詞性標註、語音識別等任務中，如中文分詞任務中，每個中文字元作為觀測變數，而該字元在詞中的角色（如詞首，詞中，詞尾，單獨成詞）作為隱變數狀態，假設當前已經通過大量文本訓練得到了HMM模型的參數集，我們的任務就是給定一段中文的文本，給這段文本的每個中文字元打上隱狀態標記，（識別詞首到詞尾，以及單獨成詞的字串）從而完成分詞任務。通常這個也叫做標註任務。

那麼如何解決這個問題呢？一種方法是在給定觀測序列的條件下，窮舉所有可能的隱狀態序列，根據參數集，計算該隱狀態序列的聯合概率（使用貝葉斯公式）。最後找出聯合概率最大的那個序列即可。這種解法很簡單，但是需要 $O(k^T)$ 計算複雜度，其中k表示隱狀態個數，T表示序列長度（或者說是時刻長度）。

因此基於上述問題，需要使用一種動態規劃演算法來解決該問題，這個問題相當於可以轉化為對一個有向無環帶權重圖，找到起點至終點路徑最短的（即概率最大）的結點集合。這裡使用了一個非常著名的動態規劃演算法，Viterbi演算法，該演算法在通信行業領域使用比較廣泛，它特別適合上述這種尋找最短路徑的問題。

我是在看了吳軍的數學之美以及一篇博客後，對該演算法有了一定的了解。博客鏈接如下：

HMM模型和Viterbi演算法 - Denise_hzf - 博客園?

www.cnblogs.com

Viterbi演算法的基礎概括成下面三點：

1、如果概率最大的路徑P（或者說是最短路徑）經過某點a，那麼這條路徑上從起始點s到a的這一段子路徑一定是s到a之間的最短路徑。否則用s到a的最短路徑來替換上述路徑，便構成了一條比P更短的路徑，矛盾。

2、從S到E的路徑必定經過第i時刻的某個狀態，假定第i時刻有k個狀態，那麼如果記錄了從S到第i個狀態的所有k個節點的最短路徑，最終的最短路徑必經過其中的一條。這樣，在任何時刻，只需要考慮非常有限條最短路徑即可。

3、結合上述兩點，假定當我們從狀態i進入狀態i+1時，從S到狀態i上各個節點的最短路徑已經找到，並且記錄在這些節點上，那麼在計算從起點S到前一個狀態i所有的k個結點的最短路徑，以及從這k個節點到Xi+1，j的距離即可。

基於上述基礎，有如下演算法：

step1：從點S出發，對於第一個狀態 $X_{1}$ 的各個節點，不妨假定有 $n_{1}$ 個，計算出S到它們的距離 $d(S,X_{1i})$ ，其中 $X_{1i}$ 代表任意狀態1的節點。因為只有一步，所以這些距離都是S到它們各自的最短距離。

step2：對於第二個狀態 $X_{2}$ 的所有節點，要計算出從S到它們的最短距離。對於特點的節點 $X_{2i}$ ，從S到它的路徑可以經過狀態1的 $n_{1}$ 中任何一個節點 $X_{1i}$ ，對應的路徑長度就是 $d(S,X_{2i})=d(S,X_{1j})+d(X_{1j},X_{2i})$ 。由於j有 $n_{1}$ 種可能性，我們要一一計算，找出最小值。即：

$d(S,X_{2i})=min_{j=1,n_{1}}d(S,X_{1j})+d(X_{1j},X_{2i})$

這樣對於第二個狀態的每個節點，需要 $n_{1}$ 次乘法計算。假定這個狀態有 $n_{2}$ 個節

點，把S這些節點的距離都算一遍，就有 $O(n_{1}*n_{2})$ 次計算。

step3：接下來，類似地按照上述方法從第二個狀態走到第三個狀態，一直走到最後一個狀態，就得到了整個網格從頭到尾的最短路徑。每一步計算的複雜度都和相鄰兩個狀態Si和Si+1各自的節點數目 $n_{i}$ ， $n_{i+1}$ 的乘積成正比，即 $O(n_{i}*n_{i+1})$

step4：要獲取最終路徑節點，只要在回溯上述計算過程，就能得到對應的路徑節點。

補充：原博客中並未提及回溯的過程，且他確定每個時刻的狀態時，貌似採用的是每個時刻取最大的貪心演算法，而看了知乎上一個回答，發現確定隱狀態結點序列，是需要根據當前已確定的最新結點往前回溯，即假設t=3的天氣是Rainy，則需要在

$P_{2}(Sunny)*A_{Sunny,Rainy},P_{2}(Cloudy)*A_{Cloudy,Rainy},P_{2}(Rainy)*A_{Rainy,Rainy}$ 中選取最大的作為t=2時刻的天氣，而不應該是直接在 $P_{2}(Sunny),P_{2}(Cloudy),P_{2}(Rainy)$ 中選最大的。個人感覺該博客在這地方有問題，最後我代碼計算得到的序列是{Sunny,Cloudy,Rainy}，與原博客也不同。

上述是從吳軍老師的書中摘取的，個人感覺已經非常明確簡潔了，如果想知道實例怎麼計算的，可以去上面我貼出的鏈接裡面看，非常清楚。

貼一下我用python實現的上述例子吧：使用了numpy，向量化一些計算，省去了一些循環。

# coding=utf-8import numpy as npobserved_status = {0:"Dry",1:"Dryish",2:"Damp",3:"Soggy"}hidden_status = {0:"Sunny",1:"Cloudy",2:"Rainy"}sequence_observe = [0,2,3]#初始狀態概率pi_0 = np.array([0.63,0.17,0.20])A_matrix = np.array([[0.5,0.375,0.125],[0.25,0.125,0.625],[0.25,0.375,0.375]])B_matrix = np.array([[0.6,0.2,0.15,0.05],[0.25,0.25,0.25,0.25],[0.05,0.10,0.35,0.5]])def viterbi(A_matrix,B_matrix,pi_0,sequence_observe): #序列長度 sequence_length = len(sequence_observe) state_length = len(hidden_status) #初始化一個矩陣存放每輪計算得到的prob curren_prob = np.zeros((sequence_length,state_length)) #存放結果隱狀態序列index final_result_list = [] #用於回溯的存放前一個結點最大計算概率 prob_max = [] #起點到第一天 curren_prob[0,:] = np.multiply(pi_0,B_matrix[:,sequence_observe[0]]) #t=1 to T: for t in range(1,sequence_length): tmp_dict = {} for state_j in hidden_status.keys(): #計算前時刻狀態到本時刻狀態最大概率 curr_state_prob_max = np.max(np.multiply(curren_prob[t-1,:],A_matrix[:,state_j])) curr_state_max = np.argmax(np.multiply(curren_prob[t-1,:],A_matrix[:,state_j])) tmp_dict[state_j] = curr_state_max #計算本時刻轉移到state_j狀態的聯合概率 curren_prob[t,state_j] = curr_state_prob_max*B_matrix[state_j,sequence_observe[t]] prob_max.append(tmp_dict) #backtrace final_pick_status = np.argmax(curren_prob[-1,:]) final_result_list.append(final_pick_status) curr_status = final_pick_status for t in range(sequence_length-1,0,-1): #根據已處理的最新結點，找到上一時刻概率最大的結點 previous = prob_max[t-1][curr_status] final_result_list.insert(0,previous) curr_status = previous final_result_str_list = [hidden_status[weather_index] for weather_index in final_result_list] return final_result_str_listprint(viterbi(A_matrix,B_matrix,pi_0,sequence_observe))

終於把HMM的相關內容整理總結了一下，其實HMM的知識遠不止我總結的這幾篇文章，包括引入最大熵的MEMM模型、引入二階馬爾科夫性質的HMM等等，但個人不會短時間再深入了，因為作為一名做工程的，需要平衡工程和數學統計的研究時間，既不能完全忽略數學統計的作用，也不能跟專業學術界的大牛一樣鑽研其中，容易出不來，而且目前暫時的實際應用中，HMM演算法的效果已經可以接受了，而且從HMM演算法中，可以學到很多解決問題的思想和方法，包括最大似然估計，貝葉斯公式，拉格朗日乘子法，動態規劃演算法以及各種消元思想。後續有時間的話還可能對條件隨機場進行總結，畢竟這兩種模型代表了不同的建模方式（聯合概率和條件概率），且條件隨機場的效果在NLP裡面通常都比HMM要好。

預告：下一個系列會對SVM支持向量機演算法進行一個詳細的總結，該演算法本身的思想很簡單，但是使用了大量的數學、凸優化知識來幫助構建該模型，值得好好剖析。

reference：

吳軍《數學之美》

wiki百科：Viterbi algorithm

HMM模型和Viterbi演算法 - Denise_hzf - 博客園