Difference between revisions of "Beam Search"
| Line 1: | Line 1: | ||
| − | Beam a heuristic search [[Category::method]]. It used for decoding in many areas including | + | Beam search is a heuristic search [[Category::method]]. It used for decoding in many areas including [[Machine Translation]] and speech recognition. |
== Basic Algorithm == | == Basic Algorithm == | ||
| Line 26: | Line 26: | ||
''EXPAND_STATES'' expands the current states, adding them to their respective stacks. How the states are organized into the stacks is implementation dependent. When NEXT is called, it returns the states in the next stack. | ''EXPAND_STATES'' expands the current states, adding them to their respective stacks. How the states are organized into the stacks is implementation dependent. When NEXT is called, it returns the states in the next stack. | ||
| − | This type of decoder (also called a stack-based decoder) was invented by Fred Jelinek [Jelinek, 1969], and applied to speech recognition in the early 1970's [Jelinek et. al, 1975]. | + | This type of decoder (also called a stack-based decoder) was invented by Fred Jelinek [Jelinek, 1969], and applied to speech recognition in the early 1970's [Jelinek et. al, 1975]. It is also widely used in machine translation. |
Revision as of 01:57, 2 November 2011
Beam search is a heuristic search method. It used for decoding in many areas including Machine Translation and speech recognition.
Basic Algorithm
The pseudocode for beam search is:
- Start: CURRENT.STATES := initial.state
- while(not CONTAINS_GOAL(CURRENT.STATES)) do
- CANDIDATE.STATES := NEXT(CURRENT.STATES)
- SCORE(CANDIDATE.STATES)
- CURRENT.STATES := PRUNE(CANDIDATE.STATES)
CONTAINS_GOAL is a function that determines whether the goal state has been reached. SCORE uses a heuristic function to score states. PRUNE selects the best states to keep.
Stack-Based Beam Search
The candidate states are often organized into stacks. (This is a poor use of the word "stack", it is really just a list.) The pseudocode for this variant of beam search is:
- Start: CURRENT.STATES := initial.state, STACKS := empty
- while(not CONTAINS_GOAL(CURRENT.STATES)) do
- EXPAND_STATES(CURRENT.STATES, STACKS)
- CANDIDATE.STATES := NEXT(STACKS)
- SCORE(CANDIDATE.STATES)
- CURRENT.STATES := PRUNE(CANDIDATE.STATES)
EXPAND_STATES expands the current states, adding them to their respective stacks. How the states are organized into the stacks is implementation dependent. When NEXT is called, it returns the states in the next stack.
This type of decoder (also called a stack-based decoder) was invented by Fred Jelinek [Jelinek, 1969], and applied to speech recognition in the early 1970's [Jelinek et. al, 1975]. It is also widely used in machine translation.
