顧廣華 霍文華 蘇明月 付 灝

(燕山大學(xué)信息科學(xué)與工程學(xué)院 秦皇島 066000)

(河北省信息傳輸與信號處理重點實驗室 秦皇島 066000)

1 引言

隨著實際應(yīng)用中數(shù)據(jù)的爆炸式增長，最近鄰搜索在信息檢索、計算機視覺等領(lǐng)域有著廣泛的應(yīng)用。然而，在大數(shù)據(jù)應(yīng)用中，對于給定的查詢，最近鄰搜索通常是很耗時的。因此，近年來，近似最近鄰(Artificial Neural Network，ANN)搜索[1]變得越來越流行。在現(xiàn)有的ANN技術(shù)中，哈希以其快速的查詢速度和較低的內(nèi)存成本成為最受歡迎和有效的技術(shù)之一。哈希方法[2,3]的目標(biāo)是將多媒體數(shù)據(jù)從原來的高維空間轉(zhuǎn)換為緊湊的漢明空間，同時保持數(shù)據(jù)的相似性。這些二進制哈希碼不僅可以顯著降低存儲成本，在信息搜索中實現(xiàn)恒定或次線性的時間復(fù)雜度，而且可以保持原有空間中存在的語義結(jié)構(gòu)。

現(xiàn)有的哈希方法大致可分為兩類：獨立于數(shù)據(jù)的哈希方法和依賴于數(shù)據(jù)的哈希方法。局部敏感哈希(Locality Sensitive Hashing, LSH)[4]及其擴展作為最典型的獨立于數(shù)據(jù)的哈希方法，利用隨機投影得到哈希函數(shù)。但是，它們需要較長的二進制代碼才能達到很高的精度。由于數(shù)據(jù)獨立哈希方法的局限性，近年來的哈希方法嘗試利用各種機器學(xué)習(xí)技術(shù)，在給定數(shù)據(jù)集的基礎(chǔ)上學(xué)習(xí)更有效的哈希函數(shù)。

依賴于數(shù)據(jù)的哈希方法從可用的訓(xùn)練數(shù)據(jù)中學(xué)習(xí)二進制代碼，也就是學(xué)習(xí)哈希?，F(xiàn)有的數(shù)據(jù)依賴哈希方法根據(jù)是否使用監(jiān)督信息進行學(xué)習(xí)，可以進一步分為無監(jiān)督哈希方法和監(jiān)督哈希方法。代表性的無監(jiān)督哈希方法包括迭代量化(IteraTive Quantization, ITQ)[5]，離散圖哈希(Discrete Graph Hashing, DGH)[6]、潛在語義最小哈希(Latent Semantic Minimal Hashing, LSMH)[7]和隨機生成哈希(Stochastic Generative Hashing, SGH)[8]。無監(jiān)督哈希只是試圖利用數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)緊湊的二進制代碼來提高性能，而監(jiān)督哈希則是利用監(jiān)督信息來學(xué)習(xí)哈希函數(shù)。典型的監(jiān)督哈希方法包括核監(jiān)督哈希(Supervised Hashing with Kernels, KSH)[9]，監(jiān)督離散哈希(Supervised Discrete Hashing, SDH)[10]和非對稱離散圖哈希(Asymmetric Discrete Graph Hashing, ADGH)[11]。近年來，基于深度學(xué)習(xí)的哈希方法[12]被提出來同時學(xué)習(xí)圖像表示和哈希編碼，表現(xiàn)出優(yōu)于傳統(tǒng)哈希方法的性能。典型的深度監(jiān)督哈希方法包括深度成對監(jiān)督哈希(Deep Supervised Hashing with Pairwise Labels, DPSH)[13]，深度監(jiān)督離散哈希(Deep Supervised Discrete Hashing,DSDH)[14]，和深度離散監(jiān)督哈希(Deep Discrete Supervised Hashing, DDSH)[15]。通過將特性學(xué)習(xí)和哈希碼學(xué)習(xí)集成到相同的端到端體系結(jié)構(gòu)中，深度監(jiān)督哈希[16,17]可以顯著優(yōu)于非深度監(jiān)督哈希。然而，現(xiàn)有的深度監(jiān)督哈希方法主要利用成對監(jiān)督進行哈希學(xué)習(xí)，語義信息沒有得到充分利用，這些信息有助于提高哈希碼的語義識別能力。更困難的是，對于大多數(shù)數(shù)據(jù)集，每個項都由多標(biāo)簽信息進行注釋。因此，不僅需要保證多個不同的項對之間具有較高的相關(guān)性，還需要在一個框架中保持多標(biāo)簽語義，以生成高質(zhì)量的哈希碼。

