在语言模型中，给定上下文c，要预测单词w: \[ \begin{align} p_{\theta}(w|c) = \frac{u_{\theta}(w,c)}{\sum_{w'\in V}u_{\theta}(w',c)} = \frac{u_{\theta}(w,c)}{Z_{\theta}(c)} \end{align} \] 其中\(u_{\theta}(w,c)=e^{s_{\theta}(w,c)}\), 而 \(Z_{\theta}(c)\)是配分函数（归一化因子）。然而当字典\(V\)非常大时，计算归一化因子非常耗时。
下面，我们令\(\tilde p(w|c)\) 和 \(\tilde p(c)\)代表经验分布，\(q(w)\)代表噪声分布。
Noise contrastive estimation(NCE)
NCE把语言模型的参数估计问题变成一个二分类问题的参数估计。二分类中的两类分别是真实样本和噪声样本。 具体地， 1. 从 \(\tilde p(c)\)中采样\(c\),再从\(\tilde p(w|c)\)中采样作为正样本(d=1)。 2. 从\(q(w)\)采样k个样本作为负样本(d=0)。
如果给定\(c\)，那么\((d,w)\)的分布是 \[ \begin{align} p(0,w|c) = \frac{k}{1+k}q(w) \\\ p(1,w|c) = \frac{1}{1+k}\tilde p(w|c). \end{align} \] 利用条件概率，我们可以把上式变为 \[ \begin{align} p(0|c,w) = \frac{k\times q(w)}{\tilde p(w|c)+k\times q(w)}\\\ p(1|c,w) = \frac{\tilde p(w|c)}{\tilde p(w|c)+k\times q(w)}. \end{align} \]
在NCE中，针对上式，用\(p_{\theta}(w|c)\)近似\(\tilde p(w|c)\)，并且假设 1. \(Z(c)\)是待估计参数 2. 对于参数众多的NN，固定\(Z(c)=1\)有效。
因此，上两式又可写成： \[ \begin{align} p(0|c,w) = \frac{k\times q(w)}{u_{\theta}(w|c)+k\times q(w)}\\\ p(1|c,w) = \frac{u_\theta(w|c)}{u_{\theta}(w|c)+k\times q(w)}. \end{align} \] 由此得到NCE loss: \[ \begin{align} -\mathcal{L}_{\mathrm{NCE}_k} = \sum_{(w,c)\in \mathcal{D}}(\log p(D=1|c,w)+k \mathbb{E}_{\bar w\sim q} \log p(D=0|c,\bar w)) \end{align} \] 对于其中的期望项，我们用MC抽样。
Negative sampling
在上面的框架下，negative sampling实际是指定了另一组条件概率
\[ \begin{align} p(D=0|c,w) = \frac{1}{u_{\theta}(w,c)+1}\\ p(D=1|c,w) = \frac{u_{\theta}(w,c)}{u_{\theta}(w,c)+1}, \end{align} \]
等价于在NCE中令\(k=\lvert V\rvert, q\sim Uniform Distribution\), 此时\(k\times q = 1\).
直接的角度
从另一个角度看,在negative sampling中,我们要做得是最大化正样本概率 \[ \sum_{(w,c)\in \mathcal{D}}\log p(D=1|w,c) \] 和最小化负样本概率 \[ \sum_{(w,c)\notin \mathcal{D}} \log p(D=0|w,c) \] 即 \[ -\mathcal{L}_{\mathrm{NS}} = \sum_{(w,c)\in\mathcal{D}}\log p(D=1|w,c)+\sum_{(w,c)\notin \mathcal{D}}(1-\log(D=1|w,c)) \] 可以直接通过logistic函数建模: \[ p(D=1|w,c)=\frac{1}{e^{-s_{\theta} (w,c)}+1}=\frac{u_{\theta}(w,c)}{u_{\theta}(w,c)+1}\\\ p(D=0|w,c) = \frac{e^{-s_{\theta}(w,c)}}{1+e^{-s_{\theta}(w,c)}}=\frac{1}{u_{\theta}(w,c)+1}, \] 回到了上面的结果。
Candidate Sampling
NCE 和 Negative sampling都属于candidate sampling.
什么是candicate sampling?
还以语言模型为例。对于给定的上下文c,我们需要预测下一个单词w,w的候选集大小是\(|V|\)。在softmax方法中为了计算\(p(W=w|c)\),需要计算出每一个类别\(p(W=w_i|c)\)的概率，这称为是“exanstive”的。在candidate sampling中，为了计算\(p(W=w|c)\)我们只需对\(V\)中的一部分某些\(w_i\)做计算。
candidate sampling的详细一些的介绍可以参见下面的参考文献2.
参考文献：
- arxiv:1410.8251
- What is Candidate Sampling from TensorFlow