Word2vec

Everything on this page is fitted to one small corpus, and it is worth knowing exactly what is in it before any method touches it. Two hundred sentences of five to eight words each, and every sentence is 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 sentences themselves are nonsense, which is the point. Nothing in them is grammatical and nothing means anything, so there is no hidden knowledge of English for a method to exploit, and the only structure available is which words turn up beside which. If a method recovers the two lists it did so from company alone, and if it does not, we can say so with a number rather than an impression.

The oldest way to use that structure is to count it. Walk along every sentence, and for each word write down which words turned up within three positions of it, with a neighbour two away counting a half and one three away a third, since a word next door tells you more than a word at the far end. What comes out is a square table with a row and a column for each of the 31 words, and the row for a word is that word’s description.

row(w)[v] = how often v occurred within reach of w, discounted by how far

Two things about that table matter for the rest of the page. The first is that it works. Comparing two whole rows by the cosine between them gives 0.8558 on average for two words of the same list and exactly 0.0000 for a word of each, because two words from different lists have no neighbour in common at all and their rows are perpendicular. The second is its shape. It has 961 cells, 440 of which are zero, which is 45.8% of the table holding no information at all.

Thirty one words is too few to see the shape, though, and a corpus built to have two lists is too tidy to be believed about it. So the same counting is done below on the first three chapters of a real book, where the vocabulary is 364 words and nobody arranged anything. A row of that table is still a word’s description, and a description is a direction, so the honest picture is not the table but where the words end up.

Counting the book and fitting it…

The toggle is the rest of this page in one control. The same words are drawn twice, once from a row of 364 counts and once from a vector of 24 numbers that a fit produced, and the figure to watch is how much of the spread three directions can hold. For the counted rows it is 19.8%, so the picture is showing a fifth of what is there and the description really is as wide as it looks.

For the learned vectors it is 76.4%. The second description was small all along; the first was merely large.

The trouble with describing a word by a row of the counting table is that the row is as wide as the vocabulary. Thirty one words give a row of 31 numbers, and the whole table is 961; a vocabulary of forty thousand words, which is a modest one, gives a row of forty thousand and a table of 1.6 billion. The table grows as the square of the vocabulary while the number of distinct pairs that actually occur grows nothing like as fast, so the zeros take over.

The alternative is to fix the width in advance. Give every word twelve numbers whatever the vocabulary holds, and the whole description of this corpus is 372 numbers rather than 961, and the description of a forty-thousand-word vocabulary is 480,000 rather than 1.6 billion. That is only worth having if twelve numbers can carry what thirty one counts carried, and nothing suggests the counts themselves could be read back out of twelve numbers.

What has to survive the squeezing is the comparisons rather than the counts, so that words of one list still come out near each other and words of different lists still do not.

Word2vec does not squeeze the counting table. It asks a different question altogether, and the answer to that question is thrown away. The question is a prediction task that nobody wants the answer to. Given a word from the corpus, how likely is each other word to have appeared beside it? Set that up as a model with a vector per word, train it until it predicts neighbours reasonably well, then delete the prediction machinery and keep the vectors it needed in order to do the predicting.

The bet is that a model cannot predict which words appear beside walked without having discovered, somewhere in its weights, that walked keeps the same company as walking and none of the company of market. It never gets told there are two lists; it gets told, 19,519 separate times over five passes of this corpus, which word turned up beside which, and the only cheap way to be right about that is to give words with the same neighbours the same vector.

The corpus becomes training data by sliding a window along every sentence. At each position one word is the centre and the words within reach on either side are its context, and that pairing is one piece of training. Nothing more elaborate than that happens; there is no parse, no grammar, and no notion of which side a neighbour was on.

The widget below runs that on three short sentences, small enough to check by hand. The corpus is walk walked talks, bond market price, and walked talks walk, which is nine word occurrences over six distinct words, and it is here for the mechanics rather than for any vectors, since nine occurrences teach nothing.

…

At a reach of one those three sentences give twelve pieces of training one way round and nine the other, and the difference is the whole of Part 3. Widening the reach to two takes the first count to eighteen and leaves the second at nine.

Every word gets two vectors, not one. It has a vector for when it is the word being read, and a row for when it is the word being predicted, and a pair is scored by multiplying the two together coordinate by coordinate and adding up. That number is large and positive when the two vectors point the same way, large and negative when they point opposite ways, and the logistic function turns it into a probability between zero and one.

score = u · h        probability = 1 / (1 + exp(−score))

The training says the probability should be near one when the pair really did occur and near zero when it did not, which is ordinary logistic regression with the vectors playing both the weights and the input. The cost of one such judgement is the usual logarithm, and the step it asks for pushes the two vectors towards each other when they should agree and apart when they should not.

