Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Hidden Markov Models › HMM for POS Tagging

Michael BrenndoerferUpdated May 7, 20254 min read

Language AI HandbookAll chapters

Part 6 of 67Sequence Labeling

Chapter 40Hidden Markov Models › HMM for POS Tagging

Reading section 6 of 13 · HMM for POS Tagging · 4 minSection 6 of 13 · 4 min

Section 6 of 13 · 4 min read

Hidden Markov Models › HMM for POS TaggingOne section · Sections in this chapter6 / 13 ↓

Sections in this chapter13

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

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.

\hat{S} = \arg\max_S P(S \,|\, O) = \arg\max_S P(O, S)

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.

In[16]:

Code

class SimpleHMMTagger:
    """A simple HMM POS tagger with greedy decoding."""

    def __init__(self, pi, A, B, vocab):
        self.pi = pi
        self.A = A
        self.B = B
        self.vocab = vocab
        self.tags = list(A.keys())

    def get_emission_prob(self, tag, word):
        """Get emission probability, handling unknown words."""
        word = word.lower()
        if word in self.B[tag]:
            return self.B[tag][word]
        return self.B[tag]["<UNK>"]

    def tag_greedy(self, sentence):
        """Tag sentence using greedy (locally optimal) decoding."""
        tags = []

        for i, word in enumerate(sentence):
            if i == 0:
                # First word: use initial and emission probabilities
                best_tag = None
                best_prob = -1
                for tag in self.tags:
                    prob = self.pi.get(tag, 1e-10) * self.get_emission_prob(
                        tag, word
                    )
                    if prob > best_prob:
                        best_prob = prob
                        best_tag = tag
            else:
                # Subsequent words: use transition and emission
                prev_tag = tags[-1]
                best_tag = None
                best_prob = -1
                for tag in self.tags:
                    trans_prob = self.A.get(prev_tag, {}).get(tag, 1e-10)
                    emit_prob = self.get_emission_prob(tag, word)
                    prob = trans_prob * emit_prob
                    if prob > best_prob:
                        best_prob = prob
                        best_tag = tag

            tags.append(best_tag)

        return tags


# Create tagger from estimated parameters
tagger = SimpleHMMTagger(pi_est, A_est, B_smoothed, vocab)

In[17]:

Code

# Test on some sentences
test_sentences = [
    ["The", "dog", "runs", "quickly"],
    ["She", "reads", "books"],
    ["The", "old", "man", "the", "boat"],  # Classic garden path sentence
]

predictions = []
for sent in test_sentences:
    tags = tagger.tag_greedy(sent)
    predictions.append(list(zip(sent, tags)))

Out[18]:

Console

Greedy HMM Tagger Results
==================================================

Sentence 1: The dog runs quickly
Tags: The/DET dog/NOUN runs/NOUN quickly/ADV 

Sentence 2: She reads books
Tags: She/PRON reads/VERB books/NOUN 

Sentence 3: The old man the boat
Tags: The/DET old/ADJ man/NOUN the/DET boat/NOUN

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.