HL-DAQ：一種Hash學習的動態自適應量化編碼

趙 亮 王永利 杜仲舒 陳廣生

1(南京理工大學計算機科學與工程學院 南京 210094) 2 (華電能源股份有限公司佳木斯熱電廠 黑龍江佳木斯 154005) (845203965@qq.com)

近年來，近似最近鄰(approximate nearest neighbor, ANN)查詢被廣泛地應用于機器學習以及相關的應用領域中，包括機器視覺、信息檢索等.隨著數據的爆炸性增長，越來越多的關注集中到ANN查詢的Hash技術上，希望通過Hash技術將原始數據映射成簡潔的二進制編碼串的形式，再進行比較查詢，從而降低計算復雜度.同時，為了使Hash碼盡可能地保持原始數據間的近鄰關系，保證近似查詢的準確度，因而引入了Hash學習的概念.基于Hash學習的ANN技術主要包括2個階段[1]：投影階段和量化階段.投影階段的主要目的是將原始高維數據映射到低維表示，并保存原始數據的相似性，本質上，近鄰結構的保持是通過構建一個包含原始數據的鄰域信息的近鄰圖，并使用圖的拉普拉斯算子概念計算出一個變換矩陣，然后將原始數據通過此變換矩陣映射到低維空間表示[2]，Hash學習的目的即在于學習此變換矩陣.量化階段通過將降維后得到的實數值使用二進制稀疏表示，從而降低計算復雜度.量化也是一個有損變換，因此可能會對二進制編碼的最終質量產生顯著影響.盡管目前學者們提出了許多Hash學習方法，但大多數方法都僅聚焦于第1階段(投影階段)的信息損失，而忽略了第2階段(量化階段)的信息損失，只是簡單地采用單位編碼閾值劃分方法，并使用海明距離進行相似性度量.事實上，量化階段所要考慮的信息損失并不比投影階段所要考慮的信息損失少，甚至一個不好的量化策略，即使采用了較好的投影策略，也會造成最后的Hash效果非常差[3].

目前已有的ANN查詢方法所采用的量化策略基本都是使用統一位數來編碼每一個投影維度，但對于實際應用而言，不同的維度所包含的信息量必然不同，某些維度上的數據比較分散，信息量比較大，為了保持原始數據相互之間的相似性，就需要使用更多的位數來編碼這一維度；某些維度上的數據比較集中，甚至基本一致，就可以使用較少的位數來編碼這一維度，或者不需要對這一維度進行編碼.

另一方面，現有的量化策略基本都是采用閾值劃分的方法，并通過計算二進制編碼之間的海明距離來度量相似性.例如普遍使用的單位編碼量化(single-bit quantization, SBQ)策略通過設定一個閾值θ，第i位的數值為fi(x)，如果fi(x)≥θ，則該位編碼為1，否則編碼為0，當數據已經被歸一化且均值為0時，閾值θ通常被設置為0.少數使用2 b編碼量化的，如分層量化(hierarchical quantization, HQ)[4]和雙比特位量化(double-bit quantization, DBQ)[1]，將投影后的某一維數據編碼成2 b二進制，但此時仍使用海明距離來對二進制編碼的相似性進行度量，例如00與01的距離為1，00與10的距離也為1，而實際上00與10的距離應該要比00與01的距離大，因此破壞了原始數據的相似性，違反了Hash方法要保持原始數據相似性的初衷.

提出一種Hash學習的動態自適應的編碼量化(Hash learning-dynamic adaptive quantization, HL-DAQ)方法，根據每一維度的離散系數來為該維度動態分配編碼位數，以保證更多的原始信息被保留下來.同時，還提出一種根據編碼位數分配情況動態計算各編碼之間相似性距離的方法，主要工作概述有3個方面：

1) 提出一種動態自適應編碼量化策略，首先計算每一投影維度的離散系數，然后通過約束條件，最大限度地保持原始數據的近鄰結構，為盡量多的維度編碼，解決原始數據的局部結構保持問題.同時，信息量越大的維度使用更多的編碼位數，并使用動態規劃方法求得總信息熵最大的二進制編碼分配方式，解決原始數據的全局結構保持問題.

