Sequence Labeling: From HMMs to Linear-Chain CRFs

Overview & Motivation

An information-extraction system reads “Solenne Power guided to 4 percent growth in the first quarter” and has to mark Solenne Power as an organization, 4 percent as a percentage, and the first quarter as a date. Each of those is a span of tokens, and the standard trick turns spans into one tag per token. With BIO tags, a token is O (outside every entity), B-type (it begins an entity), or I-type (it continues one). The sentence above becomes

solenne/B-ORG power/I-ORG guided/O to/O percent/B-PERCENT growth/O in/O the/B-DATE first/I-DATE quarter/I-DATE.

The B is not decoration: “Boston, Massachusetts” tokenizes to two adjacent places, B-GPE B-GPE, and without it the two spans would merge.

A tagging of a sentence with $T$ tokens and $K$ tags is a path through a trellis: $K$ rows of states, $T$ columns of positions, one state chosen per column. There are $K^T$ paths, so every method on this page is a way to score paths and then find good ones without enumerating them. We take that in order:

The HMM tagger scores a path by how likely it is to have generated the words, and fitting it is counting.
One recursion, two semirings. Sums over paths and the best path come from the same pass.
The linear-chain CRF scores a path given the words, and its likelihood is concave.
A generative–discriminative pair. With word-identity features the HMM and the CRF define exactly the same conditional distributions.
Decoding risk. The best path and the best tags are different answers to different losses.
Local normalization. A chain of classifiers (the MEMM) cannot let later words change earlier tags.
The structured perceptron learns the scores directly, with a mistake bound.

Then we measure all of it where the Bayes tagger is known exactly, and on the finance corpus.

The HMM tagger

We write $x_{1:T}$ for the words and $z_{1:T}$ for the tags.

Definition 1 (Sequence labeling with BIO tags).

A tagger maps a sentence $x_{1:T}$ to a tag sequence $z_{1:T} \in \mathcal Y^T$ . For entity types $E$ , the BIO tag set is $\mathcal Y = \{\mathrm O\} \cup \{\mathrm{B}\text{-}e, \mathrm{I}\text{-}e : e \in E\}$ . An entity span opens at a B- $e$ tag, or at an I- $e$ tag that does not continue a span of type $e$ , and it runs while I- $e$ tags follow.

The hidden Markov model of formalStatistics’ hidden-markov-models (its Definition 3) becomes a tagger once the hidden states are the tags. We add one ingredient, an end state, so that the model is a distribution over sentences of every length.

Definition 2 (The HMM tagger).

An HMM tagger has a start distribution $\nu$ , transitions $a_{jk}$ and stop probabilities $a_{j,\mathrm{stop}}$ with $\sum_k a_{jk} + a_{j,\mathrm{stop}} = 1$ for every tag $j$ , and emissions $b_k(w)$ . It assigns

p(x_{1:T}, z_{1:T}) = \nu_{z_1} \prod_{t=2}^{T} a_{z_{t-1} z_t} \prod_{t=1}^{T} b_{z_t}(x_t)\; a_{z_T,\mathrm{stop}}.

Read the product from left to right. The tags form a bigram language model, the n-gram topic’s model over tags instead of words, and each word is drawn from its tag alone, as naive Bayes draws a document’s words from its class. Supervised training is then what those topics already do.

Proposition 1 (The HMM tagger is counting).

Given tagged sentences, the maximum-likelihood $\hat\nu$ , $\hat a$ , and $\hat b$ are normalized counts: $\hat a_{jk}$ and $\hat a_{j,\mathrm{stop}}$ divide the counts of $j \to k$ and of $j$ ending a sentence by the number of times $j$ is followed by anything, and $\hat b_k(w)$ divides the count of $w$ tagged $k$ by the count of $k$ . Adding $\alpha$ to every count gives the posterior mean under independent symmetric Dirichlet( $\alpha$ ) priors on the rows. With the end state and every stop probability positive (add- $\alpha$ with $\alpha \gt 0$ guarantees it), $\sum_{T \ge 1} \nu A^{T-1} e = \nu(I - A)^{-1} e = 1$ , where $A = (a_{jk})$ and $e = (a_{j,\mathrm{stop}})_j$ , so the model is a distribution over sentences of every length.

Proof.

Take logs. The log-likelihood is a sum of separate terms, one per row: $\sum_k c_{jk}\log a_{jk} + c_{j,\mathrm{stop}} \log a_{j,\mathrm{stop}}$ for each tag $j$ , one such sum for $\nu$ , and $\sum_w c_{kw} \log b_k(w)$ for each emission row. Each is a multinomial log-likelihood over its own probability vector, maximized by the frequencies: by Gibbs’ inequality, $\sum_i c_i \log q_i \le \sum_i c_i \log (c_i / \sum_l c_l)$ for every probability vector $q$ . The Dirichlet statement is conjugacy (formalStatistics multivariate-distributions, Theorem 6): the posterior of a row is Dirichlet( $\alpha + c$ ), with mean $(\alpha + c_i)/\sum_l(\alpha + c_l)$ . For the last claim, every row of $A$ sums to $1 - a_{j,\mathrm{stop}}$ , so whenever every stop probability is positive the spectral radius of $A$ is below one, the series $\sum_T A^{T-1}$ converges to $(I - A)^{-1}$ , and $(I - A)\mathbf 1 = e$ gives $(I-A)^{-1}e = \mathbf 1$ and $\nu \mathbf 1 = 1$ .

