Part-of-speech tagging

POS tagging gives every token a word class (17 UD or 45 Penn Treebank tags); HMMs decoded by Viterbi reach about 96–97% on WSJ, BiLSTM and transformer taggers about 97.5–97.9%, close to the limit set by annotation noise.

7 min read597 wordscore0 viewsupdated 2026-10-15

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 x1,…,xnx_1,\dots,x_n. Output: one tag per token, y1,…,yny_1,\dots,y_n. 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.

one tag per token; the tag depends on context (flies: VBZ here, NNS in "fruit flies")wordsUPOS (17 tags)PTB (45 tags)TimeNOUNNNfliesVERBVBZlikeADPINanDETDTarrowNOUNNN.PUNCT.UD: one tag set across 100+ languages · PTB: English-only, finer (VBZ = 3rd-sg present verb)1. HMM (generative)2. BiLSTM tagger3. Transformer taggerNNtimeVBZfliesINlikep(x,y) = Π p(y_t | y_t−1)× p(x_t | y_t)counts from a treebankdecode: Viterbi, O(n·K²)TnT (Brants, 2000): trigramchars → char-BiLSTM⊕ word embedding→ LSTM + ← LSTMsoftmax over K tagstags see the whole sentencechars handle suffixes and OOVPlank et al. (2016), 22 langssubwords (WordPiece/SP)pre-trained encoderfirst-piece linear headfine-tuned end to endmultilingual encoders tagUD treebanks in many languagesoptional CRF/Viterbi on topWSJ accuracy: most-frequent tag ≈ 90% · HMM ≈ 96–97% · neural ≈ 97.5–97.9% (sentence-level far lower)
fig."Time flies like an arrow ." tagged in UPOS and PTB, and the three generations of taggers. The HMM is a generative chain of tags emitting words, estimated by counting and decoded with Viterbi. A BiLSTM reads character and word embeddings in both directions and puts a softmax on each token. A fine-tuned transformer encoder does the same on subword pieces, classifying each word's first piece.

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.

p(x,y)=∏t=1np(yt∣yt−1) p(xt∣yt),δt(j)=max⁡i  δt−1(i) p(j∣i)  p(xt∣j)p(x,y)=\prod_{t=1}^{n}p(y_t\mid y_{t-1})\,p(x_t\mid y_t),\qquad \delta_t(j)=\max_i\;\delta_{t-1}(i)\,p(j\mid i)\;p(x_t\mid j)
p(yt∣yt−1)p(y_t\mid y_{t-1})
transition probability; y0y_0 is a start symbol (a trigram tagger conditions on two previous tags)
p(xt∣yt)p(x_t\mid y_t)
emission probability of the word given its tag
δt(j)\delta_t(j)
probability of the best tag prefix ending in tag jj at position tt; a back-pointer stores the maximising ii

There are KnK^n tag sequences, but the best one can be found exactly in O(nK2)O(nK^2). The recursion works because the best path into tag jj at step tt must extend the best path into one of the tags at t−1t-1. Take max⁡jδn(j)\max_j\delta_n(j), then follow the back-pointers. Replacing max by sum gives the forward algorithm and p(x)=∑jαn(j)p(x)=\sum_j\alpha_n(j).

Neural taggers

Neural taggers are discriminative. They compute a context vector per token and classify it, trained with cross-entropy against the gold tags:

ht=[LSTM→(e1:t);  LSTM←(et:n)],p(yt∣x)=softmax⁡(Wht+b),et=[wxt; cxt]h_t=\big[\overrightarrow{\mathrm{LSTM}}(e_{1:t});\;\overleftarrow{\mathrm{LSTM}}(e_{t:n})\big],\qquad p(y_t\mid x)=\operatorname{softmax}(Wh_t+b),\qquad e_t=\big[w_{x_t};\,c_{x_t}\big]
wxtw_{x_t}
word embedding (pre-trained, e.g. Word2Vec or GloVe)
cxtc_{x_t}
character-level BiLSTM or CNN encoding of the word, which captures suffixes such as "-ly" and "-ing" and handles unseen words
hth_t
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%
HMM Viterbi: δ_t(j) = max_i δ_t−1(i) · p(j | i) · p(w_t | j) · p(NNS | NN) = 0.05timeflieslikeanarrowNNδ 4.00e-4VBδ 2.50e-5VBZδ 1.60e-8NNSδ 2.00e-9INδ 1.60e-11VBPδ 8.00e-12DTδ 3.20e-13NNδ 1.60e-17━ Viterbi path · ─ back-pointer (best predecessor) · ┄ other transitions · ╌ greedy pathall 8 tag sequences, p(y | x) = p(x, y) / p(x)NN VBZ IN DT NN0.6361.60e-17 Viterbi greedyNN NNS VBP DT NN0.2396.00e-18NN NNS IN DT NN0.0802.00e-18VB NNS VBP DT NN0.0307.50e-19VB NNS IN DT NN0.0102.50e-19NN VBZ VBP DT NN0.0051.20e-19VB VBZ IN DT NN0.0012.00e-20VB VBZ VBP DT NN0.0001.50e-22p(x) = Σ α_5 = 2.51e-17 · best path 1.60e-17 = 0.636 of the massgreedy agrees with Viterbi: NN VBZ IN DT NN
greedy path
fig.Viterbi on a toy HMM for "time flies like an arrow". Each cell shows δ, the best prefix probability. At the default p(NNS | NN) = 0.05 the best path is NN VBZ IN DT NN with p(x, y) = 1.60e-17, 0.636 of p(x) = 2.51e-17, and the noun-compound reading NN NNS VBP DT NN has 0.239. From 0.14 Viterbi switches to the compound reading (0.425 at 0.14), while greedy decoding keeps VBZ, because at "flies" it cannot see that "like" fits a plural subject better. At 0.20 greedy's path is 1.50× less likely than Viterbi's; above 0.40 greedy switches too.

