FastText

Everything on this page is fitted to one small corpus, and what matters about it is not only what it holds but what it deliberately does not. Two hundred sentences of five to eight words each, every sentence drawn from one of two word lists and never from both. One list holds twenty forms of five verbs, play, stay, say, walk and talk, in their various endings; the other holds eleven words about money, stock, bond, market, price and so on.

That comes to 1,311 word occurrences across 31 distinct words, and no word appears in both lists.

The verb list holds play, plays, player and played. It does not hold playing. Every short run of letters that playing is made of turns up somewhere in the corpus, in the four play forms and in staying, saying, walking and talking, and the word itself turns up in no sentence at all. That single absence is what the rest of the page is about, because it is the smallest honest version of the situation every model meets the moment it is asked about text it was not trained on.

Word2vec learns by prediction. Slide a window along the corpus, and at every position nudge the vectors so that a word’s vector predicts the words beside it, and words that keep the same company end up in the same place. When the passes are over there is a table with one row per word, 31 rows of twelve numbers here, and that table is the answer. Everything in this page keeps that arrangement; the one thing it changes is what a row is looked up by.

Ask that table for playing and there is nothing to return. A row was allocated for each word the corpus held, playing was not one of them, and no amount of further training changes that, since further training walks the same sentences. This is not a shortcoming of any particular program. A method whose answer is a table indexed by whole words has, by construction, no entry for a word it never indexed.

vector(w) = row(w),  which exists only for the words the corpus held

It would be comfortable to read playing as a contrivance, one word held back so that the page has something to show. This corpus cannot settle that either way, and it is worth saying so before leaning on it. Its sentences draw words uniformly from a fixed list, so its commonest word appears 73 times and its rarest 17, and not one of the 31 appears only once. A text made that way has no tail of rare words for a missing word to come from.

So the case has to be made rather than found. Take a word the corpus really does hold, walking, and drop every sentence containing it, which is 30 of the 200 and removes all 34 of its occurrences. Fit both ways on the 30 words that are left, then ask both for walking.

…

The method built from pieces places walking at a mean cosine of 0.9953 to the nineteen verb forms that survived and 0.0497 to the eleven money words, with walked nearest, and it does that having never seen the word. The method with one row per word has nothing to return, exactly as it had nothing to return for playing. Which word was held out made no difference to either answer.

FastText adds one thing. A word still has a row of its own, and the window, the scoring, the drawn wrong answers and the falling step size are all unchanged. What is new is that a word also stands for the short runs of characters its spelling is made of, so that two words spelled alike are made of some of the same parts.

Before it is cut, the word is wrapped, so play becomes <play>. The wrapping is not decoration. Without it the three letters her at the beginning of a word, in the middle of one and at its end would all be the same piece; with it the piece at the start of her is <he and the piece at its end is er>, while the her sitting inside where is the same plain her that her itself also contains.

So a beginning and an ending are told apart from the same letters somewhere in the middle, which is what carries a grammatical ending.

pieces(w) = every run of m to M characters inside <w>, except <w> itself

…

There are far more pieces than there are words. The 31 words of this corpus own 279 distinct pieces between them, 13.6129 per word on average, five for the shortest and 22 for the longest, and that ratio grows with the vocabulary rather than shrinking, since a bigger vocabulary holds longer words and a longer word has more pieces. Giving each piece an entry of its own would mean a second vocabulary to build, hold and look up, which is most of what a fixed width was meant to avoid.

So the pieces get no vocabulary at all. Each is put through a hash, a function that turns a string of bytes into a number, and the remainder of that number on division by however many rows there are is the row it uses. The number of rows is chosen before any text is read, two million in the published work and two thousand here so that the consequences are visible.

hash = 2166136261,  then for each byte b of the piece:  hash = (hash xor b) × 16777619,  modulo 2³²

the row for a piece  =  hash(piece) modulo the number of rows

With the pieces placed, a word’s vector is a sum. Its own row carries whatever is true of that word alone, and the rows of its pieces carry whatever is true of every word that shares them.

vector(w) = row(w) + Σ over the pieces g of <w> of row(g)

On this corpus play, plays, player and played all add the rows for <pl, pla, lay, <pla, play and <play, six pieces they have in common, so anything the corpus teaches about any one of them moves all four. Staying and saying share ten pieces with playing, all of them from the ending; walking and talking share three, ing, ing> and ng>. That sharing is the whole of what the method adds, and it is worth noticing that it is decided before any fitting, by the spellings alone.

The composition is a sum, and the derivative of a sum with respect to any one of its terms is the derivative with respect to the whole. So when a training pair asks a word’s vector to move, the correction is added unchanged to the word’s own row and to every one of its pieces’ rows. That is what differentiating gives rather than a convention chosen for convenience.

∂cost / ∂row(part) = ∂cost / ∂vector(w),  the same for every part

