在線哈希算法研究綜述

郭一村，陳華輝

（寧波大學(xué)信息科學(xué)與工程學(xué)院，浙江寧波 315000）

0 引言

隨著大數(shù)據(jù)時(shí)代網(wǎng)絡(luò)數(shù)據(jù)不斷增加，大規(guī)模的數(shù)據(jù)集對(duì)傳統(tǒng)的機(jī)器學(xué)習(xí)方式提出了重大挑戰(zhàn)。在各種檢索方式中，最近鄰（Nearest Neighbor，NN）檢索［1-3］在多種學(xué)習(xí)算法如基于標(biāo)簽的圖像注釋、語(yǔ)義分割、視頻分割、文本檢索［4］、內(nèi)容檢索［5］、物體識(shí)別等領(lǐng)域內(nèi)得到了廣泛應(yīng)用。最近鄰檢索的主要任務(wù)是對(duì)于給定一個(gè)查詢點(diǎn)檢索一個(gè)語(yǔ)義最近鄰數(shù)據(jù)集。傳統(tǒng)基于空間劃分的算法［6］雖然能得到比較精確的結(jié)果，但是在高維數(shù)據(jù)集上的學(xué)習(xí)和檢索的時(shí)間效率上都不高，因此對(duì)于高維度數(shù)據(jù)的最近鄰查詢往往使用乘積量化的策略，映射到低維子空間進(jìn)行近似最近鄰（Approximate NN，ANN）［7］檢索。學(xué)習(xí)型哈希［8-9］通過(guò)將數(shù)據(jù)表示為緊湊的二進(jìn)制碼形式，很方便地使用異或運(yùn)算快速計(jì)算數(shù)據(jù)間相似度，將原樣本空間相似的兩個(gè)數(shù)據(jù)點(diǎn)映射到海明空間里接近的兩個(gè)點(diǎn)。學(xué)習(xí)型哈希不僅能大大減少數(shù)據(jù)的存儲(chǔ)空間和運(yùn)算開銷，還能降低數(shù)據(jù)維度，從而顯著提高大數(shù)據(jù)學(xué)習(xí)系統(tǒng)的效率。

在線學(xué)習(xí)型哈希算法的關(guān)系如圖1 所示。本文首先介紹了學(xué)習(xí)型哈希算法的原理；然后介紹了在線哈希的難點(diǎn)以及在線哈希學(xué)習(xí)所采取的不同方式，隨后討論在線哈希的各種算法的發(fā)展?fàn)顩r并總結(jié)，對(duì)在線哈希未來(lái)發(fā)展方向進(jìn)行了展望。

圖1 在線學(xué)習(xí)型哈希算法關(guān)系圖Fig.1 Relation chart of online learning to hash algorithms

1 學(xué)習(xí)型哈希

學(xué)習(xí)型哈希由數(shù)據(jù)、哈希函數(shù)、目標(biāo)方程三個(gè)基本要素構(gòu)成。海明距離用來(lái)衡量哈希值之間的關(guān)聯(lián)程度，在海明空間內(nèi)反映數(shù)據(jù)的相似性，因此哈希學(xué)習(xí)的過(guò)程就是建立高維度空間到較低維度海明空間的映射關(guān)系，并設(shè)計(jì)合理的目標(biāo)方程量化損失減少兩個(gè)空間分布的差異。也就是說(shuō)相似的數(shù)據(jù)在海明空間內(nèi)的距離足夠接近，在最近鄰檢索數(shù)據(jù)時(shí)盡可能地找到相似數(shù)據(jù)；與之對(duì)應(yīng)的，不相似的數(shù)據(jù)在海明空間內(nèi)的距離足夠疏遠(yuǎn)，不同類別數(shù)據(jù)更容易被區(qū)分開。

假設(shè)輸入數(shù)據(jù)為n個(gè)d維的向量X∈Rd×n，而學(xué)習(xí)型哈希模型的目標(biāo)是要生成對(duì)應(yīng)數(shù)量的二進(jìn)制哈希碼y={y1，y2，…，yk}，位數(shù)為k。每一位哈希碼都由一個(gè)哈希函數(shù)進(jìn)行映射，得到一位哈希碼，依次就可以計(jì)算出一個(gè)數(shù)據(jù)樣本x∈Rd的所有哈希碼：

樣本數(shù)據(jù)被哈希函數(shù)映射為一批哈希碼的過(guò)程就是向量經(jīng)過(guò)一組線性運(yùn)算后再進(jìn)行二值化：

哈希模型可以大致分為數(shù)據(jù)獨(dú)立和數(shù)據(jù)依賴技術(shù)。數(shù)據(jù)獨(dú)立的技術(shù)往往設(shè)置若干個(gè)固定的哈希函數(shù)對(duì)數(shù)據(jù)進(jìn)行映射。在早期位置敏感哈希（Locality Sensitive Hashing，LSH）算法［10］應(yīng)用中，每一個(gè)哈希值當(dāng)作是一個(gè)容器：哈希桶（Hash Bin）。哈希桶被用來(lái)構(gòu)建哈希表，查詢操作相當(dāng)于列表搜索。原始樣本數(shù)據(jù)經(jīng)過(guò)哈希函數(shù)運(yùn)算得到一個(gè)哈希值，這個(gè)哈希值對(duì)應(yīng)與之相似的樣本。數(shù)據(jù)之間的相似度并不取決于數(shù)據(jù)本身，如余弦相似度［11］，除此之外沒(méi)有其他更多的信息。這種數(shù)據(jù)獨(dú)立的方式導(dǎo)致隨著學(xué)習(xí)的數(shù)據(jù)增加，會(huì)有越來(lái)越多的數(shù)據(jù)哈希值產(chǎn)生碰撞，那些相似的數(shù)據(jù)共享同一個(gè)哈希桶，增加了檢索所消耗的時(shí)間。為緩解碰撞則需要增大哈希碼的長(zhǎng)度，或者使用多個(gè)哈希桶，然而這又添加額外的存儲(chǔ)，并且學(xué)習(xí)到的模型只適合特定的數(shù)據(jù)分布，泛化性比較弱。但是在大規(guī)模數(shù)據(jù)集上應(yīng)用時(shí)，學(xué)習(xí)過(guò)程的計(jì)算成本至關(guān)重要，這種速度緩慢的將大批量數(shù)據(jù)集中學(xué)習(xí)的方式很難適應(yīng)隨著數(shù)據(jù)增長(zhǎng)而變化的數(shù)據(jù)集以更新哈希學(xué)習(xí)模型。

