--- title: "Viterbi Decoding, CRFs, and Neural Taggers" module: Sequences moduleNumber: 4 lessonNumber: 2 order: 402 summary: > The HMM reduced tagging to an argmax over exponentially many tag sequences. This lesson builds the decoder that makes it tractable — the Viterbi dynamic program, worked through a full numeric trace on real WSJ probabilities — then keeps that same decoder while replacing the HMM's rigid tables. The linear-chain conditional random field is a discriminative log-linear model whose global feature functions can inspect any part of the input, which is why CRFs win for NER. Finally it traces the shift to neural taggers (biLSTM-CRF, character-aware NER, ELMo), where hand-built features become learned representations while the Viterbi decoder carries over unchanged. topics: [Sequences] sources: - book: Jurafsky ref: "Ch. 8 — Sequence Labeling; §8.4.5 The Viterbi Algorithm; §8.5 Conditional Random Fields (CRFs)" - book: Jurafsky ref: "§8.7.1 Bidirectionality — neural sequence taggers" --- This builds on [Sequence Labeling: POS and NER](/natural-language-processing/sequences/sequence-labeling), 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.[^jm-viterbi] Like the [minimum-edit-distance](/natural-language-processing/foundations/regex-and-text-normalization) 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: $$ v_t(j) \;=\; \max_{q_1 \ldots q_{t-1}} P(q_1 \ldots q_{t-1},\, o_1 \ldots o_t,\, q_t = j \mid \lambda). $$ 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): $$ v_t(j) \;=\; \max_{i=1}^{N}\; v_{t-1}(i)\; a_{ij}\; b_j(o_t). $$ 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. $$ % caption: The Viterbi trellis for tagging "Janet will back the bill." Each % column is a word, each row a candidate tag; cell $v_t(j)$ holds the best path % score reaching tag $j$ at word $t$. The bold path is the winning tag sequence % NNP MD VB DT NN, recovered by following backpointers from the last column. \begin{tikzpicture}[>=stealth, font=\scriptsize, cell/.style={circle, draw, minimum size=8mm, inner sep=0pt, font=\scriptsize}, on/.style={circle, draw=acc, thick, fill=acc!8, minimum size=8mm, inner sep=0pt, font=\scriptsize}] \definecolor{acc}{HTML}{2348F2} \def\dx{2.0} \def\dy{1.0} % row labels (tags), 5 shown \foreach \r/\lab in {4/NNP, 3/MD, 2/VB, 1/DT, 0/NN} \node[anchor=east, font=\scriptsize] at (-0.5, \r*\dy) {\lab}; % column labels (words) \foreach \c/\w in {0/Janet, 1/will, 2/back, 3/the, 4/bill} \node[anchor=north, font=\scriptsize] at (\c*\dx, -0.7) {\w}; % all cells \foreach \c in {0,...,4} \foreach \r in {0,...,4} \node[cell] (n\c-\r) at (\c*\dx, \r*\dy) {}; % the winning path cells, re-drawn highlighted: NNP(r4) MD(r3) VB(r2) DT(r1) NN(r0) \node[on] (p0) at (0*\dx,4*\dy) {v(J)}; \node[on] (p1) at (1*\dx,3*\dy) {v(w)}; \node[on] (p2) at (2*\dx,2*\dy) {v(b)}; \node[on] (p3) at (3*\dx,1*\dy) {v(t)}; \node[on] (p4) at (4*\dx,0*\dy) {v(b)}; % winning path edges \draw[->, acc, very thick] (p0) -- (p1); \draw[->, acc, very thick] (p1) -- (p2); \draw[->, acc, very thick] (p2) -- (p3); \draw[->, acc, very thick] (p3) -- (p4); % a couple of losing candidate edges into column 1 (muted, thin) \draw[->, black] (n0-2) -- (n1-3); \draw[->, black] (n0-0) -- (n1-3); \node[anchor=west, text=acc, font=\scriptsize] at (4*\dx+0.6, 0*\dy) {best path}; \end{tikzpicture} $$ 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: ```algorithm caption: $\textsc{Viterbi}(O, \lambda)$ — decode the best tag sequence for observations $O = o_1{:}o_T$ under HMM $\lambda = (A, B)$ input: observations $O = o_1 \ldots o_T$, states $1 \ldots N$ create tables $v[N, T]$ and $bp[N, T]$ for each state $s = 1 \ldots N$ do // initialization $v[s, 1] \gets \pi_s \cdot b_s(o_1)$ $bp[s, 1] \gets 0$ for each time step $t = 2 \ldots T$ do // recursion for each state $s = 1 \ldots N$ do $v[s, t] \gets \max_{s'} \; v[s', t{-}1] \cdot a_{s', s} \cdot b_s(o_t)$ $bp[s, t] \gets \argmax_{s'} \; v[s', t{-}1] \cdot a_{s', s} \cdot b_s(o_t)$ $bestscore \gets \max_{s} \; v[s, T]$ // termination $bestlast \gets \argmax_{s} \; v[s, T]$ $path \gets$ states from $bestlast$ following $bp$ back to $t = 1$ return $path$, $bestscore$ ``` 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. > **Definition (Viterbi decoding).** The dynamic program that finds the single > highest-probability state (tag) sequence through an HMM given the observations. > It fills an $N \times T$ trellis by the recurrence $v_t(j) = \max_i v_{t-1}(i)\, > a_{ij}\, b_j(o_t)$, stores backpointers, and traces the best path back from the > final column. Cost: $O(N^2 T)$. ### A full Viterbi trace Run the recurrence with the real WSJ probabilities.[^jm-viterbi] Restrict attention to seven tags. The transition table $A$, with the start state $\langle s \rangle$ as a row, holds $a_{ij} = P(t_j \mid t_i)$: | $P(t_j \mid t_i)$ | NNP | MD | VB | JJ | NN | RB | DT | | --- | --- | --- | --- | --- | --- | --- | --- | | $\langle s \rangle$ | $0.2767$ | $0.0006$ | $0.0031$ | $0.0453$ | $0.0449$ | $0.0510$ | $0.2026$ | | **NNP** | $0.3777$ | $0.0110$ | $0.0009$ | $0.0084$ | $0.0584$ | $0.0090$ | $0.0025$ | | **MD** | $0.0008$ | $0.0002$ | $0.7968$ | $0.0005$ | $0.0008$ | $0.1698$ | $0.0041$ | | **VB** | $0.0322$ | $0.0005$ | $0.0050$ | $0.0837$ | $0.0615$ | $0.0514$ | $0.2231$ | | **DT** | $0.1147$ | $0.0021$ | $0.0002$ | $0.2157$ | $0.4744$ | $0.0102$ | $0.0017$ | 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): | $P(w \mid t_j)$ | Janet | will | back | the | bill | | --- | --- | --- | --- | --- | --- | | **NNP** | $0.000032$ | $0$ | $0$ | $0.000048$ | $0$ | | **MD** | $0$ | $0.308431$ | $0$ | $0$ | $0$ | | **VB** | $0$ | $0.000028$ | $0.000672$ | $0$ | $0.000028$ | | **JJ** | $0$ | $0$ | $0.000340$ | $0$ | $0$ | | **NN** | $0$ | $0.000200$ | $0.000223$ | $0$ | $0.002337$ | | **RB** | $0$ | $0$ | $0.010446$ | $0$ | $0$ | | **DT** | $0$ | $0$ | $0$ | $0.506099$ | $0$ | **Column 1 (Janet).** Initialize $v_1(j) = \pi_j \cdot b_j(\textit{Janet})$, using the $\langle s \rangle$ 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(\textit{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}}(\textit{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}}(\textit{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**. $$ % caption: The filled Viterbi trellis for "Janet will back the bill." Live cells hold % the best score reaching that tag; the bold path NNP MD VB DT NN is the argmax, % recovered by following backpointers from NN in the last column. At "back," the % adverb RB has the highest emission but loses to VB on the MD-to-VB transition. \begin{tikzpicture}[>=stealth, font=\scriptsize, cell/.style={circle, draw, minimum size=8mm, inner sep=0pt, font=\scriptsize}, dead/.style={circle, draw=black, minimum size=8mm, inner sep=0pt, font=\scriptsize}, on/.style={circle, draw=acc, thick, fill=acc!10, minimum size=8mm, inner sep=0pt, font=\scriptsize}] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} \def\dx{2.0} \def\dy{1.0} \foreach \r/\lab in {5/NNP, 4/MD, 3/VB, 2/RB, 1/DT, 0/NN} \node[anchor=east, font=\scriptsize] at (-0.4, \r*\dy) {\lab}; \foreach \c/\w in {0/Janet, 1/will, 2/back, 3/the, 4/bill} \node[anchor=north, font=\scriptsize] at (\c*\dx, -0.65) {\w}; % dead cells (light) \foreach \c in {0,...,4} \foreach \r in {0,...,5} \node[dead] (n\c-\r) at (\c*\dx, \r*\dy) {}; % live path cells: NNP(5) MD(4) VB(3) DT(1) NN(0) \node[on] (p0) at (0*\dx,5*\dy) {}; \node[on] (p1) at (1*\dx,4*\dy) {}; \node[on] (p2) at (2*\dx,3*\dy) {}; \node[on] (p3) at (3*\dx,1*\dy) {}; \node[on] (p4) at (4*\dx,0*\dy) {}; % the RB competitor at back (row 2), non-winning \node[cell, draw=red, text=red] (rbb) at (2*\dx,2*\dy) {RB}; % winning path edges \draw[->, acc, very thick] (p0) -- (p1); \draw[->, acc, very thick] (p1) -- (p2); \draw[->, acc, very thick] (p2) -- (p3); \draw[->, acc, very thick] (p3) -- (p4); % losing edge MD -> RB \draw[->, red, dashed] (p1) -- (rbb); \node[red, anchor=west, font=\scriptsize] at (2*\dx+0.55,2*\dy) {high emit, loses}; \node[anchor=west, text=acc, font=\scriptsize] at (4*\dx+0.55, 0*\dy) {best path}; \end{tikzpicture} $$ 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. $$ % caption: The Viterbi trellis for "Janet will back the bill" filled with the actual % v_t(j) scores (written in e-notation). The bold path NNP MD VB DT NN is the argmax. % At "back" the RB cell (5.3e-11) is numerically larger than the VB cell (1.6e-11), % yet the winning path runs through VB, because reaching DT at the next column favors % the VB-to-DT transition. A locally larger cell need not lie on the best path. \begin{tikzpicture}[>=stealth, font=\scriptsize, cell/.style={draw=black, minimum width=15mm, minimum height=7mm, inner sep=1pt, font=\scriptsize, align=center}, on/.style={draw=acc, thick, fill=acc!10, minimum width=15mm, minimum height=7mm, inner sep=1pt, font=\scriptsize, align=center}, lose/.style={draw=red, thick, minimum width=15mm, minimum height=7mm, inner sep=1pt, font=\scriptsize, align=center, text=red}] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} \def\dx{2.4} \def\dy{1.15} \foreach \r/\lab in {5/NNP, 4/MD, 3/VB, 2/RB, 1/DT, 0/NN} \node[anchor=east, font=\scriptsize] at (-0.95, \r*\dy) {\lab}; \foreach \c/\w in {0/Janet, 1/will, 2/back, 3/the, 4/bill} \node[anchor=south, font=\scriptsize] at (\c*\dx, 5.7*\dy) {\w}; % winning-path cells with real values \node[on] (nnp) at (0*\dx,5*\dy) {8.9e-6}; \node[on] (md) at (1*\dx,4*\dy) {3.0e-8}; \node[on] (vb) at (2*\dx,3*\dy) {1.6e-11}; \node[on] (dt) at (3*\dx,1*\dy) {1.8e-12}; \node[on] (nn) at (4*\dx,0*\dy) {2.0e-15}; % the RB competitor at back: numerically larger, off the path \node[lose] (rb) at (2*\dx,2*\dy) {5.3e-11}; % a couple of dead-but-computed cells for context \node[cell, text=black] (nn2) at (1*\dx,0*\dy) {1.0e-10}; \node[cell, text=black] (vb2) at (1*\dx,3*\dy) {2.2e-13}; % winning path edges \draw[->, acc, very thick] (nnp) -- (md); \draw[->, acc, very thick] (md) -- (vb); \draw[->, acc, very thick] (vb) -- (dt); \draw[->, acc, very thick] (dt) -- (nn); % the tempting but losing MD -> RB edge \draw[->, red, dashed] (md) -- (rb); % the deciding comparison at column 4: RB also reaches toward DT but loses \draw[->, red, dashed] (rb.south) to[out=-80,in=200] (dt.west); \node[anchor=west, text=red, font=\scriptsize] at (2*\dx+0.85, 2*\dy+0.42) {larger cell,}; \node[anchor=west, text=red, font=\scriptsize] at (2*\dx+0.85, 2*\dy+0.02) {of\/f the path}; \node[anchor=west, text=acc, font=\scriptsize] at (4*\dx+0.85, 0*\dy) {best path}; \end{tikzpicture} $$ 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.[^jm-crf] 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](/natural-language-processing/classification/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$: $$ P(Y \mid X) \;=\; \frac{1}{Z(X)}\, \exp\!\left( \sum_{k=1}^{K} w_k\, F_k(X, Y) \right), \qquad Z(X) = \sum_{Y' \in \mathcal{Y}} \exp\!\left( \sum_{k=1}^{K} w_k\, F_k(X, Y') \right). $$ 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. > **Definition (Linear-chain CRF).** A discriminative sequence model that scores an > entire tag sequence $Y$ given the input $X$ as a log-linear combination of global > features $F_k(X,Y) = \sum_i f_k(t_{i-1}, t_i, X, i)$. Each local feature may see > the previous and current tag and _any part of the whole input $X$_, but not tags > further back — and that restriction is what lets Viterbi decode it. 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} = \texttt{B-PER}$ and we are scoring the candidate current tag $t_i = \texttt{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:[^jm-crf] | feature $f_k$ | condition | fires? | | --- | --- | --- | | $f_1$ | $t_{i-1} = \texttt{B-PER} \;\wedge\; t_i = \texttt{I-PER}$ | $1$ | | $f_2$ | $t_i = \texttt{I-PER} \;\wedge\; w_i$ is capitalized | $1$ | | $f_3$ | $t_i = \texttt{I-PER} \;\wedge\; w_{i-1} = \textit{Jane}$ | $1$ | | $f_4$ | $t_i = \texttt{I-PER} \;\wedge\; w_i$ ends in _-eva_ | $1$ | | $f_5$ | $t_i = \texttt{B-ORG} \;\wedge\; w_{i+1} = \textit{Airlines}$ | $0$ | 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. | | HMM | Linear-chain CRF | | --- | --- | --- | | Type | generative, models $P(X, Y)$ | discriminative, models $P(Y \mid X)$ | | Knowledge | tag bigrams + word identity only | arbitrary features over all of $X$ | | Unknown words | weak (unseen emission) | strong (shape, affix, gazetteer features) | | Trains | count-and-divide MLE | gradient descent on log-likelihood | | Decodes with | Viterbi | Viterbi | Decoding a CRF is, once more, Viterbi. To find $\hat{Y} = \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: $$ v_t(j) \;=\; \max_{i=1}^{N}\; \Big[\, v_{t-1}(i) \;+\; \sum_{k=1}^{K} w_k\, f_k(t_i, t_j, X, t) \,\Big], $$ 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).[^biLSTM-crf] 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).[^lample] 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).[^elmo-ner] 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.[^jm-neural] 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](/natural-language-processing/sequences/rnns-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. [^jm-viterbi]: **Jurafsky & Martin**, §8.4.5 — The Viterbi Algorithm: the dynamic-programming decoder for HMMs, the trellis recurrence $v_t(j) = \max_i v_{t-1}(i)\,a_{ij}\,b_j(o_t)$ with backpointers, related to minimum edit distance. [^jm-crf]: **Jurafsky & Martin**, §8.5 — Conditional Random Fields: the linear-chain CRF as a discriminative log-linear sequence model with global feature functions decomposed into local features over the whole input, decoded by Viterbi. [^jm-neural]: **Jurafsky & Martin**, §8.7.1 — Bidirectionality: neural biLSTM sequence models, often with a CRF layer, as the standard modern approach, forward-referenced to the sequence-processing chapter. [^biLSTM-crf]: **Huang, Xu, and Yu (2015)**, _Bidirectional LSTM-CRF Models for Sequence Tagging_, arXiv — a bidirectional LSTM producing per-token representations with a CRF output layer scoring tag transitions, matching feature-engineered CRFs on POS, chunking, and NER. [^lample]: **Lample, Ballesteros, Subramanian, Kawakami, and Dyer (2016)**, _Neural Architectures for Named Entity Recognition_, NAACL — a word-and-character biLSTM with a CRF decoding layer, reporting $90.94$ $F_1$ on CoNLL-2003 English NER without external gazetteers. [^elmo-ner]: **Peters, Neumann, Iyyer, Gardner, Clark, Lee, and Zettlemoyer (2018)**, _Deep Contextualized Word Representations_, NAACL — ELMo, pretrained bidirectional-LSTM language-model representations that, added to a biLSTM-CRF tagger, raised CoNLL-2003 NER to about $92.2$ $F_1$.