∎

One recursion, two semirings

Both training targets on this page, and both ways of decoding, are sums or maxima over the $K^T$ paths. We write every model as a chain of log-potentials. A path scores

\operatorname{score}(z_{1:T}) = \sum_{t=1}^{T} U_t(z_t) + \sum_{t=1}^{T-1} P_t(z_t, z_{t+1}),

with unary terms $U_t$ and pairwise terms $P_t$ , and the chain’s distribution is $p(z) = e^{\operatorname{score}(z)}/Z$ with $Z = \sum_z e^{\operatorname{score}(z)}$ . For the HMM, $U_t(k) = \log b_k(x_t)$ (plus $\log \nu_k$ at $t = 1$ and $\log a_{k,\mathrm{stop}}$ at $t = T$ ) and $P_t(j, k) = \log a_{jk}$ , so $Z = p(x_{1:T})$ and $p(z)$ is the posterior of the tags.

Now notice that a sum over paths and a maximum over paths have the same structure. Multiplication distributes over addition, $a(b + c) = ab + ac$ , and nonnegative multiplication distributes over maximum, $a\max(b, c) = \max(ab, ac)$ . A commutative semiring is a set with two operations, $\oplus$ and $\otimes$ , each associative and commutative, with $\otimes$ distributing over $\oplus$ . The sum-product semiring $(+, \times)$ and the max-product semiring $(\max, \times)$ on the nonnegative reals are the two we need. Write $\psi_t(k) = e^{U_t(k)}$ and $\psi_{t,t+1}(j, k) = e^{P_t(j, k)}$ .

Theorem 1 (The chain distributive law).

In any commutative semiring, define $\alpha_1(k) = \psi_1(k)$ and, for $t \ge 2$ ,

\alpha_t(k) = \psi_t(k) \otimes \bigoplus_{j} \alpha_{t-1}(j) \otimes \psi_{t-1,t}(j, k),

and symmetrically $\beta_T(j) = \mathbf 1$ and $\beta_t(j) = \bigoplus_k \psi_{t,t+1}(j, k) \otimes \psi_{t+1}(k) \otimes \beta_{t+1}(k)$ . Write $\Psi(z) = \bigotimes_t \psi_t(z_t) \otimes \bigotimes_t \psi_{t,t+1}(z_t, z_{t+1})$ . Then:

(a) $\bigoplus_k \alpha_T(k) = \bigoplus_{z} \Psi(z)$ .

(b) $\alpha_t(k) \otimes \beta_t(k) = \bigoplus_{z : z_t = k} \Psi(z)$ , the aggregate of every path through $(t, k)$ .

(c) $\alpha_t(j) \otimes \psi_{t,t+1}(j, k) \otimes \psi_{t+1}(k) \otimes \beta_{t+1}(k) = \bigoplus_{z : z_t = j,\, z_{t+1} = k} \Psi(z)$ .

Each pass costs $O(TK^2)$ operations. In $(+, \times)$ , (a) is $Z$ , and dividing (b) and (c) by $Z$ gives the node marginals $\gamma_t(k) = p(z_t = k)$ and the edge marginals. In $(\max, \times)$ , (a) is the score of the best path (as a potential), and (b) divided by $Z$ is the max-marginal $\mu_t(k) = \max_{z: z_t = k} p(z)$ .

Proof.

(a) We show by induction on $t$ that $\alpha_t(k) = \bigoplus_{z_{1:t-1}} \Psi_{1:t}(z_{1:t-1}, k)$ , the aggregate over prefixes ending in $k$ of the potentials up to $t$ . At $t = 1$ there is nothing to aggregate. For the step, split the prefix into $z_{1:t-2}$ and $z_{t-1} = j$ . The factor $\psi_{t-1,t}(j, k) \otimes \psi_t(k)$ does not involve $z_{1:t-2}$ , so by distributivity it comes out of the aggregate over $z_{1:t-2}$ , which leaves $\alpha_{t-1}(j)$ ; aggregating over $j$ gives the recursion. At $t = T$ , aggregate over $k$ too.

(b) The same induction run from the right shows $\beta_t(k)$ aggregates the potentials after $t$ over suffixes that follow $k$ . A path through $(t, k)$ is a prefix ending in $k$ and a suffix following $k$ , chosen independently, and its potential is the product of the two parts. Distributivity turns the aggregate of products over independent choices into the product of the two aggregates.

