Beam search is a heuristic search algorithm that is an optimization of best-first search that reduces its memory requirement. Best-first search is a graph search which orders all partial solutions (states) according to some heuristic which attempts to predict how close a partial solution is to a complete solution (goal state).[1] In beam search, only a predetermined number of best partial solutions are kept as candidates.[2]
Beam search uses breadth-first search to build its search tree. At each level of the tree, it generates all successors of the states at the current level, sorting them in order of increasing heuristic values.[3] However, it only stores a predetermined number of states at each level (called the beam width). The smaller the beam width, the more states are pruned. Therefore, with an infinite beam width, no states are pruned and beam search is identical to breadth-first search. The beam width bounds the memory required to perform the search, at the expense of risking completeness (possibility that it will not terminate) and optimality (possibility that it will not find the best solution). The reason for this risk is that the goal state could potentially be pruned.
The beam width can either be fixed or variable. In a fixed beam width, a maximum number of successor states is kept. In a variable beam width, a threshold is set around the current best state. All states that fall outside this threshold are discarded. Thus, in places where the best path is obvious, a minimal number of states is searched. In places where the best path is ambiguous, many paths will be searched.
Contents |
Name
The term "beam search" was coined by Raj Reddy, Carnegie Mellon University, 1976.
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.[4] For example, it is used in many machine translation systems.[5] 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 criteria, choosing the translation which best keeps the goals. The first use of a beam search was in the Harpy Speech Recognition System, CMU 1976.[6]
Extensions
Beam search has been made complete by combining it with depth-first search, resulting in Beam Stack Search[7] and Depth-First Beam Search[4], and limited discrepancy search, resulting in Beam Search Using Limited Discrepancy Backtracking[4] (BULB). The resulting search algorithms are anytime algorithms 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.
References
- ^ Xu, Yuehua. Fern, Alan. "On Learning Linear Ranking Functions for Beam Search". http://www.machinelearning.org/proceedings/icml2007/papers/168.pdf
- ^ beam search from FOLDOC
- ^ British Museum Search
- ^ a b c Furcy, David. Koenig, Sven. "Limited Discrepancy Beam Search". 2005. http://www.ijcai.org/papers/0596.pdf
- ^ Tillmann, Christoph. Ney, Hermann. "Word Reordering and a Dynamic Programming Beam Search Algorithm for Statistical Machine Translation". http://acl.ldc.upenn.edu/J/J03/J03-1005.pdf
- ^ Lowerre, Bruce. "The Harpy Speech Recognition System", Ph.D. thesis, Carnegie Mellon University, 1976
- ^ Zhou, Rong. Hansen, Eric. "Beam-Stack Search: Integrating Backtracking with Beam Search". 2005. http://www.cse.msstate.edu/~hansen/papers/icaps05beam.pdf
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
