筆記 | 什麼是Beam Search

Beam Search 是一種啟發式搜索演算法
，其使用廣度優先搜索來構建搜索樹，可降低內存需求，但不一定到全局最優解（without consuming too much memory）。
因為考慮到seq2seq的inference階段的搜索空間過大而導致的搜索效率降低，所以即使是一個相對的局部優解在工程上也是可接受的。

PS：本文僅作學習過程中的記錄，供討論交流

在機器翻譯（Machine Translation）裏是這樣的：在當前級別的狀態下計算所有可能性，並按照遞增順序對他們進行排序，但只保留一定數量的可能結果（依據Beam Width決定數量），接著根據這些可能結果進行擴展，迭代以上的動作直到搜索結束並返回最佳解（具有最高概率的那個）。

Andrew Ng講得蠻清楚的，可以先看一下，為了方便我就直接下載傳到知乎啦，相關鏈接在參考資料[4]。

11:54AndrewNg-Beam Search

這邊綜合一下 @蕭瑟的回答，在Phased-Based Machine Translation做Test的時候（訓練的時候知道正確答案，不需要再進行這個搜索）：

假設詞表大小為3，包含[A, B, C]，Beam Width為2

生成第1個詞的時候，對P(A)、P(B)、P(C)進行排序，選取概率最大的兩個，假設為A，C
生成第2個詞的時候，將當前序列A，C分別和詞表中的所有詞進行組合，得到新的6個序列為AA、AB、AC，CA、CB、CC，然後同樣取概率最大的兩個作為當前序列，假設為AA、CC
重複以上的過程，直到遇到結束符為止，最終輸出2個得分最高的序列

更新：剛剛發現一個不錯的介紹10.10. 束搜索 - 《動手學深度學習》文檔，來保存一下。

PS：最近在Meeting的時候，發現Lab同學好幾個已經開始在做Machine Translation了，一年半前剛進Lab的時候，全體還是以Data Mining尤其是Text Mining為主，現在都轉向Deep Learning了。另外，最近也需要快一些實現一遍Sequence to Sequence，把相關的概念認真梳理一遍。

參考資料：

[1]:習翔宇：Seq2Seq中的beam search演算法

[2]:誰能解釋下seq2seq中的beam search演算法過程?

[3]:誰能解釋下seq2seq中的beam search演算法過程?

[4]:C5W3L03 Beam Search

[5]:Beam search - Wikipedia

[6]:ADLxMLDS Lecture 5: Gated RNN and Sequence Generation (17/10/30)