為了解決上述問題，本文提出了一種非對稱監(jiān)督深度離散哈希(Asymmetric Supervised Deep Discrete Hashing, ASDDH)方法。具體來說，為了生成能夠完全保留所有項的多標(biāo)簽語義的哈希碼，提出了一種非對稱哈希方法，利用多標(biāo)簽二進制碼映射，使哈希碼具有多標(biāo)簽語義信息。此外，本文還引入了二進制代碼的位平衡性，進一步提高哈希函數(shù)的質(zhì)量。在優(yōu)化過程中，為了減小量化誤差，利用離散循環(huán)坐標(biāo)下降法對目標(biāo)函數(shù)進行優(yōu)化，以保持哈希碼的離散性。

2 非對稱監(jiān)督深度離散哈希

2.1 符號和問題定義

2.2 模型表述

圖1 ASDDH模型體系結(jié)構(gòu)

2.3 損失函數(shù)

為了提高所學(xué)哈希碼的準(zhǔn)確性，本文還使學(xué)習(xí)的二進制碼具有以下特性：(1)語義分類最優(yōu)。直接利用標(biāo)簽信息，使所學(xué)習(xí)的二進制碼對于聯(lián)合學(xué)習(xí)的線性分類器是最優(yōu)的。(2)多標(biāo)簽語義保存。引入一種非對稱哈希方法，該方法利用多標(biāo)簽二進制碼映射，使哈希碼保留多標(biāo)簽語義信息。(3)位平衡。使學(xué)習(xí)的哈希碼的每個位有50%的概率為1或-1。

本文使用一個簡單的線性分類器來建模學(xué)習(xí)的二進制代碼和標(biāo)簽信息之間的關(guān)系：

其中W ∈RK×c是分類器權(quán)重。則分類損失可以表示為

這里L(fēng)(·)是損失函數(shù)，本文選擇的是線性分類器的l2損失。‖·‖F(xiàn)是矩陣的Frobenius范數(shù)，λ是正則化參數(shù)雖然式(1)實現(xiàn)了成對監(jiān)督信息的保存，式(4)實現(xiàn)了最優(yōu)的線性分類，但忽略了多標(biāo)簽語義的保存。

其中y^i=yi×2?1∈{?1,1}c。

為了使哈希碼的每一位在所有訓(xùn)練集上保持平衡。本文增加了位平衡損失項來最大化每一位所提供的數(shù)據(jù)點信息。更具體地，在所有訓(xùn)練點上，對每個位進行了平衡，鼓勵所有訓(xùn)練樣本中的-1和+1的數(shù)目近似。此時編碼達到平衡，信息量最大，哈希編碼最優(yōu)。該損失項表示為

其中IN×1表示所有元素都等于1的矩陣。綜合考慮式(1)、式(4)、式(5)和式(6)，得到整體目標(biāo)函數(shù)為

由于具有式(7)中的二進制約束離散優(yōu)化求解非常具有挑戰(zhàn)性，現(xiàn)有的方法大多采用對二進制約束進行連續(xù)松弛的方法。在測試階段，對連續(xù)輸出應(yīng)用閾值函數(shù)得到哈希碼。然而，這種連續(xù)松弛會通過對哈希碼的連續(xù)嵌入進行二值化而產(chǎn)生不可控制的量化誤差。為了克服這種局限性，本文采用了一種新的離散求解策略，將sign(hi)設(shè)置為接近它對應(yīng)的哈希碼bi。然而，由于sign(hi)中的hi梯度處處為零，很難進行反向傳播。本文將tanh(·)應(yīng)用于sign(·)函數(shù)的軟逼近。為了控制量化誤差，縮小期望二進制碼與松弛之間的距離，在hi上加了額外的懲罰項來逼近期望的離散二進制碼bi。將式(7)重新表述為

