Subwords and fastText

1Words with no vector

A trained table of vectors is fixed: a word it did not keep is out of vocabulary (OOV) and has no row, so no vector. A classifier that reads it gives it nothing, as the linear model weighed the cabbages of the note on linear models at 0. Such words come in two kinds: the words the table dropped, which the text used one to four times, and the words never seen at all. More text lowers their share without ever ending it, as the note on the laws of text showed: the tail of rare words never runs out. In the figure, train the table on the book up to the red point, keeping the words used at least five times, and see how many of the tokens of the next tenth of the book have no vector.

Trained on part I, the table has no vector for 10.1% of part II's tokens and 74.5% of its different words; even keeping every word, 4.1% of part II's tokens are new. Among the words it lacks are other forms of words that have a vector, such as lions and proverbs, names, and words the first part never needed, such as duchess and majordomo; they run longer than the words with a vector, 7.4 letters against 6.2. Of the 9,928 words the book's table drops, fastText's table lacks 794, in lowercase or with a capital: names such as babieca and caraculiambro, old forms such as o'er, and words with an apostrophe such as knight's. The other forms of known words are the ones that pieces of words can rescue.

2A word's subwords

What could a word with no vector be made of? Mark its start and end with < and >, then slide a window n characters wide along it, one character at a time, as the note on word2vec slid a window along a text. Each run of n characters is a character n-gram, or subword; the pieces of words of the last note are these subwords. The marks tell a run at a word's end, such as mill>, from the same letters inside a word. fastText takes every n from 3 to 6, and a word that has a row of its own, one used at least five times, counts that row as one more:

with o itself added when it has a row of its own. A word of |o| characters has |o| + 3 − n runs of length n, so 4|o| − 6 in all once |o| is at least 3. In the figure, pick a word and a range of lengths.

The 9,928 words with no vector have 67% of their subwords in words that have one: 95% of their subwords of 3 characters, but only 31% of those of 6. Short runs are shared, long runs are specific. windmill, which the book never uses, shares 22 of its 26 subwords with windmills, and one, dmill>, is in no word with a vector.

3A word as the sum of its subwords

Each subword gets a vector of its own, v_g ∈ ℝ^d, a row of the table, and a word's vector adds up its subwords' vectors:

A word never seen still has subwords seen inside other words, so it gets a vector, near the words that share them. It is the pooling of the note on word vectors, over a word's subwords instead of a text's words. fastText's program takes the mean instead of the sum, dividing by the number of rows, which, as that note showed, changes no direction and no cosine; the figures follow the program. The figure uses vectors trained on the book with subwords, as section 5 explains. Pick a word, and compare its closest words with those of the note on word vectors, which kept whole words only.

A row that no word with a vector uses keeps its random start, so short that it adds almost nothing: a length of about 0.06, against a median of 2.4 for a word's vector. For a word with a row of its own, that row is one of many: squire's is 1 of its 19, and without it the vector would keep a cosine of 0.999 with what it is. So a frequent word's closest words change too, toward words spelled like it: esquire and squirely for squire, where the whole words gave panza.

4Few symbols, every word

Won't a new word's subwords be new as well, and how many rows does this take? A fixed set of symbols composes every word: this is compositionality. The book writes its words with 37 characters (26 letters, the apostrophe, and 10 others from names and borrowed words, such as é, ñ and æ), 39 with the two marks, so there can be at most

subwords of 3 characters, where |Σ| is the number of symbols; only 53,280 can occur, since a mark only opens or closes a run and the apostrophe stands only between letters. Subwords of 3 characters grow ever more slowly and stay far below that ceiling, 4,764 after the whole book, while new words keep coming. Subwords of up to 6 characters keep growing, so fastText caps the table: a hash function turns each subword into a number, whose remainder after dividing by 2,000,000 picks its row, and two subwords can then share one. Words with a row keep their own rows as well, so 𝒢_o lists rows among G = V + 2,000,000, where V is the number of words with a row of their own, 4,993 for the book. In the figure, drag the red point along the text read; the ring marks ten times as much text.

Heaps' law of the note on the laws of text predicts about 3.3 times the words for ten times the text, and the book gives 3.0. The 36,983 subwords of the words with a vector land in 36,621 rows, so a few hundred rows hold two subwords, and training on the book reaches only those rows of the 2,000,000.

5Training with subwords

Where do the subwords' vectors come from? From the training of the note on word2vec, with one change: the target goes in by its subwords. The pairs (o, c) are that note's, but the target is no longer a one-hot vector: it is a multi-hot vector, with a 1 for each of its subwords,

where e_g has a 1 at row g and 0 everywhere else (it is not the embedding e(w) of the note on word vectors), and a subword repeated in a word, or two subwords sharing a row, gives a 2. Now W_in ∈ ℝ^G×d while W_out ∈ ℝ^d×V is as before, and so are z = W_out^Tv_o and y = softmax(z), which training replaces with negative sampling. The first layer still selects rows of W_in and adds them up, as that note said W_in^Tx does, weighted by x. A dot product is linear, so a pair's score is the sum of its subwords' scores:

and the loss is that note's binary cross-entropy with h = σ(s(o, c)). Each row's share of the gradient is (h − y)u_c, the same for every subword of the target: one step moves every row the target uses, so a word that shares some of those rows moves without being trained. Only the target's side is split. Its rows are the table that is kept, as word2vec's original program kept only W_in, so they must serve words never seen; W_out keeps a column per word and plays no part in the word vectors.

