负采样（Negative Sampling）理论与推导

分类: 词向量与表示学习 · 难度: 进阶 · 关联讲座: L02

负采样（Negative Sampling）理论与推导

负采样是 Word2Vec 训练中最关键的加速技巧——将 softmax 的 $O(|V|)$ 计算复杂度降至 $O(K)$ 。本文从动机出发，完整推导负采样的目标函数与梯度，并通过数值示例和理论分析说明其为什么有效。

1. 完整推导

📐 负采样（Negative Sampling）的完整推导

动机：Full softmax 每次更新需要遍历整个词表 $V$ （ $|V|$ 可达数十万），计算代价 $O(|V|)$ 。能否只更新少量词的向量？

核心思想：将多分类问题转化为二分类问题——区分”真实的上下文词对”和”随机拼凑的词对”。

第 1 步：定义二分类目标

对于一个真实的 (中心词, 上下文词) 对 $(c, o)$ ，我们希望：

$P(\text{真实对} | c, o) = \sigma(u_o^T v_c) = \frac{1}{1 + \exp(-u_o^T v_c)}$

对于随机采样的”负样本”词 $k$ ，我们希望：

$P(\text{非真实对} | c, k) = 1 - \sigma(u_k^T v_c) = \sigma(-u_k^T v_c)$

第 2 步：构建目标函数

对每个正样本 $(c, o)$ ，采样 $K$ 个负样本 $\{n_1, n_2, \ldots, n_K\}$ ，最大化：

$J = \log \sigma(u_o^T v_c) + \sum_{k=1}^{K} \log \sigma(-u_{n_k}^T v_c)$

取负号即为要最小化的损失。

第 3 步：对 $v_c$ 求梯度

利用 sigmoid 的性质 $\sigma'(x) = \sigma(x)(1-\sigma(x))$ 和 $\frac{d}{dx}\log\sigma(x) = 1 - \sigma(x)$ ：

$\frac{\partial J}{\partial v_c} = (1 - \sigma(u_o^T v_c)) \cdot u_o + \sum_{k=1}^{K} (-1)(1 - \sigma(-u_{n_k}^T v_c)) \cdot u_{n_k}$

化简（利用 $1 - \sigma(-x) = \sigma(x)$ ）：

$= (1 - \sigma(u_o^T v_c)) \cdot u_o - \sum_{k=1}^{K} \sigma(u_{n_k}^T v_c) \cdot u_{n_k}$

第 4 步：对 $u_o$ （正样本）求梯度

$\frac{\partial J}{\partial u_o} = (1 - \sigma(u_o^T v_c)) \cdot v_c$

第 5 步：对 $u_{n_k}$ （负样本）求梯度 $\frac{\partial J}{\partial u_{n_k}} = -\sigma(u_{n_k}^T v_c) \cdot v_c$ 采样分布：负样本按 $P(w) = \frac{f(w)^{3/4}}{\sum_{w'} f(w')^{3/4}}$ 采样，其中 $f(w)$ 是词频。 $3/4$ 次幂使低频词被采到的概率相对提高，避免只采高频词。 计算复杂度：从 $O(|V|)$ 降到 $O(K)$ ，通常 $K = 5\text{-}20$ ，加速数千倍。

2. 目标函数的另一种表述

📐 负采样目标函数推导

问题：完整 softmax 的计算瓶颈在分母 $\sum_{w \in V} \exp(u_w^T v_c)$ ，需要遍历整个词汇表（数十万次）。

解决方案：把预测任务改成二分类——区分真实上下文词（正样本）和随机噪声词（负样本）。

新目标（对于一个 (center, context) 对）：

最大化真实上下文词的出现概率 + 最大化随机词不出现的概率： $J_{neg}(o, c) = \log \sigma(u_o^T v_c) + \sum_{k=1}^{K} \log \sigma(-u_k^T v_c)$

其中 $\sigma(x) = \frac{1}{1+e^{-x}}$ ，负样本 $u_k$ 从噪声分布 $P(w) \propto U(w)^{3/4}$ （unigram 的 3/4 次方，提升低频词被采样的概率）。

为什么有效：

$\sigma(u_o^T v_c)$ 大 → 中心词和上下文词的向量相似（正确）
$\sigma(-u_k^T v_c)$ 大 ↔ $\sigma(u_k^T v_c)$ 小 → 中心词和负样本词的向量不相似（正确）

复杂度：从 $O(V)$ （全词汇表 softmax）降至 $O(K)$ （ $K$ 通常取 5-20）。

3. 数值计算示例

🔢 数值计算：负采样（K=2）

设定：沿用之前的词表，中心词 cat，真实上下文词 dog，负样本为 fish 和 cat 自身。

词	角色	$u_w^T v_\text{cat}$
dog	正样本	$0.7 \times 0.5 + 0.1 \times 0.3 = 0.38$
fish	负样本 1	$0.3 \times 0.5 + 0.5 \times 0.3 = 0.30$
cat	负样本 2	$0.2 \times 0.5 + 0.8 \times 0.3 = 0.34$

Step 1：计算 sigmoid 值：

$\sigma(0.38) = \frac{1}{1+e^{-0.38}} = \frac{1}{1+0.684} = 0.594$

$\sigma(0.30) = \frac{1}{1+e^{-0.30}} = \frac{1}{1+0.741} = 0.574$

$\sigma(0.34) = \frac{1}{1+e^{-0.34}} = \frac{1}{1+0.712} = 0.584$

Step 2：计算目标函数值：

