一種具有平衡標(biāo)簽預(yù)測能力的在線哈希算法

摘要：針對(duì)傳統(tǒng)離線哈希算法訓(xùn)練模型耗時(shí)、占用內(nèi)存大和不易更新模型的問題，以及現(xiàn)實(shí)圖像集的標(biāo)簽存在大量損失的現(xiàn)象，提出了一種能夠平衡標(biāo)簽預(yù)測的在線哈希算法（BLPOH）。BLPOH通過標(biāo)簽預(yù)測模塊生成預(yù)測標(biāo)簽，并融合殘缺的真實(shí)標(biāo)簽，能夠有效緩解因標(biāo)簽損失導(dǎo)致的模型性能下降。觀察到標(biāo)簽存在分布不平衡現(xiàn)象，提出標(biāo)簽類別相似性平衡算法并應(yīng)用于標(biāo)簽預(yù)測模塊，提升標(biāo)簽預(yù)測的準(zhǔn)確性。將舊數(shù)據(jù)的信息加入哈希函數(shù)的在線更新過程，提升模型對(duì)舊數(shù)據(jù)的兼容性。通過在兩個(gè)廣泛使用的數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，并和一些當(dāng)前先進(jìn)的算法進(jìn)行對(duì)比，結(jié)果證實(shí)了BLPOH的優(yōu)越性。

關(guān)鍵詞：在線哈希； 多標(biāo)簽； 標(biāo)簽預(yù)測； 圖像檢索

中圖分類號(hào)：TP391文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695（2022）10-045-3161-06

doi：10.19734/j.issn.1001-3695.2022.02.008

Online hash algorithm with balanced label prediction ability

He Shuo， Xie Liang

（School of Faculty of Science， Wuhan University of Technology， Wuhan 430070， China）

Abstract：Aiming at the problems that the traditional offline hashing algorithm is time-consuming to train the model， occupies a large amount of memory and is difficult to update the model， and there is a large loss of labels in real image sets， this paper proposed a balanced label prediction for online hashing algorithm（BLPOH）. BLPOH generated predicted labels through the label prediction module， and fused the incomplete real labels， which could effectively alleviate the performance degradation of the model caused by label loss. It observed that there was an imbalance in the distribution of labels， then proposed a label category similarity balance algorithm to apply to the label prediction module to improve the accuracy of label prediction. It added the information of old data to the online update process of the hash function to improve the compatibility of the model to the old data. By conducting experiments on two widely used datasets and comparing with some state-of-the-art algorithms， the results demonstrate the superiority of BLPOH.

Key words：online hashing; multi label; label prediction; image retrieval

0引言

哈希算法由于其具有高效的檢索能力和占用存儲(chǔ)低的特點(diǎn)，在圖像檢索領(lǐng)域一直備受關(guān)注。哈希算法把高維的圖像特征映射到一個(gè)低維的二值空間［1］，得到一連串緊湊的哈希碼，這串哈希碼保留了圖像間的相似性信息［2］。正是由于哈希碼的這些特性，使得圖像檢索任務(wù)可以在一個(gè)低維空間高效地進(jìn)行，而哈希碼的質(zhì)量也就成為影響圖像檢索性能的關(guān)鍵因素。

研究者們致力于學(xué)習(xí)一個(gè)優(yōu)秀的哈希函數(shù)，以得到高質(zhì)量的哈希碼。Gionis等人［3］提出局部敏感哈希算法（locality-sensitive hashing，LSH）。LSH是一種無監(jiān)督哈希算法，通過將原始數(shù)據(jù)隨機(jī)映射到不同的哈希桶中，然后經(jīng)過符號(hào)函數(shù)得到哈希碼。Weiss等人［4］提出譜哈希算法（spectral hashing，SH）。SH以圖像分割的思想解決圖像特征的編碼問題。Wang等人［5］提出基于半監(jiān)督學(xué)習(xí)的圖像哈希檢索算法（semi-supervised hashing，SSH）。Liu等人［6］提出圖哈希算法（hashing with graphs，AGH）。AGH有很多思想源于SH，不同的是AGH通過數(shù)據(jù)聚類中心和數(shù)據(jù)樣本點(diǎn)之間的近鄰圖近似樣本點(diǎn)之間的近鄰圖。Shen等人［7］提出基于有監(jiān)督的哈希算法（supervised discrete hashing，SDH）。SDH通過離散循環(huán)下降算法（cyclic coordinate descent，DCC）按位求解哈希碼，避免松弛化求解引起的次優(yōu)問題。然而，以上哈希算法都是通過離線學(xué)習(xí)［8］的方式一次性地從所有數(shù)據(jù)中學(xué)習(xí)哈希函數(shù)。面對(duì)越來越龐大的圖像數(shù)據(jù)集，這些離線哈希算法在學(xué)習(xí)過程中不僅占用大量的內(nèi)存空間，而且十分耗時(shí)。不僅如此，每當(dāng)新數(shù)據(jù)到來，離線哈希算法為了更新模型不得不重新進(jìn)行訓(xùn)練。面對(duì)這樣的應(yīng)用場景，在線哈希算法（online hashing）能夠很好地解決這些問題。在線哈希算法流式地讀取數(shù)據(jù)［9］，每次只從一個(gè)數(shù)據(jù)流中訓(xùn)練并更新模型，占用空間小、訓(xùn)練模型快、易于更新模型。近年來，研究者們提出了多種在線哈希算法，作為代表的在線哈希算法包括在線核哈希（online kernel hashing，OKH）［10］、在線監(jiān)督哈希（online supervised hashing，OSH）［11］、自適應(yīng)哈希（adaptive hashing，AdaptHash）［12］、在線草圖哈希（sketching hashing，SketchHash）［13］、具有共同信息的在線哈希（online ha-shing with mutual information，MIHASH）［14］、平衡相似性在線離散哈希（balanced similarity for online discrete hashing，BSODH）［15］、高效更新哈希碼的在線哈希（online hashing with efficient updating of binary codes，OHWEU）［16］、哈達(dá)瑪矩陣引導(dǎo)的在線哈希（Hadamard matrix online hashing，HMOH）［17］以及通過哈達(dá)瑪碼書學(xué)習(xí)的監(jiān)督在線哈希（online hashing via Hada-mard codebook，HCOH）［18］。

