Source-linked AI summary
word2vec Parameter Learning Explained
Xin Rong
TL;DR
Updating output vectors requires iterating over the entire vocabulary for each training instance, making computation expensive for large vocabularies and corpora. The paper presents hierarchical softmax and negative sampling to reduce this cost, with hierarchical softmax reducing per-instance complexity from O(V) to O(log(V)) and negative sampling updating only sampled words.
Problem
Updating output vectors requires computations over every vocabulary word for each training instance, making training expensive for large vocabularies and corpora.
Method
The paper explains hierarchical softmax and negative sampling as approaches that limit the number of output vectors updated per training instance.
Results
O(V) to O(log(V)) per context word: hierarchical softmax reduces computational complexity while retaining roughly the same number of parameters.
Takeaways & Limitations
Negative sampling updates only the observed output word and sampled negative words, saving significant computational effort per iteration.
Abstract
from arXiv · showhide
The word2vec model and application by Mikolov et al. have attracted a great amount of attention in recent two years. The vector representations of words learned by word2vec models have been shown to carry semantic meanings and are useful in various NLP tasks. As an increasing number of researchers would like to experiment with word2vec or similar techniques, I notice that there lacks a material that comprehensively explains the parameter learning process of word embedding models in details, thus preventing researchers that are non-experts in neural networks from understanding the working mechanism of such models. This note provides detailed derivations and explanations of the parameter update equations of the word2vec models, including the original continuous bag-of-word (CBOW) and skip-gram (SG) models, as well as advanced optimization techniques, including hierarchical softmax and negative sampling. Intuitive interpretations of the gradient equations are also provided alongside mathematical derivations. In the appendix, a review on the basics of neuron networks and backpropagation is provided. I also created an interactive demo, wevi, to facilitate the intuitive understanding of the model.
1 Continuous Bag-of-Word Model
CBOW predicts a target word from one or more context words by combining input vectors and applying a softmax output layer. The derivations show how prediction errors update output vectors and the active context input vectors.
- 1.1 One-word context: The one-word-context CBOW model uses a one-hot input and copies the active word’s vector through a linear hidden layer.The input→hidden matrix W stores input vectors as rows, while the hidden layer passes the selected row onward.
- 1.1 One-word context: Softmax converts vocabulary scores into a multinomial posterior distribution over possible output words.The scores are computed from the hidden representation and the hidden→output matrix W′.
- 1.1 One-word context: The training objective maximizes the conditional probability of the observed target, using negative log probability as a cross-entropy loss.The target indicator is one for the observed output word and zero elsewhere, making the derivative equal to the prediction error yj − tj.
- 1.1 One-word context: Output-vector updates move overestimated words away from the input vector and the underestimated target word closer to it.The update affects every vocabulary word, with little movement when predicted and expected probabilities are close; “closer” refers to inner product rather than Euclidean distance.
- 1.1 One-word context: Only the active context word’s input-vector row changes in one-word-context CBOW, because the one-hot input makes all other input derivatives zero.The update direction is determined by the error-weighted sum of output vectors.
- 1.2 Multi-word context: For multi-word contexts, CBOW averages the context input vectors to form the hidden representation, while retaining the same hidden→output update form.The objective remains the same as in the one-word case except that h is the average context vector.
2 Skip-Gram Model
Skip-gram reverses CBOW’s arrangement: a target word enters at the input, and multiple context words are predicted at the output. Shared output weights make the update errors aggregate across context positions.
- 2 Skip-Gram Model: Skip-gram places the target word at the input layer and the context words on the output layer, opposite to CBOW.The input hidden representation is still the vector associated with the single input word.
- 2 Skip-Gram Model: The model produces C multinomial output distributions, one for each context position, using the same hidden→output matrix.The shared matrix means each output panel uses the same word output vectors.
- 2 Skip-Gram Model: Skip-gram’s loss sums the prediction losses for the C actual context words.Each panel contributes an error for its corresponding context target.
- 2 Skip-Gram Model: The hidden→output update uses prediction errors summed across all context words, while the input→hidden derivation replaces each single-word error with that aggregate.The resulting intuitive interpretation is otherwise the same as in one-word-context CBOW.
3 Optimizing Computational Efficiency
The original word2vec models require vocabulary-wide output updates, making training expensive, while hierarchical softmax and negative sampling reduce the number of updated output representations per instance.
- Computational bottleneck: Original CBOW and skip-gram training updates output vectors for every vocabulary word, making large-vocabulary or large-corpus training impractical.Each instance requires computing output probabilities and prediction errors across the vocabulary.
- Hierarchical softmax: Hierarchical softmax represents vocabulary words as leaves in a binary tree and estimates each word probability through its root-to-leaf path.The model uses V−1 inner units, with each path encoding successive left-or-right decisions.
- Hierarchical softmax: Hierarchical-softmax updates use prediction errors along the target word’s path, moving inner-unit vectors according to whether their left-right decisions are over- or under-predicted.The same update procedure applies to CBOW and repeats across output-context words for skip-gram.
- Hierarchical softmax: Hierarchical softmax reduces computational complexity per training instance per context word from O(V) to O(log(V)) while retaining roughly the same number of parameters.The inner-unit vectors replace the original output-word vectors for parameterization.
- Negative sampling: Negative sampling updates only the positive output word and sampled negative words instead of every vocabulary word.The noise distribution supplies negative samples; word2vec uses a unigram distribution raised to the 3/4 power.
- Negative sampling: Negative sampling therefore saves substantial computation by restricting updates to wj ∈ {wO} ∪ Wneg.The simplified objective is intended to produce high-quality word embeddings without a fully defined posterior multinomial distribution.
A.1 Learning Algorithms for a Single Unit
The appendix introduces a single artificial neuron, its link functions, and stochastic-gradient updates as foundations for understanding word2vec parameter learning.
- Artificial neuron: An artificial neuron maps input values and weights to a scalar output through a link function.The inputs are x1 through xK, the weights are w1 through wK, and f is also called an activation, decision, or transfer function.
- Artificial neuron: The neuron’s net input is a weighted combination of its inputs, expressed in vector notation without a bias term.A bias can be added by including a constant input dimension x0 = 1.
- Link functions: Different link functions produce distinct neuron behaviors, including the unit step function and the logistic function.A unit-step neuron is a perceptron, whose learning algorithm has a corresponding update equation.
- Perceptron: The perceptron is a linear classifier, so its description capacity can be limited for fitting complex functions.The text motivates nonlinear models when more complex functions are required.
- Logistic function: The logistic function outputs values between 0 and 1 and is smooth and differentiable, simplifying update-equation derivation.These properties support its use in stochastic-gradient learning.
- Parameter updates: With stochastic gradient descent, the logistic-neuron weight update scales the input by prediction error and the derivative term y(1 − y).The learning objective is defined through an error function before differentiating with respect to each weight.
A.2 Back-propagation with Multi-Layer Network
The appendix derives back-propagation updates for a one-hidden-layer network by differentiating the error from the output layer toward earlier layers. Intermediate error derivatives are reused to efficiently propagate learning signals backward.
- Network setup: The network uses input, hidden, and output layers with weights connecting input-hidden and hidden-output units.The hidden and output computation units use the logistic function, and the squared sum error is defined against gold-standard output labels.
- Derivative procedure: Back-propagation computes derivatives in three steps: with respect to each layer’s output, net input, and weights.The derivation starts at the right-most output layer and then moves leftward.
- Output layer: The output-layer derivation yields an update equation for hidden-output weights, scaled by the positive learning rate η.This is the first completed weight-update result in the derivation.
- Hidden layer: The same three-step process produces updates for input-hidden weights by accounting for the hidden layer’s connections to all output units.The hidden-layer net-input derivative is reused in computing these updates.
- Interpretation: Intermediate derivatives can be reused across layers, while the back-propagated error term acts like a hidden-unit error and extends to deeper networks.This reuse makes the chain of derivative computations efficient.
B wevi: Word Embedding Visual Inspector
wevi is an interactive visual interface for examining how word-embedding models learn. It supports visual inspection, configurable training, and both CBOW and skip-gram models.
- Visualization: wevi lets users visually examine input- and output-vector movement as training instances are consumed.Training can run one instance at a time or in batch mode, revealing patterns in weight matrices and word vectors.
- Visualization: Principal component analysis projects high-dimensional vectors into a two-dimensional scatter plot.This provides the visualization used to inspect vector behavior and emerging patterns.
- Model support: The demo supports both CBOW and skip-gram models.Users can compare the behavior of these two word2vec architectures within the same interface.
- Interaction: Users can activate input units and inspect which hidden and output units become active after training.They can also customize training data, hidden-layer size, and learning rate.
- Examples and access: Preset datasets can reproduce the word analogy king - queen = man - woman, while the source code is publicly available.The demo is intended to provide intuitive insight into the model’s working mechanism.