基于深度學習的可學習索引研究

彭永鑫

(商洛學院, 數學與計算機應用學院， 陜西, 商洛 726000)

0 引言

現實世界中數據的積累越來越多，如何在海量數據中高效查找到互相關聯的數據，成為人們越來越關注的話題。作為數據檢索的一種重要方法，使用索引進行數據查找是最廣泛的應用之一。傳統索引結構雖然可以廣泛應用于數據庫的增刪改查中，但不能很好的解決最近鄰查找問題。作為精確最近鄰查找的代表性方法，樹形結構例如KD樹[1]等被廣泛使用。基于樹形結構的查找雖然結果準確，但需要較大的存儲空間，同時容易受到高維度數據的制約，造成查找效率的降低。由于在某些情況下往往不需要很高的查找精度，因此犧牲一定的查找準確率以換取更高的查找效率，即將最近鄰查找轉換為近似最近鄰查找成為一種可行的方法。常用的近似最近鄰算法有局部敏感哈希算法LSH[2]等。這類算法運行速度較快，但查找精度有待提高。找到一種既能解決高維數據的最近鄰查詢困難問題同時不會犧牲過多查詢精度的算法成為新的研究方向。

Google的研究[3]是使用深度學習算法代替傳統索引結構的一次嘗試，展現出了較好的結果。一般的哈希算法通過人為設定好的方式運行，不會考慮函數本身和數據分布之間的關系。而使用深度學習算法構建的哈希函數，會對輸入數據進行多次的訓練，整個過程需要數據的參與，不用人為設定一個固定的映射函數，可以充分學習到數據內部潛在的關系從而獲得更好的性能。在此基礎上，LISA[4]的提出使得查找任意空間數據集中的最近鄰查找成為可能；而ALEX[5]重點研究了查找策略的優化；Ali Hadian等[6]則討論了數據更新對模型的影響。本文將從具體的數據結構入手，探討構建可學習索引的一般方式，并通過實驗初步驗證可學習索引代替其他傳統索引結構的優越性。

1 可學習索引結構的構建

由文獻[3]可知，可以用深度學習算法整體或局部替代現有索引結構的某些結構，如圖1所示。基于深度學習的可學習索引通過學習數據的分布，能夠建立比傳統索引更為高效的數據結構。深度學習在處理特征向量方面具有強大的能力，而高維度數據和詞向量數據等可以根據自身的數據類型通過自編碼網絡等方法進行降維處理。將深度學習和這些降維方法等結合能夠發揮神經網絡在運算速度方面的巨大優勢。

傳統哈希索引

可學習索引圖1 可學習索引的架構

哈希函數模型和可學習索引模型都是基于鍵值對的模型。對于一個輸入的關鍵字，兩者都會輸出與其對應的索引位置。Google使用累積分布函數CDF[3]來描述給定的輸入數據的關鍵字的值與其對應的索引位置之間的函數映射關系。傳統的哈希函數模型和可學習索引模型都可以看作是一種累積分布函數，利用累積分布函數計算輸入數據映射后的索引位置。

圖2 累積分布函數

如圖2所示是某一個樣本數據的累積分布函數示意圖。其中橫坐標表示的是所有數據的關鍵字，縱坐標表示每個關鍵字對應的位置值。對于一個給定的關鍵字Key，相應的位置值Pos可以表示為

Pos=CDF(Key)×N

(1)

其中，CDF(x)表示累積分布函數，N是數據集的大小。可學習索引實際上是用深度學習的方法對數據樣本的累積分布函數進行擬合，可以用公式表示如下：

Pos=f(Key)×N

(2)

其中，f(x)表示選定的一種深度學習算法或者代表某種運算過程。基于此，在構建可學習索引結構的過程中，第一步要做的是找到輸入數據和對應位置之間的關系，構建一個累積分布函數，其次構建神經網絡，利用深度學習對已經構造好的累積分布函數進行訓練和擬合，最后進行參數的調整以達到一個較好的結果，從而讓可學習索引模型能夠完成關鍵字映射到索引位置這樣一個過程。

2 可學習索引的框架

對每一個具體的可學習索引結構來說，基本上都可以用以下幾個階段去構建完成。分別是特征提取和輸入層、神經網絡層、索引層和輸出層。每個階段分別如下：

