Named entity recognition

1. Intuition

Spans become tags. An entity is a span of tokens with a type: (1, 4, LOC) means tokens 1, 2, and 3 form a location. Classifiers predict one label per input, so we give every token a label:

• B-TYPE: this token begins an entity of TYPE.
• I-TYPE: this token is inside (continues) an entity of TYPE.
• O: this token is outside every entity.

"The New York City mayor visited Initech ." becomes O B-LOC I-LOC I-LOC O O B-ORG O. Two entities next to each other stay separate because the second one starts with a fresh B-.

What a token looks like matters more than what it is. A model that memorizes "Paris is a location" fails on "Nairobi". Features that generalize describe the token's shape (capitalized? all caps? digits?) and its context ("the mayor of ", " joined", "shares of ___").

Labels depend on neighbors. I-LOC only makes sense after B-LOC or I-LOC. A per-token classifier doesn't know that, so it can output O I-LOC. A decoder picks the best whole sequence that obeys the rules. Linear-chain CRFs learn these transition scores; we use hard rules plus the Viterbi algorithm.

Score entities, not tokens. Most tokens are O, and getting O right is easy. If the model finds "New York" but misses "City", 2 of 3 tokens are right, but the entity is wrong: a downstream system gets the wrong place. NER is scored on exact span-and-type matches.

2. Visualization

Synthetic data: 400 training and 200 test sentences built from templates, with disjoint name lists, so every test entity is unseen. Token accuracy (gray) is always far above entity F1 (blue). The gazetteer's 0.52 token accuracy comes from predicting O everywhere: about half the tokens are O.

Try it (predict first, then run the script and check):

1. The gazetteer scores 0 entity F1. Predict its F1 if the test set reused the training names. Change make_corpus("test", ...) to use "train" and rerun.
2. Adding the word itself as a feature lowers entity F1 (0.73 to 0.56 with Viterbi). Predict why before reading section 5.
3. Greedy decoding produces 38 invalid transitions. Predict how many Viterbi produces, and why it must be that number.
4. Add a template like "{PER} , CEO of {ORG} , said ..." to the test set only. Predict which entity type suffers most.

3. The math

Symbols

Sequence score and the BIO constraint

A tag sequence scores

A sentence also may not start with I-X. A linear-chain CRF uses the same score but learns $A$ and the emission weights jointly, normalizing over all $K^n$ sequences: $p(y \mid x) = \exp s(y) / \sum_{y'} \exp s(y')$.

Viterbi

Trying all $K^n$ sequences is impossible ($K = 7$, $n = 20$ gives $8 \times 10^{16}$). Viterbi keeps only the best score for each ending tag:

It stores the winning $j$ for each $(i, k)$, picks $\arg\max_k \delta_n(k)$, and follows the pointers back. Cost: $O(n K^2)$.

Worked example: greedy versus Viterbi on "New York"

Tags O, B-LOC, I-LOC. The classifier's probabilities:

Greedy takes each row's maximum: O, I-LOC. That is invalid: I-LOC continues an entity that never began.

Viterbi compares valid sequences by the product of probabilities (a sum in log space):

• O O: $0.6 \times 0.2 = 0.12$
• O B-LOC: $0.6 \times 0.3 = 0.18$
• B-LOC O: $0.4 \times 0.2 = 0.08$
• B-LOC B-LOC: $0.4 \times 0.3 = 0.12$
• B-LOC I-LOC: $0.4 \times 0.5 = 0.20$
• O I-LOC: forbidden, score $-\infty$.

The best is B-LOC I-LOC at 0.20, which beats O B-LOC at 0.18. Viterbi found "New York" as one location even though O was the more likely tag for "New" on its own.

Worked example: token accuracy versus entity F1

Gold B-LOC I-LOC I-LOC O B-ORG ("New York City ... Initech"); prediction B-LOC I-LOC O O B-ORG.

• Token accuracy: positions 1, 2, 4, 5 match, so $4/5 = 0.80$.
• Gold entities: $\{(0,3,\text{LOC}), (4,5,\text{ORG})\}$. Predicted: $\{(0,2,\text{LOC}), (4,5,\text{ORG})\}$. Exact matches: 1.
• $P = 1/2 = 0.50$, $R = 1/2 = 0.50$, $F_1 = 2 \times 0.5 \times 0.5 / (0.5 + 0.5) = 0.50$.

The truncated location counts as both a false positive (the wrong span was predicted) and a false negative (the right span was missed).

4. Implementation

