Hidden Markov Models

How to reason about a state you can never see directly, one noisy reading at a time.

Manga page: Pavlodar. Night shift. / We can't see the machine's true state. Only the sensor. / HIGH... HIGH... two in a row?

Hidden states vs observations

A sensor reports a measurement, not the full truth. Sensors give false alarms, a fault can exist before any alarm, and the same reading can have different causes. The past helps interpret the present. So we combine noisy evidence with a model of how the system changes over time.

Markov chains

A Markov chain describes how a state changes step by step. The Markov assumption says the next state depends only on the current one:

P(Xₜ₊₁ | Xₜ, Xₜ₋₁, …, X₁) = P(Xₜ₊₁ | Xₜ)

Transition T (now → next)	→ Healthy	→ Faulty
Healthy	0.90	0.10
Faulty	0.20	0.80

Each row sums to 1. One-step prediction multiplies the belief vector by T: p′ = p·T. From [0.80, 0.20]: Healthy = 0.80·0.90 + 0.20·0.20 = 0.76, Faulty = 0.80·0.10 + 0.20·0.80 = 0.24.

Building the HMM

An HMM has three ingredients:

Initial probabilities π: 80% Healthy, 20% Faulty.
Transition probabilities T: how the hidden state changes (table above).
Emission probabilities O: which readings each hidden state produces.

Emission O	Normal reading	High reading
Healthy	0.80	0.20
Faulty	0.30	0.70

Careful: P(High | Faulty) = 0.70 is not P(Faulty | High). To reverse the condition we use Bayes' rule (Chapter 6).

Filtering: predict → observe → correct → normalise

belief′(j) = α · O_j(eₜ) · Σᵢ belief(i) · T(i→j) α = normalise to sum 1

Time 1, reading HIGH: Healthy 0.80·0.20 = 0.16; Faulty 0.20·0.70 = 0.14; total 0.30 → [53.3%, 46.7%].

Time 2, HIGH again:

Predict with T: Healthy 0.5333·0.90 + 0.4667·0.20 = 0.5733; Faulty 0.5333·0.10 + 0.4667·0.80 = 0.4267.
Correct with O(High): [0.5733·0.20, 0.4267·0.70] = [0.1147, 0.2987].
Normalise by 0.4133 → [27.7%, 72.3%]. Two highs make a fault much more likely.

Prediction without new readings: one step ahead from [0.277, 0.723] gives Healthy 0.277·0.90 + 0.723·0.20 = 39.4%, Faulty 60.6%.

Smoothing: later evidence revises the past

Filtering asks "What is happening now?" using readings up to now. Smoothing asks "What was happening then?" using earlier and later readings. It is computed with the forward–backward algorithm: a forward message (evidence up to t) times a backward message (how well later readings fit each state).

Example: readings HIGH, HIGH. What was the state at time 1?

Backward message for Healthy: P(High₂ | H₁) = 0.90·0.20 + 0.10·0.70 = 0.25.
For Faulty: P(High₂ | F₁) = 0.20·0.20 + 0.80·0.70 = 0.60.
Combine with the filtered time-1 belief: [0.5333·0.25, 0.4667·0.60] = [0.1333, 0.28], normalised to [32.3%, 67.7%].

The second HIGH reading made us more suspicious about time 1 as well: from 46.7% up to 67.7% Faulty.

Viterbi: the single most likely path

Sometimes we want one best complete explanation, a sequence of hidden states. For HIGH, HIGH there are 4 paths:

Path	π · O · T · O	Joint score
Healthy, Healthy	0.80 · 0.20 · 0.90 · 0.20	0.0288
Healthy, Faulty	0.80 · 0.20 · 0.10 · 0.70	0.0112
Faulty, Healthy	0.20 · 0.70 · 0.20 · 0.20	0.0056
Faulty, Faulty	0.20 · 0.70 · 0.80 · 0.70	0.0784 ★

With many readings, listing all paths is exponential. The Viterbi algorithm keeps, for each state, only the best path ending there:

δ₁(j) = π(j) · O_j(e₁) δₜ(j) = O_j(eₜ) · maxᵢ [ δₜ₋₁(i) · T(i→j) ] remember the winning i, then backtrack δ₂(H) = max(0.16·0.90, 0.14·0.20)·0.20 = 0.0288 δ₂(F) = max(0.16·0.10, 0.14·0.80)·0.70 = 0.0784

SUM vs MAX

Filtering sums over all ways to reach a state and returns probabilities of the current state. Viterbi takes the max and returns one best whole path. Picking the most likely filtered state at each time is not the same as Viterbi.

TRY IT! Feed the sensor: filtering, smoothing and Viterbi live

Try HIGH, HIGH: you'll see the lecture's numbers (72.3%, 67.7%, path F, F). Then add NORMAL, NORMAL and watch the belief recover, while smoothing rewrites the past.

Task	Question	HIGH, HIGH example
Filtering	What is the state now?	Faulty 72.3%
Prediction	What may the next state be?	Faulty 60.6%
Smoothing	What was the earlier state?	Faulty 67.7% at time 1
Viterbi	Which whole path is best?	Faulty, Faulty

REAL WORLD

Machine monitoring: hidden equipment condition, observed temperature and vibration. Robot localisation: hidden position, observed noisy distance readings. Speech recognition: hidden phonemes, observed acoustic features (classic HMM speech systems ran on Viterbi). Bioinformatics: hidden gene regions, observed DNA letters.

ASSUMPTIONS

The next state depends only on the current state; each observation depends only on the current state; probabilities are fixed over time. The model is useful only if it represents the system well enough for the task.

DID YOU KNOW?

Andrew Viterbi published his algorithm in 1967 for decoding noisy radio signals. He later co-founded Qualcomm, and the same algorithm runs inside billions of phones.

MINI-QUIZ

1. Which HMM table tells you how likely a HIGH reading is when the machine is Faulty?

Emissions connect hidden states to observations; transitions connect hidden states over time.

2. "Reassess yesterday's warning after today's alarm" is…

Smoothing uses later evidence to estimate an earlier state.

3. Viterbi differs from filtering because it uses…

Viterbi also returns one whole path. Same model, different goal: the best complete sequence instead of current-state probabilities.

Manga page: It's probably faulty! / But should they STOP the machine? That's a decision...