Hidden Markov ModelsOpen in Colab
ML project loop
Data·Hypothesis space·Objective·Optimization·Evaluation·Deployment feedback

Hidden Markov Models

A Hidden Markov Model (HMM) is a graphical model for sequences where the thing you care about is hidden and you only see noisy evidence of it. The weather (hidden) drives whether someone carries an umbrella (observed); the spoken phoneme (hidden) drives the audio waveform (observed). HMMs were the workhorse of speech recognition and bioinformatics for decades.

Real-world examples: Speech recognition, part-of-speech tagging, gene finding, gesture recognition, financial regime detection, decoding DNA.

Two assumptions

An HMM has a chain of hidden states z1,…,zTz_1, \dots, z_T and observations x1,…,xTx_1, \dots, x_T, built on two Markov assumptions:

  1. Markov property: the next hidden state depends only on the current one: P(zt∣z1:t−1)=P(zt∣zt−1)P(z_t \mid z_{1:t-1}) = P(z_t \mid z_{t-1}).
  2. Output independence: each observation depends only on the current hidden state: P(xt∣z1:t,x1:t−1)=P(xt∣zt)P(x_t \mid z_{1:t}, x_{1:t-1}) = P(x_t \mid z_t).

These give the joint:

P(z1:T,x1:T)=P(z1)∏t=2TP(zt∣zt−1)∏t=1TP(xt∣zt)P(z_{1:T}, x_{1:T}) = P(z_1)\prod_{t=2}^{T} P(z_t \mid z_{t-1}) \prod_{t=1}^{T} P(x_t \mid z_t)

The three matrices

SymbolNameMeaning
π\boldsymbol{\pi}Initial distributionP(z1=i)P(z_1 = i)
AijA_{ij}Transition matrixP(zt=j∣zt−1=i)P(z_t = j \mid z_{t-1} = i)
BikB_{ik}Emission matrixP(xt=k∣zt=i)P(x_t = k \mid z_t = i)

Intuition

