ビーム探索（ビームたんさく）は、コンピュータ科学において、限られた集合内で最も有望なノードを展開しながらグラフを探索するために用いられるヒューリスティック探索アルゴリズムである。これは、最良優先探索の変種であり、保持する最良の部分解の数をあらかじめ決めておくことでメモリ要件を削減し、貪欲アルゴリズムとして機能する。このアルゴリズムは、機械翻訳や音声認識などのシーケンス復号タスクで広く応用されており、出力品質と計算の実用性のバランスを取る。
ビーム探索の核心的な考え方は、ビームと呼ばれる最も有望な部分解の集合を維持し、各ステップでそれらのみを展開することである。このアプローチは、すべての可能な経路を考慮する全探索手法とは対照的であり、探索空間が大きい場合には全探索は計算上不可能となり得る。有望でない候補を刈り込むことで、ビーム探索は効率を達成する一方で、完全性と最適性の保証を犠牲にする。
アルゴリズムの詳細
ビーム探索は、幅優先探索の戦略を用いて探索木を構築する。木の各レベルにおいて、現在のレベルの状態のすべての後続状態を生成し、それらをヒューリスティックコストの昇順に並べ替える。しかし、各レベルで保持する状態の数は、ビーム幅と呼ばれるあらかじめ決められた数βのみであり、それ以外の状態は破棄される。次に展開されるのは、保持された状態のみである。
ビーム幅βは、探索品質とリソース使用量のトレードオフを制御する重要なパラメータである。ビーム幅を大きくすると、より多くの状態が保持され、刈り込まれる候補が減るため、解の品質が向上する可能性があるが、メモリと計算の要件も増加する。ビーム幅が無限大の場合、刈り込みは行われず、ビーム探索は最良優先探索と同一になる。逆に、ビーム幅が1の場合、ビーム探索は、各ステップで単一の最良経路のみを貪欲に追従する山登りアルゴリズムに対応する。
ビーム幅は、探索に必要なメモリ量を制限する。このため、メモリが限られた大規模なシステムでの使用に適している。しかし、目標状態が刈り込まれる可能性があるため、ビーム探索は完全性を欠く。つまり、解が存在する場合でも、その解を見つけられる保証はない。さらに、ビーム探索は最適性も保証しない。つまり、見つかった解が最良の解であるとは限らない。
歴史的発展
ビーム探索として知られるようになった手法の最初の使用は、1976年の博士論文で紹介されたHarpy音声認識システムである。このシステムでは、この手順は当初「locus model of search」と呼ばれていたが、1977年までには「ビーム探索」という用語がすでに使用されていた。Harpyシステムは、カーネギーメロン大学で開発され、音声認識技術における重要な進歩を示し、実世界の応用におけるヒューリスティック探索の実用的な有用性を実証した。
ビーム探索の発展は、1970年代における、複雑な問題に対して効率的な探索アルゴリズムを求めるより広範な傾向の一部であった。研究者たちは、複雑な問題に対して全探索が非現実的であることを認識し、良い解を迅速に見つけることができるヒューリスティックなアプローチの開発に取り組んだ。Harpyシステムの成功は、この分野における基本的な手法としてビーム探索を確立するのに貢献した。
機械翻訳への応用
ビーム探索は、機械翻訳システムにおいて最も顕著に使用されている。そこでは、多数の可能な翻訳候補の中から最良の翻訳を選択するのに役立つ。従来の統計的機械翻訳では、文の各部分が処理され、単語の翻訳方法には多くの異なる方法がある。ビーム探索は、文の構造に基づいて最良の翻訳候補を上位に保持し、それ以外を破棄し、その後、残った候補を所定の基準に基づいて評価し、目標を最もよく満たすものを選択する。
現代のニューラル機械翻訳では、主に大規模言語モデルとトランスフォーマーアーキテクチャを使用しており、ビーム探索は主要な復号戦略であり続けている。生成中、モデルは各ステップで可能な次のトークンに対する確率分布を生成する。ビーム探索は、複数の部分的なシーケンスを維持し、それらの累積確率に基づいて最も有望なものを展開する。このアプローチは、各ステップで最も可能性の高い単一のトークンのみを選択する貪欲復号よりも高品質な翻訳を生成する。
機械翻訳におけるビーム探索の応用は広範に研究されており、研究者たちは性能を向上させるための様々な修正を探求している。例えば、より短いシーケンスへの偏りを避けるために長さ正規化が適用されることが多く、また、候補シーケンス間の多様性を高めるための多様なビーム探索技術も開発されている。
変種と拡張
ビーム探索には、その限界、特に完全性と最適性の欠如に対処するためのいくつかの変種と拡張が開発されている。一つのアプローチは、ビーム探索と深さ優先探索を組み合わせたもので、ビームスタック探索や深さ優先ビーム探索などのアルゴリズムが生まれた。これらのアルゴリズムは、いつでも良いが最適ではない可能性のある解を迅速に見つけることができる anytime アルゴリズムであり、その後、計算時間が許す限り探索を続けて、最適解への収束を目指して解を改善する。
もう一つの変種は、限定不一致ビーム探索（BULB）であり、ビーム探索と限定不一致探索を組み合わせたものである。このアプローチも anytime アルゴリズムを生成し、時間の経過とともに解を改善することができる。局所探索の文脈では、局所ビーム探索は、β個のランダムに生成された状態から開始し、各ステップで、現在の状態のすべての後続状態を考慮し、その中からヒューリスティック評価に基づいて最良のβ個を選択する。このプロセスは、目標状態に到達するまで、または終了条件が満たされるまで続けられる。
局所ビーム探索は、しばしば局所最大値で終了するという問題がある。これに対する一般的な解決策は、確率的ビーム探索であり、各ステップで次の状態を選択する際に、ヒューリスティック評価に依存した確率を用いてランダムに選択する。その他の変種には、ビーム幅を動的に調整する柔軟なビーム探索や、貧弱な刈り込み決定から回復することを可能にする回復ビーム探索などがある。
現代のAIシステムにおける役割
ビーム探索は、現代の人工知能システム、特に生成AIアプリケーションにおいて重要な役割を果たしている。深層学習モデル、特にトランスフォーマーアーキテクチャに基づくものでは、ビーム探索は推論中にテキスト、コード、音声などのシーケンスを生成するために使用される。OpenAI、Anthropic、Google DeepMindなどの企業は、言語モデルにおいてビーム探索を採用し、一貫性があり文脈に適した出力を生成している。
この技術は、画像キャプション生成、音声認識、タンパク質構造予測など、他のシーケンス生成タスクでも使用されている。これらの応用において、ビーム探索は、生成される出力の品質と、必要な計算リソースのバランスを取るのに役立つ。ビーム幅は、タスクの特定の要件に基づいて調整でき、ビーム幅を大きくすると品質が向上する可能性があるが、計算コストも増加する。
理論的特性
ビーム探索の理論的特性は、ヒューリスティック探索の文脈で分析されている。貪欲アルゴリズムとして、ビーム探索は各ステップで局所的に最適な選択を行うが、これは大域的に最適な解につながらない可能性がある。アルゴリズムの性能は、状態を評価するために使用されるヒューリスティック関数の品質に大きく依存する。適切に設計されたヒューリスティックは、探索を良い解へと導くことができるが、貧弱なヒューリスティックは、アルゴリズムが最適な経路を見逃す原因となる可能性がある。
ビーム幅と解の品質の間のトレードオフは、実用的な応用における中心的な考慮事項である。研究により、ビーム幅を増加させると一般的に解の品質は向上するが、収穫逓減が生じることが示されている。場合によっては、ビーム幅が大きすぎると、過剰生成と計算コストの増加を引き起こし、品質の大幅な向上なしに終わることがある。逆に、ビーム幅が小さすぎると、過度の刈り込みにより貧弱な解しか得られない可能性がある。
計算上の考慮事項
ビーム探索の計算複雑性は、主にビーム幅と探索空間の分岐因子によって決定される。各レベルで、アルゴリズムはビーム内のすべての状態の後続状態を生成する。これはβ × b個の後続状態を生成することを意味し、ここでbは分岐因子である。その後、これらの後続状態を並べ替える必要があり、これには追加の因子log(β × b)がかかる。したがって、全体的な複雑性はO(β × b × L × log(β × b))であり、ここでLは探索の最大深さである。
メモリ使用量はビーム幅によって制限され、各レベルでβ個の状態のみが保持される。このため、ビーム探索は、メモリが限られたアプリケーション、例えば組み込みシステムやリアルタイム処理において特に魅力的である。メモリ使用量と解の品質のバランスを取るアルゴリズムの能力は、学術研究と産業応用の両方において、その永続的な人気に貢献している。
他の探索手法との比較
ビーム探索は、貪欲探索、最良優先探索、機械学習ベースの復号手法など、他の探索アルゴリズムとしばしば比較される。貪欲探索はビーム幅が1のビーム探索に対応し、計算効率は高いが、多くの場合、品質の低い結果を生成する。最良優先探索は、すべての部分解を考慮するため、最適な解を見つけることができるが、探索空間全体に比例するメモリを必要とする。
ニューラルシーケンス生成の文脈では、ビーム探索は、確率分布に基づいてトークンをランダムに選択するサンプリングベースの手法と対比されることがある。サンプリングはより多様な出力を生成できるが、一貫性を犠牲にする可能性がある。一方、ビーム探索は、より決定的で高品質な結果を生成する傾向がある。最近の研究では、ビーム探索とサンプリングを組み合わせて、品質と多様性のバランスを取るハイブリッドアプローチが探求されている。
将来の方向性
2020年代初頭の時点で、ビーム探索は、特に大規模言語モデルの文脈において、活発な研究分野であり続けている。研究者たちは、モデルの予測の信頼度に基づいてビーム幅を調整する適応的ビーム幅戦略や、ビーム探索プロセスに外部制約を組み込む方法を探求している。NVIDIAやAMDなどの企業による専用AIアクセラレータなど、より効率的なハードウェアの開発により、リアルタイムアプリケーションにおいて、より大きなビーム幅とより複雑な探索戦略が可能になっている。
ビーム探索と、強化学習やニューラルネットワークなどの他のAI技術との統合も、進行中の研究分野である。これらの取り組みは、自然言語処理から科学的発見に至るまで、幅広いアプリケーションにおけるシーケンス生成の効率と有効性を向上させることを目的としている。