雖然這些在線哈希算法解決了離線哈希算法在巨大數(shù)據(jù)集上較難訓(xùn)練和更新模型的問題，但是它們?nèi)匀淮嬖谝恍┤秉c(diǎn)?，F(xiàn)實(shí)可用的圖像數(shù)據(jù)集總會(huì)由于圖像標(biāo)注［19］誤差造成圖像標(biāo)簽的缺失，然而當(dāng)前的在線哈希算法都默認(rèn)用到的數(shù)據(jù)集標(biāo)簽是完整的，這造成模型精度的下降。以BSODH為例，只考慮多標(biāo)簽數(shù)據(jù)的情況下，以兩幅圖像是否共享至少一個(gè)標(biāo)簽來判斷它們是否相似［20］，由于圖像標(biāo)簽并不完整，導(dǎo)致構(gòu)造的圖像標(biāo)簽相似性矩陣不準(zhǔn)確，最終造成模型精度的損失。

本文提出了一種能夠平衡標(biāo)簽預(yù)測的在線哈希算法（BLPOH）。通過引入在線哈希算法，避免離線哈希算法在巨大圖像數(shù)據(jù)集上訓(xùn)練耗時(shí)、占用內(nèi)存大和加入新數(shù)據(jù)需要重新訓(xùn)練的問題?？紤]到現(xiàn)實(shí)圖像標(biāo)簽存在缺失的問題，加入標(biāo)簽預(yù)測［21］模塊，通過圖像相似性和標(biāo)簽類別相似性預(yù)測近鄰圖像的標(biāo)簽，以對(duì)抗圖像標(biāo)簽缺失引起的性能損失。由于多數(shù)標(biāo)簽類別是不相似的，相似的只有少數(shù)，所以標(biāo)簽類別存在不平衡現(xiàn)象。因此，在標(biāo)簽預(yù)測模塊設(shè)計(jì)了一個(gè)標(biāo)簽類別相似性平衡算法，以提升標(biāo)簽預(yù)測的準(zhǔn)確性。此外，本文巧妙地根據(jù)漢明距離［22］的退化形式度量新舊數(shù)據(jù)之間哈希碼和標(biāo)簽的距離，使舊數(shù)據(jù)的信息參與哈希函數(shù)的在線更新。在MIR Flickr25k和NUS-WIDE兩個(gè)數(shù)據(jù)集上進(jìn)行廣泛的實(shí)驗(yàn)，并和一些當(dāng)前先進(jìn)的算法進(jìn)行對(duì)比以證明BLPOH的優(yōu)越性。

本文的主要貢獻(xiàn)如下：a）引入在線哈希算法，解決了離線哈希在巨大數(shù)據(jù)集訓(xùn)練和更新模型難的問題，并通過加入標(biāo)簽預(yù)測模塊，緩解了現(xiàn)實(shí)圖像數(shù)據(jù)標(biāo)簽缺失引起的性能下降問題；b）考慮到標(biāo)簽類別分布不平衡問題，在標(biāo)簽預(yù)測模塊設(shè)計(jì)標(biāo)簽類別相似性平衡算法，以提升預(yù)測的準(zhǔn)確性；c）通過漢明距離的退化形式建立新舊數(shù)據(jù)之間哈希碼和標(biāo)簽的相似性對(duì)等關(guān)系，讓舊數(shù)據(jù)的信息監(jiān)督哈希函數(shù)的在線更新，解決了在線哈希在舊數(shù)據(jù)上性能下降的問題，提升哈希函數(shù)對(duì)舊數(shù)據(jù)的兼容性。

1算法框架

圖1展示了BLPOH的整體框架。每當(dāng)數(shù)據(jù)流中有新數(shù)據(jù)到來時(shí)，通過找出圖像的K近似最近鄰計(jì)算圖像相似性矩陣，并把該矩陣應(yīng)用到標(biāo)簽預(yù)測當(dāng)中；然后，通過預(yù)測的標(biāo)簽計(jì)算圖像標(biāo)簽相似性矩陣，并利用該矩陣與舊數(shù)據(jù)建立關(guān)聯(lián)，使得舊數(shù)據(jù)的信息也參與到哈希函數(shù)的在線更新過程；最后，通過哈希函數(shù)計(jì)算出圖像數(shù)據(jù)的哈希碼。

1.1問題定義

給出一個(gè)多標(biāo)簽數(shù)據(jù)集X=［x1，…，xn］T∈Euclid Math TwoRApn×d表示圖像特征集，L=［l1，…，ln］T∈Euclid Math TwoNApn×u表示標(biāo)簽集，其中xi∈Euclid Math TwoRApd是第i個(gè)圖像實(shí)例，它對(duì)應(yīng)的標(biāo)簽是li∈Euclid Math TwoNApu，n是實(shí)例的個(gè)數(shù)，u是標(biāo)簽類別數(shù)量，d是圖像特征的維度。哈希函數(shù)把圖像特征數(shù)據(jù)映射為B=［b1，…，bn］T∈{－1，+1}n×k，其中bi是圖像實(shí)例xi對(duì)應(yīng)的二進(jìn)制哈希碼向量，k是哈希碼的位數(shù)。一般情況下，哈希函數(shù)都采用如BSODH的線性哈希映射，為了適合本文的數(shù)據(jù)處理方式，將哈希函數(shù)定義為