(c) is (b) with the path pinned at two adjacent positions: prefix ending in $j$ , the edge, and suffix following $k$ . Each step of each pass aggregates $K$ terms for each of $K$ states, so $O(K^2)$ per position.

∎

One proof covers both semirings, and formalStatistics’ forward recursion (its Theorem 5), forward–backward smoothing (Theorem 7), and Viterbi decoding (Theorem 8) are the HMM’s potentials run through it. Viterbi’s back-pointers record which $j$ attained each maximum, so the best path itself, not only its score, comes out of the max pass. In code everything runs in log space, where $\otimes$ is addition and $\oplus$ is a log-sum-exp or a maximum. The harness checks all three parts in $(+, \times)$ , and (a) and the max-marginals of (b) in $(\max, \times)$ , against brute-force enumeration of every path on random chains, some with forbidden tags and transitions, and pins the sum-product pass on Topic 12’s HMM against that topic’s forward–backward to $10^{-10}$ .

The Trellis tab draws one sequence from that HMM with its emissions blended toward uniform noise (the well-specified world described below), eight states over $24$ positions. Toggle the semiring. In $(+, \times)$ each cell shows its marginal $\gamma_t(k)$ ; in $(\max, \times)$ it shows the max-marginal relative to the best path’s probability, which is exactly $1$ along the Viterbi path. At position $9$ (the lab’s $t = 8$ , counting from zero) the two views disagree: the marginal favors state $5$ ( $0.505$ ), while the best path through state $0$ beats the best path through state $5$ ( $1$ against $0.614$ ).

One recursion, two semirings: marginals or max-marginals on the trellis

semiring

posterior-marginal pathViterbi pathgold state

positiont = 8

s0 0.194s1 0.039s2 0.032s3 0.145s4 0.033s5 0.505s6 0.017s7 0.034

Viterbi, tags right

17 / 24

posterior decoding, tags right

19 / 24

expected tags right (Viterbi / posterior)

16.384 / 16.928

probability of the best path

0.000112

Each cell is the marginal γₜ(k), the probability that the tag at t is k. Posterior decoding takes each column's darkest cell (Theorem 4(b)). At t = 8 the two semirings disagree: the marginal favors s5, the best path runs through s0.

The linear-chain CRF

The HMM spends its parameters explaining the words, which a tagger is given. The conditional random field of Lafferty, McCallum, and Pereira (2001) models only the tags given the words.

Definition 3 (The linear-chain CRF).

Fix a feature map $f(z_{t-1}, z_t, x, t) \in \mathbb R^d$ and let $F(x, z) = \sum_t f(z_{t-1}, z_t, x, t)$ , with $z_0$ a start symbol (and an end feature at $t = T$ ). The linear-chain CRF with weights $\theta \in \mathbb R^d$ is

p_\theta(z \mid x) = \frac{\exp\big(\theta \cdot F(x, z)\big)}{Z_\theta(x)}, \qquad Z_\theta(x) = \sum_{z'} \exp\big(\theta \cdot F(x, z')\big).

A feature may look at the whole sentence: the current word, its suffix, the words two to the left and two to the right. It can depend on at most two adjacent tags, which is what keeps the model a chain. For fixed $x$ the score $\theta \cdot F(x, z)$ is a chain score, so Theorem 1 computes $Z_\theta(x)$ and every marginal.

Theorem 2 (The CRF likelihood is concave).

For training pairs $(x_i, z_i)_{i \le n}$ , let $\ell(\theta) = \frac1n \sum_i \log p_\theta(z_i \mid x_i)$ . Then

\nabla \ell(\theta) = \frac1n \sum_i \Big(F(x_i, z_i) - \mathbb E_\theta\big[F(x_i, Z) \mid x_i\big]\Big), \qquad \nabla^2 \ell(\theta) = -\frac1n \sum_i \operatorname{Cov}_\theta\big[F(x_i, Z) \mid x_i\big] \preceq 0.

So $\ell$ is concave, and for every $\lambda \gt 0$ the penalized objective $\ell(\theta) - \frac\lambda2 \|\theta\|^2$ is strictly concave, with exactly one maximizer if it has one. The expectation decomposes over Theorem 1’s node and edge marginals.

Proof.

$\log p_\theta(z_i \mid x_i) = \theta \cdot F(x_i, z_i) - \log Z_\theta(x_i)$ . Differentiating $\log Z_\theta(x) = \log \sum_z e^{\theta\cdot F(x, z)}$ gives $\sum_z p_\theta(z \mid x) F(x, z)$ , the conditional mean of $F$ . Differentiating that mean once more gives $\sum_z p_\theta(z \mid x) F F^\top - \big(\sum_z p_\theta F\big)\big(\sum_z p_\theta F\big)^\top$ , the conditional covariance. This is the multivariate, conditional form of formalStatistics exponential-families, Theorem 1. A covariance matrix is positive semidefinite, so the Hessian of $\ell$ is negative semidefinite and $\ell$ is concave by the second-order condition (formalML convex-analysis, Theorem 3). Subtracting $\frac\lambda2\|\theta\|^2$ subtracts $\lambda I$ from the Hessian, which makes it negative definite, and a strictly concave function has at most one maximizer. Finally, $F$ is a sum of terms each involving at most $z_{t-1}$ and $z_t$ , so its mean is a sum of expectations under the edge marginals $p_\theta(z_{t-1}, z_t \mid x)$ .