為了克服這些問(wèn)題，近年來(lái)的研究重點(diǎn)開始轉(zhuǎn)向數(shù)據(jù)依賴的哈希技術(shù)。數(shù)據(jù)依賴型哈希通過(guò)分析數(shù)據(jù)結(jié)構(gòu)特征及分布信息自動(dòng)學(xué)習(xí)哈希函數(shù)，通常分為無(wú)監(jiān)督方法和有監(jiān)督方法以及半監(jiān)督方法。無(wú)監(jiān)督哈希方法［12-14］根據(jù)數(shù)據(jù)原始分布學(xué)習(xí)哈希函數(shù)，無(wú)須任何監(jiān)督信息。與之相比，有監(jiān)督哈希方法因引入了監(jiān)督信息顯著地提高了檢索相似度而越來(lái)越被受到關(guān)注。有監(jiān)督的學(xué)習(xí)型哈希方法利用數(shù)據(jù)標(biāo)簽來(lái)獲得語(yǔ)義相似度對(duì)生成的哈希碼進(jìn)行有效監(jiān)督［15-17］。查詢時(shí)按照海明空間距離反映的相似性進(jìn)行排序，選取一定數(shù)量的相似樣本。雖然在整個(gè)數(shù)據(jù)集中進(jìn)行檢索成本偏高，但是二進(jìn)制碼的距離計(jì)算十分簡(jiǎn)便，并且保持了更多原始空間上的相似性。另外如半監(jiān)督哈希［18］方式使用有標(biāo)簽和無(wú)標(biāo)簽的數(shù)據(jù)學(xué)習(xí)哈希函數(shù)，解決標(biāo)簽獲取困難的問(wèn)題，同時(shí)避免出現(xiàn)模型過(guò)擬合。隨著深度學(xué)習(xí)快速發(fā)展，且深度學(xué)習(xí)模型往往具備強(qiáng)大的表征能力，于是近年來(lái)一些研究將深度學(xué)習(xí)與哈希學(xué)習(xí)兩者結(jié)合強(qiáng)化模型對(duì)數(shù)據(jù)復(fù)雜特征的表示［19］。得益于這些監(jiān)督或半監(jiān)督的方法，模型能夠在多媒體數(shù)據(jù)上學(xué)習(xí)到共同的哈希函數(shù)，可以跨模態(tài)對(duì)數(shù)據(jù)進(jìn)行檢索［20-21］。

2 在線學(xué)習(xí)型哈希

在線哈希學(xué)習(xí)是一種特殊的學(xué)習(xí)型哈希方式，關(guān)鍵在于訓(xùn)練前后對(duì)數(shù)據(jù)的依賴性。離線的哈希學(xué)習(xí)假設(shè)所有數(shù)據(jù)都是已知的，基于全局優(yōu)化的目標(biāo)，數(shù)據(jù)被重復(fù)挑選用來(lái)糾正學(xué)習(xí)初期所產(chǎn)生的偏差。這就帶來(lái)了在線哈希學(xué)習(xí)中最主要的矛盾：即隨著模型更新帶來(lái)的“遺忘”問(wèn)題，因此在線哈希學(xué)習(xí)的目的是尋找一種變化與保持的平衡策略。

2.1 在線哈希方式

盡管已有的學(xué)習(xí)型哈希算法已有很好的性能，但是面對(duì)大量流數(shù)據(jù)時(shí)，仍然存在很多缺陷：1）當(dāng)數(shù)據(jù)集發(fā)生變化或擴(kuò)展時(shí)，為適應(yīng)新的數(shù)據(jù)分布，必須將全部數(shù)據(jù)納入計(jì)算以重新學(xué)習(xí)模型所有相關(guān)參數(shù)，這顯然是十分低效的。在實(shí)際的應(yīng)用中，數(shù)據(jù)往往以數(shù)據(jù)流的方式輸入，而模型很難作出頻繁的響應(yīng)。2）對(duì)于許多大規(guī)模的數(shù)據(jù)集，數(shù)據(jù)以分布式的形式存儲(chǔ)在磁盤中。每次訓(xùn)練新數(shù)據(jù)時(shí)，需要將所有先前數(shù)據(jù)調(diào)入內(nèi)存處理，不僅對(duì)于現(xiàn)有的內(nèi)存容量是無(wú)法接受的，同時(shí)也給中央處理器的調(diào)度增加了很大壓力。3）訓(xùn)練后的數(shù)據(jù)仍然長(zhǎng)期保存以應(yīng)對(duì)多次訓(xùn)練，耗費(fèi)大量存儲(chǔ)空間。

