Beam Search

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.