Introduction

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.

Try It

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.

<!-- HMM Part-of-Speech Tagger — Viterbi decoding demo -->
<p class="hint">A tiny HMM with hand-crafted probabilities runs Viterbi to label each word. Transition probabilities capture grammar patterns; emission probabilities capture word-to-tag likelihoods.</p>
<div class="controls">
  <label for="sentence-select">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">Tag sentence</button>
  <button id="reset-btn" type="button" class="ghost">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>

/* styles for the word cards and tag badges */
* { 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; }
/* one color per POS tag for quick visual scanning */
.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; }

// Hidden Markov Model: states = POS tags, observations = words
// Viterbi finds the most likely tag sequence in O(T * N^2) time

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

// the set of part-of-speech tags used in this model
const TAGS = ['DT','NN','NNS','VBZ','VBP','VB','RB','IN','PRP','CD'];

// transition probability matrix: P(tag_i | tag_{i-1})
// each row sums to ~1; <s> is the sentence-start state
const TRANS = {
  '<s>': { DT:0.35, NN:0.10, NNS:0.05, VBZ:0.01, VBP:0.01, VB:0.02, RB:0.03, IN:0.02, PRP:0.35, CD:0.06 },
  DT:    { DT:0.01, NN:0.55, NNS:0.30, VBZ:0.01, VBP:0.01, VB:0.01, RB:0.03, IN:0.02, PRP:0.01, CD:0.05 },
  NN:    { DT:0.02, NN:0.08, NNS:0.04, VBZ:0.45, VBP:0.10, VB:0.03, RB:0.05, IN:0.15, PRP:0.02, CD:0.06 },
  NNS:   { DT:0.02, NN:0.06, NNS:0.03, VBZ:0.05, VBP:0.50, VB:0.05, RB:0.05, IN:0.15, PRP:0.02, CD:0.07 },
  VBZ:   { DT:0.15, NN:0.08, NNS:0.05, VBZ:0.01, VBP:0.01, VB:0.05, RB:0.40, IN:0.15, PRP:0.05, CD:0.05 },
  VBP:   { DT:0.15, NN:0.08, NNS:0.05, VBZ:0.01, VBP:0.01, VB:0.05, RB:0.40, IN:0.15, PRP:0.05, CD:0.05 },
  VB:    { DT:0.20, NN:0.10, NNS:0.05, VBZ:0.01, VBP:0.01, VB:0.02, RB:0.25, IN:0.15, PRP:0.10, CD:0.11 },
  RB:    { DT:0.05, NN:0.05, NNS:0.03, VBZ:0.20, VBP:0.20, VB:0.20, RB:0.10, IN:0.07, PRP:0.05, CD:0.05 },
  IN:    { DT:0.45, NN:0.10, NNS:0.08, VBZ:0.01, VBP:0.01, VB:0.02, RB:0.05, IN:0.02, PRP:0.20, CD:0.06 },
  PRP:   { DT:0.03, NN:0.05, NNS:0.03, VBZ:0.25, VBP:0.35, VB:0.10, RB:0.05, IN:0.05, PRP:0.02, CD:0.07 },
  CD:    { DT:0.05, NN:0.30, NNS:0.35, VBZ:0.05, VBP:0.05, VB:0.03, RB:0.05, IN:0.05, PRP:0.02, CD:0.05 }
};

// emission probability table: P(word | tag)
const EMIT = {
  the:     { DT:0.90, NN:0.01, NNS:0.01, VBZ:0, VBP:0, VB:0, RB:0, IN:0, PRP:0, CD:0 },
  a:       { DT:0.88, NN:0.02, NNS:0.01, VBZ:0, VBP:0, VB:0.01, RB:0, IN:0, PRP:0, CD:0 },
  an:      { DT:0.88, NN:0.01, NNS:0.01, VBZ:0, VBP:0, VB:0, RB:0, IN:0.01, PRP:0, CD:0 },
  dog:     { DT:0, NN:0.85, NNS:0.05, VBZ:0.02, VBP:0.01, VB:0.02, RB:0, IN:0, PRP:0, CD:0 },
  cat:     { DT:0, NN:0.85, NNS:0.05, VBZ:0.02, VBP:0.01, VB:0.02, RB:0, IN:0, PRP:0, CD:0 },
  mat:     { DT:0, NN:0.80, NNS:0.06, VBZ:0.03, VBP:0.01, VB:0.04, RB:0, IN:0, PRP:0, CD:0 },
  book:    { DT:0, NN:0.78, NNS:0.05, VBZ:0.02, VBP:0.03, VB:0.08, RB:0, IN:0, PRP:0, CD:0 },
  time:    { DT:0, NN:0.60, NNS:0.10, VBZ:0.05, VBP:0.08, VB:0.12, RB:0, IN:0, PRP:0, CD:0 },
  arrow:   { DT:0, NN:0.85, NNS:0.05, VBZ:0.01, VBP:0.01, VB:0.03, RB:0, IN:0, PRP:0, CD:0 },
  she:     { DT:0, NN:0.01, NNS:0, VBZ:0, VBP:0, VB:0, RB:0, IN:0, PRP:0.97, CD:0 },
  barks:   { DT:0, NN:0.15, NNS:0.10, VBZ:0.70, VBP:0.01, VB:0.01, RB:0, IN:0, PRP:0, CD:0 },
  sits:    { DT:0, NN:0.05, NNS:0.05, VBZ:0.80, VBP:0.05, VB:0.02, RB:0, IN:0, PRP:0, CD:0 },
  reads:   { DT:0, NN:0.05, NNS:0.05, VBZ:0.80, VBP:0.05, VB:0.02, RB:0, IN:0, PRP:0, CD:0 },
  flies:   { DT:0, NN:0.30, NNS:0.20, VBZ:0.40, VBP:0.05, VB:0.01, RB:0, IN:0, PRP:0, CD:0 },
  like:    { DT:0, NN:0.05, NNS:0.02, VBZ:0.05, VBP:0.10, VB:0.15, RB:0.05, IN:0.55, PRP:0, CD:0 },
  on:      { DT:0, NN:0.01, NNS:0.01, VBZ:0, VBP:0, VB:0, RB:0.05, IN:0.90, PRP:0, CD:0 },
  loudly:  { DT:0, NN:0.01, NNS:0, VBZ:0, VBP:0, VB:0, RB:0.96, IN:0, PRP:0, CD:0 },
  quietly: { DT:0, NN:0.01, NNS:0, VBZ:0, VBP:0, VB:0, RB:0.96, IN:0, PRP:0, CD:0 }
};

