Negative Sampling 负采样详解[通俗易懂]

在word2vec中，为了简化训练的过程，经常会用到Negative Sampling负采样这个技巧，这个负采样到底是怎么样的呢？之前在我的博文 word2vec算法理解和数学推导 中对于word2vec有了很详细的数学推导，这里主要讲解一下负采样是如何降低word2vec的复杂度的。
首先我们直接写出word2vec的目标函数，假设有一句话： q u e r y = w 1 , w 2 , w 3 , . . , w n query = {w_1},{w_2},{w_3},..,{w_n} query=w1​,w2​,w3​,..,wn​，由n个词组成的一句话，我们需要最大化窗口中上下文词的概率：
arg ⁡ max ⁡ θ ∏ w ∈ q u e r y ∏ c ∈ c w ) P c ∣ w ; θ ) \arg \mathop {\max }\limits_\theta \prod\limits_{w \in query} {\prod\limits_{c \in cw)} {Pc|w;\theta )} } argθmax​w∈query∏​c∈cw)∏​Pc∣w;θ)
这里的$cw)$表示中心词的context words，我们在计算的时候，可以把相乘的元素转换成对数函数：
arg ⁡ max ⁡ θ ∑ w ∈ q u e r y ∑ c ∈ c w ) log ⁡ P c ∣ w ; θ ) \arg \mathop {\max }\limits_\theta \sum\limits_{w \in query} {\sum\limits_{c \in cw)} {\log Pc|w;\theta )} } argθmax​w∈query∑​c∈cw)∑​logPc∣w;θ)
我们把概率函数可以进行展开就可以得到：
arg ⁡ max ⁡ θ ∑ w ∈ q u e r y ∑ c ∈ c w ) log ⁡ e u c ⋅ v w ∑ c ′ ∈ v o c a b e u c ′ ⋅ v w \arg \mathop {\max }\limits_\theta \sum\limits_{w \in query} {\sum\limits_{c \in cw)} {\log \frac{
{
{e^{
{u_c} \cdot {v_w}}}}}{
{\sum\limits_{c’ \in vocab} {
{e^{
{u_{c’}} \cdot {v_w}}}} }}} } argθmax​w∈query∑​c∈cw)∑​logc′∈vocab∑​euc′​⋅vw​euc​⋅vw​​
这个式子可以表示成：
arg ⁡ max ⁡ θ ∑ w ∈ q u e r y ∑ c ∈ c w ) e u c ⋅ v w − log ⁡ ∑ c ′ ∈ v o c a b e u c ′ ⋅ v w ) \arg \mathop {\max }\limits_\theta \sum\limits_{w \in query} {\sum\limits_{c \in cw)} {{e^{
{u_c} \cdot {v_w}}} – \log \sum\limits_{c’ \in vocab} {
{e^{
{u_{c’}} \cdot {v_w}}}} )} } argθmax​w∈query∑​c∈cw)∑​euc​⋅vw​−logc′∈vocab∑​euc′​⋅vw​)
我们可以看到这个式子第二项，因为 c ′ c’ c′要遍历整个词库，所以复杂度非常高，所以我们要简化这一步的计算，减小运算的复杂度。这里的 u c u_c uc​表示$c$的上下文向量， v w v_w vw​表示中心词$w$的向量。
为了减小上述表达式的复杂度，我们不妨改变一下上述概率的表达方式，原来的 p w i ∣ w j ) p{w_i}|{w_j}) pwi​∣wj​) 表示以 w j w_j wj​ 为中心词的时候 w i w_i wi​ 出现的概率，这里我们用 p D = 1 ∣ w i , w j ; θ ) pD = 1|{w_i},{w_j};\theta ) pD=1∣wi​,wj​;θ) 表示 w i w_i wi​ 和 w j w_j wj​ 作为上下文词出现的概率， p D = 0 ∣ w i , w j ; θ ) pD = 0|{w_i},{w_j};\theta ) pD=0∣wi​,wj​;θ) 表示 w i w_i wi​ 和 w j w_j wj​ 不作为上下文词出现的概率。
由上述新的表达式可以写出新的目标函数：
arg ⁡ max ⁡ θ ∏ w , c ) ∈ D p D = 1 ∣ w , c ; θ ) ∏ w , c ) ∈ D ~ p D = 0 ∣ w , c ; θ ) \arg \mathop {\max }\limits_\theta \prod\limits_{w,c) \in D} {pD = 1|w,c;\theta )\prod\limits_{w,c) \in \tilde D} {pD = 0|w,c;\theta )} } argθmax​w,c)∈D∏​pD=1∣w,c;θ)w,c)∈D~∏​pD=0∣w,c;θ)
这里的 $D$ 表示上下文词的集合， D ~ \tilde D D~ 表示非上下文的集合，我们来举一个例子，这里有一句话：“川建国同志是一名优秀的党员”，这句话分词去停之后变成： 川建国 同志 一名 优秀 党员。那么 $D$ 表示上下文集合，我们假设 window size为1，那么可以写出：
$D$ = {川建国，同志)，同志，川建国)，同志，一名)，一名，同志)，一名，优秀)，优秀，一名)，优秀，党员)}
D ~ \tilde D D~ = {川建国，一名)，川建国，优秀)，川建国，党员)，同志，优秀)，同志，党员)，一名，川建国)，一名，党员)，优秀，川建国)，优秀，同志)，党员，川建国)，党员，同志)，党员，一名)}。
上述的 $D$ 表示正样本， D ~ \tilde D D~ 表示负样本。我们可以继续表示上述的目标函数，我们可以吧正负样本的概率表示成sigmoid的表达形式：
arg ⁡ max ⁡ θ ∏ w , c ) ∈ D 1 1 + e − u c ⋅ v w ∏ w , c ) ∈ D ~ 1 − 1 1 + e − u c ⋅ v w ) = arg ⁡ max ⁡ θ ∑ w , c ) ∈ D log ⁡ σ u c ⋅ v w ) + ∑ w , c ) ∈ D ~ log ⁡ σ − u c ⋅ v w ) \arg \mathop {\max }\limits_\theta \prod\limits_{w,c) \in D} {\frac{1}{
{1 + {e^{ – {u_c} \cdot {v_w}}}}}\prod\limits_{w,c) \in \tilde D} {1 – \frac{1}{
{1 + {e^{ – {u_c} \cdot {v_w}}}}})} } = \arg \mathop {\max }\limits_\theta \sum\limits_{w,c) \in D} {\log \sigma {u_c} \cdot {v_w})} + \sum\limits_{w,c) \in \tilde D} {\log \sigma – {u_c} \cdot {v_w})} argθmax​w,c)∈D∏​1+e−uc​⋅vw​1​w,c)∈D~∏​1−1+e−uc​⋅vw​1​)=argθmax​w,c)∈D∑​logσuc​⋅vw​)+w,c)∈D~∑​logσ−uc​⋅vw​)
在词库数量级为 1 0 5 10^5 105的时候，正样本加负样本 D ~ \tilde D D~的数量级可以达到 1 0 10 10^{10} 1010左右，里面绝大部分都是负样本，所以我们需要降低负样本计算中的时间复杂度，这就是Negative Sampling 负采样的核心。负采样就是对于一个中心词，我们从中心词对应的负样本中随机抽取几组来做梯度下降。还是川建国的例子，对于正样本（川建国，同志），我们随机抽取负样本（川建国，一名），（川建国，党员）来做训练，不用全部的负样本都拿来训练，这就是负采样，减小了计算的复杂度。所以，上述的目标函数可以写成：
≈ arg ⁡ max ⁡ θ ∑ w , c ) ∈ D [ log ⁡ σ u c ⋅ v w ) + ∑ c ′ ∈ N w ) log ⁡ σ − u c ′ ⋅ v w ) ] \approx \arg \mathop {\max }\limits_\theta \sum\limits_{w,c) \in D} {[\log \sigma {u_c} \cdot {v_w}) + \sum\limits_{c’ \in Nw)} {\log \sigma – {u_{c’}} \cdot {v_w})} ]} ≈argθmax​w,c)∈D∑​[logσuc​⋅vw​)+c′∈Nw)∑​logσ−uc′​⋅vw​)]
从上述表达式可以看出，负样本我们不需要取所有的都拿来训练，我们只需要每个中心词抽几个负样本就可以了，这样可以大大降低计算的复杂度。这就是word2vec训练过程中的Negative Sampling 负采样技巧，可以大大减小梯度下降的时间复杂度，这就有点像SGD随机梯度下降，就是随机一个样本进行梯度下降，大体的方向还是朝着最低点下降。
接着我来解答一下上述这个表达式，一起来看看是如何进行梯度下降的，首先我们假设：
L θ ) = log ⁡ σ u c ⋅ v w ) + ∑ c ′ ∈ N w ) log ⁡ σ − u c ′ ⋅ v w ) L\theta ) = \log \sigma {u_c} \cdot {v_w}) + \sum\limits_{c’ \in Nw)} {\log \sigma – {u_{c’}} \cdot {v_w})} Lθ)=logσuc​⋅vw​)+c′∈Nw)∑​logσ−uc′​⋅vw​)
接下来我们需要对该表达式求偏导：
∂ L θ ) ∂ u c = σ u c ⋅ v w ) [ 1 − σ u c ⋅ v w ) ] ⋅ v w σ u c ⋅ v w ) = [ 1 − σ u c ⋅ v w ) ] ⋅ v w \frac{
{\partial L\theta )}}{
{\partial {u_c}}} = \frac{
{\sigma {u_c} \cdot {v_w})[1 – \sigma {u_c} \cdot {v_w})] \cdot {v_w}}}{
{\sigma {u_c} \cdot {v_w})}} = [1 – \sigma {u_c} \cdot {v_w})] \cdot {v_w} ∂uc​∂Lθ)​=σuc​⋅vw​)σuc​⋅vw​)[1−σuc​⋅vw​)]⋅vw​​=[1−σuc​⋅vw​)]⋅vw​
∂ L θ ) ∂ u c ′ = σ − u c ′ ⋅ v w ) [ 1 − σ − u c ′ ⋅ v w ) ] ⋅ − v w ) σ − u c ′ ⋅ v w ) = [ σ u c ′ ⋅ v w ) − 1 ] ⋅ v w \frac{
{\partial L\theta )}}{
{\partial {u_{c’}}}} = \frac{
{\sigma – {u_{c’}} \cdot {v_w})[1 – \sigma – {u_{c’}} \cdot {v_w})] \cdot – {v_w})}}{
{\sigma – {u_{c’}} \cdot {v_w})}} = [\sigma {u_{c’}} \cdot {v_w}) – 1] \cdot {v_w} ∂uc′​∂Lθ)​=σ−uc′​⋅vw​)σ−uc′​⋅vw​)[1−σ−uc′​⋅vw​)]⋅−vw​)​=[σuc′​⋅vw​)−1]⋅vw​
∂ L θ ) ∂ v w = σ u c ⋅ v w ) [ 1 − σ u c ⋅ v w ) ] ⋅ u c σ u c ⋅ v w ) + ∑ c ′ ∈ N w ) ∂ − u c ′ ⋅ v w ) [ 1 − σ − u c ′ ⋅ v w ) ] ⋅ − u c ′ ) ∂ − u c ′ ⋅ v w ) = [ 1 − σ u c ⋅ v w ) ] ⋅ u c + ∑ c ′ ∈ N w ) [ σ − u c ′ ⋅ v w ) − 1 ] ⋅ u c ′ \frac{
{\partial L\theta )}}{
{\partial {v_w}}} = \frac{
{\sigma {u_c} \cdot {v_w})[1 – \sigma {u_c} \cdot {v_w})] \cdot {u_c}}}{
{\sigma {u_c} \cdot {v_w})}} + \sum\limits_{c’ \in Nw)} {\frac{
{\partial – {u_{c’}} \cdot {v_w})[1 – \sigma – {u_{c’}} \cdot {v_w})] \cdot – {u_{c’}})}}{
{\partial – {u_{c’}} \cdot {v_w})}} = [1 – \sigma {u_c} \cdot {v_w})] \cdot {u_c} + \sum\limits_{c’ \in Nw)} {[\sigma – {u_{c’}} \cdot {v_w}) – 1] \cdot {u_{c’}}} } ∂vw​∂Lθ)​=σuc​⋅vw​)σuc​⋅vw​)[1−σuc​⋅vw​)]⋅uc​​+c′∈Nw)∑​∂−uc′​⋅vw​)∂−uc′​⋅vw​)[1−σ−uc′​⋅vw​)]⋅−uc′​)​=[1−σuc​⋅vw​)]⋅uc​+c′∈Nw)∑​[σ−uc′​⋅vw​)−1]⋅uc′​
然后整体的梯度下降可以表示成：
u c : = u c + η ∂ L θ ) ∂ u c {u_c}: = {u_c} + \eta \frac{
{\partial L\theta )}}{
{\partial {u_c}}} uc​:=uc​+η∂uc​∂Lθ)​
u c ′ : = u c ′ + η ∂ L θ ) ∂ u c ′ {u_{c’}}: = {u_{c’}} + \eta \frac{
{\partial L\theta )}}{
{\partial {u_{c’}}}} uc′​:=uc′​+η∂uc′​∂Lθ)​
v w : = v w + η ∂ L θ ) ∂ v w {v_w}: = {v_w} + \eta \frac{
{\partial L\theta )}}{
{\partial {v_w}}} vw​:=vw​+η∂vw​∂Lθ)​
这就是word2vec训练过程中的负采样技巧，希望可以通过细致的讲解能够帮助大家深刻地理解负采样，码字不易，如有转载请注明出处，文中如有纰漏，也请各位读者不吝指教，谢谢。