Seq2Seq中的beam search演算法

04-30

在Sequence to Sequence模型中我們介紹了seq2seq模型，並介紹了機器翻譯的應用，在得到訓練模型之後，我們希望能夠得到句子序列的條件概率最大的序列，例如

法語句子"Jane visite lAfrique en septembre."翻譯1-Jane is visiting Africa in September.翻譯2-Jane is going to be visiting Africa in September.

顯然翻譯2聽起來比較笨拙，並不是最好的翻譯，也就是

$P(y_1|x)>P(y_2|x) ag{1}$

因此我們希望得到一個單詞序列表示英文句子使得條件概率最大：

$argmax_{y} P( y^{<1>},y^{<2>},y^{<3>},...y^{<T_y>}|x^{<1>},x^{<2>},...x^{<T_x>}) ag{2}$

1. Why not a greedy search?

一個很直觀的方法是採用貪心搜索(greedy search)，在生成第一個詞 $y^{<1>}$ 的分布之後，根據條件語言模型挑選出最有可能的第一個詞 $y^{<1>}$ ，然後生成第二個詞 $y^{<2>}$ 的概率分布挑選第二個詞 $y^{<2>}$ ，依此類推。可以看出貪心演算法始終是選擇每一個最大概率的詞，但我們真正需要的是一次性挑選整個單詞序列 $y^{<1>},y^{<2>},y^{<3>},...y^{<T_y>}$ 使得整體的條件概率最大，所以貪心演算法先挑出最好的第一個詞，在這之後再挑最好的第二詞，然後再挑第三個，這種方法其實並不管用，我們用上面的例子進行說明。

法語句子"Jane visite lAfrique en septembre."翻譯1-Jane is visiting Africa in September.翻譯2-Jane is going to be visiting Africa in September.

翻譯1顯然比翻譯2要更好，更加簡潔的表達了意思，第二個就很啰嗦並且有很多不重要的詞。如果貪心演算法挑選了 $y^{<1>},y^{<2>}=$ (Jane , is)，那麼在英語中"is going"更加常見，因此在選擇 $y^{<3>}$ 時就會得到 $y^{<3>}=$ going，於是對於法語句子來說"Jane is going"相比"Jane is visiting"會有更高的概率作為法語的翻譯，所以很有可能如果你僅僅根據前兩個詞來估計第三個詞的可能性，得到的就是going，最終你會得到一個欠佳的句子。

2. Beam Search

在Beam Search中只有一個參數B，叫做beam width(集束寬)，用來表示在每一次挑選top B的結果。

我們用下面這個例子來做說明，假設字典大小為10000，B=3

法語句子"Jane visite lAfrique en septembre."翻譯1-Jane is visiting Africa in September.翻譯2-Jane is going to be visiting Africa in September.

在第一步的時候，我們通過模型計算得到 $y^{<0>}$ 的分布概率，選擇前B個作為候選結果，比如如下圖所示的"in", "jane", "september"

圖1 beam search step 1

第二步的時候，我們已經選擇出了in、jane、September作為第一個單詞的三個最可能選擇，beam search針對每個第一個單詞考慮第二個單詞的概率，例如針對單詞「in」，我們將 $y^{<1>}$ =in，然後將它餵給 $x^{<2>}$ ，輸出結果 $y^{<2>}$ 作為第二個單詞的概率輸出。因為我們關注的是最有可能的 $P(y^{<2>},y^{<1>}|x)$ ，因此我們的選擇方法為：