Note - Viterbi 算法 与 beam-seach 算

Viterbi 算法（找出最优序列）的主要思想是：截至当前时刻的最优序列可以由上一时刻的最优序列推算出。 （动态规划）

参见  维特比算法 | 吴良超的学习笔记

Viterbi Algorithm Clarified

下面是根据理解自己画的概率图模型：

beam_search 属于贪心（不是最贪）算法， bfs with width constraint

可参考seq2seq中的beam search算法过程 - 知乎

时间复杂度是 m*b*V

m: 解码步数

b: beam size

V: Vocabulary size

viterbi 和 beam_search 的区别

如果将viterbi用到seq2seq的decoder中，只需和beam_search中的beam_size=vocabulary_size进行对比

此时，时间复杂度都是 m*V^2, 但选择过程不一样，viterbi 是取到达当前state（单词）的最优单词序列（V个中选最优， 一共V个这样的选择） 

beam_search中的beam_size=vocabulary_size 则是取整体V^2个候选中的top-V个。