Word Embedding & Word2Vec


Posted by Mars.Su on 2020-11-11

本篇概要

在這之前先前我所發佈的文章,都是圍繞『Data Augmentation』這個主題所圍繞,且以NLP這個領域去做探討,那其實一個好的系列文章無論是paper或技術分享,最終都考驗著我們的基礎功,所以接下來開始我會基礎且最重要的底層核心去做分享,包含像是本篇的Word Embedding、Word2Vec,後續依序接到Glove、RNN、Seq2Seq,甚至到Transformer跟Bert,讓讀者可以了解每個歷史的里程碑跟優缺點,當然網路有很多人做多這樣的系列文章,但其實對於我而言有些太淺、有些太深,所以我希望能以平易近人的方式帶大家去看接下來NLP相關的論文。

講到NLP這塊領域,我想大家第一直覺就是Word embedding跟Word2Vec了吧,畢竟對於電腦機器來說,在訓練或是分析的過程無法想人們可以看懂這些『自然語言』。所以要如何利用MLDL的方式來做訓練,第一步一定是要做所為『文字的embedding』,而過往有很多種做法,今天講拿出最重要的兩篇,同時也是由NLP-自然語言處理最重要的貢獻者-Tomas Mikolov所發表的論文,如下:

  1. Efficient Estimation of Word Representations inVector Space
  2. Distributed Representations of Words and Phrases and their Compositionality

在背景的部分,學者主要的目的是在於他想提出一個可以相較過往representation的model,進而提出一個能同時提高準確度跟降低計算成本的model。也許這樣講大家還不是很理解,接著我來一步一步地來說明。

Representation

還記得在前面有提過,電腦機器是無法讀懂人們所溝通的『自然語言』,因此勢必要將這樣的文字作進一步的轉換來讓電腦機器理解甚至是學習。最最最基本的作法,我想如果讀者你是一個分析過資料的人,一定會先想到的是-One Hot Representation,將一個word視為一個簡單的分類來展開,舉例如下

今天假設有一個vocabulary dictionay -> 『拜登』、『為』、『美國』、『新』、『總統』
套用到 One Hot Representation則變成
拜登 -> [1,0,0,0,0]
為 -> [0,1,0,0,0]
美國 -> [0,0,1,0,0]
新 -> [0,0,0,1,0]
總統 -> [0,0,0,0,1]

大家有發現到嗎?如果今天句子或文本ㄧ變長,整個經過One Hot Representation就會變得非常稀疏,則會造成整體的計算成本拉高;除此之外,這樣的representationn是無法表達出句子的語義,套用該例子『拜登為新總統』、『川普為前任總統』,照理來說『拜登』跟『川普』的詞向量距離應該要很近,但用了這個representation的方法,則會每一個詞的距離都一樣,就無法歸類那些詞是相近,更沒有辦法做到『上下文』的概念了。

One Hot Representation也被歸類為Local Represenntation(局部表示),因為會產生維度很大的稀疏矩陣,以及每一個詞向量都是orthogonal的。後來就延伸出了Distribution Representation,其可以解決前一個Representation的問題。

  1. 透過神經元的參數訓練,進而找出相似上下文的關係,進而使向量距離依此拉近或拉遠
  2. 維度不需要因為句子或是vocabulary dictionary的大小而無限擴展,就可以利用較低維度的方式來作為representation,進而降低計算成本。

Why to do?

過往在做word embedding最典型的作法應該是Bengio(2003)所提出的『Neural Network Language Model』(NNLM)的作法了,因為後來提出的model都是基於這個架構作延伸。模型包含了input-layer, hidden-layer, output-layer,其中在hidden-layer這邊計算量特別龐大。所以其做了一些改變,其認為在一句話當中,當前的word會與前n個word相關,進而延伸出『n-gram』的概念,n是由科學家自己定義的數值,以往延伸了像是unigram(n=1); Bi-gram(n=2)-> 前1個word相關;甚至是Tri-gram(n=3)-> 與前2個word相關,透過這樣的方式可以提升大數據上的效能。

簡單的架構圖如下:

