面向大規(guī)模數(shù)據(jù)集的索引學(xué)習(xí)算法研究

李 繁，嚴(yán) 星

(新疆財經(jīng)大學(xué)，新疆 烏魯木齊 830012)

1 引言

在大規(guī)模數(shù)據(jù)集中使用窮舉搜索法是不可行的。因此，目前最近鄰搜索算法使用的非常廣泛，也帶來了許多新的挑戰(zhàn)及討論，眾多的算法都希望能在準(zhǔn)確率、效能及內(nèi)存使用等方面找到一個較好的平衡點。

在最近鄰搜索算法中，有兩種主要做法：數(shù)據(jù)量化與二元嵌入。在數(shù)據(jù)量化中，是通過一些分群算法，進行分群并得到各群群中心信息，再將所有數(shù)據(jù)分配至最鄰近的群中心。而在二元嵌入中，則是通過雜湊函數(shù)轉(zhuǎn)換至對應(yīng)的二元碼當(dāng)中。在這兩種方法的幫助下，不管是內(nèi)存使用或是計算量都大幅降低。此外也可以利用這些群中心、二元碼，創(chuàng)建索引表或代碼表(codebook)，通過這些索引表可以快速篩選出最近的候選集。但存在的問題是，原始數(shù)據(jù)對應(yīng)到索引表后有著無法避免的數(shù)據(jù)損失，導(dǎo)致搜索準(zhǔn)確率下降。

為此，本文提出了面向大規(guī)模數(shù)據(jù)集的索引學(xué)習(xí)方法，依照近鄰概率去訪問各群使候選集信息更為精準(zhǔn)。同時，通過事先計算出各大群中包含了多少最相關(guān)子群，也能有效的分散計算量。

2 相關(guān)研究

2.1 樹狀索引

樹狀索引結(jié)構(gòu)技術(shù)廣泛使用在向量空間索引(vector space indexing)[1，2]，比較常見的如文獻[3]所使用的hierarchical k-means可以有效的降低搜索時間。

hierarchical k-means方法是先將數(shù)據(jù)進行第一次的k-means分群產(chǎn)生k個群中心(第一層)，再個別對這k個群中心內(nèi)所包含的數(shù)據(jù)進行一次k-means分群，分為k個子群(第二層)，使總?cè)簲?shù)量可達到k2個。

2.2 二元碼嵌入

在處理大規(guī)模數(shù)據(jù)時，傳統(tǒng) tree-based方法(如：KD tree[5]，ball tree[6]，metric tree[7]，vantage point tree[8])往往會造成很大的內(nèi)存負擔(dān)，在處理高維度數(shù)據(jù)集時，效率會急劇下降[9]。

二元碼嵌入提供了最簡潔的數(shù)據(jù)表示方式，二元碼轉(zhuǎn)換是通過哈希函數(shù)將數(shù)據(jù)投影至二元空間。二元碼嵌入方法主要可以分為兩種，一種是數(shù)據(jù)獨立性(Data-independent)。例如：kernelized LSH[10]與其中比較著名的 Locality Sensitive Hashing，LSH[11，12]，屬于數(shù)據(jù)獨立的哈希函數(shù)，通過高斯隨機分布的哈希矩陣，將原始空間相鄰點隨機投影至其它空間時，相鄰機會很大；反之不相鄰的點則會很少，此方法實現(xiàn)容易、速度快；不過檢索精度相對不那么準(zhǔn)確。而另一種則為數(shù)據(jù)依賴性(Data-dependent)，需要依賴原始數(shù)據(jù)來學(xué)習(xí)哈希函數(shù)[13，14]。

二元嵌入方法優(yōu)點在于節(jié)省海量存儲器空間。如要將一數(shù)據(jù)庫中十億筆128維數(shù)據(jù)存入內(nèi)存中，可能就得花費將近476GB的內(nèi)存空間，若將其轉(zhuǎn)至二元空間，卻僅需花費14GB的內(nèi)存空間。在二元空間內(nèi)，將原始數(shù)據(jù)產(chǎn)生的二元碼作為索引，并建立反向索引表，搜索時只需要對索引值二元碼進行搜索即可。雖然二元碼嵌入在漢明空間里，計算上可以更快速，但也相對的無法避免數(shù)據(jù)距離計算不夠準(zhǔn)確的問題。

2.3 乘積量化、非對稱距離計算

乘積量化(product quantization，簡稱PQ)在高維度空間上，是一個很有效率的有損壓縮技術(shù)。PQ把每個原始向量分解成各自的子向量，每個子向量再分別進行索引而產(chǎn)生多張不同的索引表；而各個原始向量將由量化后的子向量串聯(lián)代替而成。

