The Viterbi Decoding Algorithm

Purpose

Viterbi finds the single most likely hidden-state sequence $q_1^*, q_2^*, \ldots, q_T^*$ given an observation sequence $o_1, o_2, \ldots, o_T$. It is a dynamic programming algorithm: at each timestep, for each state, it stores the best path probability reaching that state and a backpointer.

Components

$\delta_j(t)$: the probability of the most likely path reaching state $j$ at time $t$, accounting for observations $o_1$ through $o_t$.

$\psi_j(t)$: the backpointer — which state at $t-1$ produced the best path to state $j$ at time $t$.

Algorithm

Initialisation ($t = 1$)

For each state $j$:

$\delta_j(1) = \pi_j \cdot b_j(o_1) \qquad \psi_j(1) = 0$

Recursion ($t = 2, 3, \dots, T$)

For each state $j$:

$\delta_j(t) = \max_i \big[ \delta_i(t-1) \cdot a_{ij} \cdot b_j(o_t) \big]$ $\psi_j(t) = \arg\max_i \big[ \delta_i(t-1) \cdot a_{ij} \big]$

Note: $b_j(o_t)$ is the same for all $i$, so it can be pulled outside the max. The $\arg\max$ is over $\delta_i(t-1) \cdot a_{ij}$ only.

Termination ($t = T$)

Best path probability: $P^* = \max_i \delta_i(T)$

Final state: $q_T^* = \arg\max_i \delta_i(T)$

Backtracking ($t = T-1$ down to $1$)

$q_t^* = \psi_{q_{t+1}^*}(t+1)$

Read the backpointer chain backwards to reconstruct the optimal state sequence.

Trellis Layout

Draw a grid: rows = states, columns = timesteps. Fill each cell with $\delta_j(t)$ and $\psi_j(t)$. Circle the maximum in each column. Draw arrows from each cell to its backpointer source. After termination, trace arrows backwards from the final state.

Log-Space Implementation

In practice, use log-probabilities to prevent underflow:

$\delta_j(t) = \max_i \big[ \delta_i(t-1) + \log a_{ij} + \log b_j(o_t) \big]$

Products become sums. The $\arg\max$ result is identical. For exam purposes, you can work in either space — log is safer for long sequences.

Worked Example: 2-State Model, 3 Timesteps

Given: $S = \{1, 2\}$, $V = \{A, B\}$, observations = $[A, B]$

$\pi = [0.6, 0.4] \quad A = \begin{bmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{bmatrix} \quad B = \begin{bmatrix} 0.5 & 0.5 \\ 0.9 & 0.1 \end{bmatrix}$

$t = 1$, observation $A$

$\delta_1(1) = 0.6 \times 0.5 = 0.30 \quad \psi_1(1) = 0$ $\delta_2(1) = 0.4 \times 0.9 = 0.36 \quad \psi_2(1) = 0$

Best at $t=1$: state 2, $\delta = 0.36$.

$t = 2$, observation $B$

For state 1: $\delta_1(2) = \max[0.30 \times 0.7 \times 0.5,\; 0.36 \times 0.4 \times 0.5] = \max[0.105, 0.072] = 0.105$ $\psi_1(2) = 1$

For state 2: $\delta_2(2) = \max[0.30 \times 0.3 \times 0.1,\; 0.36 \times 0.6 \times 0.1] = \max[0.009, 0.0216] = 0.0216$ $\psi_2(2) = 2$

Best at $t=2$: state 1, $\delta = 0.105$.

Termination and Backtrack

$P^* = \max(0.105, 0.0216) = 0.105$, final state $q_2^* = 1$. Backpointer: $\psi_1(2) = 1$, so $q_1^* = 1$. Optimal path: $[1, 1]$.

Summary

Step	Formula
Init	$\delta_j(1) = \pi_j \cdot b_j(o_1)$
Recursion	$\delta_j(t) = \max_i [\delta_i(t-1) \cdot a_{ij} \cdot b_j(o_t)]$
Backpointer	$\psi_j(t) = \arg\max_i [\delta_i(t-1) \cdot a_{ij}]$
Termination	$P^* = \max_i \delta_i(T)$, $q_T^* = \arg\max_i \delta_i(T)$
Backtrack	$q_t^* = \psi_{q_{t+1}^*}(t+1)$
Log form	Sums instead of products, avoids underflow

Past paper questions: y2022p3q9, y2024p3q8, y2025p3q9