word2vec Explained: deriving Mikolov et al.'s negative-sampling word-embedding method

article2014arXiv1,722 citations

Explains the mathematical derivation and intuitive rationale behind Mikolov et al.'s negative-sampling objective, providing a clear formulation of how word2vec optimizes word embeddings.

Listen

Modern natural language processing relies heavily on converting text into numerical vectors that capture word meanings. While the popular word2vec software achieved state-of-the-art results, its original mathematical explanations and design choices remained difficult to interpret. The article provides a clear, step-by-step derivation of the negative-sampling method used in word2vec and analyzes practical implementation choices embedded in the software.

The analysis demonstrates that negative sampling fundamentally reframes the learning problem. Instead of predicting a context word given a target word—which requires computationally prohibitive calculations across hundreds of thousands of vocabulary words—negative sampling converts the task into a binary classification problem. The model learns to distinguish true word-context pairs observed in the training text from randomly generated negative pairs. Without these negative samples, the model would produce a trivial solution where all vector representations collapse into identical values.

In addition to the mathematical formulation, the article highlights critical implementation details in the software that significantly alter the training data. The software utilizes a dynamic context window, choosing a random window size up to a defined maximum for each word. Furthermore, infrequent words are pruned entirely, and highly frequent words are down-sampled before generating context windows. This preprocessing step effectively expands the window size across remaining words, allowing the model to capture broader topical relationships between distant, content-heavy words.

These findings show that word2vec's high performance and computational efficiency stem not only from its classification objective, but also from subtle data preparation heuristics. The authors note, however, that a theoretical gap remains: while the system relies on the assumption that words appearing in similar contexts share similar meanings, a formal mathematical explanation for why this specific optimization objective consistently produces high-quality word representations has yet to be established.

language model neural networks software word2vec negative sampling word embeddings

arXiv: 1402.3722

Paper: Distributed Representations of Words and Phrases and their Compositionality, Tomas Mikolov et al. (2013). This seminal paper introduces the negative-sampling Skip-gram objective whose mathematical derivation and theoretical rationale the source note directly sets out to explain.
Paper: Efficient Estimation of Word Representations in Vector Space, Tomáš Mikolov et al. (2013). It introduces the Continuous Bag-of-Words and Skip-gram architectures that establish the foundational framework for word2vec representations.
Paper: A Neural Probabilistic Language Model, Yoshua Bengio et al. (2003). This foundational work establishes continuous vector space word representations via neural language modeling upon which word2vec builds.
Paper: From Frequency to Meaning: Vector Space Models of Semantics, Peter D. Turney et al. (2010). It provides a comprehensive foundation for vector space models and distributional semantics underlying modern word embeddings.

Paper: Neural Word Embedding as Implicit Matrix Factorization, Omer Levy et al. (2014). It rigorously proves that the word2vec negative-sampling objective derived in the source is mathematically equivalent to implicit shifted Pointwise Mutual Information matrix factorization.
Paper: GloVe: Global Vectors for Word Representation, Jeffrey Pennington et al. (2014). It introduces GloVe as an alternative word representation model combining global co-occurrence matrix factorization with the log-bilinear predictive strengths of word2vec.
Paper: Enriching Word Vectors with Subword Information, Piotr Bojanowski et al. (2017). It extends the negative-sampling skip-gram framework explained in the source by representing words as bags of character n-grams to handle subword morphology.
Paper: Distributed Representations of Sentences and Documents, Quoc V. Le et al. (2014). It generalizes the word2vec framework from individual words to variable-length paragraphs and documents.
Paper: DeepWalk: online learning of social representations, Bryan Perozzi et al. (2014). It adapts the Skip-gram architecture to graph structures by treating random walks as sentences to generate vertex embeddings.
Paper: node2vec: Scalable Feature Learning for Networks, Aditya Grover et al. (2016). It builds directly on word2vec's Skip-gram with negative sampling to learn versatile node representations in networks using biased random walks.
Paper: LINE: Large-scale Information Network Embedding, Jian Tang et al. (2015). It applies the negative-sampling optimization objective from word2vec to learn scalable node embeddings that preserve first- and second-order network proximity.
Paper: Convolutional Neural Networks for Sentence Classification, Yoon Kim (2014). It demonstrates how pre-trained word2vec embeddings can be directly leveraged as feature inputs to boost sentence classification performance in convolutional neural networks.
Paper: From Word Embeddings To Document Distances, Matt J. Kusner et al. (2015). It utilizes pre-trained word2vec embeddings to formulate an Earth Mover's Distance-based metric for computing distances between entire text documents.
Paper: Man is to Computer Programmer as Woman is to Homemaker? Debiasing Word Embeddings, Tolga Bolukbasi et al. (2016). It investigates and develops debiasing techniques for societal stereotypes encoded within geometry of pre-trained word2vec vector spaces.

Cover for word2vec Explained: deriving Mikolov et al.'s negative-sampling word-embedding method

Abstract

The word2vec software of Tomas Mikolov and colleagues (this https URL ) 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.

Topics

