Hidden Markov Models

Sequence labeling tasks like POS tagging require more than just looking up each word in a dictionary. The word "bank" could be a noun (a financial institution) or a verb (to bank on something). The word "flies" could be a noun (the insects) or a verb (the action of flying). Context determines the correct label, and that context often spans multiple words in a sequence.

Hidden Markov Models (HMMs) provide a principled probabilistic framework for sequence labeling. An HMM models two interacting processes: a hidden sequence of states (the tags you want to predict) and an observable sequence of outputs (the words you can see). The model learns statistical patterns about how states transition to each other and how each state generates observations. Given a new sentence, the HMM uses these learned patterns to infer the most likely hidden sequence.

Think of an HMM as a kind of hidden storyteller. Imagine a narrator who moves secretly through a sequence of rooms: the tags: and calls out a word from each room. You can hear the words, but you cannot see which room the narrator is in. Your job is to figure out the narrator's path through the rooms based solely on the words you hear. The HMM formalizes exactly this: it provides probabilities that describe which rooms connect to which, and which words get called out from each room. Given a sequence of heard words, the model can then work backwards to estimate the most probable path.

The main insight behind HMMs is that language is not a bag of independent tokens. When you see the word "the," you know with high confidence that a noun phrase is coming. When you see a verb, you know it probably follows a noun phrase. These regularities exist at two levels simultaneously: the syntactic level (how tags relate to one another) and the lexical level (which words are associated with which tags). HMMs capture both levels in a single probabilistic model, and the interaction between them is what makes disambiguation possible.

This chapter covers HMM components and their probabilistic foundations. You'll learn how to estimate HMM parameters from annotated data, understand the key assumptions that make HMMs tractable, and implement a working POS tagger. We'll also examine where HMMs succeed and where they fall short, setting up the motivation for more advanced models like Conditional Random Fields. By the end, you will have a working intuition for why this 1960s signal-processing technique became the backbone of practical NLP systems for nearly two decades.

An HMM defines a joint probability distribution over two sequences: a hidden state sequence and an observable output sequence. In POS tagging, the hidden states are the part-of-speech tags, and the observations are the words. The hidden states are "hidden" in a literal sense: you never observe them directly. You see only the output words, and everything about the underlying grammar must be inferred from those observations.

The model has five components:

• States ($S$): A finite set of hidden states. For POS tagging, these are the tags like NN, VB, DT, JJ. The state set defines the vocabulary of labels the model can assign.
• Observations ($V$): A finite vocabulary of observable symbols. These are the words in your corpus. Every word you will ever encounter at training or test time must belong to this set (with unknown words handled separately by smoothing).
• Initial probabilities ($\pi$): The probability of starting in each state. For sentences, this captures which tags typically begin sentences. English sentences far more often begin with a determiner or noun than with a verb or preposition, and $\pi$ encodes exactly that regularity.
• Transition probabilities ($A$): The probability of moving from one state to another. This captures tag-to-tag patterns like "determiners are often followed by nouns." The full transition matrix $A$ encodes a compressed statistical description of English syntax.
• Emission probabilities ($B$): The probability of generating each observation from each state. This captures which words are associated with which tags. The word "the" has very high emission probability from DET and near-zero from VERB; "run" has meaningful probability from both NOUN and VERB. This reflects lexical ambiguity.

The beauty of this decomposition is that each component captures a different kind of linguistic knowledge. The transition matrix captures syntax: how grammatical categories sequence. The emission matrix captures lexical associations: which words belong to which categories. The initial distribution captures positional tendencies: how sentences typically begin. Together they form a compact and learnable representation of a language's statistical structure.

Let's define these components mathematically. For a state sequence $s_1, s_2, \ldots, s_n$ and observation sequence $o_1, o_2, \ldots, o_n$, we define three probability distributions.

The initial probability captures how likely each state is to appear at the start of a sequence:

where $\pi_i$ is the probability that the first state in the sequence is state $i$.

The transition probability captures how states follow one another:

where:

• $a_{ij}$: the probability of transitioning from state $i$ to state $j$
• $s_t$: the state at position $t$ in the sequence
• $s_{t-1}$: the state at the previous position

The emission probability captures how each state generates observations:

where:

• $b_i(o)$: the probability of observing symbol $o$ when in state $i$
• $o_t$: the observation at position $t$
• $s_t$: the hidden state at position $t$

