HMM and Viterbi POS Tagging
On this page
HMM and Viterbi POS Tagging
Recall first
In an HMM tagger, what is a transition probability and what is an emission probability? Why can greedy tagging lose the best sentence-level sequence?
First principles
A Hidden Markov Model treats tags t₁…tₙ as hidden states and words w₁…wₙ as observations. A first-order HMM scores a path as
P(t₁…tₙ,w₁…wₙ) = ∏ᵢ P(tᵢ|tᵢ₋₁) P(wᵢ|tᵢ)
with a start/end state. The transition model captures tag sequence regularities; the emission model captures which words a tag tends to generate. The model is generative: it models joint probability and uses Bayes/argmax to choose tags.
Viterbi recurrence
Let V_i(t) be the best score for the first i words ending in tag t. Then
V_i(t) = max_{t'} V_{i−1}(t') P(t|t') P(w_i|t)
and store the backpointer argmax t'. Initialize from START, iterate left to right, terminate with END, then backtrace. Use log probabilities in real implementations to avoid underflow; multiplication becomes addition and max is unchanged.
Worked trace (toy, two tags). For dogs bark, suppose P(N|START)=0.6, P(V|START)=0.4; P(dogs|N)=0.8, P(dogs|V)=0.1; transitions P(V|N)=0.7, P(N|V)=0.3; emissions P(bark|V)=0.6, P(bark|N)=0.1. After dogs: V₁(N)=.48, V₁(V)=.04. For bark ending V, candidates are .48×.7×.6=.2016 and .04×.3×.6=.0072; choose predecessor N. Backtrace gives N V. The table is the algorithm; do not choose each word’s most likely tag independently.
Issues and assumptions
First-order Markov history is restrictive; MLE counts suffer sparsity and zero probabilities; unknown words need suffix/shape classes or smoothing; emissions assume conditional independence of words given tags; training annotations may be domain-specific. Viterbi finds the best path under the model, not necessarily the linguistically true path.
Exercise — reveal after answering
Why store a backpointer at every cell?
Answer: The best score records only a value; the backpointer records which predecessor achieved it, allowing the complete optimal path to be reconstructed after the final state.
Exam lens
Draw the trellis, label transition/emission, write initialization–recurrence–termination–backtrace, and state log-space implementation. Include HMM limitations.
Rapid revision checklist
- Define hidden tags and observed words.
- Write the factorization and recurrence.
- Explain backpointers and log probabilities.
- List first-order, independence, sparsity, and OOV issues.
Key takeaways
- HMM POS tagging is generative sequence decoding.
- Viterbi is dynamic programming over tag paths.
- The best model path is only as good as its probability assumptions and data.