word2vec's most famous demo predates word2vec

The cost word2vec was built to cut

Before 2013, the strongest word-vector models ran every prediction through a nonlinear hidden layer. A language model read a window of context words, mixed them together in a layer that squashed the combination nonlinearly, and only then predicted a word. That layer gave the older neural language models their expressive power, and it is also what made them slow to train on more than a few hundred million words at a time.¹

Mikolov, Chen, Corrado, and Dean's answer was to remove it. Continuous bag-of-words (CBOW) predicts a word from the words around it. Skip-gram runs the same idea backward, predicting the surrounding words from one word in the middle. Neither model passes its input through anything nonlinear, so a training step costs a sum and a lookup instead of a matrix mixture. The paper states the saving as a formula: CBOW costs N·D + D·log₂(V) per training example, and skip-gram costs C·(D + D·log₂(V)). D is the vector size and V the vocabulary. The older, nonlinear language models added a much larger term instead.¹

On identical training data and vector size, the paper's own comparison shows what removing that layer bought.¹

Turned loose on more data, skip-gram's best reported run reached 52.2% semantic and 55.1% syntactic accuracy on the paper's own 19,544-question test. That run used 300 dimensions, trained on 1.6 billion words drawn from a 6-billion-token Google News corpus, with the vocabulary capped at the million most frequent words.¹ Google never released that training corpus or the resulting vectors. Every accuracy figure attached to it is the number Mikolov and coauthors reported, not a number anyone outside Google has independently reproduced on the same data.¹

Scoring every word was still too slow

Removing the hidden layer fixed one cost. It left another standing: both models still trained by ranking the correct next word against every other word in the vocabulary, a full softmax over hundreds of thousands of candidates at each step. On a billion-word corpus, that ranking is more of the same expense the paper had just spent its effort cutting.²

So what happens when the vocabulary the model has to score, at every single step of training, runs past a million words? Mikolov, Sutskever, Chen, Corrado, and Dean's companion paper, published nine months after the first, answered by not scoring the vocabulary at all.²

Negative sampling trains the model to tell the true neighbor apart from a handful of words drawn at random, rather than ranking it above every word in the language. Picture a five-word toy vocabulary: cat, dog, ran, fast, moon, and a training pair (ran, fast). Negative sampling does not ask the model to rank fast above cat, dog, and moon all at once. It asks a few small yes-or-no questions instead: is fast the right neighbor for ran (yes), is moon (no), is cat (no), is dog (no). The paper recommends drawing five to twenty such negative words for a small corpus, and as few as two to five for a large one.² Multiply the toy example by a real vocabulary, and a training step costs a handful of comparisons instead of one comparison per word in the language.

Where King − Man + Woman = Queen actually comes from

The sentence that made “Efficient Estimation” famous sits early, in the paper's own statement of its goals. It reads: “Using a word offset technique where simple algebraic operations are performed on the word vectors, it was shown for example that vector('King') − vector('Man') + vector('Woman') results in a vector that is closest to the vector representation of the word Queen.”¹ That sentence carries a citation, numbered [20], to a different paper: Mikolov, Yih, and Zweig, “Linguistic Regularities in Continuous Space Word Representations.”³

That earlier paper, not the one this piece opened with, is where the vector-offset method and the King/Queen example both originate. Its vectors come from a recurrent neural network language model, the same family of architecture “Efficient Estimation” was built to replace. It trained on 320 million words of Broadcast News transcripts with an 82,000-word vocabulary, roughly a tenth the data of the Google News runs that made skip-gram's own numbers. On its own 8,000-question syntactic test, the best RNN model reported 39.6% accuracy.³

“Efficient Estimation” adopted the offset idea and reran it, at far larger scale, on the two new architectures the paper actually introduces. The popular account credits CBOW and skip-gram with discovering that word vectors encode analogies through direction and distance in vector space. The offset technique itself credits an earlier, smaller, differently built model, in a bracketed citation most retellings of the story drop.

Why the search never considers King, Man, or Woman

Picture the vectors for King, Man, Woman, and Queen as four points in a high-dimensional space. The offset technique computes a new point, X = vector(King) − vector(Man) + vector(Woman). It then asks which word's vector sits closest to X by the angle between them, cosine distance rather than straight-line distance. Word2vec's own paper adds one more step, stated plainly in its results section: “we discard the input question words during this search.”¹ King, Man, and Woman are not allowed to be the answer to a question that already contains them.

Levy and Goldberg's 2014 paper gave that rule a name and a formal definition, 3CosAdd: the highest-cosine word in a vocabulary V that specifically excludes the three question words, a, a*, and b.⁴ They also showed the formula rearranges, once vectors are unit length, into cos(b*,b) − cos(b*,a) + cos(b*,a*). That is the candidate word's similarity to Queen, minus its similarity to Man, plus its similarity to Woman. Read that way, an analogy answer is three ordinary similarity scores added together. The term with the largest raw similarity can swamp the other two. London:England :: Baghdad:? answers “Mosul” under 3CosAdd, because Mosul sits close to Baghdad geographically and that one term dominates the sum. The actual answer, Iraq, only wins once the three terms are multiplied instead of added, the fix Levy and Goldberg call 3CosMul.⁴

