Decoding Methods for Language Models_Greedy Search與Beam Search比較

諸多 NLP 應用（例如機器翻譯、聊天機器人、文本摘要或當前很夯的語言模型）都會產生文字作為輸出。另外，關於圖片說明（image captioning）或自動語音辨識（即語音轉文字）等應用也會輸出文字。所有這些應用在產生最終輸出的步驟中，都會使用以下幾種常用的演算法。

1.Exhaustive search(窮舉搜尋)

一種透過確認所有可能的狀況來尋找答案的方法。

窮舉所有可能的輸出序列，並在探索所有可能情況的同時，僅保留符合要求的結果。

保證能找到解但是效率不高

2.Greedy Search(貪婪搜尋)

在轉譯每個字的時候，直接選擇條件概率最大的候選值作為當前最優。

效率最高但並不能保證最終的結果一定是全局最優的。

可以看做是 beam size = 1時的 beam search。

3.Beam Search(束搜尋)

是一種對greedy search的改進算法。相對greedy search擴大了搜索空間。它非常受歡迎，因為儘管需要更多的運算量，但通常能產生更好的結果。

beam search有一個超參數beam size(束寬)，設為 k。第一個時間步長，選取當前條件概率最大的 k 個詞，當做候選輸出序列的第一個詞。

之後的每個時間步長，基於上個步長的輸出序列，挑選出所有組合中條件概率最大的 k 個，作為該時間步長下的候選輸出序列。始終保持 k 個候選。最後從 k 個候選中挑出最優的。

不保證全局最優，但是比greedy search搜索空間更大，一般結果比greedy search要好。

Ref:

Understanding greedy search and beam search

Foundations of NLP Explained Visually: Beam Search, How it Works

Two minutes NLP — Most used Decoding Methods for Language Models

How to Implement a Beam Search Decoder for Natural Language Processing

第25個冬天