Sequence labeling: NER & POS

Text classification assigns one label to a whole document. But a huge class of NLP tasks needs a label for every token: which words are people, places, organizations (named-entity recognition), or which are nouns and verbs (part-of-speech tagging). This is sequence labeling, and what makes it its own problem — not just classification repeated per word — is that the labels depend on each other.

The BIO scheme, and why labels aren’t independent

Entities span multiple tokens (“New York City”), so we tag with the BIO scheme: B-egin, I-nside, O-utside. “Barack Obama visited Paris” becomes B-PER I-PER O B-LOC. Now the key observation: these tags constrain each other. I-PER can only follow B-PER or another I-PER — an I-PER right after O is illegal. A verb rarely follows a verb. So a tagger that labels each token independently will make sequence-inconsistent mistakes; you have to model the transitions between labels, not just each token in isolation.

HMM + Viterbi: decode the best whole sequence

The classical model is the Hidden Markov Model: the true tags form a Markov chain (a transition probability from each tag to the next), and each tag emits the observed word (an emission probability). Tagging a sentence means finding the single most probable tag sequence — which the Viterbi algorithm does efficiently with dynamic programming, weighing emissions against transitions:

tags = ["DET", "NOUN", "VERB"]
trans = {"START": {"DET":0.7,"NOUN":0.2,"VERB":0.1}, "DET": {"DET":0.1,"NOUN":0.8,"VERB":0.1},
         "NOUN": {"DET":0.1,"NOUN":0.3,"VERB":0.6},  "VERB": {"DET":0.5,"NOUN":0.4,"VERB":0.1}}
emit = {"DET": {"the":0.9,"dog":0.0,"runs":0.0}, "NOUN": {"the":0.0,"dog":0.7,"runs":0.2},
        "VERB": {"the":0.0,"dog":0.1,"runs":0.8}}
sent = ["the", "dog", "runs"]

V = [{t: trans["START"][t] * emit[t][sent[0]] for t in tags}]; back = [{}]
for i in range(1, len(sent)):                       # Viterbi: best path to each tag at each step
    back.append({}); row = {}
    for t in tags:
        bp = max(tags, key=lambda p: V[i-1][p] * trans[p][t])
        row[t] = V[i-1][bp] * trans[bp][t] * emit[t][sent[i]]; back[i][t] = bp
    V.append(row)
last = max(tags, key=lambda t: V[-1][t]); path = [last]   # backtrack the best sequence
for i in range(len(sent)-1, 0, -1):
    last = back[i][last]; path.insert(0, last)
print(list(zip(sent, path)))

[('the', 'DET'), ('dog', 'NOUN'), ('runs', 'VERB')]

Viterbi recovers DET NOUN VERB, the only sequence the transitions make likely. Crucially it optimizes the whole path: a locally tempting tag gets rejected if it makes the sequence implausible — exactly the dependency a per-token classifier misses.

CRFs, then neural taggers

HMMs are generative and assume each word depends only on its own tag. The Conditional Random Field (CRF) is the discriminative upgrade: it scores the whole label sequence given the words using arbitrary features (capitalization, suffixes, neighboring words) plus learned transition scores — and it was the SOTA for NER and POS for years. The decoding is still Viterbi; the difference is a richer, trainable scoring function.

In one breath

• Sequence labeling assigns a label to every token — NER (entities) and POS (grammar) — tagged with the BIO scheme (B-egin / I-nside / O-utside) to mark spans.
• Its defining feature: labels depend on each other (I-PER can’t follow O), so you must model transitions, not label tokens independently.
• The classical HMM combines tag transitions + word emissions; Viterbi decodes the single most probable whole sequence (the demo: DET NOUN VERB).
• The CRF is the discriminative successor — arbitrary features + learned transition scores, still Viterbi-decoded — and was long the SOTA.
• Neural taggers kept the structure: BiLSTM-CRF and transformer token classification (often with a CRF head) — encoder changed, “model the label dependencies” stayed.

Quick check

Next

Sequence labeling tags every token; its document-level sibling is text classification. The HMM rests on Markov chains, and the neural encoders are RNNs/LSTMs and transformers.