# Intuitive explanation of Noise Contrastive Estimation (NCE) loss?

I read about NCE (a form of candidate sampling) from these two sources:

Tensorflow writeup

Original Paper

Can someone help me with the following:

1. A simple explanation of how NCE works (I found the above difficult to parse and get an understanding of, so something intuitive that leads to the math presented there would be great)
2. After point 1 above, a naturally intuitive description of how this is different from Negative Sampling. I can see that there's a slight change in the formula but could not understand the math. I do have an intuitive understanding of negative sampling in the context of word2vec - we randomly choose some samples from the vocabulary V and update only those because |V| is large and this offers a speedup. Please correct if wrong.
3. When to use which one and how is that decided? It would be great if you could include examples(possibly easy to understand applications)
4. Is NCE better than Negative Sampling? Better in what manner?
• may be my post may helps. nanjiang.quora.com/Noise-contrastive-Estimation and later experiment with theano can be found at my github.com/jiangnanHugo/language_modeling. I hope my understanding is right. Oct 6, 2016 at 12:03

Taken from this post:https://stats.stackexchange.com/a/245452/154812

The issue

There are some issues with learning the word vectors using an "standard" neural network. In this way, the word vectors are learned while the network learns to predict the next word given a window of words (the input of the network).

Predicting the next word is like predicting the class. That is, such a network is just a "standard" multinomial (multi-class) classifier. And this network must have as many output neurons as classes there are. When classes are actual words, the number of neurons is, well, huge.

A "standard" neural network is usually trained with a cross-entropy cost function which requires the values of the output neurons to represent probabilities - which means that the output "scores" computed by the network for each class have to be normalized, converted into actual probabilities for each class. This normalization step is achieved by means of the softmax function. Softmax is very costly when applied to a huge output layer.

The (a) solution

In order to deal with this issue, that is, the expensive computation of the softmax, Word2Vec uses a technique called noise-contrastive estimation. This technique was introduced by [A] (reformulated by [B]) then used in [C], [D], [E] to learn word embeddings from unlabelled natural language text.

The basic idea is to convert a multinomial classification problem (as it is the problem of predicting the next word) to a binary classification problem. That is, instead of using softmax to estimate a true probability distribution of the output word, a binary logistic regression (binary classification) is used instead.

For each training sample, the enhanced (optimized) classifier is fed a true pair (a center word and another word that appears in its context) and a number of kk randomly corrupted pairs (consisting of the center word and a randomly chosen word from the vocabulary). By learning to distinguish the true pairs from corrupted ones, the classifier will ultimately learn the word vectors.

This is important: instead of predicting the next word (the "standard" training technique), the optimized classifier simply predicts whether a pair of words is good or bad.

Word2Vec slightly customizes the process and calls it negative sampling. In Word2Vec, the words for the negative samples (used for the corrupted pairs) are drawn from a specially designed distribution, which favours less frequent words to be drawn more often.

References

• Just want to add a little historical notes. The word2vec paper was published first, and then [E] was published as a simplified version without the tree structure in sampling. Jul 17, 2020 at 12:55

Honestly there is no intuitive way to understand why NCE loss will work without deeply understanding its math. To understand the math, you should read the original paper.

The reason why NCE loss will work is because NCE approximates maximum likelihood estimation (MLE) when the ratio of noise to real data $$k$$ increases.

The TensorFlow implementation works in practice. Basically, for each data $$(x, y)$$, $$y$$ is the labeled class from the data, TensorFlow NCE loss samples $$k$$ classes from noise distributions. We calculate a special version of the digits for each of the classes (1 from data + $$k$$ from noise distributions) using equation

$$\Delta s_{\theta^0}(w,h) = s_{\theta^0}(w,h) - \log kP_n(w)$$

Where $$P_n(w)$$ is the noise distribution. With the digits for each classes calculated, TensorFlow use the digits to compute softmax loss for binary classification (log loss in logistic regression) for each of the classes, and add these losses together as the final NCE loss.

However, its implementation is conceptually wrong because the ratio of noise to real data $$k$$ is different to the number of classes $$n$$ sampled from noise distributions. TensorFlow NCE does not provide a variable for the noise to data ratio, and implicitly assumes $$n=k$$ which I think is conceptually incorrect.

The original NCE papers skipped the derivations of the proof a lot so that it is really hard to understand NCE. To understand the math about NCE easier, I have a blog post on this annotating the math from the NCE papers:

College sophomore or above should be able to understand it.

