Hidden Markov Models: Forward Probabilities, Viterbi and Tagging
Published:
Factor the joint distribution
For observed words \(x_{1:T}\) and hidden tags \(y_{1:T}\), a first-order HMM uses an initial distribution \(\pi\), transition probabilities \(a_{ij}\) and emissions \(b_j(x)\):
Here we condition on sequence length and omit an explicit end transition. A model of variable-length sequences needs its own termination treatment. Each transition row and each state’s emission distribution must normalise.
The assumptions are explicit: the next tag depends only on the previous tag, and the current observation depends only on the current tag. A word can still be ambiguous because several states may emit it. Context changes which path is probable.
Sum over paths with the forward algorithm
Define \(\alpha_t(j)=P(x_{1:t},y_t=j)\). Then
| The observation likelihood is \(\sum_j\alpha_T(j)\). Every partial path ending in state \(j\) contributes to this sum. There are exponentially many complete paths but only $$T | Y | \(states in the dynamic program, each considering\) | Y | \(predecessors:\)O(T | Y | ^2)$$ time. |
Maximise a path with Viterbi
Replace the sum with a maximum:
Store the predecessor attaining each maximum. Starting from the best final state and following those backpointers recovers a complete path. Keeping only the maximum values gives the path score but not the labels that achieved it.
A two-word calculation
Use states N and V, initial probabilities 0.6 and 0.4, and transitions N→N=0.3, N→V=0.7, V→N=0.8, V→V=0.2. Let emissions for robots be 0.5 under N and 0.1 under V; emissions for move are 0.1 under N and 0.6 under V. Remaining emission mass belongs to other vocabulary items.
For the first word, both algorithms start with N=0.30 and V=0.04. At the second word:
| End state | Forward value | Viterbi value |
|---|---|---|
| N | \(0.1(0.30\cdot0.3+0.04\cdot0.8)=0.0122\) | \(0.1\max(0.09,0.032)=0.009\) |
| V | \(0.6(0.30\cdot0.7+0.04\cdot0.2)=0.1308\) | \(0.6\max(0.21,0.008)=0.126\) |
The observation likelihood is 0.143. The best path is N→V with joint probability 0.126. Its posterior probability given the observations is \(0.126/0.143\approx0.881\). The best path score and total likelihood are visibly different numbers.
Training and numerical stability
With labelled sequences, estimate transitions and emissions from counts with a declared smoothing policy. With unlabelled sequences, forward–backward computes expected counts for an EM procedure commonly called Baum–Welch. Latent states learned without labels are not guaranteed to correspond to familiar grammatical tags.
Products of many probabilities underflow. Compute Viterbi in log space; compute forward sums with log-sum-exp or a consistent scaling scheme. Replacing a sum by a maximum for numerical convenience changes the question being answered.
Tokenwise posterior decoding chooses the most probable tag at each position. It need not equal the most probable complete path and can violate path constraints. Use the output criterion that matches the application. The CRF chapter keeps structured decoding while modelling the labels conditional on the entire input.
Recap
- An HMM factorises a joint distribution over observations and states.
- Forward sums over paths; Viterbi finds one highest-probability path.
- Backpointers recover the path that attains a maximum.
- Log-space arithmetic and a defined termination policy are essential.
References
- Rabiner, L. R. A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. Proceedings of the IEEE, 1989.
- Bird, Klein and Loper. Categorizing and Tagging Words.