2.4 優(yōu)化算法

由目標(biāo)函數(shù)式(8)可知，該損失函數(shù)的優(yōu)化問題是非凸非光滑的，很難直接得到最優(yōu)解。為了找到一個可行的解，本文使用的是交替優(yōu)化的方法，這種方法在哈希文獻[13,14]中得到了廣泛的應(yīng)用：固定其他變量更新一個變量。更具體地說，本文依次對深度神經(jīng)網(wǎng)絡(luò)參數(shù)、分類器權(quán)重W、二進制碼矩陣B和多標(biāo)簽二進制映射Q的參數(shù)進行迭代更新，步驟如下:

(1)更新H，固定W,B和Q。當(dāng)固定B和Q時，利用隨機梯度下降法(SGD)學(xué)習(xí)深度神經(jīng)網(wǎng)絡(luò)的參數(shù)。特別地，在每次迭代中，從整個訓(xùn)練數(shù)據(jù)集中抽取一小批圖像樣本，并使用反向傳播算法對整個網(wǎng)絡(luò)進行更新。這里表示U=tanh(H)。損失函數(shù)的導(dǎo)數(shù)為

(3)更新B，固定H,W和Q。將問題式(8)重寫為矩陣形式：

3 實驗

3.1 實驗設(shè)置

本文在兩個廣泛使用的基準(zhǔn)數(shù)據(jù)集上進行了實驗：CIFAR-10和NUS-WIDE。每個數(shù)據(jù)集被分為查詢集和檢索集，從檢索集中隨機選取訓(xùn)練集。CIFAR-10數(shù)據(jù)集是一個單標(biāo)簽數(shù)據(jù)集，包含60000張像素為32×32的彩色圖像和10類圖像標(biāo)簽。對于CIFAR-10數(shù)據(jù)集，如果兩幅圖像共享一個相同的標(biāo)簽，則它們將被認為是相似的。NUS-WIDE數(shù)據(jù)集由與標(biāo)簽相關(guān)的269,648幅Web圖像組成。它是一個多標(biāo)簽數(shù)據(jù)集，其中每個圖像都使用來自5018個標(biāo)簽的一個或多個類標(biāo)簽進行注釋。與文獻[13,14]類似，只使用屬于21個最常見的標(biāo)簽的195,834張圖像。每個類在這個數(shù)據(jù)集中至少包含5000張彩色圖像。對于NUS-WIDE數(shù)據(jù)集，如果兩個圖像至少共享一個公共標(biāo)簽，則它們將被認為是相似的。

遵循文獻[14]的實驗設(shè)置。對于CIFAR-10數(shù)據(jù)集，每個類隨機選取100張圖像作為查詢集，其余的圖像作為檢索集。從檢索集中隨機抽取每類500幅圖像作為訓(xùn)練集。對于NUS-WIDE數(shù)據(jù)集，隨機抽取2100幅圖像(每個類100幅圖像)作為查詢集，其余的圖像構(gòu)成檢索集。并且使用檢索集中每類500幅圖像作為訓(xùn)練集。對于ASDDH方法，算法的參數(shù)都是基于標(biāo)準(zhǔn)的交叉驗證過程設(shè)定的。實驗中設(shè)置α=1，β=1，μ=0.1，η=55，τ=0.001，γ=1。為了避免正相似和負相似信息的類不平衡問題所帶來的影響，將S中元素-1的權(quán)重設(shè)為元素1與元素-1在S中的數(shù)量之比。

3.2 基線和評價標(biāo)準(zhǔn)