針對(duì)以上問(wèn)題，在線學(xué)習(xí)型哈希進(jìn)行了相關(guān)研究，即哈希模型需要滿足幾個(gè)重要的條件：1）在訓(xùn)練原有數(shù)據(jù)的基礎(chǔ)上，能夠在數(shù)據(jù)流中學(xué)習(xí)哈希函數(shù)并且不依賴先前存儲(chǔ)的數(shù)據(jù)；2）學(xué)習(xí)到的哈希函數(shù)產(chǎn)生的哈希碼分布仍然符合相似性分布，使相似（不相似）數(shù)據(jù)的哈希碼保持一致的相似（不相似）性，這和傳統(tǒng)的哈希學(xué)習(xí)方式要求一致；3）學(xué)習(xí)速度加快，以響應(yīng)現(xiàn)實(shí)中較頻繁的最近鄰檢索。

在線學(xué)習(xí)型哈希仍然遵循學(xué)習(xí)型哈希的基本原則，但許多傳統(tǒng)的學(xué)習(xí)方式并不適合引入在線學(xué)習(xí)環(huán)境?，F(xiàn)有的在線哈希算法采用了多種在線學(xué)習(xí)方式，可以從不同角度對(duì)在線哈希方式進(jìn)行區(qū)分。

2.1.1 單次學(xué)習(xí)與多次學(xué)習(xí)

單次學(xué)習(xí)可大幅降低學(xué)習(xí)成本，數(shù)據(jù)只被用來(lái)訓(xùn)練一次，所以不必長(zhǎng)期存儲(chǔ)使得模型可以應(yīng)對(duì)更廣闊的數(shù)據(jù)。大部分現(xiàn)有方法如主被動(dòng)算法、聚類算法等都適用單次學(xué)習(xí)。一種折中的方法是保留少部分?jǐn)?shù)據(jù)作為樣本庫(kù)多次學(xué)習(xí)，緩解模型更新的偏差。

2.1.2 監(jiān)督和無(wú)監(jiān)督

和離線哈希學(xué)習(xí)類似，在線哈希學(xué)習(xí)也可被分為無(wú)監(jiān)督在線哈希和監(jiān)督在線哈希。無(wú)監(jiān)督哈希學(xué)習(xí)分析樣本數(shù)據(jù)之間的關(guān)系，分析相似程度，如降維提取特征值和使用自組織映射網(wǎng)絡(luò)；監(jiān)督學(xué)習(xí)的方式往往利用標(biāo)簽信息帶來(lái)更高的檢索精度，解決語(yǔ)義鴻溝問(wèn)題。每一個(gè)樣本數(shù)據(jù)都有對(duì)應(yīng)的標(biāo)簽提供這個(gè)數(shù)據(jù)的類別信息，由此可以計(jì)算出數(shù)據(jù)的語(yǔ)義相似度，比如較早的基于主-被動(dòng)算法，和后來(lái)的基于適應(yīng)性哈希函數(shù)?；蛘呖梢圆扇∈噶苛炕姆绞?，將標(biāo)簽直接生成碼本向量，直接對(duì)哈希碼進(jìn)行直接監(jiān)督。而碼本向量需要針對(duì)不同位數(shù)的哈希碼做相應(yīng)的轉(zhuǎn)換，因此要去除碼本向量之間的相關(guān)性以及減少降維運(yùn)算時(shí)產(chǎn)生的誤差來(lái)保證監(jiān)督的可靠性。

2.1.3 數(shù)據(jù)點(diǎn)、數(shù)據(jù)對(duì)和數(shù)據(jù)塊

在線哈希在模型訓(xùn)練時(shí)可以按照三種不同的數(shù)據(jù)劃分層次：數(shù)據(jù)點(diǎn)、數(shù)據(jù)對(duì)和數(shù)據(jù)塊（或數(shù)據(jù)列表）進(jìn)行參數(shù)更新。數(shù)據(jù)點(diǎn)的形式不需要進(jìn)行相似度的量化，當(dāng)一個(gè)數(shù)據(jù)點(diǎn)樣本輸入，模型可以通過(guò)標(biāo)簽生成目標(biāo)哈希碼進(jìn)行直接監(jiān)督，實(shí)際上相當(dāng)于聚類或分類問(wèn)題。哈希碼作為高維空間向量對(duì)數(shù)據(jù)類別進(jìn)行劃分（如圖2 所示），局限于標(biāo)簽所指示的類別數(shù)量，不適合類別復(fù)雜且多樣的數(shù)據(jù)。數(shù)據(jù)對(duì)和數(shù)據(jù)塊的區(qū)別在于以一對(duì)一還是一對(duì)多的方式保持相似性。數(shù)據(jù)塊在輸入模型時(shí)需要計(jì)算相似矩陣來(lái)指示數(shù)據(jù)間的相似關(guān)系，然而在數(shù)據(jù)變化較大時(shí)很難計(jì)算全局的均值做歸一化處理，給模型造成頻繁計(jì)算問(wèn)題。

圖2 二進(jìn)制哈希碼作為分類向量Fig.2 Binary hash code used as classification vector

2.2 在線哈希算法

本節(jié)將回顧在近年來(lái)關(guān)于在線哈希學(xué)習(xí)方面表現(xiàn)出檢索效率較高的各種算法，并比較它們的不同。

2.2.1 基于主-被動(dòng)算法