These three distributions fully characterize an HMM's behavior. The initial probabilities determine how sequences start, transitions determine how states evolve, and emissions determine what we observe. Notice that the parameters are not hand-crafted: they are estimated automatically from annotated data. This is what makes HMMs powerful. You do not need a linguist to write grammar rules. You need labeled sentences, and the model learns the statistical regularities on its own.

To make these concepts concrete, let's build a toy HMM for POS tagging. We'll use just three states (determiner, noun, verb) and five words, which is enough to see the key patterns while keeping the numbers tractable.

The transition matrix encodes grammatical patterns. Determiners (DT) are followed by nouns (NN) with probability 0.8, capturing the common English pattern "the dog" or "a cat." The emission matrix encodes lexical associations. The word "the" is emitted by DT with probability 0.9, while "runs" is emitted by VB with probability 0.5.

In practice, these probabilities need not be set by hand. The numbers above are illustrative, but when you train on a large corpus the same patterns emerge automatically from counting. The model "discovers" that determiners precede nouns because the data contains thousands of examples of exactly that pattern. This is maximum likelihood estimation at its simplest: the best description of the data is the one that assigns the highest probability to the observed events.

HMMs make two key independence assumptions that simplify computation. These assumptions trade off modeling power for tractability. Without them, exact inference over sequences would require considering every possible combination of hidden states, which grows exponentially with sequence length. With them, dynamic programming algorithms like Viterbi can find exact solutions in polynomial time. Understanding these assumptions deeply will help you know when HMMs are appropriate and when you need a more expressive model.

The first assumption is the Markov property: the probability of transitioning to a state depends only on the current state, not on the full history.

where:

• $s_t$: the state at position $t$ (what we want to predict)
• $s_1, s_2, \ldots, s_{t-1}$: the full history of previous states
• $s_{t-1}$: only the immediately preceding state

The equation states that knowing the entire history provides no additional information beyond knowing just the previous state. For POS tagging, this means the probability of a tag depends only on the previous tag, not on tags from earlier in the sentence. If the previous tag is DT (determiner), the probability of NN (noun) is the same regardless of what came before the determiner.

This is a strong assumption. Consider "the old old man" versus "the very old man." After seeing "old" once, the probability of another adjective might differ from seeing "old" for the first time. A first-order HMM cannot capture this distinction. Higher-order HMMs condition on the previous two or three tags rather than just one, which helps. A second-order HMM replaces $P(s_t \mid s_{t-1})$ with $P(s_t \mid s_{t-2}, s_{t-1})$, giving the model memory of the last two tags. The downside is that the transition table grows quadratically with tag set size: for $|S|$ tags, a first-order model has $|S|^2$ transition parameters, while a second-order model has $|S|^3$. For a 40-tag set like Penn Treebank, that difference is 1,600 versus 64,000 parameters, requiring substantially more training data for reliable estimates.

The second assumption is output independence: the probability of an observation depends only on the current state, not on other observations or states.

where:

• $o_t$: the observation at position $t$ (the word we see)
• $s_1, \ldots, s_n$: all hidden states in the sequence
• $o_1, \ldots, o_{t-1}, o_{t+1}, \ldots, o_n$: all other observations (past and future words)
• $s_t$: only the current hidden state

The equation states that the probability of emitting a particular word depends solely on the current tag, not on any surrounding context. For POS tagging, this means the word "bank" has the same emission probability from the NN state regardless of surrounding words. The model cannot use the context "river bank" to increase the probability of the noun interpretation, nor can it use "bank account" to do the same. All disambiguation must happen indirectly through transition probabilities.

This is perhaps the most consequential limitation of HMMs for NLP. In natural language, the meaning and function of a word are heavily influenced by its neighbors. The word "light" is more likely an adjective after "a" and before "lunch" than after "switch" and before "on." A model that ignores this surrounding evidence will make systematic errors on ambiguous words. Conditional Random Fields, which you will study in a later chapter, address exactly this limitation by allowing the model to condition on arbitrary features of the surrounding context when making labeling decisions.