cost = −log(probability) when the pair occurred,  −log(1 − probability) when it did not

…

true pair probability = sigmoid(0.5) ≈ 0.622459
first sampled probability = sigmoid(−0.5) ≈ 0.377541
second sampled probability = sigmoid(0) = 0.5

true pair loss = −ln(0.622459) ≈ 0.474077
first sampled loss = −ln(1 − 0.377541) ≈ 0.474077
second sampled loss = −ln(1 − 0.5) ≈ 0.693147
total loss ≈ 0.474077 + 0.474077 + 0.693147 ≈ 1.641301

When the passes are over there are two tables of exactly the same size, 372 numbers each on this corpus. One holds a vector per word for when the word is read; the other holds a row per word for when the word is being predicted. The answer is the first table, and the second is deleted.

…

The right-hand column is the model doing the job it was actually trained for, and it does it. Asked which words belong beside walked, the discarded table names says, player, stays, stayed and walked itself, all of them verb forms, at probabilities between 0.28 and 0.31, while every word about money comes back far lower.

Averaged over the whole vocabulary its readiness to say a verb form appeared beside walked is 0.2672 and its readiness to say a word about money did is 0.0061, which is a working, if not very confident, predictor of neighbours. Half of everything the fit learned goes into it, and none of it is kept.

The first arrangement is skip-gram. Read the centre word’s vector, and use it to predict each of its context words in turn, one piece of training per neighbour. At a position with three words in its window the centre word’s vector is read three times, corrected three times, and each of the three neighbours has its row corrected once.

score for neighbour v of the centre w   =   u(v) · h(w)

The consequence worth carrying is arithmetical rather than linguistic. Every occurrence of a word produces as many pieces of training as it has neighbours, so a word that appears rarely still generates several corrections each time it appears, which is why skip-gram is the usual choice where the corpus is small and why it is the slower of the two arrangements.

The second arrangement runs the same window the other way. Average the vectors of all the context words into one vector, and use that average to predict the centre word. One piece of training per position, whatever the reach, and the correction the average receives is shared out equally among the words that went into it.

h = the mean of the context vectors        score = u(centre) · h

The averaging is where the name comes from, since a mean discards the order of what went into it, and it is also where the behaviour differs. A rare word in the context contributes one summand out of several and receives a share of one correction, which is a much weaker signal than the same word would get as a centre under skip-gram.

centre predicting each neighbour = (1 + 2 + 1) × 3 sentences = 12
neighbours predicting the centre = (1 + 1 + 1) × 3 sentences = 9

On this corpus the difference shows up first in the pair count. Skip-gram produces 3,968 pieces of training in a pass and the bag of words 1,311, exactly one per word occurrence, so the bag of words is doing about a third as much work. What it buys with the saving is worse separation at every setting the page tried.

…

Read the four bars at the doubled first step. Skip-gram with drawn wrong answers separates the lists by 0.8266 and the bag of words by 0.2813, which is the same ordering the counts predict, since the bag of words saw a third of the training. At the published first step, which Part 5 comes to, the same pair reads 0.7033 and 0.0034, and that second number is a fit that did not separate anything.

So far a pair has been scored against one row. Asking properly how likely each word is to be the neighbour means scoring the centre word against every row in the table and normalising, so the probabilities add to one across the vocabulary. That is the softmax, it is the honest version of the question, and its gradient touches every row in the table for every pair.

P(v | w) = exp(u(v) · h(w)) / Σ over every word v′ of exp(u(v′) · h(w))

On this corpus that means 31 rows per pair and 19,519 pairs across five passes, which is 605,089 row updates and no trouble at all. On a forty-thousand-word vocabulary the same five passes over a billion words means forty thousand rows touched at every one of five billion word positions, and the sum in the denominator has to be recomputed for each of them. The method is not slightly expensive at that size; it is the only thing the computer would ever do.

The first answer replaces the question “which of the thirty one words is the neighbour” with a much easier one. Take the word that really did appear, and take five words drawn at random, and ask of each of the six separately whether it is a real neighbour or a random word. That is six independent yes-or-no judgements, six rows touched, and the number six does not grow when the vocabulary does.

cost = −log σ(u(v) · h)  −  Σ over the k drawn words of log(1 − σ(u(v′) · h))

This is called negative sampling, and the drawn words are the negatives. What the model learns is no longer a distribution over the vocabulary, since the six probabilities do not add to anything in particular, and it does not need to be. What it needs is for the true neighbour’s row to be pulled towards the word and the random rows pushed away, repeated often enough that the pulls from words with shared company accumulate in one place.