Which formula runs the search changes which kind of vector looks smarter, not just by how much it wins but by whether it wins at all. The comparison below runs on the same Wikipedia corpus, the same skip-gram embeddings, and the GOOGLE test set: 19,258 of its original 19,544 questions, after removing entries with out-of-vocabulary words. An older count-based representation trails badly under 3CosAdd and comes out ahead under 3CosMul.⁴

Levy and Goldberg add one further complication neither 2013 paper discloses. On the semantic half of Mikolov and coauthors' own published evaluation, the answers were actually scored with a different formula, PAIR_DIRECTION, not 3CosAdd. Levy and Goldberg say they confirmed that by corresponding with the original authors, not by reading it in the published text.⁴ That detail rests on one paper's account of a conversation, not on anything either 2013 paper states in print.

Turn off the exclusion and the analogy falls apart

Tal Linzen tested what the search finds without that rule, training his own skip-gram-with-negative-sampling spaces and running the raw, unconstrained version of the offset method: search the entire vocabulary, King, Man, and Woman included.⁵

Broken down, the nearest neighbor to X was Woman, the input word itself, in 93% of cases, and King, the other input word, in another 5%. It was never Man.⁵ In word2vec's own famous example, the unconstrained search's top guess for King − Man + Woman is Woman, not Queen, because the input word already sitting in the search is, geometrically, the closest point to X there is. The exclusion rule is not a footnote to the offset technique. It is most of what makes the technique look correct at all.

Nissim, van Noord, and van der Goot ran the same test on the actual, publicly distributed GoogleNews vectors, the ones millions of people have downloaded and used. They found the same collapse. Macro-accuracy under 3CosAdd fell from 0.71 with the exclusion enforced to 0.21 without it, and macro-accuracy under 3CosMul fell from 0.73 to 0.45.⁶ In most of the failures, the model's answer was simply the second input word handed back to the questioner.⁶

The same rule shapes a debate well outside the analogy literature. A bias analysis asking “man is to doctor as woman is to X” can never return “doctor” as X. That holds whatever the embedding actually encodes, because the code running the search has already ruled the input words out. Nissim and coauthors point out that the constraint is documented, in word2vec's own paper and in several papers that followed it, and still is not common knowledge among people running the test.⁶

The count hiding inside skip-gram

Negative sampling is a training shortcut, not an explanation of what the resulting vectors mean. Omer Levy and Yoav Goldberg went looking for one, in a separate paper, and found that skip-gram with negative sampling is, under the right conditions, doing something with a much older name: counting.⁷

Consider a large enough vector dimension, one big enough to let the model fit every word-context pair's target value exactly. At that size, the objective skip-gram with negative sampling optimizes has an exact solution, and that solution is not arbitrary.⁷ It equals a quantity computed straight from word co-occurrence counts in the training corpus, shifted by a constant fixed by how many negative samples the model draws:

Pointwise mutual information is an old idea in distributional semantics, nothing more exotic than a ratio of counts. Levy and Goldberg's theorem says the vectors skip-gram spends its training budget arriving at are, at the mathematical optimum, a compressed encoding of that same ratio, for every word and context in the corpus at once.⁷

The theorem carries a condition the paper states itself. It holds exactly only when the dimension is large enough to reconstruct the full word-context matrix without loss, a condition real, low-dimensional word vectors do not meet. On the analogy task specifically, trained skip-gram clears an exact factorization of that same matrix by the paper's own correlation measure: 0.627 against 0.448 on the syntactic analogy set.⁷ The paper offers a conjecture for why, not a proof. Skip-gram's training weighs frequent word pairs more heavily than rare ones. An exact factorization of the matrix treats every pair the same.⁷

The picture of King, Man, Woman, and Queen as four points whose distances and directions can be read off directly still holds for describing what the search finds. It stops explaining why skip-gram's particular arrangement of those points beats a matrix built to hit the identical target on the analogy task. That gap stays open in the very paper that proved the two were connected in the first place.

What word2vec actually established

Word2vec's practical case rests on more than the King-Queen demo. Marco Baroni, Georgiana Dinu, and German Kruszewski ran an independent, much larger test in 2014. They trained 36 traditional count-based vector configurations against 48 predict-based ones, word2vec and its relatives among them, all on the same 2.8-billion-word corpus, and scored each across 14 separate tasks. Predict models won 13 of the 14, often by a wide margin, and the authors, who expected the older count methods to hold up, called the result a “thorough and resounding victory.”⁸

Levy and Goldberg's CoNLL paper, published the same year, complicates that victory rather than confirming it. Their own head-to-head, run on a shared corpus, put 3CosMul-scored count vectors essentially tied with skip-gram. On the GOOGLE analogy set specifically, count vectors even edged ahead, 68.24% to 66.72%. The paper says so directly: the result runs “contrary to the recent findings of Baroni et al. (2014).”⁴ Two papers, the same year, reached opposite conclusions from the same kind of test.

Levy, Goldberg, and Dagan's 2015 paper is often read as the resolution. Word2vec's own tooling popularized a set of hyperparameters: context distribution smoothing, dynamically sized windows, and more. Port those into the older count-based pipeline on equal terms, and “there is no consistent advantage to one algorithmic approach over another.”⁹ That is a careful, controlled result, and it is also the same two authors' account of a dispute they were already one side of. No outside group has run the adjudicating fourth experiment.