These assumptions enable efficient algorithms for inference and learning. The Viterbi algorithm (covered in the next chapter) finds the most likely state sequence in $O(n \cdot |S|^2)$ time, where $n$ is the sequence length and $|S|$ is the number of states. Without these assumptions, exact inference would require exponential time. The Markov assumption is what allows the Viterbi algorithm to break the global optimization into independent subproblems: once you know the best way to reach state $i$ at position $t$, you do not need to remember how you got there to compute the best way to reach any state at position $t+1$. That "forgetfulness" is not a bug; it is the computational feature that makes the algorithm feasible.

Given an HMM, how do we compute the probability of a particular observation sequence and state sequence? This question has two related but distinct versions. You might want to know the probability of a specific combination of words and tags: for example, how likely is the sentence "the dog runs" tagged as "DT NN VB"? Or you might want to know the probability of the observation sequence alone, summed over all possible hidden state sequences: how likely is the sentence "the dog runs" to appear at all, regardless of how it is tagged? The first question gives you the joint probability $P(O, S)$; the second gives you the marginal $P(O)$. Both are important, and the joint probability decomposition is the foundation for computing either one.

The joint probability factors according to the HMM structure, exploiting the independence assumptions to decompose a complex probability into simple terms.

For an observation sequence $O = o_1, o_2, \ldots, o_n$ and state sequence $S = s_1, s_2, \ldots, s_n$, the joint probability is:

where:

• $P(O, S)$: the joint probability of observing sequence $O$ while the hidden states follow sequence $S$
• $P(s_1)$: the initial probability of starting in state $s_1$, denoted $\pi_{s_1}$
• $P(o_1 \,|\, s_1)$: the emission probability of the first observation given the first state, denoted $b_{s_1}(o_1)$
• $\prod_{t=2}^{n}$: the product over all positions from 2 to $n$
• $P(s_t \,|\, s_{t-1})$: the transition probability from state $s_{t-1}$ to state $s_t$, denoted $a_{s_{t-1}, s_t}$
• $P(o_t \,|\, s_t)$: the emission probability of observation $o_t$ from state $s_t$, denoted $b_{s_t}(o_t)$

The formula captures the generative story of an HMM: start in some state (with probability $\pi$), emit the first word (with probability $b$), then repeatedly transition to a new state (with probability $a$) and emit the next word (with probability $b$). This story is "generative" because you can use it to generate sentences: sample a starting tag from $\pi$, sample a word from $b$, sample a next tag from $a$, sample the next word from $b$, and so on. The HMM describes a process that could plausibly have produced the training data, and parameter estimation is the task of finding the process whose description fits that data best.

Let's compute this for a concrete example: the sentence "the dog runs" with tags "DT NN VB." We'll trace through each step of the computation, showing how the probabilities multiply together to give the joint probability of this particular word-tag pairing.

The joint probability is quite small because we're multiplying many probabilities together. For longer sequences, these products become vanishingly small, leading to numerical underflow. A 20-word sentence with probabilities around 0.1 at each step would produce a product on the order of $10^{-20}$, which many floating-point implementations round to zero. In practice, we work in log space, converting multiplications to additions:

Since $\log$ is a monotonically increasing function, maximizing the log probability is equivalent to maximizing the probability itself. Working in log space prevents numerical underflow and is standard practice for probabilistic sequence models.

An HMM is only useful if we can learn its parameters from data. For POS tagging, we have access to annotated corpora where each word is labeled with its correct tag. This is supervised learning, and parameter estimation is straightforward: we count occurrences and normalize.

The intuition behind maximum likelihood estimation is simple: the best model is the one that assigns the highest probability to the observed data. If you saw the bigram "DT NN" a thousand times in training but "DT VB" only ten times, the data is telling you that determiners are followed by nouns far more often than by verbs, and your transition probabilities should reflect that. Maximum likelihood formalized this intuition into a precise estimation procedure.

The maximum likelihood estimates for HMM parameters are simple frequency ratios derived from counting occurrences in the training data. The estimates have a satisfying form: every probability is just the count of the event you care about divided by the count of the conditioning context. There are no free hyperparameters, no optimization loops, and no gradient descent. You count, you divide, and you are done.

For initial probabilities, we count how often each state starts a sequence:

where:

• $\hat{\pi}_i$: the estimated probability of starting in state $i$
• $\text{count}(s_1 = i)$: the number of sequences that begin with state $i$
• $\text{count}(\text{sequences})$: the total number of sequences in the training data