非對稱距離計算通常用于最近鄰搜索法的第二階段，重新排序候選集名單，讓更相似的數(shù)據(jù)排在前面。非對稱距離計算是在查詢值不需進行量化的情況下，與各數(shù)據(jù)進行距離計算，來彌補量化誤差的問題，可以使候選集名單更精確。文獻[15]中提出了一個使用PQ有效計算非對稱距離的方式，將原始數(shù)據(jù)分解成不同的子向量，個別進行分群，產(chǎn)生不同的多張索引表。而在搜索時，不需將查詢值進行量化，只需計算查詢值與各個向量的距離總和，即可算出非對稱距離，再利用這些距離，重新排序候選集名單，讓搜索更為精確。

2.4 多重反向索引表

反向索引系統(tǒng)與非對稱距離計算(IVFADC)是個基于如何有效處理數(shù)十億筆數(shù)據(jù)集所產(chǎn)生的架構(gòu)。采用了k-means進行粗略量化(coarser quantization)且有效的將殘差值運用在乘積量化中。非對稱距離計算(asymmetric distance computation，簡稱ADC)是為了應(yīng)用在反向索引表中，快速的計算歐幾里得距離[16]。

多重反向索引表(inverted multi-index，簡稱IMI)使用了多維索引列表，各列表群中心是將原本的索引表分隔建構(gòu)而成。多重序列比對算法被套用在IMI中。由于大量的群可將原本數(shù)據(jù)密集的分散于各群中，可以使得 IMI達到相當(dāng)高的召回率(recall)。

3 算法描述

下面開始介紹所使用的分群結(jié)構(gòu)，及如何利用類神經(jīng)網(wǎng)絡(luò)模型找出查詢值與各群間的近鄰概率，再介紹如何有效利用這些近鄰概率，進行多層式的數(shù)據(jù)檢索。

假設(shè)有一個數(shù)據(jù)集包含了N個s維度的特征向量D={dn∈{R}s|n=1，2，…，N}。建構(gòu)了一個擁有M群的索引結(jié)構(gòu){(Cm，Im)|m=1，2，…，M}而Cm則是第m群，且Im則是反向索引列表，紀(jì)錄了第m群所包含的索引內(nèi)擁有的向量編號

Im={n|Z(dn)=Cm}

(1)

其中Z(dn)是量化函數(shù)，從而得到dn最接近的群。給予一個查詢值q，最典型利用索引結(jié)構(gòu)的方法則是檢索出前R個最接近q的群中心信息，如下述表示

(2)

為了解決在索引結(jié)構(gòu)里所產(chǎn)生的量化誤差問題，通過類神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)近鄰關(guān)系，而產(chǎn)生一個非線性模型函數(shù)f再將查詢點的原始數(shù)據(jù)作為類神經(jīng)網(wǎng)絡(luò)的輸入，投入該模型當(dāng)中，從而得到各群與查詢值的近鄰概率{pC1，pC2，…，pCM}，其中pCm代表第m群Cm與查詢值的近鄰概率

{pC1，pC2，…，pCM}=f(q)

(3)

接著依照各群的近鄰概率，由大至小進行排序，得到檢索順序R，前R個與查詢值q最相關(guān)的群中心信息

(4)

3.1 整體流程

3.1.1 預(yù)處理

Step 1：將數(shù)據(jù)使用k-means分成m群，并建立反向索引表Im。

Step 2：使用Im訓(xùn)練類神經(jīng)網(wǎng)絡(luò)模型Ω。

3.1.2 索引搜索

Step 1：通過式(5)先將查詢值q正規(guī)化，再將其投入類神經(jīng)網(wǎng)絡(luò)模型Ω中，得到Cm各群預(yù)測的近鄰概率pm。

Step 3：利用總訪問數(shù)量T與Cr各群的近鄰概率計算出Cr該子群所需訪問數(shù)量。

Step 5：重復(fù)Step 3、Step 4，直到所取群數(shù)達到設(shè)定的閾值。

Step 6：進行非對稱距離計算，重新排序候選集名單，取出前i筆數(shù)據(jù)，當(dāng)作最終候選集名單。

3.2 訓(xùn)練模塊

(5)

由于查詢值為一個s維度的特征向量，將各個向量(各維度)分別進行標(biāo)準(zhǔn)化，讓輸入數(shù)據(jù)介于0與1之間，作為模型的輸入(Dmin、Dmax為數(shù)據(jù)庫里最小值、最大值)

