Baum-Welch and EM

Letting the model learn its own numbers

So far we assumed that we knew $\pi$, $A$ and $B$. In real data we do not: we only have the observations. The Baum-Welch algorithm learns the numbers from the data. It is an example of expectation-maximisation (EM), and it works by repeating two steps. In the E-step, use the current numbers and the forward-backward algorithm to work out how likely each hidden state and each state switch was on each day. In the M-step, re-estimate the numbers by counting, but with these probabilities instead of whole counts.

Here $\gamma_t(i)$ is the smoothed probability of state $i$ on day $t$ and $\xi_t(i,j)$ is the smoothed probability of moving from $i$ to $j$ between day $t$ and $t+1$. So the new $A_{ij}$ is the expected number of $i\to j$ moves divided by the expected number of days spent in $i$. Two facts are worth knowing. The log-likelihood of the data never decreases from one EM round to the next, so you can stop when it stops improving. But EM only climbs to the nearest peak, so it can end on a local maximum, and different starting values can give different answers. In practice one tries several starts and keeps the best.

• E-step: with the current numbers, compute $\gamma$ and $\xi$ by forward-backward.
• M-step: re-estimate $\pi$, $A$ and $B$ as expected counts divided by expected totals.
• The log-likelihood never falls, but EM can stop at a local maximum: try several starts.

Lab · what's graded

• Expected calm days10 pts
• A new emission probability15 pts
• A new start probability10 pts
• A new transition probability15 pts
• What EM guarantees15 pts
• One EM round10 pts
• Match the vocabulary10 pts
• Why starts matter15 pts