1. 基本概念与问题背景

1.1 大规模分类问题

在自然语言处理中，给定上下文$c$预测单词$w$的条件概率为：
$$P(w|c)=\frac{\exp (s_{\theta }(w,c))}{{\sum }_{w^{\prime }\in V}\exp (s_{\theta }(w^{\prime },c))}$$

当词汇表$|V|$很大时（通常$10^5-10^6$量级），分母计算复杂度$O(|V|)$成为瓶颈。

1.2 解决方案概览

方法	核心思想	数学形式
原始Softmax	精确计算	$\frac{e^{s(w,c)}}{\sum e^{s(w^{\prime },c)}}$
NCE	密度比估计	二分类问题
负采样	近似NCE	简化二分类

2. Negative Contrastive Estimation理论

NCE 是一种基于噪声对比学习的优化方法，它将原始的多类分类问题转化为二分类问题。在 NCE 中，模型试图从噪声样本中区分真实的数据样本。

（二）NCE 的数学原理

NCE 的核心思想是最大化正样本对的似然函数，同时最小化负样本对的似然函数。具体来说，给定一个正样本对 $((c_i,w_i)$ 和 $k$ 个噪声样本 { c j , w ~ i j } \{c_j, \tilde{w}_{ij}\} {cj​,w~ij​}，NCE 的损失函数定义
$$J_{\theta }=-\sum _{w_i\in V}\left[\log P(y=1|c_i,w_i)+\sum _{j=1}^k\log P(y=0|c_i,{\tilde{w}}_{ij})\right]$$
其中
$P(y=1|c_i,w_i)$ 是正样本对的预测概率，$P(y=0|c_i,{\tilde{w}}_{ij})$是负样本对的预测概率。

2.1 基本框架

定义：

• 总样本数：$1+k$
• 数据分布：$p_d(x)=p(x;\theta )$
• 噪声分布：$q(x)$
• 混合分布：$p_m(x)=\frac{1}{k+1}{p}_d(x)+(1-\frac{1}{k+1})q(x)$

采样概率：
$$\begin{array}{r}P(y=1|x,\theta )=\frac{\frac{1}{k+1}{p}_m(x;\theta )}{\frac{1}{k+1}{p}_m(x;\theta )+(1-\frac{1}{k+1})q(x)}\\ =\frac{\frac{1}{k+1}{p}_m(x;\theta )}{\frac{1}{k+1}{p}_m(x;\theta )+(\frac{k}{k+1})q(x)}\\ =\frac{p_m(x;\theta )}{p_m(x;\theta )+kq(x)}\end{array}$$

其中
$$P_m(x|\theta )=\frac{\exp (s_{\theta }(w,c))}{{\sum }_{w^{\prime }\in V}\exp (s_{\theta }(w^{\prime },c))}$$

（【FunRec】Softmax负采样优化）引入一个假设：将分母部分固定为1，实验发现并没有影响模型的性能，此外，通过实验对分母进行统计，发现分母的值真的是以一个较小的方差在1 附近波动，此外，固定为1方便转化为逻辑回归的损失，最终条件概率：

$$P_m(x|\theta )=\exp (s_{\theta }(w,c))=exp(V_w^T{V}_c)$$

正样本的概率表示：
$$\begin{array}{r}P(y=1|x,\theta )=\frac{exp(V_w^T{V}_c)}{exp(V_w^T{V}_c)+kq(x)}\end{array}$$

2.2 损失函数推导

对于原损失函数
$$J_{\theta }=-\sum _{w_i\in V}\left[\log P(y=1|c_i,w_i)+\sum _{j=1}^k\log P(y=0|c_i,{\tilde{w}}_{ij})\right]$$

展开后：

$$J(\theta )=-\sum _{w_i\in V}\left[\frac{exp(V_w^T{V}_c)}{exp(V_w^T{V}_c)+kq(x)}+\sum _{j=1}^k\log \left(1-\frac{exp(V_{{\tilde{w}}_{ij}}^T{V}_c)}{exp(V_{{\tilde{w}}_{ij}}^T{V}_c)+kq({\tilde{w}}_{ij})}\right)\right]$$

NCE具有很好的理论保证：随着噪音样本数k的增加，NCE的导数趋向于softmax的梯度。有研究证明25个噪音样本足以匹配常规softmax的性能，且有45x的加速。

3. 负采样技术详解

负采样是NCE的一个特例，它通过简化NCE的损失函数来实现更高效的训练。在负采样中，我们不再直接从噪声分布中采样，而是从词汇表中随机选择负样本，从而减少计算复杂度。

3.1 从NCE到负采样

$p(D=1|c,w;\theta )$ 表示给定中心词 $c$ 和上下文词 $w$ 的正样本概率，$p(D=0|c,w;\theta )$ 表示负样本概率。
$$\begin{array}{rl}优化目标& =\arg \underset{\theta }{\max }\prod _{(w,c)\in D}p(D=1|c,w;\theta )\prod _{(w,c)\in D^{\prime }}p(D=0|c,w;\theta )\\ & =\arg \underset{\theta }{\max }\prod _{(w,c)\in D}p(D=1|c,w;\theta )\prod _{(w,c)\in D^{\prime }}(1-p(D=1|c,w;\theta ))\\ 取对数后& =\arg \underset{\theta }{\max }\sum _{(w,c)\in D}\log p(D=1|c,w;\theta )+\sum _{(w,c)\in D^{\prime }}\log (1-p(D=1|c,w;\theta ))\end{array}$$

其中，$p(D=1\mid c,w;\theta )$ 可以表示为：
$$p(D=1|c,w;\theta )=\frac{1}{1+e^{-v_c\cdot v_w}}$$
于是，上式变为：
$$=\arg \underset{\theta }{\max }\sum _{(w,c)\in D}\log \frac{1}{1+e^{-v_c\cdot v_w}}+\sum _{(w,c)\in D^{\prime }}\log \left(1-\frac{1}{1+e^{-v_c\cdot v_w}}\right)$$

进一步化简为：
$$=\arg \underset{\theta }{\max }\sum _{(w,c)\in D}\log \frac{1}{1+e^{-v_c\cdot v_w}}+\sum _{(w,c)\in D^{\prime }}\log \left(\frac{1}{1+e^{v_c\cdot v_w}}\right)$$

最终的优化目标即为：
$$\arg \underset{\theta }{\max }\sum _{(w,c)\in D}\log \sigma (v_c\cdot v_w)+\sum _{(w,c)\in D^{\prime }}\log \sigma (-v_c\cdot v_w)$$
​ 事实上，加快 Word2vec训练速度的方法还有 Hierarchical softmax（层级 softmax），但实现较为复杂，且最终效果没有明显优于负采样方法，因此较少采用

4. 算法实现细节

4.1 负采样算法流程

1. 输入：正样本对$(w,c)$，负采样数$k$
2. 采样负例： { c 1 ′ , . . . , c k ′ } ∼ q ( c ′ ) \{c'_1,...,c'_k\} \sim q(c') {c1′​,...,ck′​}∼q(c′)
3. 计算损失：
   $$\mathcal{L}=-\log \sigma (s(w,c))-\sum _{i=1}^k\log \sigma (-s(w,c_i^{\prime }))$$
4. 更新参数：
   $$\theta \leftarrow \theta -\eta {\nabla }_{\theta }\mathcal{L}$$

负采样的优势

负采样的主要优势在于其计算效率。通过减少需要考虑的负样本数量，负采样显著降低了计算复杂度，从而加快了训练速度。此外，负采样在实际应用中表现出色，尤其是在处理大规模数据集时。
事实上，除了负采样，还有其他方法可以加快Word2vec的训练速度，例如Hierarchical softmax（层级softmax）。然而，这些方法的实现较为复杂，且最终效果没有明显优于负采样方法，因此较少采用。

引用

• 【FunRec】Softmax负采样优化
• Gutmann, Michael U., and Aapo Hyvärinen. “Noise-contrastive Estimation of Unnormalized Statistical Models, with Applications to Natural Image Statistics.” The Journal of Machine Learning Research, vol. 13, 2012, pp. 307-361.