Viterbi Algorithm

Purpose: Find the single most likely sequence of hidden states in a hidden Markov model, given a sequence of observations, in $O(T{S}^2)$ where $T$ is the number of observations and $S$ the number of states.

Setup

An HMM has:

• states $\mathrm{1..}S$ with an initial distribution $\pi$;
• transition probabilities $A[i][j]=P(\text{state }j\text{ at }t+1\mid \text{state }i\text{ at }t)$;
• emission probabilities $B[i][o]=P(\text{observe }o\mid \text{state }i)$.

Algorithm

It is a shortest-path DP over the trellis — a layered DAG with $T$ layers of $S$ nodes.

$${\delta }_t(j)=\underset{i}{\max }({\delta }_{t-1}(i)\cdot A[i][j])\cdot B[j][o_t],{\delta }_1(j)={\pi }_{j}B[j][o_1].$$

Store ${\psi }_t(j)=\arg {\max }_i$ to reconstruct the path, then backtrack from $\arg {\max }_j{\delta }_T(j)$.

Code

// work in log space: products become sums, underflow disappears
vector<int> viterbi(const vector<int>& obs, int S,
                    const vector<double>& logPi,
                    const vector<vector<double>>& logA,
                    const vector<vector<double>>& logB) {
    int T = obs.size();
    vector<vector<double>> dp(T, vector<double>(S, -1e18));
    vector<vector<int>> par(T, vector<int>(S, -1));
 
    for (int j = 0; j < S; j++) dp[0][j] = logPi[j] + logB[j][obs[0]];
 
    for (int t = 1; t < T; t++)
        for (int j = 0; j < S; j++)
            for (int i = 0; i < S; i++) {
                double v = dp[t-1][i] + logA[i][j] + logB[j][obs[t]];
                if (v > dp[t][j]) { dp[t][j] = v; par[t][j] = i; }
            }
 
    int best = max_element(dp[T-1].begin(), dp[T-1].end()) - dp[T-1].begin();
    vector<int> path(T);
    for (int t = T - 1; t >= 0; t--) { path[t] = best; best = par[t][best]; }
    return path;
}

Always use logs

Multiplying $T$ probabilities underflows a double after a few hundred steps. Take logarithms once at the start; products become sums and the algorithm becomes an ordinary longest-path DP.

Paradigm

Dynamic programming on a layered DAG. Viterbi is DAG shortest path where the “distance” is negative log probability. Recognising this is the whole insight — everything else is bookkeeping.

Complexity

• Time: $O(T{S}^2)$; $O(TS\cdot \bar{d})$ if the transition matrix is sparse with average out-degree $\bar{d}$
• Space: $O(TS)$ for the backpointers; $O(S)$ if you only need the probability

Correctness

By induction on $t$: ${\delta }_t(j)$ is the probability of the most likely state sequence ending in state $j$ having emitted $o_1..o_t$. The Markov property means the future depends on the past only through the current state, so an optimal path to $(t,j)$ must have an optimal prefix to some $(t-1,i)$ — the optimal substructure that makes DP valid. ∎

Viterbi vs Forward algorithm

	Recurrence	Answers
Viterbi	$\max$ over predecessors	the single most likely path
Forward	$\sum$ over predecessors	the total probability of the observations

Same trellis, different semiring — $(\max ,\times )$ versus $(+,\times )$.

Variants / Use Cases

• Speech recognition, POS tagging, gene finding — the classical applications
• Convolutional code decoding — Viterbi’s original 1967 problem; still in every modem and satellite link
• Map matching — snapping noisy GPS traces to a road network
• Beam search — a heuristic pruning of the trellis when $S$ is huge
• DAG shortest paths — the underlying structure
• Baum-Welch / forward-backward — learning the HMM parameters rather than decoding with them