∎

At the optimum without a penalty, the gradient condition says the model’s expected feature counts equal the observed ones: the moment-matching condition of logistic regression in the linear text classifiers topic, now with expectations taken over paths. We fit by trust-region Newton’s method with exact Hessian-vector products, which we obtain by the complex step, $\nabla^2\ell\, v = \operatorname{Im} \nabla \ell(\theta + ihv)/h$ , through a log-sum-exp that shifts by the real part’s maximum. On the experiment grids we use L-BFGS stopped at gradient $10^{-6}$ , which lands within $10^{-4}$ of the Newton solution with identical decodes, a gap the harness checks at one configuration ( $n = 100$ in the next-state world).

A generative–discriminative pair

The HMM and the CRF look like different models. With the simplest features they are not.

Theorem 3 (HMMs and indicator CRFs give the same conditionals).

Call a CRF an indicator CRF if its features are indicators of each transition $j \to k$ , each tag–word pair $(k, w)$ , each start tag, and each end tag, with weights $\theta_{jk}$ , $\mu_{kw}$ , $s_k$ , and $\eta_k$ . Over a finite vocabulary, the set of conditionals $p(z \mid x)$ of HMM taggers (Definition 2) with positive parameters equals the set of conditionals of indicator CRFs. (A zero probability would need the weight $-\infty$ ; every real-weighted CRF gives every path positive probability.)

(a) An HMM’s conditional is the indicator CRF with $\theta_{jk} = \log a_{jk}$ , $\mu_{kw} = \log b_k(w)$ , $s_k = \log \nu_k$ , $\eta_k = \log a_{k,\mathrm{stop}}$ .

(b) Conversely, given any real weights, let $S_k = \sum_w e^{\mu_{kw}}$ and $M_{jk} = e^{\theta_{jk}} S_k$ , pick any $c$ larger than the spectral radius $\rho(M)$ , and let $h = (cI - M)^{-1} e^{\eta}$ , where $e^{\eta}$ is the vector of the $e^{\eta_j}$ . Then $h \gt 0$ , and the HMM

b_k(w) = \frac{e^{\mu_{kw}}}{S_k}, \qquad a_{jk} = \frac{M_{jk}\, h_k}{c\, h_j}, \qquad a_{j,\mathrm{stop}} = \frac{e^{\eta_j}}{c\, h_j}, \qquad \nu_k \propto e^{s_k} S_k h_k

has the same conditional as the CRF, for every sentence of every length.

Proof.

(a) The HMM’s log-joint is $\log\nu_{z_1} + \sum_t \log a_{z_{t-1}z_t} + \sum_t \log b_{z_t}(x_t) + \log a_{z_T,\mathrm{stop}}$ , which is the indicator CRF’s score with those weights. Dividing the joint by $p(x) = \sum_z p(x, z)$ gives the CRF’s normalization.

(b) $M$ has positive entries, so for $c \gt \rho(M)$ the Neumann series $(cI - M)^{-1} = \sum_{m \ge 0} M^m / c^{m+1}$ converges and has positive entries, and $h$ is positive. Each emission row sums to one by the choice of $S_k$ . For the transitions, the $j$ -th row of $(cI - M)h = e^{\eta}$ reads $c\,h_j = \sum_k M_{jk} h_k + e^{\eta_j}$ ; dividing by $c\,h_j$ gives $\sum_k a_{jk} + a_{j,\mathrm{stop}} = 1$ . Now multiply the HMM’s factors along a path. The factors of $h$ telescope:

\nu_{z_1} \prod_{t \ge 2} a_{z_{t-1}z_t} \, a_{z_T,\mathrm{stop}} \prod_t b_{z_t}(x_t) = \frac{e^{s_{z_1}} S_{z_1} h_{z_1}}{N} \cdot \prod_{t \ge 2} \frac{e^{\theta_{z_{t-1}z_t}} S_{z_t} h_{z_t}}{c\, h_{z_{t-1}}} \cdot \frac{e^{\eta_{z_T}}}{c\, h_{z_T}} \cdot \prod_t \frac{e^{\mu_{z_t x_t}}}{S_{z_t}},