For transition probabilities, we count how often state $j$ follows state $i$:

where:

• $\hat{a}_{ij}$: the estimated probability of transitioning from state $i$ to state $j$
• $\text{count}(s_{t-1} = i, s_t = j)$: the number of times state $i$ is immediately followed by state $j$
• $\text{count}(s_{t-1} = i)$: the total number of times state $i$ appears (except at sequence end)

For emission probabilities, we count how often state $i$ emits observation $o$:

where:

• $\hat{b}_i(o)$: the estimated probability of emitting observation $o$ from state $i$
• $\text{count}(s_t = i, o_t = o)$: the number of times state $i$ emits observation $o$
• $\text{count}(s_t = i)$: the total number of times state $i$ appears

In words: the initial probability of state $i$ is the fraction of sequences that start with $i$. The transition probability from $i$ to $j$ is the fraction of times $i$ is followed by $j$. The emission probability of $o$ from $i$ is the fraction of times state $i$ emits $o$.

Notice that each distribution is estimated independently. Transition probabilities depend only on pairs of consecutive tags; emission probabilities depend only on individual tag-word pairs. This independence makes estimation extremely fast and scales to large corpora without difficulty. The Brown corpus used below contains over 57,000 sentences and more than a million words; the entire parameter estimation completes in seconds.

Let's implement this with NLTK's tagged corpora. The Brown corpus contains over 57,000 sentences with POS tags, giving us enough data to estimate reliable probabilities. We'll use the Universal tagset, which maps the fine-grained Brown tags to 17 coarse categories for cleaner patterns.