B=F（X）=sgn（XW）（1）

其中：W是投影矩陣;sgn（x）是符號(hào)函數(shù)，當(dāng)變量xgt;0時(shí)返回1，否則返回-1。

將在線哈希算法的數(shù)據(jù)流表示為Xts和Xte，其中Xts=［xts1，…，xtsnt］T∈Euclid Math TwoRApnt×d表示t時(shí)刻到來的新數(shù)據(jù)，Xte=［xte1，…，xtemt］T∈Euclid Math TwoRApmt×d表示t時(shí)刻已經(jīng)存在的舊數(shù)據(jù)以及它們?cè)趖時(shí)刻對(duì)應(yīng)的真實(shí)標(biāo)簽矩陣Lts=［lts1，…，ltsnt］T∈Euclid Math TwoNApnt×u和Lte=［lte1，…，ltemt］T∈Euclid Math TwoNApmt×u，nt表示t時(shí)刻數(shù)據(jù)流中的數(shù)據(jù)量，mt表示t時(shí)刻已經(jīng)存在的數(shù)據(jù)量。對(duì)應(yīng)地，把t時(shí)刻數(shù)據(jù)流中的新數(shù)據(jù)對(duì)應(yīng)的哈希碼矩陣表示為Bts=sgn（XtsWt）=［bts1，…，btsnt］T∈{－1，+1}nt×k，把t時(shí)刻已經(jīng)存在的舊數(shù)據(jù)對(duì)應(yīng)的哈希碼矩陣表示為Bte=sgn（XteWt）=［bte1，…，btemt］T∈{－1，+1}mt×k。在本文的在線哈希算法中，隨著新數(shù)據(jù)Xts的到來，以在線的方式更新t時(shí)刻的哈希碼投影矩陣Wt。把t時(shí)刻數(shù)據(jù)流對(duì)應(yīng)的預(yù)測標(biāo)簽矩陣表示為Yts=［yts1，…，ytsnt］T∈{－1，+1}nt×u，把已經(jīng)存在的舊數(shù)據(jù)對(duì)應(yīng)的預(yù)測標(biāo)簽矩陣表示為Yte=［yte1，…，ytemt］T∈{－1，+1}mt×u，-1表示沒有該標(biāo)簽，1表示擁有該標(biāo)簽。

表1介紹了本文主要的變量及其定義。

1.2模型框架

1.2.1標(biāo)簽預(yù)測及標(biāo)簽類別相似性平衡

正如前文所述，現(xiàn)實(shí)可用的圖像數(shù)據(jù)集總會(huì)由于標(biāo)注誤差導(dǎo)致數(shù)據(jù)集的標(biāo)簽存在缺失。考慮到這種情況，本文通過建立標(biāo)簽預(yù)測模塊來對(duì)抗標(biāo)簽缺失引起的模型精度下降問題。受文獻(xiàn)［21］啟發(fā)，在假設(shè)標(biāo)簽類別相似矩陣Qs已知的情況下，一個(gè)圖像實(shí)例的標(biāo)簽可以由該圖像實(shí)例的最近鄰近似地表示。類似地，一個(gè)圖像實(shí)例的標(biāo)簽也可以由該標(biāo)簽的最近鄰近似表示。建立如文獻(xiàn)［21］的標(biāo)簽預(yù)測正則化項(xiàng)，得到t時(shí)刻的關(guān)系表達(dá)式為

minYts‖Yts－StiYtsQts‖2Fs.t. Yts∈{－1，1}nt×u（2）

其中：Sti是t時(shí)刻通過圖像的K近似最近鄰計(jì)算得到的圖像實(shí)例間的相似性矩陣;‖·‖F(xiàn)表示Frobenius范數(shù)。

與文獻(xiàn)［21］不同的是，本文創(chuàng)新性地提出標(biāo)簽類別相似性平衡算法。標(biāo)簽類別相似性平衡算法基于標(biāo)簽類別分布不平衡現(xiàn)象，絕大多數(shù)標(biāo)簽對(duì)是不相似的，少數(shù)標(biāo)簽對(duì)是相似的。為了解決這個(gè)問題，本文將標(biāo)簽類別相似矩陣分為Qs1和Qs2兩部分，它們分別表示相似標(biāo)簽對(duì)和非相似標(biāo)簽對(duì)，對(duì)于Qs1，給它分配一個(gè)較小的權(quán)重，而給Qs2分配一個(gè)較大的權(quán)重，以此讓標(biāo)簽類別相似性向標(biāo)簽對(duì)不相似的方向偏移。對(duì)于沒有添加標(biāo)簽類別相似性平衡算法的模型，為了達(dá)到和添加該算法模型同等的精度，需要迭代更多的次數(shù)，導(dǎo)致在相同迭代次數(shù)下預(yù)測的標(biāo)簽準(zhǔn)確性和預(yù)測的收斂速度都較為低下。將標(biāo)簽類別相似性平衡算法的公式定義為

tij=ηsQtijQtijgt;0

ηdQtijQtijlt;0（3）

其中：ηs表示較小的權(quán)重;ηd表示較大的權(quán)重。

1.2.2映射關(guān)系及其損失函數(shù)的定義

此外，建立X到預(yù)測標(biāo)簽Y的線性映射關(guān)系，Y以XV表示，建立t時(shí)刻XtsVt和Yts的F范數(shù)損失：

minVt‖XtsVt－Yts‖2F（4）

