In natural language we often wish to model the conditional distribution
over the next word \(w\) in a sentence given the previous words \(c\),
which stands for context. We can model the conditional density using a
real-valued function \(S_{\theta} (w, c)\):
| \(\displaystyle p_{\theta} (w|c) = \frac{\exp
(S_{\theta} (w, c))}{Z_{\theta} (c)} \qquad
Z_{\theta} (c) = \int \exp
(S_{\theta} (w', c)) d w'\) |
(1) |
Intuitively, a particular value of \(w\) is exponentially more likely
(higher density) if \(S_{\theta} (w, c)\) is larger. The denominator
\(Z_{\theta} (c)\) is there to ensure that the probability density
integrates to \(1\):
\(\displaystyle \int p_{\theta} (w|c) d w = \frac{1}{Z_{\theta} (c)}
\int \exp (S_{\theta} (w,
c)) d w = 1\)
Notice that we were able to pull \(Z_{\theta} (c)\) out of the integral
because it is not a function of \(w\).
1Maximum Likelihood
Suppose that for each context \(c\) there is a true data distribution
over next words \(p_d (w|c)\). For each \(c\) we would like to maximize
the log likelihood of the observed \(w\) under our model:
| \(\displaystyle \max_{\theta} E_{p_d (\cdot |c)}
[\log p_{\theta} (w|c)]\) |
(2) |
To optimize this objective we would like to differentiate the expected
log-likelihood:
\begin{eqnarray*}
\frac{d}{d \theta} \mathbb{E}_{p_d (\cdot |c)} [\log
p_{\theta} (w|c)] & = &
\mathbb{E}_{p_d (\cdot |c)} \left[ \frac{d}{d
\theta} \log (\exp (S_{\theta}
(w, c))) \right] - \frac{d}{d \theta}
\log Z_{\theta} (c)\\
& = & \mathbb{E}_{p_d (\cdot |c)} \left[
\frac{d}{d \theta} S_{\theta} (w,
c) \right] - E_{p_{\theta} (\cdot
|c)} \left[ \frac{d}{d \theta} S_{\theta}
(w, c) \right] \hspace{3cm}
\text{(3)}
\end{eqnarray*}
For the second equality we are using:
\begin{eqnarray*}
\frac{d}{d \theta} \log Z_{\theta} (c) & = &
\frac{1}{Z_{\theta} (c)}
\frac{d}{d \theta} \int \exp (S_{\theta} (w,
c)) d w\\
& = & \frac{1}{Z_{\theta} (c)} \int \exp (S_{\theta} (w, c))
\frac{d}{d
\theta} S_{\theta} (w, c) d w\\
& = & \int \frac{\exp
(S_{\theta} (w, c))}{Z_{\theta} (c)} \frac{d}{d
\theta} S_{\theta} (w,
c) d w \hspace{3cm} \text{(4)}\\
& = & E_{p_{\theta} (\cdot |c)}
\left[ \frac{d}{d \theta} S_{\theta} (w, c)
\right]
\end{eqnarray*}
We see from Eq. 4 that the second term of Eq. 3
involves an integral or sum over all possible values of \(w\), which can
be difficult to compute.
2Classifying reals vs fakes
Suppose we have a batch of samples of \(w\) from two different
distributions: one of the samples is from the real distribution \(p_d
(w|c)\), and \(k\) additional samples are from a “noise”
distribution \(p_n (w|c)\). For each sample we attach a label \(D = 1\)
if it is from the real distribution, or \(D = 0\) if it is from the
noise distribution. We want to use our model \(p_{\theta}\) to predict
this label (a binary classification problem). Essentially, the idea
behind noise contrastive estimation (NCE) is to use the model to
differentiate samples from the true data distribution versus those from
the noise distribution.
Since we want our model distribution \(p_{\theta} (w|c)\) to closely
approximate \(p_d (w|c)\), we use \(p_{\theta}\) to write down the
likelihood of each label given \((w, c)\):
\(\displaystyle p (D = 1| w, c) = \frac{p_{\theta} (w|c)}{p_{\theta}
(w|c) + kp_n (w|c)}\)
\(\displaystyle p (D = 0| w, c) = \frac{kp_n (w|c)}{p_{\theta} (w|c) +
kp_n (w|c)}\)
In practice, NCE implementations often assume the partition function \(Z
\equiv 1\), so for the rest of the section we assume
\(\displaystyle p_{\theta} (w|c) = \exp (S_{\theta} (w, c))\)
Then we can rewrite the likelihoods using the sigmoid \(\sigma (x) =
\frac{1}{1 + e^{- x}}\):
\begin{eqnarray*}
p (D = 1| w, c) & = & \frac{1}{1 + \frac{kp_n
(w|c)}{\exp (S_{\theta} (w,
c))}}\\
& = & \frac{1}{1 + \exp (-
(S_{\theta} (w, c) - k \log p_n (w|c)))}\\
& = & \sigma (S_{\theta}
(w, c) - k \log p_n (w|c))\\
& = & \sigma (\Delta (w, c))\\
p (D =
0| w, c) & = & 1 - \sigma (\Delta (w, c))
\end{eqnarray*}
where we have defined
\(\displaystyle \Delta (w, c) = S_{\theta} (w, c) - k \log p_n (w|c)\)
So we can write our maximum likelihood objective for this binary
classification task:
\(\displaystyle \max_{\theta} G (\theta) =\mathbb{E}_{p_d (\cdot |c)}
[\log \sigma (\Delta)] +
k\mathbb{E}_{p_n (\cdot |c)} [\log (1 - \sigma
(\Delta))]\)
As before we differentiate the objective making use of the fact that
\(\sigma' (x) = \sigma (x) (1 - \sigma (x))\) and that \(\frac{d \Delta
(w, c)}{d \theta} = \frac{d}{d \theta} S_{\theta} (w, c)\):
\begin{eqnarray*}
\frac{d G}{d \theta} & = & \mathbb{E}_{p_d (\cdot
|c)} \left[ \frac{d}{d
\theta} \log \sigma (\Delta) \right] +
k\mathbb{E}_{p_n (\cdot |c)} \left[
\frac{d}{d \theta} \log (1 -
\sigma (\Delta)) \right]\\
& = & \mathbb{E}_{p_d (\cdot |c)} \left[
\frac{\sigma (\Delta) (1 - \sigma
(\Delta))}{\sigma (\Delta)} \frac{d
S_{\theta}}{d \theta} \right] -
k\mathbb{E}_{p_n (\cdot |c)} \left[
\frac{\sigma (\Delta) (1 - \sigma
(\Delta))}{(1 - \sigma (\Delta))}
\frac{d S_{\theta}}{d \theta} \right]\\
& = & \mathbb{E}_{p_d (\cdot
|c)} \left[ (1 - \sigma (\Delta)) \frac{d
S_{\theta}}{d \theta}
\right] - k\mathbb{E}_{p_n (\cdot |c)} \left[ \sigma
(\Delta) \frac{d
S_{\theta}}{d \theta} \right]\\
& = & \mathbb{E}_{p_d (\cdot |c)}
\left[ (1 - \sigma (\Delta)) \frac{d
S_{\theta}}{d \theta} \right]
-\mathbb{E}_{p_{\theta} (\cdot |c)} \left[ (1
- \sigma (\Delta))
\frac{d S_{\theta}}{d \theta} \right]
\end{eqnarray*}
At the last equality we are using the fact that:
\begin{eqnarray*}
k\mathbb{E}_{p_n (\cdot |c)} \left[ \sigma (\Delta)
\frac{d S_{\theta}}{d
\theta} \right] & = & k\mathbb{E}_{p_n (\cdot
|c)} \left[ \frac{p_{\theta}
(w|c)}{p_{\theta} (w|c) + kp_n (w|c)}
\frac{d S_{\theta}}{d \theta}
\right]\\
& = & \mathbb{E}_{p_n (\cdot
|c)} \left[ \frac{kp_n (w|c)}{p_{\theta} (w|c)
+ kp_n (w|c)} \frac{d
S_{\theta}}{d \theta} \right]\\
& = & \mathbb{E}_{p_{\theta} (\cdot
|c)} \left[ (1 - \sigma (\Delta))
\frac{d S_{\theta}}{d \theta}
\right]
\end{eqnarray*}
Finally, since by inspecting the definition we can see \(\sigma (\Delta)
\xrightarrow{k \rightarrow \infty} 0\):
\(\displaystyle \frac{d G}{d \theta} \xrightarrow{k \rightarrow \infty}
\mathbb{E}_{p_d (\cdot
|c)} \left[ \frac{d}{d \theta} S_{\theta} (w, c)
\right] - E_{p_{\theta}
(\cdot |c)} \left[ \frac{d}{d \theta} S_{\theta}
(w, c) \right]\)
So if we increase the number of noise samples \(k\) in the batch, our
gradient approaches the original maximum likelihood gradient of Eq 3 asymptotically. Hence we see the motivation for why NCE's
binary classification task is a good approximation for the original
objective in Eq 2.
3Further reading
This blog post and this paper contain good
explanations of noise contrastive estimation, and have some more
detailed derivations for some results.