Word2Vec, a popular model introduced by Mikolov et al., revolutionized the way word embeddings are created by representing words in continuous vector space. This model, particularly through the negative-sampling technique, efficiently predicts words based on their context within a corpus. Understanding negative sampling requires delving into the functioning of Word2Vec and the challenge it seeks to address.

Background: Word2Vec Overview

Word2Vec operates in two main architectures:

1. Continuous Bag-of-Words (CBOW): Predicts the current word given its surrounding context words within a window.
2. Skip-Gram: Predicts surrounding context words for a given target word.

Both methods optimize the word vectors by enhancing the probability of predicting actual context words correctly. However, they handle potentially massive outputs, as the softmax function used involves computing probabilities for all words in the vocabulary, which can be computationally expensive. Negative sampling provides a workaround to this problem.

The Challenge of the Softmax Function

In its unsimplified form, the optimization objective for models using the softmax function involves computing probabilities for the entire vocabulary:

$$P(w_O|w_I) = \frac{\exp(v'_{w_O} \cdot v_{w_I})}{\sum_{w=1}^{V} \exp(v'_w \cdot v_{w_I})}$$Here, $v_{w_I}$ and $v'_{w_O}$ are input and output vectors for the input and output words respectively, and $V$ is the total vocabulary size. This calculation is computationally heavy, especially if the vocabulary V is extensive.

Negative Sampling Simplified

Negative sampling addresses the softmax computation challenge by narrowing the focus only to a few negative samples rather than the whole vocabulary. The idea is to optimize a simplified objective: distinguish a set of context word pairs from randomly sampled negative ones. This involves the following steps:

1. Select Positive Pairs: Use actual word-context pairs (target word $w_I$ and context word $w_O$) from the corpus.
2. Sample Negative Pairs: Randomly select a few negative samples, which are words that do not appear in the same context as the target word. The number of negative samples, typically set by the user, is a tuning parameter.
3. Define the Loss Function: The goal is to maximize the objective function:
   $$\log \sigma(v'_{w_O} \cdot v_{w_I}) + \sum_{i=1}^{k} \log \sigma(-v'_{w_{N_i}} \cdot v_{w_I})$$In this formulation:
   • $\sigma$ is the sigmoid function.
   • $v'_{w_{N_i}}$ is the output vector of a negative sample.
   • $k$ is the number of negative samples. This loss function contrasts the positive example score with the scores of negative samples, encouraging the model to distinguish actual context pairs from random ones.

Example Application

Consider a simple example with the sentence: "The cat sat on the mat". In this case:

• Positive Pair: ('cat', 'sat')
• Negative Samples: ('dog', 'run', 'blue') — as they do not typically appear in similar contexts in the given dataset.

By focusing the optimization on this small subset of scores, the model efficiently updates word vectors, pushing positive pairs closer in space, while moving randomly sampled negative pairs apart.

Advantages of Negative Sampling

1. Efficiency: Reduces computational complexity significantly, particularly advantageous for handling large corpora.
2. Scalability: Allows Word2Vec to scale seamlessly to handle vast vocabulary sizes.
3. Simplicity: Conceptually straightforward with easy-to-compute gradients for updates during training.

Key Considerations in Negative Sampling

• Choice of Negative Samples: Influences model quality. Typically, negative samples are chosen with a distribution reflecting word frequency, such as by the power law distribution P(w)∝U(w)^{3/4} where U(w) is the unigram distribution.
• Number of Negative Samples: A hyperparameter that might require tuning. Common choices are 5-20 per positive sample.
• Implementation: Especially valuable in neural language models where real-time processing is paramount.

Summary

Negative sampling is a cornerstone technique within Word2Vec that enhances its reliability and applicability for natural language processing tasks, underscoring its importance in the broader field of machine learning.