Word2vec from scratch (Skip-gram & CBOW)

Preface

在自然語言處理領域中，如何透過向量表達一個詞彙，是近幾年非常火熱的議題，在 distributed representation(dense vector) 尚未風行前，大多數的任務都以 1-hot encoding 作為詞彙的表示，其方法得到了高維度的稀疏向量， 雖容易理解、簡單計算，但也帶來許多副作用；直至 2013 年，Thomas Mikolov 等人提出了 word2vec，word2vec 引用了一個概念，作者導入了1957年 J. R. Firth 提出的想法，要充分地理解一個詞彙的語意，首先要先理解它的上下文資訊。

“You shall know a word by the company it keeps” (J. R. Firth 1957: 11)

舉例來說，給定一個足夠大的語料，「狗」的上下文可能會常出現「跑」、「吠」、「跳」、「動物」等詞，我們如果能透過這些上下文兜出「狗」的詞彙向量，則將「狗」賦予了不同於 1-hot vector 的向量表示。

因此，具有類似上下文的詞彙，將會有相近的語意向量，例如「狗」和「犬」計算餘弦相似度時，其值相較於「狗」和「蛋糕」來得大。

本文針對曾使用過 word2vec 且有基本概念，但對於內部詳細的運作還不太清楚的讀者，進行其原理和數學公式簡單淺白的梳理，希望看完本文的讀者能對 word2vec 有更深一層的認識。

Skip-gram & CBOW

word2vec 提出了兩個方法，Skip-gram 和 CBOW。

Skip-gram 是利用中心詞來預測上下文，如下圖所示，假定「柯文哲」為模型的輸入，則輸出為固定 window 長度的上下文詞彙，如「台北 」、「市長」、「參加」、「大甲」。

台北 w(t-2)/市長 w(t-1)/柯文哲 w(t)/參加w(t+1)/大甲 w(t+2)/媽祖/遶境

CBOW 則是利用上下文來預測中心詞，假定「台北 」、「市長」、「參加」、「大甲」為輸入，則輸出為中心詞彙「柯文哲」。

Skip-gram model

首先來談談 skip-gram ，如下式，給定中心詞 w 和模型參數 θ 要計算上下文 c 出現的機率 p(c|w; θ)，其中 C(w) 表示中心詞 w 周圍的上下文詞彙。

針對所有在語料 Text 的中心詞 w，我們希望能透過更新模型參數 θ，最大化上下文詞彙的出現機率乘積，當訓練逐漸收斂時，便可取出 θ 參數中，代表詞彙向量的部分，如下圖的 W_(VxN)，假定我們有個 V 相異詞彙，每個詞彙有 N 維向量，則它可作為大小 V x N 的詞向量 lookup table ，輸入詞彙索引，便可取出該詞彙的對應向量。

假定下例為唯一的待訓練語料

台北 市長 柯文哲 參加 大甲 媽祖 遶境

中心詞 w = [台北, 市長, 柯文哲, 參加, 大甲, 媽祖, 遶境]

當設定 window size 為 1時，我們可將所有中心詞的上下文都找出來：

C(台北) = [__, 市長] ,

C(市長) = [台北, 柯文哲],

C(柯文哲) = [市長, 參加],

C(參加) = [柯文哲, 大甲],

C(大甲) = [參加, 媽祖],

C(媽祖) = [大甲, 遶境],

C(遶境) = [媽祖, __]

因此我們藉由更新 θ，最大化下面的條件機率連乘積：

