Sequence Labeling: POS and NER

Many language problems have the same shape: read a sentence left to right and attach a label to each word. Deciding that book is a verb in book that flight but a noun in hand me that book is one such problem; finding that United Airlines names an organization is another. Both are instances of sequence labeling — map an input sequence of tokens $w_1:w_n$ to an output sequence of tags $t_1:t_n$ of the same length, one tag per token.¹

The dependence between labels is the difficulty. If the tags were independent we could classify each token on its own with the logistic regression of an earlier lesson. They are not: a determiner is far more likely to be followed by a noun than by a verb, so a good tagger scores the sequence of tags jointly. This lesson develops two models that do exactly that — the hidden Markov model and the conditional random field — and the single decoding algorithm, Viterbi, that both share.

Parts of speech

Part-of-speech tagging is the process of assigning a part-of-speech label to each word in a sequence.² Parts of speech (also called POS, word classes, or syntactic categories) tell us something about how a word behaves and about its neighbors: nouns tend to follow determiners and adjectives, verbs take nouns as arguments. Knowing a word's part of speech is a useful early step for parsing, coreference, and named-entity recognition.

Word classes divide into two families. Closed classes have a fixed, small membership that rarely admits new words: prepositions (of, in, by), determiners (a, the, this), pronouns (I, you, she), conjunctions (and, but, that), auxiliaries (be, have, can, must), and particles. These are the function words — short, frequent, and grammatical rather than contentful. Open classes accept new members freely and carry the content: nouns, verbs, adjectives, and adverbs. English coins new nouns and verbs constantly (to google, a selfie); it does not coin new prepositions.

To tag a corpus you need a tagset: an agreed inventory of labels. Tagsets for English run from about 40 to 200 tags; the most widely used is the 45-tag Penn Treebank tagset,³ which has labelled many syntactically annotated corpora. It splits the open classes finely — verbs alone get six tags (VB base, VBD past, VBG gerund, VBN past participle, VBP non-third-singular present, VBZ third-singular present) — and gives short codes to the closed classes.

POS tagging is a disambiguation task: most word types have a single tag (Janet is always NNP, hesitantly always RB), but the ambiguous types — only 14–15% of the vocabulary — are the common words, so 55–67% of word tokens in running text are ambiguous.⁴ The word back alone can be JJ (the back seat), NN (in the back), VBP (back the bill), VB (back toward the door), RP (buy back), or RB (back then). The tagger's job is to pick the right one from context.

The most-frequent-class baseline assigns each token the tag it carried most often in the training corpus. That trivial rule already reaches about 92% accuracy on English, and good taggers — HMM, CRF, or neural, it barely matters which — reach about 97%, close to the human ceiling.⁵ Always compare a classifier against a baseline at least this strong.

Named entities and BIO tagging

A named entity is anything that can be referred to with a proper name: a person, a location, an organization. The task of named-entity recognition (NER) finds spans of text that constitute proper names and labels each with its type — most commonly PER (person), LOC (location), ORG (organization), or GPE (geo-political entity), though the term stretches to cover dates, times, and prices.⁶ Unlike POS tagging, where every token gets exactly one tag, NER must find spans: United Airlines Holding is one three-word organization, and a sentence may have named-entity spans of any length interleaved with ordinary words that belong to no entity.

Spans do not fit the one-tag-per-token mold directly. The standard fix, BIO tagging, encodes the span structure into per-token labels so NER becomes an ordinary sequence-labeling problem.⁷ Each token gets one of three kinds of tag: B-type marks the token that begins a span of that type, I-type marks a token inside (continuing) a span, and a single O marks any token outside every span. With $n$ entity types the scheme uses $2n+1$ tags. The BIO labels capture exactly the same information as bracketed spans, but as a flat tag sequence a tagger can produce token by token.

Two variant schemes trade detail for tag count. IO tagging drops the B tag, using only I-type and O; it is smaller but cannot separate two same-type entities that abut. BIOES adds an E-type end tag and an S-type tag for single-token spans, encoding more structure at the cost of more tags. BIO is the common middle ground.