該架構有兩個重點,第一,是利用詞特徵矩陣C獲得 word-embbedding;第二,是將表示context的n個詞的詞嵌入拼接起來,通過一個hidden-layer和一個output-layer,最後通過softmax輸出當前的p(wt|context)(當前上下文語義的機率分佈,最大化要預測的那個詞的概率(maximum-likelihood),就可以訓練此模型)。如此一來一方面可以取得language model,同時也可以得到word-embedding。

How to do?

透過前面的Bengio的作法,我們可以發現到其實這樣的計算效率非常地差,因為整個Buttleneck都在其中的non-linear hidden layer。所以Mikolov決定簡化模型,並且將其中的hidden layer拔掉,然而因為模型簡化了,所以對於準確度勢必會造成一定程度的影響,因此學者的解法是用更多的訓練資料來做訓練,盡可能在大量資料下仍有效率地去取得最佳的詞向量。

而本篇論文提出了兩個模型,分別是Continuous Bag of Words(CBOW)Skip-Gram,都只有三層,包含了input-layer、project-layer跟output-layer,其中正因為只有這三層(淺層網路),所以無論哪一個model都是線性model(無任何非線性變換在裡頭),且利用上下文的關係來做訓練,為何這麼說呢?我們來看一下兩種model的架構圖就可以知道了,如下圖

CBOW

CBOW這個架構我們可以看到,其是利用上下文的word來計算目標word的機率,所以就會利用左邊n個word跟右邊n個word來做機率計算,公式如下:

看到這邊想必有人會認為,為什麼機率計算跟詞向量有關呢?其實真正的機率計算不是重點,而是input到projection的權重,怎麼說呢?我們來看一下下面這張圖:

今天一樣拿『拜登為美國新總統的例子』,我們在先前已經知道利用one-hot取的每一個word的one hot representation,那在這邊我們則是利用one-hot來視為這個詞在句子的『位置』,而真正的model透過大量的文本資料來學習到每一個字的上下文特徵,最後會訓練到像是中間的權重值(hidden layer的weight matrix),然而將這樣的權重值與每一個字的one-hoe作相乘,就可以進而取得『總統』對應的詞向量了。而這樣的作法就叫『Embedding Lookup Table』,其中hidden layer的神經元數就是整個embedding的dimension。

Skip-gram

而在Skip-gram這個架構,正洽與CBOW相反,透過輸入一個word來推估上下文word的機率,然而在該模型還加入了一個假設,就是『假設目標詞word與上下文的word有關』,進而去做預測,公式如下:

簡單來說,就是要輸入一個word,進而計算出鄰近word的機率,但其實會遇到一些計算上的效能問題,對應的解決策略是:

  1. 因為有了一個假設『假設目標詞word與上下文的word有關』,所以可以把資料集轉換成一對一的配對
  2. 設定window的參數
    一樣有一句話 : 拜登為美國新總統, window n=3
    (拜) -> (登,為,美)
    (登) -> (拜,為,美,國)
    (為) -> (拜,登,美,國,新)
    (美) -> (拜,登,為,國,新,總)
    (國) -> (登,為,美,新,總,統)
    (新) -> (為,美,國,總,統)
    (總) -> (美,國,新,統)
    (統) -> (國,新,總)
    
    接著再轉換成一對一的配對
    (拜) -> (登)
    (拜) -> (為)
    (拜) -> (美)
    ...
    
    所以透過以上舉例就可以更清楚知道如何在該模型進行訓練了。


小數的大量連乘積,在實務上會有溢位的風險,因此處理這類問題則轉換成log去做處理,來做為 skip-gram 理想上的目標函數,數學上我們稱之為 maximum log likelihood,轉變如下:

藉此作為最大化上下文出現的詞彙機率。

model training performance

關於model訓練效能的部分,學者只花了一天的時間就訓練好16億的單詞資料,最主要降低訓練時間的關鍵有三個,分別如下

Hierarchical Softmax based Huffman tree

簡單概念介紹一下,只要掌握好『路徑』『路徑長度』,如圖所示:

依據上圖所示,路徑意指node之間的通路,路徑長度意指通路中會經過多少分支數。根據上圖,node-a到node-d的路經長度為2,node-a到node-c的路徑長度為1。

而Huffman tree則是將node之間賦予些權重值,然後建立一顆tree來找出WPL(weight path length)值最小的樹來視為最優化的樹,舉例如下:

3.1.a tree的WPL = 7x2 + 5x2 + 2x2 + 4x2 = 36
3.1.b tree的WPL = 7x1 + 5x2 + 2x3 + 4x3 = 35
b tree的WPL值最小,就是huffman-tree。

那如果將這樣的概念整合到softmax,在原本的架構當中,最大的問題在於hidden-layer到output-layer的softmax計算量很大,就要計算每一個word的sofrmax,再去找機率最大的word。再加上架構中input-layer到hidden-layer只是線性轉換,只要把之前所有都要計算的從輸出softmax層的概率計算變成了一顆Huffman Tree,那麼我們的softmax概率計算只需要沿著樹形結構進行就可以了,時間複雜度將會從 O(n) 降為 O(logn)。

真實作法就是將計算每一個word的頻率來進行編碼,當有一個word有高的頻率時,其編碼位元數會較低,因為它很常被訪問,若能降地其編碼位元數,則能有效減輕運算所需時間。

假設二元樹中,向右走是0,向左走是1,則 w_2 的編碼則為110。

所以在計算當中,以上個為例,在root node時模型要最大化向左走的機率、第二個node模型要最大化向左走的機率,第三個node模型要最大化向右走的機率。
藉由更新 參數θ,最大化上述的三個機率條件機率連乘,如此一來,才能讓模型沿著 001 的編碼,順利找到代表target-word的node。

Negative Sampling

簡單來說藉由提供錯誤的資料給模型,並告訴它什麼是對的什麼是錯的。可視為一種二元分類,即字詞w,上下文c 是否真實存在一種關係,因此 word2vec 利用 sigmoid 函數,任何數值通過 sigmoid 後,皆會介於 0-1 之間,因此可透過此函數來模擬 (c,w) 是否是真實存在的可能性,若值靠近 1,則表示 c 是 w 的上下文,反之,表示 (c,w) 為隨機生成的 pair,透過此方式讓model可以在noise distributionn中辨識到真的word。

根據實驗,negative Sampling 數量在15時,所訓練出來的詞向量,在句法和語意的任務上都有較佳的表現。


3/4是在實驗中真實找到合適的值,f(w)為單詞出現的頻率。

SubSampling

如果在negative sampling拿到一些停用詞的話,其實是對於文意上沒有太大的幫助,所以在訓練的過程隨機除了丟棄頻率較高的word之外,也要透過一些參數來提升品質,公式如下

Conclusion

其實不難想像透過word embedding其實可以包含到許多資訊,包含上下文等關聯的資訊,所以相較於傳統的local representation效果來得更好,此外對於模型的訓練除了讓精準度提高之外,同時也要有效率地去做訓練,所以學者除了在這篇提出了新的word2vec的概念之外,同時也提供幾鐘tricking的方式來提升performance,當然這些不只用在NLP,很多模型是可以多方嘗試、融會貫通的,未來若做深度學習的時候,或許這些方式也能一定的程度上的解決所遇到的問題。

Reference

  1. Efficient Estimation of Word Representations inVector Space
  2. Distributed Representations of Words and Phrases and their Compositionality
  3. Word Embedding、詞嵌入、詞向量
  4. Word2vec from Scratch
  5. 霍夫曼樹 -- 分層softmax(Hierarchical Softmax)

#AI #NLP #Word2Vec #WordEmbedding #CBOW #Skip-Gram







Related Posts

關於 React 小書:props children 和容器類組件

關於 React 小書:props children 和容器類組件

[#006] 344. Reverse String

[#006] 344. Reverse String

《嚴防後宮起火-以無聊宅宅的視角來理解版本控制的概念》

《嚴防後宮起火-以無聊宅宅的視角來理解版本控制的概念》


Comments