The Baum–Welch AlgorithmOpen in Colab

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 π\pi (initial distribution), AA (transition matrix), and BB (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 π,A,B\pi, A, B as normalized expected counts.

Notation and key quantities

An HMM with NN hidden states emits an observation sequence x=(x1,…,xT)\mathbf{x} = (x_1, \ldots, x_T). The forward variable from the forward algorithm captures all information up to and including time tt:

αt(i)=P(x1,…,xt, zt=i)\alpha_t(i) = P(x_1, \ldots, x_t,\, z_t = i)

Its value: the product αt(i) βt(i)\alpha_t(i)\,\beta_t(i) (defined below) equals P(x, zt=i)P(\mathbf{x},\, z_t = i) — the joint probability of the full observation sequence and being in state ii at time tt. Normalizing across states ∑kαt(k)βt(k)=P(x)\sum_k \alpha_t(k)\beta_t(k) = P(\mathbf{x}) gives the state occupancy γt(i)=P(zt=i∣x)\gamma_t(i) = P(z_t=i \mid \mathbf{x}). Baum–Welch additionally needs a backward pass.

The backward pass

The E-step starts by running a recursion backward through the sequence.

Define βt(i)=P(xt+1,…,xT∣zt=i)\beta_t(i) = P(x_{t+1}, \ldots, x_T \mid z_t = i) — the probability of the future observations given the current state:

βT(i)=1(base case)\beta_T(i) = 1 \quad \text{(base case)} βt(i)=∑j=1NAij bj(xt+1) βt+1(j)\beta_t(i) = \sum_{j=1}^N A_{ij}\, b_j(x_{t+1})\, \beta_{t+1}(j)

The recursion runs backwards from t=Tt = T to t=1t = 1: 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 ii at time tt, given the whole sequence:

γt(i)=P(zt=i∣x)=αt(i) βt(i)∑k=1Nαt(k) βt(k)\gamma_t(i) = P(z_t = i \mid \mathbf{x}) = \frac{\alpha_t(i)\,\beta_t(i)}{\sum_{k=1}^N \alpha_t(k)\,\beta_t(k)}

The numerator combines everything before-and-including tt (α\alpha) with everything after tt (β\beta); 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 i→ji \to j at time tt:

ξt(i,j)=P(zt=i, zt+1=j∣x)=αt(i) Aij bj(xt+1) βt+1(j)∑k,lαt(k) Akl bl(xt+1) βt+1(l)\xi_t(i,j) = P(z_t=i,\, z_{t+1}=j \mid \mathbf{x}) = \frac{\alpha_t(i)\, A_{ij}\, b_j(x_{t+1})\, \beta_{t+1}(j)}{\sum_{k,l} \alpha_t(k)\, A_{kl}\, b_l(x_{t+1})\, \beta_{t+1}(l)}

Read the numerator left to right: arrive at state ii by time tt, take the transition to jj, emit the next observation from jj, 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:

π^i=γ1(i),A^ij=∑t=1T−1ξt(i,j)∑t=1T−1γt(i),b^j(k)=∑t: xt=kγt(j)∑t=1Tγt(j)\hat{\pi}_i = \gamma_1(i), \qquad \hat{A}_{ij} = \frac{\displaystyle\sum_{t=1}^{T-1} \xi_t(i,j)}{\displaystyle\sum_{t=1}^{T-1} \gamma_t(i)}, \qquad \hat{b}_j(k) = \frac{\displaystyle\sum_{t:\, x_t = k} \gamma_t(j)}{\displaystyle\sum_{t=1}^T \gamma_t(j)}

In words:

  • π^i\hat{\pi}_i — expected fraction of sequences starting in state ii
  • A^ij\hat{A}_{ij} — expected number of i→ji \to j transitions, divided by expected number of times in state ii
  • b^j(k)\hat{b}_j(k) — expected number of times state jj emitted symbol kk, divided by expected time in state jj

Watch it run

A two-state HMM (Rain / Sun) emitting umbrella-or-not over three days, small enough that every α\alpha, β\beta, γ\gamma and ξ\xi fits on one screen:

Baum–Welch — forward, backward, and re-estimation from expected counts

1/16

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.

python
1def baum_welch(x, pi, A, B):
2 # E-step: forward, then backward
3 a[0] = pi * B[:, x[0]]
4 for t in range(1, T):
5 a[t] = (a[t-1] @ A) * B[:, x[t]]
6 b[T-1] = 1
7 for t in range(T - 2, -1, -1):
8 b[t] = A @ (B[:, x[t+1]] * b[t+1])
9
10 # occupancy and transition posteriors
11 g = a * b / (a * b).sum(axis=1)
12 xi[t,i,j] = (a[t,i] * A[i,j]
13 * B[j,x[t+1]] * b[t+1,j]) / P
14
15 # M-step: normalized expected counts
16 pi = g[0]
17 A = xi.sum(0) / g[:-1].sum(0)[:, None]
18 B = counts(g, x) / g.sum(0)[:, None]
19 return pi, A, B
state
observation sequence
Ut1
Ut2
Nt3
A — transition
RainSun
Rain0.7000.300
Sun0.3000.700
B — emission
UN
Rain0.9000.100
Sun0.2000.800
π — initial
Rain → 0.500Sun → 0.500

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. αt(i)\alpha_t(i) knows only the past, βt(i)\beta_t(i) only the future. Neither is a posterior on its own; the product, normalized, is. Watch γ3\gamma_3 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 ξ\xi exists at all. γ\gamma tells you where the chain was; re-estimating AA 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. log⁡P(x)\log P(\mathbf{x}) rises every time, and AA and BB 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 αt\alpha_t, βt\beta_t at each step). hmmlearn handles this for you.
  • With multiple training sequences, sum the expected counts across sequences before normalizing.

Related concepts

Concept neighbourhood

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

Referenced by
The Baum–Welch AlgorithmHidden Markov ModelsThe EM AlgorithmGaussian Mixture Models