hidden Markov models and the EM algorithm
Many systems hide their true state and let you see only noisy clues about it: you cannot directly observe a speaker's intended words, only the sound; you cannot see the weather a far city is having, only what a friend there happens to do. A hidden Markov model (HMM) is the standard probabilistic machine for this. It assumes an unseen sequence of states that evolves as a Markov chain — each state depends only on the previous one — while each hidden state emits an observable output through a noise distribution. You see the outputs; you must infer the states.
An HMM has three pieces: transition probabilities (how the hidden state moves step to step), emission probabilities (how each hidden state produces an observation), and an initial state distribution. With these, classic algorithms answer the practical questions exactly: the forward-backward algorithm computes the probability of the observed sequence and the posterior over each hidden state, and the Viterbi algorithm finds the single most likely hidden path. But there is a chicken-and-egg snag when you must LEARN the probabilities from data: to estimate the transition and emission parameters you would need to know the hidden states, but to infer the hidden states you need the parameters. The EM (expectation-maximization) algorithm breaks the loop. It alternates two steps: the E-step uses the current parameters to compute the posterior distribution over the hidden states (the expected 'soft' assignments), and the M-step then re-estimates the parameters by maximum likelihood as if those soft assignments were the data. Iterating is guaranteed to never decrease the likelihood, so it climbs steadily toward a (local) maximum.
These ideas power speech recognition, part-of-speech tagging, gene finding, and finance, and EM itself is far broader than HMMs — it is THE general recipe for maximum likelihood with hidden or missing data, including Gaussian mixture models and naive Bayes with unlabeled data. The honest caveats: EM only finds a LOCAL maximum, so the starting point matters and multiple restarts are wise; it can converge slowly; and an HMM's whole power rests on its strong assumptions (the Markov property for the hidden states and conditional independence of each observation given its state), which real data may violate.
A friend in another city texts you daily what she did — walk, shop, or clean — and you want to infer the hidden weather (rainy or sunny). With transition probabilities (rainy days tend to follow rainy days) and emission probabilities (she cleans more when it rains), the Viterbi algorithm reconstructs the most likely weather sequence from her activities alone. If you do not even know those probabilities, EM learns them by alternating: guess the weather, re-estimate the probabilities, repeat.
An HMM infers hidden states from noisy outputs; EM learns the parameters when states are unobserved.
EM is guaranteed to never decrease the likelihood but only converges to a LOCAL maximum, so the initialization matters and several restarts are wise; an HMM is also only as good as its Markov and conditional-independence assumptions.