A security guard works underground and never sees the sky. Each day the director comes in either with or without an umbrella. From this sequence of umbrella observations, can the guard infer whether it is raining? This is the classic setting of a Hidden Markov Model (HMM): a hidden state evolves over time and emits noisy observations. HMMs powered speech recognition for three decades and remain important in bioinformatics and signal processing.
The model#
An HMM has:
- hidden states $X_t \in \{1, \dots, S\}$ (e.g. Rain / NoRain);
- observations $E_t$ (e.g. Umbrella / NoUmbrella);
- an initial distribution $\pi_i = P(X_1 = i)$;
- a transition model $T_{ij} = P(X_{t+1} = j \mid X_t = i)$;
- a sensor (emission) model $O_{j}(e) = P(E_t = e \mid X_t = j)$.
Two assumptions make it tractable:
- Markov assumption: $P(X_{t+1} \mid X_{1:t}) = P(X_{t+1} \mid X_t)$.
- Sensor Markov assumption: $P(E_t \mid X_{1:t}, E_{1:t-1}) = P(E_t \mid X_t)$.
The four inference tasks#
| Task | Question | Algorithm |
|---|---|---|
| Filtering | $P(X_t \mid e_{1:t})$ — where am I now? | Forward algorithm |
| Prediction | $P(X_{t+k} \mid e_{1:t})$ — where will I be? | Forward + transitions |
| Smoothing | $P(X_k \mid e_{1:t})$, $k < t$ — where was I? | Forward–backward |
| Most likely explanation | $\arg\max_{x_{1:t}} P(x_{1:t} \mid e_{1:t})$ | Viterbi |
Filtering: the forward algorithm#
Filtering is a recursive update: predict with the transition model, then correct with the new observation.
where $\alpha$ normalises the vector to sum to one. Each step costs $O(S^2)$, independent of $t$ — the agent can run forever with constant memory. This predict–update pattern is exactly the structure of the Kalman filter (for continuous linear-Gaussian models) and the particle filter (for general models) used in robotics.
Smoothing: forward–backward#
To estimate a past state using all evidence, combine a forward message with a backward message:
Decoding: the Viterbi algorithm#
Often we want the single most likely sequence of hidden states — e.g. the most likely sequence of words given audio. Viterbi is dynamic programming over the trellis of states, replacing the sum in the forward algorithm with a max:
and keeping back-pointers to recover the path.
import numpy as np
states = ["Rain", "NoRain"]
pi = np.array([0.5, 0.5])
T = np.array([[0.7, 0.3], # from Rain
[0.3, 0.7]]) # from NoRain
O = {"U": np.array([0.9, 0.2]), # P(umbrella | state)
"~U": np.array([0.1, 0.8])}
def forward(obs):
f = pi * O[obs[0]]; f /= f.sum()
out = [f]
for e in obs[1:]:
f = O[e] * (f @ T); f /= f.sum()
out.append(f)
return out
def viterbi(obs):
logT = np.log(T)
m = np.log(pi) + np.log(O[obs[0]])
back = []
for e in obs[1:]:
scores = m[:, None] + logT # scores[i, j]
back.append(scores.argmax(axis=0))
m = scores.max(axis=0) + np.log(O[e])
path = [int(m.argmax())]
for bp in reversed(back):
path.append(int(bp[path[-1]]))
return [states[s] for s in reversed(path)]
obs = ["U", "U", "~U", "U", "U"]
print([f.round(3) for f in forward(obs)])
print(viterbi(obs))Learning HMM parameters: Baum–Welch#
If we only have observation sequences, we can learn $\pi$, $T$ and $O$ with the Baum–Welch algorithm, a special case of Expectation–Maximisation (EM):
- E-step: use forward–backward to compute expected counts of each transition and emission.
- M-step: re-estimate parameters from those expected counts.
EM increases the likelihood at every iteration but may converge to a local optimum, so multiple random restarts are common.
Applications and limitations#
HMMs were the backbone of speech recognition (hidden phonemes, observed acoustic features) until deep learning took over around 2012. They remain widely used for gene finding and protein family modelling in bioinformatics, part-of-speech tagging, activity recognition from wearable sensors, and finance regime detection.
Their limitation is the first-order Markov assumption: the next state depends only on the current one, and each observation depends only on the current state. Recurrent neural networks and transformers relax these assumptions and can capture long-range dependencies — at the cost of interpretability and data hunger.