Distributed Representations of Words and Phrases and their Compositionality

Subsampling of frequent words (2–10× faster training and better vectors for rare words), negative sampling as a simple alternative to hierarchical softmax, and a data-driven method to find phrases and learn vectors for millions of them, plus the observation that vectors compose by addition.

Unlike earlier neural architectures for word vectors, it involves no dense matrix multiplications (no hidden non-linear layer); an optimized single-machine implementation could train on more than 100 billion words a day.

Many relations are approximately constant vector offsets: vec(“Madrid”) − vec(“Spain”) + vec(“France”) is closer to vec(“Paris”) than to any other word vector.

Some phrases aren’t compositions of their words’ meanings: “Boston Globe” is a newspaper, not a combination of Boston and Globe, and “Air Canada” isn’t Air + Canada. Representing such phrases by their own vectors makes the model more expressive.

Maximize the average log probability of the words around each word: \(\frac{1}{T} \sum_{t=1}^{T} \sum_{-c \le j \le c,\, j \ne 0} \log p(w_{t+j} \mid w_t)\), where \(c\) is the context size. Larger \(c\) gives more training examples and can improve accuracy, at the cost of training time.

With a softmax over the vocabulary: \(p(w_O \mid w_I) = \frac{\exp(v'^\top_{w_O} v_{w_I})}{\sum_{w=1}^{W} \exp(v'^\top_w v_{w_I})}\), with separate input vectors \(v_w\) and output vectors \(v'_w\). The gradient cost is proportional to the vocabulary size \(W\), often \(10^5\)–\(10^7\).

Words are leaves of a binary tree; each inner node has a vector \(v'_n\), and \(p(w \mid w_I)\) is the product, along the path from the root to \(w\), of \(\sigma(\pm v'^\top_n v_{w_I})\) for going left or right. It costs about \(\log_2 W\) instead of \(W\) per word, and the probabilities sum to 1.

It gives frequent words short codes (short paths), so training is fast. The tree’s structure considerably affects both speed and accuracy.

Replace each \(\log p(w_O \mid w_I)\) with \(\log \sigma(v'^\top_{w_O} v_{w_I}) + \sum_{i=1}^{k} \mathbb{E}_{w_i \sim P_n(w)} \log \sigma(-v'^\top_{w_i} v_{w_I})\): logistic regression distinguishing the real context word from \(k\) words sampled from a noise distribution.

NCE needs both noise samples and their numerical probabilities, and approximately maximizes the softmax log probability. NEG uses only samples and doesn’t approximate the softmax, which is fine since the goal is good vectors, not a language model.

\(k\) = 5–20 for small data sets, 2–5 for large ones. The unigram distribution raised to the 3/4 power, \(U(w)^{3/4}/Z\), significantly beat both the plain unigram and the uniform distribution.

Each occurrence of word \(w_i\) is discarded with probability \(P(w_i) = 1 - \sqrt{t / f(w_i)}\), where \(f\) is its frequency and \(t \approx 10^{-5}\). Frequent words like the carry little information (seeing France with Paris helps more than with the) and their vectors stop changing after millions of examples.

It aggressively subsamples words with frequency above \(t\) while keeping the frequency ranking. It sped training up several times and significantly improved vectors of rarer words.

For “Germany : Berlin :: France : ?”, find the word whose vector is closest by cosine to vec(“Berlin”) − vec(“Germany”) + vec(“France”), excluding the input words; it is correct only if it is Paris. Questions are syntactic (quick : quickly :: slow : slowly) or semantic (country–capital).

With 300-dimensional vectors on 1B words of news: NEG-15 61%, NEG-5 59%, NCE-5 53%, hierarchical softmax 47% total accuracy. With \(10^{-5}\) subsampling, training got 2–3× faster and accuracy rose (NEG-15 61%, NEG-5 60%, HS 55%).

Probably not: earlier work found that highly non-linear recurrent network language models also improve on analogies as training data grows, suggesting non-linear models also prefer a linear structure of word representations.

Score bigrams by \(\text{score}(w_i, w_j) = \frac{\text{count}(w_i w_j) - \delta}{\text{count}(w_i) \times \text{count}(w_j)}\); bigrams above a threshold become single tokens (“New York Times”, “Toronto Maple Leafs”, but not “this is”). The discount \(\delta\) prevents phrases of very rare words. 2–4 passes with decreasing thresholds form longer phrases.

With a new phrase analogy test set (3218 questions in five categories, e.g. newspapers, NHL teams, airlines, company executives): “Montreal : Montreal Canadiens :: Toronto : ?” should give “Toronto Maple Leafs”.

On 1B words: NEG-15 beat NEG-5, and hierarchical softmax, worst without subsampling, became best with it (47%). With 33B words, hierarchical softmax, 1000 dimensions and whole-sentence context, accuracy reached 72%; 6B words gave 66%, so data size is crucial.

Element-wise addition of word vectors often gives meaningful results: vec(“Russian”) + vec(“river”) is close to vec(“Volga River”), vec(“Vietnam”) + vec(“capital”) to vec(“Hanoi”), vec(“German”) + vec(“airlines”) to vec(“Lufthansa”).

Word vectors are trained to predict context, so they represent a word’s context distribution, related logarithmically to the output probabilities. Summing two vectors corresponds to multiplying the two context distributions, an AND: words likely in both contexts (e.g. “Volga River” near both Russian and river) score high.

Its nearest neighbours for rare words (e.g. ninjutsu → ninja, martial arts; capitulate → capitulation, capitulated) were far better than those of Collobert & Weston, Turian et al. and Mnih & Hinton, partly because it was trained on about 30B words, two to three orders of magnitude more, in a fraction of the time.

The model architecture (Skip-gram vs CBOW), vector size, subsampling rate and training window size. The best choices are task-specific. Negative sampling learns especially good vectors for frequent words; hierarchical softmax with subsampling did best for rare phrases.