(6)

(7)

通過訓(xùn)練得到的類神經(jīng)網(wǎng)絡(luò)模型，可用來敘述查詢值q與各群之間的近鄰關(guān)系。讓Ω表示訓(xùn)練好的類神經(jīng)網(wǎng)絡(luò)模型。Ω包含了一層輸入層，一層隱藏層與一層輸出層。每一層都為完全連接神經(jīng)元。輸入層接收了s個特征向量(查詢的q標(biāo)準(zhǔn)化后結(jié)果)，輸出層則是m個機率值，相對應(yīng)到m群的近鄰概率。

3.3 索引搜索

(8)

(9)

接著找Sr個最接近的子群：

PartialSort(subDistancesr[ ]，Sr)

(10)

3.4 非對稱距離計算

為了能讓候選集名單更加精確，使用非對稱距離計算，進行了第二次候選集的篩選。在數(shù)據(jù)預(yù)處理中，先將原始數(shù)據(jù)向量D切成n個子向量，再將各子向量進行量化分群(product quantizer pq)：

pq(D)=(pq1(D1)，pq2(D2)，…，pqn(Dn))

(11)

切割并個別進行分群后將會有n張不同的索引表(codebook)記錄群中心信息。再建立n張查找表(lookuptable)，分別記錄各個數(shù)據(jù)點在第n張表屬于哪一個群。最后在搜索時，只需將查詢值q切割成n個子向量，與候選集n個子向量所屬的群中心做距離計算，并總和得到非對稱距離：

(12)

最后再將候選集名單利用非對稱距離進行排序，取出前i筆(通常為1000筆)當(dāng)作最終候選集信息

PartialSort(Distances[]，i)

(13)

4 實驗仿真結(jié)果

4.1 實驗數(shù)據(jù)與環(huán)境

實驗數(shù)據(jù)使用SIFT_1B，此數(shù)據(jù)庫包含10億筆128維度SIFT特征向量，提供1萬筆的查詢值Query數(shù)據(jù)與每筆查詢值的對應(yīng)1000筆正確鄰居信息(正解)。使用8000筆query與正解作為類神經(jīng)網(wǎng)絡(luò)的訓(xùn)練數(shù)據(jù)，2000筆作為測試數(shù)據(jù)，總和1萬筆，測試數(shù)據(jù)將不會用于訓(xùn)練數(shù)據(jù)內(nèi)。實驗環(huán)境：Intel Core i7-5820 CPU @3.30GHz 128GB RAM，采用 C++與 Python 3.6編寫(使用 Keras套件編寫類神經(jīng)網(wǎng)絡(luò)進行模型訓(xùn)練、預(yù)測，使用CPU，無GPU加速)。

本實驗將十億筆特征數(shù)據(jù)取出一千萬筆作為分群訓(xùn)練資料，經(jīng)過hierarchical k-means clustering分群法，分為256×256群、1024×1024群以及4096×4096群。類神經(jīng)網(wǎng)絡(luò)將套用在第一層上。類神經(jīng)網(wǎng)絡(luò)的設(shè)計使用了一層輸入層、一層隱藏層、一層輸出層，每層都是完全連接神經(jīng)元。第一層神經(jīng)元數(shù)量為query特征向量數(shù)量128。第二層神經(jīng)元數(shù)量為第一層的兩倍。第三層則為群中心數(shù)量256、1024、4096，代表各群近鄰概率。一到二層使用relu作為激活函數(shù)，最后一層則使用softmax使近鄰概率加總等于1。誤差函數(shù)使用交叉熵(cross-entropy)來計算標(biāo)簽與從類神經(jīng)網(wǎng)絡(luò)輸出的誤差。輸入為經(jīng)過正規(guī)化后查詢值的特征向量，輸出為第一層k-means總?cè)簲?shù)量(代表各群的近鄰概率)。訓(xùn)練次數(shù)為：epochs=295，batch_size=8。最后將所訓(xùn)練出來的模型套用至搜索上，并與沒有使用模型的搜索結(jié)果進行比較。

4.2 實驗設(shè)計與結(jié)果

使用召回率(Recall)、精確率(Precision)來計算所挑選出的候選集質(zhì)量。召回率為候選集名單所包含的正解數(shù)量。Top@R(Top-N Recall)則是代表候選集名單中包含了N個正解。著重于候選集的精度，所有實驗均以Top1000R作為比較對象。

以下實驗將沒有套用類神經(jīng)網(wǎng)絡(luò)模型的實驗結(jié)果統(tǒng)稱為baseline，套用類神經(jīng)網(wǎng)絡(luò)模型的結(jié)果統(tǒng)稱為probability。

