Part-of-Speech Tagging

Consider the sentence "Time flies like an arrow." A human reads this effortlessly. But a machine must decide whether "time" is a noun or a verb. It must also decide whether "flies" is a verb or a plural noun. Similarly, it must judge whether "like" is a preposition or a verb. Every one of these choices changes the sentence's meaning entirely. "Time flies" could describe insects being timed, or the swift passage of time. Part-of-speech (POS) tagging is the task of resolving exactly this ambiguity. It means assigning each token in a sentence a grammatical category. Categories include noun, verb, adjective, or preposition. The assignment is based on both the word itself and its context. This task sits at the foundation of nearly every classical NLP pipeline. Syntactic parsers use POS tags as their primary input signal. They use these tags to build phrase-structure or dependency trees. Named-entity recognizers use tags to distinguish proper nouns from common ones. Information retrieval systems use tags to identify meaningful content words. Even modern neural pipelines often skip explicit tagging in favor of contextual embeddings. Still, they were built on decades of research. That research's core insight was this: grammatical category is inherently ambiguous and must be resolved using context. This insight still underlies how token-level classification works in general. The central difficulty is that most word types are ambiguous. The correct tag for a token depends on its neighbors. The word "book" is a noun in "the book was long." But it is a verb in "book the flight." A tagger that only memorizes each word's most frequent tag will get most words right. English tagging is roughly 90% solvable this way. But the residual errors compound catastrophically in downstream tasks. A single wrong tag can derail an entire parse. Solving this properly requires modeling sequences, not just isolated words. This is exactly the bridge this article builds toward. This article develops POS tagging from first principles. It covers what a tagset is, and why ambiguity is pervasive. It shows how to formalize tagging as a sequence-labeling problem. It also explains how classical statistical taggers combine lexical and contextual evidence. This combination enables consistent, high-accuracy predictions. It closes by showing how the probabilistic view of tagging leads directly into Hidden Markov Models. It also shows how the tagged output feeds into Named-Entity Recognition and Syntactic Parsing.

Key takeaways

POS tagging assigns each token a grammatical category (noun, verb, adjective, etc.) from a fixed tagset.
Ambiguity is pervasive: most frequent English words have multiple possible tags depending on context.
Tagging is framed as sequence labeling: choose the tag sequence that best fits the whole sentence, not each word alone.
Classical taggers combine emission evidence (word→tag likelihood) with transition evidence (tag→tag likelihood).
The Viterbi algorithm finds the globally optimal tag sequence efficiently via dynamic programming.
POS tags are the backbone feature feeding Syntactic Parsing, Named-Entity Recognition, and later Hidden Markov Models-based sequence models.

The core insight

Part-of-speech tagging resolves word-level grammatical ambiguity by choosing the tag sequence that jointly maximizes both how well each tag fits its word and how well adjacent tags fit each other.

The idea

A tagset is a finite inventory of grammatical categories used to label tokens, ranging from coarse schemes with roughly a dozen classes (noun, verb, adjective, adverb, pronoun, preposition, conjunction, determiner, interjection, and a few others) to fine-grained schemes like the Penn Treebank tagset, which distinguishes over 40 tags including subcategories such as `NN` (singular noun), `NNS` (plural noun), `VBD` (past-tense verb), and `VBG` (gerund/present participle). The choice of tagset is a design decision: coarser tagsets are easier to predict accurately but carry less linguistic information; finer tagsets carry more information but are harder to predict and require more training data.