Worked example: Viterbi by hand

Same toy HMM, p(NNS | NN) = 0.05

  1. 1time: δ(NN)=0.2⋅0.002=4.00×10−4\delta(\text{NN})=0.2\cdot0.002=4.00\times10^{-4}, δ(VB)=0.05⋅0.0005=2.50×10−5\delta(\text{VB})=0.05\cdot0.0005=2.50\times10^{-5}.
  2. 2flies: δ(VBZ)=max⁡(4 ⁣× ⁣10−4⋅0.1,  2.5 ⁣× ⁣10−5⋅0.002)⋅4 ⁣× ⁣10−4=1.60×10−8\delta(\text{VBZ})=\max(4\!\times\!10^{-4}\cdot0.1,\;2.5\!\times\!10^{-5}\cdot0.002)\cdot4\!\times\!10^{-4}=1.60\times10^{-8} (from NN); δ(NNS)=max⁡(4 ⁣× ⁣10−4⋅0.05,  2.5 ⁣× ⁣10−5⋅0.1)⋅10−4=2.00×10−9\delta(\text{NNS})=\max(4\!\times\!10^{-4}\cdot0.05,\;2.5\!\times\!10^{-5}\cdot0.1)\cdot10^{-4}=2.00\times10^{-9} (from NN).
  3. 3like: δ(IN)=max⁡(1.6 ⁣× ⁣10−8⋅0.1,  2 ⁣× ⁣10−9⋅0.1)⋅0.01=1.60×10−11\delta(\text{IN})=\max(1.6\!\times\!10^{-8}\cdot0.1,\;2\!\times\!10^{-9}\cdot0.1)\cdot0.01=1.60\times10^{-11} (from VBZ); δ(VBP)=max⁡(1.6 ⁣× ⁣10−8⋅0.001,  2 ⁣× ⁣10−9⋅0.4)⋅0.01=8.00×10−12\delta(\text{VBP})=\max(1.6\!\times\!10^{-8}\cdot0.001,\;2\!\times\!10^{-9}\cdot0.4)\cdot0.01=8.00\times10^{-12} (from NNS).
  4. 4an: δ(DT)=max⁡(1.6 ⁣× ⁣10−11⋅0.4,  8 ⁣× ⁣10−12⋅0.3)⋅0.05=3.20×10−13\delta(\text{DT})=\max(1.6\!\times\!10^{-11}\cdot0.4,\;8\!\times\!10^{-12}\cdot0.3)\cdot0.05=3.20\times10^{-13} (from IN). arrow: δ(NN)=3.2 ⁣× ⁣10−13⋅0.5⋅10−4=1.60×10−17\delta(\text{NN})=3.2\!\times\!10^{-13}\cdot0.5\cdot10^{-4}=1.60\times10^{-17}.
  5. 5Back-pointers from the end: NN ← DT ← IN ← VBZ ← NN, so the tags are NN VBZ IN DT NN. The compound path has probability 1.2×10−16 s1.2\times10^{-16}\,s, which overtakes 1.6×10−171.6\times10^{-17} when s>0.133s>0.133.
python
1import numpy as np
2
3tags = ["NN", "NNS", "VB", "VBZ", "VBP", "IN", "DT"]
4ix = {t: i for i, t in enumerate(tags)}
5words = ["time", "flies", "like", "an", "arrow"]
6
7pi = np.zeros(len(tags)); pi[ix["NN"]], pi[ix["VB"]] = 0.2, 0.05
8A = np.zeros((len(tags), len(tags))) # A[i, j] = p(tag j | tag i); the rest of each row goes to unseen tags
9for (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]] = p
13B = {"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)
16
17def viterbi(pi, A, emit):
18 with np.errstate(divide="ignore"): # log 0 = -inf for impossible cells
19 lp, lA, le = np.log(pi), np.log(A), np.log(emit)
20 n, K = emit.shape
21 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()
30
31path, logp = viterbi(pi, A, emit)
32print(path, f"{np.exp(logp):.2e}") # ['NN', 'VBZ', 'IN', 'DT', 'NN'] 1.60e-17
Log-space Viterbi in numpy on the same toy HMM (runs as is)

Check 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: p(x,y)=∏p(yt∣yt−1)p(xt∣yt)p(x,y)=\prod p(y_t\mid y_{t-1})p(x_t\mid y_t); Viterbi finds the best of KnK^n sequences in O(nK2)O(nK^2).
  • ✓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.
← back to Deep Learning roadmap