Hidden Markov Models › Summary

Hidden Markov Models provide a probabilistic framework for sequence labeling. The model jointly models hidden state sequences (like POS tags) and observable output sequences (like words), learning statistical patterns for how states transition and what observations each state generates. The framework needs only three counting operations, tallying initial state frequencies, tag bigram frequencies, and word-tag co-occurrence frequencies, to build a model capable of resolving linguistic ambiguity.

Key takeaways:

• HMM components include states, observations, initial probabilities, transition probabilities, and emission probabilities. These five elements fully specify the model. The transition matrix captures syntax; the emission matrix captures lexical associations; the initial distribution captures positional tendencies.
• The Markov assumption says each state depends only on the previous state, not the full history. This enables efficient algorithms but limits the model's ability to capture long-range dependencies. Higher-order HMMs extend the context window at the cost of exponentially more parameters.
• The output independence assumption says each observation depends only on its current state. This prevents the model from using surrounding context to disambiguate emissions, which is one of the primary motivations for Conditional Random Fields.
• Maximum likelihood estimation learns parameters by counting occurrences in annotated data. The estimates are straightforward frequency ratios, making HMMs fast to train even on large corpora. Smoothing handles unseen word-tag pairs that would otherwise have zero probability.
• Decoding finds the most likely state sequence given observations. Greedy decoding is fast but suboptimal; the Viterbi algorithm (next chapter) finds the globally optimal sequence in $O(n \cdot |S|^2)$ time using dynamic programming.
• HMM limitations include inability to use rich contextual features, difficulty with long-distance dependencies, and weak handling of unknown words. These motivated the development of Conditional Random Fields and, eventually, neural sequence models.
• Historical significance: HMMs established the sequence labeling paradigm, enabled the first high-accuracy POS taggers, and provided the conceptual foundation for every subsequent structured prediction model in NLP.

HMMs exemplify a recurring theme in NLP: strong independence assumptions enable efficient algorithms, but real language violates these assumptions in important ways. The tension between tractability and expressive power drives model development forward. The next chapter covers the Viterbi algorithm, which finds optimal sequences in $O(n \cdot |S|^2)$ time, and subsequent chapters introduce CRFs, which relax HMM's independence assumptions while preserving the structured prediction framework that HMMs established.