受到主-被動(dòng)算法［22］的啟發(fā)，Huang等［23］首次提出了哈希函數(shù)在線學(xué)習(xí)方式，將主-被動(dòng)算法適用于每對(duì)新樣本數(shù)據(jù)的哈希函數(shù)。在第t批次數(shù)據(jù)中，給出新的一對(duì)數(shù)據(jù)和它們的相似性標(biāo)簽sij∈{-1，+1}，模型相應(yīng)地更新哈希函數(shù)，使其能夠正確計(jì)算新數(shù)據(jù)的哈希碼，同時(shí)與舊的哈希函數(shù)足夠接近。于是目標(biāo)方程用來(lái)約束參數(shù)的變化，同時(shí)用一個(gè)非負(fù)變量ξ松弛化約束：

單純使用主-被動(dòng)算法面臨兩個(gè)明顯的問(wèn)題：1）算法每次以數(shù)據(jù)對(duì)的形式進(jìn)行優(yōu)化，使得模型頻繁更新限制了優(yōu)化效率；2）如果到來(lái)的數(shù)據(jù)越來(lái)越多變，則此算法可能會(huì)面臨收斂困難的問(wèn)題。

針對(duì)第二個(gè)問(wèn)題可以采用多模型的優(yōu)化方式［24］，分別對(duì)兩種情況下的模型選擇采取不同策略。為了控制模型參數(shù)更新頻率，引入了閾值來(lái)量化損失，如果超過(guò)這個(gè)閾值，則認(rèn)為哈希碼得到了相應(yīng)的匹配，模型參數(shù)不變；反之則要更新參數(shù)。在兩個(gè)數(shù)據(jù)樣本相似的情況下，海明距離大于閾值α，不相似時(shí)海明距離小于閾值βr，產(chǎn)生大于0的損失R(Ht，st)：

文獻(xiàn)［25］提出根據(jù)當(dāng)前數(shù)據(jù)分布采用動(dòng)態(tài)的損失閾值，使優(yōu)化目標(biāo)松弛為一個(gè)置信區(qū)間，同時(shí)約束損失函數(shù)變化，增強(qiáng)模型的穩(wěn)定性。

Weng 等［26］在哈希函數(shù)的框架基礎(chǔ)上又增加了一個(gè)映射函數(shù)。或者說(shuō)將模型分為了兩部分，首先由哈希函數(shù)迭代量化（Iterative Quantization，ITQ）［12］映射為哈希碼，再經(jīng)過(guò)映射函數(shù)進(jìn)行調(diào)整生成一個(gè)新的哈希碼，來(lái)適應(yīng)持續(xù)到來(lái)的新數(shù)據(jù)：

為了獲得更好的監(jiān)督學(xué)習(xí)效果，使用獨(dú)熱（One-Hot）編碼向量的標(biāo)簽yi，類似的投影生成理想的哈希碼用作監(jiān)督：

單獨(dú)地更新每個(gè)映射矩陣中的向量pk，按位與理想哈希碼計(jì)算損失：

映射函數(shù)旨在優(yōu)化二進(jìn)制哈希函數(shù)，糾正固定哈希函數(shù)帶來(lái)的偏差，使哈希碼適應(yīng)新的數(shù)據(jù)分布；同時(shí)基于主成分分析（Principal Component Analysis，PCA）降維的哈希函數(shù)本身帶來(lái)的誤差并不能消除，限制了優(yōu)化上限。

2.2.2 基于矩陣分解技術(shù)

Leng 等［27］提出了一個(gè)在流數(shù)據(jù)中學(xué)習(xí)哈希函數(shù)的思想：用一個(gè)尺寸更小的數(shù)據(jù)集模塊，保存數(shù)據(jù)主要特征，之后在線學(xué)習(xí)哈希函數(shù)，計(jì)算哈希函數(shù)的過(guò)程就會(huì)有一個(gè)比較低的計(jì)算復(fù)雜度和存儲(chǔ)空間。

以往的實(shí)驗(yàn)結(jié)果表明，哈希碼長(zhǎng)度越長(zhǎng)，對(duì)原有數(shù)據(jù)相似性擬合度越好。加入平衡約束和不相關(guān)約束能在有限的長(zhǎng)度內(nèi)提高哈希碼的表達(dá)能力［28］：每一位哈希碼應(yīng)當(dāng)有50%的概率為+1 或-1；不同的位之間相互獨(dú)立，即1，2，…，n）。

在線概要哈希將上述約束松弛為最大化哈希碼的方差，即最大化協(xié)方差矩陣的跡，防止模型優(yōu)化變成非確定性多項(xiàng)式（Non-Deterministic Polynomial，NP）困難問(wèn)題。主要任務(wù)為求解方程得到最優(yōu)解W，即解(X-μ)協(xié)方差矩陣的前r個(gè)最大的特征值對(duì)應(yīng)的特征向量。然而直接使用最優(yōu)化的矩陣W作為哈希投影將會(huì)帶來(lái)不平衡的問(wèn)題，因此需要在訓(xùn)練之前使數(shù)據(jù)零均值化。

使用基于矩陣分解的數(shù)據(jù)塊進(jìn)行哈希學(xué)習(xí)和PCA 降維過(guò)程類似，實(shí)質(zhì)上是在線求解特征值或奇異值的過(guò)程。另外在線概要哈希針對(duì)流數(shù)據(jù)提出一個(gè)零均值塊算法彌補(bǔ)了數(shù)據(jù)的均值變化問(wèn)題。

文獻(xiàn)［29］通過(guò)采用子采樣隨機(jī)的阿達(dá)瑪變換的方式加快了矩陣分解的進(jìn)程，加快了學(xué)習(xí)速度。其后Weng等［30］加入了樣本相似度作為監(jiān)督信息，提高了檢索精確度。

2.2.3 基于無(wú)監(jiān)督聚類