4.2.1 單層取法

baseline方法為找出n個與查詢值距離最近的群，取出群內(nèi)所有候選集數(shù)據(jù)當(dāng)作搜索結(jié)果，計算出查詢值與各群的距離，并由小至大進行排序。probability方法則會將標(biāo)準(zhǔn)化后的查詢值query，使用類神經(jīng)網(wǎng)絡(luò)模型Ω，計算出各群的近鄰概率，接著將各群的近鄰概率由大至小進行排序，最后再取出前n群距離最近(baseline)、機率最大(probability)的候選集信息作為結(jié)果。

以下所呈現(xiàn)的是SIFT1B_1B數(shù)據(jù)庫使用k-measn(一層)分為256群、1024群與4096群的搜索結(jié)果，見表1、表2、表3。baseline找出n個與查詢值距離最近的群，取出群內(nèi)所有候選集數(shù)據(jù)當(dāng)作搜索結(jié)果。probability則是套用類神經(jīng)網(wǎng)絡(luò)后，找出n筆近鄰概率最高的當(dāng)作搜索結(jié)果。

表1 SIFT_1B 256群的結(jié)果

表2 SIFT_1B 1024群的結(jié)果

表3 SIFT_1B 4096群的結(jié)果

可以從結(jié)果觀察到，使用類神經(jīng)網(wǎng)絡(luò)模型去預(yù)測各群的近鄰概率，由高至低進行檢索，取代原本的歐幾里得距離，各種群數(shù)下，Recall、precision都比baseline要好，也間接證明了使用類神經(jīng)網(wǎng)絡(luò)模型所預(yù)測的近鄰概率，是可以改善候選集質(zhì)量的。

4.2.2 多層取法

以下為使用hierarchical k-means clustering(兩層)的結(jié)果，如圖1所示。第二層采用固定最后所取總?cè)簲?shù)量，作為互相比較的標(biāo)準(zhǔn)。由于baseline無法自行決定第一層所需使用的群數(shù)量，所以將baseline的實驗結(jié)果設(shè)定為取m群(1、2、4、8群)，總?cè)簲?shù)量則固定與probability相同。假設(shè)現(xiàn)在所需總?cè)簲?shù)量為n，baseline將會有五組不同Recall。第一組為1群，則會在該群下取出n/1個子群作為結(jié)果，第二組為2群，則會在這兩群中，各取n/2個與查詢值query最近的子群作為結(jié)果，以此類推。

圖1 Precision-Recall曲線

由此可以看出，本文的方法與baseline相比都有著一定的改善幅度，雖然baseline第一層拜訪的群數(shù)越多，結(jié)果可能會越好，但這也代表著必須自行觀察搜索結(jié)果，找出最適合的參數(shù)。而由近鄰概率來決定第一層所需訪問的群數(shù)量，則可以不必再觀察搜索結(jié)果，利用近鄰概率自動找出(算出)最適合的參數(shù)。

4.2.3 非對稱距離計算

以下為上一小節(jié)實驗經(jīng)過非對稱距離(ADC)計算后的結(jié)果。ADC結(jié)構(gòu)為：原始特征切為8段，各16維，每段分256群剛好可以以一個字節(jié)來代表(1byte)。經(jīng)過ADC后取出前1000筆，并計算Top1000 Recall。如圖2所示。

圖2 ADC的結(jié)果

通過實驗可以觀察到利用近鄰概率，整體候選集質(zhì)量有所提升，因此經(jīng)過ADC后可以明顯看出優(yōu)勢所在。除了256×256群外，其它兩種都有明顯的改善。

5 結(jié)束語

本文展現(xiàn)了如何利用類神經(jīng)網(wǎng)絡(luò)去學(xué)習(xí)查詢值與各群之間的近鄰概率，舍棄原先使用歐幾里得距離的方式，在某些條件下還可以減少計算距離的時間。針對不同參數(shù)與實驗結(jié)果，對本文所提出的方法進行了深入分析。本文主要研究工作和結(jié)論如下：

1)利用近鄰概率重新排列檢索順序作為第一階段篩選，取代原本的基于距離產(chǎn)生的檢索順序。

2)有效運用近鄰概率在樹狀索引的分群方法，也可以與其它近鄰搜索方法做整合，提升它們的檢索精度。

3)用本文提出的方法重新排序檢索表后，在十億筆數(shù)據(jù)集實驗中，準(zhǔn)確度都得到了明顯的提升。