[L3]seq2seq中Beam search~Bs演算法

10-04

來自專欄深度學習與機器學習演算法5 人贊了文章

seq2seq中的Beam search演算法分成三個部分（因為標題字數限制，標題做了相應縮減）：

觸摸壹縷陽光：[L1]seq2seq中Beam search~應用場景?

zhuanlan.zhihu.com觸摸壹縷陽光：[L2]seq2seq中Beam search~貪心與維特比?

zhuanlan.zhihu.com觸摸壹縷陽光：[L3]seq2seq中Beam search~Bs演算法?

zhuanlan.zhihu.com

1.Beam search

現在正式來介紹beam search演算法。beam search方法中有一個關鍵的參數Beam Size B，這個B是遠遠小於 $V_{E}$ 的，即 $B ll V_{E}$ 。對於Viterbi演算法我們填一個 $V_{E}*N$ 的表格，那其實對於beam search演算法來說我們填的是一個 $B*V$ 的表格。直觀的來看beam search比Viterbi演算法效率高很多，因為 $B ll V_{E}$ 。

我們還是通過例子來說明演算法的流程，然後使用給出公式定義來，還是使用下面的概率圖模型來說說明：

概率圖模型~來自小象學院

我們還是要找出使得 $P(e_{1},e_{2},e_{3}|F)$ 最大的序列 $e_{1} e_{2} e_{3}$ ，現在假定beam search參數 $B = 2$ ，那麼會有：

第一步輸出（B = 2）：

第一步執行流程

第二步輸出（B = 2）：

第二步執行流程

第三步輸出（B = 2）：

第三步執行流程

從最後一步的輸出結果可以看出，最終輸出的序列為 $a c a$ 。知道了beam search的執行流程，下面給出公式定義：

$h(b,n)$ 在 $(b,n)$ 位置的已經生成的sequence；
$s(b,n) = P(h(b,n))$

遞推公式：已知 $s(b,n)$ 和 $h(b,n)$ ，求： $s(b,n+1),h(b,n+1)$ ，執行步驟如下：

$temp = [(h(b,n) + v,P(h(b,n)+v) | b = 1,...,B,v = 1,...,V)]$ ；
$temp = sort(temp,key = lambda x:[1])$ ，以概率值進行排序；
$b(i,n+1),s(i,n+1) = temp[i],i = 1,...,B$ ；

前面定義了這麼多變數，那下面那上面的第二步輸出說明一下這些變數表示的具體含義：

遞推公式具體含義

有了上面的認識，我們就可以填表了：

使用beam search演算法填的表格

那看看beam search演算法的複雜度：

計算複雜度 $O(Blog(V)N)$ ，我們是按列進行填寫的，所以需要計算 $B*N$ 個，我們對 $temp$ 進行排序的是 $Blog(V)$ ，所以是 $B*N + BVlog(V)$ ，所以每一列的計算複雜度是 $O(BVlog(V))$ ，那總共有 $N$ 列，所以計算複雜度為 $O(BVlog(V)N)$ ；
空間複雜度就是表格中需要填的元素個數，所以空間複雜度為 $O(BN)$ ；

那可以看出，beam search演算法還是很不錯的，他得到的結果是近似的最優解，如果target sequence辭彙表 $V_{E}$ 特別大的話，他的計算複雜度也不會太大，所以效率上Viterbi演算法和貪心演算法要高的很多。

4.beam search在seq2seq模型中應用

解碼器相當於是一個LSTM網路，那麼Viterbi演算法在解碼器部分，相當於每一步都需要計算出所有的 $V_{E}$ 個單詞所有的輸出概率值，也就是Viterbi演算法在編碼器中的的計算複雜度是 $O(VN)$ ，而beam search演算法雖然得到的是近似最優解，但是他在編碼器中的計算複雜度，由於每一步輸出只需要計算前一步最大的 $B$ 個值，所以beam search在編碼器上的計算複雜度是 $O(BN)$ ，那這個 $B ll V_{E}$ ，對於下面這個表格，我們如何對應到seq2seq模型中去：

使用beam search演算法填的表格

測試階段的seq2seq使用beam search

還有一點需要注意的，就是我們在第二步的時候，選擇了 $ab,ac$ ，也就是他的父節點都是 $a$ ，所以我們在進行 $h,c$ 的計算的時候需要將 $a$ 的語義編碼複製到替換 $b$ 的語義編碼，因為沒有使用 $b$ 。

也就可以認為，最後一步只需要 $a$ 的歷史，不需要 $b$ 的歷史。

參考：
1.小象學院