--- title: "Sequence Labeling: POS and NER" module: Sequences moduleNumber: 4 lessonNumber: 1 order: 401 summary: > Sequence labeling assigns one tag to every token in a sentence. This first part sets up the task through its two canonical cases — part-of-speech tagging over the Penn Treebank tagset, and named-entity recognition reframed as token labeling with the BIO scheme — then builds the hidden Markov model, the classic probabilistic tagger. The HMM tags by Bayesian inference: transition and emission probabilities under two Markov assumptions, reducing tagging to an argmax over tag sequences. That argmax is exponential to enumerate, which sets up the Viterbi decoder, the CRF, and neural taggers of the next lesson. topics: [Sequences] sources: - book: Jurafsky ref: "Ch. 8 — Sequence Labeling for Parts of Speech and Named Entities; §8.1 English Word Classes; §8.2 Part-of-Speech Tagging" - book: Jurafsky ref: "§8.3 Named Entities and Named Entity Tagging; §8.4 HMM Part-of-Speech Tagging" --- 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.[^jm-seqlab] > **Definition (Sequence labeling).** A task that assigns a label from a fixed > tagset to _each_ token of an input sequence, producing an output sequence > $t_1{:}t_n$ exactly as long as the input $w_1{:}w_n$. The labels are not > independent: the right tag for a token depends on the tags around it. The dependence between labels is the difficulty. If the tags were independent we could classify each token on its own with the [logistic regression](/natural-language-processing/classification/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.[^jm-pos] 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. > **Definition (Open vs. closed class).** A **closed class** is a part of speech > with a fixed, small membership (prepositions, determiners, pronouns, > auxiliaries) — the frequent **function words**. An **open class** (noun, verb, > adjective, adverb) admits new words freely and carries most of the content. 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**,[^jm-ptb] 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. | Tag | Meaning | Example | Tag | Meaning | Example | | --- | --- | --- | --- | --- | --- | | `NN` | noun, singular | _llama_ | `DT` | determiner | _a, the_ | | `NNS` | noun, plural | _llamas_ | `IN` | preposition/subord. | _of, in, by_ | | `NNP` | proper noun, sing. | _IBM_ | `PRP` | personal pronoun | _I, you, he_ | | `JJ` | adjective | _yellow_ | `MD` | modal | _can, should_ | | `RB` | adverb | _quickly_ | `CC` | coordinating conj. | _and, but_ | | `VB` | verb, base | _eat_ | `VBZ` | verb, 3sg present | _eats_ | | `VBD` | verb, past | _ate_ | `VBP` | verb, non-3sg pres. | _eat_ | 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.[^jm-ambig] 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.[^jm-baseline] 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.[^jm-ner] 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.[^jm-bio] 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. $$ % caption: BIO tagging turns span recognition into per-token labeling. Each % word of the sentence "Jane Villanueva of United Airlines Holding discussed % the Chicago route" gets one tag: B-TYPE begins a span, I-TYPE continues it, % and O sits outside every span. \begin{tikzpicture}[>=stealth, font=\footnotesize, wbox/.style={draw, minimum width=17mm, minimum height=7mm, align=center, font=\scriptsize}, tbox/.style={minimum width=17mm, minimum height=6mm, align=center, font=\scriptsize}] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} \def\dx{1.95} \foreach \i/\w in {0/Jane, 1/Villanueva, 2/of, 3/United, 4/Airlines, 5/Holding, 6/Chicago, 7/route} \node[wbox] (w\i) at (\i*\dx, 0) {\texttt{\w}}; % BIO tags underneath, entity tags in accent, O in muted black \node[tbox, text=acc] (t0) at (0*\dx,-1.0) {\texttt{B-PER}}; \node[tbox, text=acc] (t1) at (1*\dx,-1.0) {\texttt{I-PER}}; \node[tbox, text=black] (t2) at (2*\dx,-1.0) {\texttt{O}}; \node[tbox, text=red] (t3) at (3*\dx,-1.0) {\texttt{B-ORG}}; \node[tbox, text=red] (t4) at (4*\dx,-1.0) {\texttt{I-ORG}}; \node[tbox, text=red] (t5) at (5*\dx,-1.0) {\texttt{I-ORG}}; \node[tbox, text=acc] (t6) at (6*\dx,-1.0) {\texttt{B-LOC}}; \node[tbox, text=black] (t7) at (7*\dx,-1.0) {\texttt{O}}; \foreach \i in {0,...,7} \draw[->, black] (w\i.south) -- (t\i.north); % span underbraces \draw[acc, thick] (w0.south west)++(0,-1.55) -- ++(0,-0.14) -| ($(w1.south east)+(0,-1.55)$); \node[acc, anchor=north, font=\scriptsize] at ($(w0.south east)!0.5!(w1.south west)+(0,-1.75)$) {person}; \draw[red, thick] (w3.south west)++(0,-1.55) -- ++(0,-0.14) -| ($(w5.south east)+(0,-1.55)$); \node[red, anchor=north, font=\scriptsize] at ($(w4.south)+(0,-1.75)$) {organization}; \end{tikzpicture} $$ 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 $$ F_1 = \frac{2PR}{P + R} = \frac{2(0.80)(0.72)}{0.80 + 0.72} = \frac{1.152}{1.52} = 0.758. $$ 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.[^jm-hmm] 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, \ldots, q_n$, $$ \text{(Markov assumption)}\qquad P(q_i \mid q_1 \ldots q_{i-1}) \;=\; P(q_i \mid q_{i-1}). $$ 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 \ldots 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 \ldots 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. $$ % caption: A first-order HMM tagger separates two kinds of probability. Solid % arrows are transitions $P(t_i \mid t_{i-1})$ between hidden tag-states (three % shown: NNP, MD, VB); dashed arrows are emissions $P(w_i \mid t_i)$, each state % generating an observed word with some likelihood. \begin{tikzpicture}[>=stealth, font=\footnotesize, state/.style={circle, draw=acc, thick, minimum size=11mm, align=center, font=\small}, obs/.style={draw, minimum width=15mm, minimum height=6mm, align=center, font=\scriptsize}] \definecolor{acc}{HTML}{2348F2} \node[state] (nnp) at (0,0) {NNP}; \node[state] (md) at (3.2,1.4) {MD}; \node[state] (vb) at (6.4,0) {VB}; % transitions \draw[->, acc, thick] (nnp) to[bend left=18] (md); \draw[->, acc, thick] (md) to[bend left=18] (vb); \draw[->, acc, thick] (nnp) to[bend right=14] (vb); \draw[->, acc, thick] (vb) to[bend left=18] (md); \draw[->, acc, thick] (nnp) to[out=150, in=210, looseness=6] (nnp); % emissions (dashed) to observed words \node[obs] (wj) at (0,-2.1) {Janet}; \node[obs] (ww) at (3.2,-2.1) {will}; \node[obs] (wb) at (6.4,-2.1) {back}; \draw[->, black, dashed] (nnp) -- (wj); \draw[->, black, dashed] (md) -- (ww); \draw[->, black, dashed] (vb) -- (wb); \draw[->, acc, thick] (8.1,0.4) -- (8.9,0.4); \node[anchor=west, text=acc, font=\scriptsize] at (9.0,0.4) {transition}; \draw[->, black, dashed] (8.1,-0.4) -- (8.9,-0.4); \node[anchor=west, text=black, font=\scriptsize] at (9.0,-0.4) {emission}; \end{tikzpicture} $$ 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, $$ P(o_i \mid q_1 \ldots q_T, o_1 \ldots o_T) \;=\; P(o_i \mid q_i). $$ 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: $$ P(t_i \mid t_{i-1}) \;=\; \frac{C(t_{i-1}, t_i)}{C(t_{i-1})}, \qquad P(w_i \mid t_i) \;=\; \frac{C(t_i, w_i)}{C(t_i)}. $$ 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(\textit{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 \textit{will})$. $$ % caption: The two tables of an HMM tagger, illustrated for three states. The A % transition probabilities $a_{ij} = P(t_i \mid t_{i-1})$ connect tag-states; the % B observation likelihoods $b_i(w) = P(w \mid t_i)$ give each state a % distribution over words. The full tagger has one state per tag. \begin{tikzpicture}[>=stealth, font=\footnotesize, state/.style={circle, draw=acc, thick, minimum size=10mm, font=\small}, btab/.style={draw, align=left, font=\scriptsize, inner sep=3pt}] \definecolor{acc}{HTML}{2348F2} \node[state] (md) at (0,1.9) {MD}; \node[state] (vb) at (-1.7,-0.7) {VB}; \node[state] (nn) at (1.7,-0.7) {NN}; \draw[->, acc] (md) to[bend right=16] node[left, font=\scriptsize] {a(MD,VB)} (vb); \draw[->, acc] (vb) to[bend right=16] (md); \draw[->, acc] (md) to[bend left=16] node[right, font=\scriptsize] {a(MD,NN)} (nn); \draw[->, acc] (vb) to[bend left=12] (nn); \draw[->, acc] (md) to[out=120,in=60,looseness=6] (md); % B tables: state emits word with probability (bar avoided; header names the state) \node[btab, anchor=west] at (2.9,1.9) {\texttt{b(MD):}\\ \texttt{will = .31}\\ \texttt{the = .04}\\ \texttt{race = .00}}; \node[btab, anchor=east] at (-3.0,-0.7) {\texttt{b(VB):}\\ \texttt{race = .12}\\ \texttt{back = .00}\\ \texttt{will = .00}}; \node[btab, anchor=west] at (3.0,-1.6) {\texttt{b(NN):}\\ \texttt{bill = .30}\\ \texttt{back = .04}\\ \texttt{race = .00}}; \draw[->, black, dashed] (md) -- (2.85,2.0); \draw[->, black, dashed] (vb) -- (-2.95,-0.7); \draw[->, black, dashed] (nn) -- (2.95,-1.3); \end{tikzpicture} $$ ### HMM tagging as decoding With $A$ and $B$ in hand, tagging is **decoding**: given the observations, find the most probable hidden state sequence.[^jm-decode] For $n$ words the goal is the tag sequence maximizing the posterior, $$ \hat{t}_{1:n} \;=\; \argmax_{t_1 \ldots t_n} P(t_1 \ldots t_n \mid w_1 \ldots w_n). $$ The generative model does not give this posterior directly, so we apply Bayes' rule, drop the constant denominator $P(w_1 \ldots 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: $$ \hat{t}_{1:n} \;=\; \argmax_{t_1 \ldots t_n}\; \prod_{i=1}^{n}\; \underbrace{P(w_i \mid t_i)}_{\text{emission}}\; \underbrace{P(t_i \mid t_{i-1})}_{\text{transition}}. $$ The two factors correspond neatly to the $B$ emission and $A$ transition probabilities. The only remaining problem is the $\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](/natural-language-processing/sequences/crfs-and-neural-taggers). [^jm-seqlab]: **Jurafsky & Martin**, _Speech and Language Processing_ (3rd ed.), Ch. 8 — Sequence Labeling for Parts of Speech and Named Entities: the sequence-labeling task maps an input sequence of tokens to an equally long output sequence of labels, one label per token. [^jm-pos]: **Jurafsky & Martin**, §8.1–§8.2 — English Word Classes and Part-of-Speech Tagging: parts of speech as open and closed classes, and tagging as assigning a POS label to each word in a sequence. [^jm-ptb]: **Jurafsky & Martin**, §8.2 — the 45-tag Penn Treebank tagset (Marcus et al., 1993), used to label many syntactically annotated corpora, distinguishing tense and participles on verbs. [^jm-ambig]: **Jurafsky & Martin**, §8.2 — tag ambiguity in the Brown and WSJ corpora: most word types are unambiguous, but the ambiguous types are common, so a majority of word tokens in running text are ambiguous. [^jm-baseline]: **Jurafsky & Martin**, §8.2 — the most-frequent-class baseline reaches about 92% accuracy on English, against a 97% state-of-the-art and human ceiling; always compare against at least this baseline. [^jm-ner]: **Jurafsky & Martin**, §8.3 — Named Entities and Named Entity Tagging: named entities as things referable by a proper name, the PER/LOC/ORG/GPE types, and evaluation by recall, precision, and $F_1$. [^jm-bio]: **Jurafsky & Martin**, §8.3 — BIO tagging (Ramshaw and Marcus, 1995): B/I/O labels turn span recognition into per-token sequence labeling with $2n{+}1$ tags, with IO and BIOES as variants. [^jm-hmm]: **Jurafsky & Martin**, §8.4 — HMM Part-of-Speech Tagging: Markov chains and the Markov assumption, the hidden Markov model's five components, and its transition and emission probabilities estimated by maximum-likelihood counting. [^jm-decode]: **Jurafsky & Martin**, §8.4.4 — HMM tagging as decoding: Bayes' rule plus the output-independence and bigram assumptions reduce the argmax to a product of emission and transition probabilities.