Content deleted Content added
Mention LLMs as state of art for translation where beam search is often applied. |
m Open access bot: url-access updated in citation with #oabot. |
||
| (12 intermediate revisions by 6 users not shown) | |||
Line 1:
{{short description|Heuristic search algorithm}}
[[File:Beam search.gif|thumb|Beam search with width 3 (animation)]]
In [[computer science]], '''beam search''' is a [[heuristic (computer science)|heuristic]] [[search algorithm]] that explores a graph by expanding the most promising node in a limited set. Beam search is
The term "beam search" was coined by [[Raj Reddy]] of [[Carnegie Mellon University]] in 1977.<ref>{{Cite book |last=Defense Technical Information Center |url=http://archive.org/details/DTIC_ADA049288 |title=DTIC ADA049288: Speech Understanding Systems. Summary of Results of the Five-Year Research Effort at Carnegie-Mellon University |date=1977-08-01 |language=english}}</ref>▼
== Details ==
Beam search uses [[breadth-first search]] to build its [[Tree traversal|search tree]]. At each level of the tree, it generates all successors of the states at the current level, sorting them in increasing order of heuristic cost.<ref>{{Cite web|url=http://bradley.bradley.edu/~chris/searches.html|title=BRITISH MUSEUM SEARCH|website=bradley.bradley.edu|access-date=2016-04-11}}</ref> However, it only stores a predetermined number, <math>\beta</math>, of best states at each level (called the beam width). Only those states are expanded next. The greater the beam width, the fewer states are pruned. With an infinite beam width, no states are pruned and beam search is identical to [[
== Uses ==
A beam search is most often used to maintain tractability in large systems with insufficient amount of memory to store the entire search tree.<ref name="furcy"/> For example, it has been used in many [[machine translation]] systems.<ref>{{cite journal |last1=Tillmann |first1=C. |last2=Ney |first2=H. |title=Word reordering and a dynamic programming beam search algorithm for statistical machine translation |journal=Computational Linguistics |volume=29 |issue=1 |pages=97–133 |date=2003 |doi= 10.1162/089120103321337458|s2cid=7829066 |url=https://direct.mit.edu/coli/article-abstract/29/1/97/1794|doi-access=free }}</ref> (The state of the art now primarily uses [[neural machine translation]] based methods, especially [[large language models]].) To select the best translation, each part is processed, and many different ways of translating the words appear. The top best translations according to their sentence structures are kept, and the rest are discarded. The translator then evaluates the translations according to a given criterion, choosing the translation which best keeps the goals.
= The Harpy Speech Recognition System (introduced in a 1976 dissertation<ref>{{cite thesis |last=Lowerre |first=Bruce T. |title=The Harpy Speech Recognition System |type=PhD |publisher=Carnegie Mellon University |date=1976 |url=https://stacks.stanford.edu/file/druid:rq916rn6924/rq916rn6924.pdf}}</ref>) was the first use of what would become known as beam search.<ref>{{Cite journal |last1=Ow |first1=Peng Si |last2=Morton |first2=Thomas E. |date=1988 |title=Filtered beam search in scheduling† |url=http://www.tandfonline.com/doi/abs/10.1080/00207548808947840 |journal=International Journal of Production Research |language=en |volume=26 |issue=1 |pages=35–62 |doi=10.1080/00207548808947840 |issn=0020-7543|url-access=subscription }}</ref>
▲
== Variants ==
Beam search has been made [[Completeness (logic)|complete]] by combining it with [[depth-first search]], resulting in ''[[beam stack search]]''<ref>{{cite book |last1=Zhou |first1=Rong |last2=Hansen |first2=Eric |chapter=Beam-Stack Search: Integrating Backtracking with Beam Search |date=2005 |chapter-url=http://www.aaai.org/Library/ICAPS/2005/icaps05-010.php |title=ICAPS |pages=90–98 |access-date=2011-04-09 |archive-date=2021-04-20 |archive-url=https://web.archive.org/web/20210420205518/http://www.aaai.org/Library/ICAPS/2005/icaps05-010.php |url-status=dead }}</ref> and ''depth-first beam search'',<ref name="furcy" /> and with limited discrepancy search,<ref name=furcy>{{cite book |last1=Furcy |first1=D. |last2=Koenig |first2=S. |chapter=Limited discrepancy beam search |chapter-url=https://dl.acm.org/doi/abs/10.5555/1642293.1642313 |editor= |title=Proceedings of the 19th international joint conference on Artificial intelligence |publisher=Morgan Kaufmann |___location= |date=2005 |isbn= |pages=125–131 |url=}}</ref> resulting in ''beam search using limited discrepancy backtracking''<ref name="furcy" /> (BULB). The resulting search algorithms are [[anytime algorithm]]s that find good but likely sub-optimal solutions quickly, like beam search, then backtrack and continue to find improved solutions until convergence to an optimal solution.
In the context of a [[Local search (optimization)|local search]], we call ''local beam search'' a specific algorithm that begins selecting <math>\beta</math> randomly generated states and then, for each level of the search tree, it always considers <math>\beta</math> new states among all the possible successors of the current ones, until it reaches a goal.<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|author-link= Svetlana Lazebnik |archive-url=https://web.archive.org/web/20110705070334/http://www.cs.unc.edu/~lazebnik/fall10/lec06_local_search.pdf|archive-date=2011-07-05
Since local beam search often ends up on local maxima, a common solution is to choose the next <math>\beta</math> states in a random way, with a probability dependent from the heuristic evaluation of the states. This kind of search is called ''stochastic beam search''.<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|archive-url=https://web.archive.org/web/20171013150401/http://www-users.cselabs.umn.edu/classes/Fall-2017/csci4511/slides/week4/9.28.17.pdf|archive-date=2017-10-13|url-status=live|access-date=2018-11-21}}</ref>
| |||