PyTorch教程-10.8。波束搜索

在10.7 節(jié)中，我們介紹了編碼器-解碼器架構(gòu)，以及端到端訓(xùn)練它們的標(biāo)準(zhǔn)技術(shù)。然而，當(dāng)談到測(cè)試時(shí)間預(yù)測(cè)時(shí)，我們只提到了 貪心策略，我們?cè)诿總€(gè)時(shí)間步選擇下一個(gè)預(yù)測(cè)概率最高的標(biāo)記，直到在某個(gè)時(shí)間步，我們發(fā)現(xiàn)我們已經(jīng)預(yù)測(cè)了特殊的序列結(jié)尾“”標(biāo)記。在本節(jié)中，我們將從形式化這種貪婪搜索策略開始，并確定從業(yè)者往往會(huì)遇到的一些問題。隨后，我們將該策略與兩種替代方案進(jìn)行比較：窮舉搜索（說明性但不實(shí)用）和 波束搜索（實(shí)踐中的標(biāo)準(zhǔn)方法）。

讓我們從設(shè)置我們的數(shù)學(xué)符號(hào)開始，借用第 10.7 節(jié)中的約定。隨時(shí)步t′，解碼器輸出表示詞匯表中每個(gè)標(biāo)記出現(xiàn)在序列中的概率的預(yù)測(cè)（可能的值 yt′+1, 以先前的標(biāo)記為條件 y1,…,yt′和上下文變量c，由編碼器產(chǎn)生以表示輸入序列。為了量化計(jì)算成本，表示為Y輸出詞匯表（包括特殊的序列結(jié)束標(biāo)記“”）。我們還將輸出序列的最大標(biāo)記數(shù)指定為 T′. 我們的目標(biāo)是搜索所有的理想輸出 O(|Y|T′)可能的輸出序列。請(qǐng)注意，這稍微高估了不同輸出的數(shù)量，因?yàn)樵凇啊睒?biāo)記出現(xiàn)之后沒有后續(xù)標(biāo)記。然而，出于我們的目的，這個(gè)數(shù)字大致反映了搜索空間的大小。

10.8.1。貪心搜索

考慮第 10.7 節(jié)中的簡(jiǎn)單貪婪搜索策略 。在這里，隨時(shí)步t′，我們只需從中選擇條件概率最高的標(biāo)記 Y， IE，

(10.8.1)yt′=argmaxy∈YP(y∣y1,…,yt′?1,c).

一旦我們的模型輸出“”（或者我們達(dá)到最大長(zhǎng)度 T′) 輸出序列完成。

這個(gè)策略看似合理，其實(shí)還不錯(cuò)！考慮到它在計(jì)算上的要求是多么的低，你很難獲得更多的收益。然而，如果我們暫時(shí)擱置效率，搜索最有可能的序列似乎更合理，而不是（貪婪選擇的）最有可能的標(biāo)記序列。事實(shí)證明，這兩個(gè)對(duì)象可能完全不同。最可能的序列是最大化表達(dá)式的序列 ∏t′=1T′P(yt′∣y1,…,yt′?1,c). 在我們的機(jī)器翻譯示例中，如果解碼器真正恢復(fù)了潛在生成過程的概率，那么這將為我們提供最有可能的翻譯。不幸的是，不能保證貪心搜索會(huì)給我們這個(gè)序列。

讓我們用一個(gè)例子來(lái)說明它。假設(shè)輸出字典中有四個(gè)標(biāo)記“A”、“B”、“C”和“”。在 圖10.8.1中，每個(gè)時(shí)間步下的四個(gè)數(shù)字分別代表在該時(shí)間步生成“A”、“B”、“C”、“”的條件概率。

圖 10.8.1在每個(gè)時(shí)間步，貪婪搜索選擇條件概率最高的標(biāo)記。

在每個(gè)時(shí)間步，貪心搜索選擇條件概率最高的標(biāo)記。因此，將預(yù)測(cè)輸出序列“A”、“B”、“C”和“”（圖 10.8.1）。這個(gè)輸出序列的條件概率是 0.5×0.4×0.4×0.6=0.048.

接下來(lái)，讓我們看一下圖 10.8.2中的另一個(gè)例子。與圖 10.8.1不同，在時(shí)間步 2 中，我們選擇圖 10.8.2中的標(biāo)記“C” ，它具有第二高的條件概率。

圖 10.8.2每個(gè)時(shí)間步下的四個(gè)數(shù)字代表在該時(shí)間步生成“A”、“B”、“C”和“”的條件概率。在時(shí)間步 2，選擇具有第二高條件概率的標(biāo)記“C”。

由于時(shí)間步3所基于的時(shí)間步1和2的輸出子序列已經(jīng)從圖10.8.1中的“A”和“B”變?yōu)閳D10.8.2 中的“A”和“C” ，圖 10.8.2中每個(gè)標(biāo)記在時(shí)間步長(zhǎng) 3 的條件概率也發(fā)生了變化 。假設(shè)我們?cè)跁r(shí)間步 3 選擇標(biāo)記“B”。現(xiàn)在時(shí)間步 4 以前三個(gè)時(shí)間步“A”、“C”和“B”的輸出子序列為條件，這與“A”不同、“B”、“C”在圖 10.8.1中。因此，圖 10.8.2中第 4 步生成每個(gè) token 的條件概率 也與 圖 10.8.1不同. 因此， 圖 10.8.2中輸出序列“A”、“C”、“B”和“”的條件概率為 0.5×0.3×0.6×0.6=0.054，大于圖 10.8.1中的貪心搜索。在本例中，貪心搜索得到的輸出序列“A”、“B”、“C”、“”并不是最優(yōu)序列。