本文選擇了一些典型方法作為基線進行比較。對于基線，大致將其分為兩組：傳統(tǒng)哈希方法和深度哈希方法。傳統(tǒng)哈希方法包括無監(jiān)督哈希方法和監(jiān)督哈希方法。無監(jiān)督哈希方法包括SH(Spectral Hashing)[19], ITQ[5]。監(jiān)督哈希方法包括SPLH(Sequential Projection Learning for Hashing)[20],KSH[9], FastH(Fast Supervised Hashing)[21],LFH(Latent Factor Hashing)[22]和SDH[10]。傳統(tǒng)的哈希方法采用手工特征作為輸入。本文將傳統(tǒng)哈希方法的手工特征替換為由卷積神經(jīng)網(wǎng)絡(luò)提取的深度特征作為基線進行比較，比如表1中的“FastH+CNN”表示FastH方法利用卷積神經(jīng)網(wǎng)絡(luò)提取特征取代手工特征，其它方法同理。深度哈希方法包括DQN(Deep Quantization Network)[23]，DHN(Deep Hashing Network)[24]，CNNH(Convolutional Neural Network Hashing)[25]，NINH[26]，DPSH[13]，DTSH(Deep Supervised Hashing with Triplet Labels)[27]和DSDH[14]。對于深度哈希方法，首先將所有圖像的大小調(diào)整為224像素×224像素，然后直接使用原始圖像像素作為輸入。本文采用在ImageNet數(shù)據(jù)集上預(yù)訓(xùn)練的AlexNet網(wǎng)絡(luò)初始化ASDDH框架的前7層，其它深度哈希方法也采用了類似的初始化策略。

為了定量地評估本文方法和基線方法，本文采用了一種常用的度量方法：平均準(zhǔn)確率均值(Mean Average Precision, MAP)。NUS-WIDE數(shù)據(jù)集上的MAP值是根據(jù)返回的前5000個最近鄰來計算的。CIFAR-10數(shù)據(jù)集的MAP是基于整個檢索集計算的。所有實驗運行5次，并報告平均值。

3.3 精確度

表1報告了兩個數(shù)據(jù)集上所有基線方法和提出的ASDDH方法的MAP結(jié)果。其中DSDH*表示本文重新運行DSDH原作者提供代碼的實驗結(jié)果。從表1可以看出：(1)本文ASDDH方法顯著優(yōu)于所有基線；(2)在大多數(shù)情況下，監(jiān)督方法優(yōu)于無監(jiān)督方法。這表明深度監(jiān)督哈希是一種更兼容的哈希學(xué)習(xí)體系結(jié)構(gòu)。

表1 兩個數(shù)據(jù)集上不同方法的MAP

在CIFAR-10數(shù)據(jù)集上，隨著編碼長度從12增加到48，ASDDH計算得到的MAP分數(shù)從0.763增加到0.785，遠遠優(yōu)于傳統(tǒng)的基于深度學(xué)習(xí)特征的哈希方法?；谏疃裙５幕€方法中，DPSH,DTSH和DSDH的學(xué)習(xí)效果顯著優(yōu)于DQN, DHN,NINH和CNNH。將所提出的ASDDH方法與DPSH、DTSH和DSDH進行比較可以看出，在不同的編碼長度下，ASDDH方法獲得的性能都有不同程度的提高。與DSDH相比，ASDDH方法進一步提高了3%到5%的性能。

在NUS-WIDE數(shù)據(jù)集上，ASDDH在MAP性能方面取得了顯著的提高。在所有編碼長度情況下，ASDDH得到的MAP分數(shù)始終高于0.834，尤其是當(dāng)編碼長度為48時達到0.874；而DPSH,DTSH和DSDH得到的最佳結(jié)果僅為0.824，遠遠低于本文方法。與DPSH和DSDH相比，當(dāng)編碼長度在12到48之間時，所提出的方法獲得了大約6%～8%的增強。與DTSH相比，ASDDH的性能也有5%左右的提高。

本文方法在NUS-WIDE數(shù)據(jù)集上的效果比CIFAR-10數(shù)據(jù)集提高得更多，主要原因是NUS-WIDE數(shù)據(jù)集內(nèi)包含的圖像類別比CIFAR-10數(shù)據(jù)集更多，而且每個圖像都包含多個標(biāo)簽。損失函數(shù)中的L3利用多標(biāo)簽二進制碼映射進行非對稱訓(xùn)練，使哈希碼具有多標(biāo)簽語義信息，進一步提高了實際應(yīng)用中的檢索性能。因此，本文提出的ASDDH方法在NUS-WIDE多標(biāo)簽數(shù)據(jù)集上更有效。

3.4 特征學(xué)習(xí)網(wǎng)絡(luò)

