Difference between revisions of "Beam Search"
| (3 intermediate revisions by the same user not shown) | |||
| 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. |
| − | == Algorithm == | + | == Basic Algorithm == |
The pseudocode for beam search is: | 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. | |
| − | |||
| − | |||
| − | |||
| − | ''CONTAINS_GOAL'' | + | == 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. | ||
| + | |||
| + | == Comments == | ||
| + | Beam search's ability to search seemly impossibly large search spaces in fractions of a second are a testiment to its usefullness. | ||
Latest revision as of 02:06, 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.
Comments
Beam search's ability to search seemly impossibly large search spaces in fractions of a second are a testiment to its usefullness.
