论文标题
最佳第一光束搜索
Best-First Beam Search
论文作者
论文摘要
为许多NLP任务进行解码需要有效的启发式算法来近似精确的搜索，因为搜索完整的输出空间的问题通常是棘手的，或者在许多情况下都不切实际。此作业的默认算法是Beam Search - 一个修剪版本的广度优先搜索。令人惊讶的是，由于对NLP任务的有益搜索偏差，横梁搜索通常比精确推断更好。在这项工作中，我们表明，在实践中，梁搜索的标准实现最多可快10倍。我们的方法假设评分函数在序列长度上是单调的，这使我们能够安全地修剪无法在最终的假设中进行的假设。我们将有效的单调近似值用于流行的非单线评分功能，包括长度归一化和相互信息解码。最后，我们提出了一种最佳优先梁搜索的记忆降低的变体，该变体在下游性能方面具有类似的有益搜索偏差，但在很少的时间内运行。
Decoding for many NLP tasks requires an effective heuristic algorithm for approximating exact search since the problem of searching the full output space is often intractable, or impractical in many settings. The default algorithm for this job is beam search -- a pruned version of breadth-first search. Quite surprisingly, beam search often returns better results than exact inference due to beneficial search bias for NLP tasks. In this work, we show that the standard implementation of beam search can be made up to 10x faster in practice. Our method assumes that the scoring function is monotonic in the sequence length, which allows us to safely prune hypotheses that cannot be in the final set of hypotheses early on. We devise effective monotonic approximations to popular nonmonontic scoring functions, including length normalization and mutual information decoding. Lastly, we propose a memory-reduced variant of Best-First Beam Search, which has a similar beneficial search bias in terms of downstream performance, but runs in a fraction of the time.
