fastText,智慧與美貌並重的文本分類及向量化工具

 2018-06-06 12:00:46.0




fastText的起源

fastText是FAIR(Facebook AIResearch) 在2016年推出的一款文本分類與向量化工具。它的官網(fasttext.cc)上是這樣介紹的:

 

FastText is an open-source, free, lightweightlibrary that allows users to learn text representations and text classifiers.It works on standard, generic hardware. Models can later be reduced in size toeven fit on mobile devices.

 

fastText開源、免費、輕量級,適用於文本分類和文本向量化表示場景,運行於標準硬件環境。裁剪壓縮過的模型甚至可以輕鬆跑在移動設備上。

 

fastText最驚豔的地方在於,和最前沿深度神經網絡模型相比,它在分類精度等指標毫不遜色的情況下,把訓練和推斷速度降低了幾個數量級!按Facebook的報告,在普通多核CPU上,10億詞的文本訓練時間小於10分鐘,50萬句子分到31.2萬類別用時小於1分鐘。

 

下面這張圖可以清楚地看到這一點,深度模型天級的訓練時間被壓榨到了秒級!

 

 

簡單介紹一下fastText的主要作者,這位高顏值的Facebook科學家Tomas Mikolov小哥。他2012年到2014年就職於Google,隨後跳到了Facebook至今。

 

 

他名揚天下的,主要是以下三篇重要論文:


1.Efficient Estimation of WordRepresentation in Vector Space, 2013 —— 這篇是word2vec的開蒙之作;

2.Distributed Representations ofSentences and Documents, 2014 —— 這篇將詞向量的思想擴展到了段落和文檔上;

3.Enriching Word Vectors withSubword Information, 2016 —— 這篇和fastText相關,引入了詞內的n-gram信息,豐富了詞向量的語義。


fastText能夠做到效果好,速度快,主要依靠兩個祕密武器:一是利用了詞內的n-gram信息(subword n-gram information),二是用到了層次化Softmax迴歸(Hierarchical Softmax)的訓練trick。我們分別介紹一下。


Subword n-gramlnformation


在fastText的工作之前,大部分的文本向量化的工作,都是以詞彙表中的獨立單詞作爲基本單元來進行訓練學習的。這種想法非常自然,但也會帶來如下的問題:


· 低頻詞、罕見詞,由於在語料中本身出現的次數就少,得不到足夠的訓練,效果不佳;

· 未登錄詞,如果出現了一些在詞典中都沒有出現過的詞,或者帶有某些拼寫錯誤的詞,傳統模型更加無能爲力。


fastText引入了subword n-gram的概念來解決詞形變化(morphology)的問題。直觀上,它將一個單詞打散到字符級別,並且利用字符級別的n-gram信息來捕捉字符間的順序關係,希望能夠以此豐富單詞內部更細微的語義。我們知道,西方語言文字常常通過前綴、後綴、字根來構詞,漢語也有單字表義的傳統,所以這樣的做法聽起來還是有一定的道理。

 

舉個例子。對於一個單詞「google」,爲了表達單詞前後邊界,我們加入<>兩個字符,即變形爲「 」。假設我們希望抽取所有的tri-gram信息,可以得到如下集合:G = { }。在實踐中,我們往往會同時提取單詞的多種n-gram信息,如2/3/4/5-gram。這樣,原始的一個單詞google,就被一個字符級別的n-gram集合所表達。

 

在訓練過程中,每個n-gram都會對應訓練一個向量,而原來完整單詞的詞向量就由它對應的所有n-gram的向量求和得到。所有的單詞向量以及字符級別的n-gram向量會同時相加求平均作爲訓練模型的輸入。

 

從實驗效果來看,subword n-gram信息的加入,不但解決了低頻詞未登錄詞的表達的問題,而且對於最終任務精度一般會有幾個百分點的提升。唯一的問題就是由於需要估計的參數多,模型可能會比較膨脹。不過,Facebook也提供了幾點壓縮模型的建議:

 

· 採用hash-trick。由於n-gram原始的空間太大,可以用某種hash函數將其映射到固定大小的buckets中去,從而實現內存可控;

· 採用quantize命令,對生成的模型進行參數量化和壓縮;

· 減小最終向量的維度。


需要注意的是以上幾種方法都會以一定的精度損失爲代價,尤其是維度的壓縮,具體可以實踐中再權衡。


Hierarchical Softmax


另一個效率優化的點是所謂的層次化Softmax。

 

Softmax大家都比較熟悉,它是邏輯迴歸(logisticregression)在多分類任務上的推廣,是我們訓練的神經網絡中的最後一層。一般地,Softmax以隱藏層的輸出h爲輸入,經過線性和指數變換後,再進行全局的歸一化處理,找到概率最大的輸出項。當詞彙數量V較大時(一般會到幾十萬量級),Softmax計算代價很大,是O(V)量級。

 