10.8.2。窮舉搜索

如果目標(biāo)是獲得最可能的序列，我們可以考慮使用 窮舉搜索：窮舉所有可能的輸出序列及其條件概率，然后輸出得分最高的預(yù)測(cè)概率。

雖然這肯定會(huì)給我們想要的東西，但它的計(jì)算成本卻高得令人望而卻步 O(|Y|T′)，序列長(zhǎng)度呈指數(shù)增長(zhǎng)，詞匯量很大。例如，當(dāng)|Y|=10000和T′=10，我們需要評(píng)估1000010=1040序列。與實(shí)際應(yīng)用程序相比，這些數(shù)字很小，但已經(jīng)超出了任何可預(yù)見的計(jì)算機(jī)的能力。另一方面，貪心搜索的計(jì)算成本是 O(|Y|T′): 奇跡般地便宜，但遠(yuǎn)非最佳。例如，當(dāng)|Y|=10000和 T′=10, 我們只需要評(píng)估10000×10=105 序列。

10.8.3。波束搜索

您可以將序列解碼策略視為位于頻譜上， 波束搜索在貪婪搜索的效率和窮舉搜索的最優(yōu)性之間做出折衷。波束搜索的最直接版本的特征在于單個(gè)超參數(shù)， 波束大小，k. 在時(shí)間步 1，我們選擇k具有最高預(yù)測(cè)概率的標(biāo)記。他們每個(gè)人都將是第一個(gè)令牌k候選輸出序列，分別。在隨后的每個(gè)時(shí)間步，基于k上一時(shí)間步的候選輸出序列，我們繼續(xù)選擇k具有最高預(yù)測(cè)概率的候選輸出序列 k|Y|可能的選擇。

圖 10.8.3束搜索過程（束大?。?，輸出序列的最大長(zhǎng)度：3）。候選輸出序列是A, C,AB,CE,ABD， 和CED.

圖 10.8.3舉例說明了 beam search 的過程。假設(shè)輸出詞匯表只包含五個(gè)元素：Y={A,B,C,D,E}，其中之一是“”。令波束大小為 2，輸出序列的最大長(zhǎng)度為 3。在時(shí)間步長(zhǎng) 1，假設(shè)具有最高條件概率的標(biāo)記P(y1∣c)是A 和C. 在時(shí)間步 2，對(duì)于所有y2∈Y,我們計(jì)算

(10.8.2)P(A,y2∣c)=P(A∣c)P(y2∣A,c),P(C,y2∣c)=P(C∣c)P(y2∣C,c),

并在這十個(gè)值中選擇最大的兩個(gè)，比如說 P(A,B∣c)和P(C,E∣c). 然后在第 3 步，對(duì)于所有y3∈Y, 我們計(jì)算

(10.8.3)P(A,B,y3∣c)=P(A,B∣c)P(y3∣A,B,c),P(C,E,y3∣c)=P(C,E∣c)P(y3∣C,E,c),

并在這十個(gè)值中選擇最大的兩個(gè)，比如說 P(A,B,D∣c)和 P(C,E,D∣c).結(jié)果，我們得到六個(gè)候選輸出序列：(i)A; (二)C; (三)A, B; (四)C,E; (五)A,B, D; (六)C,E,D.

最后，我們根據(jù)這六個(gè)序列得到最終候選輸出序列的集合（例如，丟棄包括“”和“”之后的部分）。然后我們選擇以下得分最高的序列作為輸出序列：

(10.8.4)1Lαlog?P(y1,…,yL∣c)=1Lα∑t′=1Llog?P(yt′∣y1,…,yt′?1,c),

在哪里L(fēng)是最終候選序列的長(zhǎng)度， α通常設(shè)置為 0.75。由于較長(zhǎng)的序列在(10.8.4)的總和中具有更多的對(duì)數(shù)項(xiàng)，因此項(xiàng)Lα在分母中懲罰長(zhǎng)序列。

beam search的計(jì)算成本是 O(k|Y|T′). 這個(gè)結(jié)果介于貪婪搜索和窮舉搜索之間。貪心搜索可以看作是波束大小為 1 時(shí)出現(xiàn)的波束搜索的特例。

10.8.4。概括

序列搜索策略包括貪婪搜索、窮舉搜索和波束搜索。波束搜索通過其對(duì)波束大小的靈活選擇，在準(zhǔn)確性與計(jì)算成本之間進(jìn)行權(quán)衡。

10.8.5。練習(xí)

我們可以將窮舉搜索視為一種特殊類型的波束搜索嗎？為什么或者為什么不？

在10.7 節(jié)的機(jī)器翻譯問題中應(yīng)用集束搜索 。光束大小如何影響翻譯結(jié)果和預(yù)測(cè)速度？

在第 9.5 節(jié)中，我們使用語(yǔ)言建模來(lái)生成遵循用戶提供的前綴的文本。它使用哪種搜索策略？你能改進(jìn)它嗎？

Discussions