Named-Entity Recognition

A named entity is a real-world object referred to by a proper name: people, organizations, locations, dates, monetary amounts, and similar categories agreed upon by an annotation scheme (common sets include the four-type CoNLL-2003 scheme — PER, ORG, LOC, MISC — and richer schemes like OntoNotes with 18 types). Named-entity recognition is the task of finding every entity mention in a text, marking its exact token span, and assigning it a type label. The central difficulty is that entities have variable length. If we treated NER as ordinary classification — one label per token drawn from {PER, ORG, LOC, O} — we could not distinguish "New York" as a single two-token entity from "New" and "York" appearing as two separate one-token entities. The fix is the BIO tagging scheme:

• B-TYPE: this token begins an entity of type TYPE.
• I-TYPE: this token continues (is inside) an entity of type TYPE, immediately following a B-TYPE or another I-TYPE of the same type.
• O: this token is outside any entity.

So "Marie Curie won the Nobel Prize in Stockholm" becomes: ``` Marie B-PER Curie I-PER won O the O Nobel B-MISC Prize I-MISC in O Stockholm B-LOC ``` With $K$ entity types, the BIO scheme produces $2K+1$ possible tags: one B-tag and one I-tag per type, plus the single O tag. Every span-detection problem is now an ordinary sequence-labeling problem over this enlarged tag set — precisely the same shape of problem as POS tagging, which means the same inference algorithms apply. (Variants exist — BIOES adds End and Single tags for tighter boundary modeling, and IOB2 vs IOB1 differ in whether B is mandatory at every entity start — but BIO is the canonical, most widely taught scheme.)

From tokens to tag sequences

Given a sentence $w_1, \dots, w_n$, an NER system must produce a tag sequence $t_1, \dots, t_n$ over the BIO tag set. This is scored by a probabilistic sequence model. Two classical families dominate: 1. Hidden Markov Model (HMM) — generative, defines $P(w_1^n, t_1^n) = \prod_i P(t_i \mid t_{i-1}) P(w_i \mid t_i)$. 2. Linear-chain Conditional Random Field (CRF) — discriminative, defines

where $f_k$ are arbitrary feature functions (word identity, capitalization, prefixes/suffixes, gazetteer membership, POS tag, previous tag) and $Z$ is the normalizing partition function. The CRF is preferred in practice because it can use overlapping, non-independent features of the whole observed sentence without violating any conditional-independence assumption — a freedom generative HMMs do not have. Both models factor the sequence score into a sum of local terms that depend only on adjacent tag pairs $(t_{i-1}, t_i)$ and the observation sequence. This local factorization is exactly what makes efficient dynamic programming possible.

Decoding: Viterbi over BIO tags

Given trained weights, the system must find

Because the score decomposes into a sum over adjacent-tag terms, this maximization is solved by The Viterbi Algorithm, exactly as in POS tagging — the only difference is that the tag alphabet is now the BIO set and certain transitions must be forbidden. A crucial detail specific to NER: not every BIO transition is valid. An I-LOC tag cannot legally follow an O tag or a B-PER tag — it can only follow B-LOC or I-LOC (of the same type). Enforcing these hard constraints (by setting their transition score to $-\infty$, or by structurally excluding them from the trellis) prevents the decoder from ever outputting an ill-formed tag sequence such as "O I-LOC," which would be nonsensical (an "inside" continuation with no beginning). ``` Algorithm: BIO-constrained Viterbi decoding for NER Input: sentence w[1..n] tag set T = {O} ∪ {B-c, I-c : c in entity types} transition score function trans(t_prev, t_curr) // -inf if illegal emission/local score function emit(t, w, i) // feature-weighted score at position i Output: highest-scoring tag sequence t[1..n] 1. // δ[i][t] = best score of any tag sequence for w[1..i] ending in tag t // ψ[i][t] = backpointer: the tag at position i-1 that achieves this best score for each tag t in T: δ[1][t] = emit(t, w, 1) + trans(START, t) ψ[1][t] = START 2. for i = 2 to n: for each tag t in T: best_prev, best_score = None, -infinity for each tag t_prev in T: s = δ[i-1][t_prev] + trans(t_prev, t) + emit(t, w, i) if s > best_score: best_score, best_prev = s, t_prev δ[i][t] = best_score ψ[i][t] = best_prev 3. // termination t[n] = argmax_t ( δ[n][t] + trans(t, END) ) 4. // backtrace for i = n-1 down to 1: t[i] = ψ[i+1][t[i+1]] 5. return t[1..n] ``` After decoding, a post-processing step reads the BIO sequence and emits entity spans: scan left to right, open a new span at each B-TYPE, extend it through following I-TYPE tokens of the same type, and close it the moment an O, a new B, or an I of a different type appears.

Training

For a CRF, training maximizes the conditional log-likelihood of the gold tag sequences over the training corpus via gradient-based optimization (e.g., L-BFGS or stochastic gradient descent). The gradient of the log-likelihood with respect to feature weight $\lambda_k$ has the classic form

the difference between observed feature counts and their expectation under the model. This expectation is computed efficiently with the forward-backward algorithm, the same dynamic-programming trellis structure underlying Viterbi, just replacing max with sum.

