Hidden Markov models

Summary

A Hidden Markov Model is a latent-variable sequence model with: (a) a discrete latent state $z_{t}$ evolving as a first-order Markov chain with transition matrix $A$ , and (b) per-state emission distributions producing observations $x_{t} ∣ z_{t}$ .

HMMs were the dominant sequence model from the 1970s through the early 2010s for speech recognition, part-of-speech tagging, gene finding, and many time-series problems. They have largely been displaced by neural sequence models (RNNs, transformers) for tasks with abundant data, but remain useful for:

Small-data sequence labeling.
Settings with strong domain structure (gene finding still uses HMMs).
Online filtering with limited compute.
As a teaching example of latent-variable inference.

The three classical HMM problems. Likelihood, decoding, learning. And their solutions (forward, Viterbi, Baum-Welch) are core probabilistic ML.

The model

Discrete latent states $z_{t} \in {1, \dots, K}$ .
Initial distribution $π_{k} = p (z_{1} = k)$ .
Transition matrix $A_{ij} = p (z_{t + 1} = j ∣ z_{t} = i)$ .
Emission distributions $p (x_{t} ∣ z_{t} = k; ϕ_{k})$ . Typically Gaussian or categorical.

The joint:

p (x_{1 : T}, z_{1 : T}) = π_{z_{1}} p (x_{1} ∣ z_{1}) t = 2 \prod T A_{z_{t - 1}, z_{t}} p (x_{t} ∣ z_{t}) .

Learning objective: trace how temporal dependence travels through the hidden-state chain while each observation is generated only from its same-time state.

Hidden dynamics, local evidence

Hidden states connect observations that have no direct edge

Derivation

follow the top row to sample the hidden trajectory, then move down once at each timestep to emit the observation. There is no direct arrow from one x_t to the next: distant observations are related because their hidden causes are related. Condition on the double-ringed z₂, and that state blocks the path between past and future. The graph therefore reads directly as the joint's initial factor followed by one transition and one emission per timestep. Original schematic checked against Rabiner's HMM tutorial and the hmmlearn model description.

Check: How can x1 and x3 depend even though the graph contains no direct edge between observations?

Read it this way: The hidden states transmit dependence through time. Each observation is emitted locally; there is no direct observation-to-observation edge.
Does a direct arrow between neighboring observations belong in this HMM?

The three classical problems

1. Likelihood: forward algorithm

Compute $p (x_{1 : T})$ by marginalizing over $z_{1 : T}$ . Naive sum is $O (K^{T})$ . The forward algorithm uses dynamic programming:

α_{t} (k) = p (x_{1 : t}, z_{t} = k) = p (x_{t} ∣ z_{t} = k) j \sum A_{j, k} α_{t - 1} (j) .

Complexity: $O (T K^{2})$ . Final likelihood: $\sum_{k} α_{T} (k)$ .

2. Decoding: Viterbi algorithm

Find the most likely sequence $z_{1 : T}^{*}$ . Same DP structure but replace sum with max:

δ_{t} (k) = j max A_{j, k} δ_{t - 1} (j) \cdot p (x_{t} ∣ z_{t} = k) .

Backtrack from $ar g max_{k} δ_{T} (k)$ . Complexity: $O (T K^{2})$ .

3. Learning: Baum-Welch (EM)

Estimate $π, A, ϕ$ from observations alone. E-step: compute posterior over latents using forward-backward. M-step: weighted MLE on transitions and emissions. This is EM applied to HMMs; converges to local optimum of the log-likelihood.

Forward-backward

The forward variable $α_{t} (k) = p (x_{1 : t}, z_{t} = k)$ and backward variable $β_{t} (k) = p (x_{t + 1 : T} ∣ z_{t} = k)$ together give:

Posterior over single state: $p (z_{t} = k ∣ x_{1 : T}) = α_{t} (k) β_{t} (k) / p (x_{1 : T})$ .
Posterior over consecutive pair: needed for the EM transition update.

Forward-backward is the HMM analog of message passing on a chain. Exact in $O (T K^{2})$ .

Connection to other models

Model	Relation to HMM
Mixture of Gaussians	HMM with $T = 1$
Linear-Gaussian state space (Kalman filter)	Continuous-state HMM
CRF	Discriminative HMM (model $p (z ∣ x)$ directly)
Linear-chain RNN	Neural generalization with continuous latents
Transformer	Replaces Markov assumption with attention over full sequence

When to use HMMs in 2026

Setting	HMM vs. alternatives
Phoneme alignment in TTS / ASR forced alignment	HMM still standard
Bioinformatics (gene finding, profile HMMs)	HMMs dominant
Small-data sequence labeling	HMM or CRF baseline
Modern NLP (NER, POS)	Transformers win
Speech recognition (end-to-end)	RNN-T or transformer encoder + CTC

Common pitfalls

Numerical underflow. $α_{t} (k)$ shrinks geometrically; use log-space or scaling.
EM local optima. Multiple random restarts; initialize emission means with k-means.
Treating HMMs as state-of-the-art for general sequence tasks. They are not for any task with abundant data.
Confusing first-order Markov with the model’s expressiveness. The latent is first-order Markov; the observations can have arbitrary long-range structure mediated by latents (which is why HMMs work at all).

Markov chains. The latent dynamics.
Expectation-Maximization. Baum-Welch is EM for HMMs.