ビームサーチのソースを表示

[[計算機科学|コンピュータサイエンス]]分野において、'''ビームサーチ'''とは、枝刈りをしながら木・[[グラフ (データ構造)|グラフ]]を探索する[[ヒューリスティック]]な[[探索|探索アルゴリズム]]である。ビームサーチは、枝刈りを行うことで[[幅優先探索]]を省コスト化したもので、幅優先探索は全探索を行うが、ビームサーチでは事前に決めておいた数の候補から、最良のものを選ぶ。<ref>{{Cite web |url=http://foldoc.org/index.cgi?query=beam+search&action=Search |title=FOLDOC - Computing Dictionary |website=foldoc.org |accessdate=2016-04-11}}</ref>これは、[[貪欲法]]から候補数を広げた形ともいえる。

「ビームサーチ」という名前は、1977年に[[カーネギーメロン大学]]の[[ラジ・レディ]]によって付けられた。<ref>Reddy, D. Raj. "Speech Understanding Systems: A Summary of Results of the Five-Year Research Effort. Department of Computer Science.", 1977.</ref>

== 詳細 ==
ビームサーチでは、[[幅優先探索|幅優先]]探索を使用して[[木構造 (データ構造)|木構造]]を探索する。木の各レベルで、リストに保持してある現在のレベルのノードからたどれる次のレベルのノードを列挙して[[評価値]]順でソートする。<ref>{{Cite web |url=http://bradley.bradley.edu/~chris/searches.html |title=BRITISH MUSEUM SEARCH |website=bradley.bradley.edu |accessdate=2016-04-11}}</ref>この時、次のレベルのノードのリストには上位からあらかじめ決められた数 <math>\beta</math> 個（このサイズをビーム幅という）のノードしか保持しない。次のレベルでは、その絞り込んだ後ノードのリストからたどれるノードを処理する。

ビーム幅が大きいほど枝刈りされるノードは少なくなり、ビーム幅が無限大の場合、枝刈りされる状態は無く[[幅優先探索]]と同じになり、逆にビーム幅が 1 の場合は、[[貪欲法]]と同じになる。ビーム幅によって、探索の実行に必要なメモリが制限できる。目標ノードが枝刈りされる可能性があるため、ビームサーチは完全・最適ではない（解・最適解を見つけられずに終了する可能性がある）。<ref>{{Cite book|url=https://books.google.com/books?id=X4mhySvjqUAC|title=Paradigms of Artificial Intelligence Programming: Case Studies in Common LISP|last=Norvig|first=Peter|date=1992-01-01|publisher=Morgan Kaufmann|isbn=9781558601918|language=en}}</ref>

== 用途 ==
ビームサーチは、探索空間全体を格納するのにはメモリが足りない大規模な課題に対してよく使用される。<ref name="furcy">Furcy, David. Koenig, Sven. "Limited Discrepancy Beam Search". 2005. {{Cite web |url=http://www.ijcai.org/papers/0596.pdf |title=Archived copy |accessdate=2007-12-22 |archiveurl=https://web.archive.org/web/20080516202406/http://www.ijcai.org/papers/0596.pdf |archivedate=2008-05-16}}</ref>たとえば、多くの[[機械翻訳]]システムで使用されていた <ref>Tillmann, Christoph. Ney, Hermann. "Word Reordering and a Dynamic Programming Beam Search Algorithm for Statistical Machine Translation". {{Cite web |url=http://acl.ldc.upenn.edu/J/J03/J03-1005.pdf |title=Archived copy |accessdate=2007-12-22 |archiveurl=https://web.archive.org/web/20060618020933/http://acl.ldc.upenn.edu/J/J03/J03-1005.pdf |archivedate=2006-06-18}}</ref> （現在、最先端技術では、[[ニューラル機械翻訳]]ベースの方法が主に使用されている。）。最適な翻訳を選択するために、各部分についてさまざまな方法で単語を翻訳していく。文の構造に良くあった翻訳が保持され、残りは破棄する。次に、翻訳アルゴリズムは、与えられた基準に従って翻訳を評価し、目標を最もよく維持する翻訳を選択する。ビームサーチが初めて使われたのは、ハーピー音声認識システム、CMU1976だった。<ref>Lowerre, Bruce. "The Harpy Speech Recognition System", Ph.D. thesis, Carnegie Mellon University, 1976</ref>

== 派生 ==
[[完全性]]を実現する派生としては、深さ優先探索を組み合わせたビームスタックサーチ<ref>Zhou, Rong. Hansen, Eric. "Beam-Stack Search: Integrating Backtracking with Beam Search". 2005. http://www.aaai.org/Library/ICAPS/2005/icaps05-010.php</ref>''や深さ優先ビームサーチ<ref name="furcy">Furcy, David. Koenig, Sven. "Limited Discrepancy Beam Search". 2005. {{Cite web |url=http://www.ijcai.org/papers/0596.pdf |title=Archived copy |accessdate=2007-12-22 |archiveurl=https://web.archive.org/web/20080516202406/http://www.ijcai.org/papers/0596.pdf |archivedate=2008-05-16}}</ref>''や''、''不一致制限探索（limited discrepancy search）と組み合わせたの不一致バックトラック付き''ビームサーチ（BULB）''<ref>{{CiteSeerX|10.1.1.34.2426}}</ref>がある 。これらのアルゴリズムは{{仮リンク|Anytimeアルゴリズム|en|Anytime algorithm|label=Anytimeなアルゴリズム}}、つまり、短時間である程度良い解を見つけ、その後に段々と時間を使ってより良い解を見つけていくことで、途中で中断してもその探索時間に応じた良い解を見つけられるアルゴリズムである。

こういった完全性を実現できる・Anytimeな派生としては、狭いビーム幅で探索を行った後にビーム幅を段々と広げながら再探索を繰り返していく反復広化<ref>{{Cite web |url=https://www.aaai.org/Papers/AAAI/1998/AAAI98-060.pdf |title=Complete Anytime Beam Search |accessdate=2022/03/24 |publisher=AAAI |author=Weixiong Zhang}}</ref>や、探索木のレベルごとの優先度付きキューなどを保持しておくことで狭いビーム幅での探索結果を残したまま幅を広げていくchokudaiサーチ<ref>{{Cite web |url=https://www.slideshare.net/chokudai/chokudai-search-23234124 |title=Chokudai search |accessdate=2022/03/24 |publisher=Slideshare |author=高橋直大}}</ref>などもある。

[[局所探索法]]としては、ランダムに生成された <math>\beta</math> 個の状態を選んでから、探索木の各レベルで''新しい状態リストを'' <math>\beta</math> ''個まで枝刈りしながら、解が得られるまで現在の状態リストからの近傍の探索を繰り返していく手法をローカルビームサーチと呼ぶ。''<ref>{{Cite web |url=https://www.cs.unc.edu/~lazebnik/fall10/lec06_local_search.pdf |title=Local search algorithms |publisher=University of North Carolina at Chapel Hill, Department of Computer Science |page=15 |author=Svetlana Lazebnik |authorlink=Svetlana Lazebnik |archiveurl=https://web.archive.org/web/20110705070334/http://www.cs.unc.edu/~lazebnik/fall10/lec06_local_search.pdf |archivedate=2011-07-05|accessdate=2011-07-05}}</ref> <ref name="iitb">{{Cite web |url=https://www.cse.iitb.ac.in/~cs344/2011/slides/cs344-beam-search-2feb11.pptx |title=Beam Search |publisher=Indian Institute of Technology Bombay, Department of Computer Science and Engineering (CSE) |pages=39–40 |author=Pushpak Bhattacharyya |archiveurl=https://web.archive.org/web/20181121123057/https://www.cse.iitb.ac.in/~cs344/2011/slides/cs344-beam-search-2feb11.pptx |archivedate=2018-11-21|accessdate=2018-11-21}}</ref>

ローカルビームサーチは局所解で終わることが多いため、よく使われる解決策として次の <math>\beta</math> 個ノードを状態のヒューリスティック評価を使って、ランダム性を加えて選択することがある。この種の探索は、''確率的ビームサーチ''と呼ばれる。<ref>{{Cite web |url=http://www-users.cselabs.umn.edu/classes/Fall-2017/csci4511/slides/week4/9.28.17.pdf |title=Local Search |author=James Parker |page=17 |publisher=University of Minnesota |date=2017-09-28 |archiveurl=https://web.archive.org/web/20171013150401/http://www-users.cselabs.umn.edu/classes/Fall-2017/csci4511/slides/week4/9.28.17.pdf |archivedate=2017-10-13 |accessdate=2018-11-21}}</ref>

他の派生としては、''フレキシブルビームサーチ''と''リカバリービームサーチがある''。<ref name="iitb">{{Cite web |url=https://www.cse.iitb.ac.in/~cs344/2011/slides/cs344-beam-search-2feb11.pptx |title=Beam Search |publisher=Indian Institute of Technology Bombay, Department of Computer Science and Engineering (CSE) |pages=39–40 |author=Pushpak Bhattacharyya |archiveurl=https://web.archive.org/web/20181121123057/https://www.cse.iitb.ac.in/~cs344/2011/slides/cs344-beam-search-2feb11.pptx |archivedate=2018-11-21|accessdate=2018-11-21}}</ref>

== 出典 ==
{{Reflist}}

{{アルゴリズム}}
{{DEFAULTSORT:ひーむさーち}}
[[Category:検索アルゴリズム]]
[[Category:アルゴリズム]]
[[Category:組合せ最適化]]
[[Category:数学に関する記事]]