10.8.1。貪心搜索

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

一旦我們的模型輸出“”（或者我們達(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ù)了潛在生成過(guò)程的概率，那么這將為我們提供最有可能的翻譯。不幸的是，不能保證貪心搜索會(huì)給我們這個(gè)序列。

讓我們用一個(gè)例子來(lái)說(shuō)明它。假設(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)?/font>圖10.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)序列。