Beam search: Difference between revisions

Revision as of 20:07, 6 December 2023

Revision as of 18:51, 31 January 2024

Line 10:

== 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 first use of a beam search was in the Harpy Speech Recognition System, CMU 1976.<ref>{{cite thesis |last=Lowerre |first=Bruce T. |title=The Harpy Speech Recognition System |type=PhD |publisher=Carnegie Mellon University |date=1976 |url=https://cmu.primo.exlibrisgroup.com/permalink/01CMU_INST/1feg4j8/alma991010499929704436}}</ref>

== Variants ==