argmax (p(市長|台北; θ)p(台北 |市長; θ) p(柯文哲 |市長; θ)p(市長|柯文哲; θ) p(參加|柯文哲; θ) p(柯文哲|參加; θ) p(大甲|參加; θ）p(參加|大甲; θ) p(媽祖|大甲; θ) p(大甲|媽祖; θ)p(遶境|媽祖; θ) p(媽祖|遶境; θ) )

完成訓練後，便可從θ中取出詞向量 matrix。

為方便後續式子的呈現，我們將式子 1 簡化為下列式子 2 ，其中 D 表示中心詞與其對應上下文的所有 pairs (w, c)。

接著我們要將 p(c|w; θ) 此條件機率轉化為模型中參數的實際運作，如式子3，給定某中心詞 w 和模型參數 θ，要計算詞彙 c 的機率。

式子 3 分子的部分，將中心詞向量 v_w 和上下文詞向量 v_c 進行點積 (dot product) 作為指數函數 (e) 的輸入，可以想像的是，若兩個詞向量是接近的，那計算出來的點積將會是較大的純量，反之，若兩向量相差很大，則點積結果會變小；我們知道指數函數 exp(x)，當x越大，則 exp(x) 就越大，因為我們的目標是讓 p(c|w; θ) 機率值越大越好，所以也就是 v_w & v_c 點積越大越好，換句話說，我們的實際目標就是讓中心詞與其上下文向量盡可能的接近。

而 p(c|w; θ) 中的 θ 以式3的分子來說，就是 中心詞 v_w 和 上下文 v_c 所對應的詞向量。

式子 3 分母的部分，我們計算語料中，所有上下文詞彙分別與中心詞彙向量計算點積的總合，因此結合分子，就變成了一個 softmax 函數，透過此函數，可以得到每一個特定上下文詞彙基於中心詞的出現機率，雖然嚴格來說，softmax 輸出值不算是機率，也因為每一個 element 的 softmax 輸出皆介於 0-1 且其總和為 1，因此我們姑且把其輸出值視為發生可能性高低。

仔細觀察一下式子 2 發現，小數的大量連乘積，在實務上會有溢位的風險，因此在處理這類的問題，我們傾向將乘除法想辦法轉換成加減法，高中數學有教， log(a/b) = log(a) – log(b)，因此我們將式子2 取 log，即得到式子4 的結果，亦是 skip-gram 理想上 的目標函數，數學上我們稱之為 maximum log likelihood (最大對數似然估計)。

此外，word2vec 可視為一個淺層網路架構，由於速度的考量，模型中沒有使用到任何的 activation function，因此無任何非線性變換；也因其特點是不斷地採用點積來作為兩向量相似的依據，因此作者將此作法稱之為 log bi-linear model。

這裡值得一提的是，語料中每一個詞彙都有兩種身分，可以是中心詞，也可以是別的中心詞的上下文詞彙，因此在實作上，就如下圖所示 ，word2vec 將每個詞彙都預設了兩個向量(中心詞向量矩陣 W & 上下文向量矩陣 W’)。至於為什麼這樣做，首先是參數更新上，若W & W’ 相同，則必須有機制，能支援兩向量矩陣同步更新。

另外，以 dog 為例，通常文本中，很少會在一個小的 windows 中，有兩個相同詞彙同時出現的情況發生，也就是說 dog 一詞的周圍是 dog 的可能性不高，因此模型肯定會讓 p(dog|dog) 機率越低越好，但若套入上式會發現，v(dog) 與 v(dog) 兩個相同向量的點積其純量肯定是大的，這則會跟 p(dog|dog) 機率越低越好相違背而造成矛盾的現象，因此，word2vec 就將此情境變為 u(dog) & v(dog) 的點積，便不會有上述問題發生。

講到這裡，讀者心理可能會冒出一個疑問，skip-gram 圖和上述的公式具體來說是怎麼結合在一起呢?

我們參考上圖，並將之分為下列幾個步驟來說明:

假設輸入了一個中心詞彙 x_k，其周圍有 C 個上下文詞彙，則…

1. input layer 為中心詞 x_k 的 1-hot vector，維度是 1 x V。
2. 通過預先初始化好的權重 W，W 的大小為相異總字數 V 與詞向量維度 N ，V x N 的矩陣，此 W 訓練完畢後，將成為日後的詞向量矩陣。
3. 完成第二步後， hidden layer 獲得中心詞維度 N 的詞向量。
4. 從 hidden layer 到 Output layer 做了 C 次的前向傳遞，每次的傳遞都與相同的 W’ 權重矩陣相乘產生 V 維的向量 y，這邊的 W’ 表示上下文的詞向量矩陣，但不同於W的是，當詞彙的身分是上下文時，才會對應到此向量；而的 C 表示該中心詞彙的上下文數量，透過 window size 決定，因此總和的大小是 C x V。
5. 將這 C 次所產生的值 y_1 到 y_c 通過 Softmax function 轉換，這裡要注意的是，Softmax 分母的計算是由 y 每一個維度值而來，而非僅透過 y_1 到 y_c 所對應維度，因此我們可以將 y 的每一個維度值視為所有相異詞彙與該中心詞彙的點積，點積越大，機率值就越大。
6. 由於 y_1 到 y_C 皆為 x_k 的中心詞，因此給定中心詞 x_k 我們要最大化 y_1 到 y_C 的條件機率值，而每一個條件機率值就以 Softmax 來模擬。

因此步驟一到步驟六即跟 skip-gram 公式不謀而合，目標是最大化上下文詞彙出現的機率。

Negative Sampling 負面採樣

從錯誤中學習、從失敗中成長，模型除了學習正向的資料外，我們也要同時提供錯誤的資料給模型，並告訴它什麼是對的什麼是錯的。

假定文本中有 10 萬個相異詞彙，如果要按照上述的策略進行模型訓練，那每次計算目標函數的 likelihood ，除了提供正面教材 (中心詞、上下文) pair 給模型外，還要提供其他近 10萬條非上下文詞彙供模型學習，因此我們就要以這10萬筆作為基底作最大似然估計，肯定在訓練速度和記憶體上會是一大挑戰，對於此問題作者提出了 Negative sampling 的概念，也就是說，與其對十萬筆詞彙作運算，我們能不能僅挑選出少量的負面案例，就作為模型學習、訓練的依據。

以下為例，已知文本中詞彙「柯文哲」的上下文不存在如「吠」、「叫」、「動物」等詞彙，我們可以將此組合作為模型的負面教材，讓模型學習到基於某中心詞什麼是正確、合理的上下文，什麼不是。

上下文 : [吠、叫、動物]

中心詞 : 柯文哲。

因此，我們將式子作了一些修改，如式子 5 ， D 表示所有真實出現在語料中(w中心詞、c上下文) pair，給定 w, c，模型要去計算 (c, w) pair真實出現在語料中的機率。

其中 p(D=1|w,c;θ)可視為一種二元分類，即 w, c 是否真實存在於語料、還是是虛造的c並非w的上下文，因此 word2vec 利用 sigmoid 函數，任何數值通過 sigmoid 後，皆會介於 0-1 之間，因此可透過此函數來模擬 (c,w) 是否是真實存在的可能性，若值靠近 1，則表示c是w的上下文，反之，表示 (c,w) 為隨機生成的 pair。

若沒有任何負面訓練資料，則我們的目標函數就如式子 7 所述。

接著我們要將負面的訓練資料一併加入，如下式所示，公式中除了要最大化(w,c) ∈ D 存在於真實文本的機率外，也要最大化 (w, c) ∈ D’ 不存在真實文本的機率，當給定任意一組 (w,c)，已知 p(d=0|w,c)+ p(d=1|w,c)=1，因此，為了式子的簡潔性，可以將 p(d=0|w,c) 統一轉換成 1 – p(d=1|w,c)。

接著如上面介紹，將連機率連乘積取 log 且其機率值使用 sigmoid 函數來表示，就成了式子8最後的數學式。

為簡易表示，我們將 σ()視為 sigmoid 函數，因此最終結果如式子 9。

而該怎麼聰明的從 D’ 中選擇負面採樣的數量，作者也作了一些實驗，從下表可以發現，Negative Sampling 數量在 15 時，所訓練出來的詞向量，在句法和語意的任務上都有較佳的表現。

另一個問題，則是我們該如何進行採樣，參考詞彙分布圖，假設每一個詞彙都有一個固定的長度，且其長度總和為1，我們要基於詞彙的長度，隨機公平的採樣詞彙，作為模型的負面教材。

因此長度越大的詞彙越容易被取樣，而詞彙的長度就套用式子10，計算所有詞彙的出現次數總合為分母，欲計算長度的詞彙出現次數作為分子。

Corpus :台北 市長 柯文哲 參加 大甲 媽祖 遶境

total length : 7/7 = 1

length of 柯文哲 :1/7

probability of 柯文哲 being sampled : 1/7 = 0.1429 = 14.29%

Subsampling of Frequent Words

因為停用詞、功能詞總散布在文本中，若採用上式的作法容易採樣到那些詞彙，那對於語意向量的訓練相對來說是沒有幫助的，因此，如式子11，作者將出現次數取根號 3/4，能有效降低停用詞、功能詞被取樣的機率，實驗顯示，Magic number 3/4 確實對於詞向量的品質有不少的幫助。

如下圖，經過 subsampling 後，bombastic 被取樣的機率約提升了三倍，而高頻詞 is 僅有微幅增加，經 normalize 後可預期 is被採樣的機率將下降，而 Constitution 和 bombastic 被採樣的機率將大幅上升。

Hierarchical Softmax (CBOW)

除了 Negative sampling 外，作者亦提出了一個方法 Hierarchical Softmax ，能快速的縮短訓練所需要的時間。

傳統作法，針對每一筆訓練資料，我們需要花費 10 萬次的計算才得以獲得 likelihood，因此作者試著將輸出層作一些改變，試想如果將 10 萬個節點的輸出，建構一顆二元樹，那時間複雜度將會從 O(n) 降為 O(logn)。

作者利用 霍夫曼编码 (huffman coding) 來建立二元樹，其精神是經由統計每個詞彙的出現頻率，來決定詞彙的編碼，也就是說，當某個詞彙有高的詞頻時，其編碼位元數會較低，因為它很常被訪問，若能降地其編碼位元數，則能有效減輕運算所需時間。

因此每一個詞彙都其代表的編碼，如下圖，假設二元樹中，向右走是0，向左走是1，則 w_2 的編碼則為110。

台北 市長 柯文哲 參加 大甲 媽祖 遶境

我們以 CBOW 為例，模型輸入上下文詞彙 (windows:2)，試著預測中心詞彙是什麼。因此模型將 「台北」、 「市長」 、「參加」 、「大甲」詞向量加總作為輸入，並以中心詞「柯文哲」作為模型的輸出。

假定「柯文哲」的霍夫曼編碼維是 110(w_2)，如上樹狀圖， 編碼 110需要經過三個內部節點才會抵達葉節點，每一個內部節點模型能選擇擇往右(1)或往左走(0)，因此每個節點都有一個可訓練的參數 θ，分別與輸入X_w 點積後作為 sigmoid 函數的輸入，根據 sigmoid 的特性其輸出介於0-1之間，所以，可依據 sigmoid 的輸出值靠近1或靠近0，來決定要往右或往左走 (式子11)。

因此假定 sigmoid 輸出值為內部節點向右走的機率，則式子12 為內部節點向左走的機率。

因為模型在前處理階段，就已完成所有相異詞彙的霍夫曼編碼，因此我們可以很清楚的知道該最大化什麼東西；以「柯文哲 110」為例，在根節點時模型要最大化向左走的機率、第二個內部節點模型要最大化向左走的機率，第三個內部節點模型要最大化向右走的機率。

藉由更新 θ，最大化上述的三個機率條件機率連乘積(式子13)，如此一來，才能讓模型沿著 001 的編碼，順利找到代表「柯文哲 」一詞的葉節點。

條件機率值可有兩種情況如式子14，依照詞彙的編碼而定，若其編碼d為0 則條件機率值 p(d|x,θ)採用σ(xθ)，反之若編碼d為1，p(d|x,θ)採用 1 – σ(xθ)。

因此，條件機率值便可以式子15來表示，當 d 為 0 時，式子後項 [1- σ(xθ)]^d = 1 可忽略不見，當 d 為1時，式子前項 [σ(xθ)]^(1-d)] = 1 也可忽略不見。