How the negatives are drawn turns out to matter. Draw them in proportion to how often each word appears and nearly every negative is one of the commonest words, so the model spends its effort learning to say no to those. Draw them uniformly and a word seen seventeen times is offered as a wrong answer as often as one seen seventy three, which tells the model little about the words it actually meets.

Word2vec raises each count to the power three quarters before normalising, which sits between the two. The exponent has no derivation behind it; the paper reports it as the value that worked, and it has stayed.

share of the draw for word w  ∝  count(w) ^ 0.75

…

The second answer keeps the honest question and changes how the answer is reached. Arrange the words as the leaves of a binary tree, and reaching a word becomes a sequence of left-or-right choices, one at each branch point on the way down. Give every branch point its own row, ask it the same yes-or-no question the pairs were asked before, and the probability of a word is the product of the probabilities along its path.

P(v | w) = Π over the branch points on v’s path of σ(±  u(node) · h(w))

The probabilities of all the words still add to one, because the probabilities at every branch point add to one and the paths partition the leaves, so nothing has been approximated. What has changed is that the number of rows touched is the length of one path rather than the size of the vocabulary. Any binary tree works; the shape decides the cost, and word2vec uses Huffman’s arrangement, which gives frequent words the short paths and is the arrangement with the smallest average path length there is.

…

On the corpus this page uses, the tree saves almost nothing, and it is worth saying so plainly rather than quoting the logarithm and moving on. Thirty one words give an average path of 4.9008 branch points against a sweep of 31, so the saving is a factor of about six, and against the six rows negative sampling touches it is a saving of about one row.

The second disappointment is that Huffman’s arrangement is barely earning its keep here either. Its average path is 4.9008 where a tree that ignored the counts entirely and split evenly would cost 4.9542, a difference of five hundredths of a branch point, because the counts on this corpus run from 73 down to 17 and there is no long tail of rare words to give long paths to.

Give the same construction counts that fall as one over the rank, which is roughly how word counts really fall, and at forty thousand words the average path is 10.7469 against the balanced tree’s 15.2877.

A fit is a number of passes over the corpus, and after each one the mean cost of a training pair is recorded. That number is the only thing the fit itself knows about how it is doing, and it is a strange quantity, since under negative sampling it depends on which words happened to be drawn as negatives and is therefore not comparable between two runs that drew differently.

The playground at the top of the page draws that curve for whatever settings are chosen, and the useful habit is to watch the shape rather than the value. A curve that does not fall is a step size too large; a curve that falls and flattens immediately, as this one does, usually means the corpus is small enough that the model has learned everything available in a pass or two.

The step size starts at a stated value and falls linearly towards a floor across every position of every pass, so the first corrections are large and the last are tiny. The value the original program ships with is 0.025, and on this corpus one of the four arrangements does not work at that value.

Fitted at 0.025 with the bag of words and drawn wrong answers, five passes leave the two lists at 0.9907 within a list and 0.9873 across the two, a difference of 0.0034. Every vector points very nearly the same way as every other, which is the state a fit starts in and has barely left, and the nearest words to market come back as trade, stock, cash, bond and stays, with a verb form fifth.

Doubling the step size to 0.05 takes the same arrangement to 0.9929 and 0.7116, a difference of 0.2813, and the verb form is gone from the list.

This is worth dwelling on because it is a published default producing a result that looks like a working fit. Nothing raises, the cost curve falls from 4.1568 to 2.8830, and the nearest-word list for a verb form is full of verb forms. It is only the second number, how alike two words from different lists came out, that says the fit answered the same thing for everything.

The default is not wrong; it was chosen for corpora of billions of words, where five passes is tens of billions of corrections and a small first step is plenty.

Two directions and two ways round the softmax make four arrangements, and they are genuinely four methods rather than four settings. Compare them on the same corpus at the same width, reach, passes and start, and the first thing to notice is that the numbers are not on a common scale.

The two tree fits report negative cosines across the lists, −0.5570 and −0.9618, where the two negative sampling fits report positive ones, 0.1696 and 0.7116. That is not the tree separating the lists four times better; it is a different geometry. Every branch point is trained to say one thing for the words that go left of it and the opposite for the words that go right, so words on different sides of the root are pushed to opposite ends of one direction; drawn wrong answers only ever push a pair towards being unrelated, which is an angle near ninety degrees rather than near a hundred and eighty.

…

What can be compared is whether the lists came apart, and at the doubled step all four separate them. What can also be compared is the nearest-word lists, and there the four agree on the answer to the question anybody would ask and disagree on everything else. Asked for the five words nearest walked, all four return five verb forms and no word about money; between them they name ten different words, and only one word, talking, appears in all four lists.

