[Day8] 词性标注(三)-Viterbi 演算法

一. 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