Noise Contrastive Estimation

Definition

Noise contrastive estimation (NCE) transforms the problem of density estimation to binary classification between data samples and noise samples. Given a sample of data points that follow unknown probability distribution $p_m(\cdot ;{\theta }^{\ast })$ parametrized by $\theta$. Noise contrastive estimation (NCE) is used to find an estimator $\hat{\theta }$ that best approximate the true parameter ${\theta }^{\ast }$. Although MLE has good properties, it requires the parametric family $p_m(\cdot ;\theta )$ to be normalized $\int p_m(x;\theta )dx=1$ while calculating. NCE finds the estimator by maximizing an objective function (like in MLE) but without needs of normalizing while calculating, so that it treats normalization coefficient as another estimation parameter. It is desirable property, since the normalization constant may be difficult or expensive to calculate.

The idea is to pollute sample with noise, data points that come from a known distribution, and perform nonlinear logistic regression to discriminate between data and noise.

Consider a data sample $X=(x_1,x_2,\dots ,x_M),x_i\sim p_m(\cdot ;\theta )$ and noise sample $Y=(y_1,y_2,\dots ,y_N),p_n(\cdot )$ and the union of the two samples $U=X\cup Y$. A binary class label $C_i$ is assigned to each $u_i$, where $C_i=\{\begin{array}{ll}1& u_i\in X\\ 0& u_i\in Y\end{array}$.

By the definition of the function, $P(u|C=1)=p_m(u;\theta )$ and $P(u|C=0)=p_n(u)$. By the Bayes Theorem, $P(C=1|u)=\frac{p_m(u;\theta )}{p_m(u;\theta )+\nu p_n(u)}$ and $P(C=0|u)=1-\frac{p_m(u;\theta )}{p_m(u;\theta )+\nu p_n(u)}$, where $\nu =\frac{N}{M}$ is the sample-noise ratio. The log-likelihood function of the binary classification problem is derived as $l(\theta )=\sum _{i=1}^M\ln [P(C=1|x_i)]+\sum _{i=1}^N\ln [1-P(C=1|y_i)]$ The NCE estimator is obtained by maximizing the objective function (log-likelihood) with respect to $\theta$ $\hat{\theta }=\underset{\theta }{\mathrm{argmax}}l(\theta )$

Examples

Word Embedding (Skip-Gram Model)

In the context of word embeddings, particularly the Skip-gram model, the unknown distribution $p_m(\cdot ;\theta )$ becomes $p(c|w;\theta )$, the probability of a context word $c$ given an input word $w$. The $\theta$ represents the parameters of the word embedding model.

The noise distribution $p_n(c)=\frac{\mathrm{cnt}(c{)}^{3/4}}{{\sum }_{c^{\prime }\in C}\mathrm{cnt}(c^{\prime })}$, where $\mathrm{cnt}(c)$ is the count of word $c$ in the corpus, is the unigram distribution of contexts raised to the power of $\frac{3}{4}$ to balance frequent and rare words.

For each word-context pair $(w,c)$ from the true data, we sample $k$ negative examples from $p_n(\cdot )$. The NCE objective function is derived as: ${\mathcal{L}}_{\text{NCE}}=\sum _{(w,c)\in D}\left[\ln \left(\frac{p_m(c|w;\theta )}{p_m(c|w;\theta )+k{p}_n(c)}\right)+\sum _{c^{\prime }\sim p_n(c)}^k\ln \left(\frac{k{p}_n(c^{\prime })}{p_m(c^{\prime }|w)+k{p}_n(c^{\prime })}\right)\right]$ where $D$ is the set of observed word-context pairs, and $k$ is the number of noise samples per data sample.

In practice, $p_m(c|w)$ is often modeled as $\exp (v_w{v}_c)$, without explicit normalization. By maximizing this objective, we obtain word embeddings (vectors $v_w$ and $v_c$) that can discriminate between true context words and random noise words, effectively capturing semantic relationships in the vector space.