The figure follows a designed example in two numbers per vector, with subwords of 3 characters only, to keep it small: the target giants, with its six subwords and its own row; the pair (giants, windmills) of the note on word2vec, windmills in green, and one drawn word, habit, in ink; and giantess, in no pair and with no row of its own, which shares four of its eight subwords with giants. The target's vector is the mean of its rows, as fastText computes it, and every row takes the whole step. Take steps of gradient descent with η = 0.4.

The book's model is the training of the note on word vectors (d = 100, a radius drawn up to m = 5, k = 5 drawn words with β = ¾, 20 readings, a minimum count of 5, five training runs), with each target going in by its subwords of 3 to 6 characters and its own row, in 2,000,000 rows; with the subwords switched off, it gives that note's vectors exactly. The figures and the numbers quoted show the first training run, and the text claims only what held in at least four of the five. In our program it took about 2.5 times as long (101 seconds against 41 on the English book); the paper on fastText reports about 1.5 times slower than the skip-gram.

6fastText and the vectors you download

fastText is the program of Bojanowski, Grave, Joulin and Mikolov (“Enriching Word Vectors with Subword Information”, 2017): the skip-gram of sections 2 to 5. Their paper trained it on Wikipedia in nine languages, with d = 300, 5 negatives drawn by the square root of the counts (β = ½), a radius drawn from 1 to 5, and 5 readings of the text. Among the vectors published later are 294 languages trained on Wikipedia with that skip-gram, and 157 languages trained on Common Crawl and Wikipedia (Grave et al. 2018), the tables of the note on word vectors. Those are CBOW with position weights, with subwords of 5 characters only, a radius drawn from 1 to 5, 10 negatives and d = 300: each word around goes in as the mean of its rows, weighted number by number by a vector learned for its place in the window. In CBOW the words around go in by their subwords and the word guessed stays whole: in both models, the side that goes in by pieces is the input, whose rows are kept. In the figure, pick a target in Sancho's line from the note on word2vec, with radius m = 2, and a model.

The web's tables draw a radius of up to 5, not the figure's 2. Their .vec file holds one finished row per word, the word's own row averaged with its subwords', so it cannot build a new word; their .bin file, about 7 GB, keeps the subword rows and can. With subwords of 5 characters only, a word of one or two letters missing from the table has no subword at all and gets the zero vector. Like the book's vectors, these have one vector per spelling, whatever the sentence. The same library also classifies texts (Joulin et al. 2017), and the often-quoted billion words in under ten minutes is that classifier's speed.

7What subwords get right and wrong

Is closeness in spelling closeness in meaning? The cut is blind to meaning: when the shared subwords are the lexeme, the likeness is real, and when they are only the ending, it is spelling. By the same linearity as section 5, a word's cosine with another splits into one part per subword:

(with the program's mean, the same value). So the cosine tends to rise with the number of subwords the two words share, |𝒢_o ∩ 𝒢_o′|. If every subword's vector had the same length and stood at right angles to the others, the cosine would be the share in common, |𝒢_o ∩ 𝒢_o′| / √(|𝒢_o| |𝒢_o′|); trained rows are neither, so the count is a tendency, not a rule. Pick a word with no vector, and compare its closest word that shares its start with its closest word that shares its end.

Subwords get forms right. Of 532 words whose form with an added s also has a vector (plurals such as knights, but also verb forms such as knows), the whole-word vectors of the note on word vectors put that form, at the median, 335th among the word's closest words, and first in 1% of them; with subwords it comes first in 66%. falsehoods moves from 164th to first for falsehood. Analogies of form gain while those of meaning lose: knight : knights :: giant : giants moves from 180th to first in all five training runs, while king : kingdom :: governor : island, first for the whole words, falls to sixth or seventh, behind governor's. The paper on fastText found the same split between analogies of form and of meaning.

They get meaning wrong where spelling misleads. Frequent words drift toward words spelled like them: of the 10 closest words of each of the book's 878 most frequent words of four letters or more, 3.4 share a run of 4 characters with it, against 0.19 with whole words. still now sits by till and bread by breadth, in all five training runs, where the note on word vectors put bread by cheese; patience sits by impatience too, but through their shared lexeme, a real relation between opposites. With far more text the accidents fade: in the web's table, knighting has a cosine of 0.585 with knight and 0.199 with righting, and still 0.259 with till. Subwords help most where text is scarce, and their mistakes are spelling's mistakes; one spelling still keeps one vector. Later notes cut the text itself into pieces chosen by merges, and build vectors that change with the sentence.

8Summary

The note's ideas in NumPy. w_in has a row per word with a vector, then 2,000,000 rows of subwords, and w_out a column per word; idx gives a word's row, rows lists the rows of the word o, c is a context word's column, y its label and eta the learning rate; tokens is a text, and V the number of words with a vector.

The note's data: the books are Project Gutenberg's Don Quijote (#2000) and Ormsby's translation (#996); the counts of fastText's tables, cc.en.300 and cc.es.300 (Grave et al. 2018), come from the files at fasttext.cc, under the Creative Commons Attribution-ShareAlike 3.0 license, and the page shows only what was computed from them. The book's vectors with subwords were trained for this note.