Viterbi 算法（找出最优序列）的主要思想是：截至当前时刻的最优序列可以由上一时刻的最优序列推算出。 （动态规划）
下面是根据理解自己画的概率图模型：
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个。
网友评论