2) 提出一種動態自適應距離度量方式來度量自然二進制編碼的相似性，改進了原始基于海明距離的相似性度量方式只適用于單位量化以及近鄰結構保持不夠好等弊端，可以證明，利用動態自適應距離較海明距離而言更能保持原始數據的相似性.

3) 公開數據集上進行的實驗證明，HL-DAQ方法與其他已有的量化方法相比，能更好地保持原始數據的相似性，提高查詢準確率，并在圖像與非圖像數據集上具有通用性.

1 相關工作

目前已有的Hash算法基本可以分為兩大類：1)與數據集無關的Hash方法，例如局部敏感Hash(locality-sensitive Hash, LSH)[5]、位移不變的內核Hash(shift invariant kernel Hash, SIKH)[6]等，生成與數據集無關的隨機投影.與數據集無關的Hash方法通常需要比較長的二進制編碼來保證Hash函數的性能.2)與數據集有關的Hash方法，例如光譜Hash(spectral Hash, SH)[7]、主成分分析Hash(principal component analysis Hash, PCAH)[8]、快速Hash(fast Hash, FastH)[9]、迭代量化(iterative quantization, ITQ)[10]、監督離散Hash(supervised discrete Hash, SDH)[11]、可擴展離散Hash(scalable discrete supervised Hash, COSDISH)[12]等，其特征在于通過訓練數據集學習投影函數.一般來說，與數據集有關的Hash方法要比與數據集無關的Hash方法性能較好[13-14]，然而這些方法的主要目的都是希望找到一個高質量的投影方法，以達到最大限度保持原始數據相似性的目的，卻很少把注意力集中到量化階段.典型的量化方法為SBQ，它首先設定一個閾值，將投影后的每一維度的數值與此閾值進行比較，然后使用一個二進制位對此維度進行編碼.然而量化也是一個有損變換，降低了所表示數據的精度，并且使用簡單的單位量化方法會對所獲得的二進制編碼的檢索質量帶來顯著影響.近年來，一些研究者也相繼提出了一些更高位數的量化方法來解決這一局限性.

Liu等人[15]提出了一種用于錨點圖Hash(anchor graph Hash, AGH)的HQ方法，HQ通過將投影劃分為4種狀態，并使用2個位來對每個投影維度進行編碼.

Kong等人[1]提出了另一種稱之為DBQ的量化策略，更有效地保留了數據的近鄰結構，但是通過2 b編碼量化僅將投影維度量化為3個狀態，而不是可以編碼的4個2 b編碼.Lee等人[16]也提出了一種類似的方法，通過采用專門的距離度量方式來對4個2 b狀態進行度量.

Kong等人[17]還提出了一種更為靈活的量化方法稱為曼哈頓量化(Manhattan quantization, MQ)，它能夠將每個投影維度編碼成多個位組成的自然二進制碼(natural binary code, NBC)，并且曼哈頓距離度量方式有效地保留了數據的近鄰結構，該方法首次提出使用NBC的十進制距離來對原始數據距離進行度量.曼哈頓距離和海明距離的比較如圖1所示，可以看出，2 b曼哈頓距離度量方式的距離度量粒度顯然比海明距離度量方式更精細.

Fig. 1 Two distance measurement methods圖1 2種距離度量方式

上述提出的量化方法在標準SBQ上均有所改進，能夠顯著提高量化性能.然而，所有這些策略都具有明顯的局限性，即它們對每個預測維度采用固定的k位來進行編碼量化，沒有考慮到不同投影維度的信息量與數據分布不同.

基于離散系數的動態自適應編碼量化技術解決了這2個限制，提出了一種有效的編碼量化方法和信息離散性度量標準，并通過在每個投影維度上動態分配二進制編碼，解決保留最大原始數據信息量問題.

2 模型與定義

Fig. 2 HL-DAQ overall framework diagram圖2 HL-DAQ模型整體流程框架圖

