集束搜尋（Beam Search）

核心概念

集束搜尋是一種啟發式搜尋演算法，旨在解決序列生成任務中，貪婪演算法容易陷入局部最佳解的問題。與貪婪演算法每次只選擇當前最佳選項不同，集束搜尋在每個時間步保留 k 個最有可能的候選序列，其中 k 被稱為集束寬度（beam width）。

核心概念包括：

• 集束寬度 (Beam Width): k 值，決定了在每個時間步保留多少個候選序列。較大的 k 值意味著更廣泛的搜索空間，但也需要更多的計算資源。
• 候選序列 (Candidate Sequence): 在每個時間步，演算法維護的 k 個最有可能的序列。
• 分數 (Score): 每個候選序列都有一個分數，通常是該序列的對數概率。分數用於評估序列的優劣。
• 擴展 (Expansion): 在每個時間步，演算法會將每個候選序列擴展到所有可能的下一個詞，並計算每個新序列的分數。
• 修剪 (Pruning): 在擴展後，演算法會根據分數修剪序列，只保留 k 個最佳序列。

運作原理

集束搜尋的運作原理可以概括為以下步驟：

1. 初始化: 從一個空的序列開始，作為初始集束。
2. 迭代: 對於每個時間步，執行以下操作：
   • 擴展: 將集束中的每個序列擴展到所有可能的下一個詞。
   • 評分: 計算每個新序列的分數（通常是對數概率）。
   • 修剪: 根據分數，從所有新序列中選擇 k 個最佳序列，作為新的集束。
3. 終止: 當所有序列都達到終止符號或達到最大長度時，演算法終止。
4. 選擇最佳序列: 從最終的集束中選擇分數最高的序列作為最終輸出。

更詳細的步驟如下：

• Step 1: 初始化
  • 從一個起始符號（例如 <SOS>）開始，建立一個包含單一空序列的集束。這個序列的分數通常初始化為 0。
• Step 2: 迭代 (每個時間步 t)
  • 擴展: 對於集束中的每個序列，將其擴展到所有可能的下一個詞彙。這意味著對於每個序列，我們都會生成 |V| 個新序列，其中 |V| 是詞彙表的大小。
  • 評分: 使用模型（例如，序列到序列模型）計算每個新序列的條件概率。通常，我們使用對數概率，因為它可以避免數值下溢，並且將概率的乘法轉換為加法。序列的分數是其所有詞的對數概率之和。
  • 修剪: 從所有新生成的序列中，選擇分數最高的 k 個序列，作為新的集束。這個步驟是集束搜尋的核心，它允許演算法在探索多個可能性的同時，保持計算的可控性。
• Step 3: 終止
  • 當集束中的所有序列都以終止符號（例如 <EOS>）結束，或者達到預定義的最大長度時，演算法終止。
• Step 4: 選擇最佳序列
  • 從最終的集束中，選擇分數最高的序列作為最終的輸出。這個序列被認為是最有可能的序列。

數學表示:

假設我們有一個序列到序列模型，它將輸入序列 x = (x_1, x_2, ..., x_n) 映射到輸出序列 y = (y_1, y_2, ..., y_m)。集束搜尋的目標是找到最有可能的輸出序列 y*：

y* = argmax_y P(y | x)

在每個時間步 t，集束搜尋維護一個包含 k 個候選序列的集束 B_t。每個序列 y_{1:t} = (y_1, y_2, ..., y_t) 都有一個分數 S(y_{1:t})，通常是其對數概率：

S(y_{1:t}) = log P(y_{1:t} | x) = Σ_{i=1}^t log P(y_i | y_{1:i-1}, x)

在每個時間步，集束搜尋通過擴展集束中的每個序列，並選擇分數最高的 k 個序列來更新集束。

實際應用

集束搜尋廣泛應用於各種序列生成任務中，包括：

• 機器翻譯: 將一種語言的文本翻譯成另一種語言。
• 文本摘要: 將長文本壓縮成簡短的摘要。
• 語音辨識: 將語音信號轉換成文本。
• 圖像字幕: 為圖像生成描述性文本。
• 程式碼生成: 從自然語言描述生成程式碼。
• 對話系統: 生成對話回應。

在這些應用中，集束搜尋通常與序列到序列模型（例如，Transformer）結合使用，以生成高品質的輸出序列。

具體案例：機器翻譯

在機器翻譯中，集束搜尋用於生成目標語言的翻譯。給定一個源語言句子，集束搜尋會探索多個可能的目標語言翻譯，並選擇最有可能的翻譯。集束寬度 k 的選擇會影響翻譯的質量和計算成本。較大的 k 值通常會產生更好的翻譯，但需要更多的計算資源。

常見誤區

• 集束搜尋一定能找到最佳解嗎？
  • 不一定。集束搜尋是一種啟發式演算法，它不能保證找到全局最佳解。由於它只保留 k 個候選序列，因此可能會錯過一些更優的序列。
• 集束寬度越大越好嗎？
  • 不一定。雖然較大的集束寬度可以探索更廣泛的搜索空間，但也會增加計算成本。此外，隨著集束寬度的增加，收益遞減效應也會出現，即增加集束寬度所帶來的性能提升會越來越小。通常需要根據具體任務和計算資源來選擇合適的集束寬度。
• 集束搜尋和貪婪演算法有什麼區別？
  • 貪婪演算法在每個時間步只選擇當前最佳選項，而集束搜尋則保留 k 個最佳選項。因此，集束搜尋可以探索更多的可能性，並降低陷入局部最佳解的風險。然而，集束搜尋的計算成本也比貪婪演算法更高。
• 集束搜尋是否適用於所有序列生成任務？
  • 集束搜尋通常適用於需要生成高品質序列的任務。對於一些對延遲要求較高的任務，例如實時語音辨識，貪婪演算法可能更適合。

總之，集束搜尋是一種強大的序列生成演算法，它通過在每個時間步保留多個候選序列來探索更廣泛的搜索空間，並降低陷入局部最佳解的風險。然而，它也需要更多的計算資源，並且不能保證找到全局最佳解。在實際應用中，需要根據具體任務和計算資源來選擇合適的集束寬度。