: Emission probabilities for ambiguous words across POS tags. "Time" shows moderate noun vs. verb ambiguity. "Run" is more strongly verbal. "Set" has large probability from both noun and verb tags. This reflects its high ambiguity in English. {#tbl-emission-ambiguity}

The table reveals that "time" has higher emission probability from NOUN than VERB, but both are non-zero. This reflects lexical ambiguity. These patterns form the statistical backbone of HMM-based tagging.

A critical challenge emerges when we encounter words not seen during training. If a word $o$ never appeared with tag $i$, then $\hat{b}_i(o) = 0$. When we multiply by zero, the entire sequence probability becomes zero, making it impossible to tag sentences containing unknown words.

This is not a minor edge case. In real text, a significant fraction of words at test time will never have appeared in training. Technical documents use specialized vocabulary. Named entities change constantly. New words enter the language every year. An HMM tagger without a strategy for unknown words would completely fail on any non-trivial text.

Smoothing techniques address this problem. The simplest approach is add-one (Laplace) smoothing: add a small count to every word-tag combination before normalizing.

where:

• $\hat{b}_i(o)$: the smoothed emission probability of observation $o$ from state $i$
• $\text{count}(s_t = i, o_t = o)$: the number of times state $i$ emits observation $o$ (zero for unseen combinations)
• $\text{count}(s_t = i)$: the total number of times state $i$ appears
• $|V|$: the vocabulary size (number of unique observations)

The numerator adds 1 to every count. This ensures no probability is ever zero. The denominator adds $|V|$ to compensate, keeping the probabilities properly normalized (summing to 1). This ensures every word has a non-zero probability from every tag, though the probability is very small for unseen combinations.

With smoothing, unseen words get a small but non-zero probability from each tag. This allows the HMM to tag sentences containing new words by relying on transition probabilities to disambiguate. The smoother the unknown-word distribution, the more the model falls back on syntax (transitions) and the less it can rely on lexical identity. In practice, Laplace smoothing is often too aggressive: it assigns the same small probability to an unknown word from every tag, which means a rare capitalized word like "Zuckerberg" gets equal emission probability from NOUN, VERB, and ADJ, leaving disambiguation entirely to surrounding context.

More sophisticated approaches use morphological clues. Words ending in "-tion" are almost always nouns; words ending in "-ly" are almost always adverbs; capitalized words in the middle of a sentence are often proper nouns. By clustering unknown words into morphological classes and learning separate emission probabilities for each class, you can handle unknowns much more accurately without abandoning the HMM framework. This is the strategy used by the TNT tagger (Brants, 2000) and similar high-accuracy HMM systems.

Now let's build a complete HMM POS tagger. Given a sentence, we want to find the most likely tag sequence. This is called the decoding problem because it is analogous to decoding a message in a noisy channel: the "true signal" is the tag sequence, the "noise" is the mapping from tags to words, and your task is to recover the most probable original signal given what you received.

where:

• $\hat{S}$: the optimal (most likely) state sequence
• $\arg\max_S$: "the value of $S$ that maximizes" the following expression
• $P(S \,|\, O)$: the posterior probability of state sequence $S$ given observations $O$
• $P(O, S)$: the joint probability of observations and states

The second equality follows from Bayes' rule: $P(S \mid O) = P(O, S) / P(O)$. Since $P(O)$ is constant for a given observation sequence (it does not depend on which state sequence we are evaluating), maximizing the posterior is equivalent to maximizing the joint probability.

A naive approach would enumerate all possible tag sequences, compute their joint probabilities, and return the maximum. But with $|S|$ tags and $n$ words, there are $|S|^n$ possible sequences. For 12 tags and a 20-word sentence, that is over 3.8 quadrillion possibilities. Even at a billion evaluations per second, exhaustive search would take over 3 million years.

The Viterbi algorithm solves this efficiently in $O(n \cdot |S|^2)$ time using dynamic programming. We will cover Viterbi in detail in the next chapter. For now, let's implement a simplified greedy decoder that selects the locally best tag at each position.

Greedy decoding works as follows: for the first word, we pick the tag that maximizes $\pi_i \cdot b_i(o_1)$. For each subsequent word, we pick the tag that maximizes $a_{prev, i} \cdot b_i(o_t)$ given the previous tag we chose. This is fast but can make mistakes when a locally optimal choice leads to a globally suboptimal sequence.

The greedy tagger works reasonably well for straightforward sentences but can make errors when local decisions conflict with global coherence. The sentence "The old man the boat" is a famous garden path sentence where "man" functions as a verb (meaning "to operate") and "old" is a noun phrase ("the elderly people"). Greedy decoding often misses such non-local dependencies because each decision only considers the immediately preceding tag.

Garden path sentences illustrate a broader point about greedy decoding: a locally optimal choice can lock you into a globally suboptimal path. Once the greedy decoder decides "man" is a noun, it has committed to that interpretation and there is no backtracking. The Viterbi algorithm avoids this by postponing final decisions. Rather than committing to a single path at each step, Viterbi maintains the best partial sequence ending in each state, and only commits to a full sequence once all positions have been processed. This global search within the dynamic programming framework is what separates Viterbi from greedy decoding and why it consistently outperforms greedy by several percentage points on held-out data.

The transition matrix is the heart of an HMM's syntactic knowledge. By visualizing it as a heatmap, we can see which tag sequences the model considers likely and which it considers rare. This provides insight into both the structure of English grammar and the quality of our learned model. Notice that the matrix is quite sparse: most entries are small because most tag pairs rarely occur consecutively in well-formed English. The few high-probability entries correspond to the syntactic rules that generate most English sentences.

The transition matrix reveals clear syntactic patterns. Determiners (DET) have high transition probability to nouns (NOUN) and adjectives (ADJ). Nouns frequently transition to verbs (VERB) or punctuation. Prepositions (ADP) strongly predict nouns. This reflects prepositional phrase structure. These patterns are exactly what we'd expect from English grammar.

How well does our HMM tagger perform? To answer this rigorously, we need to evaluate on data the model hasn't seen during training. We'll split the Brown corpus into 90% training and 10% test, re-estimate all parameters on the training portion, and measure accuracy on the held-out test sentences.

We'll also track performance separately for known words (those seen during training) versus unknown words. This distinction matters because the model handles these cases very differently: known words have learned emission probabilities, while unknown words must rely entirely on transition patterns and smoothed probabilities.

The log-scale y-axis is necessary here because emission probabilities span several orders of magnitude. A word that appears frequently as a NOUN will have emission probability on the order of $10^{-3}$, while the same word appearing rarely as a VERB might have probability on the order of $10^{-5}$. Both are small in absolute terms, but the ratio between them is what the model exploits for disambiguation. When the bars for NOUN and VERB are nearly the same height (indicating similar emission probabilities from both tags), the model must rely on the transition matrix to pick the right tag.

To understand how an HMM resolves ambiguity, let's trace through the complete probability computation for the classic ambiguous sentence "Time flies." This two-word sentence has two plausible interpretations, and both words can function as either nouns or verbs:

• "Time flies" could mean "Time passes quickly" (NOUN VERB)
• "Time flies" could mean "Measure how fast flies move" (VERB NOUN)

The second interpretation is grammatically valid but pragmatically unusual. Most readers parse "Time flies" as the first interpretation without hesitation, which is exactly what we want the HMM to do. The question is: does the statistical evidence from the corpus lead the model to the same conclusion?

We will compute the joint probability for each interpretation and see which one the HMM prefers. Since we are multiplying many small probabilities, we will work in log space to avoid numerical underflow. Each log probability is a negative number (since all probabilities are between 0 and 1), so the interpretation with the higher (less negative) total log probability is the preferred one.

The HMM prefers "Time flies" as NOUN VERB. This makes sense: in the training data, sentences starting with nouns are more common than sentences starting with verbs, and noun-verb transitions are frequent. The emission probability of "time" from NOUN is also higher than from VERB, since "time" appears as a noun more often in general text.

This example illustrates how HMMs combine multiple sources of evidence: initial probabilities favor starting with nouns, transitions favor noun-verb patterns, and emissions favor "time" as a noun and "flies" as a verb. The bar chart above lets you see exactly how each component contributes to the total log probability. When the NOUN VERB interpretation wins, it is not because of a single dominant factor; it is because several moderately sized factors all point in the same direction.

The key insight from this example is that HMMs do not disambiguate words in isolation. "Flies" has substantial probability from both NOUN and VERB, so the emission alone would not clearly favor either interpretation. What tips the balance is the combination of initial probability (nouns are more common sentence starters), transition probability (noun-to-verb transitions are common), and emission probability (time-as-noun and flies-as-verb are both plausible). No single source of evidence is conclusive; together they provide enough signal to make the correct call. This is the power of the joint probability framework.

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.

When implementing HMM-based taggers, several parameters affect model performance. Understanding what each parameter controls and how it interacts with the others will help you tune your model effectively on new tasks and datasets.

• Smoothing constant ($\alpha$): Controls how much probability mass is reserved for unseen word-tag combinations. Higher values (e.g., 1.0 for Laplace smoothing) give more weight to unseen events but dilute the learned emission probabilities for known words. Lower values (e.g., 0.01) preserve learned distributions better but may leave unknown words dangerously undersmoothed. Start with $\alpha = 1.0$ and tune based on unknown word accuracy on a development set. If your test domain has very different vocabulary from training (e.g., medical text trained on news), you will likely need to increase $\alpha$.

• Tag set granularity: Finer tag sets (like Penn Treebank's 36 tags) capture more distinctions but require more training data and increase computational cost. Coarser sets (like Universal Dependencies' 17 tags) are easier to learn but lose information. Choose based on your downstream task requirements. For most information extraction applications, coarse tags are sufficient; for linguistic research or parsing support, fine-grained tags matter.

• Case normalization: Converting words to lowercase reduces vocabulary size and improves emission estimates for rare words, but loses capitalization signals that help identify proper nouns and sentence boundaries. The implementation above uses lowercase normalization, which helps with data sparsity but hurts on named entity recognition tasks where capitalization is a strong signal. A practical compromise is to lowercase everything but preserve a "starts with capital" feature in an augmented emission model.

• Unknown word handling: Beyond smoothing, you can improve unknown word accuracy by using morphological features (suffixes, prefixes, capitalization patterns) or by backing off to character-level models. The simple <UNK> token approach shown here provides a baseline, but production systems typically cluster unknown words by their suffix (last 3-4 characters) and learn separate emission distributions for each suffix class. This allows the model to recognize that "implementation" is very likely a noun based on its "-tion" suffix, even if "implementation" itself never appeared in training.

• Higher-order transitions: Switching from first-order (bigram) to second-order (trigram) transitions improves accuracy but requires more data and memory. For a 40-tag Penn Treebank model, the transition table grows from 1,600 to 64,000 entries. If your corpus has fewer than 100,000 sentences, trigram transitions may be too sparse to estimate reliably without additional smoothing (such as linear interpolation between trigram, bigram, and unigram estimates).

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.

Ready to test your understanding? Take this quick quiz to reinforce what you've learned about Hidden Markov Models and sequence labeling.