The full script is code/09-classical-nlp/ner_scratch.py (NumPy plus scikit-learn's logistic regression as the token classifier).

Build it from scratch

Step 1: spans to BIO tags. Training data usually arrives as character or token spans. We write the first token of each span as B- and the rest as I-. The end index is exclusive, like Python slices.

def spans_to_bio(n_tokens, spans):
    labels = ["O"] * n_tokens
    for start, end, typ in spans:                 # end is exclusive
        labels[start] = f"B-{typ}"
        for i in range(start + 1, end):
            labels[i] = f"I-{typ}"
    return labels

Predict: two adjacent organizations, "Globex Initech", with spans (0,1,ORG) and (1,2,ORG). What tags come out, and could you tell them apart with IO tags (no B-)?

Step 2: BIO tags back to spans. Predictions are tags, but users and metrics want spans. A span closes when the next tag is not an I- of the same type. The sentinel "O" closes a span that runs to the end. A stray I-X with no open span is treated as a new span; this is the lenient convention, and strict evaluators reject it instead.

def bio_to_spans(labels):
    spans, cur = [], None
    for i, lab in enumerate(labels + ["O"]):      # sentinel "O" closes a span at the end
        if cur and not (lab.startswith("I-") and lab[2:] == cur[2]):
            spans.append(tuple(cur))
            cur = None
        if lab.startswith("B-") or (lab.startswith("I-") and cur is None):  # lenient: stray I- starts a span
            cur = [i, i + 1, lab[2:]]
        elif cur:
            cur[1] = i + 1
    return spans

Predict: what does bio_to_spans(["B-PER", "I-ORG"]) return?

Step 3: features that generalize. Word shape maps every uppercase letter to X, lowercase to x, and digits to d, so "iPhone" becomes xXxxxx and "USA-2024" becomes XXX-dddd. Context words two to the left and right capture patterns like "the mayor of ___". The lexical switch adds the word itself, which we will see hurts on unseen names.

def word_shape(w):
    return "".join("X" if c.isupper() else "x" if c.islower() else "d" if c.isdigit() else c for c in w)

def token_features(tokens, i, lexical=False):
    w = tokens[i]
    ctx = lambda j: tokens[j].lower() if 0 <= j < len(tokens) else ("<BOS>" if j < 0 else "<EOS>")
    f = {"shape=" + word_shape(w): 1, "is_title": w.istitle(), "is_upper": w.isupper(), "first": i == 0,
         "prev=" + ctx(i - 1): 1, "next=" + ctx(i + 1): 1, "prev2=" + ctx(i - 2): 1, "next2=" + ctx(i + 2): 1,
         "prev_title": i > 0 and tokens[i - 1].istitle()}
    if lexical:
        f["word=" + w.lower()] = 1
        f["suffix3=" + w[-3:].lower()] = 1
    return f

Predict: the first word of every sentence is capitalized. Which feature lets the model tell "Yesterday" (not an entity) from "Grace" (a person) at position 0?

Step 4: Viterbi with BIO constraints. The transition matrix holds 0 for allowed pairs and $-\infty$ for forbidden ones. cand[j, k] is the best score ending in tag j at the previous token plus the move to k. We keep the max over j and remember which j won.

def allowed(prev, cur):
    return not cur.startswith("I-") or (prev != "O" and prev[2:] == cur[2:])

def viterbi(log_emit, tags):
    n, k = log_emit.shape
    trans = np.array([[0.0 if allowed(p, c) else -np.inf for c in tags] for p in tags])   # [k, k]
    start = np.array([-np.inf if t.startswith("I-") else 0.0 for t in tags])
    score = start + log_emit[0]                                   # [k] best score ending in each tag
    back = np.zeros((n, k), dtype=int)
    for i in range(1, n):
        cand = score[:, None] + trans + log_emit[i][None, :]       # [k_prev, k_cur]
        back[i] = cand.argmax(0)
        score = cand.max(0)
    path = [int(score.argmax())]
    for i in range(n - 1, 0, -1):
        path.append(int(back[i, path[-1]]))
    return [tags[j] for j in reversed(path)]

Predict: if you replace $-\infty$ with $-2$ in trans, can Viterbi still output an invalid sequence? When?

Step 5: entity-level metrics. Convert both sequences to sets of (start, end, type) and count exact matches. Precision divides by predicted entities, recall by gold entities.

def entity_prf(gold_seqs, pred_seqs):
    tp = n_pred = n_gold = 0
    for g, p in zip(gold_seqs, pred_seqs):
        gs, ps = set(bio_to_spans(g)), set(bio_to_spans(p))
        tp += len(gs & ps)
        n_pred += len(ps)
        n_gold += len(gs)
    prec, rec = tp / max(n_pred, 1), tp / max(n_gold, 1)
    return prec, rec, 2 * prec * rec / max(prec + rec, 1e-12)

Predict: a model that outputs O for every token. What are its precision, recall, and token accuracy on a test set where 48% of tokens are entities?

The script then trains LogisticRegression on the feature dictionaries (via DictVectorizer) and decodes its predict_proba output greedily and with Viterbi.

Use the library

The classic trained baseline is a linear-chain CRF over the same feature dictionaries. sklearn-crfsuite learns emission and transition weights together:

import sklearn_crfsuite   # pip install sklearn-crfsuite

crf = sklearn_crfsuite.CRF(algorithm="lbfgs", c1=0.1, c2=0.1, max_iterations=100,
                           all_possible_transitions=True)   # learn weights for unseen pairs too (often negative)
crf.fit([[token_features(t, i) for i in range(len(t))] for t, _ in train],
        [labels for _, labels in train])

For production, a pretrained pipeline is usually the starting point:

import spacy                                      # python -m spacy download en_core_web_sm
doc = spacy.load("en_core_web_sm")("Apple sued Google over its iPhone search deal in the US.")
print([(e.text, e.label_) for e in doc.ents])     # spans with OntoNotes labels such as ORG, GPE, PRODUCT

from transformers import pipeline
ner = pipeline("ner", model="dslim/bert-base-NER", aggregation_strategy="simple")  # merges B-/I- word pieces
print(ner("Apple sued Google over its iPhone in the US."))  # entity_group in {PER, ORG, LOC, MISC}

from seqeval.metrics import classification_report  # entity-level P/R/F1 per type
from seqeval.scheme import IOB2
print(classification_report(gold_tags, pred_tags, mode="strict", scheme=IOB2))

What the libraries add: learned transition weights (CRF), subword tokenization with labels aligned to word pieces (transformers), span merging (aggregation_strategy), and per-type reports (seqeval). Small models make type mistakes on things like product names, so always check on your own data.

Run it

uv run code/09-classical-nlp/ner_scratch.py

Key lines of output:

greedy: ['O', 'I-LOC'] (I-LOC after O is invalid)
viterbi: ['B-LOC', 'I-LOC'] score 0.20 vs best valid alternative 0.18
token accuracy 0.80, entity P/R/F1 = 0.50/0.50/0.50

                         model | token acc | entity P | entity R | entity F1 | invalid
    gazetteer (training names) |     0.517 |    0.000 |    0.000 |     0.000 |       0
         word+context, Viterbi |     0.817 |    0.562 |    0.553 |     0.557 |       0
         shape+context, greedy |     0.889 |    0.633 |    0.690 |     0.660 |      38
        shape+context, Viterbi |     0.912 |    0.706 |    0.755 |     0.730 |       0

The first three lines reproduce the worked examples. The table is on synthetic sentences whose names never appear in training.

5. Engineering

The approach ladder.

A sound 2026 workflow: try an LLM prompt with a JSON schema to bootstrap labels, have humans correct a few hundred, measure entity F1 on a held-out set, then decide whether a small fine-tuned encoder meets the latency and cost budget. Regex still wins for structured IDs (emails, phone numbers, account numbers), and many PII pipelines combine regex with a model.

Why the word feature hurt. With word identity available, the classifier puts a lot of weight on "lovelace means PER". On unseen names those weights are useless, and the shape and context features got less weight during training. That is overfitting to the name list. In real data you want word features (they help on frequent entities), but you must evaluate on entities not seen in training, or your score measures memorization.

Subword alignment. Transformers split "Lovelace" into word pieces. Label only the first piece (and mask the rest with -100 in the loss), or copy the label to all pieces; then merge back to words at inference.

Nested and overlapping entities. "Bank of America Stadium" is a facility containing an organization. BIO assigns one tag per token, so it cannot represent both. Use span-based models (classify every candidate span) or one pass per type.

Production concerns. Domain shift is the main failure: a model trained on news misses drug names and contract parties. Re-label a sample from your domain before trusting any number. Track per-type F1, since rare types hide behind a good average. For PII redaction, optimize recall and accept extra false positives.

Common mistakes

• Reporting token accuracy or token-level F1. Report entity-level P/R/F1 with exact span match, per type.
• Testing on sentences that share entity names with training data, which measures memorization.
• Greedy decoding that emits I-X after O, then a lenient span parser that silently "repairs" it.
• Treating LLM output as ground truth: offsets drift, spans get paraphrased. Validate that each extracted string actually occurs in the input.
• Forgetting that subword tokenizers break word-level labels.

6. Knowledge check

Practice exercise. Tags O, B-PER, I-PER. For "Grace Hopper", the classifier gives "Grace": O 0.5, B-PER 0.45, I-PER 0.05; "Hopper": O 0.3, B-PER 0.1, I-PER 0.6. What do greedy decoding and Viterbi output?

Implementation challenge. Add BILOU tags (L- for the last token, U- for a single-token entity) to the script: write spans_to_bilou, update allowed for the new rules (for example, I-X and L-X must follow B-X or I-X), retrain, and compare entity F1 with BIO.

Summary

• BIO tags turn span extraction into per-token classification: B- starts, I- continues, O is outside.
• Shape and context features generalize to unseen names; word identity alone memorizes the training list.
• Per-token classifiers can emit invalid sequences; Viterbi finds the best valid sequence in $O(nK^2)$, and a CRF learns the transition scores.
• Evaluate with entity-level P/R/F1 (exact span and type) on entities unseen in training. Token accuracy is inflated by O.
• Pick the tool by data and budget: regex for IDs, CRF or a small encoder for fast and stable, LLM prompts to bootstrap.

Next: Topic modeling

Related: Word embeddings · Logistic regression · Recurrent networks · BERT and masked language modeling

Parts of this lesson are adapted from AI Engineering from Scratch by Rohit Ghumare (MIT license, notice): Named Entity Recognition.

Interview angle