本節給出HL-DAQ模型的執行流程框架圖以及一些相關概念的定義.HL-DAQ方法主要分為投影和量化2個階段，如圖2所示.首先從數據集中取出的數據經過諸如LSHPCAHITQ等投影方法進行降維，投影到低維矩陣上；然后再通過計算每一維度的離散系數值，根據離散系數值動態為每一維度分配編碼位數，使得總信息熵最大.進一步地，根據所分配的編碼位數，使用K-means[18]對每一維度進行聚類，根據聚類結果進行編碼得到二進制串，最后通過所提出的動態自適應距離度量方式計算數據對象之間的距離.

2.1 基于離散系數的動態自適應量化方法

定義1. 離散系數.給定一組數據分布f(X)，其離散系數表示為其標準差與均值的比值，定義為

(1)

Fig. 3 Two different sets of data with different ranges on different dimensions圖3 2個不同維度上值域不同的2類數據分布

其中,μi=E(fi(X))；E(fi(X))是表示X在投影fi(X)下的數據分布中心，即均值，數學上該式被稱為標準差系數，標準差系數是衡量數據中各觀測值離散程度的一個統計量[19].當進行2個或多個數據離散程度的比較時，如果度量單位與平均數相同，可以直接利用標準差來比較.如果單位和(或)平均數不同，比較其離散程度就不能采用標準差，而需采用標準差與平均數的比值(相對值).離散系數較大的表明數據的分布情況差異也大，從而需要分配更多的編碼位進行編碼，反之則較少.離散系數可以消除單位和(或)平均數不同對2個或多個數據離散程度比較的影響.

假設從諸如PCAH或LSH等某種Hash方法中得到了m維投影{f1(x),f2(x),…,fm(x)}，首先定義這些投影信息量的度量方式.在信息理論中，方差和熵都是公認的信息量的度量方式[20]，可以作為每個投影的信息量度量選擇，但實際上由于不同維度所表達的信息不一樣，其取值范圍也不一樣，例如：

如圖3所示，Y1的方差為6.386，而Y2的方差為0.13，如果使用方差來表示信息量并為投影維度分配二進制編碼位，Y1的編碼位數將比Y2大許多倍，然而從整體分布來看，顯然Y1的分布比較集中，而Y2的分布比較分散，使用方差來度量信息量并對編碼位數進行分配的話，顯然不能很好地保持Y2的近鄰結構，一種更為合理的方案是，根據原始數據計算其數據的離散程度，用離散系數表示，如定義1所示.

對于圖3中的2組數據，根據式(1)計算可得，Y1的離散系數為0.548，Y2的離散系數為0.724，因此使用離散系數對信息量進行度量并分配編碼位數的情況下，Y2所分配的編碼位數將比Y1的多或至少相當，因此更能保證原始數據的近鄰結構.

根據生成投影的獨立性，所有投影的總離散系數可計算得到：

(2)

通過計算每一投影維度離散系數占總離散系數的比重，來為該維度動態分配可變數量的位.如果該維度的離散系數足夠小，那么分配給該維度的位可以為0；如果該維度的離散系數足夠大，分配給該維度的位也可以是總位數.

將k位分配給某一維投影，對于該投影維度將產生2k個不同的二進制編碼.因此，在該維度中應該有2k個質心，將其分成2k個間隔或簇.每個數據點被分配給這些簇之一并由其對應的二進制編碼表示.

為了準確度量二進制編碼串所能保持的近鄰結構信息量，定義一種新的近鄰結構信息熵概念.

定義2. 近鄰結構信息熵.給定數據集X={xi},i=1,2,…,n，其近鄰結構信息熵定義為每一投影維度量化后的編碼位數與該維度的信息量的乘積：

(3)

其中,CV(xi)表示第i維投影的離散系數，即信息量;k(xi)表示第i維投影所分得的量化編碼位數.由此可知，要使得最終二進制編碼所包含的原始數據近鄰結構信息量最大，就得使信息熵最大，即使得每一投影維度的編碼位數與其離散系數的乘積之和最大.

2.2 動態自適應編碼量化方法的位分配方式

s.t. ?i∈{1,2,…,m},ki∈{0,1,…,L}，

(4)

對于總長度為L位的m維投影{f1(x),f2(x),…,fm(x)}和對應的信息熵，通過求解式(4)，可以找到每個投影的最佳位分配，使得來自m維投影的總信息熵最大化.然而，優化該目標函數是一個組合問題，可能的分配方式是指數級的，如何得到最佳分配方式成為問題關鍵.

