Sequence labeling: CRF, HMM and Viterbi

1A label for every token

Sequence labeling gives every token one label, so the output is as long as the input. Part-of-speech tagging has that shape already, since each token is its own unit. A name can span several tokens, so named-entity recognition marks where each name begins, B- for “beginning”; the tokens that continue it, I- for “inside”; and everything else, O for “outside”. After the dash comes the name's kind. Here there are two kinds, persons and places, so there are K = 2 · 2 + 1 = 5 labels:

where a sentence's tokens are x = (x₁, …, x_N) and its labels y = (y₁, …, y_N), N its length. A name starts at each B- and runs over the I- of its kind that follow. An I- after an O, at the start, or after a name of the other kind continues nothing and breaks the scheme. Names cannot nest: La Mancha inside the knight's name is I-PER, as the note on words underlined the whole name. In the figure, pick a phrase and click a word to change its label.

Both readings of the knight's name are valid: one person, or a person and a place. The labels alone cannot choose between them; the model of sections 3 and 4 weighs them. The second phrase shows why the scheme needs B-: with kinds alone, two names that touch read as one. In the puppet show of chapter XXVI of part II, Don Quixote says the puppets seemed real, “Melisendra was Melisendra, Don Gaiferos Don Gaiferos, Marsilio Marsilio”. Ramshaw and Marcus (1995) introduced the three letters for noun phrases, with B- only where two phrases touch; the version used here, and by most taggers, puts it at every start.

2One encoder, many heads

An encoder is whatever gives each token a vector. The simplest is a trained table of word vectors: here the book's vectors with subwords from the note on subwords, d = 100, which give every token a vector, the same in every sentence. They stay as they were trained; only what sits on top is trained, and that part, the head, decides the task. A head that gives the whole text one label is the classifier of the notes on linear models and word vectors; a head that compares two texts' vectors is the cosine of the note on word vectors; a head that gives every token a label is this note's.

The labeling head is a linear layer, the same at every token. It gives each token one score per label, the score w_k^Tx of the note on linear models with the token's vector in place of x. The scores stack into a table P with a row per token and a column per label,

where v_xi is token i's vector with a 1 in front, so that the bias sits in w_k, row k of the layer's matrix. A softmax per token turns each row into probabilities, and each token takes its highest:

The book has no labeled names, so for this note its people and places were listed, about 90 entries for people and 36 for places, and every occurrence was labeled: Don opens a person's name, while Rocinante and God stay O, as do the few names printed all in capitals. The heads train on the book except chapter I of part I and every tenth chapter, which are held out to measure them. The figure draws P on its side, a column per token and a row per label, each column shaded by its token's probabilities. Pick a phrase and a box, and check that the columns of “of La Mancha” do not change between the two phrases.

The head decides each token alone, and a word's row is the same wherever it stands. Mancha is part of the knight's name in about three of every four of its uses in the book, so the head labels it I-PER even after “a village of”, and nothing stops an I- right after an O: both phrases end in labels the scheme forbids. “El Toboso” alone reads B-LOC I-PER, because Toboso is mostly in “Dulcinea del Toboso”. The vectors were trained on lowercase text, so this head never sees a capital letter, the clue the note on words pointed to. What is missing is a way for one token's label to look at its neighbor's.

3The transition matrix and a labeling's score

A conditional random field (CRF; Lafferty, McCallum and Pereira 2001) adds one table A, the transition matrix, a score for every ordered pair of labels in a row: which label may follow which. The first token has no label before it, so a start label y₀ stands before the sentence, and A has one more row, A_y0,k, for how a sentence may begin. A labeling's score walks the sentence adding, at each token, what the head says of its label and what the table says of the step into it:

with A ∈ ℝ^K×K plus its start row: 30 numbers, against the head's K(d + 1) = 505. The table is learned with the head, as section 4 explains; nobody writes the scheme's rules into it. Lample et al. (2016) put this table on top of a recurrent network's scores, which a later note covers; here it sits on the static vectors and a linear layer. Lample et al. also add an end label, a column of A for how a sentence may end; this tagger has only the start row. From here on, the head is the one trained together with the table, so its scores differ from section 2's: the table now does part of the work. In the figure, pick one label per token and read the labeling's score.

The table learned what the labels did. An I-PER right after an O scores −8.66, and at the start −5.93; a place's second word after its first scores +3.67. It learned the data, not the rules: B-PER right after B-PER, two names that touch, is legal but sits at −6.77, since the labeled book has it once, while the illegal I-LOC → I-PER sits at only −2.03. Training pushes a step down only while the model is still tempted to take it, so a legal step almost never seen sinks like an illegal one, and an illegal step that rarely tempts stays mild. Nothing forbids a broken labeling if the head's scores push hard enough.

