Wait, What?
The Viterbi algorithm does not ask which hidden state is most likely at each moment. It asks which entire hidden-state path is most likely to have produced the observations.
That distinction makes Viterbi one of the best algorithms for learning dynamic programming in a probabilistic setting. The state is hidden, the observations are visible, and many possible paths compete. Instead of enumerating every path, Viterbi keeps only the best path ending in each state at each time step, together with enough backpointer information to reconstruct the winning sequence.
Quick Answer
Learn Viterbi through hidden states → transitions → emissions → trellis → best-path recurrence → backpointers → log probabilities → traceback → complexity → model validation. The key invariant is simple: after processing time t, the score stored for state j is the score of the best complete partial path that ends in j.
1. Start With a Hidden Markov Model
A hidden Markov model has a finite set of hidden states, transition probabilities between states, emission probabilities for observations, and an initial-state distribution. The Markov assumption says the next hidden state depends on the current hidden state rather than the entire earlier history. The emission assumption says the current observation depends on the current hidden state.
Suppose the hidden weather is Sunny or Rainy, while the visible observation is whether someone carries an umbrella. You see a sequence such as Umbrella, Umbrella, No-Umbrella. Viterbi asks for the single most probable hidden weather path that could have produced that observation sequence.
2. Draw the Trellis Before Writing Code
Put time on the horizontal axis and hidden states vertically. Each column contains one node per possible hidden state. Draw directed transitions from every allowable state at time t−1 to every allowable state at time t. Attach transition and emission probabilities to the moves.
The trellis turns an apparently exponential path problem into a repeated local decision. Every full path reaching state j at time t must come through exactly one predecessor state i at time t−1. If you already know the best path to each predecessor, you do not need to remember the inferior paths ending at the same predecessor.
3. The Dynamic-Programming State
Let δt(j) be the probability of the most likely hidden-state path for observations 1…t that ends in state j at time t. Let ψt(j) record which predecessor state achieved that maximum.
The recurrence is:
δ_t(j) = emission(j, observation_t) * max_i [ δ_(t-1)(i) * transition(i, j) ]
ψ_t(j) = argmax_i [ δ_(t-1)(i) * transition(i, j) ]The emission factor depends only on the destination state and current observation, while the maximum compares predecessor paths.
4. Initialization Is Part of the Algorithm
At time 1, there is no predecessor transition from an earlier hidden state. Initialize with the prior probability of each state multiplied by the probability of emitting the first observation:
δ_1(j) = initial(j) * emission(j, observation_1)A surprising number of incorrect implementations accidentally apply a transition twice, omit the first emission, or mix a special start-state probability into the wrong place. Write the model contract before the loop.
5. Work One Column by Hand
Imagine that at time t−1 the best path scores are 0.18 for Sunny and 0.12 for Rainy. To compute the best path ending in Rainy at time t, compare 0.18 × P(Rainy|Sunny) with 0.12 × P(Rainy|Rainy). Keep the larger predecessor score, multiply by the probability of the current observation given Rainy, and store the winning predecessor in the backpointer table.
Do this separately for every destination state. The algorithm never chooses one global state per column until the very end.
6. Why Greedy Per-Time Decisions Fail
Choosing the state with the largest emission probability at each time can produce an impossible or low-probability path because transition structure matters. A state that explains the current observation well may be extremely unlikely given the previous state. Viterbi optimizes the whole path probability, not independent local labels.
7. Use Log Probabilities in Real Code
Multiplying many probabilities quickly underflows toward zero in floating-point arithmetic. Professional implementations normally work in log space. Products become sums, and the maximization stays a maximization because logarithm is monotonic.
score_t(j) = log_emission(j, obs_t) + max_i(
score_prev(i) + log_transition(i, j)
)Impossible events can be represented as negative infinity. This also makes debugging easier because scores remain interpretable as additive path costs.
8. A Clear Python Skeleton
from math import log, inf
def safe_log(p):
return -inf if p == 0 else log(p)
def viterbi(observations, states, start_p, trans_p, emit_p):
T = len(observations)
score = [{s: -inf for s in states} for _ in range(T)]
back = [{s: None for s in states} for _ in range(T)]
for s in states:
score[0][s] = safe_log(start_p[s]) + safe_log(emit_p[s][observations[0]])
for t in range(1, T):
obs = observations[t]
for s in states:
best_prev = None
best_score = -inf
for p in states:
candidate = score[t - 1][p] + safe_log(trans_p[p][s])
if candidate > best_score:
best_score = candidate
best_prev = p
score[t][s] = best_score + safe_log(emit_p[s][obs])
back[t][s] = best_prev
last = max(states, key=lambda s: score[T - 1][s])
path = [last]
for t in range(T - 1, 0, -1):
last = back[t][last]
path.append(last)
path.reverse()
return path, score[T - 1][path[-1]]This version favours clarity. Production code often uses arrays, sparse transitions, vectorized operations, beam restrictions or specialized semiring libraries.
9. The Correctness Invariant
After time t is processed, score[t][j] represents the best possible score among all hidden paths of length t that end in j. The proof is induction. At t=1 the initialization checks every possible starting state. For t>1, every path ending in j has some predecessor i. By induction, only the best path ending in i needs to be considered; any worse path ending in the same i can never beat it after multiplying by the same i→j transition and j emission.
This is the same optimal-substructure argument that powers many dynamic-programming algorithms, but the probability model makes the state meaning especially visible.
10. Backpointers Separate Scoring From Reconstruction
The forward pass decides the best predecessor for each state and time. The traceback phase starts at the best final state and follows stored predecessor links backward. This separation is a reusable algorithmic pattern: compute optimum values first, store choices, reconstruct the object later.
If you only need the best final score and not the path, you can keep just the previous score column and reduce score memory to O(S). If you need the full path, backpointers usually require O(TS) memory unless you use more advanced checkpointing or divide-and-conquer reconstruction.
11. Complexity
With S hidden states and T observations, a dense HMM checks S possible predecessors for each of S destination states at each time step, giving O(TS²) time. The full score and backpointer tables use O(TS) memory. Sparse transition structure can reduce work dramatically because impossible transitions need not be evaluated.
12. Viterbi Path Is Not the Same as Per-Time Posterior Mode
Another common error is to confuse Viterbi decoding with choosing the most probable state at each time after computing posterior marginals. The most likely whole sequence can differ from the sequence formed by independently choosing each time’s most probable marginal state. These are different optimization objectives and should not be mixed.
13. Where Professionals Use the Pattern
- Digital communications: the algorithm originated in decoding convolutional codes.
- Speech and language processing: hidden-state sequence decoding.
- Bioinformatics: state-path inference in sequence models.
- Tracking and signal processing: choosing the most likely latent trajectory under a Markov model.
Modern machine-learning systems may use richer models, but the Viterbi recurrence remains an important reference point for maximum-a-posteriori sequence decoding and for understanding dynamic programming over state lattices.
14. Professional Failure States
- Multiplying raw probabilities until numerical underflow turns every path into zero.
- Forgetting the initial-state distribution.
- Choosing the locally best state instead of the best predecessor path for each destination state.
- Storing scores but not backpointers when a full path is required.
- Using the wrong orientation for the transition matrix.
- Ignoring zero-probability transitions or emissions.
- Confusing Viterbi MAP-path decoding with posterior marginal decoding.
- Failing to define deterministic tie-breaking when reproducibility matters.
15. Test the Model and the Algorithm Separately
For tiny state spaces, enumerate every possible hidden path and verify that Viterbi selects the same winner. Check that transition and emission distributions satisfy the intended normalization. Test impossible observations, ties, one-element sequences and sparse transition graphs. A correct dynamic program over an incorrect probability model is still an incorrect system.
16. From Beginner to Professional
Beginner: draw a two-state trellis and multiply path probabilities. Foundation: fill one dynamic-programming column by hand. Intermediate: add backpointers and perform traceback. Advanced: prove the recurrence and move the implementation into log space. Professional: exploit sparse transitions, benchmark vectorized implementations, reason about tie-breaking and memory, and distinguish path decoding from posterior inference.
Learning Hall Boundary
This article owns Viterbi-style best-path sequence decoding: trellises, recurrence, backpointers, log-space implementation and validation. It does not replace the existing Learning Hall dynamic-programming foundations, probability instruction, error-correcting-code overview or broader machine-learning articles.
Evidence Boundary
Andrew J. Viterbi’s 1967 IEEE Transactions on Information Theory paper introduced the decoding method in the context of convolutional codes. The same dynamic-programming structure is now standard in hidden Markov model teaching; current Stanford materials continue to teach Viterbi decoding in information-science and graphical-model courses. The instructional structure here uses trellis drawing, hand tracing, worked examples, explicit invariants and debugging checks in line with current computing-education emphasis on reading code, assessing efficiency, testing and explaining algorithmic choices.
Professional rule: Viterbi works because once you know the best path to each state, every inferior path ending at that same state can be discarded without harming the final optimum.
eduKate Sengkang 