Decoding Methods for Language Models_Exhaustive search,Greedy Search與Beam Search比較
語言模型不是只會「算機率」，真正影響輸出品質的是「怎麼選字」基本上分兩模式
Deterministic（確定性）
優點:可重現、偏「安全 / 標準答案」，常被應用在法規 / 技術文件。
缺點:容易重複、呆板，生成式任務中不夠生動。
Stochastic（隨機性）
優點:多樣有創意、輸出不固定
缺點:可能胡說、不一致
諸多 NLP 應用（例如機器翻譯、聊天機器人、文本摘要或當前很夯的語言模型）都會產生文字作為輸出。另外，關於圖片說明（image captioning）或自動語音辨識（即語音轉文字）等應用也會輸出文字。所有這些應用在產生最終輸出的步驟中，都會使用以下幾種常用的演算法。
以下探討的針對Deterministic模式做比較
1.Exhaustive search(窮舉搜尋)
一種透過確認所有可能的狀況來尋找答案的方法。
窮舉所有可能的輸出序列，並在探索所有可能情況的同時，僅保留符合要求的結果。
保證能找到解但是效率不高
假設我們要用詞彙表 { cold, coffee, I , like , water, <stop>} 生成一個 5 個詞的序列。
窮舉搜尋所有可能序列及其對應機率，並輸出機率最高的序列。
I like cold water
I like cold coffee
coffee coffee coffee coffee
I like I like
coffee like cold coffee
.....
所以對於每個句子的輸出，其機率將會是
P(x1, x2, x3,…..xn) = P(x1).P(x2/x1), ……….., P(xn/x1, x2, ……xn-1)
我們會在解碼過程中找到所有可能的序列。在每個時間步都會傳入所有的詞彙。
上述序列的總機率將等於
P(I) * P(like/I)*P(cold/I,like)*P(coffee/I,like,cold)
依樣畫葫蘆，其他組合的序列也會遵循上面相同的模式，並在每個時間步對所有標記進行概率計算，以產生最大機率的輸出。
搜尋空間中的機率
如果「I like cold coffee」序列被產生為最高機率，則該結果將會被標示出來
無論我們計算多少次，只要輸入相同，就會得到相同的答案，無法看見任何創造性的輸出。這屬於確定性策略。
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要好。
beam_size 是在每個時間步 t 中具有最高條件機率的詞數量。如下圖片中，beam_size=3。
序列 2 — 第二個 war 是 — (0.35 * 0.2 * 0.25 * 0.2) =0.0034
序列 3 — the war was the — (0.35 * 0.1 * 0.15 * 0.17) = 0.00089
序列 3 — the war was the — (0.35 * 0.1 * 0.15 * 0.17) = 0.00089
根據貪婪搜索演算法，我們選擇了序列 1，因為貪婪搜索找到的最高機率出現在第二個標記（last = 0.4），並且後續只從這一條分支繼續生成標記。
若採用 beam search 演算法，機率最高的序列是序列 2。這是一個明顯的例子，說明貪婪搜索演算法會捨棄機率較高的標記序列。
Ref:
Decoding Strategies of all Decoder only Models (GPT)
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
Learning as search
留言
張貼留言