自然語言處理基礎技術之分詞、向量化、詞性標註

01-25

前段時間，因為項目需求, 開始接觸了NLP，有感自己不是科班出身，很多東西理解不深，於是花時間再讀了一些NLP的經典教程的部分章節，這裡是第一部分，主要包括三小塊：中文分詞、詞向量、詞性標註，這三塊是前段時間項目上有用到過，所以稍做總結與大家分享下，只有更極致地深入了解才能學習得更多。

分詞

分詞可能是自然語言處理中最基本的問題，在英文中，天然地使用空格來對句子做分詞工作，而中文就不行了，沒有特點符號來標誌某個詞的開始或者結尾，而分詞通常對語義的理解是特別重要的，這裡舉個栗子：

下雨天留客天留我不留==>下雨天留客天留我不留 ==>下雨天留客天留我不留

不同的分詞，會造成完全不同的語義理解，其重要性不明而喻，那麼如何把詞從句子中正確地切分出來呢？

我愛北京天安門

分成我愛北京天安門而不是我愛北京天安門？對於計算機而已，天安門和京天安門都是二進位存儲在硬碟或者內存中，沒有其他差別，那麼我們如何讓計算機知道切分為天安門而不是京天安門呢？這裡我們需要提到詞典的幫助，做過NLP的小夥伴通常都知道在一些基礎任務上，詞典的好壞決定最後的性能指標，那麼詞典是如何對分詞起作用的呢？

分詞詞典

最簡單的一個想法，是構造一個常用詞的候選集合，如我、愛、天安門、北京這些詞，然後從句子頭到尾遍歷，如何詞在候選集合中出現過則切分該詞，那麼很容易將我愛天安門分詞為我愛天安門，這樣的邏輯很容易理解，所以接下來就是如何去設計這個候選集合的數據結構，常用的list，當然是可以的，但是很明顯，將一個海量詞的詞典載入，詞典元素的查找還有存儲，如果使用list必然會存在很嚴重的性能問題，如果高效地存儲詞典，還有高效地查詢詞或者短語在詞典中，是這部分分詞最重要的工作，Trie樹在自然語言處理詞庫的存儲和查找上使用的比較普遍。

Trie樹存儲及最長匹配法

Wikipedia上對於Trie樹是這樣解釋的：在計算機科學中，trie，又稱前綴樹或字典樹，是一種有序樹，用於保存關聯數組，其中的鍵通常是字元串。與二叉查找樹不同，鍵不是直接保存在節點中，而是由節點在樹中的位置決定。一個節點的所有子孫都有相同的前綴，也就是這個節點對應的字元串，而根節點對應空字元串。一般情況下，不是所有的節點都有對應的值，只有葉子節點和部分內部節點所對應的鍵才有相關的值。

圖中主要包括三種節點：開始節點、中間節點、和結束節點，利用Trie樹存儲後，根據一條路徑上來存儲一個詞典的詞如上海大學、當然中間節點也可以做為一個詞的結尾來保存如上海，常用的中文字不到5000，大概只需要一個一層分支為2^12的Trie樹來保存所有的中文詞庫信息，樹形的結構，保證了高效的存儲和查找方法，遍歷sentence時，只需要依次向樹下一層訪問，如果無法訪問到下一節點，則切分，如到葉子節點，也切分即可,這就是基於Tire樹的最長匹配法，分詞性能的好壞完全依賴於詞庫。具體的實現可以讀下cppjieba的MPSEGMENT的部分https://github.com/yanyiwu/cppjieba/blob/master/include/cppjieba/MPSegment.hpp，這裡主要關注下Calc和CutByDag即可比較好的理解。 Trie樹的更高效的實現方式包括三數組Trie和二數組Trie，三數組Trie結構包括三個數組結：base,next和check；二數組Trie包含base和check兩個數組，base的每個元素表示一個Trie節點，而check數組表示某個狀態的前驅狀態，高效Trie樹的實現，大家有興趣可以拿源碼來讀讀，這裡我先略過。

基於HMM的分詞方法