層次化的Softmax的思想實質上是將一個全局多分類的問題,轉化成爲了若干個二元分類問題,從而將計算複雜度從O(V)降到O(logV)。

 

每個二元分類問題,由一個基本的邏輯迴歸單元來實現。如下圖所示,從根結點開始,每個中間結點(標記成灰色)都是一個邏輯迴歸單元,根據它的輸出來選擇下一步是向左走還是向右走。下圖示例中實際上走了一條「左-左-右」的路線,從而找到單詞w₂。而最終輸出單詞w₂的概率,等於中間若干邏輯迴歸單元輸出概率的連乘積。


 


至此,我們還剩下兩個問題,一是如何構造每個邏輯迴歸單元的輸入,另一個是如何建立這棵用於判斷的樹形結構。


邏輯迴歸單元的參數


每個邏輯迴歸單元中,sigmoid函數所需的輸入實際上由三項構成,如下公式所示:



記號說明如下:


1. ⟦x⟧是一個特殊的函數,如果下一步需要向左走其函數值定義爲1,向右則取-1。在訓練時,我們知道最終輸出葉子結點,並且從根結點到葉子結點的每一步的路徑也是確定的。

2. v' 是每個內部結點(邏輯迴歸單元)對應的一個向量,這個向量可以在訓練過程中學習和更新。

3. h 是網絡中隱藏層的輸出。


因此,我們以隱藏層的輸出、中間結點對應向量以及路徑取向函數爲輸入,相乘後再經過sigmoid函數,得到每一步邏輯迴歸的輸出值。


霍夫曼樹的構造


Hierarchical Softmax採用的樹型結構實際上是一棵二叉霍夫曼樹。

 

霍夫曼樹是在解決通信編碼過程中引入的。在通信過程中,需要將字符信息編碼成爲0/1二進制串。顯然,給出現頻繁的字符較短的編碼,出現較少的字符以較長的編碼,是最經濟的方案。通過一棵霍夫曼樹的構造,我們讓越頻繁的字符離根結點越近,使得最終的通信編碼最短。

 

霍夫曼樹的構造步驟如下:

 

 

在做Hierarchical Softmax之前,我們需要先利用所有詞彙(類別)及其頻次構建一棵霍夫曼樹。這樣,不同詞彙(類別)作爲輸出時,所需要的判斷次數實際上是不同的。越頻繁出現的詞彙,離根結點越近,所需要的判斷次數也越少。從而使最終整體的判斷效率更高。


fastText和傳統CBOW模型對比


這裏假設你對word2vec的CBOW模型比較熟悉,我們來小結一下CBOW和fastText的訓練過程有什麼不同。下面兩張圖分別對應CBOW和fastText的網絡結構圖。

 


兩者的不同主要體現在如下幾個方面:

 

· 輸入層:CBOW的輸入是目標單詞的上下文並進行one-hot編碼,fastText的輸入是多個單詞embedding向量,並將單詞的字符級別的n-gram向量作爲額外的特徵;

· 從輸入層到隱藏層,CBOW會將上下文單詞向量疊加起來並經過一次矩陣乘法(線性變化)並應用激活函數,而fastText省略了這一過程,直接將embedding過的向量特徵求和取平均;

· 輸出層,一般的CBOW模型會採用Softmax作爲輸出,而fastText則採用了Hierarchical Softmax,大大降低了模型訓練時間;

· CBOW的輸出是目標詞彙,fastText的輸出是文檔對應的類標。


小結


fastText已經在雲腦科技內部多個項目中得到了實踐運用,包括短文本分類任務、實體識別消歧任務、同義近義簡稱別名挖掘任務、推薦系統中的文本向量化特徵提取等等。

 

實踐經驗表明,fastText更適用於樣本數量大、類別標籤多的任務,一般能夠得到很好的效果,大多數情況下強於傳統的BOW + LR/SVM分類器。更重要的是,訓練效率非常之高。


參考資料


1. 1607.01759Bag of Tricks for Efficient Text Classification

2. 1607.04606Enriching Word Vectors with Subword Information

3. [1411.2738]word2vec Parameter Learning Explained

4. 技術乾貨丨fastText原理及實踐 - 雲+社區 - 騰訊雲


作者介紹


數據系統負責人 黃頌


北京大學計算機碩士,超過13年的數據及算法實踐經驗。

曾在微軟亞洲研究院(MSRA)從事搜索引擎技術研發、軟件安全數據挖掘工作。

愛幫網初創成員,帶領團隊在LBS數據挖掘和推薦算法上做到行業頂尖水平。

美麗說初創成員,高級架構師,負責搭建公司數據團隊及商業智能平臺,提供市場營銷及用戶增長策略支持,抓住流量紅利實現了用戶量快速增長。

對算法和金融等行業的結合,有着濃厚興趣和實戰經驗。

文章來源:機器之心