Because NER is span recognition, its errors and its evaluation differ from POS tagging. The unit of response is the entity, not the word, so a system that labels Jane but misses Jane Villanueva commits two errors at once — a false positive and a false negative. NER is scored by precision, recall, and their harmonic mean, the $F_1$ measure, rather than by plain token accuracy.

For example, suppose a gold document contains $100$ entity spans, and a system predicts $90$ spans, of which $72$ exactly match a gold span (right boundaries, right type). Then precision is $P=72/90=0.80$ (of what it proposed, $80\%$ was right), recall is $R=72/100=0.72$ (of what existed, it found $72\%$), and

The harmonic mean sits below the arithmetic mean of $0.76$, and much closer to the lower of the two scores — a system that is lopsided (high precision, low recall, or the reverse) is punished. Because the span is the unit, labeling Jane when the gold span is Jane Villanueva is a boundary error that costs both a false positive (the wrong span Jane) and a false negative (the missed span Jane Villanueva), which is why NER scores run well below the per-token accuracies of POS tagging.

The hidden Markov model

The hidden Markov model (HMM) is the classic probabilistic sequence tagger, and it introduces machinery — states, transitions, emissions, and Viterbi decoding — that reappears in every model after it.⁸ It is a generative model: it models how a tagged sentence is produced, then inverts that model to recover the tags.

The HMM builds on the Markov chain, a model of sequences of states that makes one strong assumption: to predict the next state, only the current state matters — the states before it have no further influence. Formally, for a sequence of states $q_1,q_2,\dots ,q_n$,

A Markov chain assigns probabilities to sequences of observable events. But the events we care about in tagging — the parts of speech — are hidden: we see the words, not their tags, and must infer the tags from the words. A hidden Markov model lets us reason about both a sequence of hidden states (the tags) and a sequence of observations they generate (the words).

An HMM is specified by five components. The states are the tags $Q=q_1\dots q_N$. The transition probability matrix $A$ holds $a_{ij}=P(t_i\mid t_{i-1})$, the probability of tag $j$ following tag $i$. The observations are the words $O=o_1\dots o_T$, drawn from a vocabulary. The emission probabilities (or observation likelihoods) $B$ hold $b_i(o_t)=P(w_t\mid t_i)$, the probability that tag $i$ emits word $o_t$. Finally an initial distribution $\pi$ gives the probability of each tag starting the sequence.

A first-order HMM makes two simplifying assumptions, both visible in the figure. The first is the Markov assumption on transitions: a tag depends only on the previous tag. The second is output independence: a word depends only on its own tag, not on neighboring words or tags,

Both probability tables come from a labelled corpus by maximum-likelihood counting. The transition estimate is one tag-bigram count over one tag-unigram count, and the emission estimate is a tag-word count over the same tag count:

In the WSJ corpus, for instance, MD (modal) occurs 13124 times and is followed by VB 10471 of them, so $P(\text{VB}\mid \text{MD})=10471/13124=0.80$; the same MD state emits the word will 4046 times, so $P(\text{will}\mid \text{MD})=4046/13124=0.31$. Note the counterintuitive direction of the emission: it is the probability of the word will given that an MD is being generated — the likelihood, not the posterior $P(\text{MD}\mid \text{will})$.

HMM tagging as decoding

With $A$ and $B$ in hand, tagging is decoding: given the observations, find the most probable hidden state sequence.⁹ For $n$ words the goal is the tag sequence maximizing the posterior,

The generative model does not give this posterior directly, so we apply Bayes' rule, drop the constant denominator $P(w_1\dots w_n)$, and impose the two HMM assumptions. Output independence factors the likelihood into per-word emissions; the bigram assumption factors the prior into per-tag transitions. What remains is a product of exactly the two tables we estimated:

The two factors correspond neatly to the $B$ emission and $A$ transition probabilities. The only remaining problem is the $\mathrm{argmax}$: the number of tag sequences is $N^n$, exponential in sentence length, so we cannot enumerate them.

The argmax ranges over $N^n$ tag sequences, so brute force is infeasible — but the score factors over adjacent tags, and that local structure is what a dynamic program exploits. The next lesson builds that decoder, the Viterbi algorithm, works a full numeric trace through it, and then shows how the conditional random field keeps the same decoder while relaxing the HMM's rigid tables.

This continues in Viterbi Decoding, CRFs, and Neural Taggers.