Source-linked AI summary
Distributed Representations of Words and Phrases and their Compositionality
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, Jeffrey Dean
TL;DR
Word representations struggle with idiomatic phrases and efficient training at vocabulary scale. The paper extends Skip-gram with subsampling, negative sampling, and phrase representations, yielding faster training and improved word and phrase representations.
Problem
Word representations cannot naturally capture idiomatic phrases, while standard Skip-gram training is impractical when computation scales with large vocabularies.
Method
The paper extends Skip-gram with frequent-word subsampling, simplified negative sampling, and a method for learning vector representations of multiword phrases.
Results
The extensions produce faster training and more accurate representations, while phrase models reach 72% accuracy on phrase analogies with 33 billion training words.
Takeaways & Limitations
Skip-gram can learn high-quality word and phrase representations at large scale, supporting precise analogical reasoning and improved coverage of rare entities.
Takeaways & Limitations
The original softmax formulation is impractical because computing its gradient costs proportionally to the vocabulary size.
Abstract
from arXiv · showhide
The recently introduced continuous Skip-gram model is an efficient method for learning high-quality distributed vector representations that capture a large number of precise syntactic and semantic word relationships. In this paper we present several extensions that improve both the quality of the vectors and the training speed. By subsampling of the frequent words we obtain significant speedup and also learn more regular word representations. We also describe a simple alternative to the hierarchical softmax called negative sampling. An inherent limitation of word representations is their indifference to word order and their inability to represent idiomatic phrases. For example, the meanings of "Canada" and "Air" cannot be easily combined to obtain "Air Canada". Motivated by this example, we present a simple method for finding phrases in text, and show that learning good vector representations for millions of phrases is possible.
1 Introduction
The paper extends Skip-gram to improve training speed and vector quality, while addressing limitations in representing idiomatic phrases through phrase-level tokens. It also highlights linguistic regularities captured by vector arithmetic, including analogies and compositionality.
- Skip-gram extensions: Skip-gram efficiently learns high-quality word vectors from large unstructured text because its training avoids dense matrix multiplications.An optimized single-machine implementation can train on more than 100 billion words.
- Vector regularities: Word vectors encode linguistic regularities as linear translations, exemplified by vec(“Madrid”) - vec(“Spain”) + vec(“France”) being closest to vec(“Paris”).The calculation is closer to vec(“Paris”) than to any other word vector.
- Skip-gram extensions: Subsampling frequent words yields a 2x - 10x speedup and improves the accuracy of representations for less frequent words.The paper also introduces a simplified Noise Contrastive Estimation variant for faster training and better representations of frequent words.
- Phrase representations: Phrase vectors make Skip-gram more expressive by representing idiomatic phrases whose meanings cannot be composed naturally from their individual words.The paper uses “Boston Globe” as an example of a phrase that is not a natural combination of “Boston” and “Globe.”
- Phrase representations: The phrase-based extension identifies phrases data-dependently, trains on them as individual tokens, and evaluates them with word-and-phrase analogy tasks.A typical analogy is “Montreal”:“Montreal Canadiens”::“Toronto”:“Toronto Maple Leafs”.
- Compositionality: Simple vector addition can produce meaningful phrase-like results, such as vec(“Russia”) + vec(“river”) approximating vec(“Volga River”).Another example is vec(“Germany”) + vec(“capital”) being close to vec(“Berlin”).
2 The Skip-gram Model
The Skip-gram model learns word representations by predicting surrounding words, with larger contexts improving accuracy at the cost of training time. Hierarchical softmax, negative sampling, and subsampling make training more efficient while preserving or improving vector quality.
- Training objective: Skip-gram learns word representations by maximizing the average log probability of surrounding words given each center word.The training objective predicts context words in a sentence or document.
- Training objective: Larger context size c provides more training examples and can improve accuracy, but increases training time.
- Efficient training: The standard softmax is impractical because computing ∇log p(wO|wI) costs O(W), with vocabularies often containing 10^5–10^7 terms.
- Efficient training: Hierarchical softmax reduces evaluation from W output nodes to about log2(W) nodes using a binary tree, and Huffman coding gives frequent words shorter paths for faster training.The model uses one representation per word and one per inner tree node.
- Efficient training: Negative sampling replaces each log P(wO|wI) term with logistic discrimination of the target word against k noise samples.Useful k values are 5–20 for small datasets and 2–5 for large datasets.
- Efficient training: The unigram noise distribution raised to the 3/4 power outperformed unigram and uniform distributions for both NCE and negative sampling on every tested task.
- Subsampling: Subsampling frequent words, typically with threshold t around 10^-5, accelerates learning and significantly improves rare-word vector accuracy.The method aggressively discards words more frequent than t while preserving frequency rankings.
3 Empirical Results
The section evaluates Skip-gram training methods on a word analogy task using a one-billion-word news dataset. Negative Sampling outperforms Hierarchical Softmax on this task, while prior results suggest that even nonlinear models can learn linearly structured word representations.
- Evaluation setup: The evaluation compares Hierarchical Softmax, Noise Contrastive Estimation, Negative Sampling, and word subsampling on analogical reasoning.Analogies are solved by finding the word vector closest to vec(“Berlin”) - vec(“Germany”) + vec(“France”) under cosine distance, excluding input words.
- Model comparison: Negative Sampling outperforms Hierarchical Softmax on the word analogy task.Models were trained on one billion news-article words after removing words occurring fewer than five times, leaving a 692K-word vocabulary.
- Interpretation: Prior results indicate that nonlinear recurrent neural networks also improve on analogical reasoning as training data increases, suggesting a preference for linear word-representation structure.This interpretation is presented alongside the argument that Skip-gram’s linearity suits linear analogical reasoning.
4 Learning Phrases
The paper identifies multiword phrases through frequency-based statistics, replaces selected phrases with unique tokens, and evaluates their representations using phrase analogies. Hierarchical softmax with subsampling and substantially more training data produce the strongest reported phrase representations and accuracy.
- Phrase identification: Phrases are formed by identifying words that occur frequently together but infrequently elsewhere, then replacing selected multiword expressions with unique tokens.“New York Times” and “Toronto Maple Leafs” become tokens, while “this is” remains unchanged.
- Phrase identification: The data-driven phrase detector uses unigram and bigram counts, discounts infrequent-word combinations, and applies decreasing thresholds across 2-4 passes to form longer phrases.Bigrams exceeding the chosen threshold are treated as phrases; the discounting coefficient δ limits phrases made from very infrequent words.
- Phrase representation experiments: Negative Sampling performs respectably with k = 5 but improves considerably at k = 15, while Hierarchical Softmax becomes best when frequent tokens are subsampled.Without subsampling, Hierarchical Softmax performs worse; with subsampling, it becomes the strongest method, showing that subsampling can improve both speed and accuracy in some cases.
- Phrase representation experiments: 72% accuracy was achieved on the phrase analogy task using hierarchical softmax, 1000-dimensional vectors, full-sentence context, and approximately 33 billion training words.Reducing the training corpus to 6B words lowered accuracy to 66%, indicating that the larger dataset is crucial.
- Phrase representation experiments: Manual nearest-neighbor comparisons consistently indicate that hierarchical softmax with subsampling learns the best representations for infrequent phrases.The comparison examines how representations differ across models using examples of nearest neighbors.
5 Additive Compositionality
Skip-gram word and phrase representations exhibit a linear structure that supports precise analogical reasoning and meaningful word composition through element-wise vector addition. This additive property reflects vectors’ relationship to surrounding-word context distributions and the softmax output probabilities.
- Additive compositionality: Skip-gram word and phrase vectors support meaningful composition through element-wise addition of their representations.The paper illustrates this additive phenomenon in Table 5.
- Additive compositionality: The representations also exhibit a linear structure enabling precise analogical reasoning through simple vector arithmetic.
- Additive compositionality: The additive property arises because word vectors predict surrounding words and therefore represent context distributions linked logarithmically to softmax probabilities.
6 Comparison to Published Word Representations
The paper compares its vectors with previously published neural word representations and finds that the large Skip-gram model produces visibly better nearest-neighbour quality, partly because it uses about 30 billion training words.
- Published representations: Previously published vectors from Collobert and Weston, Turian et al., and Mnih and Hinton were downloaded for comparison.These models had also been evaluated on word analogies, where Skip-gram achieved the best performance with a huge margin.
- Nearest-neighbour comparison: The comparison examines nearest neighbours of infrequent words across several published models and the phrase-trained Skip-gram model.Table 6 uses a model trained on over 30 billion training words; empty cells indicate out-of-vocabulary words.
- Nearest-neighbour comparison: The large Skip-gram model visibly outperforms the other models in the quality of its learned representations.The paper attributes part of this advantage to training on about 30 billion words, roughly two to three orders of magnitude more data.
7 Conclusion
The paper presents efficient methods for learning word and phrase representations whose linear structure supports analogical reasoning and simple composition. It also shows that performance depends on task-specific training choices, while frequent-word subsampling improves both speed and uncommon-word representations.
- Contributions: The Skip-gram model learns distributed word and phrase representations with linear structure that enables precise analogical reasoning.The techniques also apply to the continuous bag-of-words model.
- Results: Training on several orders of magnitude more data improves word and phrase representations, especially for rare entities.The computationally efficient architecture enables this larger-scale training.
- Results: Subsampling frequent words both accelerates training and significantly improves representations of uncommon words.The conclusion identifies subsampling as beneficial for both computational speed and representation quality.
- Training choices: Optimal training algorithms and hyperparameters are task-specific, with model architecture, vector size, subsampling rate, and training-window size most affecting performance.Different problems required different optimal hyperparameter configurations.
- Composition: Simple vector addition and single-token phrase representations combine into a powerful, computationally simple method for representing longer text.The paper presents the combination as requiring minimal computational complexity.