Part-of-speech tagging is the task of mapping a sequence of tokens $w_1, w_2, \ldots, w_n$ to a sequence of tags $t_1, t_2, \ldots, t_n$ , one tag per token, drawn from the tagset. Formally it is a sequence labeling problem: the output is not a single label for the whole input, but a structured sequence of labels, one aligned to each input position. This distinguishes it from simple classification (one label per instance) and motivates the entire machinery of sequence models used throughout NLP. The core obstacle is lexical ambiguity: the same word type can take different tags in different contexts. Studies of tagged corpora show that while the majority of English word types are unambiguous, the majority of word tokens in running text belong to ambiguous types, because common function words and frequent verbs are exactly the ones with multiple tags. "That" can be a determiner ("that book"), a complementizer ("I know that he left"), or a pronoun ("that is true"). Resolving this requires context: the tags of neighboring words, and the broader syntactic pattern of the sentence, both constrain which reading is plausible. A tagger that ignores context and always picks a word's single most frequent tag is called a most-frequent-class baseline; it is a genuinely strong baseline in English (roughly 92% token accuracy) precisely because tag ambiguity, while pervasive at the type level, is skewed at the token level — but it is not adequate for any pipeline that depends on getting the ambiguous 8% right, since those are disproportionately the words that determine syntactic structure.

How it works

The classical statistical approach treats tagging as finding the tag sequence $t_1^n$ that maximizes the joint probability of the words and tags together, given a trained model:

\hat{t}_1^n = \arg\max_{t_1^n} \; P(t_1^n \mid w_1^n)

Applying Bayes' rule and dropping the constant denominator $P(w_1^n)$ :

\hat{t}_1^n = \arg\max_{t_1^n} \; P(w_1^n \mid t_1^n) \, P(t_1^n)

To make this tractable, two independence assumptions are introduced — the same assumptions that define a bigram Hidden Markov Model tagger, the natural next step after this article: 1. Emission (output) independence: each word depends only on its own tag, not on neighboring words or tags:

P(w_1^n \mid t_1^n) \approx \prod_{i=1}^n P(w_i \mid t_i)

2. Markov (transition) assumption: each tag depends only on the preceding tag (bigram case), not the entire tag history:

P(t_1^n) \approx \prod_{i=1}^n P(t_i \mid t_{i-1})

Combining these gives the tagging objective actually optimized in practice:

\hat{t}_1^n = \arg\max_{t_1^n} \; \prod_{i=1}^n P(w_i \mid t_i) \, P(t_i \mid t_{i-1})

Both factors are estimated from a tagged training corpus by counting. Emission probabilities $P(w \mid t)$ are estimated as $\frac{\text{count}(t, w)}{\text{count}(t)}$ : how often tag $t$ produces word $w$ , out of all tokens with tag $t$ . Transition probabilities $P(t_i \mid t_{i-1})$ are estimated as $\frac{\text{count}(t_{i-1}, t_i)}{\text{count}(t_{i-1})}$ : how often tag $t_{i-1}$ is followed by tag $t_i$ . Special boundary symbols mark sentence start (`⟨s⟩`) and end (`⟨/s⟩`) so the first and last tags are also conditioned properly. Naively, finding the best tag sequence requires enumerating all $|T|^n$ possible sequences for a tagset of size $|T|$ and sentence length $n$ — exponential and infeasible even for short sentences. The Viterbi algorithm solves this exactly via dynamic programming in polynomial time, exploiting the fact that the bigram Markov assumption makes the optimal sequence decomposable: the best path to position $i$ ending in tag $t$ only depends on the best path to position $i-1$ ending in each possible tag, never on the full history before that.

Step-by-step mechanism: 1. Initialization: for each tag $t$ , compute the probability of starting the sentence with $t$ and emitting the first word: $v_1(t) = P(t \mid \langle s \rangle) \cdot P(w_1 \mid t)$ . 2. Recursion: for each subsequent position $i$ and each tag $t$ , take the best score from all possible previous tags $t'$ , multiplied by the transition and emission probabilities:

