The Baum–Welch Algorithm
When you have observation sequences but no hidden labels, Baum–Welch (an instance of the EM algorithm) estimates the HMM parameters (initial distribution), (transition matrix), and (emission matrix).
The loop alternates between two steps until the log-likelihood converges:
- E-step: given current parameters, compute how responsible each hidden state (and each transition) is for the observed data.
- M-step: re-estimate as normalized expected counts.
Notation and key quantities
An HMM with hidden states emits an observation sequence . The forward variable from the forward algorithm captures all information up to and including time :
Its value: the product (defined below) equals — the joint probability of the full observation sequence and being in state at time . Normalizing across states gives the state occupancy . Baum–Welch additionally needs a backward pass.
The backward pass
The E-step starts by running a recursion backward through the sequence.
Define — the probability of the future observations given the current state:
The recursion runs backwards from to : each state's backward value is a sum over where it could transition next, weighted by the emission probability of the next observation.
Computing the state occupancy γ
Combine forward and backward to get the probability of being in state at time , given the whole sequence:
The numerator combines everything before-and-including () with everything after (); the denominator normalizes over all states.
Computing the transition counts ξ
We also need the expected transitions, not just the per-state occupancies.
The probability of transitioning at time :
Read the numerator left to right: arrive at state by time , take the transition to , emit the next observation from , then account for the rest of the sequence.
The M-step parameter re-estimation
With the expected counts in hand, re-estimate every parameter as a ratio of expected counts:
In words:
- — expected fraction of sequences starting in state
- — expected number of transitions, divided by expected number of times in state
- — expected number of times state emitted symbol , divided by expected time in state
Watch it run
A two-state HMM (Rain / Sun) emitting umbrella-or-not over three days, small enough that every , , and fits on one screen:
Baum–Welch — forward, backward, and re-estimation from expected counts
A two-state HMM — Rain and Sun — that emits "umbrella" (U) or "none" (N). The observed sequence is (U, U, N): two umbrella days then a dry one. The hidden states are never observed, which is the whole difficulty; Baum–Welch has to infer both the states *and* the parameters that generated them.
| Rain | Sun | |
|---|---|---|
| Rain | 0.700 | 0.300 |
| Sun | 0.300 | 0.700 |
| U | N | |
|---|---|---|
| Rain | 0.900 | 0.100 |
| Sun | 0.200 | 0.800 |
Initialization already leans the right way (Rain emits U with 0.9), but nothing forces the hidden path — the algorithm still has to work out how much each state explains each day.
The full E-step and M-step on a 2-state HMM over three observations, small enough that every α, β, γ and ξ is on screen. The point to watch is why *both* passes are needed: α carries the past, β carries the future, and only their product gives the posterior over hidden states given the whole sequence. The final step iterates to convergence — log P(x) rises monotonically, and the parameters sharpen to the point of overfitting a single short sequence.
What to notice as you step:
- Why there are two passes. knows only the past, only the future. Neither is a posterior on its own; the product, normalized, is. Watch swing to Sun on the dry third day even though the transition matrix prefers staying put — evidence from the end of the sequence reaching backwards.
- Why exists at all. tells you where the chain was; re-estimating needs to know where it went. That is a different posterior and needs its own quantity.
- The M-step is just counting. Every re-estimate is expected-count over expected-total — precisely the maximum-likelihood estimator you would write down if the hidden states had been observed.
- The final step iterates to convergence. rises every time, and and sharpen toward 0/1 — a single 3-step sequence cannot support a 2-state HMM, so the model overfits it exactly. Real training sums expected counts across many sequences before normalizing.
Connection to Gaussian Mixture Models
It's GMMs with a Markov chain
This is the same E-step/M-step loop as Gaussian Mixture Models — HMMs are essentially "GMMs with a Markov chain tying the components across time." γ plays the role of the GMM responsibilities; the M-step is the same weighted-count normalization.
Convergence guarantees and pitfalls
- Each iteration provably increases the likelihood (the standard EM guarantee), but only to a local optimum. Use multiple random restarts.
- Multiplying many probabilities underflows fast; real implementations run all recursions in log space (or rescale , at each step).
hmmlearnhandles this for you. - With multiple training sequences, sum the expected counts across sequences before normalizing.
Related concepts
- Hidden Markov Models: the model Baum–Welch trains
- The EM Algorithm: the general framework
- Gaussian Mixture Models: the static-data analogue