六、維特比算法（Viterbi Algorithm）
尋找最可能的隐藏狀态序列(Finding most probable sequence of hidden states)
2d.反向指針，
’s
考慮下面這個網格
在每一個中間及終止狀态我們都知道了局部機率，
(i,t)。然而我們的目标是在給定一個觀察序列的情況下尋找網格中最可能的隐藏狀态序列——是以，我們需要一些方法來記住網格中的局部最佳路徑。
回顧一下我們是如何計算局部機率的，計算t時刻的
’s我們僅僅需要知道t-1時刻的
’s。在這個局部機率計算之後，就有可能記錄前一時刻哪個狀态生成了
(i,t)——也就是說，在t-1時刻系統必須處于某個狀态，該狀态導緻了系統在t時刻到達狀态i是最優的。這種記錄（記憶）是通過對每一個狀态賦予一個反向指針
完成的，這個指針指向最優的引發目前狀态的前一時刻的某個狀态。
形式上，我們可以寫成如下的公式
其中argmax運算符是用來計算使括号中表達式的值最大的索引j的。
請注意這個表達式是通過前一個時間步驟的局部機率
’s和轉移機率計算的，并不包括觀察機率（與計算局部機率
’s本身不同）。這是因為我們希望這些
’s能回答這個問題“如果我在這裡，最可能通過哪條路徑到達下一個狀态？”——這個問題與隐藏狀态有關，是以與觀察機率有關的混淆（矩陣）因子是可以被忽略的。
2e.維特比算法的優點
使用Viterbi算法對觀察序列進行解碼有兩個重要的優點：
1. 通過使用遞歸減少計算複雜度——這一點和前向算法使用遞歸減少計算複雜度是完全類似的。
2.維特比算法有一個非常有用的性質，就是對于觀察序列的整個上下文進行了最好的解釋（考慮）。事實上，尋找最可能的隐藏狀态序列不止這一種方法，其他替代方法也可以，譬如，可以這樣确定如下的隐藏狀态序列：
其中
這裡，采用了“自左向右”的決策方式進行一種近似的判斷，其對于每個隐藏狀态的判斷是建立在前一個步驟的判斷的基礎之上（而第一步從隐藏狀态的初始向量
開始）。
這種做法，如果在整個觀察序列的中部發生“噪音幹擾”時，其最終的結果将與正确的答案嚴重偏離。
相反， 維特比算法在确定最可能的終止狀态前将考慮整個觀察序列，然後通過
指針“回溯”以确定某個隐藏狀态是否是最可能的隐藏狀态序列中的一員。這是非常有用的，因為這樣就可以孤立序列中的“噪音”，而這些“噪音”在實時資料中是很常見的。
3.小結
維特比算法提供了一種有效的計算方法來分析隐馬爾科夫模型的觀察序列，并捕獲最可能的隐藏狀态序列。它利用遞歸減少計算量，并使用整個序列的上下文來做判斷，進而對包含“噪音”的序列也能進行良好的分析。
在使用時，維特比算法對于網格中的每一個單元(cell)都計算一個局部機率，同時包括一個反向指針用來訓示最可能的到達該單元的路徑。當完成整個計算過程後，首先在終止時刻找到最可能的狀态，然後通過反向指針回溯到t=1時刻，這樣回溯路徑上的狀态序列就是最可能的隐藏狀态序列了。
本系列文章全部轉載自：http://www.52nlp.cn/hmm-learn-best-practices-six-viterbi-algorithm-3