論文標題：Best-First Beam Search

論文作者：Clara Meister, Tim Vieira,?Ryan Cotterell

論文鏈接：https://arxiv.org/pdf/2007.03909.pdf

---

Beam Search是當前各類文本生成任務的標配解碼方式，作為一種受限的寬度優先搜索，它可以極大降低搜索復雜度。但是，Beam Search依舊還有提高的空間！

本文提出一種結合優先隊列和A*經驗式搜索的Beam Search，可以顯著減少調用打分函數（如負對數似然）的次數，從而能夠使整個Beam Search速度大大加快，還能得到和Beam Search一樣的結果。

Beam Search?概述

在文本生成中，Beam Search已經被作為一種普遍的解碼方式運用在各種任務中。假設當前輸入是，要生成的句子是，最大長度是，字典是，那么，所有可能的句子就是。Beam Search就是在每一步通過打分函數只保留個候選句子。打分函數一般是對數似然：

-最大堆，在每一步，對這個句子中的每一個，如果它已經結束了（第5行），那么就不處理它，否則加上當前步的得分（每個句子都有次計算得分），再把新得到的句子加入堆中，等到所有句子處理完之后，再從中取個得分最大的。

因為Beam Search是主要的比較對象，因此我們把由Beam Search返回的個句子叫做-最佳集，其中的任何一個句子都稱為-最佳句子。

Beam Search 的問題

從上面的介紹講，乍一看，Beam Search的效率很高，然而，Beam Search也隱藏著一些細節上的問題。舉個例子，假設，詞典是，現在保留的句子是，它們當前的得分分別是，且下一步可能的句子的得分是：

句子得分句子得分句子得分

acb	acba	0.30	acbb	0.31	acbc	0.25
abb	abba	0.29	abbb	0.28	abbc	0.24

看，在下一步的Beam Search中，我們當前得到的第二個句子根本不重要，因為下一步得分最高的兩個句子都來自于，因此，我們完全可以不去計算由得到的三個句子。

那么，這里的關鍵是什么呢？是最佳優先，即讓當前得分最大的句子先計算下一步，這就很像A*搜索。

A?*?Beam?Search?

A*是一種啟發式搜索，即通過預定義的得分函數，每次都首先探索得分最高的那一條路徑。顯然，只要得分函數定義得好，就能比DFS和BFS更快地找到正確答案。

那么在這里，所謂的正確答案就是BS得到的-最佳結果。我們的目標是設計一種啟發式的搜索算法，既能得到-最佳結果，又比BS更快。

下面的算法就描述了一種通用的搜索算法框架。

注意觀察，和BS相比，該算法引入了4個關鍵的成分：（1）比較符；（2）停止策略；（3）；（4）經驗函數。其中除了（3）是BS原有的之外，其他的都是新增的。有了這幾個成分，就可以使用該算法實現BS，和即將要介紹的A* Beam Search。

來看一下這個算法做了什么。首先用定義了一個優先隊列；然后在搜索的每一步，直接看得分最大的那個句子，如果這個句子結束了，那么就繼續放入優先隊列中。

否則像BS一樣考慮字典中的每個字，在原來的得分（如對數似然）上再加上經驗函數得分，然后再把它送到優先隊列中。

注意到圖中綠色的部分，它的意思是，對同一個句子長度，如果之前已經遇到了個同樣長度的句子，那么后面的同樣長度的句子就不再考慮了，這是因為最先考慮的一定是得分最大的，后面打分的得分過小再考慮就沒有意義。

那么這個算法怎么恢復到BS呢？其實很簡單，只需要讓（4）經驗函數恒為0，讓比較運算符（1）為：

這個式子的意思是，讓那些要么長度更短要么長度相同且得分更大的句子優先被計算，這其實和BS是一致的。因為BS在每一步要么優先考慮已經結束的句子，要么長度相同但得分更大。

同時讓終止條件（2）為：

也就是說要讓所有句子都搜索完。

那么，怎么用這個算法實現最佳優先的A* Beam Search呢？回想一下，A*是優先探索得分較大的路徑，但是它并不限制路徑的長度，也就是說，如果已經探索了條長度為的路徑，如果后面需要，它還會繼續探索長度為的其他路徑。

所以它在最壞情況下仍然是的。將A*和BS結合起來，就是要在A*算法上限制可探索的路徑數，這就是上述算法的思想。

所以，最佳優先搜索就可以定義為：

• （1）比較運算符：

• （2）終止條件：

• （4）經驗函數：根據得分函數的設置（對數似然設置為0）

正如上面所述，這個算法的優勢在于，對于對數似然而言，一旦已經計算了長度為的個句子，那么后面任何長度小于的句子都不需要再考慮了，因為它們的得分在該長度上一定更低。

本文有一節專門證明了該結論，并證明了該算法的時間復雜度，由于內容較為復雜，有興趣的讀者可以參考原文Section 4。

下圖是從本算法可以導出的主要搜索算法，包括BS，最佳優先BS，A* 等算法?？梢钥吹?#xff0c;通過定義4個關鍵因子，我們可以實現各種典型的搜索算法，當然運用在文本生成上，BS、最佳BS和A* BS是我們最關心的。

實驗

空口無憑，且看實驗效果。本文在多個數據集上測量各搜索算法具體調用了多少次得分函數。注意到這里沒直接比較運行時間，原文認為運行時間和硬件關系很大。

下圖是在本文實驗的機器上，運行時間和得分函數調用次數的關系?？梢钥吹?#xff0c;二者有很強的線性相關性，所以直接比較得分函數是合理的。

下表是主要實驗結果。Beam Search (ES)是指使用了提前終止的BS。

從結果可以看到，相比BS和BS(ES)，BFBS調用得分函數的次數顯著降低，這在很大的時候尤其明顯。這也就意味著，模型花在解碼上的時候大大縮短。

下面一個問題是，BFBS真的可以取得BS的最后得到的句子嗎？如下表所見，shrinking和ES都不能完全得到BS的結果（），反而效果也會變差。

相反，BFBS始終能得到BS一樣的結果，只要BS能夠取得好效果，BFBS也就能取得同樣的效果。

上面的實驗都是基于對數似然這個得分函數而言，對于其他得分函數，如互信息、長度歸一化等，本文也都做了實驗，限于篇幅，在此不再展開，有興趣的讀者可以參考原文。

小結

這是一篇偏算法理論的應用文，提出了一種通用的Beam Search算法框架，采用不同的比較運算符、經驗函數、終止策略或Beam Size，算法可以復原很多常見的搜索算法。

基于這個算法框架，本文提出了一種新的，基于最佳優先策略的Beam Search，和BS相比，能夠顯著減少得分函數的調用次數，從而提高解碼速度。

當然，本文所提出的算法其實并不算簡單，在理解上也有諸多障礙，尤其是很多細節，如是否可以并行化解碼，優先隊列又該怎么在并行條件下實現等，都需要仔細推敲。原文Section3.1給出了實現的概述，讀者可以根據此自己嘗試實現一個版本。

????

現在，在「知乎」也能找到我們了

進入知乎首頁搜索「PaperWeekly」

點擊「關注」訂閱我們的專欄吧

關于PaperWeekly

PaperWeekly 是一個推薦、解讀、討論、報道人工智能前沿論文成果的學術平臺。如果你研究或從事 AI 領域，歡迎在公眾號后臺點擊「交流群」，小助手將把你帶入 PaperWeekly 的交流群里。

總結

以上是生活随笔為你收集整理的Beam Search还能更快？结合优先队列的最佳优先化Beam Search的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。