[I've added this answer as I think others miss the main theoretical gist.]

Firstly, NCE and Negative Sampling (NS) serve different purposes:

• NS is a generic trick used to train a classifier if you only have training samples from one `positive' class (e.g. labelled $$y\!=\!1$$);
• NCE is a method to learn parameters $$\theta$$ of a model $$p_m(x;\theta)$$ of a true data distribution $$p_d(x)$$.

So their purposes are different: NS learns to approximate a conditional label distribution $$p(y|x)$$, NCE approximates $$p_d(x)$$. Since NCE uses negative samples (or a noise distribution) to learn $$p_m(x|\theta)$$ it can be seen as a case of NS.

NS is generic as it can be used just to train the classifier (e.g. in Knowledge Graph link prediction), to learn embeddings/representations (e.g. word2vec), or as a step in NCE. NCE is a special case of NS where $$p_n(x)$$ is not just sampled from, but the actual density $$p_n(x)$$ must be computed.

Simple explanation of NCE:

NCE is used to estimate the parameters $$\theta$$ of a modelled data distribution $$p_m(x;\theta)$$ by learning a classifier (optimised w.r.t. $$\theta$$) that distinguishes true data samples from artificially generated noise samples $$x\!\sim\! p_n(x)$$. When the classifier is optimised, the corresponding $$\theta^*$$ gives the desired distribution $$p_m(x;\theta^*)$$.

A naturally intuitive description of how this is different from Negative Sampling.

NS is not as clearly defined as NCE, but typically refers to when artificially generated samples, $$x\!\sim\!p_n(x)$$, labelled $$y\!=\!0$$ (i.e. $$p_n(x)\!\equiv\!p(x|y\!=\!0)$$) are used to train a classifier $$f(x;\theta)$$ that distinguishes them from positive samples, $$x\sim p_d(x)\!\equiv\!p(x|y\!=\!1)$$, i.e. once trained $$f(x;\theta)\!\approx\!p(y\!=\!1|x)$$.

If the classifier uses the sigmoid function $$\sigma(t) \!=\! (1\!+\!e^{-t})^{-1}$$, i.e. $$f(x;\theta) \!=\! \sigma(g(x;\theta)$$), then implicitly $$g(x;\theta) \!\approx\! \log\tfrac{p(y=1|x)}{p(y=0|x)} \!=\! \log\tfrac{p(x|y=1)p(y=1)}{p(x|y=0)p(y=0)} \!=\! \log\tfrac{p_d(x)}{p_n(x)k}$$, where $$k\!=\!\tfrac{p(y=0)}{p(y=1)}$$. Whilst this reformulation may not be of interest generally, it explains e.g. why word2vec embeddings learn pointwise mutual information (PMI).

In NCE, $$\theta$$ is used to specifically parameterise $$p_d(x)$$ (not the whole log ratio), i.e. $$p_m(x;\theta)\!\approx\!p_d(x)$$. Making that substitution and reversing the above equation gives a formula that approximates $$p(y\!=\!1|x)$$ in terms of $$p_m(x;\theta), p_n(x)$$ and $$k$$ that fits into a binary cross entropy loss function. When that loss is minimised $$p_m(x;\theta)$$ is the best approximation of $$p_d(x)$$.

Intuition for negative sampling in word2vec: we randomly sample from the vocabulary V and update only those as |V| is large and this offers a speedup. Correct if wrong.

In my view this isn't quite right. Yes, negative sampling seems to have been implemented as a trick to reduce computation time, but it fundamentally changes the maths and means the model parameters - which become word embeddings - learn different values (PMI) due to the choice of noise distribution (see Levy & Goldberg (2014)). That seems to have been an important aspect of why word2vec embeddings work as they do.

When to use which one and how to decide? Is NCE better than NS? Better in what manner?

Hopefully it's clear that you do the same thing in either case (generate negative samples, train a classifier). Whether you call it NCE or NS depends on what you want from it. A key choice affecting performance in all cases is the negative sampling distribution. The NCE paper looks into this but (I believe) the optimal choice is an open research question.

Basically, this is selecting a sample from the true distribution which consists of the true class and some other noisy class labels. Then taking the softmax over it.

This is based on sampling words from true distribution and noise distribution.

Here the basic Idea is to train logistic regression classifier which can separate the samples obtained from true distribution and sample obtained from noise distribution. Remember When we are talking about the samples obtained from the true distribution we are talking about only one sample which is the true class obtained from the model distribution.

Here I have explained about NCE loss and how it differ from the NCE loss .

Noise Contrastive Estimation : Solution for expensive Softmax .

• While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. Jul 19, 2017 at 6:35

In simple words, the NCE is just a multi-label classification loss function with only 1 positive label and k sampled negative ones.

Illustration of multilabel classification: 