一種較簡單的方式實現最優位分配問題如下：

給定二進制散列長度L和m維投影，其總信息熵表示為

(5)

然后近鄰結構信息熵由如下貝爾曼方程[21]來表示：

(6)

定理1. 假設使用L位二進制對一個m維的數據X={x1,x2,…,xm}進行編碼，設傳統固定位數編碼量化方法的近鄰結構信息熵為G1(X)，基于離散系數的動態自適應量化方法的近鄰結構信息熵為G2(X)，那么G2(X)≥G1(X)恒成立.

證明. 根據式(3)計算近鄰結構信息熵，當使用傳統固定位數編碼量化方法時，每一維度被編碼成Lm位，那么總信息熵為當使用基于離散系數的動態自適應量化編碼方法時，由于編碼位數根據離散系數進行分配，根據動態規劃求解最優分配思想，同時需滿足離散系數越大所對應的編碼位數也越多，因此當離散系數為CV(xi)時，設編碼位數為a×CV(xi)，并且滿足此時的總信息熵為根據計算：

(7)

證畢.

當原始數據本身均勻分布，度量單位也一致，即信息量均勻分布，那么采用固定位編碼方式時復雜度為O(1)，而使用此編碼方式復雜度將大大增加，因此此方法在信息量均勻分布的數據集上不具有優勢.然而，原始數據均分分布的數據集在現實場景下幾乎是不存在的.

2.3 基于自然二進制編碼十進制距離的距離度量算法

引言提到，現階段已有的二進制編碼距離度量方式主要包括海明距離和曼哈頓距離.2種方法都是采用固定編碼長度的度量方式，需要首先確定每一投影所使用的二進制編碼長度[23]，其中曼哈頓距離第1次提出使用NBC的十進制距離來對二進制編碼進行度量.海明距離只適用于單位量化，例如當某一維度被編碼成2 b二進制時，其海明距離和十進制距離如圖4、圖5所示：

Fig. 4 Hamming distance under two binary codes圖4 2 b二進制編碼下的海明距離

其中每條線段表示距離為1，但在這種距離度量模式下，00—10的距離與00—01的距離是相等的，都為1，而實際上2 b自然二進制編碼下00—10的距離應該要比00—01的距離大.并且，01—10的距離由實際上的1被擴大到了2，00—11的距離也由實際上的3被縮小到了2，使得00—11的距離與01—10的距離相等，這顯然破壞了原始數據的相似性，給距離度量結果造成了很大的誤差[24].

定義3. 動態自適應距離.給定量化時每一投影維度所分配的NBC長度，以及每一投影維度量化后得到的二進制串，2點之間的動態自適應距離即為它們各個維度上二進制編碼所對應的NBC之間的十進制距離的差的總和.令x=(x1,x2,…,xm)T，y=(y1,y2,…,ym)T，編碼分配方式為K=(k1,k2,…,km)，那么x和y之間的動態自適應距離定義如下：

(8)

定理2. 動態自適應距離對于原始數據近鄰結構的保持優于海明距離.

證畢.

3 動態自適應編碼量化方法相關算法

本節對所提出的相關算法進行了詳細的描述，包括動態自適應編碼量化算法和動態自適應距離度量算法，分別對應圖2中的量化階段和距離度量階段.

3.1 動態自適應編碼量化算法

算法1. 動態規劃獲取最優二進制編碼分配算法.

輸出：二進制編碼最優分配方案K=(k1,k2,…,km).

① for eachi=1:m

② for each integer ofki=0:kmax

③ if (G(Xi,ki))=ki×CVi沒有被計算過)

④temp[ki,CVi]=ki×CVi；

⑤ elseG(Xi,ki)=temp[ki,CVi]；

⑥ end if

G(Xi,ki)

G(Xi,ki)；*G(Xi,ki))表示數據X的第i維被編碼成ki位時的信息熵，表示余下m-1維的總信息熵，初值為0 *

⑨ end if

⑩ end for

對于給定的維度m、編碼長度L，算法1的行③～⑨的計算復雜度為O(1)，加之嵌套的2重循環，因此總時間復雜度為O(mL).