文獻(xiàn)［31］利用自適應(yīng)的K均值聚類進(jìn)行無(wú)監(jiān)督哈希函數(shù)學(xué)習(xí)。但是K均值聚類哈希算法本質(zhì)上是基于批次的學(xué)習(xí)模型，具有很高的時(shí)間和存儲(chǔ)的復(fù)雜性。Chen 等［32］將傳統(tǒng)的自組織映射（Self-Organizing Mapping，SOM）網(wǎng)絡(luò)擴(kuò)展到高維空間，形成網(wǎng)格狀超立方體。聚類中心作為超立方體的頂點(diǎn)，頂點(diǎn)位置信息引導(dǎo)生成二進(jìn)制哈希碼（如圖3所示）。

圖3 三維空間的自組織映射網(wǎng)絡(luò)Fig.3 SOM network of 3D space

使用PCA 將數(shù)據(jù)降維到與超立方體同一維度，減小量化誤差的同時(shí)保持了海明空間與歐幾里得空間之間的親和度。但另外一方面，SOM一次只能針對(duì)特定維度的數(shù)據(jù)進(jìn)行學(xué)習(xí)，若數(shù)據(jù)樣本維度過(guò)高，映射到超立方體神經(jīng)網(wǎng)絡(luò)的編碼則可能會(huì)超過(guò)哈希碼表示的限度，于是模型不得不再次降維而產(chǎn)生二次近似誤差。

2.2.4 基于相似性監(jiān)督

當(dāng)一對(duì)新數(shù)據(jù)點(diǎn){xi，xj}到來(lái)時(shí)，利用相似性信息sij進(jìn)行隨機(jī)梯度下降找到適應(yīng)數(shù)據(jù)變化的哈希函數(shù)。損失函數(shù)用來(lái)保持海明親和度：

通過(guò)隨機(jī)梯度下降，每次迭代選擇一對(duì)數(shù)據(jù)點(diǎn)進(jìn)行在線更新：

只針對(duì)新數(shù)據(jù)設(shè)計(jì)適應(yīng)性的哈希函數(shù)忽略了在線連續(xù)學(xué)習(xí)的情況下，不僅隨著舊數(shù)據(jù)樣本越來(lái)越多模型承受著“退化”的風(fēng)險(xiǎn)，同時(shí)相似數(shù)據(jù)與不相似數(shù)據(jù)的不均衡也往往會(huì)導(dǎo)致相似數(shù)據(jù)之間并沒(méi)有得到充分學(xué)習(xí)而降低了檢索時(shí)的精確度。Lin 等［34］主要關(guān)注了在流數(shù)據(jù)的哈希模型學(xué)習(xí)中新數(shù)據(jù)與現(xiàn)有數(shù)據(jù)對(duì)應(yīng)的相似性分布，以及在線學(xué)習(xí)中數(shù)據(jù)的不平衡問(wèn)題（相似數(shù)據(jù)與不相似數(shù)據(jù)的數(shù)量不均等），采用了一種新穎的平衡相似性，使得在線學(xué)習(xí)中使用離散優(yōu)化成為可能。

在線學(xué)習(xí)環(huán)境中，學(xué)習(xí)數(shù)據(jù)不斷增加，將舊數(shù)據(jù)重新讀取學(xué)習(xí)是十分困難的，這也違背了在線哈希學(xué)習(xí)的框架。為解決模型在舊數(shù)據(jù)上的偏離問(wèn)題，首先需要對(duì)新舊數(shù)據(jù)樣本分開來(lái)討論，生成的哈希碼也被劃為兩部分然后在新舊數(shù)據(jù)之間根據(jù)相似度標(biāo)簽進(jìn)行監(jiān)督學(xué)習(xí)：

如圖4 所示，新數(shù)據(jù)在數(shù)據(jù)集中的相似數(shù)據(jù)遠(yuǎn)少于不相似的。事實(shí)上模型訓(xùn)練的目的是利用相似數(shù)據(jù)能夠得到較緊密的哈希碼，因?yàn)樵跈z索時(shí)所需要的是相似數(shù)據(jù)樣本而非不相似的，學(xué)習(xí)時(shí)間被大量地消耗在了不相似數(shù)據(jù)的學(xué)習(xí)上而致使學(xué)習(xí)效率降低。最直接的做法就是調(diào)整兩式的超參數(shù)使之均衡，然而這在實(shí)驗(yàn)上模型很難被優(yōu)化，且隨著數(shù)據(jù)流的增加超參數(shù)也要實(shí)時(shí)調(diào)整。具有平衡相似度的在線離散哈希提出了平衡相似度的概念，用兩個(gè)特征值來(lái)平衡相似與不相似時(shí)的相似度：

添加平衡相似度后得到能夠平衡學(xué)習(xí)兩種數(shù)據(jù)分布的目標(biāo)方程：

第一，以馬克思主義辯證唯物主義和歷史唯物主義為指導(dǎo)，引導(dǎo)大學(xué)生樹立科學(xué)的世界觀，從而積極地改造自己的主觀世界；大學(xué)生的教育本身就是責(zé)任教育與未來(lái)教育，因此深入國(guó)情和國(guó)際環(huán)境的愛國(guó)主義教育，增強(qiáng)青年的民族自豪感、自信心，提高青年一代的責(zé)任承擔(dān)意識(shí)。

平衡相似度同時(shí)調(diào)節(jié)了訓(xùn)練過(guò)程中相似和不相似數(shù)據(jù)與新舊數(shù)據(jù)兩類失衡的問(wèn)題，防止模型出現(xiàn)退化和遺忘。因此在學(xué)習(xí)過(guò)程中不得不保留一部分舊數(shù)據(jù)，消耗部分存儲(chǔ)空間維持模型性能，在數(shù)據(jù)集較大時(shí)，舊數(shù)據(jù)如何表示復(fù)雜的原始分布仍然存在挑戰(zhàn)。

