21
$\begingroup$

I have been trying hard to understand the concept of negative sampling in the context of word2vec. I am unable to digest the idea of [negative] sampling. For example in Mikolov's papers the negative sampling expectation is formulated as

$$\log \sigma(\langle w,c\rangle ) + k \cdot \mathbb E_{c_N\sim PD}[\log\sigma(−\langle w,c_N\rangle)].$$

I understand the left term $\log \sigma(\langle w,c\rangle)$, but I can't understand the idea of sampling negative word-context pairs.

$\endgroup$
  • 4
    $\begingroup$ It's ridiculous how scattered the documentation is for word2vec. You'll find the negative sampling derivations here: arxiv.org/pdf/1402.3722v1.pdf $\endgroup$ – Alex R. Nov 7 '16 at 6:15
  • $\begingroup$ I went through the explanation you referred and understood the maths behind it. But I am unable to digest the intuition behind sampling. $\endgroup$ – Upendra Kumar Nov 7 '16 at 6:51
  • $\begingroup$ Related: stackoverflow.com/a/27864657 $\endgroup$ – amoeba says Reinstate Monica Jul 24 '18 at 13:51
30
$\begingroup$

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 $k$ 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

[A] (2005) - Contrastive estimation: Training log-linear models on unlabeled data

[B] (2010) - Noise-contrastive estimation: A new estimation principle for unnormalized statistical models

[C] (2008) - A unified architecture for natural language processing: Deep neural networks with multitask learning

[D] (2012) - A fast and simple algorithm for training neural probabilistic language models.

[E] (2013) - Learning word embeddings efficiently with noise-contrastive estimation.


The answer is based on some older notes of mine - I hope they were correct :)

$\endgroup$
  • 2
    $\begingroup$ You mentioned, "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". I'm wondering is this correct? Because some other sources say more frequent words are sampled as negative samples. Essentially, the probability for selecting a word as a negative sample is related to its frequency, with more frequent words being more likely to be selected as negative samples. $\endgroup$ – Tyler傲来国主 Aug 29 '18 at 8:40
  • $\begingroup$ (mccormickml.com/2017/01/11/…)`, also, tensorflow.org/api_docs/python/tf/nn/…. $\endgroup$ – Tyler傲来国主 Aug 29 '18 at 8:40
  • $\begingroup$ BTW, what is the reason for choosing from high or low frequent words as negative samples? Is random sampling from non-context words not good enough? $\endgroup$ – Tyler傲来国主 Aug 30 '18 at 5:27
  • $\begingroup$ @Tyler傲来国主 As I understand it, the less frequent words are more informative as they tend to be context specific. More frequent words tend to be associated with many more other words (take the extreme example "the"). This makes the infrequent words "harder" to get right (you learn faster) and also reduces the chance of picking a word that actually isn't a negative sample (since with large corpora, checking this is expensive and is often left out). $\endgroup$ – drevicko Dec 15 '19 at 22:26
  • $\begingroup$ @drevicko Less frequent words are more informative, but less frequent words being negative samples is less informative. According to Information theory, the higher the probability is, the smaller the self-information is. The event of frequent words being negative samples for a given target word should be of smaller probability, which means higher Quantities of information. $\endgroup$ – Tyler傲来国主 Dec 16 '19 at 6:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.