Four things in the fit are random, namely where every vector starts, how far the window reaches at each position, which words are drawn as negatives, and which occurrences of frequent words are thinned out. One seed fixes all four, so two fits from the same seed are identical to the last bit, and two fits from different seeds are two different answers.

…

The twelve coordinates of walked from the two starts have nothing in common. Across the whole table the mean gap coordinate by coordinate is 0.7816 and the largest single gap is 2.5336, which is larger than most of the coordinates themselves. Yet the cosine between any two words comes out almost the same in both, with the two runs’ lists of pairwise similarities correlating at 0.9996 and differing by 0.0073 on average.

The training cost is the number of pieces of training times the number of rows each touches. Five passes of skip-gram over this corpus is 19,519 pairs, each touching one word vector and six rows under drawn wrong answers, so 136,633 row corrections. The bag of words makes 1,311 pairs a pass, so 6,555 across five, though each of those corrects every word in its window rather than one.

The storage cost is two tables of one row per word, which is 744 numbers here, of which 372 are kept. That is the number to compare against the counting table’s 961 cells, and on this corpus the saving is modest, since twelve is not much smaller than thirty one. The comparison is worth making anyway, because both numbers are exact and both scale in known ways, one as the square of the vocabulary and the other as twelve times it.

On this corpus, plain counting beats word2vec, and hiding that would misrepresent what the method is for. Two rows of the counting table compared directly give 0.8558 within a list and exactly 0.0000 across the two, which is a perfect separation reached in one pass with nothing to tune, no random start and no seed. The best of the four word2vec arrangements at the doubled step gives 0.9962 and 0.1696, which separates the lists and does not separate them cleanly.

The zero is not luck. Two words from different lists never share a sentence, so they share no neighbour, so their count rows have no coordinate nonzero in both and the cosine between them is exactly zero by construction. Word2vec cannot reach that, because its vectors are twelve numbers rather than thirty one and it is not trying to reproduce the rows at all.

The fit lowers the cost of predicting neighbours. Nobody wants a neighbour predicted, and no quantity computed during the fit says anything about whether the vectors are good. That is not a gap in any particular implementation; it follows from the method being defined as an optimisation of one thing and used for another, and it means the two can move in opposite directions without anything being wrong.

…

Measured on this corpus, they do. Going from five passes to ten to twenty, the mean cost per pair falls at every step, 2.0872 to 2.0617 to 2.0267, exactly as the fit intends. The separation of the two lists rises to 0.8404 at ten passes and then falls back to 0.7397 at twenty, and the mean cosine within a list falls from 0.9962 to 0.8510, so the verb forms are coming apart from each other while the objective keeps improving.

A reader watching only the cost curve would have concluded that twenty passes was better than ten.

The objective is not convex, and the walk that lowers it is a stochastic one that visits pairs in an order the draws decide. So a fit arrives at a local answer, and a different start arrives at a different local answer, and neither is more correct than the other. There is nothing in the method that would distinguish them.

Worse for anyone hoping to compare two fits, the objective is invariant to a whole family of transformations of the answer. Rotate every vector in the kept table and every row in the discarded table by the same rotation and every dot product is unchanged, so the cost is unchanged, so the rotated answer is exactly as good.

The coordinates therefore have no meaning individually, and the fifth coordinate of one run has no relation whatever to the fifth coordinate of another. Measured on the two starts of Part 5, the mean gap coordinate by coordinate is 0.7816 while the pairwise cosines agree to 0.0073.

A word’s vector is the accumulation of the corrections its occurrences produced. A word that occurs twice produces corrections from two windows, and everything else about where it ends up is where it started, which was a draw. There is no amount of further training that repairs this, since further training visits the same two windows again.

…

Put a made-up word into two sentences of the corpus and fit four times from four starts. How alike it comes out to walked is 0.8790, 0.9591, 0.9448 and 0.9532, a spread of 0.0801, while the same comparison for walk, which appears 42 times, spreads by 0.0025 across the same four starts, thirty one times narrower. The three words the rare one lands nearest change from run to run, naming played first once, saying twice and say once.

Nothing in the answer marks the difference. The rare word gets a vector of the same twelve numbers, and a cosine against it comes back to four decimal places like any other. The usual response is a minimum count, which declines to answer for a rare word rather than answering it better, and where the threshold goes is a judgement rather than a fact. Below it a word has no vector, and it is also removed from the sentences before the windows are formed, so the words on either side of it become neighbours.

Several inputs leave word2vec 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.