Study guide · Language models & AI · 2013

Efficient Estimation of Word Representations in Vector Space

Tomas Mikolov, Kai Chen, Greg Corrado, Jeffrey Dean · ICLR 2013 workshop

Can a computer learn what words mean just by reading a lot of text, cheaply enough to read billions of words in a day? Mikolov and colleagues strip neural language models down to almost nothing and show that the word vectors they learn line up so neatly that "Paris minus France plus Italy" lands near "Rome".

The paper in four sentences

A computer can represent each word as a list of a few hundred numbers, a point in a high-dimensional space, so that words used in similar ways end up close together.

Earlier neural networks learned such lists, but slowly, because they did a lot of expensive work on every word they read.

This paper throws away the expensive middle layer and trains two very simple models: one guesses a word from its neighbours (CBOW), the other guesses the neighbours from a word (skip-gram).

These cheap models are fast: CBOW read 1.6 billion words in under a day (skip-gram took about two), and their vectors capture relationships: the step from "man" to "woman" is roughly the same as the step from "king" to "queen".

Idea · §1

Words as points on a map

To a computer, a word is just a string of letters. "Cat" and "kitten" look no more related than "cat" and "carburettor". The simplest fix, giving each word its own ID number, keeps that blindness: every word is equally different from every other.

A better idea is to give each word a vector: a list of numbers, say 300 of them, which you can think of as coordinates of a point in a space with 300 directions. If similar words get nearby points, then a system that has learned something about "cat" automatically knows a little about "kitten". These are called word vectors or word embeddings.

Where do the numbers come from? From an old observation in linguistics: you can tell a lot about a word from the company it keeps. Words that appear in similar sentences ("I fed the ___", "the ___ purred") probably mean similar things. So the computer reads huge amounts of text and adjusts each word's numbers until words that share contexts share neighbourhoods.

Everyday pictureA supermarket. Nobody gives the shop a definition of "pasta", but it ends up shelved near rice and sauces because people buy them together. Its location tells you what kind of thing it is.

TakeawayA word vector places each word as a point in space, learned from which words it appears near, so that similar words sit close together.

Check yourself
Why are plain word ID numbers a poor representation?
They carry no notion of similarity: word 412 and word 413 are no more alike than word 412 and word 9,000, so nothing learned about one word transfers to another.

Idea · §3 · Fig. 1

Two very simple guessing games

The networks people used before this paper to learn word vectors were full language models: they read the previous few words and tried to predict the next one, passing everything through a large "hidden layer" of artificial neurons. That hidden layer was where most of the computing time went.

Mikolov and colleagues ask: what if we only care about the word vectors, not about building a good predictor? Then the hidden layer can go. They propose two stripped-down games.

  • CBOW ("continuous bag of words"): take the words around a gap, average their vectors, and guess the missing middle word. "Bag of words" means the order of the neighbours is ignored.
  • Skip-gram: the reverse. Take one word and guess each of the words around it.

Each time a guess is wrong, the vectors involved are nudged slightly so the right answer becomes more likely next time. Over billions of guesses, words that appear in similar company get similar vectors. Below, step a skip-gram window along a sentence and watch which training examples it produces.

The amber word is the input; the blue words inside the window are the ones it must guess. As in the paper (§3.2), the window size for each word is drawn at random between 1 and C, so close neighbours are used more often than distant ones. The small bars underneath show that chance for each distance: a word k places away is used with probability (C − k + 1) / C.

TakeawayCBOW guesses a word from its neighbours; skip-gram guesses the neighbours from a word. Both drop the costly hidden layer of earlier models.

Check yourself
In skip-gram with a window of 2 on each side, how many guesses does one word in the middle of a sentence produce?
Four: two words to the left and two to the right, each a separate guess.
Why would anyone want to give up the hidden layer?
It was the main computing cost. Without it, training is fast enough to read billions of words, and more data improves the vectors more than the hidden layer did.

Idea · §4.1 · Table 1

Meaning as directions you can add

