Negative Sampling is an optimization technique used in Word2Vec to reduce the computational cost of updating weights. Instead of updating the weights for all words in the vocabulary during each training step, Negative Sampling updates only the weights for the true context word (the positive sample) and a small number of randomly chosen "noise" words (the negative samples). The probability of selecting a specific word as a negative sample is proportional to its frequency in the training corpus, meaning highly frequent words are more likely to be selected as negative samples.

Google

Training a standard Word2Vec model on a large vocabulary is computationally expensive because the naive approach requires calculating and normalizing probabilities across all words in the output layer for every training sample. To significantly reduce this computational cost, two primary optimization techniques are utilized:

1. **Hierarchical Softmax**: Replaces the flat output layer with a Huffman tree-based model, reducing the time complexity of the output probability calculation and weight updates. It evaluates a path of binary decisions instead of calculating probabilities for every word.

2. **Negative Sampling**: Instead of updating all output vectors, this approach updates only the target word and a small, randomly selected sample of incorrect, or "negative", words. The probability of selecting a word as a negative sample is positively correlated with its frequency in the corpus, which also helps mitigate the influence of overly common words (e.g., "the").

Optimization Techniques in Word2Vec

https://www.coursera.org/learn/nlp-sequence-models

Sequence Models

Negative Sampling in Word2Vec

Hierarchical Softmax is an approach to reduce the computational cost of high-dimensional output layers over large vocabulary sets $$\mathbb{V}$$. It decomposes probabilities hierarchically by organizing words into a tree-like structure of nested categories. Instead of requiring computations proportional to the vocabulary size $$|\mathbb{V}|$$ and the number of hidden units $$n_h$$, a balanced tree reduces the required computations to a depth of $$O(\log|\mathbb{V}|)$$. The probability of selecting a specific word is calculated as the product of the conditional probabilities of choosing the correct branch at every node along the path from the root of the tree to the leaf containing that word. These conditional probabilities are often predicted using a logistic regression model with context $$C$$ as input. While it is possible to optimize a binary tree structure, it is often simpler to define a tree with a depth of 2 and a branching factor of $$\sqrt{|\mathbb{V}|}$$ to capture most of the computational benefits by creating mutually exclusive word classes.

Learn Before

Related