1. 基本概念与问题背景

1.1 大规模分类问题

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

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

1.2 解决方案概览

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

2. Negative Contrastive Estimation理论

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

（二）NCE 的数学原理

NCE 的核心思想是最大化正样本对的似然函数，同时最小化负样本对的似然函数。具体来说，给定一个正样本对 $c_i, w_i)$ 和 $k$ 个噪声样本 $\{c_j, \tilde{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)$ 是正样本对的预测概率， $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{aligned} 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{aligned}$

其中
$P_m(x|\theta) = \frac{\exp(s_\theta(w,c))}{\sum_{w'\in V}\exp(s_\theta(w',c))}$

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

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

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

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到负采样

$\theta)$ 表示给定中心词 $c$ 和上下文词 $w$ 的正样本概率， $\theta)$ 表示负样本概率。
$\begin{aligned} 优化目标 &= \arg \max_{\theta} \prod_{(w,c) \in D} p(D = 1 | c, w; \theta) \prod_{(w,c) \in D'} p(D = 0 | c, w; \theta)\\ &= \arg \max_{\theta} \prod_{(w,c) \in D} p(D = 1 | c, w; \theta) \prod_{(w,c) \in D'} (1 - p(D = 1 | c, w; \theta))\\ 取对数后&= \arg \max_{\theta} \sum_{(w,c) \in D} \log p(D = 1 | c, w; \theta) + \sum_{(w,c) \in D'} \log (1 - p(D = 1 | c, w; \theta)) \end{aligned}$

其中， $p (D = 1 ∣ c, w; θ)$ 可以表示为：
$\theta) = \frac{1}{1 + e^{-v_c \cdot v_w}}$
于是，上式变为：
$\arg \max_{\theta} \sum_{(w,c) \in D} \log \frac{1}{1 + e^{-v_c \cdot v_w}} + \sum_{(w,c) \in D'} \log \left( 1 - \frac{1}{1 + e^{-v_c \cdot v_w}} \right)$

进一步化简为：
$\arg \max_{\theta} \sum_{(w,c) \in D} \log \frac{1}{1 + e^{-v_c \cdot v_w}} + \sum_{(w,c) \in D'} \log \left( \frac{1}{1 + e^{v_c \cdot v_w}} \right)$

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

4. 算法实现细节

4.1 负采样算法流程

输入：正样本对 $(w, c)$ ，负采样数 $k$
采样负例： $\{c'_1,...,c'_k\} \sim q(c')$
计算损失：
$\mathcal{L} = -\log\sigma(s(w,c)) - \sum_{i=1}^k \log\sigma(-s(w,c'_i))$
更新参数：
$\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.