李 繁，嚴(yán) 星

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

1 引言

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

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

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

2 相關(guān)研究

2.1 樹(shù)狀索引

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

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

2.2 二元碼嵌入

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

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

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

2.3 乘積量化、非對(duì)稱(chēng)距離計(jì)算

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

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

2.4 多重反向索引表

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

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

3 算法描述

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

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

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

(1)

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

(2)

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

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

(3)

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

(4)

3.1 整體流程

3.1.1 預(yù)處理

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

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

3.1.2 索引搜索

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

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

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

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

3.2 訓(xùn)練模塊

(5)

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

(6)

(7)

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

3.3 索引搜索

(8)

(9)

接著找Sr個(gè)最接近的子群：

PartialSort(subDistancesr[ ]，Sr)

(10)

3.4 非對(duì)稱(chēng)距離計(jì)算

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

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

(11)

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

(12)

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

PartialSort(Distances[]，i)

(13)

4 實(shí)驗(yàn)仿真結(jié)果

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

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

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

4.2 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果

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

以下實(shí)驗(yàn)將沒(méi)有套用類(lèi)神經(jīng)網(wǎng)絡(luò)模型的實(shí)驗(yàn)結(jié)果統(tǒng)稱(chēng)為baseline，套用類(lèi)神經(jīng)網(wǎng)絡(luò)模型的結(jié)果統(tǒng)稱(chēng)為probability。

4.2.1 單層取法

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

以下所呈現(xiàn)的是SIFT1B_1B數(shù)據(jù)庫(kù)使用k-measn(一層)分為256群、1024群與4096群的搜索結(jié)果，見(jiàn)表1、表2、表3。baseline找出n個(gè)與查詢(xún)值距離最近的群，取出群內(nèi)所有候選集數(shù)據(jù)當(dāng)作搜索結(jié)果。probability則是套用類(lèi)神經(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é)果觀察到，使用類(lèi)神經(jīng)網(wǎng)絡(luò)模型去預(yù)測(cè)各群的近鄰概率，由高至低進(jìn)行檢索，取代原本的歐幾里得距離，各種群數(shù)下，Recall、precision都比baseline要好，也間接證明了使用類(lèi)神經(jīng)網(wǎng)絡(luò)模型所預(yù)測(cè)的近鄰概率，是可以改善候選集質(zhì)量的。

4.2.2 多層取法

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

圖1 Precision-Recall曲線

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

4.2.3 非對(duì)稱(chēng)距離計(jì)算

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

圖2 ADC的結(jié)果

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

5 結(jié)束語(yǔ)

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

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

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

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