自己動手寫word2vec (一):主要概念和流程

word2vec 是 Google 於 2013 年開源推出的一個用於獲取詞向量(word vector)的工具包,它簡單、高效,因此引起了很多人的關注。我在看了@peghoty所寫的《word2vec中的數學以後》(個人覺得這是很好的資料,各方面知識很全面,不像網上大部分有殘缺),為了加深理解,自己用Python實現了一遍。貼在我的github上


系列所有帖子
自己動手寫word2vec (一):主要概念和流程
自己動手寫word2vec (二):統計詞頻
自己動手寫word2vec (三):構建Huffman樹
自己動手寫word2vec (四):CBOW和skip-gram模型


1.單詞的向量化表示

所謂的word vector,就是指將單詞向量化,將某個單詞用特定的向量來表示。將單詞轉化成對應的向量以後,就可以將其應用於各種機器學習的演算法中去。一般來講,詞向量主要有兩種形式,分別是稀疏向量和密集向量。

所謂稀疏向量,又稱為one-hot representation,就是用一個很長的向量來表示一個詞,向量的長度為詞典的大小N,向量的分量只有一個1,其他全為0,1的位置對應該詞在詞典中的索引[1]。舉例來說,如果有一個詞典[“麵條”,”方便麵”,”獅子”],那麼“麵條”對應的詞向量就是[1,0,0],“方便麵”對應的詞向量就是[0,1,0]。這種表示方法不需要繁瑣的計算,簡單易得,但是缺點也不少,比如長度過長(這會引發維數災難),以及無法體現出近義詞之間的關係,比如“麵條”和“方便麵”顯然有非常緊密的關係,但轉化成向量[1,0,0]和[0,1,0]以後,就看不出兩者有什麼關係了,因為這兩個向量相互正交。當然了,用這種稀疏向量求和來表示文件向量效果還不錯,清華的長文字分類工具THUCTC使用的就是此種表示方法

至於密集向量,又稱distributed representation,即分散式表示。最早由Hinton提出,可以克服one-hot representation的上述缺點,基本思路是通過訓練將每個詞對映成一個固定長度的短向量,所有這些向量就構成一個詞向量空間,每一個向量可視為該空間上的一個點[1]。此時向量長度可以自由選擇,與詞典規模無關。這是非常大的優勢。還是用之前的例子[“麵條”,”方便麵”,”獅子”],經過訓練後,“麵條”對應的向量可能是[1,0,1,1,0],而“方便麵”對應的可能是[1,0,1,0,0],而“獅子”對應的可能是[0,1,0,0,1]。這樣“麵條”向量乘“方便麵”=2,而“麵條”向量乘“獅子”=0 。這樣就體現出麵條與方便麵之間的關係更加緊密,而與獅子就沒什麼關係了。這種表示方式更精準的表現出近義詞之間的關係,比之稀疏向量優勢很明顯。可以說這是深度學習在NLP領域的第一個運用(雖然我覺得並沒深到哪裡去)

回過頭來看word2vec,其實word2vec做的事情很簡單,大致來說,就是構建了一個多層神經網路,然後在給定文字中獲取對應的輸入和輸出,在訓練過程中不斷修正神經網路中的引數,最後得到詞向量。

2.word2vec的語言模型

所謂的語言模型,就是指對自然語言進行假設和建模,使得能夠用計算機能夠理解的方式來表達自然語言。word2vec採用的是n元語法模型(n-gram model),即假設一個詞只與周圍n個詞有關,而與文字中的其他詞無關。這種模型構建簡單直接,當然也有後續的各種平滑方法[2],這裡就不展開了。

現在就可以引出其他資料中經常提到的CBOW模型skip-gram模型了。其實這兩個模型非常相似,核心部分程式碼甚至是可以共用的。CBOW模型能夠根據輸入周圍n-1個詞來預測出這個詞本身,而skip-gram模型能夠根據詞本身來預測周圍有哪些詞。也就是說,CBOW模型的輸入是某個詞A周圍的n個單詞的詞向量之和,輸出是詞A本身的詞向量;而skip-gram模型的輸入是詞A本身,輸出是詞A周圍的n個單詞的詞向量(對的,要迴圈n遍)。

3.基於Hierarchical Softmax的模型

