Efficient Estimation of Word Representations in Vector Space

Reading guide

Problem and motivation

Traditional NLP systems represented words as discrete atomic indices, discarding inherent semantic and syntactic relationships. While distributed word representations trained using neural network language models (NNLMs) or recurrent neural network language models (RNNLMs) significantly outperformed n-grams, their computational complexity made scaling prohibitively expensive. Previous architectures were rarely trained on more than a few hundred million words, usually restricted to dimensionalities between $50$ and $100$.

In feedforward NNLMs, the computational bottleneck stems from the dense non-linear hidden layer ($N\times D\times H$) and the unnormalized vocabulary output layer ($H\times V$). The goal of this paper is to eliminate the non-linear hidden layer bottleneck, enabling models to scale to billions of training tokens and vocabularies containing millions of words, while retaining subtle linear relationships (e.g., $\text{vector}(\text{"King"})-\text{vector}(\text{"Man"})+\text{vector}(\text{"Woman"})\approx \text{vector}(\text{"Queen"})$).

Key ideas

• Removing Hidden Layer Non-Linearities: By stripping out the non-linear activation layer, training complexity drops dramatically, allowing vast increases in both corpus size and embedding dimensionality.
• Continuous Bag-of-Words (CBOW): A log-linear classifier predicting a target center word given its surrounding context words (both history and future). Context vectors are averaged into a shared projection layer.
• Continuous Skip-gram: A log-linear classifier predicting surrounding context words within a window given only the current center word, sampling distant words less frequently.
• Hierarchical Softmax with Huffman Coding: Softmax normalization cost is reduced from $V$ to approximately ${\log }_2(V)$ (or ${\log }_2(\text{Unigram\_perplexity}(V))$ via Huffman trees, which assign shorter codes to frequent words).
• Analogy Evaluation Benchmark: A new 19,544-question test set evaluating syntactic (e.g., comparative, past tense) and semantic (e.g., capital-country, currency) linguistic regularities using vector arithmetic and cosine distance.

Method (with the key equations)

Training complexity is defined as the number of parameter accesses across $E$ epochs, $T$ words in the training set, and per-example cost $Q$: $$O=E\times T\times Q$$

Feedforward NNLM Baseline

For context length $N$, embedding dimension $D$, hidden units $H$, and vocabulary size $V$: $$Q=N\times D+N\times D\times H+H\times V$$ When using hierarchical softmax, the output term reduces to $H\times {\log }_2(V)$, leaving $N\times D\times H$ as the bottleneck.

Recurrent Neural Net Language Model (RNNLM) Baseline

With hidden state dimension $H$ equal to embedding dimension $D$: $$Q=H\times H+H\times V$$ Using hierarchical softmax, the output term reduces to $H\times {\log }_2(V)$, leaving recurrent transition $H\times H$ as the dominant cost.

Continuous Bag-of-Words (CBOW)

CBOW replaces the hidden layer with an averaged projection layer across $N$ context words (typically 4 past and 4 future words): $$Q=N\times D+D\times {\log }_2(V)$$

Continuous Skip-gram

Skip-gram takes the center word and predicts context words within maximum distance $C$ (in experiments, $C=10$). For each word, an offset $R\in \{1,\dots ,C\}$ is drawn uniformly, predicting $R$ words before and after: $$Q=C\times (D+D\times {\log }_2(V))$$

Analogy Search

Questions of the form "$A$ is to $B$ as $C$ is to $D$" are answered by finding the vocabulary vector $X$ maximizing: $$X=\arg \underset{w\notin \{B,C,A\}}{\max }\cos (v_w,v_B-v_A+v_C)$$

Results (with the most important numbers)

• Analogy Benchmark Performance (640-D, 320M words):
  • RNNLM: 9% Semantic, 36% Syntactic.
  • NNLM: 23% Semantic, 53% Syntactic.
  • CBOW: 24% Semantic, 64% Syntactic.
  • Skip-gram: 55% Semantic, 59% Syntactic.
• Scaling on Google News 6B tokens (DistBelief distributed training):
  • NNLM ($100$-D): 34.2% Semantic, 64.5% Syntactic, 50.8% Total (took $14\times 180$ CPU-core days).
  • CBOW ($1000$-D): 57.3% Semantic, 68.9% Syntactic, 63.7% Total (took $2\times 140$ CPU-core days).
  • Skip-gram ($1000$-D): 66.1% Semantic, 65.1% Syntactic, 65.6% Total (took $2.5\times 125$ CPU-core days).
• Microsoft Sentence Completion Challenge: Skip-gram alone reached 48.0% accuracy; combined with an ensemble of RNNLMs, it reached a state-of-the-art 58.9% accuracy.
• Epochs vs. Data: Training for 1 epoch on twice as much data performed comparably to or better than 3 epochs over smaller data while reducing wall-clock training time.

Limitations and open questions

• Exact Match Evaluation Metric: The test set counts synonyms as mistakes (e.g., predicting an equivalent valid city or plural form), setting an artificial ceiling below 100%.
• Lack of Subword Morphology: Words are treated as single tokens; the model does not exploit internal character or morpheme structure, limiting its syntactic generalization on rare or inflected words.
• Multi-Word Phrases: The model operates only on single-token words and does not natively handle multi-word expressions (such as "New York").
• Sentence Completion Performance: Skip-gram by itself scored lower (48.0%) than average LSA similarity (49.0%) on the Microsoft Sentence Completion task, relying on hybridization with RNNLMs to achieve competitive results.