with $N = \sum_k e^{s_k} S_k h_k$ . Each $h_{z_t}$ in a numerator cancels the denominator of the next factor, the last against $a_{z_T,\mathrm{stop}}$ ; each $S_{z_t}$ cancels its emission’s denominator. What remains is $e^{\operatorname{score}(z)}/(N c^{T})$ , where $\operatorname{score}$ is the CRF’s. The constant depends on $T$ but not on $z$ , so conditioning on $x$ removes it, and $p(z \mid x)$ is the CRF’s.

∎

Sutton and McCallum (2012, §2.3) prove direction (a) and call the converse “more complicated.” Smith and Johnson (2007, Corollary 2) prove the equivalence for features that pair a transition with the word it emits, by renormalizing weighted grammars; the construction above is the direct proof for our features. The harness builds the HMM of (b) for random weights, checks that it is a valid HMM, and checks its conditional against the CRF’s on every path to $10^{-12}$ .

Corollary 1 (Same family, two estimators).

On indicator features, fitting an HMM by joint maximum likelihood and fitting a CRF by conditional maximum likelihood search the same set of conditionals. They differ in the criterion: the CRF minimizes the conditional log-loss of the tags on the training data, the HMM the joint log-loss of words and tags. As $n \to \infty$ , the CRF’s conditional log-loss converges to the smallest the family allows, so it is at most the HMM’s, with equality when the data come from an HMM.

This is the linear text classifiers topic’s naive Bayes and logistic regression story, now for sequences; formalML’s naive-bayes (Section 7) has the classifier version of Ng and Jordan’s comparison. The geometry is one set of conditionals and two estimators landing at different points of it. Where the HMM is right, both land at the truth, and the HMM, whose estimates are counts, gets there faster. Where the HMM is wrong, the CRF lands closer in the metric it optimizes, and a CRF with richer features leaves the family altogether.

The harness measures both regimes in worlds where the Bayes tagger is exact, built on Topic 12’s HMM: eight states in two regimes, $24$ tokens per sequence, emissions blended with uniform noise. In the well-specified world the data come from that HMM. In the next-state world each word is drawn, with probability $0.5$ , from the emission row of the next state, so an HMM is wrong, and a CRF that sees the previous word can capture much of the dependence; the exact conditional also couples the two tags with the word between them, which no per-tag feature does. The true model’s conditional is still a chain, with each word’s emission folded into the edge it straddles, so Theorem 1 gives the Bayes tagger exactly. The CRFs are fit at $\lambda = 1/n$ , which on the mean objective is MAP estimation under a standard normal prior on $\theta$ ; the HMM’s smoothing $\alpha$ is tuned on validation data.

world, n	HMM	CRF, words	CRF, ±1 word	Bayes
well-specified, 10	$0.738$	$0.725$	$0.708$	$0.782$
well-specified, 1000	$0.776$	$0.776$	$0.773$	$0.782$
next-state, 10	$0.486$	$0.479$	$0.496$	$0.620$
next-state, 1000	$0.540$	$0.534$	$0.591$	$0.620$

The table gives test token accuracy; the CRF on words alone is the indicator CRF, the conditional family of HMMs with an end state (the fitted HMM, on sequences of one length, has none). On this training draw, in the well-specified world the HMM leads at $n = 10$ and the two tie at $n = 1000$ , in accuracy and in conditional log-loss ( $0.583$ nats per token each, against the Bayes tagger’s $0.580$ ). In the next-state world the window CRF leads at every $n$ . The indicator CRF trails the HMM in accuracy there, $0.534$ against $0.540$ at $n = 1000$ , but beats it in conditional log-loss, $1.036$ against $1.040$ nats: Corollary 1 is a statement about the criterion each estimator optimizes, and accuracy is not that criterion. The HMM’s $\alpha$ is chosen from $\{1, 0.1, 0.01\}$ , and it picks the top edge, $1$ , at every $n$ in both worlds. Past the edge, validation picks $3$ at $n = 100$ and $300$ and $10$ at $n = 1000$ in the next-state world; then the HMM’s log-loss falls below the indicator CRF’s at $n = 300$ , so the CRF’s log-loss win holds from $n = 1000$ on ( $1.036$ against $1.039$ ). Every accuracy ordering is unchanged. The Learning curves tab plots every $n$ , in accuracy or log-loss.

Decoding risk

The trellis offers two answers: the single best path, and the best tag at each position. They answer different questions.

Theorem 4 (What each decoder minimizes).

Let $p(z \mid x)$ be a distribution over tag sequences with node marginals $\gamma_t$ .

(a) The Viterbi path $z^\ast = \arg\max_z p(z \mid x)$ minimizes the expected sequence loss $\mathbb E[\mathbf 1\{\hat z \ne z\}]$ .

(b) The posterior-marginal (or minimum-Bayes-risk) decoding $\hat z_t = \arg\max_k \gamma_t(k)$ minimizes the expected Hamming loss $\mathbb E\big[\sum_t \mathbf 1\{\hat z_t \ne z_t\}\big]$ , the expected number of wrong tags.

Proof.

