Viterbi algorithm

Background

The Viterbi algorithm is dynamic programming for hidden Markov models: given a sequence of observations, it finds the single most likely sequence of hidden states. Rather than enumerating exponentially many state paths, it carries forward, for each state and time step, the probability of the best path ending there — together with a back-pointer so the optimal path can be recovered by tracing back.

Problem statement

Implement viterbi(obs, start_p, trans_p, emit_p) returning the most likely hidden-state path as a list of state indices.

For $T$ observations and $N$ states:

$$V_0(s) = \pi_s\, B_{s, o_0}, \qquad V_t(s) = \max_{s'}\big[V_{t-1}(s')\, A_{s', s}\big]\, B_{s, o_t}$$

Store back[t][s] = argmax, then backtrack from $\arg\max_s V_{T-1}(s)$.

Input

• obs — list of int observation indices, length $T$.
• start_p — np.ndarray shape (N,), initial state probabilities $\pi$.
• trans_p — np.ndarray shape (N, N), trans_p[i, j] = $P(\text{state } j \mid \text{state } i)$.
• emit_p — np.ndarray shape (N, M), emit_p[s, o] = $P(\text{obs } o \mid \text{state } s)$.

Output

A list[int] of length $T$: the most likely hidden-state sequence.

Examples

Example 1

States: 0 = Healthy, 1 = Fever
start_p = [0.6, 0.4]
trans_p = [[0.7, 0.3], [0.4, 0.6]]
emit_p  = [[0.5, 0.4, 0.1],     # Healthy: P(normal/cold/dizzy)
           [0.1, 0.3, 0.6]]     # Fever
obs = [0, 1, 2]   # normal, cold, dizzy
Output: [0, 0, 1]   # Healthy, Healthy, Fever

Explanation: the best path keeps the patient Healthy through the first two (mild) observations, then switches to Fever for "dizzy", which Fever emits with high probability.

Constraints

• Use a max (not a sum) at each step — Viterbi finds the single best path, not the total likelihood.
• Keep back-pointers and reconstruct the path by tracing from the best final state.
• Break ties by lowest state index (NumPy argmax behavior).

Notes

• Replacing max/argmax with a sum turns Viterbi into the forward algorithm, which computes the observation likelihood instead of the best path.
• Production implementations run in log space (sums of log-probabilities) to avoid numerical underflow on long sequences.