Viterbi Decoding, CRFs, and Neural Taggers

This builds on Sequence Labeling: POS and NER, which set up part-of-speech and named-entity tagging and built the hidden Markov model. That lesson ended with an obstacle: tagging is an argmax over $N^n$ tag sequences, far too many to enumerate. Here the Viterbi dynamic program makes it tractable; we trace it through real numbers, then swap the HMM's two rigid tables for a discriminative model that conditions on any feature of the whole sentence — and keep Viterbi as the decoder the whole way through, into the neural taggers that learn their features instead of hand-coding them.

Decoding with Viterbi

The decoding algorithm for HMMs is the Viterbi algorithm, a dynamic program.¹ Like the minimum-edit-distance recurrence, it fills a table so that each cell reuses the solutions to smaller subproblems, turning an exponential search into a polynomial fill. The subproblem is the best path to a given state at a given time.

The algorithm builds a trellis (or lattice): a grid with one column per observation $w_t$ and one row per state $q_j$. The cell $v_t(j)$ holds the probability of the single most probable path that ends in state $j$ after emitting the first $t$ words:

The dynamic-programming insight is that a best path to state $j$ at time $t$ must extend some best path to a state $i$ at time $t-1$; nothing earlier can be revisited or improved. So each cell is computed by taking the max over the previous column of (path so far) $\times$ (transition into $j$) $\times$ (emission of the current word):

Three quantities multiply: $v_{t-1}(i)$, the best score reaching state $i$ one step back; $a_{ij}=P(t_j\mid t_i)$, the transition; and $b_j(o_t)=P(w_t\mid t_j)$, the emission of the current word. Alongside the score, each cell stores a backpointer to the state $i$ that achieved the max, so that once the last column is filled we can trace the winning path back to the start.

Written as pseudocode, the recurrence becomes three phases — initialize the first column from the start distribution, recurse column by column filling each cell from the previous one, then read off and backtrace the best final path:

The table is $N\times T$, and filling each cell costs a max over $N$ predecessors, so Viterbi runs in $O(N^{2}T)$ time — polynomial in sentence length, where naive enumeration was exponential. That reduction is the entire reason the model is usable. To tag Janet will back the bill, the trellis has $N$ rows and five columns; most cells are zero (the word Janet can only be NNP), the max in each surviving cell picks the best predecessor, and backtracing from the last column recovers the gold sequence NNP MD VB DT NN.

A full Viterbi trace

Run the recurrence with the real WSJ probabilities.¹ Restrict attention to seven tags. The transition table $A$, with the start state $⟨s⟩$ as a row, holds $a_{ij}=P(t_j\mid t_i)$:

The emission table $B$ holds $b_j(w)=P(w\mid t_j)$ for the five words of Janet will back the bill (only the non-zero cells matter):

Column 1 (Janet). Initialize $v_1(j)={\pi }_j\cdot b_j(\text{Janet})$, using the $⟨s⟩$ row for $\pi$. Only NNP emits Janet with non-zero probability, so only its cell survives: $v_1(\text{NNP})=0.2767\times 0.000032=0.0000089$. Every other tag has emission $0$ and dies here.

Column 2 (will). For each tag $j$, $v_2(j)={\max }_i{v}_1(i)a_{ij}{b}_j(\text{will})$. Since only NNP is alive in column 1, the max collapses to that one predecessor. For MD: $v_2(\text{MD})=0.0000089\times a_{\text{NNP,MD}}\times b_{\text{MD}}(\text{will})=0.0000089\times 0.0110\times 0.308431=0.0000000302$, with backpointer NNP. Jurafsky & Martin's normalized trellis records $v_2(\text{MD})=0.308431$ once the shared $v_1(\text{NNP})$ and transition factor are folded in; the winner in column 2 is MD, because will as a modal is far likelier than will as a noun ($b_{\text{NN}}(\text{will})=0.0002$).

Column 3 (back). back is the ambiguous word: VB $0.000672$, JJ $0.000340$, NN $0.000223$, RB $0.010446$. Even though RB has the largest emission, the transition $P(\text{RB}\mid \text{MD})=0.1698$ against $P(\text{VB}\mid \text{MD})=0.7968$ tips the product toward VB. The best path through column 3 lands on VB, backpointer MD.