圖4 新數(shù)據(jù)和舊數(shù)據(jù)構(gòu)成非對(duì)稱圖Fig.4 Asymmetric graph constructed by new data and old data

2.2.5 基于互信息度量

Cakir 等［35］致力于分離不相似的數(shù)據(jù)在海明空間上的分布，提出了一種新的衡量哈希碼質(zhì)量的方式，對(duì)比一直使用的基于海明距離對(duì)數(shù)據(jù)相似性的度量，互信息基于二進(jìn)制碼的分布量化哈希函數(shù)的質(zhì)量顯得更加直觀有效。在被哈希函數(shù)映射進(jìn)哈希桶的模型中，考察哈希碼編碼分布往往會(huì)各不相同：如圖5 所示，統(tǒng)計(jì)某個(gè)樣本相似數(shù)據(jù)的哈希碼分布情況可以得到一個(gè)近似的高斯分布，其他不相似的哈希碼又會(huì)得到另一個(gè)不同的分布。兩種分布重疊的區(qū)域可能使得相似和不相似數(shù)據(jù)的哈希碼產(chǎn)生重復(fù)而導(dǎo)致誤差。在理想情況下，這兩種分布盡量疏離，相似的數(shù)據(jù)緊密分布，那么重疊區(qū)域的面積則較小，兩種數(shù)據(jù)的編碼的重合程度也會(huì)較小，海明距離就自然較遠(yuǎn)。基于上述對(duì)于哈希碼分布的認(rèn)識(shí)，便得出互信息的概念，基于互信息的取值反映模型的性能。

圖5 哈希碼分布指示映射函數(shù)質(zhì)量Fig.5 Hash code distribution indicating quality of mapping function

顯然互信息I(D；C)取值越大時(shí)，分布的不確定性就越低，體現(xiàn)出哈希函數(shù)Φ能夠?qū)煞N分布映射得更加離散，減少了哈希碼重疊的可能性。在理想的狀態(tài)下，互信息足夠大，哈希碼幾乎不發(fā)生重疊為獨(dú)立分布。利用互信息可以對(duì)模型質(zhì)量進(jìn)行整體的檢驗(yàn)：

由于在實(shí)際情況下不可能加載所有樣本，因此在流數(shù)據(jù)中采樣一部分作為樣本庫(kù)：

QR可以當(dāng)作是一個(gè)觸發(fā)器，新數(shù)據(jù)和樣本庫(kù)中的數(shù)據(jù)同時(shí)被哈希函數(shù)映射，如果函數(shù)保證了原有的互信息，哈希函數(shù)才可以更新，這樣就控制了不同數(shù)據(jù)間的映射分布在添加新數(shù)據(jù)后也是離散的，維持了模型性能。另一方面，樣本庫(kù)中的數(shù)據(jù)也不能無(wú)限增長(zhǎng)，隨著學(xué)習(xí)到的哈希碼越來(lái)越多，樣本庫(kù)表示性的下降也是無(wú)法避免的。再者算法使用了哈希桶的方式，雖然在進(jìn)行互信息的優(yōu)化后不相似的樣本哈希碼得到較好分離，卻又加重相似樣本的哈希碼的重疊程度，增大了檢索時(shí)的復(fù)雜度。

2.2.6 基于碼本監(jiān)督

在先前的各種學(xué)習(xí)方式中，數(shù)據(jù)都是以批次或數(shù)據(jù)對(duì)的形式進(jìn)行學(xué)習(xí)，而無(wú)法立刻學(xué)習(xí)單個(gè)數(shù)據(jù)；又考慮到新到來(lái)的數(shù)據(jù)可能會(huì)具有原來(lái)未包含的標(biāo)簽，而產(chǎn)生錯(cuò)誤分類。于是受通信領(lǐng)域的信號(hào)傳輸模型的啟發(fā)，Cakir等［36］引入了錯(cuò)誤糾正編碼（Error Correcting Output Codes，ECOC）來(lái)代表每一個(gè)新的標(biāo)簽。

哈希函數(shù)可以被用來(lái)訓(xùn)練為空間里的分類器，生成的二進(jìn)制哈希碼則是指示分類的超平面向量，由錯(cuò)誤糾正編碼來(lái)表示。碼本（Codebook）C是由1 和-1 兩種元素組成的矩陣，其中每一列向量稱為碼字（Codeword）分別代表了一個(gè)虛擬類別，同時(shí)正交的行向量就代表了類別所處的虛擬區(qū)域。假設(shè)新標(biāo)簽的數(shù)量是未知的，當(dāng)帶有新標(biāo)簽的數(shù)據(jù)到來(lái)時(shí)，將會(huì)在碼本中為其分配一個(gè)新的錯(cuò)誤糾正編碼來(lái)進(jìn)行監(jiān)督學(xué)習(xí)，而不需要對(duì)標(biāo)簽數(shù)據(jù)的任何先驗(yàn)信息。另一方面，帶有舊標(biāo)簽的數(shù)據(jù)則依據(jù)先前已分配的錯(cuò)誤糾正編碼來(lái)學(xué)習(xí)，那么所有具有相同標(biāo)簽的數(shù)據(jù)則會(huì)由相同的錯(cuò)誤糾正編碼緊湊地聚集在同一個(gè)類別里而擁有近似的哈希碼。