(1) 特征提取和輸入層，這個階段主要完成對輸入數據的預處理和數據的輸入，包含了噪音清除、數據降維等過程。經過特征提取后的數據一般為較低維度的特征向量，方便神經網絡的處理，同時剔除了噪聲的不良影響，能夠使得結果更加準確。目前有很多特征處理的方法，例如SIFT與GIST等通常用于圖像的處理，word2vector能夠有效的提取語言文字的抽象表征。如果數據本身就是特征向量或者維度較低的數據，則可以將其直接輸入到之后的神經網絡層。

(2) 神經網絡層是整個可學習索引模型構建過程中最為重要的一個部分。可學習索引學習對象的不同，神經網絡的模型也會不同。對于某些數據結構，使用簡單的全連接網絡便能學習到數據的內在聯系。當數據集的數據量較多或者本身難以被學習時，需要設計和利用更為復雜的網絡結構，例如將一個深度神經網絡模型擴展為多個。不同的模型可以擁有不同的神經網絡層數和節點數。通過并行計算，各個模型互不干擾，能夠提高網絡的運行效率。神經網絡參數的更新也在這個階段進行。訓練過程中，對于有多個模型的神經網絡，將所有子網絡輸出的結果向量拼接為矩陣后，當成整個神經網絡模型的輸出，和輸入標簽放在一起計算損失。

(3) 索引層主要是對神經網絡輸出的結果進行處理。由于神經網絡的輸出通常是一些待轉換的編碼，不能直接使用得到結果，甚至可能這些編碼形式比較復雜，因此在索引層需要進行二次或者更多次的映射操作。

(4) 整個結構的最后一層是輸出層。當映射完成后，需要將得到的結果進行最終的計算、對比和排序，才能輸出精確最近鄰點或者近似最近鄰點。

對于精確最近鄰查找，在訓練過程中，需要著重提高的是神經網絡的運算速度，方式是選擇具有較好模型和結構的神經網絡；而局部敏感哈希這類的近似的最近鄰查找，為了提高準確率需要選擇或者設計較好的損失函數。

3 結果與分析

本節將會在可學習索引模型的基礎上，將其應用于具體的索引結構——局部敏感哈希，針對最近鄰查找問題，驗證可學習索引模型的優越性。實驗均使用Python編寫的代碼在Intel(R)Core(TM)i7-4770上完成。深度學習框架則選用的是目前較為常見的TensorFlow，版本號為1.13。TensorFlow能便捷地對神經網絡模型進行訓練，而且能夠將模型參數和模型結構進行固化后保存在特定類型的文件中方便后續的預測過程。

圖3是在相同的環境和條件下，采用監督學習的方式，將神經網絡訓練好之后，可學習局部敏感哈希算法和傳統局部敏感哈希算法以及KD樹的對比結果。其中，橫坐標為待查找的數據量大小，分別為1×104，2×104，3×104，4×104和5×104。所使用的數據集是符合正態分布的生成數據集，維度均為50維；縱坐標為查找的準確率。從圖3中可以看出，可學習局部敏感哈希在查找準確率上具有明顯的優勢，甚至比傳統的樹形結構還要高，最高能達到接近95%的準確率；同時，準確率相比較于傳統的局部敏感哈希也要高出10%左右。

表1是從查找時間的角度出發對比三者的差異。可以看出，無論是可學習的局部敏感哈希還是傳統的局部敏感哈希，相對于樹形結構KD樹，在查找速度上都具有巨大的優勢，且隨著查找數據量的增加，其優勢越來越明顯。與局部敏感哈希相比，可學習的局部敏感哈希在查找速度上更快，領先達到2倍左右。總的來說，基于可學習索引的可學習局部敏感哈希，無論是在查找準確率還是查找時間上都要優于傳統的局部敏感哈希和KD樹。

圖3 數據量對準確率的影響

表1 數據量對查找時間的影響

4 總結

本文針對目前最近鄰查找存在的問題，提出了新的解決方案，表現出了一定的優越性。在建立可學習索引模型的基礎上，將其應用于一種具體的數據結構——局部敏感哈希。在之后的工作中，將繼續研究其在真實數據集上的效果。