论文笔记：Beam Search Strategies for Neural Machine Translation
作者：
Markus Freitag and Yaser Al-Onaizan
单位：
IBM T.J. Watson Research Center
关键词：
Beam search; Pruning strategies
问题：
束搜索算法跟踪k个状态，而不仅仅只跟踪一个。它从k个随机生成的状态开始，在每一步中都生成所有k个状态的所有后继者。如果这其中的任何一个后继者是目标，那么算法就会停止。否则，它将从完整列表中选择k个最佳后继者并不断重复。
在束或并行搜索数量确定的情况下，现有的束搜索策略存在的可能的问题是：
1、 远小于当前最优得分的序列也会被扩展；
2、 与当前最优得分相差不多的序列由于k的限制未被扩展。
第二种情况可以通过采用较大的束宽度来避免，然而这种性能的提高会导致解码速度降低。
动机：
提出多种beam search的策略，加快解码器速度。
候选序列（best scoring candidates）往往共享同一个部分序列（partialhypothesis），文章对这种现象做出限制，从而加大候选序列的多样性。
模型：
几种剪枝策略：
1、 Relative Threshold Prunning
给定一个相对剪枝门限rp，丢弃比最优候选序列得分低的序列：
2、 Absolute Threshold Prunning
给定一个绝对剪枝门限ap，丢弃比最优候选序列得分低的序列：
3、 Relative Local Threshold Prunning
只考虑最后一个生成的单词的得分而不是整个候选序列的得分：
4、 Maximum Candidates per Node
只允许有限数目个共享部分序列的候选序列。
解码速度的衡量:
1、 与不采用任何剪枝策略的普通beamsearch速度相比
2、 在每一个时刻，定义该时刻扩展的候选序列为fan out。fan out的取值上限为beam size，也可以小于beam size，小于的情况包括扩展到终止符或者使用了上面提到的剪枝策略。
对于每种剪枝策略，作者在不同的threshold值下做了实验，最终选取在不会降低翻译质量的前提下的最大threshold值。
简评：
采用文章的剪枝策略可以做到在每个时刻选择的后继者数目不同。实验证明能够加速解码。