4The normalizer Z and the forward recursion

A score is any number. To make it a probability, exponentiate it and divide by the sum over every labeling, the softmax of the note on linear models with one class per labeling:

Z(x) depends on the sentence, not on the labels: it is computed once per sentence and shared by all its labelings, and it does not change which is best. But there are K^N labelings, the note on word2vec's costly normalizer at its worst. The grid avoids listing them. Let α_i(k) be the sum of e^s over every labeling of the first i tokens that ends at label k, the score stopped at token i. Every such path comes through some box of the column before, and e^a+b = e^ae^b, so each box is the column before times one step:

This is the forward recursion, often called the forward algorithm (not the forward pass of a network). It takes N·K numbers and about N·K² multiplications, against K^N labelings. The softmax per token of section 2 summed one column of the grid; Z sums every path through it. In the figure, pick a box to see what flows into it, or the Z box at the right.

Adding up e^s over all 625 labelings gives the same Z, 6,134. Training lowers, over the training sentences, the loss of each labeled sentence (Lample et al. 2016),

with logarithms natural on this page. Lowering it raises the right labeling's score and, through Z, lowers all the others; the head and A learn together by a variant of gradient descent. In practice e^s overflows on long sentences: a sentence of 168 tokens in chapter XLI of part I already has a log Z of 716, while a 64-bit number holds nothing above e^709.78. So programs keep log α and add in logs, by log-sum-exp: log(e^a + e^b) = m + log(e^a−m + e^b−m), with m the larger of a and b, so that no exponential exceeds 1 (the summary's row “In logs”); the note on word2vec's code subtracts z.max() before its softmax for the same reason. Sizes grow fast: the book's first six words, “In a village of La Mancha”, have 15,625 labelings and 30 boxes, and the book's median sentence, 45 tokens, has about 2.8 × 10³¹ labelings and 225 boxes.

On “Don Quixote of La Mancha”, the tagger gives one person a probability of 0.89 and a person and a place 0.09: it prefers the name, as the labeled book does. On the held-out chapters, measured against the names list, 95% or 96% of the names it marks match a listed name in span and kind, and it finds 83% or 84% of the listed names, in all five training runs; the head trained alone matches 81% to 83% and finds 74% or 75%. It leaves at most one broken I- in 962 sentences, where the head alone leaves 51 to 64. Forbidden steps sink only with enough training: after 8 readings of the training chapters instead of 30, at a fifth of the learning rate, A_O,I-PER was −2.13, three broken I- remained, and “In a village of La Mancha” came out O O O O I-PER I-PER.

5The hidden Markov model, trained by counting

Could a tagger's tables simply be counted from text that people have tagged? A hidden Markov model (HMM) tells how a sentence could have been produced: a chain of labels, each depending only on the one before it (a Markov chain, not the chain of hypernyms of the note on words), and each label producing its word, which depends only on its label. Its labels are written h, for hidden: in a new sentence only the words arrive. On this page h means this, not the logistic output of earlier notes, and many texts write the hidden chain as q and the words as o; here x is always the input. y and h are the same kind of thing, labels, as the CRF and the HMM write them.

The second also holds when the other words are known: a word depends on its own label alone. Together they give the probability of words and labels together, the joint, not the labels given the words:

with h₀ the start. An upright P followed by parentheses, as in P(x, h) or P(h_i | h_i−1), is a probability; the italic P with two indices stays the head's table of scores. The task switches to parts of speech, the tags of Universal Dependencies from the note on words, since text tagged by hand is plentiful for them: the counts come from two treebanks, UD English EWT (14,545 sentences and 226,751 tokens counted; its other 2,077 sentences are kept for testing) and UD Spanish GSD. Training sees words and tags, and each table is counted and divided:

where c counts. c(j) counts every j, a sentence's last tag included, which is followed by the sentence's end, a column of its own, so each row's shares sum to 1 over the tags and the end; a whole sentence's chain ends with that one more step, P(end | h_N), which the clause in the figures, not ending its sentence, leaves out. These shares make the tagged text most likely, for the reason the note on word2vec's best guess gave each word its share; nothing is iterated, which is needed only when no tags are given. Two tables remain, transitions and emissions, and the chain's log is a sum, log P(x, h) = ∑_i [log P(h_i | h_i−1) + log P(x_i | h_i)]. In the figure, the clause “To come to the point”, which opens its sentence in chapter XLV of part II, sits on the grid with a box only where the treebank gave a word that tag in at least one of every 50 uses. Pick a tag for each word and watch the chain's log.

