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

彭永鑫

(商洛學院, 數(shù)學與計算機應(yīng)用學院， 陜西, 商洛 726000)

0 引言

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

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

1 可學習索引結(jié)構(gòu)的構(gòu)建

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

傳統(tǒng)哈希索引

可學習索引圖1 可學習索引的架構(gòu)

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

圖2 累積分布函數(shù)

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

Pos=CDF(Key)×N

(1)

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

Pos=f(Key)×N

(2)

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

2 可學習索引的框架

對每一個具體的可學習索引結(jié)構(gòu)來說，基本上都可以用以下幾個階段去構(gòu)建完成。分別是特征提取和輸入層、神經(jīng)網(wǎng)絡(luò)層、索引層和輸出層。每個階段分別如下：

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

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

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

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

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

3 結(jié)果與分析

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

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

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

圖3 數(shù)據(jù)量對準確率的影響

表1 數(shù)據(jù)量對查找時間的影響

4 總結(jié)

本文針對目前最近鄰查找存在的問題，提出了新的解決方案，表現(xiàn)出了一定的優(yōu)越性。在建立可學習索引模型的基礎(chǔ)上，將其應(yīng)用于一種具體的數(shù)據(jù)結(jié)構(gòu)——局部敏感哈希。在之后的工作中，將繼續(xù)研究其在真實數(shù)據(jù)集上的效果。