Loading article…
コンピュータサイエンスにおいて、ビーム探索は、限られたセットの中で最も有望なノードを拡張することでグラフを探索するヒューリスティックな 探索アルゴリズムです。ビーム探索は、メモリ要件を削減したベストファースト探索の修正版です。ベストファースト探索は、すべての部分解（状態）を何らかのヒューリスティックに従って順序付けるグラフ探索です。しかし、ビーム探索では、事前に決定された数の最良部分解のみが候補として保持されます。[1]したがって、これは貪欲アルゴリズムです。
詳細
ビーム探索では、幅優先探索を使用して探索木を構築します。木の各レベルで、現在のレベルの状態のすべての後継状態を生成し、ヒューリスティックコストの昇順でソートします。[2]ただし、各レベルでは、事前に決定された数の最良の状態のみが格納されます (ビーム幅と呼ばれます)。次に、それらの状態のみが拡張されます。ビーム幅が大きいほど、剪定される状態は少なくなります。ビーム幅が無限大の場合、状態は剪定されず、ビーム探索は最良優先探索と同じです。[3]逆に、ビーム幅 1 は山登りアルゴリズムに対応します。[3]ビーム幅は、探索を実行するために必要なメモリを制限します。目標状態が剪定される可能性があるため、ビーム探索では完全性 (アルゴリズムがソリューションが存在する場合に、そのソリューションで終了するという保証) が犠牲になります。ビーム探索は最適ではありません (つまり、最良のソリューションが見つかる保証はありません)。
用途
ビーム探索は、検索ツリー全体を格納するメモリが不十分な大規模システムで扱いやすさを維持するために最もよく使用されます。[4]たとえば、多くの機械翻訳システムで使用されています。[5] (現在、最先端の技術では、主にニューラル機械翻訳ベースの方法、特に大規模言語モデルが使用されています) 最適な翻訳を選択するために、各部分が処理され、単語を翻訳するさまざまな方法が表示されます。文の構造に従って最も優れた翻訳が保持され、残りは破棄されます。次に、翻訳者は指定された基準に従って翻訳を評価し、目標を最もよく維持する翻訳を選択します。
歴史
Harpy音声認識システム（1976年の論文[6]で紹介）は、後にビームサーチとして知られるようになる手法を初めて採用したシステムでした。[7] この手法は当初「探索の軌跡モデル」と呼ばれていましたが、「ビームサーチ」という用語は1977年にはすでに使用されていました。[8]
バリエーション
ビーム探索は深さ優先探索と組み合わせることで完成し、ビームスタック探索[9]と深さ優先ビーム探索[ 4 ]が実現しました。また、限定不一致探索[4]と組み合わせることで、限定不一致バックトラッキングを使用したビーム探索[4] (BULB)が実現しました。結果として得られる探索アルゴリズムは、ビーム探索のように、適切だがおそらく最適ではない解を迅速に見つけ、その後バックトラックして、最適解に収束するまで改善された解を探し続ける、いつ でも実行できるアルゴリズムです。
局所探索の文脈では、ランダムに生成された状態を選択し、探索木の各レベルにおいて、目標に到達するまで、現在の状態のすべての可能な後続状態の中から常に新しい状態を検討する特定のアルゴリズムを局所ビーム探索と呼びます。[10] [11]
局所ビーム探索は局所的最大値に到達することが多いため、一般的な解決策は状態のヒューリスティック評価に依存する確率で次の状態をランダムに選択することです。この種の探索は確率的ビーム探索と呼ばれます。[12]
他のバリエーションとしてはフレキシブルビームサーチとリカバリービームサーチがある。[11]
参考文献
- ^ 「ビームサーチ」。無料のオンラインコンピューティング辞書。 2024年3月27日閲覧。
- ^ 「BRITISH MUSEUM SEARCH」bradley.bradley.edu . 2016年4月11日閲覧。
- ^ ab Norvig, Peter (1992). 人工知能プログラミングのパラダイム: Common LISP のケーススタディ。Morgan Kaufmann。p. 196。ISBN 9781558601918。
- ^ abcd Furcy, D.; Koenig, S. (2005). 「限定不一致ビーム探索」。人工知能に関する第 19 回国際合同会議議事録。Morgan Kaufmann。pp. 125–131。
- ^ Tillmann, C.; Ney, H. (2003). 「統計的機械翻訳のための単語の並べ替えと動的計画法ビーム探索アルゴリズム」.計算言語学. 29 (1): 97–133. doi : 10.1162/089120103321337458 . S2CID 7829066.
- ^ Lowerre, Bruce T. (1976). Harpy 音声認識システム(PDF) (PhD). カーネギーメロン大学.
- ^ Ow, Peng Si; Morton, Thomas E. (1988). 「スケジューリングにおけるフィルタービームサーチ†」International Journal of Production Research . 26 (1): 35–62. doi :10.1080/00207548808947840. ISSN 0020-7543.
- ^ 国防技術情報センター (1977-08-01)。DTIC ADA049288: 音声理解システム。カーネギーメロン大学における 5 年間の研究成果の概要。p. 6。
- ^ Zhou, Rong; Hansen, Eric (2005). 「ビームスタック検索: バックトラッキングとビーム検索の統合」ICAPS . pp. 90–98. 2021-04-20時点のオリジナルよりアーカイブ。2011-04-09に取得。
- ^ Svetlana Lazebnik . 「ローカル検索アルゴリズム」(PDF)。ノースカロライナ大学チャペルヒル校、コンピュータサイエンス学部。p. 15。2011-07-05 のオリジナル(PDF)からアーカイブ。
- ^ ab Pushpak Bhattacharyya. 「ビームサーチ」。インド工科大学ボンベイ校、コンピュータサイエンスおよびエンジニアリング学部 (CSE)。pp. 39–40。2018年11月21日時点のオリジナルよりアーカイブ。
- ^ James Parker (2017-09-28). 「Local Search」（PDF）。ミネソタ大学。p. 17。2017-10-13時点のオリジナルよりアーカイブ（PDF）。2018-11-21閲覧。