beam search柱搜索

柱搜索在每次预测的时候是选取概率最高的topk个路径。假设词表大小为3，内容为a，b，c，topk是2。在seq2seq任务decode时：

1. 生成第1个词的时候，选择概率最大的2个词，假设为a,c,那么当前序列就是a,c
2. 生成第2个词的时候，将当前序列a和c分别作为输入，得到新的6个序列：aa,ab,ac,ca,cb,cc。然后又从其中选择得分最高的两个，假如是aa，cb
3. 不断重复这个过程，知道遇到结束符为止。最终输出得分最高的2个序列。

要点：

• 基于贪心算法思想。
• seq2seq中decoder的预测过程，可以看做一种宽度（或者说是广度）优先图搜索。因为每一步预测候选集（词表大小是10万量级）很大，所以将概率较低的分支删除，即剪枝。这样大大缩小了搜索空间，所以其得到的是近似解，不是全局最优解。是一种启发式算法。
• beam search只在test的时候需要。训练的时候知道正确答案，并不需要再进行这个搜索。
• 常用于搜索空间非常大的情况，如语言生成任务，每一步是选择一个词，而词表非常大，在十万量级，beam search可以大大减少计算量。

viterbi维特比

要点：

• viterbi是基于动态规划思想。
• 每一步是根据上一步全部可能选择的最高概率推测当前所有可能选择的最高概率，保证有全局最优解。
• 适合于搜索宽度较小的图寻找最优路径，即每一步的选择比较少的时候。如在CRF、HMM中使用