Viterbi Algorithm › Viterbi for Beam Search Foundation
Language AI HandbookAll chapters Viterbi Algorithm › Viterbi for Beam Search FoundationOne section · Sections in this chapter8 / 12 ↓
Reading tools Definitions & inline links
Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.
Article links
Make inline references clickable
While Viterbi finds the single best path, many applications need the best paths. Neural sequence models often use beam search, which maintains the top partial hypotheses at each step. Beam search is essentially a pruned version of Viterbi.
Beam search is a heuristic search algorithm that explores the most promising paths in parallel. At each step, it keeps only the top (beam width) partial sequences, pruning less promising alternatives.
The connection to Viterbi is direct: if we set the beam width to equal the number of states, beam search becomes equivalent to Viterbi. Smaller beam widths trade optimality for speed.
import heapq
def beam_search_viterbi(
observations, states, start_prob, trans_prob, emit_prob, beam_width=3
):
"""
Beam search approximation to Viterbi.
Keeps only the top beam_width hypotheses at each step.
"""
n = len(observations)
# Initialize with start probabilities
# Each hypothesis is (score, path)
beam = []
for s in states:
emit = emit_prob.get((s, observations[0]), 1e-10)
score = math.log(start_prob.get(s, 1e-10)) + math.log(emit)
beam.append((score, [s]))
# Keep top k
beam = heapq.nlargest(beam_width, beam, key=lambda x: x[0])
# Extend hypotheses
for i in range(1, n):
new_beam = []
for score, path in beam:
prev_state = path[-1]
emit_obs = observations[i]
for s in states:
trans = trans_prob.get((prev_state, s), 1e-10)
emit = emit_prob.get((s, emit_obs), 1e-10)
new_score = score + math.log(trans) + math.log(emit)
new_beam.append((new_score, path + [s]))
# Prune to beam width
beam = heapq.nlargest(beam_width, new_beam, key=lambda x: x[0])
# Return best hypothesis
best_score, best_path = max(beam, key=lambda x: x[0])
return best_path, best_score
# Compare Viterbi (full) vs beam search
beam_widths = [1, 2, 3, len(states)] # 1 is greedy, len(states) is full Viterbi
results = []
for bw in beam_widths:
path, score = beam_search_viterbi(
observations, states, start_prob, trans_prob, emit_prob, beam_width=bw
)
results.append((bw, path, score))Beam Search vs Viterbi
=======================================================
greedy : State0 → State0 → State0 → State0 → State0 → State0 → State0
score = -322.3619
beam=2 : State0 → State0 → State0 → State0 → State0 → State0 → State0
score = -322.3619
Viterbi : State0 → State0 → State0 → State0 → State0 → State0 → State0
score = -322.3619
Viterbi : State0 → State0 → State0 → State0 → State0 → State0 → State0
score = -322.3619
Beam width vs optimality:
k=1: matches optimal ✓
k=2: matches optimal ✓
k=3: matches optimal ✓
k=3: matches optimal ✓The comparison reveals the tradeoff between beam width and optimality. Greedy search (k=1) may find a suboptimal path because it prunes too aggressively. As beam width increases, we retain more hypotheses and are more likely to find the optimal solution. With beam width equal to the number of states, beam search becomes exact Viterbi. In practice, small beam widths (3-10) often find near-optimal solutions while running much faster than exact Viterbi.
Beam search with is greedy decoding. As increases, we approach Viterbi's optimal solution. The tradeoff is computation time: beam search is where is the beam width, compared to Viterbi's .