Difference between revisions of "Beam Search"
From Cohen Courses
Jump to navigationJump to search| Line 1: | Line 1: | ||
Beam a heuristic search [[Category::method]]. It used for decoding in many areas including in [[Machine Translation]] and speech recognition. | Beam a heuristic search [[Category::method]]. It used for decoding in many areas including in [[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 varient 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(''CURRENT.STATES) | ||
| + | ::''SCORE(''CANDIDATE.STATES'')'' | ||
| + | ::CURRENT.STATES := ''PRUNE(''CANDIDATE.STATES) | ||
| + | |||
| + | |||
| + | When NEXT is called, . | ||
Revision as of 02:36, 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 varient 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(CURRENT.STATES)
- SCORE(CANDIDATE.STATES)
- CURRENT.STATES := PRUNE(CANDIDATE.STATES)
When NEXT is called, .
