Definition
Part-of-speech tagging assigns each token of a sentence its grammatical category, such as noun, verb or determiner. English work mostly uses the 45-tag Penn Treebank set (Marcus, Santorini and Marcinkiewicz, 1993). Multilingual work uses the 17 Universal POS tags of Universal Dependencies, which grew out of the 12-tag universal set of Petrov, Das and McDonald (2012).
Input: tokens . Output: one tag per token, . The difficulty is ambiguity. "flies" is a verb (VBZ) in "time flies" and a plural noun (NNS) in "fruit flies"; "like" can be a preposition (IN) or a verb (VBP). Only context decides, and unknown words have no dictionary entry at all.
The tag sets differ in grain. PTB splits verbs by form (VB, VBD, VBG, VBN, VBP, VBZ) and nouns by number and properness (NN, NNS, NNP, NNPS). UPOS has one VERB and one NOUN/PROPN, and moves the inflection into separate morphological features, so the same 17 tags work across 100+ languages.
HMM taggers and Viterbi decoding
The classical tagger is a hidden Markov model: tags form a Markov chain and each tag emits a word. Transition and emission probabilities are relative frequencies in a treebank (with smoothing). TnT (Brants, 2000) used tag trigrams and a suffix model for unknown words.
- transition probability; is a start symbol (a trigram tagger conditions on two previous tags)
- emission probability of the word given its tag
- probability of the best tag prefix ending in tag at position ; a back-pointer stores the maximising
There are tag sequences, but the best one can be found exactly in . The recursion works because the best path into tag at step must extend the best path into one of the tags at . Take , then follow the back-pointers. Replacing max by sum gives the forward algorithm and .
Neural taggers
Neural taggers are discriminative. They compute a context vector per token and classify it, trained with cross-entropy against the gold tags:
- word embedding (pre-trained, e.g. Word2Vec or GloVe)
- character-level BiLSTM or CNN encoding of the word, which captures suffixes such as "-ly" and "-ing" and handles unseen words
- concatenated forward and backward states: the tag at t sees the whole sentence
Plank, Søgaard and Goldberg (ACL 2016) showed that such a Bidirectional LSTM tagger with character and word inputs is accurate across 22 languages. Ma and Hovy (2016) added a CRF output layer (as in Named entity recognition (NER)) and reported 97.55% on WSJ. Contextual string embeddings (Akbik et al., 2018) reached 97.85%.
Today the default is a fine-tuned pre-trained encoder (BERT, or a multilingual model for UD treebanks) with a linear head on each word's first subword. Unlike NER, POS tags have no span structure, so a CRF layer usually adds little: there are no forbidden tag sequences, and the contextual states already carry most transition information.
Data and reference numbers
- Penn Treebank WSJ
- 45 tags; standard split: sections 0–18 train, 19–21 dev, 22–24 test
- Universal Dependencies
- 17 UPOS tags plus morphological features; treebanks for 100+ languages, scored per treebank
- Metric
- token accuracy (and sentence accuracy: the share of sentences with every tag right)
- WSJ test accuracy
- most-frequent tag ≈ 90%; HMM ≈ 96–97%; feature-rich log-linear tagger 97.24% (Toutanova et al., 2003); BiLSTM-CNN-CRF 97.55%; Flair 97.85%
Worked example: Viterbi by hand
Same toy HMM, p(NNS | NN) = 0.05
- 1time: , .
- 2flies: (from NN); (from NN).
- 3like: (from VBZ); (from NNS).
- 4an: (from IN). arrow: .
- 5Back-pointers from the end: NN ← DT ← IN ← VBZ ← NN, so the tags are NN VBZ IN DT NN. The compound path has probability , which overtakes when .
1import numpy as np23tags = ["NN", "NNS", "VB", "VBZ", "VBP", "IN", "DT"]4ix = {t: i for i, t in enumerate(tags)}5words = ["time", "flies", "like", "an", "arrow"]67pi = np.zeros(len(tags)); pi[ix["NN"]], pi[ix["VB"]] = 0.2, 0.058A = np.zeros((len(tags), len(tags))) # A[i, j] = p(tag j | tag i); the rest of each row goes to unseen tags9for (a, b), p in {("NN", "VBZ"): 0.1, ("NN", "NNS"): 0.05, ("VB", "VBZ"): 0.002, ("VB", "NNS"): 0.1,10 ("VBZ", "IN"): 0.1, ("VBZ", "VBP"): 0.001, ("NNS", "IN"): 0.1, ("NNS", "VBP"): 0.4,11 ("IN", "DT"): 0.4, ("VBP", "DT"): 0.3, ("DT", "NN"): 0.5}.items():12 A[ix[a], ix[b]] = p13B = {"time": {"NN": 2e-3, "VB": 5e-4}, "flies": {"VBZ": 4e-4, "NNS": 1e-4},14 "like": {"IN": 1e-2, "VBP": 1e-2}, "an": {"DT": 5e-2}, "arrow": {"NN": 1e-4}}15emit = np.array([[B[w].get(t, 0.0) for t in tags] for w in words]) # (n, K)1617def viterbi(pi, A, emit):18 with np.errstate(divide="ignore"): # log 0 = -inf for impossible cells19 lp, lA, le = np.log(pi), np.log(A), np.log(emit)20 n, K = emit.shape21 delta, back = lp + le[0], np.zeros((n, K), dtype=int)22 for t in range(1, n):23 scores = delta[:, None] + lA # (prev K, next K)24 back[t] = scores.argmax(0)25 delta = scores.max(0) + le[t]26 path = [int(delta.argmax())]27 for t in range(n - 1, 0, -1):28 path.append(int(back[t, path[-1]]))29 return [tags[i] for i in path[::-1]], delta.max()3031path, logp = viterbi(pi, A, emit)32print(path, f"{np.exp(logp):.2e}") # ['NN', 'VBZ', 'IN', 'DT', 'NN'] 1.60e-17Check yourself
With K = 45 tags and a 25-token sentence, how many tag sequences are there, and roughly how many max-product operations does Viterbi need?
Check yourself
Why can greedy left-to-right decoding pick a worse tag sequence than Viterbi under the same HMM?
Remember
- ✓POS tagging: one tag per token from 45 PTB or 17 UPOS tags; context resolves ambiguity.
- ✓HMM: ; Viterbi finds the best of sequences in .
- ✓Neural taggers classify contextual states: char + word BiLSTM (≈97.5% WSJ), then fine-tuned transformers.
- ✓Greedy decoding can be wrong where Viterbi is exact; in the figure Viterbi switches above 0.133 and greedy only above 0.40.
- ✓Token accuracy near 97–98% hides sentence-level errors and annotation noise.