在上一篇中我們講到了基于Hierarchical Softmax的word2vec模型，本文我們我們再來看看另一種求解word2vec模型的方法：Negative Sampling。
1. Hierarchical Softmax的缺點與改進
在講基于Negative Sampling的word2vec模型前，我們先看看Hierarchical Softmax的的缺點。的确，使用霍夫曼樹來代替傳統的神經網絡，可以提高模型訓練的效率。但是如果我們的訓練樣本裡的中心詞w是一個很生僻的詞，那麼就得在霍夫曼樹中辛苦的向下走很久了。能不能不用搞這麼複雜的一顆霍夫曼樹，将模型變的更加簡單呢？
Negative Sampling就是這麼一種求解word2vec模型的方法，它摒棄了霍夫曼樹，采用了Negative Sampling（負采樣）的方法來求解，下面我們就來看看Negative Sampling的求解思路。
2. 基于Negative Sampling的模型概述
既然名字叫Negative Sampling（負采樣），那麼肯定使用了采樣的方法。采樣的方法有很多種，比如之前講到的大名鼎鼎的MC。我們這裡的Negative Sampling采樣方法并沒有MC那麼複雜。
比如我們有一個訓練樣本，中心詞是w,它周圍上下文共有2c個詞，記為 c o n t e x t ( w ) context(w) context(w)。由于這個中心詞w,的确和context(w)相關存在，是以它是一個真實的正例。通過Negative Sampling采樣，我們得到neg個和w不同的中心詞 w i , i = 1 , 2 , . . n e g w i , i = 1 , 2 , . . n e g w_i,i=1,2,..neg_{w_i},i=1,2,..neg wi,i=1,2,..negwi,i=1,2,..neg，這樣 c o n t e x t ( w ) context(w) context(w)和 w i w_i wi就組成了neg個并不真實存在的負例。利用這一個正例和neg個負例，我們進行二進制邏輯回歸，得到負采樣對應每個詞 w i w_i wi對應的模型參數 θ i \theta_{i} θi，和每個詞的詞向量。
從上面的描述可以看出，Negative Sampling由于沒有采用霍夫曼樹，每次隻是通過采樣neg個不同的中心詞做負例，就可以訓練模型，是以整個過程要比Hierarchical Softmax簡單。
不過有兩個問題還需要弄明白：
1）如果通過一個正例和neg個負例進行二進制邏輯回歸呢？
2） 如何進行負采樣呢？
我們在第三節讨論問題1，在第四節讨論問題2.
3. 基于Negative Sampling的模型梯度計算
4. Negative Sampling負采樣方法
現在我們來看看如何進行負采樣，得到neg個負例。word2vec采樣的方法并不複雜，如果詞彙表的大小為V,那麼我們就将一段長度為1的線段分成V份，每份對應詞彙表中的一個詞。當然每個詞對應的線段長度是不一樣的，高頻詞對應的線段長，低頻詞對應的線段短。每個詞w的線段長度由下式決定：
采樣前，我們将這段長度為1的線段劃分成M等份，這裡M>>V，這樣可以保證每個詞對應的線段都會劃分成對應的小塊。而M份中的每一份都會落在某一個詞對應的線段上。在采樣的時候，我們隻需要從M個位置中采樣出neg個位置就行，此時采樣到的每一個位置對應到的線段所屬的詞就是我們的負例詞。
在word2vec中，M取值預設為 1 0 8 10^8 108。
5. 基于Negative Sampling的CBOW模型
有了上面Negative Sampling負采樣的方法和邏輯回歸求解模型參數的方法，我們就可以總結出基于Negative Sampling的CBOW模型算法流程了。梯度疊代過程使用了随機梯度上升法：
輸入：基于CBOW的語料訓練樣本，詞向量的次元大小Mcount，CBOW的上下文大小2c,步長η, 負采樣的個數neg
輸出：詞彙表每個詞對應的模型參數 θ θ θ，所有的詞向量 x w x_w xw
1. 随機初始化所有的模型參數θ，所有的詞向量w
2. 對于每個訓練樣本 ( c o n t e x t ( w 0 ) , w 0 ) (context(w_0),w_0) (context(w0),w0),負采樣出neg個負例中心詞 w i , i = 1 , 2 , . . . n e g w_i,i=1,2,...neg wi,i=1,2,...neg
3. 進行梯度上升疊代過程，對于訓練集中的每一個樣本 ( c o n t e x t ( w 0 ) , w 0 , w 1 , . . . w n e g ) (context(w_0),w_0,w_1,...w_{neg}) (context(w0),w0,w1,...wneg)做如下處理：
6. 基于Negative Sampling的Skip-Gram模型
有了上一節CBOW的基礎和上一篇基于Hierarchical Softmax的Skip-Gram模型基礎，我們也可以總結出基于Negative Sampling的Skip-Gram模型算法流程了。梯度疊代過程使用了随機梯度上升法：
輸入：基于Skip-Gram的語料訓練樣本，詞向量的次元大小Mcount，Skip-Gram的上下文大小2c,步長η, 負采樣的個數neg。
輸出：詞彙表每個詞對應的模型參數θ，所有的詞向量xw
1. 随機初始化所有的模型參數θ，所有的詞向量w
2. 對于每個訓練樣本 ( c o n t e x t ( w 0 ) , w 0 ) (context(w_0),w_0) (context(w0),w0),負采樣出neg個負例中心詞 w i , i = 1 , 2 , . . . n e g w_i,i=1,2,...neg wi,i=1,2,...neg
3. 進行梯度上升疊代過程，對于訓練集中的每一個樣本 ( c o n t e x t ( w 0 ) , w 0 , w 1 , . . . w n e g ) (context(w_0),w_0,w1,...w_{neg}) (context(w0),w0,w1,...wneg)做如下處理：
7. Negative Sampling的模型源碼和算法的對應
這裡給出上面算法和word2vec源碼中的變量對應關系。
在源代碼中，基于Negative Sampling的CBOW模型算法在464-494行，基于Hierarchical Softmax的Skip-Gram的模型算法在520-542行。大家可以對着源代碼再深入研究下算法。
在源代碼中，neule對應我們上面的e, syn0對應我們的xw, syn1neg對應我們的θwi, layer1_size對應詞向量的次元，window對應我們的c。negative對應我們的neg, table_size對應我們負采樣中的劃分數M。
另外，vocab[word].code[d]指的是，目前單詞word的，第d個編碼，編碼不含Root結點。vocab[word].point[d]指的是，目前單詞word，第d個編碼下，前置的結點。這些和基于Hierarchical Softmax的是一樣的。
參考:word2vec原理(三) 基于Negative Sampling的模型