哈希算法的目的是學(xué)習(xí)一個(gè)哈希函數(shù)，根據(jù)式（1），最小化線性哈希函數(shù)F和Xts對(duì)應(yīng)哈希碼Bts之間的誤差，建立公式：

minWt‖XtsWt－Bts‖2F（5）

1.2.3舊數(shù)據(jù)的信息參與哈希函數(shù)的在線更新

以漢明距離度量兩個(gè)維度相同的向量之間的距離，如果兩個(gè)數(shù)據(jù)越相似，則它們對(duì)應(yīng)的二進(jìn)制哈希碼之間的漢明距離越小，反之越大。在訓(xùn)練新數(shù)據(jù)和更新模型的同時(shí)，得到的新模型應(yīng)該同樣適用于舊數(shù)據(jù)。因此，從數(shù)據(jù)流中訓(xùn)練模型的同時(shí)，應(yīng)該把舊數(shù)據(jù)的信息考慮在內(nèi)。考慮到如果數(shù)據(jù)xi和xj是相似的，那么它們就有相似的標(biāo)簽矩陣，而且由哈希函數(shù)的特性可知，哈希碼保留了數(shù)據(jù)間的相似性關(guān)系，因此能夠通過哈希碼和標(biāo)簽數(shù)據(jù)建立新、舊數(shù)據(jù)之間的相似性對(duì)等關(guān)系?？紤]到，當(dāng)哈希碼以-1和1表示時(shí)，哈希碼bi和bj之間的漢明距離h可以表示為

h=1/2（k－〈bi，bj〉）（6）

其中：〈bi，bj〉表示bi和bj的內(nèi)積。

同樣，對(duì)于某個(gè)標(biāo)簽類別，以-1和1分別標(biāo)志數(shù)據(jù)沒有該標(biāo)簽和擁有該標(biāo)簽。最小化兩者間的F范數(shù)損失得

minBts，Bte‖BtsBteT-Stl‖2F

s.t. Bts∈{-1，1}nt×k，Bte∈{-1，1}mt×k（7）

其中：Stl是標(biāo)簽相似性矩陣。為了有效利用存在損失的真實(shí)標(biāo)簽信息，在計(jì)算標(biāo)簽相似性矩陣Stl時(shí)，將存留的真實(shí)標(biāo)簽信息附加到對(duì)應(yīng)的預(yù)測標(biāo)簽上，即將真實(shí)的標(biāo)簽矩陣中為1處的值加到對(duì)應(yīng)位置的預(yù)測標(biāo)簽矩陣中，充分利用已經(jīng)存在的真實(shí)標(biāo)簽信息，進(jìn)一步提升模型精度。因?yàn)橹恍枰脴?biāo)簽存在的信息，所以把Lts和Lte中值為-1的位置替換為0，為1的位置不變，分別用Ats和Ate表示。Stl的計(jì)算定義為

Stl=k（Yts+Ats）（Yte+Ate）Tu（8）

綜上，建立BLPOH的模型公式：

minQts，Bts，Bte，Wt，Vt，Yts‖Yts-StiYtsQts‖2F+α‖BtsBteT-Stl‖2F+

β‖XtsWt-Bts‖2F+Euclid Math OneSAp‖XtsVt-Yts‖2F+λ（‖Wt‖2F+‖Vt‖2F）

s.t. Bts∈{-1，1}nt×k，Bte∈{-1，1}mt×k，Yts∈{-1，1}nt×u（9）

1.3算法優(yōu)化

由于存在二進(jìn)制約束問題，所以采用迭代的方式進(jìn)行求解，在更新一個(gè)變量時(shí)固定其他變量，把其他變量當(dāng)做常量處理。

a）更新Wt。固定Qts、Bts、Bte、Vt和Yts，然后學(xué)習(xí)Wt。求解Wt的子問題是：

minWt β‖XtsWt－Bts‖2F+λ（‖Wt‖2F）（10）

因此，可以得到式（10）的閉式解：

Wt=βt（βtXtsTXts+λtI）-1XtsTBts（11）

其中：I是一個(gè)d×d的單位矩陣。

b）更新Vt。和更新Wt一樣，固定Qts、Bts、Bte、Wt和Yts，然后學(xué)習(xí)Vt。求解的子問題是

minVtEuclid Math OneSAp‖XtsVt－Yts‖2F+λ（‖Vt‖2F）（12）

因此，可以得到Vt的閉式解：

Vt=Euclid Math OneSApt（Euclid Math OneSAptXtsTXts+λtI）-1XtsTYts（13）

c）更新Bte。同樣固定其他所有變量，更新Bte。求解子問題是：

minBte α‖BtsBteT-Stl‖2Fs.t. Bte∈{-1，1}mt×k（14）

類似文獻(xiàn)［23］，式（14）可以退化為求解：

minBte‖BtsBteT-Stl‖1s.t. Bte∈{-1，1}mt×k（15）

求解式（15），得

Bte=sgn（StlTBts）∈{-1，1}mt×k（16）

d）更新Bts。固定其他所有變量，學(xué)習(xí)Bts。求解子問題為

minBts α‖BtsBteT-Stl‖2F+β‖XtsWt-Bts‖2F

s.t. Bts∈{-1，1}nt×k（17）

展開式（17）為

minBts α（‖BteBtsT‖2F+‖Stl‖2F-2tr（BtsBteTStlT））+

β（‖Bts‖2F+‖WtTXtsT‖2F-2tr（BtsWtTXtsT））

s.t. Bts∈{-1，1}nt×k（18）

式（18）可以簡化為

minBts α‖BteBtsT‖2F-2tr（αBtsBteTStlT+βBtsWtTXtsT）s.t. Bts∈{-1，1}nt×k