基於Trie Tree的分詞方法，主要依賴詞典，通常能滿足大部分場景，但是很多時候也會效果不好，通常會引入概率模型來做分詞，隱性馬爾科夫模型通過引入狀態見的概率轉換，來提高分詞的效果，尤其是對未登錄詞效果要好很多。相信大家在很多場景下聽過HMM，HMM的基本部分包括狀態值集合、觀察值集合、狀態轉移矩陣、條件概率矩陣、初始化概率。這裡稍微解釋下這五個術語在分詞中是啥意思：狀態值序列，這裡一般有四種狀態：B:Begin, M:Middel, E:End, S:single，對於一個待分詞序列：大家都愛北京天安門對應的狀態序列為BESSBEBME，這樣就很容易切分為:BE S S BE BME。觀察值序列，指的就是待切分的詞，如：我愛北京天安門；初始化概率，指的是BMES這四種狀態在第一個字的概率分布情況；狀態轉移矩陣，在馬爾科夫模型裡面十分重要，在HMM中，假設當前狀態只與上一個狀態有關，而這個關係我們可以使用轉移矩陣來表示，在這裡我們是一個44的矩陣；條件概率矩陣，HMM中，觀察值只取決於當前狀態值（假設條件），條件概率矩陣主要建模在BMES下各個詞的不同概率，和初始化概率、狀態轉移矩陣一樣，我們需要在語料中計算得到對應的數據。舉個例子來說明下：如大家都愛北京天安門，我們初始化一個weight[4][9],則數組第一列值為初始化概率條件概率集，依次為：P(B)*P(大|B)，P(E)P(大|E)，P(M)*P(大|M),P(E)*P(大|E)。然後根據轉移概率計算下一個字的狀態概率分布：weight[k][i-1] + _transProb[k][j] +_emitProb[j][sentence[i]]，依次到最後即可，即可計算句子中所有詞的狀態分布，然後確定好邊界對比條件，即可計算出對應狀態序列。 HMM是中文分詞中一種很常見的分詞方法，由上述描述我們知道，其分詞狀態主要依賴於語料的標註，通過語料初始化概率、狀態轉移矩陣、條件概率矩陣的計算，對需要分詞的句子來進行計算，簡單來說，是通過模型學習到對應詞的歷史狀態經驗，然後在新的矩陣中取使用。HMM的模型計算簡單，且通常非常有效，對詞典中未出現詞有比較好的效果。

更複雜的概率分詞模型：CRF

這裡我們提到的CRF，不是廣義的CRF，而是線性鏈式CRF，和HMM一樣，CRF的分詞問題，同樣是一個序列標註問題，將BEMS標註到句子中的不同詞上，相對與HMM，CRF能夠利用更多特徵，數學原理不講啦，都是圖加概率模型的解釋，有興趣的可以去看下

和HMM不同的是，HMM描述的是已知量和未知量的一個聯合概率分布，屬於generative model，而CRF則是建模條件概率，屬於discriminative model。另外CRF特徵更加豐富，可通過自定義特徵函數來增加特徵信息，通常CRF能建模的信息應該包括HMM的狀態轉移、數據初始化的特徵，CRF理論和實踐上通常都優於HMM，CRF主要包括兩部分特徵：一，簡單特徵，只涉及當前狀態的特徵；二，轉移特徵，涉及到兩種狀態之間的特徵；特徵模板的說明可以看下https://taku910.github.io/crfpp/

深度學習在分詞上的嘗試: bi-lstm+crf

基本做法包括：首先，訓練字向量，使用word2vec對語料的字訓練50維的向量，然後接入一個bi-lstm，用來建模整個句子本身的語義信息，最後接入一個crf完成序列標註工作，bi-lstm+crf可以用來完成分詞、詞性標註這類的工作。這個我會在之後做一些相關的嘗試。

詞向量

詞向量是在NLP中比較基礎的一個工作，相對計算機而言，人要聰明的多，人很容易明白幸福和開心是兩個比較近的詞，而計算機要想了解，其實是很難的，而在現代計算機中，對語言的理解顯得越來越重要，如何去表示一個詞，也成為了理解語言的基礎。

one-hot編碼

One-hot編碼可能是最簡單的一種編碼方法，每個詞只在對應的index置1，其他位置都是0，One-hot編碼的問題在於很難做相似度計算，在大規模語料上時，One-hot編碼的長度可能為幾十萬、幾百萬甚至更大，One-hot編碼顯然不行；

矩陣分解方法(LSA)

"You shall know a word by the company it keeps" --Firth, J. R

