Beam Search 演算法概述
定義與用途
Beam Search 是一種啟發式搜尋演算法，廣泛應用於自然語言處理（NLP）、語音辨識、機器翻譯等序列產生任務。它在搜尋樹的每一層只保留前 k 個最有希望的節點（k 稱為 beam width），進而在可接受的運算資源下找到高品質的結果。
運作機制
- 初始化
從起始節點開始，將所有候選結果展開，計算每個候選的概率或評分。 - 節點擴展
在每一步，僅對目前保留的 top k（beam width）候選進行擴展。例如：當 beam width 設為 2 時，每次只保留 2 條最高分支繼續擴展。 - 候選選擇
根據當前已知的分數（如概率累積值）排名，選出分數最高的 k 個序列，其餘全數剪枝不再追蹤。 - 重複擴展
不斷重複上述步驟，直到所有候選都到達結束條件（如產生結束符號、達到最大長度等）。 - 輸出結果
從最後保留的序列中挑選累積評分最高的作為最終輸出。
優缺點
優點：
- 大幅減少記憶體與時間消耗，相較於暴力搜尋。
- 能兼顧效能與結果品質，比單純 greedy search 更能取得較佳解答。
- 可擴展性強，適合用於大型輸出空間。
- 最佳解可能被剪枝而遺失，無法保證尋得全球最佳解（非最佳且不完全）。
- 結果優劣受 beam width 影響，beam width 過小易丟失好路徑、過大則資源消耗提升。
應用範例
- 機器翻譯與摘要：協助生成譯文或精簡文本時，輸出更佳連貫且準確序列。
- 語音辨識：根據音訊，尋找最有可能的字詞序列組合。
- 聊天機器人產生回應：從多個潛在答案中，選出語意連貫度最高者。
參考說明
Beam Search 成為現代 NLP 及生成式 AI 過程中最常用的解碼技術之一，尤其在 Transformer 等 encoder-decoder 架構模型中廣泛使用，用來在推理階段取得品質最優化的輸出。