最後我們可以將 CBOW Hierarchical Softmax 整理成如式子16，每一筆的訓練資料都將基於中心詞的編碼，走訪霍夫曼樹，假定中心詞編碼為l^w，除了 j=1 為根節點外(沒有方向性)，j=2開始一直到葉節點第l^w步，每一個節點都有其對應的方向，表示需要走左邊或走右邊才可以抵達該節點。

為了簡化計算和避免溢位的風險，我們將對數似然函數的機率乘積取log，從乘積值轉為取其總合。

實務上，模型將預設定的 batch size 的訓練資料，一次性地產生 likelihood value，每一批次所計算出的 likelihood value ，將利用 back propagation 作為參數 θ 更新的依據，我們可將式子16簡化為式子17，此式即為 CBOW Hierarchical Softmax 最終的 log likelihood function。

Conclusion

本文簡述了 word2vec 使用到的兩個核心技術，CBOW 和 Skip-gram，且詳述了 word2vec 訓練優化的兩個技巧，Negative Sampling & Hierarchical Softmax，並直白的梳理其公式的原理。

word2vec 是 NLP 近年內之所以能快速成長的最主要原因，當今作為一名自然語言處理研究者，各式各樣的 NLP 任務為達到 state-of-the-art 成果，皆套用了如 Google BERT 、OpenAI GPT2 等作法，或許 word2vec 已逐漸式微，但我們必須知道，這些高大上的模型背後，仍是基於 word2vec 的概念作延伸，且這些龐大的模型在產生所謂高品質的詞向量前，最初始的詞彙表達，仍是採用如 word2vec & GloVe 方法作為詞彙的初始化，因此其重要性不言而喻。

在 NLP 持續發展的路上，我們必須鑑往知來，充分理解、感受過去偉大的研究發明，才得以站在巨人的肩膀上繼續提出新的貢獻。

References

1. Distributed Representations of Words and Phrases and their Compositionality

2. word2vec Explained: Deriving Mikolov et al.’s Negative-Sampling Word-Embedding Method