針對一個詞來說，它的語義由其上下文決定。 LSA使用詞-文檔矩陣，矩陣通常是一個稀疏矩陣，其行代表詞語、其列代表文檔。詞-文檔矩陣表示中的值表示詞在該文章出現的次數，通常，我們可以簡單地通過文檔的出現次數分布來表示對應的詞，但是由於這個矩陣通常是比較稀疏的，我們可以利用矩陣分解，學習到對應詞的低秩表示，這個表示建模了文檔中詞的共現關係,讓相似度的計算變得更加容易。同理，可以也可以在更小粒度上計算矩陣的構建，如設定指定窗口大小，若在該窗口內出現，則數值加一，構建好詞-詞共現矩陣，最終使用如svd這類的矩陣分解方法即可。這類方法明顯的弊病在於當copur過大時，計算很消耗資源，且對於未出現詞或者新文檔不友好。

Word2Vec

關於Word2vec有很多很好的學習資料，大致包括CBOW和Skip-gram模型，其中CBOW的輸入就是上下文的表示，然後對目標詞進行預測;skip-gram每次從目標詞w的上下文c中選擇一個詞，將其詞向量作為模型的輸入。之前有寫Word2vec的文章可以簡單看看Stanford CS224d筆記之Word2Vec.

其中skip-gram主要由包括以下幾塊：

輸入one-hot編碼；
隱層大小為次維度大小；
對於常見詞或者片語，我們將其作為單個word處理；
對高頻詞進行抽樣減少訓練樣本數目；
對優化目標採用negative sampling，每個樣本訓練時，只更新部分網路權重。

Glove

Glove實際上是結合了矩陣分解方法和Window-based method的一種方法，具體看下中公式2-7的推導，Glove的優勢主要在於：

skip-gram利用local context，但是沒有考慮大量詞共現的信息，而文中認為詞共現信息可以在一定程度上解釋詞的語義,通過修改目標函數，z
作者認為相對於原始的額條件概率，條件概率的比值更好地反映出詞之間的相關性,如下圖：

為保證神經網路建模線性結構關係（神經網路容易建模非線性關係，容易歡笑線性關係），對詞差值建模，並且增加一個權重函數；

使用AdaGrad：根據參數的歷史梯度信息更新每個參數的學習率；
為減少模型複雜度，增加假設詞符合冪率分布，可為模型找下界限，減少參數空間；

NNLM

如上圖，早在2001年，Bengio就使用神經網路學習語言模型，中間可輸出詞向量，NNLM和傳統的方法不同，不通過計數的方法對n元條件概率估計，而是直接通過神經網路結構對模型求解，傳統的語言模型通常已知序列，來預測接下來的出現詞的可能性，Bengio提出的nnlm通過將各詞的表示拼接，然後接入剩下兩層神經網路，依次得到隱藏層h和輸出層y，其中涉及到一些網路優化的工作，如直連邊的引入，最終的輸出節點有|V|個元素，依次對應此表中某個詞的可能性，通過正向傳播、反向反饋，輸入層的e就會更新使得語言模型最後的性能最好，e就是我們可拿來的向量化的一種表示。

知識表示

知識表示是最近開始火起來的一種表示方式，結合知識圖譜，實體之間的關係，來建模某個實體的表示，和NLP里的很類似，上下文通常能表徵詞的關係，這裡也是一樣，結合知識圖譜的知識表示，不僅考慮實體間鏈接關係，還可以通過引入更多的如text、image信息來表徵實體，這裡可以關注下清華劉知遠老師的相關工作。

詞性標註

詞性標註的相關學習路線，基本可以重搬下分詞相關的工作，也是一個詞性標註的工作

基於最大熵的詞性標註
基於統計最大概率輸出詞性
基於HMM詞性標註
基於CRF的詞性標註可以稍微多聊一點的是Transformation-based learning，這裡主要參考曼寧那本經典的NLP教材 Transformation-based learning of Tags, Transformation 主要包括兩個部分：a triggering environment, rewrite rule,通過不停統計語料中的頻繁項，若滿足需要更改的閾值，則增加詞性標註的規則。

總結

從來都認為基礎不牢、地動山搖，後面會繼續努力，從源碼、文章上更深了解自然語言處理相關的工作，雖然現在還是半調子水平，但是一定會努力，過去一段時間由於工作相對比較忙，主要還沉淪了一段時間打農藥，後面會多花點時間在技術上的積澱，刷課、讀paper、讀源碼。另外，為了加強自己的coding能力，已經開始用cpp啦（周六寫了500+行代碼），想想都刺激，哈哈哈！！！我這智商夠不夠呀，anyway，加油吧！！！

===================================================================

2017-10-22：個人博客，出了點問題，貌似是因為七牛圖床需要再搞個啥備案，看來以後博客要費啦！！！

哎，真麻煩