维特比算法与beam search

　　端到端现在越来越火，花了点时间了解。发现端到端的解码用的都是beam search方法，而这种方法从理论上就不能得到最优解，为什么不能采用维特比算法呢？带着这个问题，看了数篇网上的介绍文章，结合自己几年做维特比解码的理解，简单整理了一下核心思想。

一、维特比算法

而维特比算法的精髓就是，既然知道到第i列所有节点Xi{j=123…}的最短路径，那么到第i+1列节点的最短路径就等于到第i列j个节点的最短路径+第i列j个节点到第i+1列各个节点的距离的最小值。

参考：https://www.zhihu.com/question/20136144

二、beam search

举个例子很容易说清楚：

seq2seq模型的decoder解码的时候：

1： 生成第1个词的时候，选择概率最大的2个词，假设为a,c,那么当前序列就是a,c
2：生成第2个词的时候，我们将当前序列a和c，分别与词表中的所有词进行组合，得到新的6个序列aa ab ac ca cb cc,然后从其中选择2个得分最高的，作为当前序列，假如为aa cb
3：后面会不断重复这个过程，直到遇到结束符为止。最终输出2个得分最高的序列。

简单来说，beamsearch是每次选取概率最大的beam width个词组作为结果，并将它们分别传入下一个时刻的decode阶段进行解码得到新的组合序列，在从新的序列中选取最大的beam width个词组，一直循环到结束。

三、对比greedy search和维特比算法

greedy search是beamsearch在beam width=1的情况下的特例。相对于greedy search，beamsearch实际上是增加了搜索空间，但也只能做到局部最优解，不一定是全局最优解。因为考虑到seq2seq的inference阶段的搜索空间过大而导致的搜索效率降低，所以即使是一个相对的局部优解在工程上也是可接受的。

那么怎么能得到一个全局最优解呢？个人理解只能是beam width等于语料库的大小时才能找到全局最优，当然这只是理论上，不存在应用上的可能，毕竟语料库太大，也没有必要。还有一种算法是可以reach全局最优解的，维特比算法，专为全局最优而生。但他是建立在前后隐状态独立的条件下的（维特比算法使用的假设前提是：全局最优解＝各分段最优解之和），所以decoder不能用维特比算法的根本原因在于不独立，隐状态太大不是不能使用维特比算法的理由。

总结一下：维特比算法从理论上能够得到最优解，beam search不能只能得到局部最后解。理由是维特比算法假设前后状态之间是相互独立的。

（viterbi有最优解是因为HMM每一步是条件独立的！！！独立！！！独立！！！重要的事说三遍！既然后面的概率和前面的没关系，那前面选最大的概率就行了！！！beam search时后面的概率依赖于前面所有的词，相当于n-gram是满的，viterbi的n-gram是2！）

作者：马奔
链接：https://www.zhihu.com/question/54356960/answer/556706681
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

四、关于beam search和维特比算法的时间复杂度

      设建模单元为N， beam size为K，解码所需时间步骤为T：

      (1) 如果k=1，即为greedy search，时间复杂度为O(NT)

      (2)beam search，时间复杂度为O(KNT)，局部最优

      (3)如果K=N，即维特比算法，时间复杂度为O(NNT),全局最优

参考：https://blog.csdn.net/pnnngchg/article/details/88082826

 　　   https://blog.csdn.net/Ding_xiaofei/article/details/82287275