（19）

與BSODH類似，使P=αBteTStlT+βWtTXtsT，得到

minBts α‖BtsBteTtermⅠ‖2F-2tr（BtsPtermⅡ）

s.t. Bts∈{-1，1}nt×k（20）

其中：termⅠ=b～tsrb～terT+B～tsB～teT;termⅡ=b～tsrr+B～ts;b～tsr、b～ter、r分別表示Bts、Bte、P的第r行；B～ts、B～te、分別表示除了b～tsr、b～ter、r余下的行。

式（20）轉(zhuǎn)換為

minb～tsr α‖b～tsrb～terT+B～tsB～teT‖2F-2tr（b～tsrr）-2tr（B～ts）

s.t. b～tsr∈{-1，1}1×k（21）

求解式（21），得

b～tsr=sgn（Tr-αB～tsB～teTb～ter）∈{-1，1}1×k（22）

通過迭代求解每一行，得到最終的Bts。

e）更新Yts。固定其他所有變量，學(xué)習(xí)Yts。求解子問題為

minYts‖Yts－StiYtsQts‖2F+Euclid Math OneSAp‖XtsVt－Yts‖2F

s.t. Yts∈{－1，1}nt×u（23）

將式（23）轉(zhuǎn)換為普通的線性方程：

（MTM+Euclid Math OneSApI_V）Vec（Yts）=Vec（Euclid Math OneSApXtsVt）（24）

其中：M=I_V－L_S;L_S=QtsTSti;是Kronecker積;I_V是一個(gè)unt×unt的單位矩陣。

f）更新Qts。固定其他所有變量，更新Qts。過程與求解Yts類似，得

（I_L（（StiYts）T（StiYts）））Vec（Qts）=Vec（（StiYts）TYts）（25）

其中：I_L是一個(gè)uu×uu的單位矩陣。

算法1BLPOH的描述

輸入：數(shù)據(jù)集X;哈希碼位數(shù)k;數(shù)據(jù)流大小nt;參數(shù)α、β、Euclid Math OneSAp、λ、ηs/ηd和圖像的最近鄰個(gè)數(shù)K。

輸出：W和B，其中W=Wt，B=sgn（XW）。

a）對(duì)數(shù)據(jù)集X進(jìn)行歸一化處理，并根據(jù)nt從X中切分出Xts，隨機(jī)初始化Wt和Vt，初始化Qts為一個(gè)單位矩陣，并計(jì)算初始的Bts和Yts。

b）根據(jù)K計(jì)算Xts中數(shù)據(jù)間的相似性矩陣Sti。

c）根據(jù)式（11）和（13）分別更新Wt和Vt。

d）根據(jù)式（16）更新Bte。

e）根據(jù)式（22）迭代更新Bts。

f）根據(jù)式（24）（25）分別更新Yts和Qts。

g）設(shè)置Xte=［Xte;Xts］，Bte=［Bte;Bts］，Yte=［Yte;Yts］，并從X中切分出下一次的Xts。

h）重復(fù)步驟b）～g）。

2實(shí)驗(yàn)與分析

2.1數(shù)據(jù)集

本文在兩個(gè)公開可用的數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。為了更準(zhǔn)確地模擬圖像標(biāo)簽損失的情況，需要構(gòu)造確定標(biāo)簽存在損失的數(shù)據(jù)集。首先，從數(shù)據(jù)集中篩選出具有特定標(biāo)簽數(shù)量以上的數(shù)據(jù)，建立實(shí)驗(yàn)所需的圖像數(shù)據(jù)集和對(duì)應(yīng)的標(biāo)簽集。然后，本文使用卷積神經(jīng)網(wǎng)絡(luò)VGG-16對(duì)圖像數(shù)據(jù)進(jìn)行特征提取，提取的特征維度為4 096。同時(shí)，對(duì)圖像對(duì)應(yīng)的標(biāo)簽集進(jìn)行編碼，建立標(biāo)簽矩陣，為了模型計(jì)算相似度的需要，如果一個(gè)圖像包含該標(biāo)簽，就把該標(biāo)簽所在位置標(biāo)識(shí)為1，否則為-1。最后，如文獻(xiàn)［21］那樣考慮不完整標(biāo)簽率，隨機(jī)丟棄訓(xùn)練數(shù)據(jù){0%， 20%， 40%， 60%， 80%}的標(biāo)簽，分別建立這五種狀態(tài)下的子數(shù)據(jù)集。

MIR Flickr25k數(shù)據(jù)集包含25 000張圖像數(shù)據(jù)和24個(gè)標(biāo)簽類別，本文篩選具有3個(gè)及3個(gè)以上標(biāo)簽數(shù)量的數(shù)據(jù)，總共篩選出17 568張圖像。在提取完圖像特征和建立標(biāo)簽矩陣之后，再以{0%， 20%， 40%， 60%， 80%}的比率隨機(jī)丟棄標(biāo)簽，模擬數(shù)據(jù)標(biāo)簽丟失標(biāo)簽的情況。實(shí)驗(yàn)中，除了分析數(shù)據(jù)庫的數(shù)量對(duì)實(shí)驗(yàn)結(jié)果影響的實(shí)驗(yàn)，對(duì)于其他的實(shí)驗(yàn)，本文從挑選出的17 568個(gè)圖像數(shù)據(jù)中隨機(jī)選擇12 400個(gè)作為實(shí)驗(yàn)的數(shù)據(jù)集，其中10 000個(gè)作為數(shù)據(jù)庫用做訓(xùn)練，剩下的2 400個(gè)圖像數(shù)據(jù)用做查詢集。

