参考视频1：https://www.bilibili.com/video/BV1Gs421N7S1/?spm_id_from=333.337.search-card.all.click&vd_source=7a1a0bc74158c6993c7355c5490fc600 （beam search 视频）

参考博客1：https://jasonhhao.github.io/2020/06/19/S2S-Beam-Search/ （beam search 博客）

---

Beam search 如下图所示
Beam search 可以用来做文本生成任务，也可以用来做序列标注任务（比如给每一个单词分配一个词性 (名词/谓词)）
以 k=3 为例，从 <start> 计算 softmax 可以得到所有单词的概率(概率加个 log，让它成为负数)，我们选择 k=3 个概率最高的单词，然后再次计算它们的 softmax，得到 k=3 个单词的所有单词概率(加个 log，让它成为负数)。此时再从这所有概率中挑出 3 个概率最大的单词，用来做接下来的分支。
这个过程持续到找到一个 <end> 标志，且这个 <end> 标志的概率最大
这个过程复杂度是 O(k^2 T)
但这个方法有一个缺陷：那就是算法最终输出的语句趋向于短句。因为序列越短，log 相加的结果就会大一些。
所以可以做一个优化：log值的计算和序列长度求平均