[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.