上述隨機(jī)梯度下降的在線監(jiān)督哈希雖然為哈希學(xué)習(xí)提供了監(jiān)督信息，但未明確監(jiān)督的質(zhì)量。在構(gòu)造錯(cuò)誤糾正編碼的碼本時(shí)用隨機(jī)的方式使編碼向量離散，這并不能完全保證消除其相關(guān)性。Lin等［37］提出編碼矩陣應(yīng)當(dāng)滿足以下要求：最大化每行之間的海明距離，從而具有較強(qiáng)的糾錯(cuò)能力；最大化每行之間的海明距離，確保每個(gè)分類器之間保持顯著的差異性。

阿達(dá)瑪矩陣滿足以上要求。阿達(dá)瑪矩陣是一個(gè)n階正交矩陣，行向量和列向量都各自正交，其元素為+1 或-1。高階的阿達(dá)瑪矩陣可由低階矩陣推導(dǎo)生成。當(dāng)帶有新標(biāo)簽的數(shù)據(jù)樣本輸入時(shí)，將會(huì)從阿達(dá)瑪矩陣中隨機(jī)且非重復(fù)選擇列向量構(gòu)造用來(lái)虛擬的表示這個(gè)標(biāo)簽。若標(biāo)簽已存在，則給出已分配給相同標(biāo)簽樣本的虛擬標(biāo)簽。最終把這些向量進(jìn)行聚合以構(gòu)成編碼矩陣（如圖6所示）。

圖6 阿達(dá)瑪矩陣作為碼本Fig.6 Hadamard matrix used as codebook

值得注意的是，基于阿達(dá)瑪矩陣的錯(cuò)誤糾正編碼的碼本可以離線生成而且采用哈希桶的位置敏感哈希也同樣是數(shù)據(jù)獨(dú)立的方法，在查找時(shí)可以用近似線性的復(fù)雜度進(jìn)行查找，同時(shí)也緩解了在線學(xué)習(xí)時(shí)所帶來(lái)的不穩(wěn)定性。在此之后，文獻(xiàn)［38］采用了核的方式映射原始數(shù)據(jù)，并進(jìn)一步地在多標(biāo)簽數(shù)據(jù)輸入的情況下進(jìn)行了研究。

2.2.7 小結(jié)

綜上所述，無(wú)監(jiān)督的在線哈希方式如基于無(wú)監(jiān)督聚類和早期基于矩陣分解的方式無(wú)法利用標(biāo)簽信息而檢索能力較差，目前大部分在線哈希算法如基于主-被動(dòng)算法、相似性監(jiān)督、碼本監(jiān)督、互信息度量等都采用監(jiān)督學(xué)習(xí)的方式提高檢索精確度，總結(jié)如表1所列?；谥?被動(dòng)算法的方式限制了更新模型時(shí)對(duì)舊數(shù)據(jù)可能出現(xiàn)的偏差，但模型不能學(xué)習(xí)到參數(shù)更新的方向。系統(tǒng)不能分辨哪些特征是前所未有的哪些是已經(jīng)存在的，在保留原有映射函數(shù)的同時(shí)針對(duì)性地優(yōu)化部分映射，及損失函數(shù)中對(duì)參數(shù)的約束往往使得模型難以優(yōu)化?；谙嗨菩员O(jiān)督的方法同時(shí)優(yōu)化相似數(shù)據(jù)和不相似數(shù)據(jù)之間的距離損失，然而在數(shù)據(jù)流中無(wú)法保證各類數(shù)據(jù)是獨(dú)立同分布的，尤其是相似的數(shù)據(jù)獲取困難。要解決這種不平衡問(wèn)題則必須耗費(fèi)一些存儲(chǔ)空間來(lái)存儲(chǔ)舊數(shù)據(jù)，例如平衡相似度在線哈希?；バ畔⒐Ｒ餐瑯用媾R此類問(wèn)題，尤其是一些網(wǎng)絡(luò)通信數(shù)據(jù)，會(huì)定期刪除一些歷史流量，在處理時(shí)效性較短的數(shù)據(jù)時(shí)面臨挑戰(zhàn)；基于碼本監(jiān)督的算法和互信息在線哈希把哈希碼學(xué)習(xí)轉(zhuǎn)化為分類問(wèn)題，通過(guò)優(yōu)化分類能夠較好地保持相似哈希碼之間的緊密度，在明確固定類別的數(shù)據(jù)上表現(xiàn)較好。碼本監(jiān)督允許數(shù)據(jù)以單個(gè)數(shù)據(jù)點(diǎn)的更新方式進(jìn)行分類，更能適應(yīng)數(shù)據(jù)流環(huán)境下學(xué)習(xí)哈希碼來(lái)應(yīng)對(duì)實(shí)時(shí)檢索。難點(diǎn)在于固定長(zhǎng)度的碼本向量的編碼過(guò)程是離線的，如阿達(dá)瑪矩陣引導(dǎo)的在線哈希，在轉(zhuǎn)化為不同長(zhǎng)度的哈希碼時(shí)產(chǎn)生的誤差導(dǎo)致保證哈希碼之間離散度的問(wèn)題，并且如果標(biāo)簽類別改變則要重新生成碼本，導(dǎo)致額外的計(jì)算開銷。此外碼本數(shù)量也較為固定，不適合處理數(shù)據(jù)類別有較多增加或減少的在線學(xué)習(xí)任務(wù)，數(shù)據(jù)的可擴(kuò)展性較差；部分基于矩陣分解的在線哈希雖然采用了監(jiān)督學(xué)習(xí)但未考慮到求解過(guò)程中原有數(shù)據(jù)所內(nèi)含的語(yǔ)義信息，導(dǎo)致數(shù)據(jù)尺寸縮小的同時(shí)沒(méi)有學(xué)習(xí)到有效特征來(lái)擬合優(yōu)化目標(biāo)。