v_i(t) = \max_{t'} \; v_{i-1}(t') \cdot P(t \mid t') \cdot P(w_i \mid t)

and record which $t'$ achieved this maximum (the backpointer). 3. Termination: multiply in the end-of-sentence transition and take the overall maximum. 4. Backtrace: follow the backpointers from the best final state back to position 1, reading off the optimal tag sequence. ``` function VITERBI-TAG(words[1..n], tagset T, transitionProb, emissionProb): // v[i][t] = probability of the best tag sequence for words[1..i] // that ends with tag t at position i v = array of size (n+1) x |T|, initialized to 0 backptr = array of size (n+1) x |T|, initialized to null // 1. Initialization: first word for each tag t in T: v[1][t] = P(t | START) P(words[1] | t) backptr[1][t] = START // 2. Recursion: fill the trellis left to right for i = 2 to n: for each tag t in T: bestScore = -infinity bestPrev = null for each tag tPrev in T: score = v[i-1][tPrev] transitionProb(t | tPrev) emissionProb(words[i] | t) if score > bestScore: bestScore = score bestPrev = tPrev v[i][t] = bestScore backptr[i][t] = bestPrev // 3. Termination: close out with END transition bestFinalScore = -infinity bestFinalTag = null for each tag t in T: score = v[n][t] transitionProb(END | t) if score > bestFinalScore: bestFinalScore = score bestFinalTag = t // 4. Backtrace: recover the optimal path tags = array of size n tags[n] = bestFinalTag for i = n down to 2: tags[i-1] = backptr[i][tags[i]] return tags ``` A practical detail: raw word emission counts fail on unknown words (words never seen in training). Real taggers back off to morphological and orthographic cues — suffixes like "-ing" or "-ly", capitalization, hyphenation, digit patterns — treating an unknown word's tag distribution as a function of its shape rather than its identity. This is exactly where Morphology and Stemming resurfaces: the internal structure of a word (its stem, affixes, and inflection) supplies the features that let a tagger guess plausibly even for words it has never encountered.

Figure

Viterbi trellis for tagging "time flies fast" — bold path is the decoded sequence

Complexity & correctness

Time complexity. The Viterbi recursion fills a trellis of size $n \times |T|$ , where $n$ is the sentence length and $|T|$ is the tagset size. Computing each cell $v_i(t)$ requires examining every possible previous tag $t'$ , an $O(|T|)$ operation, so filling the whole trellis costs

O(n \cdot |T|^2).

This is a dramatic improvement over the naive $O(|T|^n)$ brute-force enumeration of all tag sequences. Since $|T|$ is a small constant (tens of tags) fixed independently of sentence length, Viterbi tagging is effectively linear in sentence length, making it fast enough for real-time and large-corpus use.

Space complexity. The trellis itself requires $O(n \cdot |T|)$ space to store scores and backpointers. This can be reduced to $O(|T|)$ if only the final tag sequence (not intermediate scores) is needed and backpointers are stored separately, but in practice the full $O(n|T|)$ trellis is kept since it is cheap and simplifies the backtrace.

Correctness argument. The proof that Viterbi finds the globally optimal tag sequence — not merely a locally good one — rests on an optimal-substructure invariant, provable by induction on sentence position: Claim: $v_i(t)$ , as computed by the recursion, equals the probability of the single highest-probability tag sequence for $w_1, \ldots, w_i$ that ends with tag $t$ at position $i$ . Base case ( $i=1$ ): $v_1(t) = P(t \mid \langle s\rangle) P(w_1 \mid t)$ is trivially the probability of the only length-1 sequence ending in $t$ , so the claim holds. Inductive step: assume $v_{i-1}(t')$ is correct for every tag $t'$ . Any tag sequence of length $i$ ending in $t$ must pass through some tag $t'$ at position $i-1$ . Because of the Markov and emission independence assumptions, the probability of any such length- $i$ sequence factors as

(\text{probability of its length-}(i-1)\text{ prefix}) \times P(t \mid t') \times P(w_i \mid t),

so for fixed $t'$ , the best sequence through $t'$ must use the best length- $(i-1)$ prefix ending in $t'$ — that is exactly $v_{i-1}(t')$ by the inductive hypothesis. Maximizing over all choices of $t'$ , as the recursion does, therefore finds the true best sequence ending in $t$ at position $i$ . This is precisely why the Markov assumption is not just a convenience but a correctness enabler: it guarantees that the best path to any state depends only on the best paths to the previous states, never on how those paths were reached, which is what licenses dynamic programming instead of exhaustive search. By induction this holds for all $i$ up to $n$ , and the termination step correctly selects the global maximum over all tags at the final position combined with the end-of-sentence transition.

Honest tradeoffs. The bigram independence assumptions that make Viterbi tractable are linguistically false — real tag dependencies stretch further than one step back, and word choice genuinely depends on surrounding words, not just its own tag. Higher-order Markov models (trigram taggers) partially address the first limitation at the cost of a larger effective tagset (pairs of tags as states), increasing the $|T|^2$ factor to $|T|^3$ style blow-up unless pruned. The output-independence assumption is addressed by richer models — maximum-entropy Markov models and, later, Hidden Markov Models-style sequence models with neural emissions — that condition on overlapping word features (suffixes, capitalization, neighboring words) rather than the word identity alone. Classical Viterbi tagging remains a strong, exactly-solvable baseline whose accuracy on well-resourced languages like English exceeds 96-97% token accuracy despite these simplifications, which is why it remained the production standard for decades before neural sequence taggers displaced it.

Worked example

Take the miniature sentence "can fish swim", deliberately chosen because every word is ambiguous: "can" is usually a modal verb but can be a noun ("a can"); "fish" is usually a noun but can be a verb; "swim" is a verb. Suppose a bigram tagger has been trained with the (simplified, illustrative) parameters below.

Transition $P(t_i \mid t_{i-1})$	to MD	to NN	to VB
from ⟨s⟩	0.4	0.5	0.1
from MD	0.05	0.15	0.80
from NN	0.10	0.30	0.60
from VB	0.20	0.60	0.20

Emission $P(w \mid t)$	"can"	"fish"	"swim"
MD	0.60	0.00	0.00
NN	0.05	0.50	0.20
VB	0.02	0.20	0.40

Trellis fill, step by step: Position 1 ("can"):

$v_1(\text{MD}) = 0.4 \times 0.60 = 0.240$
$v_1(\text{NN}) = 0.5 \times 0.05 = 0.025$
$v_1(\text{VB}) = 0.1 \times 0.02 = 0.002$

Position 2 ("fish"), considering all previous tags for each candidate tag:

Into MD: best of $\{0.240{\times}0.05,\ 0.025{\times}0.10,\ 0.002{\times}0.20\} = 0.012$ (from MD) $\times P(\text{fish}\mid\text{MD}){=}0$ → $v_2(\text{MD}) = 0$
Into NN: best of $\{0.240{\times}0.15,\ 0.025{\times}0.30,\ 0.002{\times}0.60\} = 0.0360$ (from MD) $\times 0.50 = 0.0180$
Into VB: best of $\{0.240{\times}0.80,\ 0.025{\times}0.60,\ 0.002{\times}0.20\} = 0.1920$ (from MD) $\times 0.20 = 0.03840$

So $v_2(\text{NN}) = 0.0180$ with backpointer MD, and $v_2(\text{VB}) = 0.03840$ with backpointer MD — "fish" as a verb, following "can" as a modal, is currently winning. Position 3 ("swim"):

Into MD: best of $\{0.0180{\times}0.05,\ 0.03840{\times}0.05\} = 0.00192$ (from VB) $\times P(\text{swim}\mid\text{MD}){=}0 \to 0$
Into NN: best of $\{0.0180{\times}0.30,\ 0.03840{\times}0.60\} = 0.02304$ (from VB) $\times 0.20 = 0.004608$
Into VB: best of $\{0.0180{\times}0.60,\ 0.03840{\times}0.20\} = 0.01080$ (from NN) $\times 0.40 = 0.004320$

Termination: multiply by end-of-sentence transition (assume roughly uniform, so it doesn't change the ranking here). The best final score is $v_3(\text{NN}) = 0.004608$ , reached via backpointer VB at position 2.

Backtrace: position 3 → NN, backpointer says position 2 → VB, backpointer says position 1 → MD.

\text{can/MD} \quad \text{fish/VB} \quad \text{swim/NN}

This is a linguistically odd but internally consistent reading ("can fish" as "are able to fish," with "swim" nominalized), which is exactly the kind of result a toy parameter table can produce — it illustrates that the algorithm is behaving correctly (always taking the true joint maximum, never a myopic per-word guess), even though the quality of the output is entirely bounded by the quality of the trained probabilities. A model trained on a real corpus, where "can fish swim" contexts are seen abundantly, would instead correctly favor "can/MD fish/VB swim/VB" or "can/NN fish/VB swim/VB" depending on true usage statistics — the mechanism is identical, only the parameters differ.

Common pitfalls & traps

Pitfall	Why it happens	Consequence
Using per-word most-frequent tag only	Ignores context; assumes independence between neighboring tags	~92% accuracy ceiling; fails exactly on the hardest, most informative ambiguous cases
Zero-probability emissions for unknown words	Word never seen in training corpus has no emission estimate	Entire sentence probability collapses to zero without smoothing or morphological backoff
Confusing tagset granularity with model quality	Fine-grained tagset (many tags) looks more informative	Sparser transition/emission tables, harder estimation, lower raw accuracy without more data
Off-by-one at sentence boundaries	Forgetting explicit `⟨s⟩`/`⟨/s⟩` handling in transition probabilities	First and last tags are systematically mis-scored, biasing whole-sentence likelihoods
Treating tagging accuracy as uniform across genres	Training corpus (e.g., news text) mismatched to deployment domain (e.g., social media, biomedical text)	Accuracy quietly drops well below reported benchmark numbers on the true target domain

Pioneers & history

Origins · 1 minFrederick Jelinek and how this was discovered

Frederick Jelinek

1932–2010 · IBM Speech Recognition Group, statistical NLP pioneer

Jelinek championed the corpus-driven, probabilistic view of language that made statistical POS tagging and speech recognition possible, famously arguing that "every time I fire a linguist, the performance of the speech recognizer improves" — a provocative claim underscoring his belief that data-driven statistical models could outperform hand-built rule systems for language processing.

History

1967

— Greene and Rubin build TAGGIT, one of the first rule-based automatic POS taggers, achieving roughly 77% accuracy on the Brown Corpus.

1983

— Steven DeRose and Kenneth Church independently develop early stochastic tagging methods using tag-sequence probabilities estimated from corpora.

1988

— Church publishes a fast, practical stochastic tagger applying the Viterbi algorithm to part-of-speech tagging with strong accuracy and speed.

1992

— The Penn Treebank project, led by Mitchell Marcus, releases a large hand-annotated corpus with its now-standard 45-tag tagset, becoming the de facto benchmark.

2000

s — Maximum-entropy and CRF-based taggers (e.g., Ratnaparkhi's MaxEnt tagger) surpass 96–97% accuracy by incorporating richer, overlapping context features beyond bigram Markov assumptions.

Where this matters

POS tagging remains embedded, often invisibly, throughout production NLP infrastructure. Search engines and grammar-checking tools use POS tags to identify verbs and nouns for query expansion and error detection (subject-verb agreement checks require knowing which token is the verb). Machine translation systems historically used source-language tags to guide reordering rules, and even modern neural MT systems are frequently evaluated in part through tagging-consistency diagnostics. Spelling and grammar correction tools (e.g., style checkers embedded in word processors) use tags to detect misused homophones and agreement errors. Voice assistants and dialogue systems use lightweight taggers as a fast pre-processing stage before deeper semantic parsing, since tagging is orders of magnitude cheaper than full parsing. Academically and pedagogically, POS tagging is the canonical first example of sequence labeling, the problem class that also includes chunking, Named-Entity Recognition, and slot-filling in dialogue systems. The exact same Viterbi machinery developed here — emission and transition probabilities, dynamic-programming decoding — generalizes directly into full Hidden Markov Models, where tags become latent states and words become observations in a general probabilistic sequence model. Once tag sequences are available, they become the standard input features for statistical Syntactic Parsing algorithms, which build hierarchical sentence structure on top of the flat tag sequence a tagger produces. In this sense POS tagging is not an isolated task but the connective layer between word-level Morphology and Stemming and sentence-level syntactic and semantic analysis.

Ask the tutor: How would the Viterbi recursion change if the tagger used trigram (second-order) tag dependencies instead of bigrams?

What exactly is a tagset, and why don't all taggers use the same one?

A tagset is the fixed inventory of grammatical category labels a tagger assigns, ranging from coarse schemes (noun, verb, adjective — a dozen or so tags) to fine-grained ones like the Penn Treebank's 45-tag inventory, which separates plural nouns from singular ones and distinguishes verb tenses. Different tagsets trade off informativeness against learnability: a fine-grained tagset gives downstream tasks like parsing richer signal but requires more training data to estimate reliably, since each additional tag fragments the counts used for emission and transition probabilities. Languages with rich morphology (like Finnish or Turkish) often need larger tagsets encoding case and agreement information that English tagsets don't need, since English expresses much of that information through word order rather than inflection.

How does POS tagging relate to Hidden Markov Models specifically?

The bigram tagging model described here — transition probabilities between tags plus emission probabilities from tags to words, decoded with Viterbi — is literally a Hidden Markov Model where the tags are hidden states and the words are observed emissions. POS tagging is the textbook first application of HMMs in NLP precisely because the problem structure (a hidden sequence generating an observed sequence) matches the HMM formalism exactly. Understanding tagging as presented here — the independence assumptions, the trellis, the Viterbi recursion, and the correctness proof by induction — transfers directly to the general HMM framework used for tasks like speech recognition and gene sequence analysis, with only the state and observation spaces changing.

Why can't we just always pick each word's single most common tag and skip the sequence model?

Because ambiguous words are disproportionately common function words and frequent verbs, ignoring context gets you a respectable-looking accuracy number (around 92% for English) while systematically failing on exactly the tokens that matter most for downstream syntax. A word like "that" appears constantly and can be a determiner, complementizer, or pronoun depending entirely on what surrounds it; guessing its single most frequent tag guarantees errors every time the less-frequent reading is correct. Since parsers and other downstream consumers are highly sensitive to errors on these structurally important words, the residual gap between context-free and context-aware tagging matters far more than the raw accuracy percentage suggests.

What happens when a tagger encounters a word it has never seen during training?

This is the unknown-word problem, and naive emission estimation fails outright because count-based probabilities for an unseen word are zero, which would make any tag sequence containing it have zero total probability. Practical taggers handle this by backing off to orthographic and morphological cues: word suffixes ("-ing" suggests a verb gerund, "-tion" suggests a noun), capitalization patterns (suggesting a proper noun), hyphenation, and digit content, each contributing evidence toward a tag distribution even without having seen the exact word before. This is precisely where insights from Morphology and Stemming resurface, since a word's internal structure is often a better guide to its category than its raw surface form when the form itself is novel.

How is tagger accuracy actually measured, and what accuracy is considered good?

Tagger accuracy is typically measured as the percentage of tokens assigned the correct tag against a held-out, human-annotated gold-standard corpus, most commonly a section of the Penn Treebank for English. A most-frequent-tag baseline reaches roughly 92% token accuracy; classical bigram HMM Viterbi taggers typically reach 95-96%; feature-rich statistical taggers (maximum-entropy, CRF-based) and modern neural sequence taggers reach 97% or higher on standard benchmarks. Because errors compound in downstream syntactic parsing and semantic tasks, even the gap between 95% and 97% accuracy represents a meaningful difference in how often an entire sentence is tagged perfectly, since sentence-level accuracy drops much faster than token-level accuracy as sentence length grows.

Does POS tagging still matter given large neural language models that don't explicitly tag anything?

Yes, though its role has shifted from an explicit pipeline stage to an implicit and diagnostic one. Modern transformer-based models learn contextual representations that implicitly encode part-of-speech information, which can be probed and extracted, but pure POS tagging remains a standard lightweight component in latency-sensitive systems, in linguistic annotation pipelines, in low-resource languages lacking large pretrained models, and as a diagnostic benchmark for evaluating what syntactic knowledge a representation captures. It is also foundational pedagogically: the emission/transition decomposition and Viterbi decoding introduced for tagging generalize directly to Hidden Markov Models and set up the sequence-labeling formalism used throughout Named-Entity Recognition and structured prediction generally.