ビームサーチ【beam search】

ビームサーチとは？

人工知能や自然言語処理の分野で用いられる探索アルゴリズムの一種で、各ステップで有望な候補を一定数に絞り込みながら段階的に解を探す手法。

コンピュータで問題を解く過程では、ステップを重ねるごとに選択肢が枝分かれして膨大な数になる。文章生成を例にすると、各ステップで選べる単語が数十種類あれば、数ステップ先には天文学的な候補が生まれる。

これを片っ端からすべて調べる「全探索」は計算量が爆発的に増大し、選択肢やステップ数が極少ない場合以外は現実的な時間では処理できない。一方、各ステップで最善の一択だけを選び続ける「貪欲法」は高速だが、後の文脈と整合しない結果になりやすい。ビームサーチはこの両者の中間にあたる手法と考えることができる。

ビームサーチでは、各ステップで確率やスコアをもとに候補を評価し、上位の一定数だけを残して次のステップへ引き継ぐ。この「保持する候補の数」を「ビーム幅」（beam width）と呼ぶ。ビーム幅が「5」であれば、常に上位5つの候補を並行して追い続ける。冒頭では評価が低かった単語でも、数語先まで考慮すると全体として自然な表現になる場合があり、貪欲法では見落としがちなそうした候補を拾い上げられる。

ビーム幅の設定は精度と計算コストのバランスに直結する。幅を大きくすれば見落としは減るが、メモリ使用量と処理時間が増加する。幅を「1」にすると貪欲法と同等になる。加えて、候補を評価する評価関数の設計も結果に大きく影響し、適切な指標を選ばなければ探索が偏り、望ましくない出力につながることもある。

ビームサーチは機械翻訳や音声認識、大規模言語モデル（LLM）によるテキスト生成など、逐次的に候補を展開していく処理で活用されている。最適解を必ず保証するわけではないが、限られた計算資源の中で十分に質の高い解を素早く得られる実用的なアルゴリズムとして知られている。