維特比算法解碼隱藏狀態(tài)序列致盟，即給定模型和觀測序列薪前，求給定觀測序列條件下贝乎，最可能出現(xiàn)的對應的隱藏狀態(tài)序列。
HMM模型的解碼問題最常用的算法是維特比算法貌矿，同時維特比算法是一個通用的求序列最短路徑的動態(tài)規(guī)劃算法炭菌。
1 HMM最可能隱藏狀態(tài)序列求解概述
HMM模型的解碼問題即：
給定模型 λ=(A,B,Π) 和觀測序列?o = o1,o2,o3.....，求給定觀測序列O條件下逛漫，最可能出現(xiàn)的對應的狀態(tài)序列I= I1.I2.....
即p（I|o）的最大化黑低。
2 維特比算法概述
維特比算法是一個通用的解碼算法，是基于動態(tài)規(guī)劃的求序列最短路徑的方法酌毡。
既然是動態(tài)規(guī)劃算法克握，那么就需要找到合適的局部狀態(tài)，以及局部狀態(tài)的遞推公式枷踏。在HMM中菩暗，維特比算法定義了兩個局部狀態(tài)用于遞推。
1) 第一個局部狀態(tài)是在時刻t隱藏狀態(tài)為 i 所有可能的狀態(tài)轉移路徑I= I1.I2.....中的概率最大值旭蠕。
2) 第二個局部狀態(tài)由第一個局部狀態(tài)遞推得到停团。
有了這兩個局部狀態(tài)，我們就可以從時刻0一直遞推到時刻T掏熬，然后利用 i 記錄的前一個最可能的狀態(tài)節(jié)點回溯佑稠，直到找到最優(yōu)的隱藏狀態(tài)序列。
3 維特比算法流程總結
現(xiàn)在我們來總結下維特比算法的流程：
輸入：HMM模型 λ=(A,B,Π)旗芬，觀測序列o = o1,o2,o3.....
輸出：最有可能的隱藏狀態(tài)序列I= I1.I2.....
流程如下：
1）初始化局部狀態(tài)：
2) 進行動態(tài)規(guī)劃遞推時刻 t=2,3,...T 時刻的局部狀態(tài)：
3) 計算時刻T最大的Ti,即為最可能隱藏狀態(tài)序列出現(xiàn)的概率舌胶。計算時刻T最大的ti, 即為時刻T最可能的隱藏狀態(tài)。
4) 利用局部狀態(tài)ti開始回溯岗屏。對于 t=T-1,T-2,...,1
最終得到最有可能的隱藏狀態(tài)序列I= I1.I2.....
4 HMM維特比算法求解實例
下面我們仍然用盒子與球的例子來看看HMM維特比算法求解辆琅。 我們的觀察集合是:
我們的狀態(tài)集合是：
而觀察序列和狀態(tài)序列的長度為3.
初始狀態(tài)分布為：
狀態(tài)轉移概率分布矩陣為：
觀測狀態(tài)概率矩陣為：
球的顏色的觀測序列:
按照我們前面的維特比算法漱办，首先需要得到三個隱藏狀態(tài)在時刻1時對應的各自兩個局部狀態(tài)这刷，此時觀測狀態(tài)為1：
現(xiàn)在開始遞推三個隱藏狀態(tài)在時刻2時對應的各自兩個局部狀態(tài)，此時觀測狀態(tài)為2：
繼續(xù)遞推三個隱藏狀態(tài)在時刻3時對應的各自兩個局部狀態(tài)娩井，此時觀測狀態(tài)為1：