One consequence is arithmetical. A word here has 14.6129 parts on average counting its own row, six for the shortest word and 23 for the longest, so its composed vector travels that many times as far per correction as a plain one would for the same gradient. The cost curve shows it. The first pass over the corpus costs 2.5560 per training pair where the same fit without pieces costs 3.7370, and by the second pass the two are 2.0716 and 2.6643.

For a word the corpus held, the vector is the row plus the pieces. For a word it did not hold, the first term is simply absent, and what remains is a sum a caller can still compute, because the pieces of any spelling can be worked out and hashed whether or not anything has ever written to their rows.

vector(w) = Σ over the pieces g of <w> of row(g)

Playing has 22 pieces at the published lengths. Sixteen of them are owned by some word of the corpus, and those rows have been written to thousands of times; six of them, layi, playi, layin, <playi, playin and laying, occur in no word of the corpus and their rows never moved. Seventeen of the 22 rows it reaches had been written to, one more than those sixteen pieces account for, and the extra one is an accident worth remembering.

The piece playin, which no word of this corpus holds, was sent to row 1312, and so was ayed>, which played, stayed, walked and talked all own.

A mean on its own would not settle whether the answer is any good, since two means can be far apart while the ranges behind them overlap completely. So both worst cases are marked as well.

…

Playing comes back at a mean cosine of 0.9970 to the twenty verb forms and 0.1003 to the eleven money words. The verb form it is least alike is still 0.9939 and the money word it is most alike is 0.1106, so the two ranges are separated by 0.8833 and nothing overlaps. Its four nearest words are play at 0.9993, plays at 0.9988, player at 0.9987 and played at 0.9985, which are the four forms of its own verb and in a sensible order, from a fit that never saw the word.

The same sum can be taken for a word the corpus did hold, leaving out its own row. What comes back is what that word’s vector would have been had it never been seen, and comparing the two says how much of the word is carried by its spelling rather than by its own occurrences.

On this corpus a word is almost entirely its spelling. Dropping played’s own row leaves a vector pointing 0.9997 of the way in the same direction and 0.9827 as long, and bond, the shortest of the four with nine pieces, is the one that loses most of its length at 0.9043.

Both fits use the same corpus, the same width of twelve, the same reach of three, the same five passes, the same first step and the same seed, so the only difference between the two columns below is whether a word also stands for its pieces.

…

Asked for the five words nearest walked, the fit that reads spellings names talked, walk, says, walking and walks; the fit with one row per word names talking, walking, talk, stays and said. Both lists are entirely verb forms, so neither is wrong about the category, and they share one word of the five. What has changed is that three of the five are now forms of walk itself where before there was one, which is what sharing <wa, wal and alk does.

Before counting what the pieces cost, it is worth knowing exactly what they add, and there is a clean way to ask. Set the shortest piece to fifty characters. The longest wrapped word in this corpus is nine characters, so no word has a piece at all, every row kept for the pieces stays where it started, and what is left ought to be the plain method exactly.

…

It is the plain method exactly. Under all four pairings of the two training choices the fitted table, the scoring rows and every pass’s cost agree with a fit that never had the pieces, and the largest disagreement anywhere is 0.0 rather than something very small. Two passes cost 3.8942 and 2.7842 by both routes, the same numbers to the last bit.

A word of length L wrapped has L plus two characters, so at lengths m to M it yields one run for every starting position at every length that fits, which is a count that grows with the word’s length and with the width of the range.

how many pieces =  Σ over k from m to min(M, L + 1) of (L + 3 − k)

where, L = 5:     (5 + 3 − 3) + (5 + 3 − 4) + (5 + 3 − 5) + (5 + 3 − 6) = 5 + 4 + 3 + 2 = 14
playing, L = 7:   7 + 6 + 5 + 4 = 22
at, L = 2:        (2 + 3 − 3) = 2

Where that lands is a choice with nothing inside the fit to settle it, and both ends of it cost something. Cut this corpus at exactly three characters and there are 84 distinct pieces, five per word, and the missing form comes back at 0.1427 to the money words rather than 0.1003. Refuse to cut below four and there are 195 pieces and it comes back at 0.2302, because the short pieces are the ones the ending shares.

With 279 pieces to place and the number of rows fixed in advance, some pieces land on top of each other, and the method makes no attempt to prevent it. Two pieces sent to one row are simply added into the same twelve numbers, and every word that owns either piece then reads the sum.

…

At two thousand rows the 279 pieces occupy 260, so nineteen of them are sharing. Row 1713 holds <play, which the four play forms own, together with alk, which walk, talk and their six other forms own, so every one of those twelve words is reading a number the other eleven helped write. Row 897 holds <sto from stock and lay> from play. At twenty thousand rows only two pieces share one, and at the published two million none of them do.

