HMM Part-of-Speech Tagging

Read the sentence "The dog barks loudly." You instantly know that the is a determiner, dog is a noun, barks is a verb, and loudly is an adverb. You did that in milliseconds without consciously thinking about it.

Teaching a computer to do the same thing is called part-of-speech (POS) tagging, and it is one of the oldest and most studied tasks in natural language processing. Every downstream tool — parsers, translators, search engines — builds on it.

The classic approach uses a Hidden Markov Model (HMM). The idea is elegant: the real grammatical structure of a sentence (noun follows determiner, verb follows noun, …) is a hidden sequence of states. What we actually observe is just the words. The HMM encodes two kinds of knowledge as probabilities: how likely each tag is to follow the previous one (transition probabilities), and how likely each word is given a tag (emission probabilities). Finding the most likely hidden sequence for a sentence is then a problem that the Viterbi algorithm (Andrew Viterbi, 1967) solves exactly in time proportional to the length of the sentence — a beautifully efficient answer to what sounds like an exponential search.

Pick a sentence from the dropdown and press Tag sentence. The tagger runs the Viterbi algorithm over a small HMM trained on simplified English grammar. Each word lights up with its most likely tag and a confidence score derived from the Viterbi probabilities.

<!-- {{c_intro}} -->
<p class="hint">{{hint_para}}</p>
<div class="controls">
  <label for="sentence-select">{{label_sentence}}</label>
  <select id="sentence-select">
    <option value="0">The dog barks loudly</option>
    <option value="1">Time flies like an arrow</option>
    <option value="2">The cat sits on the mat</option>
    <option value="3">She reads a book quietly</option>
  </select>
  <button id="tag-btn" type="button">{{btn_tag}}</button>
  <button id="reset-btn" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div id="tags-row" class="tags-row" aria-live="polite"></div>
<div id="status" class="status" role="status"></div>
<div id="path-info" class="path-info"></div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.controls { display: flex; flex-wrap: wrap; align-items: center; gap: .5rem; margin-bottom: 1rem; }
label { font-size: .88rem; font-weight: 600; color: #333; }
select { font: 14px system-ui, sans-serif; padding: .35rem .6rem; border: 1px solid #adb1b8;
         border-radius: 6px; background: #fff; cursor: pointer; }
button { font: 600 14px system-ui, sans-serif; padding: .4rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.tags-row { display: flex; flex-wrap: wrap; gap: .5rem; min-height: 90px; align-items: flex-start; }
.word-card { display: flex; flex-direction: column; align-items: center; gap: .25rem;
             opacity: 0; transform: translateY(8px);
             transition: opacity .3s ease, transform .3s ease; }
.word-card.visible { opacity: 1; transform: translateY(0); }
.word-text { font: 700 15px ui-monospace, monospace; color: #1d3557; }
.tag-badge { font: 700 11px system-ui, sans-serif; padding: .18rem .5rem; border-radius: 99px;
             color: #fff; white-space: nowrap; }
.conf-bar-wrap { width: 52px; height: 5px; background: #e0e4ea; border-radius: 3px; overflow: hidden; }
.conf-bar { height: 100%; border-radius: 3px; transition: width .4s; }
.conf-text { font-size: .72rem; color: #666; }
.status { font-size: .95rem; font-weight: 600; margin: .6rem 0 .3rem; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.path-info { font-size: .8rem; color: #555; line-height: 1.5; }
/* {{c_tag_colors}} */
.tag-DT  { background: #457b9d; }
.tag-NN  { background: #1d3557; }
.tag-NNS { background: #264653; }
.tag-VBZ { background: #e76f51; }
.tag-VBP { background: #f4a261; }
.tag-VB  { background: #2a9d8f; }
.tag-RB  { background: #e9c46a; color: #222 !important; }
.tag-IN  { background: #6d6875; }
.tag-PRP { background: #b5838d; }
.tag-CD  { background: #4a4e69; }

// Code not found

Notice that the tagger doesn't look at each word in isolation — it picks the tag sequence that maximises the joint probability of words and tags together. That is why "flies" gets tagged as a verb in "Time flies like an arrow" but as a noun in another context: the surrounding words shift the balance of probabilities.

The naive approach to POS tagging would enumerate every possible sequence of tags for a sentence and pick the best one. With $N$ tags and a sentence of length $T$, that is $N^{T}$ sequences — exponential and utterly impractical for real text.

Viterbi avoids this explosion through dynamic programming. It fills a table of size $T \times N$: for each position $t$ and each tag $j$, it stores the probability of the most likely sequence of tags ending with tag $j$ at position $t$. Each cell depends only on the previous column, so the whole table fills in a single left-to-right sweep.

• Time complexity: $O(T \cdot N^{2})$ — for each of the $T$ words, check all $N$ previous tags to find the best predecessor.
• Space complexity: $O(T \cdot N)$ for the probability table plus a backpointer table of the same size to reconstruct the sequence at the end.
• Exact solution: unlike greedy taggers that pick the locally best tag at each step, Viterbi is guaranteed to find the globally most likely sequence.

The key insight is that the Markov property — each tag depends only on the immediately preceding tag — makes the subproblems independent. Without it, dynamic programming would not apply and you would be back to the exponential search.

HMMs trained on large corpora (Penn Treebank, for example) reach word-level accuracy above 97% on English text. Their successors — CRFs and transformer-based taggers — push higher still, but Viterbi's clean complexity story remains a benchmark for what "efficient exact inference" can look like.

Part-of-speech tags are the first rung of almost every language-understanding pipeline:

• Machine translation: knowing that a word is a verb (not a noun) changes which translation to choose and how to inflect it in the target language.
• Information extraction: finding named entities (people, places, organisations) is easier once you know which words are nouns and which are modifiers.
• Grammar checkers and style tools: subject–verb agreement errors can only be caught after tagging establishes which word is the subject and which is the verb.
• Text-to-speech synthesis: pronouncing "record" correctly depends on whether it is a noun (REC-ord) or a verb (re-CORD) — a tagging decision.
• Question answering and search: query analysis breaks a user's question into its grammatical parts before matching against documents.

The HMM approach also generalises far beyond words. The same Viterbi framework appears in speech recognition (the hidden states are phonemes), gene finding in bioinformatics, and financial regime detection. Anywhere a hidden state sequence generates observable signals, dynamic programming on an HMM is a natural first model to reach for.

Hidden Markov Models capture a deep intuition: language is produced by a hidden grammatical structure, and we only see its surface. By encoding that structure as transition and emission probabilities, HMMs turn POS tagging into a neat probabilistic inference problem.

What makes the whole approach practical is the Viterbi algorithm — a dynamic programming tour de force that collapses an exponential search into a single efficient sweep. The price is the Markov assumption: each tag depends only on its immediate predecessor. Real language is richer than that, which is why modern neural taggers go further. But Viterbi's clarity — the way it makes the complexity story so crisp — remains the reason every NLP course starts here.

The next time your phone's autocomplete, grammar checker, or voice assistant gets the grammar right, somewhere in the chain a sequence labeler is threading the most likely path through a web of probabilities, one word at a time.