The surprising part is not just that similar words cluster. The direction from one word to another seems to carry meaning. The arrow from "France" to "Paris" points roughly the same way as the arrow from "Italy" to "Rome": it is a "capital of" direction. So you can do arithmetic: start at Paris, subtract France, add Italy, and look up which word is nearest to where you land.

The authors turn this into a test. They built about 8,900 "semantic" questions (capitals, currencies, family relations) and about 10,700 "syntactic" ones (big to biggest, walk to walked, mouse to mice). A question counts as correct only if the nearest word is exactly the expected one. The words in the question itself are not allowed as answers, a detail that matters more than it looks.

Try it on a toy map below. The positions are hand-placed to illustrate the idea in two dimensions; real word vectors have hundreds.

"A is to B as C is to ?" is answered by B − A + C (the dashed arrows copy the A→B step onto C). The ring marks where the arithmetic lands; the nearest word is the answer. Click any three words in order to make your own question. Untick the box to see how often the nearest word would simply be one of the question words, which is why the paper excludes them.
Everyday pictureGiving directions on a city grid. "From the station, two blocks north is the library." If the same "two blocks north" from the town hall lands at the court house, then "two blocks north" means something consistent, like "the civic building behind it".

TakeawayIn good word vectors, consistent relationships become consistent directions, so analogies can be solved by adding and subtracting vectors.

Check yourself
Write the arithmetic for "walking is to walked as swimming is to ?".
vector(walked) − vector(walking) + vector(swimming), then find the nearest word, hoping for "swam".
Why are the question words excluded from the answers?
The arithmetic often lands closest to one of the words you started with (especially C), so without the rule many questions would be "answered" with an input word.

Idea · §4.2–4.4 · Tables 2–6

Cheap models plus lots of text win

The big result is a trade. The simple models are a little less clever per word read, but they are so much cheaper that they can read far more, and reading more helps a lot. In the paper's tests, accuracy on the analogy questions keeps rising when the vectors get bigger and the training text gets longer, as long as both grow together (Table 2).

Trained on 783 million words with 300 numbers per word, skip-gram answered about 53% of the analogy questions exactly right. Older publicly available word vectors scored between 2% and 25% on the same test (Table 4). On a cluster of computers, using a Google News collection of about 6 billion words, the best skip-gram reached about 66% while training in roughly 2.5 days (Table 6). CBOW processed 1.6 billion words in under a day; skip-gram took about two days.

The two models also differ in character: skip-gram was much better on meaning-type questions (capitals, family), CBOW a bit better on grammar-type questions (plurals, tenses), and CBOW trains faster.

TakeawaySimple models that can read billions of words beat clever models that can only read millions.

Check yourself
Why is "53% correct" more impressive than it sounds?
Only an exact match counts, among a vocabulary of many thousands of words; near-synonyms or slight variants count as wrong.

Idea · §6–7 · What came next

From fixed vectors to words in context

Months later the same team published a follow-up that made skip-gram faster and better still, with a trick called negative sampling (instead of scoring every word in the vocabulary, compare the right neighbour against a handful of random ones) and by skipping some very common words like "the". They released the program as word2vec, and it became one of the most used tools in language processing.

Word2vec's vectors have a basic limitation: each word gets exactly one point, whatever it means in context. "Bank" in "river bank" and "bank account" share one vector. Later models such as BERT solved this by computing a fresh vector for each word every time it appears, based on the whole sentence. The idea of learning meaning from neighbouring words survives in them; the single fixed vector per word does not.

Later refinementThe "king − man + woman = queen" magic is partly an artefact of the test. Later researchers showed that without the rule excluding the question words, the nearest vector is often just one of the inputs, and that the analogies are less reliable than the famous examples suggest. Word vectors also absorb social biases from their training text (the same arithmetic produces stereotypes).

TakeawayWord2vec made good word vectors cheap and popular; modern models keep the idea of learning from context but give each word a different vector in each sentence.

Check yourself
What can a single vector per word not capture?
Different meanings of the same word in different contexts, like "bank" (river) versus "bank" (money).

Follow the idea

Led to: BERT (2018)