language model neural networks software word embedding part of speech differential equations network architecture

Keywords

word2vec negative sampling word embeddings skip-gram model negative-sampling word-embedding method

1 The skip-gram model
1.1 Parameterization of the skip-gram model
2 Negative Sampling
2.1 Remarks
3 Context definitions
4 Why does this produce good word representations?
References

Knowls

Knowl 1 — Skip-Gram with Negative Sampling Objective Function
equation
The Skip-gram model parameterized with Negative Sampling (SGNS) optimizes target word embeddings $v_w \in \mathbb{R}^d$ for words $w \in V$ and context embeddings $v_c \in \mathbb{R}^d$ for context items $c \in C$ over a corpus of observed word-context pairs $D$ and generated negative pairs $D'$ by maximizing the objective function:

$\arg \max_\theta \sum_{(w,c) \in D} \log \sigma(v_c \cdot v_w) + \sum_{(w,c) \in D'} \log \sigma(-v_c \cdot v_w)$

where $\theta = \{v_w\}_{w \in V} \cup \{v_c\}_{c \in C}$ , $\sigma(x) = \frac{1}{1 + e^{-x}}$ is the logistic sigmoid function, and $v_c \cdot v_w$ denotes the scalar dot product between the context vector $v_c$ and target word vector $v_w$ . In this framework, $D$ is the multiset of positive word-context pairs extracted from text, and $D'$ is the multiset of randomly sampled negative pairs where each true pair $(w,c) \in D$ is matched with $k$ sampled negative pairs $(w, c_j) \in D'$ .
Knowl 2 — Binary Classification Formulation of Negative Sampling
theoretical result
Unlike standard Skip-gram, which models the conditional probability $p(c|w)$ via a full softmax distribution over the entire context vocabulary $C$ :

$p(c \mid w; \theta) = \frac{e^{v_c \cdot v_w}}{\sum_{c' \in C} e^{v_{c'} \cdot v_w}}$

the negative sampling formulation does not model $p(c|w)$ . Instead, it casts the objective as binary classification over the joint distribution of word-context pairs $(w, c)$ . Letting the binary random variable $D=1$ indicate that $(w, c)$ comes from the true corpus and $D=0$ indicate that it was drawn from noise, the probabilities are parameterized as:

$p(D = 1 \mid w, c; \theta) = \sigma(v_c \cdot v_w) = \frac{1}{1 + e^{-v_c \cdot v_w}}$

$p(D = 0 \mid w, c; \theta) = 1 - p(D = 1 \mid w, c; \theta) = \sigma(-v_c \cdot v_w) = \frac{1}{1 + e^{v_c \cdot v_w}}$

where $v_w, v_c \in \mathbb{R}^d$ are the embedding vectors for target word $w$ and context word $c$ . Maximizing the likelihood of observed pairs $D$ alone admits a trivial degenerate solution where all vectors are identical and $v_c \cdot v_w \to \infty$ ; the inclusion of negative pairs $D'$ prevents this collapse by penalizing $p(D = 1 \mid w, c; \theta)$ on noise samples.
Knowl 3 — Noise Distribution for Negative Context Sampling
model/method
For each observed positive pair $(w, c) \in D$ in Skip-gram with Negative Sampling, $k$ negative context tokens $c_1, \ldots, c_k$ are drawn to form negative pairs $(w, c_j) \in D'$ . Each context word $c_j$ is sampled independently from a smoothed unigram distribution raised to the $3/4$ power:

$P(c) = \frac{p_{\text{contexts}}(c)^{3/4}}{Z} = \frac{(\text{count}(c))^{3/4}}{\sum_{c' \in C} (\text{count}(c'))^{3/4}}$

where $p_{\text{contexts}}(c) = \frac{\text{count}(c)}{|Text|}$ is the empirical unigram probability of context $c$ across corpus $Text$ , $C$ is the context vocabulary, and $Z = \sum_{c' \in C} p_{\text{contexts}}(c')^{3/4}$ is the normalization constant. When all words appear as contexts, $p_{\text{contexts}}(x) = p_{\text{words}}(x)$ . Raising the distribution to the $3/4$ exponent increases the relative sampling frequency of rare words compared to standard unigram sampling.
Knowl 4 — Convexity and Optimization Properties of SGNS
theoretical result
In the Skip-gram Negative Sampling (SGNS) objective:

$\sum_{(w,c) \in D} \log \sigma(v_c \cdot v_w) + \sum_{(w,c) \in D'} \log \sigma(-v_c \cdot v_w)$

if the target word embeddings $\{v_w\}_{w \in V}$ are held fixed while only context embeddings $\{v_c\}_{c \in C}$ are optimized (or conversely, if context embeddings are held fixed while word embeddings are optimized), the problem reduces to standard binary logistic regression and is convex. However, because the algorithm optimizes both word and context representations simultaneously, the joint optimization problem over all parameters $\theta = \{v_w\}_{w \in V} \cup \{v_c\}_{c \in C}$ is non-convex.
Knowl 5 — Geometric Motivation for Dual Word and Context Vector Spaces
assumption
The Skip-gram architecture maintains two separate vector representations for every vocabulary term: a target word vector $v_w \in \mathbb{R}^d$ and a context vector $v_c \in \mathbb{R}^d$ , requiring $2 \cdot |V| \cdot d$ total parameters when the word and context vocabularies coincide.

This separation is necessary to avoid a geometric inconsistency: if target words and contexts shared a single representation vector $v$ , identical self-context pairs $(w, w)$ would have dot product $v \cdot v = \|v\|^2 \ge 0$ . Because words rarely occur within their own immediate local context window, the model must assign a low probability to $p(w \mid w)$ (or low $p(D=1 \mid w, w)$ ), which requires a low or negative dot product $v \cdot v$ . Assigning a low dot product to $v \cdot v$ is impossible under a single shared Euclidean vector parameterization.
Knowl 6 — Dynamic Context Window Sizing in word2vec
model/method
In word2vec's Skip-gram implementation, the context window around each word token is dynamic rather than fixed. Given a user-defined maximum window radius parameter $k \in \mathbb{N}^+$ , for each token occurrence $w_i$ at sentence position $i \in \{1, \ldots, n\}$ , an effective window size $k'$ is sampled uniformly at random from the discrete set $\{1, \ldots, k\}$ .

The context set $C(w_i)$ extracted for word $w_i$ is then defined as:

$C(w_i) = \{w_{i-k'}, \ldots, w_{i-1}, w_{i+1}, \ldots, w_{i+k'}\}$

Because smaller window radii are sampled alongside larger ones, context words located closer to the focus word $w_i$ are included in the training objective with higher probability across the corpus than words near the maximum distance $k$ , implementing a linear distance decay without explicit weighting terms.
Knowl 7 — Text Pre-Pruning and Subsampling Impact on Context Windows
model/method
In word2vec, vocabulary filtering and frequent-word subsampling are applied directly to the text stream before context window extraction occurs:
1. Words appearing fewer than $\text{min-count}$ times across the corpus are pruned and omitted as both target words and contexts.
2. High-frequency words are probabilistically removed according to a down-sampling formula parameterized by a threshold.
Because pruned and subsampled words are deleted from the token sequence prior to context window formation, the effective text span spanned by a window of size $k'$ expands across deleted positions. This expansion connects target words to informative, content-bearing context words that were originally linearly separated by frequent or rare tokens, increasing the topicality of the learned embeddings.

Coverage note — No substantial contributed material was omitted; the knowls cover the complete derivation of the SGNS objective, the negative sampling noise distribution, the binary classification formulation, convexity properties, dual-embedding representation assumptions, dynamic window sizing, and subsampling effects.

References

1.Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word representations in vector space. CoRR, abs/1301.3781, 2013.
2.Tomas Mikolov, Ilya Sutskever, Kai Chen, Gregory S. Corrado, and Jeffrey Dean. Distributed representations of words and phrases and their compositionality. In Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pages 3111–3119, 2013.

Citation

MLA

Goldberg, Y., and O. Levy. “Word2vec Explained: Deriving Mikolov Et Al.'s Negative-sampling Word-embedding Method”. arXiv, 2014, http://arxiv.org/abs/1402.3722v1.

APA

Goldberg, Y., & Levy, O. (2014). word2vec Explained: deriving Mikolov et al.'s negative-sampling word-embedding method. arXiv. http://arxiv.org/abs/1402.3722v1

Chicago

Goldberg, Y., and O. Levy. 2014. “Word2vec Explained: Deriving Mikolov Et Al.'s Negative-sampling Word-embedding Method”. arXiv. http://arxiv.org/abs/1402.3722v1.

Harvard

Goldberg, Y. and Levy, O. (2014) “word2vec Explained: deriving Mikolov et al.'s negative-sampling word-embedding method”, arXiv [Preprint]. Available at: http://arxiv.org/abs/1402.3722v1.

Vancouver

1. Goldberg Y, Levy O (2014) word2vec Explained: deriving Mikolov et al.'s negative-sampling word-embedding method. arXiv

BibTeX

@article{goldberg2014word2vec,
  title = {word2vec Explained: deriving Mikolov et al.'s negative-sampling word-embedding method},
  author = {Goldberg, Yoav and Levy, Omer},
  year = {2014},
  journal = {arXiv},
  url = {http://arxiv.org/abs/1402.3722v1},
  eprint = {1402.3722}
}

Metadata:arXiv

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: Published with permission

word2vec Explained: deriving Mikolov et al.'s negative-sampling word-embedding method

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Skip-Gram with Negative Sampling Objective Function

Knowl 2 — Binary Classification Formulation of Negative Sampling

Knowl 3 — Noise Distribution for Negative Context Sampling

Knowl 4 — Convexity and Optimization Properties of SGNS

Knowl 5 — Geometric Motivation for Dual Word and Context Vector Spaces

Knowl 6 — Dynamic Context Window Sizing in word2vec

Knowl 7 — Text Pre-Pruning and Subsampling Impact on Context Windows

References

Citation

BibTeX

Access the Paper