Hidden Markov Models › Limitations and Impact

HMMs were the dominant approach to sequence labeling from the 1980s through the early 2000s. They remain instructive for understanding probabilistic sequence models and provide a foundation for more advanced techniques. To appreciate why HMMs were eventually replaced, you need to understand the abstract limitations and the concrete situations where those limitations cause real errors. And to appreciate why they lasted so long, you need to understand what they enabled that was simply not possible before.

The independence assumptions that make HMMs tractable also limit their power. The emission independence assumption is particularly restrictive: an HMM cannot condition on neighboring words when deciding what tag to emit. Consider the word "set." In "the set of numbers," it's a noun. In "set the table," it's a verb. An HMM can only use transition probabilities to disambiguate, ignoring the direct evidence from surrounding words like "the" before "set" or "table" after "set." The transition probabilities capture some of this information indirectly (if the previous tag is DET, a NOUN is more likely than a VERB), but they cannot capture word-specific context. The word "the" before "set" is strong evidence for a noun, but an HMM encodes only the tag of the previous word, not the word itself.

The Markov assumption also causes problems for long-distance dependencies. In "The dog that the cat chased runs," the verb "runs" must agree with "dog," but an HMM only sees the immediately preceding "chased." Higher-order HMMs (conditioning on two or three previous tags) help but create exponentially more parameters to estimate. In practice, second-order HMMs offer a meaningful improvement over first-order, but third-order and beyond suffer from data sparsity: the required counts simply do not accumulate reliably even in large corpora.

Unknown words present another persistent challenge. With Laplace smoothing, unknown words get similar emission probabilities from all tags, forcing the model to rely on transitions for disambiguation. But transition patterns alone often carry insufficient information. Consider the sentence "The zylothene process requires careful monitoring." The word "zylothene" is unknown, and the tagger must guess its tag from context. The preceding DET suggests a noun or adjective, which is helpful. But without any lexical signal from the word itself, distinguishing noun from adjective is difficult. Modern approaches address this by using character-level features: words ending in "-tion" are almost always nouns, words starting with a capital mid-sentence are often proper nouns, and words ending in "-ness" or "-ment" are reliably nouns. HMMs can incorporate such features only awkwardly, by creating special pseudo-word categories and routing unknown words through them.

Feature independence is perhaps the deepest limitation. HMMs encode the feature "current word" through the emission distribution, and that is essentially the only input feature available. A CRF, by contrast, can include arbitrary features of the input: the current word, surrounding words, word prefixes and suffixes, capitalization, whether the word appears in a gazetteer, and so on. All of these features can influence the tag prediction jointly, without assuming independence. This flexibility is why CRFs became the preferred model once the computational machinery for training them was worked out.

Despite these limitations, HMMs achieved remarkable success and enabled practical NLP systems for the first time. Their contributions extend well beyond POS tagging.

The Viterbi algorithm made efficient exact inference possible, allowing HMM taggers to process text at thousands of words per second. This speed made NLP practical for large document collections. Before Viterbi, sequence labeling was either heuristic or computationally prohibitive at scale. The algorithm's $O(n \cdot |S|^2)$ complexity meant that tagging a 100-word document with 40 tags required only 160,000 operations, fast enough to process millions of documents in reasonable time.

The forward-backward algorithm enabled unsupervised learning from raw text. Given an HMM architecture with a fixed number of states but no labeled training data, the Baum-Welch algorithm iteratively re-estimates parameters to maximize the likelihood of the observed text. You could discover latent structure in tag sequences without any human annotation. While unsupervised HMMs never matched supervised accuracy, they opened up possibilities for low-resource languages where annotated corpora did not exist, and for tasks where defining labels ahead of time was difficult.

The probabilistic framework integrated naturally with other statistical models. HMM outputs could feed into named entity recognizers, parsers, and information extraction systems, with probabilities propagating through the pipeline. When you have a full probability distribution over tag sequences rather than a single deterministic output, downstream systems can weight competing hypotheses appropriately rather than treating the tagger's output as certain.

HMMs also established the paradigm of sequence labeling as a structured prediction problem. They formalized how labels depend on both the inputs and other labels. This structured view led directly to CRFs, which relax the emission independence assumption while preserving the Markov structure of transitions. From CRFs, the conceptual lineage runs to BiLSTM-CRF models, where a bidirectional LSTM replaces the emission distribution with a contextual neural encoder, and then to transformer-based taggers like BERT fine-tuned on sequence labeling tasks. Every step in this lineage builds on the HMM's foundational insight that the joint probability over a label sequence matters alongside the probability of each label in isolation.