(a) The expected sequence loss of $\hat z$ is $1 - p(\hat z \mid x)$ , smallest when $p(\hat z \mid x)$ is largest. (b) By linearity of expectation the expected Hamming loss is $\sum_t \big(1 - \gamma_t(\hat z_t)\big)$ , a sum of terms each depending on one $\hat z_t$ , so it is minimized position by position.

∎

Token accuracy is one minus the Hamming loss divided by $T$ , so the Bayes tagger for token accuracy is posterior-marginal decoding, not Viterbi. In the well-specified world, the true model decoded by posterior marginals tags $0.782$ of test tokens correctly and decoded by Viterbi $0.776$ . On the trellis sequence, Viterbi gets $17$ of $24$ tags right and posterior decoding $19$ ; their expected numbers of correct tags are $16.384$ and $16.928$ . formalStatistics shows that the posterior-marginal path can even be impossible, with a zero-probability transition. Theorem 4 says when that is still the right answer: when what we count is tags, not sentences. Every learned tagger on this page is nevertheless decoded by Viterbi, as is standard, except the posterior-decoded MEMMs of the next section’s table; the Bayes reference is reported both ways.

Local normalization and label bias

Before the CRF there was a cheaper discriminative tagger: train a classifier for each tag given the previous tag and the words, and chain the classifiers.

Definition 4 (The MEMM).

A maximum-entropy Markov model (McCallum, Freitag, and Pereira 2000) is $p(z \mid x) = \prod_{t} p(z_t \mid z_{t-1}, x)$ , each factor a softmax logistic regression on features of $x$ . It has lookahead $w$ if the factor at $t$ depends on $x$ only through $x_{1:t+w}$ .

Each factor is trained as an ordinary classifier on the gold previous tag, so an MEMM needs no forward–backward pass to train. It pays for that in what its marginals can see.

