Negative Sampling

一、什麼是Negative Sampling

Negative Sampling是一種用於訓練神經網路的技術，主要用於解決softmax函數在處理大規模多分類問題時計算複雜度高的問題。在Word2Vec模型中，為了避免對每個可能的上下文或者中心詞計算所有單詞的softmax概率，可以通過負採樣（Negative Sampling）的方式來加速代碼執行速度。

二、Negative Sampling的實現方式

對於所有的上下文和中心詞單詞，我們需要把它們表示為向量形式，比如在Word2Vec中，可以使用詞向量來表示。另外，我們需要使用sigmoid函數來計算每個單詞是否出現在文本序列中的概率。

假設我們有一個單詞w和它的上下文單詞wc1, wc2, …, wcn。為了訓練我們的模型，我們需要把w和每個上下文單詞表示為向量形式。假設w的向量為v_w，上下文單詞wc1的向量為v_wc1，那麼我們可以使用以下公式計算這兩個向量之間的相似度：

sim(w, wc1) = dot(v_w, v_wc1) / ||v_w|| * ||v_wc1||

其中dot(v_w, v_wc1)是向量v_w和v_wc1的點積（內積），||v_w||和||v_wc1||分別是向量v_w和v_wc1的模長。

接著，我們需要使用sigmoid函數來計算單詞w是否在上下文中出現的概率。

P(wc1 in context of w) = 1 / (1 + exp(-sim(w, wc1)))

然而，這個函數需要計算整個辭彙表中每個單詞作為上下文單詞出現的概率，這是計算複雜度非常高的。因此，我們使用Negative Sampling技術來解決這個問題，即在每個訓練樣本中選擇一部分單詞作為negative的樣本。這些樣本對應於不在上下文中的單詞，我們希望讓神經網路能夠將它們判定為負樣本。為了實現這個過程，我們需要定義一個大小為k的unigram（均勻分布）概率分布。該分布是指從詞庫中隨機選擇k個單詞作為negative樣本的概率，注意，這個分布是按照單詞的詞頻進行歸一化的。

選定unigram分布後，我們可以按以下方式計算正樣本和負樣本的概率：

P(wc in context of w) = 1 / (1 + exp(-sim(w, wc)))
P(neg in context of w) = 1 - P(wc in context of w)

其中，wc是正樣本單詞，neg是負樣本單詞。接著，我們可以定義代價函數來訓練模型，計算正樣本和負樣本對於代價函數的貢獻：

J(w, wc1, ... wcn) = -log(P(wc1, ... wcn in context of w)) - sum_{i=1}^{k}log(P(neg_i in context of w))

最終希望的是將代價函數最小化，使得神經網路可以較好地判斷哪些單詞是上下文單詞，哪些單詞是負樣本。

三、Negative Sampling的代碼實現

下面是利用Negative Sampling的Word2Vec模型的代碼實現，代碼實現了一個簡單的模型，模型使用one-hot編碼的方式來表示單詞，使用隨機梯度下降（SGD）方法進行訓練。代碼實現基於Python和numpy庫。

import numpy as np
import random

class Word2Vec:
    
    def __init__(self, vocab_size, embedding_size):
        self.vocab_size = vocab_size
        self.embedding_size = embedding_size
        self.W = np.random.uniform(-1, 1, (vocab_size, embedding_size))
        self.C = np.random.uniform(-1, 1, (embedding_size, vocab_size))
        
    def train(self, data, window_size, negative_samples, learning_rate):
        num_samples = 0
        total_loss = 0
        for idx, word in enumerate(data):
            # randomly sample a window around word
            start = max(0, idx - window_size)
            end = min(len(data), idx + window_size + 1)
            context_words = set(data[start:idx] + data[idx+1:end])
            for context_word in context_words:
                # update positive example
                sim = np.dot(self.W[word], self.C[:,context_word])
                p = 1 / (1 + np.exp(-sim))
                error = p - 1
                self.W[word] -= learning_rate * error * self.C[:,context_word]
                self.C[:,context_word] -= learning_rate * error * self.W[word]
                
                # randomly sample negative examples
                sampled_words = [word]
                while len(sampled_words) < negative_samples + 1:
                    w = random.randint(0, self.vocab_size - 1)
                    if w not in context_words and w not in sampled_words:
                        sampled_words.append(w)
                        
                # update negative examples
                for neg_word in sampled_words[1:]:
                    sim = np.dot(self.W[neg_word], self.C[:,context_word])
                    p = 1 / (1 + np.exp(-sim))
                    error = p
                    self.W[neg_word] -= learning_rate * error * self.C[:,context_word]
                    self.C[:,context_word] -= learning_rate * error * self.W[neg_word]
                    
                # increment loss and sample counter
                total_loss += -np.log(p)
                num_samples += 1
                
        # return average loss per sample
        return total_loss / num_samples

四、總結

Negative Sampling是加速神經網路處理多分類問題的一種方法，可以用於訓練諸如Word2Vec模型等自然語言處理技術。它通過隨機選擇負採樣樣本，避免了對整個辭彙表計算softmax函數的複雜度高問題，進而提高了代碼的執行速度。在代碼實現上，我們需要設計相應的代價函數和採樣方式。因為Negative Sampling對於高緯度數據應用極為有效，所以在自然語言處理中是非常重要的一種工具。