Skip to main content
deleted 6 characters in body
Source Link
Carl
  • 416
  • 2
  • 6

[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/(1\!+\!e^{-t})$$\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 parameterises theparameterise $p_d(x)$ component (not the whole log ratio as a whole), 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.

[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/(1\!+\!e^{-t})$, 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$ specifically parameterises the $p_d(x)$ component (not the log ratio as a whole), 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.

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

added 1259 characters in body
Source Link
Carl
  • 416
  • 2
  • 6

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

  • NCE is for learning parameters $\theta$ of a modelled data distribution $p_m(x|\theta)$.
  • NS is a generic trick used to train a classifier whenif you only have `positive' training samples from one `positive' class (one classe.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: NCENS learns to approximate a conditional label distribution $p(x)$$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 learns.

NS is generic as it can be used just to train the classifier $p(y|x)$(e.g. in Knowledge Graph link prediction), but mechanics are vto learn embeddings/representations (e.similarg. 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.

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 optimalcorresponding $\theta^*$ gives the desired distribution $p_m(x;\theta^*)$.

NS works similarlyis not as clearly defined as NCE, using a distribution of negativebut typically refers to when artificially generated samples (labelled, $0$ if the positive samples are$x\!\sim\!p_n(x)$, labelled $1$$y\!=\!0$ (i.e. $p_n(x)\!\equiv\!p(x|y\!=\!0)$) are used to train a classifier to distinguish the two sets. The difference is$f(x;\theta)$ that the distributiondistinguishes them from positive samples, $p_1(x)$ of$x\sim p_d(x)\!\equiv\!p(x|y\!=\!1)$, i.e. once trained $f(x;\theta)\!\approx\!p(y\!=\!1|x)$.

If the positive class isclassifier uses the sigmoid function $\sigma(t) \!=\! 1/(1\!+\!e^{-t})$, 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 typically wantedbe of interest generally, it explains e.g. why word2vec embeddings learn pointwise mutual information (as in NCEPMI). For example, in Knowledge Graph link prediction

In NCE, $\theta$ specifically parameterises the classifier itself is wanted$p_d(x)$ component (which would not be useful if trained on only one classnot the log ratio as a whole), 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 Word2vec, parametersterms 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 classifier are used as word embeddingsbest approximation of $p_d(x)$.

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, subject (PMI) due to the choice of noise distribution (e.g. seesee Levy & Goldberg (2014)). That seems to behave been an important aspect of why word2vec embeddings work so wellas they do.

So, hopefullyHopefully it's clear that you do pretty much the same thing to start with in either case (generate negative samples, train a classifier). Whether you call it NCE or NS depends on what you do nextwant from it. A key choice affecting performance in bothall cases is the negative sampling distribution. The NCE paper looks into this but (note: you must be able to evaluate $p_n(x)$ for NCEI believe), the bestoptimal choice is pretty much an open research question.

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

  • NCE is for learning parameters $\theta$ of a modelled data distribution $p_m(x|\theta)$.
  • NS is a trick to train a classifier when you only have `positive' training samples (one class).

So their purposes are different: NCE learns $p(x)$, NS learns $p(y|x)$, but mechanics are v.similar.

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 optimal $\theta^*$ gives the desired distribution $p_m(x;\theta^*)$.

NS works similarly, using a distribution of negative samples (labelled $0$ if the positive samples are labelled $1$) to train a classifier to distinguish the two sets. The difference is that the distribution $p_1(x)$ of the positive class is not typically wanted (as in NCE). For example, in Knowledge Graph link prediction, the classifier itself is wanted (which would not be useful if trained on only one class), in Word2vec, parameters of the classifier are used as word embeddings.

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, subject to the noise distribution (e.g. see Levy & Goldberg (2014)). That seems to be an important aspect of why word2vec embeddings work so well.

So, hopefully it's clear that you do pretty much the same thing to start with in either case (generate negative samples, train a classifier). Whether you call it NCE or NS depends on what you do next. A key choice affecting performance in both cases is the negative sampling distribution (note: you must be able to evaluate $p_n(x)$ for NCE), the best choice is pretty much an open research question.

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

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

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^*)$.

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/(1\!+\!e^{-t})$, 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$ specifically parameterises the $p_d(x)$ component (not the log ratio as a whole), 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)$.

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.

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.

added 50 characters in body
Source Link
Carl
  • 416
  • 2
  • 6

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

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

  • NCE is for learning parameters $\theta$ of a modelled data distribution $p_m(x|\theta)$.
  • NS is a trick to train a classifier when you only have `positive' training samples (one class).

So their purposes are different: NCE learns $p(x)$, NS learns $p(y|x)$, but mechanics are v.similar.

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 optimal $\theta^*$ gives the desired distribution $p_m(x;\theta^*)$.

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

NS works similarly, using a distribution of negative samples (labelled $0$ if the positive samples are labelled $1$) to train a classifier to distinguish the two sets. The difference is that the distribution $p_1(x)$ of the positive class is not typically wanted (as in NCE). For example, in Knowledge Graph link prediction, the classifier itself is wanted (which would not be useful if trained on only one class), in Word2vec, parameters of the classifier are used as word embeddings.

I do have an intuitive understanding ofIntuition for negative sampling in the context of word2vec -: we randomly choose some samplessample from the vocabulary V and update only those becauseas |V| is large and this offers a speedup. Please correctCorrect 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, subject to the noise distribution (e.g. see Levy & Goldberg (2014)). That seems to be an important aspect of why word2vec embeddings work so well.

When to use which one and how is that decidedto decide? Is NCE better than Negative SamplingNS? Better in what manner?

HopefullySo, hopefully it's clear that you do pretty much the same thing for bothto start with in either case (generate negative samples, train a classifier), but then. Whether you call it NCE or NS depends on what you are afterdo next. TheA key choice affecting performance in both cases is the negative sampling distribution (note: you must be able to evaluate $p_n(x)$ for NCE), whichthe best choice is pretty much an open research question.

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

  • NCE is for learning parameters $\theta$ of a modelled data distribution $p_m(x|\theta)$.
  • NS is a trick to train a classifier when you only have `positive' training samples (one class).

So their purposes are different: NCE learns $p(x)$, NS learns $p(y|x)$, but mechanics are v.similar.

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 optimal $\theta^*$ gives the desired distribution $p_m(x;\theta^*)$.

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

NS works similarly, using a distribution of negative samples (labelled $0$ if the positive samples are labelled $1$) to train a classifier to distinguish the two sets. The difference is that the distribution $p_1(x)$ of the positive class is not typically wanted (as in NCE). For example, in Knowledge Graph link prediction, the classifier itself is wanted (which would not be useful if trained on only one class), in Word2vec, parameters of the classifier are used as word embeddings.

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.

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, subject to the noise distribution (e.g. see Levy & Goldberg (2014)). That seems to be an important aspect of why word2vec embeddings work so well.

When to use which one and how is that decided? Is NCE better than Negative Sampling? Better in what manner?

Hopefully it's clear that you do pretty much the same thing for both (generate negative samples, train a classifier), but then it depends on what you are after. The key choice is the negative sampling distribution, which is pretty much an open research question.

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

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

  • NCE is for learning parameters $\theta$ of a modelled data distribution $p_m(x|\theta)$.
  • NS is a trick to train a classifier when you only have `positive' training samples (one class).

So their purposes are different: NCE learns $p(x)$, NS learns $p(y|x)$, but mechanics are v.similar.

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 optimal $\theta^*$ gives the desired distribution $p_m(x;\theta^*)$.

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

NS works similarly, using a distribution of negative samples (labelled $0$ if the positive samples are labelled $1$) to train a classifier to distinguish the two sets. The difference is that the distribution $p_1(x)$ of the positive class is not typically wanted (as in NCE). For example, in Knowledge Graph link prediction, the classifier itself is wanted (which would not be useful if trained on only one class), in Word2vec, parameters of the classifier are used as word embeddings.

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, subject to the noise distribution (e.g. see Levy & Goldberg (2014)). That seems to be an important aspect of why word2vec embeddings work so well.

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

So, hopefully it's clear that you do pretty much the same thing to start with in either case (generate negative samples, train a classifier). Whether you call it NCE or NS depends on what you do next. A key choice affecting performance in both cases is the negative sampling distribution (note: you must be able to evaluate $p_n(x)$ for NCE), the best choice is pretty much an open research question.

Source Link
Carl
  • 416
  • 2
  • 6
Loading