Proposition 2 (An MEMM's past ignores its future).

For an MEMM with lookahead $w$ and every $t$ , $p(z_{1:t} \mid x) = p(z_{1:t} \mid x_{1:t+w})$ : the marginal of the first $t$ tags depends on no word after position $t + w$ .

Proof.

$p(z_{1:t} \mid x) = \sum_{z_{t+1:T}} \prod_{s \le T} p(z_s \mid z_{s-1}, x)$ . Sum out $z_T$ first: only the last factor involves it, and it is a distribution over $z_T$ , so it sums to one. Then sum out $z_{T-1}$ , and so on down to $z_{t+1}$ . What remains is $\prod_{s \le t} p(z_s \mid z_{s-1}, x)$ , and by the lookahead assumption each of those factors depends on $x$ only through $x_{1:s+w} \subseteq x_{1:t+w}$ .

∎

This is label bias in its cleanest form (Lafferty, McCallum, and Pereira 2001): a locally normalized tagger passes on all of a state’s probability whatever the later words say, so the evidence of a later word cannot reach an earlier tag. Smith and Johnson (2007, Theorem 2) show that MEMMs represent strictly fewer conditionals than HMMs. Sutton and McCallum (2012, §5.1.3) add the practical caveat: copying later words into each factor’s features, a lookahead $w \gt 0$ , buys back exactly $w$ words, which Proposition 2 makes precise.

Corollary 2 (A ceiling for posterior decoding).

An MEMM with lookahead $w$ , decoded by posterior marginals, has expected token accuracy at most that of the Bayes rule $\hat z_t = \arg\max_k p(z_t = k \mid x_{1:t+w})$ .

Proof.

By Proposition 2 the MEMM’s marginal for $z_t$ , and hence its decision at $t$ , is a function of $x_{1:t+w}$ . Among all functions of $x_{1:t+w}$ , the Bayes rule maximizes the probability of a correct tag at each $t$ .

∎

Remark.

Corollary 2 is about posterior decoding, and it does not extend to Viterbi. The later factors of an MEMM sum to one over their tags, but their maximum is not constant, so the best path through $(t, k)$ still depends on how peaked the later factors are, and so on later words. That is label bias in Lafferty and colleagues’ original, Viterbi form.

Both halves are visible in the simulated worlds. Each MEMM sees two words to the left, with lookahead $0$ or $1$ , and is trained on $1{,}000$ sequences:

world, lookahead	ceiling	MEMM, posterior	MEMM, Viterbi
well-specified, 0	$0.743$	$0.735$	$0.758$
well-specified, 1	$0.769$	$0.763$	$0.765$
next-state, 0	$0.588$	$0.574$	$0.563$
next-state, 1	$0.610$	$0.593$	$0.580$

The “ceiling” column is Corollary 2’s lagged Bayes rule, computed exactly on prefix chains. Every posterior-decoded MEMM sits below its ceiling, and in the well-specified world the causal MEMM decoded by Viterbi ( $0.758$ ) rises above it ( $0.743$ ), as the remark allows. The CRF, whose marginals see the whole sentence, is bounded only by the full Bayes rule, $0.782$ there. One word of lookahead recovers about two-thirds of the gap, $0.769$ . In a chain the influence of a word on a tag tends to shrink with their distance, so the nearest future word carries most of what the future says; that is a picture, not a theorem proved here. The CRF vs. MEMM tab shows Proposition 2 on a sentence.

The structured perceptron

The CRF fits probabilities. Collins (2002) asked for less: weights under which the gold path outscores every other path, found by correcting mistakes.

Algorithm 1 (The structured perceptron).

Start at $\theta = 0$ . For each training pair $(x_i, z_i)$ in turn, decode $\hat z = \arg\max_z \theta \cdot F(x_i, z)$ by Viterbi; if $\hat z \ne z_i$ , update $\theta \leftarrow \theta + F(x_i, z_i) - F(x_i, \hat z)$ . Repeat for several epochs. The averaged perceptron returns the average of $\theta$ over every step.

Theorem 5 (The perceptron's mistake bound).

Suppose some unit vector $u$ separates the training data with margin $\gamma \gt 0$ , $u \cdot \big(F(x_i, z_i) - F(x_i, z)\big) \ge \gamma$ for every $i$ and every $z \ne z_i$ , and every difference has norm at most $R$ . Then the perceptron makes at most $R^2/\gamma^2$ mistakes, however many epochs it runs.

Proof.

Let $\theta_k$ be the weights before the $k$ -th mistake, $\theta_1 = 0$ , and suppose that mistake happens on pair $i$ with decoded path $\hat z$ . Then $\theta_{k+1} = \theta_k + \Delta$ with $\Delta = F(x_i, z_i) - F(x_i, \hat z)$ . First, $u \cdot \theta_{k+1} = u \cdot \theta_k + u \cdot \Delta \ge u \cdot \theta_k + \gamma$ , so $u \cdot \theta_{k+1} \ge k\gamma$ . Second, $\|\theta_{k+1}\|^2 = \|\theta_k\|^2 + 2\,\theta_k \cdot \Delta + \|\Delta\|^2 \le \|\theta_k\|^2 + R^2$ , because $\hat z$ won the decoding, so $\theta_k \cdot \Delta \le 0$ . So $\|\theta_{k+1}\|^2 \le kR^2$ . Since $u$ is a unit vector, $k\gamma \le u \cdot \theta_{k+1} \le \|\theta_{k+1}\| \le \sqrt k\, R$ , so $k \le R^2/\gamma^2$ .

∎

The proof uses the decoder only through one fact, that it returned a path scoring at least as high as the gold one, so the bound holds for any exact decoder. Collins’s Theorem 2 extends it to data that are not separable, and averaging, which every simulated-world and finance tagger here uses, is his practical recommendation; the Perceptron tab runs the plain perceptron. The Perceptron tab runs the theorem on data labeled by a teacher, at six margins: mistakes trend up from $3$ to $21$ as $\gamma$ falls from $0.315$ to $0.041$ (not at every step: $13$ , then $11$ ), while the bound rises from $867$ to $50{,}700$ . It holds every time, and it is loose by a factor of $121$ to $2{,}414$ , as worst-case bounds are.

Tagging entities in filings

§ Finance case study: BIO tags over the corpus's entity spans

The shared finance corpus annotates every entity span in its synthetic filings and call transcripts: organizations, people, places, products, sectors, dates, money amounts, and percentages. We convert the spans to BIO tags over the corpus’s tokens, lowercase letters only, which gives $17$ tags. That tokenization keeps only the word million of a money amount and the word percent of a percentage, two words that occur only inside entities, so MONEY and PERCENT are easy. The work is in names, and in “the”, which opens a PRODUCT or DATE span (“the third quarter”) and is otherwise outside every entity.

We train on the first $3$ , $10$ , and $30$ documents of one corpus run and test on $200$ documents of another. Every tagger except the HMM sees the same features: the word, its three-letter prefix and suffix, and the two words on each side (the causal MEMM sees only the left side). There is no gazetteer, so a name is learned only from training text. The HMM maps words seen once to an unknown-word symbol. Accuracy / span F1 on the test documents:

docs	HMM	causal MEMM	CRF	perceptron
3	$0.909$ / $0.618$	$0.890$ / $0.517$	$0.895$ / $0.556$	$0.909$ / $0.572$
10	$0.936$ / $0.745$	$0.942$ / $0.756$	$0.943$ / $0.776$	$0.960$ / $0.840$
30	$0.977$ / $0.923$	$0.982$ / $0.936$	$0.983$ / $0.943$	$0.991$ / $0.964$

At $3$ documents the HMM leads the CRF in both measures, the well-specified world’s small- $n$ story; by $30$ every discriminative tagger passes it, and the averaged perceptron, which carries no prior pulling the name weights toward zero, leads. What remains is mostly unseen names. With $3$ training documents, $0.369$ of the test tokens are words never seen in training, and with $30$ still $0.138$ . On those tokens the taggers score $0.911$ (HMM) to $0.958$ (perceptron) at $30$ documents, against $0.977$ to $0.991$ overall: the context features carry a name the model has never seen. How far context alone can go, with names held out by design, is the subject of the next topic, named-entity recognition.

Label bias has little to bite on here. The causal MEMM must tag “the” before it sees the next word, yet it tags “the” correctly $0.997$ of the time at $30$ documents: the templates that generate the corpus make the left context enough. So we test Proposition 2 directly instead. Take a test sentence’s opening, “solenne power guided to percent growth in the”, and complete it five ways with words seen in training (“prior year” itself never occurs in the corpus). With “first quarter”, the CRF tags “the” B-DATE with probability $0.963$ ; with “prior year” it tags it O with probability $0.977$ . The causal MEMM gives “the” B-DATE with probability $0.850$ under every continuation, identical to every printed digit as Proposition 2 requires, and its Viterbi path opens a date at “the” under every continuation, tagging “the prior” as the start of a date. The HMM agrees with the CRF except on “kestrel platform”, where it reads the polyseme kestrel, a company that is also a product name, as a PRODUCT with probability $0.962$ : the word’s emission outweighs its neighbors, which reach a tag only through the transitions, never as features of it. An invented sentence has no gold, and this reading follows the corpus’s product template: “the kestrel turbine” is a PRODUCT all $61$ times it occurs in training, and “platform” is inside a product $16$ of $19$ times. The CRF vs. MEMM tab shows every token of every continuation, and the Finance tab the table above with unseen-word accuracy.

Where this sits

The tagger on this page has two parts: a chain over tags and a scorer for each position. The chain, and with it every algorithm here, stays when the scorer changes. The next topic, named-entity recognition, replaces the hand-built features with a contextual encoder’s states and keeps the CRF on top. It also takes up what this page left aside: span-level evaluation, decoding constrained to valid BIO sequences, and names held out by design. A chain is the simplest graphical model; Theorem 1’s semiring argument is the one that sum-product and max-product message passing generalize to trees.

Honest caveats

⚠ Rigor flag

Proved and checked. Theorems 1–5, Propositions 1–2, and Corollary 2 are proved here in full. The harness checks Theorems 1, 3, and 4 against enumeration of every path on random instances, Theorem 2 against complex-step derivatives, Proposition 1 against counts, Proposition 2 by changing later words on random chains, Corollary 2 in the simulated worlds, and Theorem 5 on teacher-labeled data. Corollary 1’s asymptotic claim is measured, not proved.
Indicator features only. Theorem 3’s equivalence is for word-identity features. A CRF with overlapping features, such as neighboring words or suffixes, has a larger family than any HMM.
Posterior decoding only. Proposition 2 and Corollary 2 bind an MEMM’s marginals. Decoded by Viterbi, an MEMM still sees later words, as the well-specified world shows.
One prior, untuned. Every discriminative tagger is fit at $\lambda = 1/n$ , MAP under a standard normal prior, while the HMM’s add- $\alpha$ is tuned on validation data. Add-one smoothing cost the finance HMM two to five points.
A templated corpus. With $30$ training documents of one corpus run every tagger passes $0.977$ token accuracy, $0.54$ to $0.65$ of each tagger’s remaining errors fall on unseen words, and the left context settles the one tag (“the”) whose label depends on the next word, so this corpus barely exercises label bias. Proposition 2 is shown on counterfactual continuations.
Loose bound. Theorem 5 assumes separability, and its bound exceeds the observed mistakes by a factor of $121$ to $2{,}414$ .

Implementation

The companion notebook (notebookPath) imports sequence_labeling_hmm_crf.py, which owns every number on this page. It imports the n-gram topic’s module and the linear text classifiers topic’s module, whose softmax logistic regression fits every MEMM factor and whose finance corpus supplies the entity spans, and the masked-LM topic’s module for its HMM, sampler, and forward–backward pass. Its harness checks:

Theorem 1 in both semirings, and the max-marginals, against enumeration of every path;
Proposition 1’s counts and length law;
Theorem 2’s gradient and Hessian-vector products against complex-step derivatives, and its unique optimum from two starts;
Theorem 3 in both directions on random weights, sentences, and lengths;
Proposition 2 and Theorem 4 on random chains, and Corollary 2 against lagged Bayes rules;
Theorem 5 at every margin of the sweep;
every comparison this page states, in both worlds and on the finance documents.

The laboratory reads its data from a JSON file that one of the harness’s tests requires to equal the module’s viz_payload() exactly, so the figure cannot drift from the code.

Sequence Labeling: From HMMs to Linear-Chain CRFs

Overview & Motivation

The HMM tagger

One recursion, two semirings

The linear-chain CRF

A generative–discriminative pair

Decoding risk

Local normalization and label bias

The structured perceptron

Tagging entities in filings

Where this sits

Honest caveats

Implementation

Connections

References & Further Reading