給定經過某個具有m維投影的現有投影方法(如LSH，PCAH，ITQ等)學習過后的訓練與測試數據集，一個固定的Hash編碼長度L，基于離散系數的動態自適應編碼量化方法可以描述如下：

算法2. 動態自適應量化編碼算法.

輸入：投影矩陣U_trn、為所有投影維度編碼的二進制總長度L;

輸出：編碼好的二進制編碼矩陣U_trn.

① for each dimension of the matrixU_trn

② 計算離散系數

③ end for

⑤ 給定信息熵的計算公式G(xi)=k(xi)-CV(xi)以及目標函數

⑥ 根據算法1得到最優分配K=(k1,k2,…,km)；

⑦ for each dimension of the matrixU_trni=1:m

⑧ ifki>0

⑩ end if

size(U_trn,1)*訓練數據集大小*

假設訓練數據集大小為n，數據維度為m維，對各階段時間復雜度進行分析，行①～③計算離散系數為O(m)；行⑥動態規劃求最佳編碼分配為O(mL)，其中L是編碼長度，為編碼前指定的定值；對于給定迭代次數T，行⑦～對每一維度使用K-means聚類并對所有數據進行分類為其中ki最大為常數L，因此時間復雜度為O(mn)；行～對訓練數據集進行編碼為O(mn).綜上，總時間復雜度為O(mn)，受數據規模影響不大，適合處理大規模數據.

3.2 動態自適應距離度量算法

對于根據動態自適應算法編碼好的二進制串，使用動態自適應距離對各編碼之間的相似度進行度量，動態自適應距離度量算法描述如算法3.

算法3. 動態自適應距離度量算法.

輸入:編碼好的訓練集二進制矩陣UX_trn、編碼好的測試集二進制矩陣UX_tst、二進制編碼分配K=(k1,k2,…,km)；

輸出:距離矩陣D.

①D=zeros[size(UX_trn,1),size(UX_tst)]；

② for each row of the matrixUX_trni=1:size(UX_trn,1)*訓練數據集大小*

③ for each row of the matrixUX_tsti=1:size(UX_tst,1)*測試數據集大小*

④ for each dimension of the matrixUX_trnm=1:size(UX_trn,2)*數據對象維度*

⑤ ifkm>0

⑦D(i,j)=D(i,j)+|UX_trn(i,a:b)-UX_tst(j,a:b)|；*UX_trn(i,a:b)表示數據集中第i行(第i個數據)的第a列到第b列(第a維到第b維)*

⑧ end if

⑨ end for

⑩ end for

對于m×n1維的訓練數據集和m×n2維測試數據集，算法3行⑦的計算復雜度為O(1)，對于3重循環，因此總復雜度為O(mn1n2).

4 算法性能對比實驗

4.1 實驗數據集

為了驗證所述方法的性能，利用4個公開圖像數據集及1個非圖像數據集與已有方法進行比較實驗：

1) CIFAR-10①.該數據集是8 000萬個微小圖像數據集中的一個子集，總大小174 MB，包括6萬幅圖像，分成10個類別，每幅圖像由3 072個特征描述(32×32 RGB像素圖像)，其中5萬幅為訓練圖像，1萬幅為測試圖像.

2) NUS-WIDE②.由大約27萬幅圖像組成，總大小1.1 GB，包括5 018個類別，每幅圖像有634個特征.

3) Gist-1M-960③.由960個gist特征描述的100萬幅圖像，總大小5.37 GB.

4) 22K-LabelMe④.從大的LabelMe數據集中采樣的22 019幅圖像，總大小5.94 GB，每幅圖像由512個GIST特征描述符表示.

5) 20Newsgroups⑤.包括大約2萬個新聞文檔，分成20個類別，總大小16.5 MB.

4.2 ANN相關評價指標

采用普遍的方案，將到每個點的前50個最近鄰點的平均距離設置為確定點對于查詢點是否是真實“命中”的閾值.對于所有實驗，隨機選擇1 000個點作為查詢點，其余點作為訓練點.最終結果是由10組隨機訓練查詢分區的平均值.評價指標包括查準率(Precision)、召回率(Recall)和平均準確率(mAP)，定義如下：

