Hidden Markov Models — Section 7: Probabilistic Reasoning

An HMM models a sequence of observations $o_1, o_2, \dots, o_T$ generated by an unobserved sequence of states $s_1, s_2, \dots, s_T$ . Two assumptions:

1. Markov: $s_t$ depends only on $s_{t-1}$ . 2. Output independence: $o_t$ depends only on $s_t$ .

Specified by:

Initial state distribution $\pi$
Transition matrix $A_{ij} = P(s_t = j | s_{t-1} = i)$
Emission distribution $B_i(o) = P(o_t = o | s_t = i)$

Three classical tasks

1. Filtering (likelihood): $P(o_{1:T})$ — given parameters and observations, how likely is this sequence? Solved by the forward algorithm. 2. Decoding (inference): $\arg\max_{s_{1:T}} P(s_{1:T} | o_{1:T})$ — best explanation. Solved by the Viterbi algorithm. 3. Learning: estimate parameters from data. Solved by the Baum-Welch algorithm (Expectation-Maximization specialized to HMMs).

Forward algorithm

Compute $\alpha_t(i) = P(o_{1:t}, s_t = i)$ recursively:

\alpha_t(i) = B_i(o_t) \sum_j \alpha_{t-1}(j) A_{ji}

Time and space: $O(T \cdot |S|^2)$ . Linear in sequence length; quadratic in state cardinality.

Viterbi

Same recursion but with max instead of sum:

\delta_t(i) = B_i(o_t) \max_j \delta_{t-1}(j) A_{ji}

Plus backpointers to reconstruct the optimal state sequence. Same complexity as forward.

Backward and forward-backward

Backward $\beta_t(i) = P(o_{t+1:T} | s_t = i)$ . Combined with forward gives $P(s_t = i | o_{1:T})$ — useful for parameter learning.

When HMMs are the right tool

Sequence labeling with strong locality and small state spaces: part-of-speech tagging, named entity recognition (pre-deep-learning).
Speech recognition acoustic models (pre-deep-learning).
Bioinformatics: gene finding, protein sequence analysis.

When they're not

Long-range dependencies that don't fit in the Markov assumption (use RNN/transformer).
Very large state spaces (Viterbi quadratic blows up).
Rich emission distributions (neural network emissions extend HMMs but at that point you're in deep learning).

HMMs were the dominant sequence model from the 1980s through the early 2010s. RNNs and then transformers ate most of the application areas, but HMMs remain pedagogically central and still useful in low-resource or strongly-structured domains.