理論上說,無論是CBOW模型還是skip-gram模型,其具體的實現都可以用神經網路來完成。問題在於,這樣做的計算量太大了。我們可以簡略估計一下。首先定義一些變數的含義[3]
(1) n : 一個詞的上下文包含的詞數,與n-gram中n的含義相同
(2) m : 詞向量的長度,通常在10~100
(3) h : 隱藏層的規模,一般在100量級
(4) N :詞典的規模,通常在1W~10W
(5) T : 訓練文字中單詞個數

以CBOW為例,輸入層為n-1個單詞的詞向量,長度為m(n-1),隱藏層的規模為h,輸出層的規模為N。那麼前向的時間複雜度就是o(m(n-1)h hN) = o(hN) 這還是處理一個詞所需要的複雜度。如果要處理所有文字,則需要o(hNT)的時間複雜度。這個是不可接受的。同時我們也注意到,o(hNT)之中,h和T的值相對固定,想要對其進行優化,主要還是應該從N入手。而輸出層的規模之所以為N,是因為這個神經網路要完成的是N選1的任務。那麼可不可以減小N的值呢?答案是可以的。解決的思路就是將一次分類分解為多次分類,這也是Hierarchical Softmax的核心思想。舉個栗子,有[1,2,3,4,5,6,7,8]這8個分類,想要判斷詞A屬於哪個分類,我們可以一步步來,首先判斷A是屬於[1,2,3,4]還是屬於[5,6,7,8]。如果判斷出屬於[1,2,3,4],那麼就進一步分析是屬於[1,2]還是[3,4],以此類推,如圖中所示的那樣。這樣一來,就把單個詞的時間複雜度從o(h*N)降為o(h*logN),更重要的減少了記憶體的開銷。

這裡寫圖片描述
從上面可以看到從輸入到輸出,中間是一個樹形結構,其中的每一個節點都完成一個二分類(logistic分類)問題。那麼就存在一個如何構建樹的問題。這裡採用huffman樹,因為這樣構建的話,出現頻率越高的詞所經過的路徑越短,從而使得所有單詞的平均路徑長度達到最短。

4.word2vec的大概流程

至此,word2vec中的主要元件都大概提到過一遍,現在應該把它們串起來,大概瞭解一下word2vec的執行流程。

(1) 分詞 / 詞幹提取和詞形還原。 中文和英文的nlp各有各的難點,中文的難點在於需要進行分詞,將一個個句子分解成一個單詞陣列。而英文雖然不需要分詞,但是要處理各種各樣的時態,所以要進行詞幹提取和詞形還原。
(2) 構造詞典,統計詞頻。這一步需要遍歷一遍所有文字,找出所有出現過的詞,並統計各詞的出現頻率。
(3) 構造樹形結構。依照出現概率構造Huffman樹。如果是完全二叉樹,則簡單很多,後面會仔細解釋。需要注意的是,所有分類都應該處於葉節點,像下圖顯示的那樣[4]

這裡寫圖片描述

(4)生成節點所在的二進位制碼。拿上圖舉例,22對應的二進位制碼為00,而17對應的是100。也就是說,這個二進位制碼反映了節點在樹中的位置,就像門牌號一樣,能按照編碼從根節點一步步找到對應的葉節點。
(5) 初始化各非葉節點的中間向量和葉節點中的詞向量。樹中的各個節點,都儲存著一個長為m的向量,但葉節點和非葉結點中的向量的含義不同。葉節點中儲存的是各詞的詞向量,是作為神經網路的輸入的。而非葉結點中儲存的是中間向量,對應於神經網路中隱含層的引數,與輸入一起決定分類結果。
(6) 訓練中間向量和詞向量。對於CBOW模型,首先將詞A附近的n-1個詞的詞向量相加作為系統的輸入,並且按照詞A在步驟4中生成的二進位制碼,一步步的進行分類並按照分類結果訓練中間向量和詞向量。舉個栗子,對於綠17節點,我們已經知道其二進位制碼是100。那麼在第一個中間節點應該將對應的輸入分類到右邊。如果分類到左邊,則表明分類錯誤,需要對向量進行修正。第二個,第三個節點也是這樣,以此類推,直到達到葉節點。因此對於單個單詞來說,最多隻會改動其路徑上的節點的中間向量,而不會改動其他節點。

這裡寫圖片描述

參考文獻

[1]word2vec中的數學,p14
[2]統計自然語言處理,宗成慶,第五章
[3]word2vec中的數學,p13
[4]Huffman樹詞條