相似性搜索與詞向量中的應用分析

6 人贊了文章

參考論文《On Approximately Searching for Similar Word Embeddings》原文鏈接 發表於ACL2016

什麼是相似性搜索

相似性搜索的概念是在n維空間中通過比較數據之間的相似性，尋找與輸入點最接近的目標點。該技術被廣泛應用在資料庫、信息檢索、模式識別、數據分析等各個領域。

相似性搜索包含兩個大類：近鄰搜索和範圍搜索。以尋找你附近的火鍋店為例，近鄰搜索可以幫助你找到距離最近的n家火鍋店，而範圍搜索可以幫助找到1公里範圍內所有的火鍋店。下圖中左邊展示的是近鄰搜索，右邊是範圍搜索。

最傳統的相似性搜索方法是線性搜索，對於給定的數據集，通過一定的距離計算公式，計算數據集中所有數據點到輸入點的距離，然後對計算後的距離進行排序，選擇最近的結果作為相似性最高的輸出。

在只有幾千個點的低維度數據集上，這樣的方法是ok的。但是當數據集是百萬級甚至千萬級的海量數據時，這種線性搜索的方案將會非常耗時。同時隨著數據維度的增加，線性搜索也會帶來維度災難(Curse of dimensionality)，相似性搜索的性能會急速下降。

為了解決該問題，最常用解決方案就是對數據集使用索引技術。

索引技術

通過事先對數據集進行索引，從而達到高效搜索n維空間數據的目的。在相似性搜索中，數據索引的方案可以分為三大類，分別是哈希索引、樹索引以及圖索引。

哈希索引

哈希索引由於其簡單的特性，經常被運用在自然語言處理上計算文本間的相似度。一種常用的索引方法是局部敏感哈希(Locality Sensitive Hashing，LSH)演算法。LSH的核心思想是在哈希演算法的過程中依舊在一定概率上保持數據原有的相似性，也就是說在原始數據集中距離較近的兩個數據點，在LSH以後仍然很大概率非常接近。另外，LSH的方法通常更適合於範圍搜索，而非近鄰搜索。

下面是LSH函數h的條件：

樹索引

樹索引可以理解為將數據排列成樹結構，在搜索過程中排除掉不符合要求的分支，從而提升搜索速度。

這裡從R樹開始入手了解一下樹索引。如下圖所示，我們將數據集按照數據值分配到9個子集中（紅框），並確保每個子集擁有相同數目的數據。然後我們對每個子集重新劃分更小的9個子集（藍框）。循環往複直到最後的每個子集只擁有不超過9個數據點。這就是R樹的整體概念，可以從二維延展到更高維。

kd樹是另一種樹索引方案，相對於R樹在每一層將數據分發到多個子集不同的是，kd樹每一級僅將空間劃分為兩個部分，劃分的維度會根據每一部分數據的狀態選擇劃分度最大的維度，循環往複將數據切分為各個小部分。kd樹無法處理數據的添加和移除，但是具有實現方便且搜索速度快的特點。

FLANN（Fast library for approximate nearest neighbors）是一套樹空間搜索的開源庫，其採用的方案是在三種樹索引方案中選擇最優解（三種方案分別是隨機kd樹、k-means樹以及前兩者的混合方案）。目前FLANN支持C/C++、Matlab、Python等介面調用嗎，使用起來也非常方便。

SASH（Spatial approximation sample hierarchy）是一種建立在隨機採樣數據上的層級結構加上數據鏈接的索引。數據準確性不是一定能夠保證的，但是可以通過調整比例因子的參數來提高精度。SASH的大致原理是通過隨機採樣數據集中的數據，並對其建立樹索引，然後對於未被隨機採樣到的數據集與樹結構中的數據進行鏈接配對，從而完成完整數據的索引[如圖]。在SASH的官網上可以下載C++的源碼進行使用。

圖索引

圖索引的方法是通過近鄰圖尋找最近的節點。最近鄰圖(NNG)中的每一個點通過距離計算被連接到最接近的點上。下圖是一個二維平面100個點的最近鄰圖，其中的每一個點都可以通過圖結構尋找到自己的最鄰近點。

