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: https://d2l.ai/chapter_recurrent-modern/beam-search.html https://hackmd.io/@ucjVdUisQgurlILr8R9VCw/ry2_sVvin Understanding greedy search and beam search https://medium.com/@jessica_lopez/understanding-greedy-search-and-beam-search-98c1e3cd821d Foundations of NLP Explained Visually: Beam Search, How it Works https://towardsdatascien...