Columns 4–5 (the, bill). the forces DT (the only non-zero emitter, $0.506099$), reached from VB by $P(\text{DT}\mid \text{VB})=0.2231$. bill is emitted by NN ($0.002337$) or VB ($0.000028$); NN wins by two orders of magnitude and is reached from DT by $P(\text{NN}\mid \text{DT})=0.4744$. Backtracing from NN in the last column follows the pointers NN $\to$ DT $\to$ VB $\to$ MD $\to$ NNP, recovering the gold sequence NNP MD VB DT NN.

Notice how sparsity did most of the work: three of the five columns had a single non-zero emitter, so the trellis was nearly deterministic and only back required a real competition among tags. This is typical — the ambiguity that makes tagging hard concentrates in a few tokens, and Viterbi resolves each using the transition probabilities of its neighbors.

The numbers expose one subtlety. Filling the cells with the actual $v_t(j)$ values — the same arithmetic worked above, $v_1(\text{NNP})=0.2767\times 0.000032=8.9\text{e-}6$, then $v_2(\text{MD})=8.9\text{e-}6\times 0.0110\times 0.3084=3.0\text{e-}8$ — exposes what the earlier VB wins at back gloss hides. At column three the cell value of RB is actually the largest, $v_3(\text{RB})=v_2(\text{MD})\times 0.1698\times 0.010446=5.3\text{e-}11$, ahead of $v_3(\text{VB})=v_2(\text{MD})\times 0.7968\times 0.000672=1.6\text{e-}11$, because RB's emission of back swamps the transition gap. What decides the tag is not that column but the next one: reaching DT at column four takes the max over predecessors, and $v_3(\text{VB})\times P(\text{DT}\mid \text{VB})=1.6\text{e-}11\times 0.2231$ beats $v_3(\text{RB})\times P(\text{DT}\mid \text{RB})=5.3\text{e-}11\times 0.0479$, so DT's backpointer selects VB, not RB. The globally best path can route through a cell that was not the local winner — exactly the property that makes the full trellis, rather than a greedy left-to-right choice, necessary.

Viterbi is a general decoder, not a property of the HMM. Any model that scores a tag sequence by a product (or sum) of terms depending only on adjacent tags can be decoded by the same trellis. The conditional random field is exactly such a model.

Conditional random fields

The HMM is useful but rigid. Its two tables represent only tag bigrams and word identities, so it performs poorly on unknown words — proper names and acronyms it never saw in training — precisely where features like capitalized, ends in -ed, or preceded by the would help.² The problem is that an HMM is generative: every source of knowledge has to be forced into $P(t_i\mid t_{i-1})$ or $P(w_i\mid t_i)$, and arbitrary features do not fit those tables.

The conditional random field (CRF) is the discriminative answer. It is a log-linear model — a sequence-length version of logistic regression — that computes the posterior $P(Y\mid X)$ over the whole tag sequence $Y=t_1:t_n$ given the whole word sequence $X=w_1:w_n$ directly, without the generative detour through Bayes' rule. The linear-chain CRF is the variant used for language, and its conditioning matches the HMM's.

A CRF assigns a probability to an entire output sequence $Y$ through $K$ global feature functions $F_k(X,Y)$, each weighted by a learned $w_k$:

Each global feature is a sum of local features over the positions of the sequence, $F_k(X,Y)={\sum }_{i=1}^n{f}_k(t_{i-1},t_i,X,i)$. This decomposition carries one constraint and one freedom. A local feature $f_k$ may depend on the current tag $t_i$, the previous tag $t_{i-1}$, the position $i$, and — this is what the HMM could not do — the entire input sequence $X$. A feature can look at the word two places to the right, at whether the current word is capitalized, at its suffix, at whether it appears in a gazetteer of place names. The tag pair $(t_{i-1},t_i)$ is what keeps the chain linear, so Viterbi still works; everything else is free to inspect the whole sentence.