表1 在線哈希算法總結(jié)Tab.1 Summary of online hashing algorithms

3 未來(lái)發(fā)展方向

進(jìn)入到互聯(lián)網(wǎng)時(shí)代線上數(shù)據(jù)每時(shí)每刻呈爆炸式增長(zhǎng)，處理這些大規(guī)模流數(shù)據(jù)的任務(wù)顯得至關(guān)重要。目前哈希學(xué)習(xí)方式引入了不少在線算法，但具體到現(xiàn)實(shí)應(yīng)用仍然有一些相關(guān)問(wèn)題值得被探索：1）流數(shù)據(jù)的一大特點(diǎn)在于其產(chǎn)生的實(shí)時(shí)性，而數(shù)據(jù)個(gè)體本身可能是高維且復(fù)雜的，比如使用哈希碼處理圖片分類任務(wù)［39］，需要先對(duì)數(shù)據(jù)進(jìn)行預(yù)處理壓縮或提取特征，如提取尺度不變特征轉(zhuǎn)換（Scale-Invariant Feature Transform）特征［40-41］、梯度直方圖（Histogram of Gradient）特征使哈希碼獲取深層的語(yǔ)義信息。由于深度神經(jīng)網(wǎng)絡(luò)的龐大參數(shù)量給整個(gè)在線更新過(guò)程帶來(lái)很大計(jì)算壓力而無(wú)法完成端到端學(xué)習(xí)，即遇到數(shù)據(jù)流中非獨(dú)立同分布的特征變化學(xué)習(xí)能力可能會(huì)大打折扣。2）數(shù)據(jù)流的實(shí)時(shí)性也體現(xiàn)在即時(shí)的反饋結(jié)果，如電商平臺(tái)根據(jù)用戶的商品瀏覽信息提供有針對(duì)性的商品推薦，在改善用戶體驗(yàn)的同時(shí)也擴(kuò)大了平臺(tái)市場(chǎng)潛在的交易量。這就需要模型在用戶作出操作行為后快速計(jì)算保證結(jié)果的時(shí)效性。因此算法的復(fù)雜度不能太高且收斂速度不能太慢，而現(xiàn)有的在線哈希方式則較少關(guān)注這兩項(xiàng)指標(biāo)。3）最近一些方法逐漸開始關(guān)注模型更新后對(duì)舊數(shù)據(jù)的檢索能力，設(shè)置彌補(bǔ)措施防止模型在學(xué)習(xí)過(guò)程中傾向遺忘。但長(zhǎng)期存儲(chǔ)舊數(shù)據(jù)的成本較高，往往會(huì)刪除一些早期數(shù)據(jù)，因此模型也應(yīng)考慮學(xué)習(xí)過(guò)程中的時(shí)序性：每個(gè)時(shí)間步的更新優(yōu)化都會(huì)影響到后續(xù)時(shí)間步的先驗(yàn)概率。不僅如此，數(shù)據(jù)流有時(shí)會(huì)出現(xiàn)新類型的數(shù)據(jù)，這些數(shù)據(jù)是以往學(xué)習(xí)過(guò)程中沒(méi)有出現(xiàn)的，模型會(huì)面臨“概念演化”（Concept Evolution）的問(wèn)題。例如在金融大數(shù)據(jù)運(yùn)營(yíng)［42］中出現(xiàn)異常交易或非法交易信息系統(tǒng)能及時(shí)對(duì)這些結(jié)構(gòu)化的數(shù)據(jù)進(jìn)行識(shí)別，而非誤判為原有的合法信息，向系統(tǒng)發(fā)出警示信號(hào)防止資產(chǎn)流失，類似的也可用于其他的異常檢測(cè)。因此模型應(yīng)當(dāng)能夠?qū)W習(xí)到新數(shù)據(jù)的增量特征并且保持原有數(shù)據(jù)的深層次內(nèi)聯(lián)關(guān)系來(lái)提高在整個(gè)時(shí)間線前后的泛化能力。

就上述觀點(diǎn)而言，仍有許多新的技術(shù)和方向（如深度學(xué)習(xí)、強(qiáng)化學(xué)習(xí)）可以與在線哈希學(xué)習(xí)進(jìn)行結(jié)合來(lái)進(jìn)一步提高模型的時(shí)效性與泛化能力。

4 結(jié)語(yǔ)

本文總結(jié)了近年來(lái)表現(xiàn)較好的幾種在線哈希學(xué)習(xí)方法，這些方法通過(guò)權(quán)衡模型更新與保持有效檢索，使得在大規(guī)模數(shù)據(jù)集上進(jìn)行在線哈希學(xué)習(xí)成為可能，相較于原有的離線學(xué)習(xí)帶來(lái)了存儲(chǔ)空間更低、學(xué)習(xí)成本更小以及在新數(shù)據(jù)樣本上具有更好適應(yīng)性等優(yōu)勢(shì)。當(dāng)前大數(shù)據(jù)的迅猛發(fā)展，要求哈希模型能夠在數(shù)據(jù)流中快速學(xué)習(xí)以應(yīng)對(duì)檢索，因此在線學(xué)習(xí)型哈希在面對(duì)復(fù)雜且多變的未知數(shù)據(jù)，進(jìn)一步提高學(xué)習(xí)效率，增強(qiáng)模型的實(shí)時(shí)性和準(zhǔn)確性上有著非常廣闊的發(fā)展前景。