預(yù)備知識(shí)
為了更好的理解fastText，我們先來(lái)了解一些預(yù)備知識(shí)。第一個(gè)是BoW模型，也叫做詞袋模型。BoW模型（Bag of words）應(yīng)用于自然語(yǔ)言處理、信息檢索和圖像分類(lèi)等方面。它忽略掉文本的語(yǔ)法和語(yǔ)序等要素（舉個(gè)例子，Bow模型認(rèn)為“我愛(ài)你”和“你愛(ài)我”是相同的，如果我們的世界是一個(gè)BoW模型該有多好，再也不會(huì)出現(xiàn)對(duì)女神單相思的情況了），將其僅僅看作是若干詞匯的集合。BoW 使用一組無(wú)序的單詞（word）來(lái)表達(dá)一段文字或一個(gè)文檔，并且文檔中每個(gè)單詞的出現(xiàn)都是獨(dú)立的。
例如：首先給出兩個(gè)簡(jiǎn)單的文本文檔如下：
John likes to watch movies. Mary likes too.
John also likes to watch football games.
基于上述兩個(gè)文檔中出現(xiàn)的單詞，構(gòu)建如下一個(gè)詞典 (dictionary)：
{“John”: 1, “l(fā)ikes”: 2,”to”: 3, “watch”: 4, “movies”: 5,”also”: 6, “football”: 7, “games”: 8,”Mary”: 9, “too”: 10}
上面的詞典中包含10個(gè)單詞, 每個(gè)單詞有唯一的索引, 那么每個(gè)文本我們可以使用一個(gè)10維的向量來(lái)表示，向量中的元素是詞典中對(duì)應(yīng)的詞語(yǔ)出現(xiàn)的頻數(shù)。如下所示：
[1, 2, 1, 1, 1, 0, 0, 0, 1, 1]
[1, 1,1, 1, 0, 1, 1, 1, 0, 0]
該向量與原來(lái)文本中單詞出現(xiàn)的順序沒(méi)有關(guān)系，而是詞典中每個(gè)單詞在文本中出現(xiàn)的頻數(shù)。
第二個(gè)要介紹的是名為“霍夫曼樹(shù)”的數(shù)據(jù)結(jié)構(gòu)，fastText的速度快，且不會(huì)受到不平衡分類(lèi)問(wèn)題影響的關(guān)鍵因素就是這個(gè)數(shù)據(jù)結(jié)構(gòu)。
霍夫曼編碼樹(shù)，又稱(chēng)最優(yōu)二叉樹(shù)。是一類(lèi)帶權(quán)路徑長(zhǎng)度最短的樹(shù)。假設(shè)有n個(gè)權(quán)值{w1,w2,…,wn}，如果構(gòu)造一棵有n個(gè)葉子節(jié)點(diǎn)的二叉樹(shù)，而這n個(gè)葉子節(jié)點(diǎn)的權(quán)值是{w1,w2,…,wn}，則所構(gòu)造出的帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)就被稱(chēng)為霍夫曼樹(shù)。
帶權(quán)路徑長(zhǎng)度：如果在一棵二叉樹(shù)中共有n個(gè)葉子節(jié)點(diǎn)，用Wi表示第i個(gè)葉子節(jié)點(diǎn)的權(quán)值，Li表示第i個(gè)葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑長(zhǎng)度，則該二叉樹(shù)的帶權(quán)路徑長(zhǎng)度：
WPL=W1?L1+W2?L2+...Wn?Ln
霍夫曼樹(shù)的構(gòu)建步驟如下：
（1）將給定的n個(gè)權(quán)值看做n棵只有根節(jié)點(diǎn)（無(wú)左右孩子）的二叉樹(shù)，組成一個(gè)集合HT，每棵樹(shù)的權(quán)值為該節(jié)點(diǎn)的權(quán)值。
（2）從集合HT中選出2棵權(quán)值最小的二叉樹(shù)，組成一棵新的二叉樹(shù)，其權(quán)值為這2棵二叉樹(shù)的權(quán)值之和。
（3）將步驟2中選出的2棵二叉樹(shù)從集合HT中刪去，同時(shí)將步驟2中新得到的二叉樹(shù)加入到集合HT中。
（4）重復(fù)步驟2和步驟3，直到集合HT中只含一棵樹(shù)，這棵樹(shù)便是霍夫曼樹(shù)。
感覺(jué)還云里霧里？沒(méi)關(guān)系，小編來(lái)舉個(gè)簡(jiǎn)單的例子你就明白了。假設(shè)給定如圖1的四個(gè)帶權(quán)重的節(jié)點(diǎn)A—D，結(jié)點(diǎn)下方為其對(duì)應(yīng)的權(quán)重。
感覺(jué)還云里霧里？沒(méi)關(guān)系，小編來(lái)舉個(gè)簡(jiǎn)單的例子你就明白了。假設(shè)給定如圖1的四個(gè)帶權(quán)重的節(jié)點(diǎn)A—D，結(jié)點(diǎn)下方為其對(duì)應(yīng)的權(quán)重。
首先選出權(quán)重最小的兩個(gè)節(jié)點(diǎn)作為圖2中新樹(shù)的左右子樹(shù)（新樹(shù)即右側(cè)由6、C、A組成的樹(shù)），新樹(shù)根節(jié)點(diǎn)權(quán)重為其左右子樹(shù)權(quán)重之和（即1+5=6）。
然后重復(fù)前一操作，從剩余結(jié)點(diǎn)中選出最小的，與前一個(gè)樹(shù)的根節(jié)點(diǎn)組成新樹(shù)的左右結(jié)點(diǎn)，如圖3所示，新的根節(jié)點(diǎn)權(quán)重為其兩個(gè)子結(jié)點(diǎn)之和（10+6=16）。
在重復(fù)前面的操作，得到圖4的最終樹(shù)。
fastText的霍夫曼樹(shù)葉子結(jié)點(diǎn)對(duì)應(yīng)為最終的label，可以看到，權(quán)重最大的，也就是權(quán)重最大的label，其深度最小，fastText 充分利用了這個(gè)性質(zhì)，使得其速度得以提升。
Huffman編碼（霍夫曼編碼）：
對(duì)每個(gè)字符設(shè)計(jì)長(zhǎng)度不等的編碼，讓出現(xiàn)較多的字符采用盡可能短的編碼。利用霍夫曼樹(shù)求得的用于通信的二進(jìn)制編碼稱(chēng)為霍夫曼編碼。
樹(shù)中從根結(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)都有一條路徑，對(duì)路徑上的各分支約定指向左子樹(shù)的分支表示“0”碼，指向右子樹(shù)的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為各個(gè)葉子節(jié)點(diǎn)對(duì)應(yīng)的字符編碼，即是霍夫曼編碼。以前面的例子為例，各路徑上的編碼如圖5所示。故A結(jié)點(diǎn)的編碼應(yīng)當(dāng)為111，B為10，C為110，D為0。D是權(quán)重最大的結(jié)點(diǎn)，換言之也就是出現(xiàn)最多的結(jié)點(diǎn)，其編碼最短，只有一個(gè)0，而權(quán)重最小的結(jié)點(diǎn)是A，其編碼為111，這樣的編碼方式完成了我們對(duì)節(jié)點(diǎn)編碼的需求。
fastText模型架構(gòu)
fastText算法是一種有監(jiān)督的模型，與《前篇》中的CBOW架構(gòu)很相似，其結(jié)構(gòu)如圖6所示?！肚捌分械腃BOW，通過(guò)上下文預(yù)測(cè)中間詞，而fastText則是通過(guò)上下文預(yù)測(cè)標(biāo)簽（這個(gè)標(biāo)簽就是文本的類(lèi)別，是訓(xùn)練模型之前通過(guò)人工標(biāo)注等方法事先確定下來(lái)的）。如果小主在上一篇文章中已經(jīng)對(duì)CBOW了解透徹了，可能到這里你已經(jīng)覺(jué)得fastText并沒(méi)有什么新鮮玩意兒。事實(shí)確實(shí)如此，從模型架構(gòu)上來(lái)說(shuō)，沿用了CBOW的單層神經(jīng)網(wǎng)絡(luò)的模式，不過(guò)fastText的處理速度才是這個(gè)算法的創(chuàng)新之處。
fastText模型的輸入是一個(gè)詞的序列（一段文本或者一句話)，輸出是這個(gè)詞序列屬于不同類(lèi)別的概率。在序列中的詞和詞組構(gòu)成特征向量，特征向量通過(guò)線性變換映射到中間層，再由中間層映射到標(biāo)簽。fastText在預(yù)測(cè)標(biāo)簽時(shí)使用了非線性激活函數(shù)，但在中間層不使用非線性激活函數(shù)。
圖 6 展示了一個(gè)有一個(gè)隱藏層的簡(jiǎn)單模型。第一個(gè)權(quán)重矩陣w_1可以被視作某個(gè)句子的詞查找表（詞表查找是啥來(lái)著？去看看《前篇》中的那個(gè)矩陣相乘你就想起來(lái)了）。詞表征被平均成一個(gè)文本表征，然后其會(huì)被饋送入一個(gè)線性分類(lèi)器。這個(gè)構(gòu)架和《前篇》介紹的CBOW模型相似，只是中間詞（middle word）被替換成了標(biāo)簽（label）。該模型將一系列單詞作為輸入并產(chǎn)生一個(gè)預(yù)定義類(lèi)的概率分布。我們使用一個(gè)softmax方程來(lái)計(jì)算這些概率。當(dāng)數(shù)據(jù)量巨大時(shí)，線性分類(lèi)器的計(jì)算十分昂貴，所以fastText使用了一個(gè)基于霍夫曼編碼樹(shù)的分層softmax方法。常用的文本特征表示方法是詞袋模型，然而詞袋（BoW）中的詞順序是不變的，但是明確考慮該順序的計(jì)算成本通常十分高昂。作為替代，fastText使用n-gram獲取額外特征來(lái)得到關(guān)于局部詞順序的部分信息，后文將詳細(xì)介紹。
層次softmax
Facebook聲稱(chēng)fastText比其他學(xué)習(xí)方法要快得多，能夠訓(xùn)練模型“在使用標(biāo)準(zhǔn)多核CPU的情況下10分鐘內(nèi)處理超過(guò)10億個(gè)詞匯”，特別是與深度模型對(duì)比，fastText能將訓(xùn)練時(shí)間由數(shù)天縮短到幾秒鐘。這樣的速度取決于什么呢？模型架構(gòu)上并沒(méi)有什么本質(zhì)革新，接下來(lái)就帶你“上高速”~
softmax函數(shù)
上一篇，我們已經(jīng)介紹了這個(gè)函數(shù)。softmax函數(shù)實(shí)際是一個(gè)歸一化的指數(shù)函數(shù)：
σ(z)j=ezj∑Kk=1ezk
而softmax把一個(gè)k維的real value向量（a1,a2,a3,a4….）映射成一個(gè)（b1,b2,b3,b4….）其中bi是一個(gè)0-1的常數(shù)，然后可以根據(jù)bi的大小來(lái)進(jìn)行多分類(lèi)的任務(wù)，如取權(quán)重最大的一維。
分層softmax（Hierarchical softmax）
分層softmax的目的是降低softmax層的計(jì)算復(fù)雜度。
二叉樹(shù)。Hierarchical softmax本質(zhì)上是用層級(jí)關(guān)系替代了扁平化的softmax層，如圖1所示，每個(gè)葉子節(jié)點(diǎn)表示一個(gè)詞語(yǔ)（即霍夫曼樹(shù)的結(jié)構(gòu)）。
我們可以把原來(lái)的softmax看做深度為1的樹(shù)，詞表V中的每一個(gè)詞語(yǔ)表示一個(gè)葉子節(jié)點(diǎn)。如果把softmax改為二叉樹(shù)結(jié)構(gòu)，每個(gè)word表示葉子節(jié)點(diǎn)，那么只需要沿著通向該詞語(yǔ)的葉子節(jié)點(diǎn)的路徑搜索，而不需要考慮其它的節(jié)點(diǎn)。這就是為什么fastText可以解決不平衡分類(lèi)問(wèn)題，因?yàn)樵趯?duì)某個(gè)節(jié)點(diǎn)進(jìn)行計(jì)算時(shí)，完全不依賴(lài)于它的上一層的葉子節(jié)點(diǎn)（即權(quán)重大于它的葉結(jié)點(diǎn)），也就是數(shù)目較大的label不能影響數(shù)目較小的label（即圖5中B無(wú)法影響A和C）。
平衡二叉樹(shù)的深度是log2(|V|)，因此，最多只需要計(jì)算log2(|V|)個(gè)節(jié)點(diǎn)就能得到目標(biāo)詞語(yǔ)的概率值。hierarchical softmax定義了詞表V中所有詞語(yǔ)的標(biāo)準(zhǔn)化概率分布。
具體說(shuō)來(lái)，當(dāng)遍歷樹(shù)的時(shí)候，我們需要能夠計(jì)算左側(cè)分枝或是右側(cè)分枝的概率值。為此，給每個(gè)節(jié)點(diǎn)分配一個(gè)向量表示。與常規(guī)的softmax做法不同，這里不是給每個(gè)輸出詞語(yǔ)w生成詞向量v_w^’，而是給每個(gè)節(jié)點(diǎn)n計(jì)算一個(gè)向量〖v?n?’〗?？偣灿衸V|-1個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都有自己獨(dú)一無(wú)二的向量表示，H-Softmax方法用到的參數(shù)與常規(guī)的softmax幾乎一樣。于是，在給定上下文c時(shí)，就能夠計(jì)算節(jié)點(diǎn)n左右兩個(gè)分枝的概率：
p(right|n,c=σ(hTvnT))
上式與常規(guī)的softmax大致相同?，F(xiàn)在需要計(jì)算h與樹(shù)的每個(gè)節(jié)點(diǎn)的向量v_n^’的內(nèi)積，而不是與每個(gè)輸出詞語(yǔ)的向量計(jì)算。而且，只需要計(jì)算一個(gè)概率值，這里就是偏向n節(jié)點(diǎn)右枝的概率值。相反的，偏向左枝的概率值是1- p(right│n,c)。
如圖8所示，為了方便理解，這里的葉子節(jié)點(diǎn)給出的依然是詞語(yǔ)，也就是CBOW的架構(gòu)，fastText是相同的道理，只是將葉子節(jié)點(diǎn)替換為label即可。假設(shè)已知出現(xiàn)了詞語(yǔ)“the”、“dog”、“and”、“the”，則出現(xiàn)詞語(yǔ)“cat”的概率值就是在節(jié)點(diǎn)1向左偏的概率值、在節(jié)點(diǎn)2向右偏的概率以及在節(jié)點(diǎn)5向右偏的概率值的乘積。
值得注意的是，此方法只是加速了訓(xùn)練過(guò)程，因?yàn)槲覀兛梢蕴崆爸缹⒁A(yù)測(cè)的詞語(yǔ)（以及其搜索路徑）。在測(cè)試過(guò)程中，被預(yù)測(cè)詞語(yǔ)是未知的，仍然無(wú)法避免計(jì)算所有詞語(yǔ)的概率值。
向量表示該節(jié)點(diǎn)的搜索路徑，詞語(yǔ)“cat”的向量就是011。上文中提到平衡二叉樹(shù)的深度不超過(guò)log2(|V|)。若詞表的大小是|V|=10000，那么搜索路徑的平均長(zhǎng)度就是13.3。
N-gram
常用的特征是詞袋模型，在第一部分小編已經(jīng)介紹過(guò)詞袋模型了。詞袋模型不考慮詞之間的順序，因此 fastText 還加入了 N-gram 特征?！拔覑?ài)你”的特征應(yīng)當(dāng)是“我”、“愛(ài)”、“你”。那么“你愛(ài)我”這句話的特征和“我愛(ài)你”是一樣的，因?yàn)椤拔覑?ài)你”的bag（詞袋）中也是只包含“你”、“愛(ài)”、“我”。
還是那句話——“我愛(ài)你”：如果使用2-gram，這句話的特征還有 “我-愛(ài)”和“愛(ài)-你”，這兩句話“我愛(ài)你”和“你愛(ài)我”就能區(qū)別開(kāi)來(lái)了，因?yàn)椤澳銗?ài)我”的2-gram的特征還包括“你-愛(ài)”和“愛(ài)-我”，這樣就可以區(qū)分“你愛(ài)我”和“我愛(ài)你”了。為了提高效率，實(shí)務(wù)中會(huì)過(guò)濾掉低頻的 N-gram。否則將會(huì)嚴(yán)重影響速度。
在fastText 中一個(gè)低維度向量與每個(gè)單詞都相關(guān)。隱藏表征在不同類(lèi)別所有分類(lèi)器中進(jìn)行共享，使得文本信息在不同類(lèi)別中能夠共同使用。這類(lèi)表征被稱(chēng)為詞袋（bag of words）（此處忽視詞序）。在 fastText中也使用向量表征單詞 n-gram來(lái)將局部詞序考慮在內(nèi)，這對(duì)很多文本分類(lèi)問(wèn)題來(lái)說(shuō)十分重要。
fastText算法實(shí)現(xiàn)
這里提醒讀者，fastText在Python2和Python3中都可以使用，已有了現(xiàn)成的包，但只支持Linux和mac系統(tǒng)，windows暫時(shí)還不支持fastText。本例使用的環(huán)境是linux-ubuntu16.04+Python3+JupyterNotebook的組合，讀者當(dāng)然可以使用其他IDE或是使用Python2，都是完全沒(méi)有問(wèn)題的。只需要在終端使用語(yǔ)句pip install fasttext（Python2）或是pip3 install fasttext進(jìn)行安裝即可。
我們使用的語(yǔ)料是清華大學(xué)的新聞文本（數(shù)據(jù)比較大，可以在http://thuctc.thunlp.org/message進(jìn)行下載），這里不在詳細(xì)介紹分詞過(guò)程，與《前篇》中的過(guò)程基本是一致的?？梢灾苯拥?a target="_blank" rel="nofollow">https://pan.baidu.com/s/1jH7wyOY和https://pan.baidu.com/s/1slGlPgx下載處理好的訓(xùn)練集和測(cè)試集（處理后的數(shù)據(jù)形式為詞與詞之間用空格分開(kāi)，詞語(yǔ)與標(biāo)簽?zāi)J(rèn)用label分隔），如圖9所示。
使用logging可以查看程序運(yùn)行日志。fasttext.supervised()的第一個(gè)參數(shù)為訓(xùn)練集，即用來(lái)擬合模型的數(shù)據(jù)，第二個(gè)參數(shù)為模型存儲(chǔ)的絕對(duì)路徑，第三個(gè)為文本與標(biāo)簽的分隔符；訓(xùn)練好模型后通過(guò)load_model加載模型，對(duì)訓(xùn)練集使用test方法則可以在測(cè)試集上使用模型，則會(huì)得到模型在測(cè)試集上的準(zhǔn)確率和召回率，可以看到模型的準(zhǔn)確率和召回率是非常高的，而且對(duì)于這個(gè)近400Mb的訓(xùn)練集，擬合模型只花費(fèi)了60秒左右（小編的電腦為8GB內(nèi)存），速度是非常可觀的。
fastText算法通過(guò)了兩篇的講解，相比聰明的你已經(jīng)掌握了算法原理，關(guān)于fastText算法到這里就要告一段落了，熟悉了原理和思想，接下來(lái)小主可以去找些有趣的文本做一些有趣的事情了，與fastText一起飚車(chē)吧！
fasttext參數(shù)：
The following arguments are optional:
-lr learning rate [0.05]
-lrUpdateRate change the rate of updates for the learning rate [100]
-dim size of word vectors [100]
-ws size of the context window [5]
-epoch number of epochs [5]
-minCount minimal number of word occurences [1]
-neg number of negatives sampled [5]
-wordNgrams max length of word ngram [1]
-loss loss function {ns, hs, softmax} [ns]
-bucket number of buckets [2000000]
-minn min length of char ngram [3]
-maxn max length of char ngram [6]
-thread number of threads [12]
-t sampling threshold [0.0001]
-label labels prefix [__label__]
