Difference between revisions of "Beam Search"
| Line 14: | Line 14: | ||
== Stack-Based Beam Search == | == 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 | + | 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 | :Start: CURRENT.STATES := initial.state, STACKS := empty | ||
| Line 20: | Line 20: | ||
:while(not ''CONTAINS_GOAL(''CURRENT.STATES)) do | :while(not ''CONTAINS_GOAL(''CURRENT.STATES)) do | ||
::''EXPAND_STATES(''CURRENT.STATES, STACKS) | ::''EXPAND_STATES(''CURRENT.STATES, STACKS) | ||
| − | ::CANDIDATE.STATES := ''NEXT('' | + | ::CANDIDATE.STATES := ''NEXT(''STACKS) |
::''SCORE(''CANDIDATE.STATES'')'' | ::''SCORE(''CANDIDATE.STATES'')'' | ||
::CURRENT.STATES := ''PRUNE(''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]. | |
Revision as of 01:52, 2 November 2011
Beam a heuristic search method. It used for decoding in many areas including in 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].