That freedom is why CRFs beat HMMs for NER. Deciding whether L'Occitane begins a PER or an ORG span turns on cues an HMM cannot represent: the word's shape (X'Xxxxxxxx), its capitalization, its prefixes and suffixes, whether a neighbor sits in a gazetteer, the parts of speech of surrounding words. A CRF folds all of these into local features that condition on the full sentence, so the tag of one token can draw on evidence anywhere in the input.

Worked example: local features on one token

For example, consider tagging the word Villanueva at position $i$ in Jane Villanueva of United Airlines, where the previous tag is $t_{i-1}=\text{B-PER}$ and we are scoring the candidate current tag $t_i=\text{I-PER}$. A handful of local features $f_k(t_{i-1},t_i,X,i)$ fire — each is an indicator, $1$ when its condition holds and $0$ otherwise:²

Features $f_1$ through $f_4$ fire; $f_5$ does not (it is about a different tag). The score the CRF assigns this tag transition is ${\sum }_k{w}_k{f}_k=w_1+w_2+w_3+w_4$, the sum of the learned weights on the firing features. Two of these — $f_2$ (shape) and $f_4$ (suffix) — an HMM structurally cannot express, because they condition on the word form rather than on tag bigrams or a single emission. This is the extra evidence that lets a CRF label an unseen proper name correctly, and $f_1$, the tag-pair feature, is the only one Viterbi needs to see as a transition score.

Decoding a CRF is, once more, Viterbi. To find $\hat{Y}={\mathrm{argmax}}_{Y}P(Y\mid X)$ we drop the constant $Z(X)$ and the monotone $\exp$, leaving a sum of weighted features to maximize over tag sequences. The trellis fills by the same recurrence as the HMM, with the product of $a$ and $b$ replaced by the CRF's weighted feature score for the tag transition into the current cell:

Only the per-cell scoring changed; the dynamic program is identical. Training swaps counting for stochastic gradient descent on the log-likelihood of the labelled corpus, with a forward-backward pass supplying the gradient and $L_1$ or $L_2$ regularization, exactly as for logistic regression.

Neural sequence taggers

Jurafsky & Martin forward-reference the neural approach; the public literature traces the progression. Three papers mark the shift from hand-built features to learned representations, all keeping the CRF's Viterbi-decodable structure.

biLSTM-CRF (Huang, Xu, and Yu, 2015).³ The first widely-cited neural sequence tagger replaced the CRF's hand-engineered features with the hidden states of a bidirectional LSTM, then kept a CRF layer on top to score tag-to-tag transitions. The LSTM supplies a context-aware vector for each token; the CRF layer enforces valid label sequences (an I-PER may not follow a B-ORG). On POS, chunking, and NER benchmarks it matched or beat the best feature-engineered CRFs while needing far less task-specific feature design.

Character-aware NER (Lample et al., 2016).⁴ The state-of-the-art NER architecture of its era added a second representation: alongside each word's embedding, a character-level biLSTM reads the word's spelling and produces a vector that captures morphology and shape — capitalization, hyphenation, suffixes — the very cues the CRF had encoded by hand. Concatenating the word and character representations, feeding them through a word-level biLSTM, and decoding with a CRF layer, Lample and colleagues reported $90.94$ $F_1$ on CoNLL-2003 English NER, then the best result without external gazetteers. The character encoder solved the unknown-word problem structurally: any name, however rare, still has letters.

ELMo and contextual features (Peters et al., 2018).⁵ The next jump came from pretraining the representations. ELMo derives each token's vector from a bidirectional LSTM language model trained on a large unlabelled corpus, then feeds those contextual vectors into a task-specific biLSTM-CRF. Adding ELMo raised CoNLL-2003 NER to roughly $92.2$ $F_1$, a large gain from representations learned before any NER labels were seen — the same pretraining idea that the next module's transformer models push further.

What survives: features change, Viterbi stays

Jurafsky & Martin themselves forward-reference this neural direction as the modern default: a biLSTM producing a context-aware vector for each token, usually with a CRF layer on top to score tag-to-tag transitions.⁶ Across the whole progression one thing never changes. HMM to CRF to biLSTM-CRF changes only how a tag sequence is scored — count tables, then weighted features over the whole input, then learned and pretrained vectors — but the decoding is Viterbi in every one, because each model keeps the tag-bigram (linear-chain) structure that makes the trellis exact.

The next lesson, recurrent networks and LSTMs, builds the biLSTM that supplies those learned representations, and shows how the same sequence-labeling task looks once the features are learned rather than written down by hand.