The other tags are possible but rare, and decoding over these boxes gives the same chain as over all 17 tags. The cells that decide: a verb follows a particle with P(VERB | PART) = 3,679 / 4,723 ≈ 0.78, and a determiner follows a preposition with 7,037 / 19,747 ≈ 0.36 but a particle with only 83 / 4,723 ≈ 0.018. The HMM is a CRF with log-probabilities: with A_j,k = log P(h_i = k | h_i−1 = j) and P_i,k = log P(x_i | h_i = k), section 3's score is log P(x, h), and section 4's Z(x), with the step into the end, becomes P(x), the probability the model gives the sentence. Both chains run over the labels; the difference is what each models and how it learns. The HMM counts tables that explain how the words were written, the joint; the CRF learns scores that tell labels apart given the words, the conditional. A pair never counted gives log 0 = −∞, a chain the HMM calls impossible, which a learned A never quite does. A word the treebank never saw gets a share guessed from words seen once that, like it, do or do not start with a capital and end in the same three letters; without that, it would have probability 0 under every tag.

6Viterbi: the best labeling without trying them all

With 17 tags per word, how does a tagger find the best chain without trying 17^N of them, and why not choose each tag as it goes? Let δ_i(k) be the probability of the best chain that reaches tag k at word i, using only the words up to there. It is section 4's grid with a max in place of the sum (Viterbi 1967):

with δ₁(k) = P(h₁ = k | h₀) P(x₁ | h₁ = k). Each box keeps only its best incoming chain, and remembers which tag it came from, its back-pointer. The largest δ of the last column is the best chain's probability, P(x, h*) = max_k δ_N(k); its argmax gives only the last tag, and the chain is read by following the back-pointers from right to left: h*_N = argmax_k δ_N(k), h*_i−1 = argmax_j δ_i−1(j) P(h_i = h*_i | h_i−1 = j). δ falls along the sentence, since every step multiplies in one more probability, so boxes are compared within a column, never across, and δ is kept in logs: a product of factors of 0.001 is exactly 0 in 64-bit numbers after 108 factors, and the best chain of a sentence of 100 tokens in chapter III of part I already has a log of −746.4, while a 64-bit number rounds to 0 below about e⁻⁷⁴⁵. Choosing one tag at a time, left to right (“greedy”), commits to each tag before seeing the next word; Viterbi waits for it, at the same cost as the forward recursion, N·K² steps. In the figure, compare the two.

Each word alone, its most frequent tag, gives PART VERB PART DET NOUN, with a log of −25.73. On each treebank's own test sentences, each word alone tags 89.3% of the words right, one at a time 90.0%, and Viterbi 92.4% (Spanish GSD: 93.4%, 93.8%, 94.8%). Over the whole book, Viterbi tags to a particle 7,855 times and a preposition 5,366, where each word alone always says particle. The treebanks are modern and the book is not: 8.2% of its tokens are words the English treebank never saw, such as thee and hast.

The CRF decodes the same way on its scores, which add up along a path, so its δ adds where the HMM's multiplies (Lample et al. 2016): δ_i(k) = max_j [δ_i−1(j) + A_j,k] + P_i,k. On “village of La Mancha” it gives O O B-LOC I-LOC, with a score of 8.40, though at La the best chain so far ended in I-PER (1.95 against 1.20 for B-LOC): the last word changed the answer. Run with the sum instead of the max, the HMM's grid gives P(x), section 4's recursion; both models use both recursions. The head here reads one word's vector at a time. The next note's recurrent networks give each token a vector that depends on its neighbors, and turn the HMM's hidden tag into a hidden vector.

7Summary

The note's ideas in NumPy. vecs holds the tokens' vectors, one row each with a 1 first; w is the head, a row per label; A has K + 1 rows, the last the start label's; trans has K + 1 rows (the last the start) and K + 1 columns (the last the sentence's end, as section 5 counts it), and emit a row per tag and a column per word; tagged holds the treebank's sentences as pairs of index arrays, and V is the number of different words in it; x, y and h are arrays of indices, N the sentence's length.

The note's data: the books are Project Gutenberg's Don Quijote (#2000) and Ormsby's translation (#996). The book's vectors with subwords were trained for these notes, and the list of the book's people and places, its labels and the taggers were made for this note. The counts of the hidden Markov model come from Universal Dependencies' English EWT and Spanish GSD treebanks, under the Creative Commons Attribution-ShareAlike 4.0 license; the page shows only counts computed from them, shared under the same license.