NUS-WIDE數(shù)據(jù)集包含269 648張圖像數(shù)據(jù)和81個(gè)標(biāo)簽類別，本文選擇出現(xiàn)最多的21個(gè)類別作為標(biāo)簽。處理過程和MIR Flickr25k類似，總共篩選出57 073張圖像數(shù)據(jù)，并從中隨機(jī)選擇12 100個(gè)作為實(shí)驗(yàn)的數(shù)據(jù)集，其中10 000個(gè)作為數(shù)據(jù)庫用做訓(xùn)練，剩下的2 100個(gè)圖像數(shù)據(jù)用做查詢集。

2.2基準(zhǔn)方法與評(píng)估指標(biāo)

本文以一些前沿的在線哈希算法作為基準(zhǔn)方法，包括BSODH、MIHASH、OKH、AdaptHash、SketchHash、HMOH和OHWEU。實(shí)驗(yàn)時(shí)，BLPOH與對(duì)比算法使用的數(shù)據(jù)集和數(shù)據(jù)集的標(biāo)簽損失率等設(shè)定完全一致，對(duì)于每個(gè)對(duì)比算法的參數(shù)，專門設(shè)定使其得到最好的效果。實(shí)驗(yàn)設(shè)備的操作系統(tǒng)為Windows 10，CPU為R5-3600，內(nèi)存為32 GB。當(dāng)數(shù)據(jù)集是MIR Flickr25k時(shí)，實(shí)驗(yàn)設(shè)置參數(shù)α=β=0.8，Euclid Math OneSAp=0.9，λ=0.6，流數(shù)據(jù)量為200，最近鄰K=10，ηs=0.4，ηd=1。當(dāng)數(shù)據(jù)集是NUS-WIDE時(shí)，實(shí)驗(yàn)設(shè)置參數(shù)α=β=Euclid Math OneSAp=0.9，λ=0.1，流數(shù)據(jù)量為200，最近鄰K=12，ηs=0.2，ηd=1。本文使用平均精度均值（mean average precision，MAP）作為度量的標(biāo)準(zhǔn)來評(píng)估這些算法的性能。

2.3實(shí)驗(yàn)結(jié)果

2.3.1MAP對(duì)比

表2～4和圖2展示了BLPOH和對(duì)比算法在數(shù)據(jù)集為MIR Flickr25k和NUS-WIDE，并且標(biāo)簽損失率分別為{0， 20%， 40%， 60%， 80%}時(shí)不同哈希碼位數(shù)下的MAP結(jié)果對(duì)比和變化曲線。如表2所示，在數(shù)據(jù)集MIR Flickr25k的不同標(biāo)簽損失率下，BLPOH的MAP始終高于其他所有對(duì)比算法。其中，HMOH和OHWEU的整體效果和BLPOH較為接近，AdaptHash的整體效果相比最差。在NUS-WIDE數(shù)據(jù)集下，當(dāng)標(biāo)簽損失率為0的時(shí)候，BLPOH的MAP高于除HMOH外的其他對(duì)比算法，當(dāng)標(biāo)簽損失率繼續(xù)上升時(shí)，BLPOH的MAP超過包括HMOH在內(nèi)的所有對(duì)比算法，證明了BLPOH的優(yōu)越性能。從HMOH在數(shù)據(jù)集NUS-WIDE下的結(jié)果中可以看出，當(dāng)沒有標(biāo)簽損失時(shí)，HMOH的MAP高于BLPOH，當(dāng)標(biāo)簽損失率上升到20%及以后時(shí)，BLPOH的MAP超過了HMOH，證明了BLPOH對(duì)抗標(biāo)簽損失的有效性。在實(shí)際應(yīng)用中，標(biāo)簽的損失程度可能會(huì)非常嚴(yán)重，BLPOH更適用于實(shí)際情況。

圖2給出了BLPOH和對(duì)比算法在數(shù)據(jù)集MIR Flickr25k和NUS-WIDE不同哈希碼位數(shù)下的MAP隨標(biāo)簽損失率上升的變化圖。從圖中可以看出，在不同數(shù)據(jù)集和不同哈希碼位數(shù)的情況下，BLPOH的MAP下降更加平緩，且多數(shù)情況下總能保持更高的水平。

2.3.2關(guān)鍵參數(shù)靈敏度分析

本節(jié)分析標(biāo)簽類別相似性權(quán)重參數(shù)ηs和ηd對(duì)實(shí)驗(yàn)結(jié)果的影響。在實(shí)驗(yàn)中，設(shè)置ηd=1，并通過改變?chǔ)莝/ηd的大小來分析它們對(duì)實(shí)驗(yàn)結(jié)果的影響。從圖3（a）中可以看出，在數(shù)據(jù)集MIR Flickr25k上，當(dāng)ηs/ηd的值介于（0.3，0.5）時(shí)，MAP出現(xiàn)最大值，當(dāng)ηs/ηd在0.8以后MAP大幅下降，當(dāng)ηs/ηd=1時(shí)MAP的值最低，此時(shí)表示的是沒有使用標(biāo)簽類別相似性平衡算法的MAP，最終本文選取ηs=0.4，ηd=1作為實(shí)際參數(shù)值。如圖3（b）所示，在數(shù)據(jù)集NUS-WIDE上，ηs/ηd=0.2時(shí)MAP最高，當(dāng)ηs/ηd=1時(shí)MAP最低，最終選取ηs=0.2，ηd=1作為實(shí)際參數(shù)值。從標(biāo)簽類別相似性權(quán)重比值在兩種數(shù)據(jù)集上的表現(xiàn)可以看出，沒有使用標(biāo)簽類別相似性平衡的MAP總是低于使用標(biāo)簽類別相似性平衡的，這證明了標(biāo)簽類別相似性平衡對(duì)BLPOH的有效性。