// fallback emission for unseen words
const UNK = { DT:0.02, NN:0.25, NNS:0.15, VBZ:0.10, VBP:0.10, VB:0.12, RB:0.08, IN:0.06, PRP:0.05, CD:0.07 };

const SENTENCES = [
  'The dog barks loudly',
  'Time flies like an arrow',
  'The cat sits on the mat',
  'She reads a book quietly'
];

// runs the Viterbi algorithm on an array of word strings
function viterbi(words) {
  const n = words.length;
  // dp[i][t] = best probability of sequence ending with tag t at position i
  const dp = [];
  const bp = [];
  const emit0 = EMIT[words[0].toLowerCase()] || UNK;
  const row0 = {}, back0 = {};
  for (const t of TAGS) {
    row0[t] = (TRANS['<s>'][t] || 0.001) * (emit0[t] || 0.001);
    back0[t] = null;
  }
  dp.push(row0); bp.push(back0);
  // fill the trellis left to right
  for (let i = 1; i < n; i++) {
    const emit = EMIT[words[i].toLowerCase()] || UNK;
    const row = {}, back = {};
    for (const t of TAGS) {
      let best = -1, bestPrev = null;
      for (const prev of TAGS) {
        const score = dp[i-1][prev] * (TRANS[prev][t] || 0.0001) * (emit[t] || 0.001);
        if (score > best) { best = score; bestPrev = prev; }
      }
      row[t] = best; back[t] = bestPrev;
    }
    dp.push(row); bp.push(back);
  }
  // backtrack to recover the best sequence
  let bestTag = TAGS.reduce((a, b) => dp[n-1][a] > dp[n-1][b] ? a : b);
  const seq = [bestTag];
  for (let i = n-1; i > 0; i--) { bestTag = bp[i][bestTag]; seq.unshift(bestTag); }
  // compute per-word confidence as fraction of total probability mass
  const confs = dp.map((row, i) => {
    const total = Object.values(row).reduce((a, b) => a + b, 0);
    return total > 0 ? (row[seq[i]] / total) : 0;
  });
  return { seq, confs };
}

const tagsRow = document.getElementById('tags-row');
const statusEl = document.getElementById('status');
const pathInfo = document.getElementById('path-info');

function reset() {
  tagsRow.innerHTML = '';
  statusEl.textContent = '';
  statusEl.className = 'status';
  pathInfo.textContent = '';
}

function tagSentence() {
  reset();
  const idx = parseInt(document.getElementById('sentence-select').value, 10);
  const sentence = SENTENCES[idx];
  const words = sentence.split(' ');
  const { seq, confs } = viterbi(words);

  words.forEach((word, i) => {
    const card = document.createElement('div');
    card.className = 'word-card';
    const wt = document.createElement('div'); wt.className = 'word-text'; wt.textContent = word;
    const badge = document.createElement('div');
    badge.className = 'tag-badge tag-' + seq[i]; badge.textContent = seq[i];
    const barWrap = document.createElement('div'); barWrap.className = 'conf-bar-wrap';
    const bar = document.createElement('div'); bar.className = 'conf-bar tag-' + seq[i];
    bar.style.width = '0%';
    barWrap.appendChild(bar);
    const confTxt = document.createElement('div');
    confTxt.className = 'conf-text';
    confTxt.textContent = Math.round(confs[i] * 100) + '%';
    card.append(wt, badge, barWrap, confTxt);
    tagsRow.appendChild(card);
    // stagger card animations for a word-by-word reveal
    setTimeout(() => {
      card.classList.add('visible');
      bar.style.width = Math.round(confs[i] * 100) + '%';
    }, i * 120);
  });

  setTimeout(() => {
    const tagStr = seq.join(' → ');
    statusEl.textContent = 'Tagging complete — see the most likely path below.';
    statusEl.className = 'status ok';
    pathInfo.textContent = i18nFmt('Best tag path: %path%', { path: tagStr });
  }, words.length * 120 + 200);
}

document.getElementById('tag-btn').addEventListener('click', tagSentence);
document.getElementById('reset-btn').addEventListener('click', reset);
Result
Console

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 Real Complexity

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

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

  • Time complexity: O(T⋅N2)O(T \cdot N^{2}) — for each of the TT words, check all NN previous tags to find the best predecessor.
  • Space complexity: O(T⋅N)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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/hmm-pos-tagging/Content licensed under CC BY-NC 4.0.