Viterbi Algorithm

Viterbi finds the single most probable hidden state sequence in an HMM using dynamic programming over paths.

The most likely path

Forward-backward gives the probability of each state marginally, but often we want the single best joint explanation: the state sequence z_1..z_T with the highest posterior probability. The Viterbi algorithm computes it exactly by dynamic programming, replacing the sums of the forward algorithm with maximizations.

The recursion

Let delta_t(i) be the probability of the best path ending in state i at time t. It recurses as delta_t(j) = max_i [ delta_{t-1}(i) A_ij ] B_j(x_t). At each step the algorithm records which predecessor i achieved the maximum in a backpointer table psi_t(j).

Backtracking

After the forward sweep, the algorithm picks the highest-probability final state and follows the backpointers from time T back to time 1, reconstructing the optimal path. This two-phase structure, a forward maximization then a backward trace, is the same pattern used across sequence alignment and shortest-path problems.

# Viterbi in log-space
delta[0] = log(pi) + logB[:, x[0]]
for t in range(1, T):
    scores = delta[t-1][:, None] + logA
    psi[t] = scores.argmax(0)
    delta[t] = scores.max(0) + logB[:, x[t]]
path = backtrack(delta, psi)

Properties

Viterbi runs in O(T K^2) time and O(T K) memory. Working in log-space turns products into sums and avoids underflow. The most probable path is not the same as the sequence of individually most probable states: forward-backward can return a state assignment that has zero probability as a joint path, whereas Viterbi always returns a valid, self-consistent sequence.

The same algorithm decodes convolutional error-correcting codes and aligns speech frames to phoneme models, and it generalizes to conditional random fields for structured prediction.