推薦系統從零單排系列(六)—Word2Vec優化策略層次Softmax與負採樣
【導讀】前兩篇文章中介紹了兩種基本的Word2Vec模型：CBOW，Skip-gram。今天將詳細介紹使得Word2Vec落地的兩種優化策略：層次Softmax與負採樣策略。最後在文末將給出Word2Vec實踐代碼，以及小編整理的一些資料方便同學深入研究。
只收藏不點贊的都是臭流氓！ （傲嬌臉）
Hierarchical Softmax
原始的Word2Vec使用softmax得到最種的辭彙概率分布，辭彙表往往包含上百萬個單詞，如果針對輸出中每一個單詞都要用softmax計算概率的話，計算量是非常大的。解決辦法之一就是Hierarchical Softmax。相比於原始的Softmax直接計算每個單詞的概率，Hierarchical Softmax使用一顆二叉樹來得到每個單詞的概率。被驗證的效果最好的二叉樹類型就是霍夫曼樹：
霍夫曼樹中有V-1個中間節點，V個葉節點。葉節點與單詞表中V個單詞一一對應。首先根據單詞出現的頻率構造一顆霍夫曼樹，出現頻率高的單詞霍夫曼編碼就短，更加靠近根節點。
原來的Word2Vec模型結構會被改變，隱藏層後直接和霍夫曼樹中每一個非葉節點相連，如下圖所示（相當於輸出層中只有V-1個神經元節點）。然後再每一個非葉節點上計算二分概率（也就是用Sigmoid函數進行激活），這個概率是指從當前節點隨機遊走的概率，可以任意指定是向左遊走的概率，還是向右遊走的概率。從根節點到目標單詞的路徑是唯一的，將中間非葉節點的遊走概率相乘就得到了最終目標單詞的概率。
這樣只用計算樹深度個輸出節點的概率就可以得到目標單詞的概率。霍夫曼樹的深度基本是logV，所以此時的計算複雜度就降為了O(logV)。另外，高頻詞非常接近樹根，其所需要的計算次數將進一步減少，這也是使用霍夫曼樹的一個優點。此時的目標函數為：
L(w)是樹深度；n(w,j)表示從根節點到目標單詞w的路徑上第j個節點；ch(n)表示節點n的孩子節點。中間的尖括弧表示是否成立的判斷，結果無非是+1，或-1。注意sigmoid的特性：
Sigmoid(-x) = 1 - Sigmoid(x)Vwi表示輸入單詞的input vector，Vn』表示霍夫曼樹中間節點的output vector。
Negative Sampling
Negative Sampling（簡稱NEG）是NCE（Noise Contrastive Estimation）的簡化版本，目的是提高訓練速度並改善所得詞向量的質量。與Hierarchical Softmax相比，NEG不再採用複雜的霍夫曼樹，而是利用相對簡單的隨機負採樣，能大幅提升性能，因而可以作為Hierarchical Softmax的一種替代。
針對一個樣本(WI, W)，Negative Sampling的目標函數如下所示：
現在的目標就是利用logistic regression，從帶有雜訊（負樣本）的目標中找到正樣本（Wo），其中K是負樣本採樣的數量。作者指出在小訓練集上，k取5-20比較合適；大訓練集上k取2-5即可。和SGD的思想非常像，不再是利用所有的負樣本進行參數的更新，而是只利用負採樣出來的K個來進行loss的計算，參數的更新。只不過SGD每次只用一個樣本，而不是K個。
負樣本採樣服從分布Pn(W)，經過試驗發現unigram分布效果最好，如下：
其中f(wi)表示單詞wi在語料中出現的頻率。3/4這個值是通過實驗發現的經驗值。
Subsampling of Frequent Wrods
大語料集中，像the a in之類的單詞出現頻率非常高几乎是很多單詞的上下文，造成其攜帶的信息非常少。對這些單詞進行下採樣不僅可以加快訓練速度還可以提高低頻詞訓練詞向量的質量。
為了平衡高頻與低頻詞，對訓練集中的單詞按照下述公式決定是否保留該單詞：
其中f(wi)是單詞wi出現的頻率，t憑經驗值取10的-5次方。該公式保證出現頻率超過t的單詞將被下採樣，並且不會影響原有的單詞的頻率相對大小（rank）。先生成（target， context），比如（love，[ I,China]），然後依次遍歷他們，小於P(wi)的訓練樣本將被從訓練樣本中去掉。
片語Phrases
片語並不能簡單的將單詞分開解釋，而是應該看做一個整體，例如「New York」。把這樣的片語看成是一個整體，用特殊的符號代替不會過多的增加辭彙表的大小，但效果是很顯著的。
實踐
又到了快樂的code時間，完整代碼見github：
https://github.com/gutouyu/ML_CIA/blob/master/Embedding/Word2Vec.py歡迎star~
使用的是Pytorch最新的穩定版本，關鍵代碼如下：
計算word頻率，用於下採樣
word_frequency = np.array(list(word_count.values()))
word_frequency = word_frequency / word_frequency.sum()
word_sample = 1 - np.sqrt(T / word_frequency)
word_sample = np.clip(word_sample, 0, 1)
word_sample = {wc[0]: s for wc, s in zip(word_count.items(), word_sample)}
生成訓練樣本，並完成下採樣：
class PermutedSubsampleedCorpus(Dataset):
def __init__(self, data, word_sample):
self.data = []
for iword, owords in data:
if np.random.rand() > word_sample[iword]:
self.data.append((iword, owords))
def __len__(self):
return len(self.data)
def __getitem__(self, item):
iword, owords = self.data[item]
# 按列拼接形成batch的
return (iword, owords)
data = []
for target_pos in range(CONTEXT_SIZE, len(raw_data) - CONTEXT_SIZE):
context = []
for w in range(-CONTEXT_SIZE, CONTEXT_SIZE + 1):
if w == 0:
continue
context.append(raw_data[target_pos + w])
data.append((raw_data[target_pos], context))
dataset = PermutedSubsampleedCorpus(data, word_sample)
Skip-gram with negative sampling模型代碼，時刻關注變數的維度變化：
class SkipGramNegativeSample(nn.Module):
def __init__(self, vocab_size, embedding_size, n_negs):
super(SkipGramNegativeSample, self).__init__()
self.ivectors = nn.Embedding(vocab_size, embedding_size)
self.ovectors = nn.Embedding(vocab_size, embedding_size)
self.ivectors.weight.data.uniform_(- 0.5/embedding_size, 0.5/embedding_size)
self.ovectors.weight.data.zero_()
self.n_negs = n_negs
self.vocab_size = vocab_size
def forward(self, iwords, owords):
# iwords: (batch_size)
# owords: (batch_size, context_size * 2)
batch_size = iwords.size()[0]
context_size = owords.size()[-1] # 兩邊的context之和
nwords = torch.FloatTensor(batch_size, context_size * self.n_negs).uniform_(0, self.vocab_size - 1).long()
ivectors = self.ivectors(iwords).unsqueeze(2) # (batch_size, embeding_dim, 1)
ovectors = self.ovectors(owords) # (batch_size, context_size, embedding_dim)
nvectors = self.ovectors(nwords).neg() #(batch_size, context_size * n_negs, embedding_dim)
oloss = torch.bmm(ovectors, ivectors).squeeze().sigmoid().log().mean() #(batch_size)
nloss = torch.bmm(nvectors, ivectors).squeeze().sigmoid().log().view(-1, context_size, self.n_negs).sum(2).mean(1) #(batch_size)
return -(oloss + nloss).mean()
訓練模型：
dataloader = DataLoader(dataset, batch_size=5, shuffle=False, num_workers=1)
model = SkipGramNegativeSample(vocab_size, EMBEDDING_DIM, n_negs=5)
optimizer = optim.SGD(model.parameters(), lr=0.1)
def make_context_vectors(context, word_to_ix):
context_ixs = [word_to_ix[w] for w in context]
return torch.tensor(context_ixs, dtype=torch.long)
losses = []
for epoch in range(10):
total_loss = 0
for batch_size, (iword, owords) in enumerate(dataloader):
iword = list(map(lambda x: word_to_ix[x], iword))
iword = torch.tensor(iword, dtype=torch.long)
owords = list(map(list, owords))
owords = np.array(owords).T
myfunc = np.vectorize(lambda x: word_to_ix[x])
owords = list(map(myfunc, owords))
owords = torch.tensor(owords, dtype=torch.long)
model.zero_grad()
loss = model(iword, owords)
loss.backward()
optimizer.step()
total_loss += loss
losses.append(total_loss)
print(losses)
這份代碼只是用來學習的，可以理解Skip-gram以及negative sampling、下採樣等知識點，並不能用於實際生產中，望知悉。在代碼中，要時刻關注每個向量的維度變化，關注訓練集的生成，以及loss的計算方式。
自從用了Pytorch，腰也不疼了，皮膚也光滑了。Hello torch， bye-bye tensorflow.真香~
Word2Vec資料
如果你對Word2Vec感興趣，下面這些資料也許對你會有幫助：
論文
- Distributed Representations of Words and Phrases and their Compositionality (Google 2013)
- Efficient Estimation of Word Representations in Vector Space (Google 2013)
- Word2vec Parameter Learning Explained (UMich 2016)
Code
- Word2Vec源碼，注釋版本
chrisjmccormick/word2vec_commented
- tensorflow實現
https://github.com/zyxue/stanford-cs20si-tensorflow-for-deep-learning-research/blob/master/assignments/01/q3_04_word2vec_visualize.py
博客
- CBOW與Skip-gram比較
卡門：cbow 與 skip-gram的比較
- Hierarchical softmax and negative sampling: short notes worth telling
https://towardsdatascience.com/hierarchical-softmax-and-negative-sampling-short-notes-worth-telling-2672010dbe08
- [ Word embeddings: exploration, explanation, and exploitation (with code in Python)]
https://towardsdatascience.com/word-embeddings-exploration-explanation-and-exploitation-with-code-in-python-5dac99d5d795
- [ Word2Vec Tutorial - The Skip-Gram Model ]
Word2Vec Tutorial - The Skip-Gram Model
- [ Word2Vec Tutorial Part 2 - Negative Sampling ]
Word2Vec Tutorial Part 2 - Negative Sampling
- [秒懂詞向量Word2Vec的本質]
穆文：[NLP] 秒懂詞向量Word2vec的本質
- [ A Beginners Guide to Word2Vec and Neural Word Embeddings ]
A Beginners Guide to Word2Vec and Neural Word Embeddings
課程
- [CS224n: NLP with Deep Learning]
CS 224N | Home
歡迎關注我的專欄，同名公眾號： 機器學習薦貨情報局
還可加我私人微信拉你入群哦~
推薦閱讀：
