隱馬爾可夫模型的預測問題----維特比演算法

01-27

在介紹隱馬爾可夫模型的兩篇文章中，我們介紹了隱馬爾可夫模型有三個問題，並且在文章中也說過可以用維特比演算法來解決通信模型中的解碼問題，也就是隱馬爾可夫模型的預測問題。本文就詳細介紹一下維特比演算法。

維特比演算法利用動態規劃解決隱馬爾科夫模型的預測問題，即用動態規劃求概率最大路徑（隱馬爾可夫模型是概率圖模型），這時一條路徑對應著一個狀態序列。根據DP原理，最優路徑是這樣的：如果最優路徑在時刻t通過節點 $i_t^*$ ,那麼這一路徑從節點 $i_t^*$ 到終點 $i_T^*$ 的部分路徑，對於從 $i_t^*$ 到 $i_T^*$ 的所有可能的部分路徑來說，必須是最優的。依據這一原理，我們只需從時刻t=1開始，遞推的計算在時刻t狀態為i的各條部分路徑的最大概率，直至得到時刻t=T狀態為i的各條路徑的最大概率。時刻t=T的最大概率即為最優路徑的概率 $P^*$ ，最優路徑的終結點 $i_T^*$ 也同時得到。之後，為了找出最優路徑的各個節點，從終結點 $i_T^*$ 開始，由後向前逐步求得結點 $i_T^*,...,i_1^*$ ，得到最優路徑 $I^*=(i_1^*,i_2^*,...,i_T^*)$ ，這就是維特比演算法。

維特比演算法是針對籬笆網路的有向圖（Lattice）的最短路徑而提出的，凡是使用隱馬爾可夫模型描述的問題都可以用它來解碼。包括數字通信、語音識別、機器翻譯、拼音轉漢字、分詞等。以拼音轉漢字為例，我們假設用戶輸入的拼音序列是 $y_1,y_2,...,y_N$ ，對應的漢字序列是 $x_1,x_2,...,x_N$ ，我們的目的是要通過輸入的拼音來輸出最有可能和拼音對應的漢字，比如輸入zhong，可以使中也可以是種等等，一個輸入對應很多狀態，也就是求解以下概率的最大值：

$x_1,x_2,..,x_N=ArgMax_{xin X}P(x_1,x_2,...,x_N|y_1,y_2,...,y_N) = ArgMax_{xin X}prod_{i=1}^{N}P(y_i|x_i)P(x_i|x_{i-1})$

從拼音到漢字的解碼過程可以用下圖來描述：

$P(x_i|x_{i-1})$ 是狀態之間的轉移概率， $P(y_i|x_{i})$ 是每個狀態的產生概率。可以看到狀態的輸出是固定的，但是每個狀態的值可以變化。用符號 $x_{i,j}$ 表示狀態 $x_i$ 的第j個可能的值，把每個狀態按照不同的值展開，就得到下面這個籬笆網路：

在上圖中，每個狀態有3到4個值，從第一個狀態到最後的任何一條路徑都可能產生我們觀察到的輸出序列Y。我們要做的就是找到最可能的那條路徑。對於每一條路徑，可以使用上文的公式進行計算，但是因為隨著狀態值的可能性增多，路徑組合呈指數級爆炸增長，很顯然用窮舉法是無法做的，因此我們使用維特比演算法來解決。

依據上文我們描述的維特比演算法步驟，對於拼音轉漢字這個例子，可以進行如下步驟計算：

從S點出發，對於第一個狀態x1的各個節點，不妨假定有n1個，計算出S到它們的距離 $d(S,x_{1i})$ ，其中 $x_{1i}$ 代表任意狀態1的節點。因為只有一步，所以這些距離都是S到它們各自的最短距離。
對於第二個狀態x2的所有節點，要計算出從S到它們的最短距離。我們知道，對於特定的節點 $x_{2i}$ ,從S到它的路徑可以經過狀態1到n1中的任何一個節點 $x_{1i}$ ，當然，對應的路徑長度就是 $d(S,x_{2i}) = d(S,x_{1i})+d(x_{1i},x_{2i})$ ，由於j有n1種可能，我們需要一一計算，然後找到最小值。即： $d(S,x_{2i}) = min_{i=1,n_1}d(S,x_{1i})+d(x_{1i},x_{2i})$ 。這樣對於第二個狀態的每個節點，需要n1詞乘法計算。假定這個狀態有n2個節點，把S這些節點的距離都算一遍，就有O(n1*n2)詞計算。
接下來，類似地按照上一條方法從第二個狀態走到第三個狀態，一直走到最後一個狀態，就得到了整個網格從頭到尾的最短路徑。每一步計算的複雜度都和相鄰的兩個狀態 $S_i$ 和 $S_{i+1}$ 各自節點數目 $n_i,n_{i+1}$ 的乘積成正比，即 $O（n_i,n_{i+1}）$ 。假定在這個隱馬爾科夫鏈中節點最多的狀態有D個節點，也就是說整個網格的寬度為D，那麼任何一步的複雜度不超過 $O(D^2)$ ，由於網格長度是N，所以整個維特比演算法的複雜度是 $O(Ncdot D^2)$ 。