2.3.3數(shù)據(jù)庫樣本數(shù)量對(duì)實(shí)驗(yàn)結(jié)果的影響

BLPOH是一種基于在線哈希的改進(jìn)算法，為了測試BLPOH作為在線哈希算法的檢索性能，本文分析了BLPOH的實(shí)驗(yàn)結(jié)果隨數(shù)據(jù)庫樣本增加的變化情況。設(shè)置MIR Flickr25k和NUS-WIDE查詢集的數(shù)量分別為2 400和2 100，剩下的用做訓(xùn)練。如圖4（a）所示，數(shù)據(jù)集為MIR Flickr25k，當(dāng)數(shù)據(jù)庫的樣本數(shù)量為2 000時(shí)，BLPOH的MAP較其他五種情況最差，當(dāng)樣本數(shù)量在4 000以后，MAP逐漸增加，當(dāng)樣本數(shù)量為10 000時(shí)，BLPOH的MAP基本趨于穩(wěn)定。如圖4（b）所示，BLPOH在NUS-WIDE數(shù)據(jù)集下的MAP從數(shù)據(jù)庫樣本數(shù)量為2 000開始逐漸上升，在樣本數(shù)量為8 000時(shí)趨于穩(wěn)定。

2.3.4標(biāo)簽類別相似性平衡算法對(duì)實(shí)驗(yàn)結(jié)果的影響

在算法優(yōu)化過程中，本文把優(yōu)化預(yù)測標(biāo)簽矩陣Yts和標(biāo)簽類別相似性矩陣Qts轉(zhuǎn)換為求解對(duì)應(yīng)的線性方程組，即式（23）（24）。在實(shí)際編程計(jì)算中，本文使用預(yù)條件共軛梯度法（preconditional conjugate gradient，PCG）對(duì)式（23）（24）進(jìn)行求解。

本節(jié)通過PCG的收斂位置來分析標(biāo)簽類別相似性平衡對(duì)BLPOH的影響。以NUS-WIDE數(shù)據(jù)集下的標(biāo)簽預(yù)測和求解標(biāo)簽類別相似性矩陣為例。如圖5（a）所示，在每次數(shù)據(jù)流到來并進(jìn)行標(biāo)簽預(yù)測時(shí)，使用標(biāo)簽類別相似性平衡算法總能比未使用標(biāo)簽類別相似性平衡算法收斂得更快，且每次收斂的位置變化較小，表現(xiàn)更穩(wěn)定。同樣地，如圖5（b）所示，在求解標(biāo)簽類別相似性矩陣時(shí)，使用標(biāo)簽類別相似性平衡算法相比未使用標(biāo)簽類別相似性平衡算法的表現(xiàn)也相對(duì)穩(wěn)定一些。

2.3.5圖像實(shí)例的檢索效果

為了展現(xiàn)BLPOH的實(shí)際檢索效果，將BLPOH和BSODH在數(shù)據(jù)集MIR Flickr25k中的圖像實(shí)例檢索效果進(jìn)行對(duì)比。實(shí)驗(yàn)時(shí)，從MIR Flickr25k數(shù)據(jù)集中選取一張圖像，根據(jù)相同條件下訓(xùn)練出的模型返回前五張最相似的圖像，結(jié)果如圖6所示，圖像下的文本為該圖像的標(biāo)簽。根據(jù)BLPOH訓(xùn)練的模型返回了五張人像，而根據(jù)BSODH訓(xùn)練的模型返回了四張人像和一張動(dòng)物的圖像，因此BLPOH的檢索效果明顯優(yōu)于BSODH。

3結(jié)束語

本文提出了改進(jìn)的在線哈希算法，流式地讀取數(shù)據(jù)，以在線的方式訓(xùn)練和更新模型，使得算法模型不受制于數(shù)據(jù)集的大小，并使模型契合當(dāng)前的數(shù)據(jù)信息，該模型具有良好的實(shí)時(shí)性。并且，讓舊數(shù)據(jù)的信息監(jiān)督哈希函數(shù)的在線更新，提升哈希函數(shù)對(duì)舊數(shù)據(jù)的兼容性。此外，考慮到現(xiàn)實(shí)圖像數(shù)據(jù)標(biāo)簽存在缺失的問題，加入標(biāo)簽預(yù)測模塊，并且新穎地提出使用標(biāo)簽類別相似性平衡算法指導(dǎo)標(biāo)簽的預(yù)測，使得預(yù)測的標(biāo)簽更加精確，也提升了圖像標(biāo)簽相似度的準(zhǔn)確性，進(jìn)一步提升模型精度。此外，本文的標(biāo)簽預(yù)測模塊不僅能讓模型很好地對(duì)抗標(biāo)簽缺失，并且在標(biāo)簽損失率不斷上升時(shí)，也能夠使模型的性能以較平緩的速度下降，在標(biāo)簽存在缺失的在線圖像檢索任務(wù)中具有良好的應(yīng)用前景。然而，本文的標(biāo)簽預(yù)測模型比較單一，模型的健壯性并不能令人非常滿意，所以在今后的工作中考慮加入集成學(xué)習(xí)思想，以提升模型的健壯性。

參考文獻(xiàn)：

[1]郭一村，陳華輝.在線哈希算法研究綜述［J］.計(jì)算機(jī)應(yīng)用，2021，41（4）：1106-1112.（Guo Yicun， Chen Huahui. Survey on online hashing algorithm［J］.Journal of Computer Applications，2021，41（4）：1106-1112.）

［2]Lin Guosheng， Shen Chunhua， Shi Qinfeng， et al. Fast supervised hashing with decision trees for high-dimensional data［C］//Proc of IEEE Conference on Computer Vision and Pattern Recognition.Pisca-taway，NJ：IEEE Press，2014：1971-1978.

