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?v_w}}$$
于是，上式變為：
$$=\arg \underset{\theta }{\max }\sum _{(w,c)\in D}\log \frac{1}{1+e^{?v_c?v_w}}+\sum _{(w,c)\in D^{\prime }}\log \left(1?\frac{1}{1+e^{?v_c?v_w}}\right)$$

進一步化簡為：
$$=\arg \underset{\theta }{\max }\sum _{(w,c)\in D}\log \frac{1}{1+e^{?v_c?v_w}}+\sum _{(w,c)\in D^{\prime }}\log \left(\frac{1}{1+e^{v_c?v_w}}\right)$$

最終的優化目標即為：
$$\arg \underset{\theta }{\max }\sum _{(w,c)\in D}\log \sigma (v_c?v_w)+\sum _{(w,c)\in D^{\prime }}\log \sigma (?v_c?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 {?}_{\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.