4.3 實驗對比方法

為了測試HL-DAQ策略的影響，對現有的Hash量化方法進行改進，提取已有Hash方法的投影方法，將它們組合到不同的量化方法中，并比較其性能，所采用的Hash投影方法有：

1) LSH—通過從標準高斯函數隨機采樣獲得投影；

2) PCAH—使用數據的主方向作為投影；

3) ITQ—找到使量化損失最小的正交旋轉矩陣的迭代法;

4) 將HL-DAQ方法與SBQ，DBQ，2-MQ這3種量化方法進行比較：

5) SBQ—單位數量化，大多數Hash方法使用的標準技術；

6) DBQ—2 b量化；

7) 2-MQ—使用曼哈頓距離的2 b量化.

測試多種Hash方法和量化方法的組合，表示為每個“XXX-YYY”，其中XXX表示Hash方法，YYY表示量化方法.例如PCAH-DBQ表示使用DBQ量化的PCAH方法.

4.4 實驗結果與分析

為了說明動態自適應量化方法的一般性和有效性，將3種不同的投影方法與4種不同的量化方法進行組合，并且在5個不同的數據集上進行同樣的測試，測試結果如表1～5所示.其中表1～5分別給出了3種Hash投影方法與4種編碼量化方法的不同組合在22K-LabelMe，CIFAR-10，Gist-1M-960，NUS-WIDE，20Newsgroups數據集上，就編碼位數分別為32 b，64 b，128 b情況下的平均準確率mAP.由表1～5可知，在不同的Hash投影方法和不同的編碼位數下，HL-DAQ方法均比其他量化編碼算法具有更高的mAP，由此可知，動態自適應量化編碼方法與動態自適應距離在大多數情況下實現了較好性能.

圖6～9給出了4種量化編碼方法分別組合LSH，PCAH，ITQ這3種Hash投影方法在CIFAR-10，Gist-1M-960，NUS-WIDE，20Newsgroups數據集下的某一次實驗結果，其中每幅圖中的第1個坐標系給出的是Recall與Precision的關系，第2個坐標系給出的是檢索樣本數與Recall的關系，第3個坐標系給出的是檢索樣本數與Precision的關系，第4個坐標系給出的是編碼位數與mAP的關系.由圖6可知，數據集采用CIFAR-10、Hash投影方法采用LSH時，在相同Recall下，HL-DAQ比其他量化方法具有更高的Precision；在相同Precision下，HL-DAQ比其他量化方法具有在更高的Recall；但在相同檢索樣本點數量情況下，HL-DAQ的Precision與Recall均稍遜于DBQ；在所有編碼位數情況下，HL-DAQ均比其他方法具有更高的mAP.圖7采用的數據集為Gist-1M-960，Hash投影方法采用的是PCAH，其結果與圖6基本一致，只是在相同Recall情況下，HL-DAQ的Precision稍遜于DBQ和MQ.圖8給出的是數據集采用NUS-WIDE、Hash投影方法采用ITQ時的實驗結果，HL-DAQ各項性能明顯均優于其他3種量化編碼方法.圖9給出的是數據集采用20Newsgroups、Hash投影方法采用LSH時的實驗結果，其結果與圖6基本一致，證明提出的方法不僅僅適用于圖像數據集，對非圖像數據集具有通用性.

Table 1 The mAP Comparison under Different Hash Projection Methods Combined with DifferentQuantitative Coding Methods on 22K-LableMe Dataset表1 22K-LableMe數據集上不同Hash投影方法與不同量化編碼方法組合的mAP比較

Table 2 The mAP Comparison under Different Hash Projection Methods Combined withDifferent Quantitative Coding Methods on CIFAR-10 Dataset表2 CIFAR-10數據集上不同Hash投影方法與不同量化編碼方法組合的mAP比較

Table 3 The mAP Comparison under Different Hash Projection Methods Combined withDifferent Quantitative Coding Methods on Gist-1M-960 Dataset表3 Gist-1M-960數據集上不同Hash投影方法與不同量化編碼方法組合的mAP比較

Table 4 The mAP Comparison under Different Hash Projection Methods Combined withDifferent Quantitative Coding Methods on NUS-WIDE Dataset表4 NUS-WIDE數據集上不同Hash投影方法與不同量化編碼方法組合的mAP比較

