基于负采样（Negative Sampling）的Skip-gram模型训练算法
题目描述
负采样是Word2Vec工具中用于优化Skip-gram模型训练效率的核心技术。Skip-gram模型的目标是通过中心词预测其上下文词，但传统Softmax输出层的计算成本随词汇表规模线性增长，难以扩展到大规模语料。负采样通过将多分类问题转化为二分类问题，仅采样少量负样本更新参数，显著提升了训练速度。本题目将详解负采样的动机、采样策略定义及梯度推导过程。
解题过程
- 问题建模与原始Skip-gram的缺陷
- 目标函数：给定中心词 \(w_c\)，最大化上下文窗口内所有上下文词 \(w_o\) 的条件概率：
\[ \max \frac{1}{T} \sum_{t=1}^T \sum_{-m \le j \le m, j \neq 0} \log p(w_{t+j} \mid w_t) \]
- 传统Softmax定义：
\[ p(w_o \mid w_c) = \frac{\exp(\mathbf{u}_o^\top \mathbf{v}_c)}{\sum_{i=1}^V \exp(\mathbf{u}_i^\top \mathbf{v}_c)} \]
其中 $ \mathbf{v}_c $ 和 $ \mathbf{u}_o $ 分别表示中心词和上下文词的向量，$ V $ 为词汇表大小。
- 缺陷：计算分母的归一化项需遍历整个词汇表，时间复杂度为 \(O(V)\)，当 \(V\) 达到百万级别时计算代价过高。
- 负采样的核心思想
- 将多分类问题转化为二分类：判断一组词对 \((w_c, w_o)\) 是否来自真实上下文（正样本）或随机组合（负样本）。
- 目标函数重构：
\[ \log \sigma(\mathbf{u}_o^\top \mathbf{v}_c) + \sum_{k=1}^K \mathbb{E}_{w_k \sim P_n(w)} \left[ \log \sigma(-\mathbf{u}_k^\top \mathbf{v}_c) \right] \]
其中 $ \sigma $ 为Sigmoid函数，$ K $ 为负样本数量，$ P_n(w) $ 是负样本采样分布。
- 负样本采样分布的设计
- 使用一元语法分布 \(U(w)\) 的 \(3/4\) 次幂平滑频次，避免高频词主导采样：
\[ P_n(w) = \frac{U(w)^{3/4}}{\sum_{i=1}^V U(w_i)^{3/4}} \]
- 平滑作用：
- 原始频次：\(\text{"the"}\) 出现0.1，"apple"出现0.01
- 平滑后比例：\(0.1^{3/4} : 0.01^{3/4} \approx 0.18 : 0.03\)，降低高频词权重。
- 梯度下降的参数更新
- 损失函数对中心词向量 \(\mathbf{v}_c\) 的梯度：
\[ \frac{\partial J}{\partial \mathbf{v}_c} = \left[ \sigma(\mathbf{u}_o^\top \mathbf{v}_c) - 1 \right] \mathbf{u}_o + \sum_{k=1}^K \left[ \sigma(\mathbf{u}_k^\top \mathbf{v}_c) \right] \mathbf{u}_k \]
- 对正样本上下文词向量 \(\mathbf{u}_o\) 的梯度：
\[ \frac{\partial J}{\partial \mathbf{u}_o} = \left[ \sigma(\mathbf{u}_o^\top \mathbf{v}_c) - 1 \right] \mathbf{v}_c \]
- 对负样本上下文词向量 \(\mathbf{u}_k\) 的梯度：
\[ \frac{\partial J}{\partial \mathbf{u}_k} = \sigma(\mathbf{u}_k^\top \mathbf{v}_c) \mathbf{v}_c \]
- 更新规则：通过梯度下降使正样本的向量内积增大，负样本的内积减小。
- 算法优势总结
- 计算复杂度从 \(O(V)\) 降至 \(O(K+1)\)（\(K\) 通常取5~20），支持大规模语料训练。
- 保留词向量的线性类比关系（如“国王-男人+女人≈女王”）。
- 通过采样分布调整，平衡高频词与低频词的贡献。
关键点说明
负采样的本质是噪声对比估计（Noise-Contrastive Estimation, NCE）的简化版，通过区分真实数据分布与噪声分布，避免全局归一化计算。这种思想后续被扩展至图神经网络、推荐系统等领域，成为处理大规模分类问题的通用范式。