［3]Gionis A， Indyk P， Motwani R. Similarity search in high dimensions via hashing［C］//Proc of the 25th Very Large Data Base Conference. San Francisco，CA：Morgan Kaufmann Publishers，1999：518-529.

［4]Weiss Y， Fergus R， Torralba A. Multidimensional spectral hashing［C］//Proc of the 12th European Conference on Computer Vision.Berlin：Springer，2012：340-353.

［5]Wang Jun， Kumar S， Chang S F. Semi-supervised hashing for large-scale search［J］.IEEE Trans on Pattern Analysis and Machine Intelligence，2012，34（12）：2393-2406.

［6]Liu Wei， Mu Cun， Kumar S， et al. Discrete graph hashing［C］//Proc of the 27th International Conference on Neural Information Processing Systems.Cambridge，MA：MIT Press，2014：3419-3427.

［7]Shen Fumin， Shen Chunhua， Liu Wei， et al. Supervised discrete hashing［C］//Proc of the 28th IEEE Conference on Computer Vision and Pattern Recognition.Piscataway，NJ：IEEE Press，2015：37-45.

［8]Bombara G， Belta C. Offline and online learning of signal temporal logic formulae using decision trees［J］.ACM Trans on Cyber-Physical Systems，2021，5（3）：1-23.

［9]Lu Xu， Zhu Lei， Cheng Zhiyong， et al. Flexible online multi-modal hashing for large-scale multimedia retrieval［C］//Proc of the 27th ACM International Conference on Multimedia.New York：ACM Press，2019：1129-1137.

［10]Huang Longkai， Yang Qiang， Zheng Weishi. Online hashing［C］//Proc of the 23rd International Joint Conference on Artificial Intelligence.Palo Alto，CA：AAAI Press，2013：1422-1428.

［11]Cakir F， Bargal S A， Sclaroff S. Online supervised hashing［J］.Computer Vision and Image Understanding，2017，156：162-173.

［12]Cakir F， Sclaroff S. Adaptive hashing for fast similarity search［C］//Proc of the 15th IEEE International Conference on Computer Vision.Piscataway，NJ：IEEE Press，2015：1044-1052.

［13]Leng Cong， Wu Jiaxiang， Cheng Jian， et al. Online sketching ha-shing［C］//Proc of IEEE Conference on Computer Vision and Pattern Recognition.Piscataway，NJ：IEEE Press，2015：2503-2511.

［14]Cakir F， He Kun， Bargal S A， et al. MIHash： online hashing with mutual information［C］//Proc of the 16th IEEE International Confe-rence on Computer Vision.Piscataway，NJ：IEEE Press，2017：437-445.

［15]Lin Mingbao， Ji Rongrong， Liu Hong， et al. Towards optimal discrete online hashing with balanced similarity［C］//Proc of the 33rd Association for the Advancement of Artificial Intelligence Conference on Artificial Intelligence.Palo Alto，CA：AAAI Press，2019：8722-8729.

［16]Weng Zhenyu， Zhu Yuesheng. Online hashing with efficient updating of binary codes［C］//Proc of the 34th Association for the Advancement of Artificial Intelligence Conference on Artificial Intelligence.Palo Alto，CA：AAAI Press，2020：12354-12361.

［17]Lin Mingbao， Ji Rongrong， Liu Hong， et al. Hadamard matrix guided online hashing［J］.International Journal of Computer Vision，2020，128（8）：2279-2306.

［18]Lin Mingbao， Ji Rongrong， Liu Hong， et al. Supervised online ha-shing via Hadamard codebook learning［C］//Proc of the 26th ACM International Conference on Multimedia.New York：ACM Press，2018：1635-1643.

［19]王琳，張素蘭，楊海峰.基于CNN和加權(quán)貝葉斯的最近鄰圖像標(biāo)注方法［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2021，31（10）：63-69.（Wang Lin， Zhang Sulan， Yang Haifeng. A nearest neighbor image annotation method based on CNN and weighted Bayesian［J］.Computer Technology and Development，2021，31（10）：63-69.）

［20]Jiang Qingyuan， Li Wujun. Deep cross-modal hashing［C］//Proc of the 30th IEEE Conference on Computer Vision and Pattern Recognition.Piscataway，NJ：IEEE Press，2017：3270-3278.

［21]Dong Haochen， Li Yufeng， Zhou Zhihua. Learning from semi-supervised weak-label data［C］//Proc of the 32nd Association for the Advancement of Artificial Intelligence Conference on Artificial Intelligence.Palo Alto，CA：AAAI Press，2018：2926-2933.

［22]Norouzi M， Punjani A， Fleet D J. Fast search in Hamming space with multi-index hashing［C］//Proc of IEEE Conference on Computer Vision and Pattern Recognition.Piscataway，NJ：IEEE Press，2012：3108-3115.

［23]Kang Wangcheng， Li Wujun， Zhou Zhihua. Column sampling based discrete supervised hashing［C］//Proc of the 30th Association for the Advancement of Artificial Intelligence Conference on Artificial Intelligence.Palo Alto，CA：AAAI Press，2016：1230-1236.

收稿日期：2022-02-25；

修回日期：2022-04-21

作者簡介：何碩（1997-），男，河南駐馬店人，碩士研究生，主要研究方向?yàn)閳D像哈希；謝良（1987-），男（通信作者），副教授，博士，主要研究方向?yàn)槎嗝襟w大數(shù)據(jù)檢索、語義分析與跨模態(tài)分析以及機(jī)器學(xué)習(xí)的應(yīng)用（whutxl@hotmail.com）.