Negative Sampling

Definition

Negative sampling (NS) is a simplified version of NCE. It shares the core idea of transforming the problem of density estimation into binary classification between true data samples and noise samples.

In the context of word embeddings, particularly the Skip-gram model, NS aims to learn good word representations without the need to estimate a full probability distribution. The goal is to find parameters $\theta$ that best represent the relationship between words and their contexts. Given a word-context pair $(w,c)$ from the true data distribution, NS samples $k$ negative examples (noise) from a noise distribution $p_n(c)$. The objective is to maximize the probability of the true pair while minimizing the probability of the noise pairs.

NS models $p(D=1|w,c;\theta )$ with the Sigmoid Function: $p(D=1|w,c;\theta )=\sigma (v_c\cdot v_w)=\frac{1}{1+\exp (-v_c\cdot v_w)}$

The NS objective function is derived as: ${\mathcal{L}}_{\text{NS}}=\sum _{(w,c)\in D}\ln \sigma (v_c\cdot v_w)+\sum _{(w,c)\in D^{\prime }}^k\ln \sigma (-v_c\cdot v_w)$ where $D^{\prime }$ is the set of negative samples drawn from the noise distribution.

The NS objective function is similar to the Skip-gram objective but replaces the expensive Softmax Function with a simpler binary classification task between true and noise samples.