Time complexity of decoding. With $n$ tokens and $|T|$ tags, the Viterbi recurrence fills an $n \times |T|$ table, and computing each cell requires examining all $|T|$ predecessor tags, giving $O(n \cdot |T|^2)$ time. With BIO's $2K+1$ tags, this is $O(n K^2)$ — quadratic in the number of entity types but linear in sentence length, which is what makes the algorithm practical even for corpora with dozens of entity types. Space is $O(n \cdot |T|)$ for the $\delta$ and $\psi$ tables (or $O(|T|)$ if only the final tag sequence is needed via online recomputation, though the standard implementation keeps the full table for backtracing).

Why Viterbi is correct here. The argument is the same optimal-substructure argument used for POS tagging, transplanted to the BIO alphabet. Define $\delta[i][t]$ as the score of the best tag sequence for $w_1, \dots, w_i$ that ends in tag $t$. Because the total sequence score decomposes as a sum of terms that each depend only on $(t_{i-1}, t_i)$ and the input, any optimal sequence ending in tag $t$ at position $i$ must, when restricted to positions $1, \dots, i-1$, be an optimal sequence ending in some tag $t_{\text{prev}}$ at position $i-1$ — otherwise swapping in a better prefix would strictly improve the whole sequence, contradicting optimality. This is precisely the optimal-substructure property required for dynamic programming, and it justifies the recurrence

Enforcing illegal transitions (I-LOC after O) as $-\infty$ does not break this argument — it merely restricts the search space to well-formed BIO sequences, and the same optimal-substructure reasoning applies within that restricted space. Correctness of the final answer follows by induction on $i$: the base case ($i=1$) is correct by direct computation, and the inductive step is exactly the recurrence above.

Honest tradeoffs.

• HMMs are cheap to train (closed-form counting) but assume tag-conditional independence of features, so they cannot easily use overlapping features like "capitalized AND ends in -son AND previous word is 'Mr.'"
• CRFs handle rich, overlapping features and are almost always more accurate, but training requires iterative optimization with repeated forward-backward passes, costing $O(n K^2)$ per sentence per gradient step — far more expensive than HMM counting.
• Enforcing BIO legality constraints is essentially free (it only shrinks the transition matrix), but it does not fix genuine model errors — a strong classifier score for a wrong boundary will still be chosen if it is the best legal option.
• Neither HMM nor CRF captures unbounded-length dependencies (e.g., an entity type depending on a noun ten tokens away); this is the classical model's central limitation, later addressed by neural sequence models (BiLSTM-CRF, transformer-based taggers) that keep the same BIO-and-Viterbi decoding backbone but replace hand-built features with learned representations.

Sentence: "Yuri Gagarin visited Paris", true entities: PER = "Yuri Gagarin", LOC = "Paris". Suppose a trained (simplified, illustrative) CRF assigns the following local scores (emission + best incoming transition already folded in, rounded for readability) at each position, restricted to legal tags only:

Running the Viterbi recurrence:

• $\delta[1][\text{B-PER}] = 4.5$ dominates $\delta[1][O]=1.0$ and $\delta[1][\text{B-LOC}]=2.0$.
• $\delta[2][\text{I-PER}] = \delta[1][\text{B-PER}] + \text{trans}(\text{B-PER}\to\text{I-PER}) + \text{emit} = 6.0$, the best option at position 2 (I-PER is only reachable from B-PER or I-PER, and B-PER was the strong choice at position 1, so this path is favored over starting fresh with B-PER at position 2).
• $\delta[3][O] = \delta[2][\text{I-PER}] + \text{trans}(\text{I-PER}\to O) + \text{emit} = 11.0$, clearly best since "visited" is not an entity token and O is reachable from any tag.
• $\delta[4][\text{B-LOC}] = \delta[3][O] + \text{trans}(O \to \text{B-LOC}) + \text{emit} = 15.0$, beating staying in O (which would give roughly $11.5$).

Backtracing from the highest final score gives the path:

which decodes to PER = "Yuri Gagarin", LOC = "Paris" — matching the gold entities exactly. Notice that even though "B-PER" at position 1 was chosen for local reasons, the global Viterbi search is what confirms it remains optimal once the strong I-PER continuation score at position 2 is taken into account; a greedy left-to-right tagger without the backward look implicit in dynamic programming could make the same choice here, but in general only the full Viterbi search guarantees the globally best sequence.

NER as a distinct shared task crystallized during the Message Understanding Conferences (MUC) in the 1990s, and the CRF formalism that dominates classical NER traces back to foundational work in statistical sequence modeling and probabilistic graphical models.

NER is a load-bearing component wherever unstructured text must be converted into structured facts. Search engines use it to detect entities in queries and documents for knowledge-panel construction and entity linking. Financial and legal technology firms use NER to extract company names, monetary amounts, and dates from filings and contracts for compliance monitoring. Clinical NLP pipelines rely on NER (often domain-tuned, e.g., i2b2 or BioNER) to pull medication names, dosages, and diagnoses from unstructured clinical notes. Chatbots and virtual assistants use lightweight NER modules to fill slots (dates, locations, product names) for downstream task completion. Downstream, NER output routinely feeds relation extraction, knowledge-graph population, and coreference resolution — and structurally, the same span-labeling-via-tagging idea recurs in shallow parsing and foreshadows the richer structural prediction problems tackled in Dependency Parsing, where entities and their syntactic relations are jointly modeled.

Ask the tutor: How would you extend BIO-based NER to handle entities that are nested inside one another?