通俗講解維特比演算法

本文假定讀者有一定的隱馬模型基礎！或者大家可以參考這兩篇文章。隱馬爾科夫模型（HMM）一前向與後向演算法和隱馬爾科夫模型（HMM）一基本模型與三個基本問題

維特比演算法說白了就是動態規劃實現最短路徑，只要知道「動態規劃可以降低複雜度」這一點就能輕鬆理解維特比演算法

維特比演算法之所以重要，是因為凡是使用隱含馬爾可夫模型描述的問題都可以用它來解碼，包括今天的數字通信、語音識別、機器翻譯、拼音轉漢字、分詞等。——《數學之美》

下面我通過一個例子來解釋講解一下維特比演算法！

詞性標註問題

首先介紹一下什麼是詞性標註問題，比如我們有一句已經分詞好的句子。

dog chase mouse

那麼我們就可以進行詞性標註為：

其中nn為名詞，vv為動詞。通過上面例子，我們就很容易看出詞性標註的任務。

那麼我們來了一句話之後，比如我們的詞性字典中有nn,vv,prp(代詞)，我們怎麼能夠找到dog

chase mouse 所對應的詞性標註呢，如果每一個單詞有nn，vv，prp三種可能，那麼將會有3*3*3=27種可能，我們如何去挑選呢？

如下圖：

我們總共有27條路徑，那麼如何得到我們Dog chase mouse的最優路徑呢？

我們至少可以遍歷每一條路徑，求出各自的概率值，然後挑選最大的即可，比如我們求第一條路徑的時候，可以這麼表示：

所求的路徑對應如下圖紅色線條所示：

求第27條路徑的時候，我們可以這麼表示：

所求的路徑對應如下圖紅色線條所示：

那麼我們從上面可以知道，要求一個句子的最優詞性標註，我們至少可以遍歷所有的路徑，然後挑選概率值最大的那條路徑即可！！！

但是問題來了！

給定模型，求給定長度為T的觀測序列(這裡指的就是Dog Chase Mouse)的概率，直接計演算法的思路是枚舉所有的長度T（例子中是三個，Dog，Chase，Mouse總共三個單詞）的狀態序列，計算該狀態序列與觀測序列的聯合概率（隱狀態發射到觀測），對所有的枚舉項求和即可。

在狀態種類為N(例子中就是三個，NN，VV,PRP)的情況下，一共有 種排列組合，每種組合計算聯合概率的計算量為T，總的複雜度為 ，這並不可取。

於是維特比演算法隆重登場了！！

維特比演算法

好了，到現在為止，我們假定我們已經訓練好了一個隱馬爾可夫模型了（訓練好的意思，也就是單詞到詞性的發射概率，詞性與詞性的轉移概率都已經在訓練數據中學習得到了），來了一句話，Dog Chase Mouse，我如何得到它的詞性標註序列？

首先先上一個維特比演算法流程圖：

是不是非常暈，好吧，我下面爭取按自己的話幫助大家理解一遍，再附上相應邏輯的代碼！

解釋如下：

# We implement the viterbi decoding algorithm.ndef viterbi(words, hmm):n n Viterbi algorihtm.nn Parametersn ----------n words: list(str)n The list of wordsn hmm: HMMn The hmm modelnn Returnn ------n result: list(str)n The POS-tag for each word.n n # unpack the length of words, and number of postagsn N, T = len(words), len(hmm.postags)nn # allocate the decode matrixn score = [[-float(inf) for j in range(T)] for i in range(N)]n path = [[-1 for j in range(T)] for i in range(N)]nn for i, word in enumerate(words):n if i == 0:n for j, tag in enumerate(hmm.postags):n score[i][j] = hmm.emit(words, i, tag)n else:n for j, tag in enumerate(hmm.postags):n best, best_t = -1e20, -1n temp = 0n # Your code here, enumerate all the previous tagn for j2,tag2 in enumerate(hmm.postags):n if best < hmm.trans(tag2,tag)*score[i-1][j2]:n best = hmm.trans(tag2,tag)*score[i-1][j2]n best_t = j2n best*=hmm.emit(words,i,tag)n score[i][j] = bestn path[i][j] = best_tnn #n best, best_t = -1e20, -1n for j, tag in enumerate(hmm.postags):n if best < score[len(words)- 1][j]:n best = score[len(words)- 1][j]n best_t = jnn result = [best_t]n best, best_t = -1e20, -1n best_t = result[0]n for i in range(len(words)-1, 0, -1):n # Your code here, back trace to recover the full viterbi decode pathn result.append(path[i][best_t])n best_t = result[-1] #result[-1]代表的是挑選最後一個nn # convert POStag indexing to POStag strn result = [hmm.postags[t] for t in reversed(result)]n return resultn

致謝：

郭江師兄