束搜索（beam search）

貪心搜索（greedy search）

在 seq2seq 中使用了貪心搜索來預(yù)測(cè)序列（對(duì)于輸出序列的每一時(shí)間步，將當(dāng)前時(shí)刻具有最高條件概率的詞元輸出，作為下一個(gè)序列，一旦輸出序列包含了“<eos>”或者達(dá)到最大長(zhǎng)度，則輸出完成）

但是貪心搜索的結(jié)果可能不是最優(yōu)的，舉例如下

• 上圖中將兩次選擇各部分的概率分別進(jìn)行相乘，會(huì)發(fā)現(xiàn)雖然右邊并沒有選擇最優(yōu)，但是最終生成 sequence 的概率比貪心搜索所得到的概率更高（因?yàn)楫?dāng)前步所選擇的最優(yōu)的詞從整個(gè)句子來看的話不一定是最優(yōu)的，所以貪心搜索可能是效率最高的，但是不一定是最優(yōu)的）

窮舉搜索（exhaustive search）

如果目標(biāo)是獲取最優(yōu)序列，可以考慮使用窮舉搜索：窮舉地列出所有可能的輸出序列及其條件概率，然后計(jì)算輸出條件概率最高的一個(gè)（遍歷所有的序列，將所有的序列的概率計(jì)算出來，最后選出最好的那個(gè)序列一定是最優(yōu)的，也就是將所有的序列都使用模型評(píng)估一下）

如果輸出字典大小為 n ，序列最長(zhǎng)為 T ，那么需要考察 n ^ T 個(gè)序列

• n = 10000 , T = 10 : n^T = 10^4
• 計(jì)算上不可行，現(xiàn)有的計(jì)算機(jī)幾乎不可能計(jì)算它
• 貪心搜索是最快的，但不是最好的；窮舉搜索是最好的，但是計(jì)算量巨大，計(jì)算起來比較困難

束搜索（beam search）

• 如果只看重精度的話，顯然窮舉搜索算法是最優(yōu)的；如果更注重計(jì)算成本的話，則貪心搜索算法是最優(yōu)的；束搜索的實(shí)際應(yīng)用介于這兩個(gè)極端之間
• 在每個(gè)時(shí)刻，保存最好的 k 個(gè)候選序列，對(duì)每個(gè)候選新加一項(xiàng)（ n 種可能），在 kn 個(gè)選項(xiàng)中選出最好的 k 個(gè)

舉例：

• 束搜索是貪心搜索的改進(jìn)版本，它和貪心算法的區(qū)別在于，貪心算法每次都選擇最好的一個(gè)詞元來組成序列，而束搜索每次選擇 k 個(gè)作為候選
• k 是超參數(shù)，稱為束寬（beam size），在時(shí)間步 1 ，算法所選擇的是具有條件概率最高的 k 個(gè)詞元，這 k 個(gè)詞元將分別是 k 個(gè)候選輸出序列的第一個(gè)詞元；在隨后的每個(gè)時(shí)間步，基于上一時(shí)間步的 k 個(gè)候選輸出序列，將繼續(xù)挑出具有最高條件概率的 k 個(gè)候選輸出序列

時(shí)間復(fù)雜度： O(knT)

• 對(duì)于每一個(gè)時(shí)刻 T 都需要做 kn 次搜索
• k = 5 , n = 10000 , T = 10 : knT = 5 x 10^5
• 束搜索的計(jì)算量介于貪心搜索和窮舉搜索之間
• 貪心搜索可以看作是一種束寬為 1 的特殊類型的束搜索
• 通過靈活地選擇束寬，束搜索可以在正確率和計(jì)算代價(jià)之間進(jìn)行權(quán)衡

每個(gè)候選的最終分?jǐn)?shù)是

• 最后不僅能夠得到 k 個(gè)選擇，還能夠?qū)⑺阉鬟^程中得到的子序列也保存下來，基于這些序列獲得最終候選輸出序列集合，然后按照上述公式挑選其中條件概率乘積最高的序列作為輸出序列
• 在計(jì)算概率的時(shí)候會(huì)發(fā)現(xiàn)，長(zhǎng)句子的概率會(huì)低于短句子的概率（因?yàn)槭歉鞑糠指怕实某朔e，而概率的值都是小于 1 的，所以句子越長(zhǎng)，概率就越低，所以一個(gè)句子的概率會(huì)低于它的子句的概率），所以這里引入了一個(gè) 1 / (L ^ α)，等價(jià)于提高最終長(zhǎng)句子所得到的分?jǐn)?shù)，否則模型會(huì)傾向于學(xué)習(xí)長(zhǎng)度較短的句子
• L 是最終候選序列的長(zhǎng)度
• 通常 α = 0.75

總結(jié)

1、序列搜索策略包括貪心搜索、窮舉搜索和束搜索

• 貪心搜索所選取序列的計(jì)算量最小，但是精度相對(duì)較低
• 窮舉搜索所選取序列的精度最高，但是計(jì)算量最大
• 束搜索通過靈活選擇帶寬，在正確率和計(jì)算代價(jià)之間進(jìn)行權(quán)衡

2、束搜索在每次搜索時(shí)保存 k 個(gè)最好的候選

• k = 1 時(shí)是貪心搜索，每一步總是選擇最好的詞元作為候選
• 束搜索的 k 一般取 5 或者 10 ，通常來說 k 的值選的越大，所選擇的范圍也就越大，但是可能最后實(shí)施的效果也就越差（在做語音特別是實(shí)時(shí)翻譯的時(shí)候，k 的取值不能太大，如果取值比較大的話，會(huì)大大降低模型的實(shí)時(shí)性）

----end----

其他參考

1、《動(dòng)手學(xué)深度學(xué)習(xí)》，課程安排，https://courses.d2l.ai/zh-v2/assets/pdfs/part-3_10.pdf