Picture a person in a windowless room (you can't see the weather = hidden state) who each day carries an umbrella or not (the observation). Rainy days transition to rainy days often (AA), and rain makes umbrellas likely (BB). From a week of umbrella sightings alone, you can infer the hidden weather sequence.

Three classic problems

Every HMM use case is one of these three, each with a dynamic-programming algorithm:

ProblemQuestionAlgorithm
1. LikelihoodP(x1:T)P(x_{1:T}): how probable is this sequence?Forward
2. DecodingMost likely hidden path arg⁡max⁡zP(z1:T∣x1:T)\arg\max_z P(z_{1:T}\mid x_{1:T})Viterbi
3. LearningBest π,A,B\pi, A, B from dataBaum–Welch (EM)

Problem 1: the Forward algorithm

Naively, P(x1:T)=∑zP(z,x)P(x_{1:T}) = \sum_z P(z, x) sums over KTK^T hidden paths — exponential. The forward algorithm does it in O(K2T)O(K^2 T) by caching αt(i)=P(x1:t,zt=i)\alpha_t(i) = P(x_{1:t}, z_t = i):

α1(i)=πi Bi,x1αt(j)=Bj,xt∑iαt−1(i) Aij\alpha_1(i) = \pi_i\, B_{i, x_1} \qquad \alpha_t(j) = B_{j, x_t}\sum_{i} \alpha_{t-1}(i)\, A_{ij}

Then P(x1:T)=∑iαT(i)P(x_{1:T}) = \sum_i \alpha_T(i). This is dynamic programming: reuse the sum over all paths ending in each state rather than re-enumerating paths.

Problem 2: Viterbi decoding

Viterbi finds the single most likely hidden sequence. It's the forward recursion with ∑\sum replaced by max⁡\max, plus back-pointers to reconstruct the path:

δt(j)=Bj,xtmax⁡i[δt−1(i) Aij]\delta_t(j) = B_{j, x_t}\max_{i}\big[\delta_{t-1}(i)\, A_{ij}\big]

Sum vs max

Forward and Viterbi are the same recursion with one operator swapped. Forward sums over paths (total probability of the evidence); Viterbi maximizes over paths (the best explanation). Back-pointers in Viterbi let you trace the winning path backward at the end.

Worked example: Viterbi by hand

States , π=[0.6,0.4]\pi = [0.6, 0.4]. Transitions A=[0.70.30.40.6]A = \begin{bmatrix}0.7 & 0.3\\ 0.4 & 0.6\end{bmatrix}. Emissions for : Rainy [0.1,0.4,0.5][0.1, 0.4, 0.5], Sunny [0.6,0.3,0.1][0.6, 0.3, 0.1]. Observe Walk → Shop.

Step 1 (Walk): δ1(R)=0.6⋅0.1=0.06\delta_1(R)=0.6\cdot 0.1=0.06, δ1(S)=0.4⋅0.6=0.24\delta_1(S)=0.4\cdot 0.6=0.24.

Step 2 (Shop), Rainy: max⁡(0.06⋅0.7, 0.24⋅0.4)⋅0.4=max⁡(0.042,0.096)⋅0.4=0.0384\max(0.06\cdot 0.7,\ 0.24\cdot 0.4)\cdot 0.4 = \max(0.042, 0.096)\cdot 0.4 = 0.0384 (came from Sunny). Step 2, Sunny: max⁡(0.06⋅0.3, 0.24⋅0.6)⋅0.3=max⁡(0.018,0.144)⋅0.3=0.0432\max(0.06\cdot 0.3,\ 0.24\cdot 0.6)\cdot 0.3 = \max(0.018, 0.144)\cdot 0.3 = 0.0432 (came from Sunny).

Winner at t=2t=2: Sunny (0.04320.0432), back-pointer → Sunny. Best path: Sunny → Sunny.

Backpointer table (tracking the best path)

Time stepObservationRainy (δ\delta, from)Sunny (δ\delta, from)
t=1t=1Walk0.06, —0.24, —
t=2t=2Shop0.0384, Sunny0.0432, Sunny

The highest score at t=2t=2 is δ2(S)=0.0432\delta_2(S)=0.0432, so we start back-tracking from Sunny. Reading the path backwards from the highest final state: qT∗→qT−1∗→…→q1∗q_T^* \to q_{T-1}^* \to \ldots \to q_1^*. In our example this gives the state sequence Sunny → Sunny: at t=2t=2 the winner is Sunny, and its back-pointer records it came from Sunny at t=1t=1.

To reconstruct the path in code, store ψt(j)=arg⁡max⁡i[δt−1(i) Aij]\psi_t(j) = \arg\max_i [\delta_{t-1}(i)\,A_{ij}] at every step. At the end, find qT∗=arg⁡max⁡jδT(j)q_T^* = \arg\max_j \delta_T(j), then follow the back-pointers: qt−1∗=ψt(qt∗)q_{t-1}^* = \psi_t(q_t^*). This single backward pass recovers the complete optimal sequence in O(KT)O(KT) time — no additional computation beyond what the forward pass already stored.

Step through the decoder

The same numbers as the table above, one lattice cell at a time — every incoming candidate scored, the max taken, the loser discarded, and a backpointer stored:

Viterbi — max over paths, and the backpointers that reconstruct one

1/9

A two-state weather HMM — Rainy or Sunny — where you never see the weather, only what someone did: Walk, Shop or Clean. The observations are Walk → Shop. Viterbi answers one specific question: **which single hidden sequence is most probable?**

python
1def viterbi(x, pi, A, B):
2 T, N = len(x), len(pi)
3 d = [[0.0] * N for _ in range(T)]
4 psi = [[0] * N for _ in range(T)]
5 for j in range(N):
6 d[0][j] = pi[j] * B[j][x[0]]
7 for t in range(1, T):
8 for j in range(N):
9 # max over paths, not sum
10 cand = [d[t-1][i] * A[i][j]
11 for i in range(N)]
12 psi[t][j] = argmax(cand)
13 d[t][j] = max(cand) * B[j][x[t]]
14 q = [argmax(d[T-1])] # best last
15 for t in range(T - 1, 0, -1):
16 q.insert(0, psi[t][q[0]]) # backtrace
17 return q, max(d[T-1])
state
A — transition
RainySunny
Rainy0.700.30
Sunny0.400.60
B — emission
WalkShopClean
Rainy0.100.400.50
Sunny0.600.300.10
π — initial
Rainy → 0.6Sunny → 0.4
the trellis, empty
Rainy ·Sunny ·Rainy ·Sunny ·t=1 (Walk) t=2 (Shop)

Viterbi decoding on the Rainy/Sunny HMM worked by hand above, cell by cell: every incoming candidate scored, the max taken, the loser discarded, and a backpointer stored so the winning path can be walked back at the end. The last step swaps max for sum — the forward algorithm — on the identical lattice, and the per-step argmax disagrees with the best whole path. That disagreement is the whole reason both algorithms exist.

What to notice as you step:

  • The loser is discarded permanently. When δ2(Rainy)\delta_2(\text{Rainy}) picks the Sunny predecessor, the Rainy-to-Rainy path is gone for good. That pruning is what makes the recursion O(K2T)O(K^2T) instead of O(KT)O(K^T), and it is only valid because the Markov property guarantees no discarded prefix could ever be rescued by a later observation.
  • δ\delta is not a probability of a state. It is the score of one complete best-path-so-far. The brute-force enumeration step confirms it: δ2\delta_2 equals the joint probability of the single best path, not the marginal.
  • The final step swaps max for sum: that one change is the forward algorithm, and the answers diverge on identical numbers. α2\alpha_2 says Rainy is the more likely state at t=2t = 2; δ2\delta_2 says the best path ends in Sunny. Per-step argmax and best-whole-path are genuinely different questions, which is why Viterbi bothers with backpointers at all.

Viterbi Algorithm — Weather / Ice Cream HMM

t=1obs=3t=2obs=1t=3obs=3t=4obs=2HotColdNeutral————————————
columns filled0 / 4
best path—
P(best path)—

States: Hot (orange), Cold (indigo), Neutral (yellow). Click Step to fill one column. Back-pointer arrows (→) show which previous state maximised the probability. The teal path is the optimal decoded sequence.

Python
import numpy as np
from hmmlearn import hmm   # pip install hmmlearn

model = hmm.CategoricalHMM(n_components=2)
model.startprob_ = np.array([0.6, 0.4])
model.transmat_  = np.array([[0.7, 0.3],
                             [0.4, 0.6]])
model.emissionprob_ = np.array([[0.1, 0.4, 0.5],   # Rainy: Walk/Shop/Clean
                                [0.6, 0.3, 0.1]])   # Sunny

obs = np.array([[0], [1]])                          # Walk, Shop
logprob, states = model.decode(obs, algorithm="viterbi")
print("best hidden path:", states)                 # -> [1 1] = Sunny, Sunny
print("log P:", round(logprob, 3))

Problem 3: Baum–Welch (learning)

When you have observation sequences but no hidden labels, Baum–Welch (an instance of the EM algorithm) estimates π,A,B\pi, A, B. It alternates an E-step (run forward and backward passes to compute how responsible each state and transition is for the data) with an M-step (re-estimate all parameters as normalized expected counts), repeating until the likelihood converges to a local optimum. It is the same E/M loop as Gaussian Mixture Models — HMMs are essentially "GMMs with a Markov chain tying the components across time."

Deep dive
The Baum–Welch Algorithm
Includes runnable notebook

HMM as a graphical model

An HMM is just a specific Bayesian Network: a chain z1→z2→⋯→zTz_1 \to z_2 \to \dots \to z_T with each zt→xtz_t \to x_t. Everything from the Bayesian Networks lesson applies — the forward/backward passes are belief propagation specialized to a chain.

Underflow: work in log space

Multiplying many probabilities underflows to 0 fast. Real implementations run the forward/Viterbi recursions in log space (sums of log-probs, logsumexp for the forward sum), or rescale αt\alpha_t at each step. hmmlearn does this for you.

Limits and what replaced HMMs

HMMs assume discrete hidden state and a strict Markov chain. For richer dependencies and continuous representations, RNNs/LSTMs and Transformers (earlier courses) largely superseded HMMs in speech and NLP, but HMMs remain valuable when data is scarce, interpretability matters, or the Markov structure is genuinely correct (e.g. bioinformatics).

Exercise

Which two assumptions define a Hidden Markov Model?

Need a hint?

One is about hidden states, one about observations.

Exercise

What is the key difference between the Forward algorithm and the Viterbi algorithm for HMMs?

Need a hint?

One sums over paths, the other maximizes.

Exercise

The Baum-Welch algorithm for learning HMM parameters is an instance of which general algorithm?

Need a hint?

It alternates an E-step and an M-step.

Common mistakes

  1. Confusing Forward with Viterbi: Forward sums (likelihood); Viterbi maximizes (best path). Don't use one for the other's question.
  2. Multiplying probabilities in linear space: underflow; use logs.
  3. Expecting a global optimum from Baum–Welch: it's EM, so it finds a local optimum; use multiple random restarts.

Key takeaways

  • An HMM has hidden states (Markov chain) emitting observations.
  • Forward sums over paths (likelihood); Viterbi maximizes (best path).
  • Baum-Welch learns the parameters. It is EM for sequences.
  • Work in log space to avoid underflow.

Related concepts

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

Builds onRelatedGo deeper
Hidden Markov ModelsProbabilistic Models & EMProbability & StatisticsGaussian Mixture ModelsThe EM AlgorithmBayesian NetworksMarkov Random FieldsRecurrent Neural NetworksSpeech RecognitionThe Baum–Welch AlgorithmPartially Observable MDPs…The EM AlgorithmVariable Elimination