Making the table small enough shows the sharing doing damage. At ten rows all 279 pieces are crushed into ten, and the two lists come out 0.9359 alike within a list and 0.4942 alike across the two, a separation of 0.4417 against the 0.8723 that two thousand rows give. The missing form comes back at 0.5497 to the money words, which is no longer an answer worth reading.

What the sweep does not show is a smooth curve, and it is worth reporting rather than smoothing over. Fifty rows put the missing form at 0.1133 to the money words and two hundred rows put it at 0.2285, which is worse at the larger table. Which particular pieces happen to collide is a fact about the hash and this vocabulary, not a quantity that improves steadily as the table grows.

The answer a caller reads is the same size either way. Thirty one words of twelve numbers is 372 numbers, and composing each word from its parts before handing it over does not change that. What grew is what has to be kept in order to answer at all, since the rows for the pieces have to be there whether or not anything ever wrote to them.

That is just over sixty five times as many numbers held for an answer of the same size, and 1,740 of the two thousand rows were never written to at all, because how many rows there are is settled before any text is read rather than discovered from it. On a corpus this small that is the clearest place the method is worse than the one it extends, and it is also the cost that scales best, since two million rows is a fixed bill however large the vocabulary becomes.

Playing is the flattering case, since its spelling and its meaning agree about which list it belongs to. Seven more words no sentence holds are worth putting through the same fit, chosen so that some of them ought to land among the money words and some among the verb forms.

…

Five of them land where a reader would put them. Banking comes back at 0.9632 to the money words against 0.3718 to the verbs, and its three nearest are trade, yield and debt; stocking, traded, sharing and priced do the same, the last at 0.9870 with price, yield and fund nearest. Walkway lands among the verbs at 0.9970, nearest walk and walks, and that is the spelling working exactly as designed while giving the wrong answer, since a walkway is a thing rather than something anybody does.

No sentence here ever put walkway beside anything, so there was no evidence to weigh against the letters it shares with walk, walks, walked and walking.

The eighth word is the interesting one. Queue has fourteen pieces and shares no letters worth mentioning with anything in this corpus, so thirteen of its rows were never written to and contribute nothing. The fourteenth is queue>, which the hash sent to row 98, and so is arket, which market owns.

So the whole of queue’s vector is one row that market and nothing else wrote, and it comes back at 0.9919 to the eleven money words with market, stock and cash nearest. That sits within 0.0051 of playing’s reading of its own list, and it was produced by an arithmetic accident with no connection to spelling, meaning or usage. Nothing distinguishes the two answers at the point a reader sees them.

Zap has five pieces at the published lengths, and the hash sent every one of them to a row that no word of this corpus reaches. So every term of the sum is a row that never moved, and the vector is every coordinate exactly zero.

cos(a, b) = (a · b) / (|a| |b|),  which is 0 / 0 when |a| = 0

A cosine is a ratio whose denominator is the product of the two lengths, so against a zero vector it is zero divided by zero. It is not a small similarity and not a large distance; the quantity does not exist, because the zero vector has no direction for an angle to be measured from.

That is a fact about the arithmetic rather than about any program, and every implementation faces the same choice. Refusing says so. Returning zero would report that the word is unrelated to everything, which is a claim the method never made. Returning some default direction would place the word somewhere the corpus never implied, which is the thing having pieces was supposed to avoid.

When two pieces land in one row, their corrections are added into the same numbers, and addition of that kind has no inverse. The fitted table holds a sum and no record of what went into it, so from the answer alone there is no procedure that recovers which pieces wrote a row, or how many did.

The collisions this page names were found from outside, by taking the corpus’s own list of pieces and hashing it a second time looking for two that agree, which works only because that list was already in hand. It does not extend to the case that matters. The piece queue> belongs to no word of the corpus, so no list of the corpus’s pieces contains it, and the only way to find that particular accident is to already suspect the word queue and go looking.

The set of spellings that might one day be asked for is not a set anybody can enumerate.

Everything the method adds is carried by one quantity, how much two related words’ pieces overlap. On this corpus that quantity is generous, and it is why the method works here at all. Playing shares ten pieces with saying and six with played, and none at all with any of the eleven money words, so the sum over its pieces could hardly land anywhere else.

That overlap is not a property of the method. It is a property of how a language writes its grammar, and it is fixed before any fitting begins. Where related forms are built by adding letters to a stem, as they are for walk and walking, the overlap is large and the method is buying something real.

Where a related form is written differently, as go and went are, the two share no run of letters at all and the pieces have nothing to carry. And where two unrelated words happen to look alike, the pieces carry a connection that is not there, which stocking and stock show in miniature.

Several inputs leave the method with nothing to compute rather than something approximate to compute, and a few more leave it with a genuine choice whose cost is worth knowing. The table gathers both, with what the mathematics says in each case.