Source-linked AI summary
word2vec Explained: deriving Mikolov et al.'s negative-sampling word-embedding method
Yoav Goldberg, Omer Levy
TL;DR
The skip-gram formulation is computationally expensive because computing p(c|w; θ) requires an expensive summation. The note derives negative sampling as a more efficient alternative, clarifying that it optimizes a different quantity related to the joint distribution of words and contexts.
Problem
Computing the skip-gram objective is computationally expensive because p(c|w; θ) requires an expensive summation.
Method
The note derives Mikolov et al.'s negative-sampling objective from the skip-gram model as a more efficient way to derive word embeddings.
Results
Negative sampling models a quantity related to the joint distribution of words and contexts rather than the conditional distribution p(c|w).
Takeaways & Limitations
Negative sampling provides an efficient alternative for deriving word embeddings, but it does not optimize the original skip-gram conditional objective.
Takeaways & Limitations
The negative-sampling objective has a trivial solution that assigns p(D = 1|w, c; θ) = 1 for every word-context pair.
Abstract
from arXiv · showhide
The word2vec software of Tomas Mikolov and colleagues (https://code.google.com/p/word2vec/ ) has gained a lot of traction lately, and provides state-of-the-art word embeddings. The learning models behind the software are described in two research papers. We found the description of the models in these papers to be somewhat cryptic and hard to follow. While the motivations and presentation may be obvious to the neural-networks language-modeling crowd, we had to struggle quite a bit to figure out the rationale behind the equations. This note is an attempt to explain equation (4) (negative sampling) in "Distributed Representations of Words and Phrases and their Compositionality" by Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado and Jeffrey Dean.
1 The skip-gram model
The skip-gram model learns word and context vector parameters by maximizing the probability of observed word-context pairs. Its softmax formulation is conceptually direct but computationally expensive, motivating hierarchical-softmax alternatives.
- The model starts with corpus words and their contexts, modeling conditional probabilities p(c|w).
- 1.1 Parameterization of the skip-gram model: Softmax parameterizes p(c|w; θ) using vector representations for words and contexts and their dot products.
- 1.1 Parameterization of the skip-gram model: The parameters include word and context vectors in R^d, totaling |C| × |V | × d parameters.
- 1.1 Parameterization of the skip-gram model: The embedding assumption is that maximizing objective (4) produces vectors in which similar words have similar representations.
- 1.1 Parameterization of the skip-gram model: Computing the softmax is expensive because its normalization sums over potentially hundreds of thousands of contexts, motivating hierarchical softmax.
2 Negative Sampling
Negative sampling derives embeddings by distinguishing observed word-context pairs from randomly sampled negative pairs, optimizing an objective different from skip-gram’s conditional-probability objective. The construction uses k negative contexts per observed pair, sampled from a unigram distribution raised to the 3/4 power.
- Negative sampling is presented as a more efficient embedding derivation, but it optimizes a different objective from the skip-gram model.
- The model assigns probabilities that word-context pairs came from corpus data, with parameters θ controlling p(D = 1|w, c; θ).
- Using only observed pairs has a trivial solution: assign p(D = 1|w, c; θ) = 1 to every pair by making vector dot products sufficiently large.The note states that a probability of 1 is reached practically when K ≈40.
- Negative examples D′ prevent this collapse by supplying random word-context pairs that the model is required to classify as incorrect.
- For negative sampling of k, D′ is k times larger than D, with k contexts sampled per observed pair from the unigram distribution raised to the 3/4 power.
- Unlike skip-gram, the formulation models a quantity related to the joint distribution of words and contexts rather than p(c|w), and joint representation learning is non-convex.
3 Context definitions
word2vec constructs contexts from a window around each word, with implementation details that alter the effective window and the retained vocabulary. The maximum window is randomized per word, while rare and frequent words may be removed before context generation.
- For a sentence of n words, a word’s contexts generally come from a window of size k around that word.The context set includes up to k preceding and k following words, excluding the target word.
- Dynamic window size: The window size is dynamic: k is the maximum, and each word receives a uniformly sampled window size k′ from 1 through k.
- Effect of subsampling and rare-word pruning: Words occurring fewer than min-count times are removed from consideration as both words and contexts.
- Effect of subsampling and rare-word pruning: Frequent words are down-sampled using the sample parameter before contexts are generated, which increases the effective window size for some words.
- Effect of subsampling and rare-word pruning: According to Mikolov et al., sub-sampling frequent words improves embedding quality on some benchmarks.
4 Why does this produce good word representations?
The note gives an intuitive distributional explanation for why the objective may produce useful word representations, but explicitly acknowledges that this explanation remains informal. It calls for a more formal account.
- The distributional hypothesis links similar meanings to similar contexts, while the objective raises dot products for good pairs and lowers them for bad pairs.
- Words sharing many contexts, and contexts sharing many words, are therefore described as becoming similar in the embedding space.
- The note acknowledges that this explanation is hand-wavy and asks for a more precise formal treatment.