Introduction
"They can fish" and "a can of fish" use the same words in different roles. Part-of-speech (POS) tagging labels each word with its grammatical category: noun, verb, determiner (the, a), adjective, pronoun and so on. Tags help later steps: a noun phrase chunker needs them, a lemmatizer needs to know that "saw" is a verb before turning it into "see", and text-to-speech must know whether "record" is a noun or a verb to pronounce it. POS tagging is also the classic example of sequence labelling, where each decision depends on its neighbours.
How it works
A surprisingly strong baseline gives each word the tag it had most often in a tagged training corpus, and gives unknown words the most common tag overall. It is right for most words, but it always tags "can" the same way, whatever the context.
A hidden Markov model (HMM) adds context. Imagine the tags as hidden states that follow each other, each state emitting a visible word. It has three tables, all estimated by counting a tagged corpus:
- Start probabilities: P(tag at the first position).
- Transition probabilities: P(tag given previous tag) = count(prev → tag) ÷ count of transitions out of prev. After a determiner, a noun is very likely.
- Emission probabilities: P(word given tag) = count(word tagged as tag) ÷ count(tag).
The probability of a sentence with a tag sequence is the start probability of the first tag, times each transition, times each word's emission. The tagger wants the tag sequence with the highest probability, but there are T to the power n sequences for T tags and n words, far too many to try.
The Viterbi algorithm solves this with dynamic programming. For each word position and each tag, it stores the probability of the best path that ends in that tag, and a back-pointer to the previous tag on that path:
best[i][t] = max over s of (best[i − 1][s] × P(t given s)) × P(word i given t)
At the end, take the tag with the highest final value and follow the back-pointers backwards. The work is only n × T × T steps. Real taggers add the logs of the probabilities to avoid underflow and smooth the emissions of unknown words.
Example
tags = ["NOUN", "VERB", "DET"]
start = {"NOUN": 0.3, "VERB": 0.1, "DET": 0.6}
trans = {
"NOUN": {"NOUN": 0.2, "VERB": 0.7, "DET": 0.1},
"VERB": {"NOUN": 0.3, "VERB": 0.1, "DET": 0.6},
"DET": {"NOUN": 0.9, "VERB": 0.05, "DET": 0.05},
}
emit = {
"NOUN": {"dog": 0.4, "can": 0.2, "fish": 0.4},
"VERB": {"can": 0.5, "fish": 0.3},
"DET": {"the": 0.9},
}
def viterbi(words):
best = [{t: start[t] * emit[t].get(words[0], 0) for t in tags}]
back = []
for w in words[1:]:
col, ptr = {}, {}
for t in tags:
score, src = max((best[-1][s] * trans[s][t], s) for s in tags)
col[t] = score * emit[t].get(w, 0)
ptr[t] = src
best.append(col)
back.append(ptr)
tag = max(tags, key=lambda t: best[-1][t])
path = [tag]
for ptr in reversed(back):
tag = ptr[tag]
path.append(tag)
return best, path[::-1]
words = "the dog can fish".split()
best, path = viterbi(words)
for w, col in zip(words, best):
print(f" {w:5} NOUN {col['NOUN']:.4f} VERB {col['VERB']:.4f} DET {col['DET']:.4f}")
print(" ".join(f"{w}/{t}" for w, t in zip(words, path)))
best, path = viterbi(["the", "can"])
print("the can ->", path)Line by line
- The first column multiplies each tag's start probability by the probability that it emits "the"; only DET can.
- For each later word and tag,
maxpicks the best previous tagsby best[s] × transition(s → t), and remembers it as the back-pointer. - At "can", VERB (0.0680) beats NOUN (0.0078) because a noun ("dog") is very often followed by a verb.
- At "fish", the best path into NOUN comes from VERB: "can" as a verb, then "fish" as its object.
- Following the back-pointers gives the/DET dog/NOUN can/VERB fish/NOUN. In "the can", the same word is tagged NOUN, because a determiner is almost always followed by a noun.
Expected result
the NOUN 0.0000 VERB 0.0000 DET 0.5400
dog NOUN 0.1944 VERB 0.0000 DET 0.0000
can NOUN 0.0078 VERB 0.0680 DET 0.0000
fish NOUN 0.0082 VERB 0.0020 DET 0.0000
the/DET dog/NOUN can/VERB fish/NOUN
the can -> ['DET', 'NOUN']
In the real world
Tag sets range from the 17 Universal Dependencies tags (NOUN, VERB, ADJ, DET and so on) to the 45 Penn Treebank tags (NN, NNS, VBD and so on). HMM taggers reach about 95% accuracy on English news; modern neural taggers reach about 97 to 98%, and most of the remaining errors are genuinely hard cases. With spaCy (shown, not run: it is not available in StepVioz's browser Python):
import spacy
nlp = spacy.load("en_core_web_sm")
for token in nlp("They can fish"):
print(token.text, token.pos_, token.tag_)
pos_ is the universal tag and tag_ the detailed Penn Treebank tag. The Viterbi algorithm itself is everywhere: speech recognition, gene finding, error-correcting codes and named-entity tagging with CRFs.
Common mistakes
- Multiplying many probabilities without logs, which underflows on long sentences.
- Giving unknown words emission probability 0, so no path survives; smooth or use the word's shape (capitals, endings such as -ing).
- Taking the best tag at each position separately (greedy) instead of the best sequence.
- Mixing up the direction of transitions: the table holds P(tag given previous tag), not the reverse.
Best practices
- Always compare with the most-frequent-tag baseline; it is hard to beat by a lot.
- Estimate the tables on training data and measure accuracy on separate test sentences.
- Break ties in a fixed order so the output does not depend on luck.
- Check the algorithm on a two-word example you can compute by hand.
Summary
POS tagging labels each word with its grammatical category. A most-frequent-tag baseline ignores context; a hidden Markov model scores tag sequences with start, transition and emission probabilities counted from a tagged corpus. The Viterbi algorithm finds the most probable tag sequence with dynamic programming, keeping the best path into each tag and following back-pointers at the end.
Quick check
Key takeaways
- Many words can take several tags; context decides which one is right.
- An HMM scores a tag sequence by multiplying start, transition and emission probabilities.
- Viterbi keeps only the best path into each tag at each word, so it finds the best sequence without trying them all.
Practice problems for this lesson
My notes
Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.