Table 5 The mAP Comparison under Different Hash Projection Methods Combined withDifferent Quantitative Coding Methods on 20Newsgroups Dataset表5 20Newsgroups數據集上不同Hash投影方法與不同量化編碼方法組合的mAP比較

Fig. 6 Comparison of four quantization effects combined with LSH projection method on CIFAR-10 dataset圖6 CIFAR-10數據集下LSH投影方法4種量化效果比較

Fig. 7 Comparison of four quantization effects combined with PCAH projection method on Gist-1M-960 dataset圖7 Gist-1M-960數據集下PCAH投影方法4種量化效果比較

Fig. 8 Comparison of four quantization effects combined with ITQ projection method on NUS-WIDE dataset圖8 NUS-WIDE數據集下ITQ投影方法4種量化效果比較

Fig. 9 Comparison of four quantization effects combined with LSH projection method on 20Newsgroups dataset圖9 20Newsgroups數據集下LSH投影方法4種量化效果比較

根據典型的實驗結果，LSH通常比其他現有技術的Hash方法(例如ITQ，PCAH，SH)性能更差.為了演示量化階段的重要性，將HL-DAQ方法添加到LSH中，并將得到的“LSH-DAQ”方法與其他最先進的技術進行比較.在22K-LabelMe數據集上運行實驗，實驗結果如圖10所示.結果表明，雖然標準LSH算法平常效果比較差，簡單地替換其默認量化方案與HL-DAQ方法相結合產生的結果顯著優于其他的先進Hash方法.

Fig. 10 Comparison of LSH projection combination DAQ quantization method and other methods圖10 LSH投影組合DAQ量化方法與其他方法效果比較

5 結 論

現有的Hash方法通常忽略在量化階段學習和適應的重要性.HL-DAQ方法較以前的算法具有更好的效果.對現有的Hash應用帶來了顯著改善，并且表明量化學習在很大程度上還沒有被研究，是亟需要發展突破的研究領域.有理由相信，量化學習的研究定將促進數據挖掘和信息檢索方面準確率的更大提升.

[1]Kong Weihao, Li Wujun. Double-bit quantization for hashing[C]Proc of the 26th AAAI Conf on Artificial Intelligence. Menlo Park, CA: AAAI, 2013: 137-138

[2]He Xiaofei, Cai Deng, Yan Shuicheng, et al. Neighborhood preserving embedding[C]Proc of the 10th IEEE Int Conf on Computer Vision. Los Alamitos, CA: IEEE Computer Society, 2005: 1208-1213

[3]Li Wujun, Zhou Zhihua. Learning to Hash for big data: Current status and future trends[J]. Chinese Science Bulletin, 2015, 60(5): 485-490 (in Chinese)(李武軍, 周志華. 大數據哈希學習: 現狀與趨勢[J]. 科學通報, 2015, 60(5): 485-490)

[4]Wang Wei, Yang Xiaoyan, Ooi B C, et al. Effective deep learning-based multi-modal retrieval[J]. The VLDB Journal, 2016, 25(1): 79-101

[5]Long Mingsheng, Cao Yue, Wang Jianmin, et al. Composite correlation quantization for efficient multimodal retrieval[C]Proc of the 39th Int ACM SIGIR Conf on Research and Development in Information Retrieval. New York: ACM, 2016: 579-588

[6]Heo Jae-Pil, Lee Youngwoon, He Junfeng, et al. Spherical hashing: Binary code embedding with hyperspheres[J]. IEEE Trans on Pattern Analysis & Machine Intelligence, 2015, 37(11): 2304-2316

[7]Wang Jun, Liu Wei, Kumar Sanjiv, et al. Learning to Hash for indexing big data—A survey[J]. Proceedings of the IEEE, 2015, 104(1): 34-57

[8]Tsai Yi-Hsuan, Yang Ming-Hsuan. Locality preserving hashing[C]Proc of the 2014 IEEE Int Conf on Image Processing. Piscataway, NJ: IEEE, 2014: 2988-2992