最鄰近圖NNG是k鄰近圖(KNNG)在k等於1時候的一種特殊情況，由於需要對所有節點計算最鄰近點，通常KNNG在構建的時候隨著節點數量的上升會非常耗時。但在實際運用中，採用一種ANNG的方案可以大大優化構建過程。2015年基於ANNG發布的NGT的開源項目，也已經被應用在多項實際業務上了。

詞向量中的相似性搜索

詞嵌入

自從Mikolov在2013年發表了word2vec，由於其優秀的性能表現，將自然語言處理帶入了一個新的階段，詞嵌入逐漸開始被大量應用於自然語言處理的行業應用中。

詞向量的本質是通過向量的方式來表示每一個辭彙，最簡單的方法是01向量，向量的維度為詞的總數，第N個詞可以表達為第N位為1，向量中其餘的元素全部為0。形如： [0,0,0,……0,1,0,……0,0,0]。然而這樣的表現方式基本不可用，因為維度實在太高。

word2vec等方案通過對一套語料庫的訓練，通過利用每個詞與上下文間關係(可分為CBOW或Skip-gram方法)來進行的詞嵌入(Word Embedding)。所謂的詞嵌入，其實就是將超高維度抽象化的詞向量嵌入到一個較低維度的空間中。當然除了word2vec，現在也有wordrank、GloVe等其它方案。在經過詞嵌入處理後，可以把原本稀疏的高維度01詞向量降到幾百維左右的稠密向量空間中，並且保留住詞與詞之間的隱含關聯。一個簡單的例子是：可以在詞空間中通過距離公式找出與某個詞距離最接近的詞，比如「麥當勞「，可能和它最接近的應該就是「肯德基「「漢堡」之類的辭彙。

在實際應用中我們經常需要在詞向量空間中尋找與目標詞距離最近的詞向量。On Approximately Searching for Similar Word Embeddings這篇論文分別在各場景下對之前提到的LSH、FLANN、SASH、NGT進行了詞向量應用中的測試比較，在這裡我們看一下對比結果。

索引時間比較

首先我們看一下建立索引時間的比較。文中採用的是2015年的英文維基百科作為訓練集產生的200維詞向量作為基礎，採用了三種距離公式，分別是歐式距離、歸一化距離和餘弦距離，對各個方案的索引時間進行比較。

結論可以發現採用歐氏距離時樹索引FLANN的索引時間最短，僅需20分鐘。而在歸一化距離和餘弦距離的情況下，代表圖索引的NGT都具有更好的表現，分別是33.9分鐘和155.4分鐘。

搜索性能比較

(a) 分別對100、200、300維的詞向量數據進行比較。理論上，在維度變得越來越高的時候SASH性能會更好，而FLANN和NGT在維度上升後性能會下降。在測試結果中(如下圖所示)，在三種情況下，NGT均在更短的時間內取得了較高的準確率。

(b) 根據不同的近鄰數量k值進行對比。當k取200時，SASH的性能下降明顯。一個可能的原因是當劃分的子空間不合適的時候，樹索引的搜索性能會大大受到影響。

(c) 不同數據量的對比。下圖是分別在數據量是100K、1M、2M的情況下的對比，搜索效果依次是NGT、SASH、FLANN。

(d) 三種不同詞向量的對比。分別是Mikolov使用skip-gram模型與負採樣技術的word2vec訓練產生的300維詞向量；深度神經網路生成的200維詞向量；GloVe生成的300維詞向量。結果圖中所示，在第三種情況下，所有的索引方案都比去前兩種模型都差了不少，可以發現搜索效果非常容易受到詞向量訓練模型的影響。

(e) 最後文章對詞向量運算做了一下比較，所謂的詞向量運算是指：」巴黎」之於」法國」等於什麼之於」日本」，正確答案應該是」東京」，而詞向量運算本質上是計算 vec(「巴黎」)-vec(「法國」)+ vec(「日本」)，並搜索距離結果向量最近的那個詞。

完整的測試內容感興趣可以看原文，也可以結合自己的實際場景去測試一下各個方案在你自己的詞向量上的表現效果。

推薦閱讀：