為了分析不同深度卷積神經(jīng)網(wǎng)絡(luò)對檢索結(jié)果的影響，本文將原來ASDDH模型中的AlexNet網(wǎng)絡(luò)改為預(yù)訓(xùn)練的VGG-16, ResNet50和ResNeXt50網(wǎng)絡(luò)進行訓(xùn)練。VGG-16網(wǎng)絡(luò)由13個卷積層和3個全連接層組成，比AlexNet網(wǎng)絡(luò)更為復(fù)雜且參數(shù)更多。殘差網(wǎng)絡(luò)ResNet50包含49個卷積層和1個全連接層，該網(wǎng)絡(luò)主要通過跳躍連接的方式，在加深網(wǎng)絡(luò)的情況下又解決梯度爆炸和梯度消失的問題。ResNeXt是ResNet和Inception的結(jié)合體，Res-NeXt結(jié)構(gòu)可以在不增加參數(shù)復(fù)雜度的前提下提高準(zhǔn)確率，同時還減少了超參數(shù)的數(shù)量。ResNeXt50和ResNet50類似，包含49個卷積層和1個全連接層。

為了得到最終的二進制代碼，本文將VGG-16,ResNet50和ResNeXt50網(wǎng)絡(luò)的最后一層用1個完全連通的哈希層(激活函數(shù)為tanh)所取代，并將這3種模型分別表示為ASDDH-V16, ASDDHRN50和ASDDH-RNX50。同時對基于深度哈希的DSDH進行了同樣的實驗并做對比，以保證結(jié)論的可靠性。DSDH對應(yīng)的3種模型分別表示為DSDHV16, DSDH--RN50和DSDH-RNX50。表2顯示了CIFAR-10數(shù)據(jù)集上每個模型的MAP值。

如表2所示，使用VGG-16, ResNet50和Res-NeXt50網(wǎng)絡(luò)代替AlexNet網(wǎng)絡(luò)使得最終的檢索準(zhǔn)確率有所上升，這種趨勢在基線DSDH和提出的ASDDH中都有體現(xiàn)。這說明不同的深度網(wǎng)絡(luò)對模型的性能有一定的影響。并且隨著網(wǎng)絡(luò)復(fù)雜度的增加，提取的特征也更加準(zhǔn)確，使得模型訓(xùn)練更加可靠。

表2 不同網(wǎng)絡(luò)的MAP

3.5 參數(shù)敏感性分析

圖2給出了針對ASDDH的超參數(shù)γ和τ在CIFAR-10數(shù)據(jù)集上的影響，二進制代碼長度分別為24 bit和48 bit。值得注意的是，當(dāng)對一個參數(shù)進行調(diào)優(yōu)時，其他參數(shù)是固定的。例如在[0.001, 0.01,0.1, 1, 10, 100]范圍內(nèi)調(diào)優(yōu)γ時，分別固定其他超參數(shù)。由圖2 (a)可以看出，在0.001<γ<10的范圍內(nèi)，ASDDH對γ并不敏感。同樣，由圖2 (b)給出的CIFAR-10數(shù)據(jù)集上不同τ的MAP結(jié)果可以知道，當(dāng)τ在范圍[0.0001，0.1]的時候，該方法總是取得令人滿意的效果。除此之外，本文提出的ASDDH方法不管是在24 bit還是48 bit哈希碼上，在γ=1,τ=0.001時取得最好的結(jié)果。

圖2 CIFAR-10數(shù)據(jù)集上的超參數(shù)影響

4 結(jié)論

本文提出了一種新的非對稱深度監(jiān)督離散哈希方法，即ASDDH，用于大規(guī)模的最近鄰搜索。首先利用深度網(wǎng)絡(luò)提取圖像特征，將特征表示和哈希函數(shù)學(xué)習(xí)集成到端到端框架中。然后引入成對損失和分類損失來保存每對輸出之間的語義結(jié)構(gòu)。在此基礎(chǔ)上，提出了一種非對稱哈希方法，既能捕獲離散二進制碼與多標(biāo)簽語義之間的相似性，又能在訓(xùn)練階段快速收斂。值得注意的是，非對稱哈希項尤其針對多標(biāo)簽數(shù)據(jù)庫更有效。在實際數(shù)據(jù)集上的實驗表明，ASDDH在實際應(yīng)用中可以達到最先進的性能。