一. Viterbi 演算法

因為若要一條條計算每個path的話會花許多時間，利用Dynamic Programming的方法通常會先將前一次狀態的結果存起來，再計算下一個狀態時，再將前一個狀態的結果取出來，可以降低時間複雜度。那如何保留前一個狀態的結果，下面我以前一篇的天氣當例子，當水草當天都為Dry時，哪種天氣組合的機率最大例子：

假設我們有HMM需要的三種矩陣：

1. 初始狀態:
   

   • 在為晴天的狀況下綠色Dry的機率為 0.4(初始的機率)x 0.6(晴天對Dry的機率) = 0.024
   • 在為雨天的狀況下綠色Dry的機率為 0.6(初始的機率)x 0.1(晴天對Dry的機率) = 0.06

2. 計算第二個Dry上半部分的狀態:
   

   • 前一天為晴天，今天又為晴天的機率，並且為Dry的機率為 0.024(上一個狀態的機率) * 0.6(前一天為晴天後一天又為晴天的機率) * 0.6(晴天對Dry的機率) = 0.00864
   • 前一天為雨天，今天為雨天的機率，並且為Dry的機率為 0.06(上一個狀態的機率) * 0.3(前一天為雨天後一天又為晴天的機率) * 0.1(晴天對Dry的機率) = 0.0018
   • 接者就是Viterbi 演算法的精髓~紀錄當前最大的機率:
     max(0.00864, 0.0018) = 0.00864

3. 計算第二個Dry下半部分的狀態:
   

   • 前一天為晴天，今天為雨天的機率，並且為Dry的機率為 0.024(上一個狀態的機率) * 0.4(前一天為晴天後一天為雨天的機率) * 0.6(雨天對Dry的機率) = 0.00144
   • 前一天為雨天，今天為晴天的機率，並且為Dry的機率為 0.06(上一個狀態的機率) * 0.7(前一天為雨天後一天又為雨天的機率) * 0.1(雨天對Dry的機率) = 0.0042
   • 紀錄當前最大的機率:
     max(0.00144, 0.0042) = 0.0042
   • P.S. Viterbi 演算法會多一個table去記錄目前連結到這個node的前一個node，用此來記錄經過這個node的最大path，下面的圖我會多紀錄這個node的前一個node

4. 計算第三個Dry上半部分的狀態:
   

   • 前一天為晴天，今天又為晴天的機率，並且為Dry的機率為 0.00864(上一個狀態的機率) * 0.6(前一天為晴天後一天又為晴天的機率) * 0.6(晴天對Dry的機率) = 0.0031104
   • 前一天為晴天，今天為雨天的機率，並且為Dry的機率為 0.0042(上一個狀態的機率) * 0.3(前一天為雨天後一天為晴天的機率) * 0.6(晴天對Dry的機率) = 0.000756
   • 紀錄當前最大的機率:
     max(0.0031104, 0.000756) = 0.0031104

5. 計算第三個Dry下半部分的狀態:
   

   • 前一天為晴天，今天為雨天的機率，並且為Dry的機率為 0.00864(上一個狀態的機率) * 0.4(前一天為晴天後一天為雨天的機率) * 0.1(雨天對Dry的機率) = 0.0003456
   • 前一天為雨天，今天為雨天的機率，並且為Dry的機率為 0.0042(上一個狀態的機率) * 0.7(前一天為雨天後一天又為雨天的機率) * 0.1(雨天對Dry的機率) = 0.000294
   • 紀錄當前最大的機率:
     max(0.0003456, 0.000294) = 0.0003456

6. 最後狀態回如下圖:
   

然後就完成了~~

上面的式子算到後面真的有點亂掉ＱＱ~如果有覺得哪裡算得很怪可以再跟我說，我有空會看~
這邊也附上一個參考資訊[1]，寫的真的非常詳細~也可以參考一下
明天將會利用python實現HMM+Viterbi 演算法來處理POS的任務~~

參考資訊
[1] Viterbi Algorithm