# 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.

Source: https://www.mlfoundry.in/learn/part-of-speech-tagging  
Section: Deep Learning › Deep Learning for NLP  
Level: core · 7 min read · updated 2026-10-15

**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 $x_1,\dots,x_n$. Output: one tag per token, $y_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.

> Figure: "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)=\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(y_t\mid y_{t-1})$: transition probability; $y_0$ is a start symbol (a trigram tagger conditions on two previous tags)
- $p(x_t\mid y_t)$: emission probability of the word given its tag
- $\delta_t(j)$: probability of the best tag prefix ending in tag $j$ at position $t$; a back-pointer stores the maximising $i$

There are $K^n$ tag sequences, but the best one can be found exactly in $O(nK^2)$. The recursion works because the best path into tag $j$ at step $t$ must extend the best path into one of the tags at $t-1$. Take $\max_j\delta_n(j)$, then follow the back-pointers. Replacing max by sum gives the forward algorithm and $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:

$$
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]
$$

- $w_{x_t}$: word embedding (pre-trained, e.g. Word2Vec or GloVe)
- $c_{x_t}$: character-level BiLSTM or CNN encoding of the word, which captures suffixes such as "-ly" and "-ing" and handles unseen words
- $h_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%

> Figure: 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. **time**: $\delta(\text{NN})=0.2\cdot0.002=4.00\times10^{-4}$, $\delta(\text{VB})=0.05\cdot0.0005=2.50\times10^{-5}$.
2. **flies**: $\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); $\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. **like**: $\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); $\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. **an**: $\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**: $\delta(\text{NN})=3.2\!\times\!10^{-13}\cdot0.5\cdot10^{-4}=1.60\times10^{-17}$.
5. Back-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\times10^{-16}\,s$, which overtakes $1.6\times10^{-17}$ when $s>0.133$.

```python
import numpy as np

tags = ["NN", "NNS", "VB", "VBZ", "VBP", "IN", "DT"]
ix = {t: i for i, t in enumerate(tags)}
words = ["time", "flies", "like", "an", "arrow"]

pi = np.zeros(len(tags)); pi[ix["NN"]], pi[ix["VB"]] = 0.2, 0.05
A = np.zeros((len(tags), len(tags)))   # A[i, j] = p(tag j | tag i); the rest of each row goes to unseen tags
for (a, b), p in {("NN", "VBZ"): 0.1, ("NN", "NNS"): 0.05, ("VB", "VBZ"): 0.002, ("VB", "NNS"): 0.1,
                  ("VBZ", "IN"): 0.1, ("VBZ", "VBP"): 0.001, ("NNS", "IN"): 0.1, ("NNS", "VBP"): 0.4,
                  ("IN", "DT"): 0.4, ("VBP", "DT"): 0.3, ("DT", "NN"): 0.5}.items():
    A[ix[a], ix[b]] = p
B = {"time": {"NN": 2e-3, "VB": 5e-4}, "flies": {"VBZ": 4e-4, "NNS": 1e-4},
     "like": {"IN": 1e-2, "VBP": 1e-2}, "an": {"DT": 5e-2}, "arrow": {"NN": 1e-4}}
emit = np.array([[B[w].get(t, 0.0) for t in tags] for w in words])   # (n, K)

def viterbi(pi, A, emit):
    with np.errstate(divide="ignore"):                 # log 0 = -inf for impossible cells
        lp, lA, le = np.log(pi), np.log(A), np.log(emit)
    n, K = emit.shape
    delta, back = lp + le[0], np.zeros((n, K), dtype=int)
    for t in range(1, n):
        scores = delta[:, None] + lA                     # (prev K, next K)
        back[t] = scores.argmax(0)
        delta = scores.max(0) + le[t]
    path = [int(delta.argmax())]
    for t in range(n - 1, 0, -1):
        path.append(int(back[t, path[-1]]))
    return [tags[i] for i in path[::-1]], delta.max()

path, logp = viterbi(pi, A, emit)
print(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)

> **97% sounds better than it is:** At 97% token accuracy, a 25-token sentence has 0.75 expected errors. Manning (2011) found that only a little over half of WSJ test sentences are tagged entirely correctly, and that many remaining "errors" are inconsistencies in the gold annotation. Report sentence accuracy or accuracy on unknown words when comparing strong taggers.

> **Work in log space:** Five words already give $p=1.6\times10^{-17}$; a 40-word sentence underflows float32. Viterbi only needs sums and maxima of log probabilities, and neural CRF layers run the same recursion on unnormalised log scores.

**Question:** 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?

- A. 45 × 25 sequences; 45 operations
- B. 45²⁵ ≈ 2.1·10⁴¹ sequences; 25 · 45² = 50,625 operations
- C. 25⁴⁵ sequences; 25 · 45 operations
- D. Both about 10⁶

**Answer:** B. 45²⁵ ≈ 2.1·10⁴¹ sequences; 25 · 45² = 50,625 operations — Each of the $n$ positions can take any of $K$ tags, so there are $K^n=45^{25}\approx2.1\times10^{41}$ sequences. Viterbi considers, at each position, every (previous tag, next tag) pair: $nK^2=50{,}625$.

**Question:** Why can greedy left-to-right decoding pick a worse tag sequence than Viterbi under the same HMM?

- A. Greedy uses different probabilities
- B. Greedy commits at each word using only the past, so it cannot revise a choice when later words favour another tag
- C. Viterbi uses a larger tag set
- D. Greedy ignores emission probabilities

**Answer:** B. Greedy commits at each word using only the past, so it cannot revise a choice when later words favour another tag — Greedy chooses $y_t$ from $p(y_t\mid y_{t-1})p(x_t\mid y_t)$ alone. In the figure at $p(\text{NNS}\mid\text{NN})=0.2$, VBZ wins locally at "flies", but NNS then fits "like" as VBP far better; Viterbi keeps both hypotheses alive until the end.

**Key points**

- POS tagging: one tag per token from 45 PTB or 17 UPOS tags; context resolves ambiguity.
- HMM: $p(x,y)=\prod p(y_t\mid y_{t-1})p(x_t\mid y_t)$; Viterbi finds the best of $K^n$ sequences in $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.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