[9]Zhong Zisha, Fan Bin, Ding Kun, et al. Efficient multiple feature fusion with hashing for hyperspectral imagery classification: A comparative study[J]. IEEE Trans on Geoscience & Remote Sensing, 2016, 54(8): 4461-4478

[10]Liu Haomiao, Wang Ruiping, Shan Shiguang, et al. Deep supervised hashing for fast image retrieval[C]Proc of the 2016 IEEE Conf on Computer Vision and Pattern Recognition. Los Alamitos, CA: IEEE Computer Society, 2016: 2064-2072

[11]Shen Fumin, Shen Chunhua, Liu Wei, et al. Supervised discrete hashing[C]Proc of the 2015 IEEE Conf on Computer Vision and Pattern Recognition. Los Alamitos, CA: IEEE Computer Society, 2015: 37-45

[12]Zhang Shifeng, Li Jianmin, Guo Jinma, et al. Scalable discrete supervised Hash learning with asymmetric matrix factorization[C]Proc of the 16th IEEE Int Conf on Data Mining (ICDM). Piscataway, NJ: IEEE, 2016: 1347-1352

[13]Qian Jiangbo, Zhu Qiang, Chen Huahui. Multi-granularity locality-sensitive Bloom filter[J]. IEEE Trans on Computers, 2015, 64(12): 3500-3514

[14]Qian Jiangbo, Zhu Qiang, Chen Huahui. Integer-granularity locality-sensitive Bloom filter[J]. IEEE Communications Letters, 2016, 20(11): 2125-2128

[15]Liu Wei, Wang Jun, Kumar S, et al. Hashing with graphs[COL]Proc of the 28th Int Conf on Machine Learning. 2011[2017-02-01]. http:machinelearning.wustl.edumlpaperspaper_filesICML2011Liu_6.pdf

[16]Lee Youngwoon, Heo Jae-Pil, Yoon Sung-Eui. Quadra-embedding: Binary code embedding with low quantization error[J]. Computer Vision and Image Understanding, 2014, 125(8): 214-222

[17]Kong Weihao, Li Wujun, Guo Minyi. Manhattan hashing for large-scale image retrieval[C]Proc of the 35th Int ACM SIGIR Conf on Research and Development in Information Retrieval. New York: ACM, 2012: 45-54

[18]Silva J A, Faria E R, Barros R C, et al. Data stream clustering: A survey[J]. ACM Computing Surveys, 2013, 46(1): 1-31

[19]Moran S, Lavrenko V, Osborne M. Variable bit quantisation for LSH[COL]Proc of the 51st Annual Meeting of the Association for Computational Linguistics. 2013 [2017-02-01]. https:www.aclweb.organthologyP13-2132

[20]Duan Lingyu, Lin Jie, Wang Zhe, et al. Weighted component hashing of binary aggregated descriptors for fast visual search[J]. IEEE Trans on Multimedia, 2015, 17(6): 1-1

[21]Groeneveld R A, Meeden G. The mode, median, and mean inequality[J]. The American Statistician, 1977, 31(3): 120-121

[22]Dolcetta I C, Ishii H. Approximate solutions of the Bellman equation of deterministic control theory[J]. Applied Mathematics & Optimization, 1984, 11(1): 161-181

[23]Li Peng, Wang Meng, Cheng Jian, et al. Spectral hashing with semantically consistent graph for image indexing[J]. IEEE Trans on Multimedia, 2013, 15(1): 141-152

[24]Moran S, Lavrenko V, Osborne M. Neighbourhood preserving quantisation for LSH[C]Proc of the 36th Int ACM SIGIR Conf on Research and Development in Information Retrieval. New York: ACM, 2013: 1009-1012

ZhaoLiang, born in 1992. Master in Nanjing University of Science and Technology. His main research interests include approxi-mate nearest neighbor search, intelligent computing and system.

WangYongli, born in 1974. Professor, PhD supervisor. His main research interests include big data analysis, intelligent services and cloud computing.

DuZhongshu, born in 1993. Master candidate in Nanjing University of Science and Technology. His main research interests include approximate nearest neighbor search, distributed system and hashing.

ChenGuangsheng, born in 1971. Technician. His main research interests include machine learning, electronic instrument designing and intelligent computing.