$J = \log(0.594) + \log(1-0.574) + \log(1-0.584)$

$= \log(0.594) + \log(0.426) + \log(0.416)$

$= -0.521 + (-0.854) + (-0.877) = -2.252$ Step 3：计算对 $v_\text{cat}$ 的梯度： $\frac{\partial J}{\partial v_\text{cat}} = (1-0.594) \cdot u_\text{dog} - 0.574 \cdot u_\text{fish} - 0.584 \cdot u_\text{cat}$ $= 0.406 \cdot [0.7, 0.1] - 0.574 \cdot [0.3, 0.5] - 0.584 \cdot [0.2, 0.8]$ $= [0.284, 0.041] - [0.172, 0.287] - [0.117, 0.467]$ $= [-0.005, -0.713]$ 解读：梯度在第二维分量很大（ $-0.713$ ），说明 $v_\text{cat}$ 的第二维需要大幅减小。直觉上，这是因为负样本（fish, cat）的 $u$ 向量在第二维都较大，模型需要让 $v_\text{cat}$ 远离它们。 对比 full softmax：full softmax 需要对所有 $|V|$ 个词计算 softmax 概率再求梯度；负采样只需要 $1 + K = 3$ 个词的 sigmoid 计算。当 $|V| = 100{,}000$ 时，这是 $33{,}000\times$ 的加速。

🔢 SGD 更新一步示例

设定：词汇表 $V = \{\text{the, cat, sat, on, mat}\}$ ， $d = 2$ ，学习率 $\alpha = 0.1$

中心词 “cat”，真实上下文词 “sat”，负样本 “the”（ $K=1$ ）：

$v_{\text{cat}} = [0.5, 0.3]$ ， $u_{\text{sat}} = [0.4, 0.6]$ ， $u_{\text{the}} = [-0.2, 0.1]$

计算损失的梯度：

$s_{pos} = u_{\text{sat}}^T v_{\text{cat}} = 0.4 \times 0.5 + 0.6 \times 0.3 = 0.38$
$s_{neg} = u_{\text{the}}^T v_{\text{cat}} = -0.2 \times 0.5 + 0.1 \times 0.3 = -0.07$
$\frac{\partial J}{\partial v_{\text{cat}}} = -(1 - \sigma(0.38)) u_{\text{sat}} - (- \sigma(-0.07)) u_{\text{the}}$ $= -(1-0.594)[0.4, 0.6] - (-0.517)[-0.2, 0.1]$ $\approx [-0.163, -0.244] + [0.103, -0.052]$ $= [-0.060, -0.296]$
更新： $v_{\text{cat}}^{new} = [0.5, 0.3] - 0.1 \times [-0.060, -0.296] = [0.506, 0.330]$

观察： $v_{\text{cat}}$ 向 $u_{\text{sat}}$ 方向移动，远离 $u_{\text{the}}$ 。

4. 为什么负采样有效？

💡 为什么负采样有效？

负采样看起来是一个粗暴的近似——把 softmax 换成了几个 sigmoid，真的靠谱吗？

理论保证：Mikolov et al. (2013b) 和 Goldberg & Levy (2014) 证明，当 $K \to \infty$ 时，负采样的目标函数等价于最大化：

$u_o^T v_c \approx \log \frac{P(\text{共现}|o,c)}{P(\text{独立}|o,c)} = \text{PMI}(o, c) - \log K$

即点积在学习逐点互信息（PMI）——这正是统计 NLP 中衡量词共现强度的经典指标。

直觉理解：

正样本项 $\log\sigma(u_o^T v_c)$ ：推动真实共现词对的向量靠近
负样本项 $\sum \log\sigma(-u_k^T v_c)$ ：推动随机词对的向量远离
两股力平衡后，向量空间自然编码了词的共现模式 为什么 $K=5\text{-}20$ 就够了？ 因为大部分词和中心词都没有关系（随机采的词大概率是负例），少量负样本就足以提供”什么是不相关的”的信号。更多负样本带来的信息增益递减，但计算成本线性增长。经验上：小数据集 $K=5\text{-}15$ ，大数据集 $K=2\text{-}5$ 。

5. 常见误区

⚠️ 负采样的常见误区

误区：负样本随机均匀采样 → 正确：使用 $P(w) \propto f(w)^{3/4}$ 分布。如果均匀采样，罕见词几乎永远不会被选为负样本，导致它们的向量得不到有效训练。 $3/4$ 次幂是实验发现的最优值——比均匀分布更偏向高频词，但没有按词频等比例那么极端。
误区： $K$ 越大越好 → 正确： $K$ 过大会使负样本中意外包含真实上下文词的概率增加（假负例），反而降低性能。而且 $K$ 过大接近 full softmax 的计算量，失去了负采样的意义。
误区：负采样和 softmax 学到的向量一样 → 正确：它们学到的向量不完全相同。负采样优化的是二分类损失（sigmoid），softmax 优化的是多分类损失。在实践中，负采样在词类比任务上表现与 softmax 相当甚至更好，但在需要精确概率估计的任务中 softmax 更合适。

⚠️ 常见误区

误区：负采样是近似算法，会导致词向量质量下降 → 正确：负采样改变了优化目标，但优化的是更适合词向量学习的目标（二分类而非多分类），实践中效果很好。
误区：SGD 每步只更新一个词向量 → 正确：每步更新窗口内所有词的向量（ $2m$ 个上下文词 + 1 个中心词），以及 $K$ 个负样本的向量。