基于語義相關(guān)性與拓?fù)潢P(guān)系的跨媒體檢索算法

代 剛，張 鴻

(1.武漢科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，武漢 430065； 2.智能信息處理與實(shí)時工業(yè)系統(tǒng)湖北省重點(diǎn)實(shí)驗(yàn)室(武漢科技大學(xué))，武漢 430065)

0 引言

如今，非結(jié)構(gòu)化的異構(gòu)多媒體內(nèi)容(如圖像、文本、音頻、視頻和3D模型)正在迅猛地涌入互聯(lián)網(wǎng)中，有效地分析這些多媒體數(shù)據(jù)是有必要的。雖然許多研究致力于多模態(tài)數(shù)據(jù)分析[1-3]，這些研究共同的策略是整合多種模態(tài)來提高學(xué)習(xí)性能。本文集中在與多模態(tài)數(shù)據(jù)分析相關(guān)的跨媒體檢索?？缑襟w檢索指用某一種類型的媒體數(shù)據(jù)作為查詢?nèi)z索其他媒體類型相關(guān)的媒體數(shù)據(jù)。例如，用戶能使用一個文本去檢索相關(guān)的圖片或視頻，或者使用一張圖片去檢索相關(guān)的文本描述或視頻。

跨媒體檢索的關(guān)鍵問題是如何去學(xué)習(xí)不同模態(tài)數(shù)據(jù)之間的內(nèi)在相關(guān)性[4]。已經(jīng)存在一些方法能解決跨媒體檢索問題，例如，典型相關(guān)分析(Canonical Correlation Analysis, CCA)[5-6]已被應(yīng)用于跨媒體檢索作為一種自然的解決方案，是去最大化兩組異構(gòu)數(shù)據(jù)之間的相關(guān)性?？缒B(tài)因子分析(Cross-modal Factor Analysis, CFA)[7]評估兩種不同媒體數(shù)據(jù)之間的關(guān)聯(lián)，在變換域中，CFA最小化成對數(shù)據(jù)之間的Frobenius范數(shù)。聯(lián)合圖正則化的異構(gòu)度量學(xué)習(xí)(Heterogeneous Metric Learning with Joint Graph Regularization, JGRHML)[8]學(xué)習(xí)異構(gòu)度量并將不同媒體的結(jié)構(gòu)整合為一個聯(lián)合圖正則化，進(jìn)而能夠測量不同媒體數(shù)據(jù)之間的內(nèi)容相似度。跨模態(tài)相關(guān)傳播(Cross Modality Correlation Propagation, CMCP)[9]同時處理不同模態(tài)的媒體數(shù)據(jù)之間的正相關(guān)和負(fù)相關(guān)，并且在異構(gòu)的模態(tài)之間傳播這種相關(guān)性。近鄰的異構(gòu)相似性度量(Heterogeneous Similarity measure with Nearest Neighbors, HSNN)[10]可以計(jì)算不同媒體類型的媒體對象之間的相似度，它通過計(jì)算兩個媒體對象屬于同一個語義類別的概率來獲得異構(gòu)相似度。

另外，共同的表示學(xué)習(xí)(Joint Representation Learning, JRL)[11]是一種用稀疏和半監(jiān)督正則化去學(xué)習(xí)跨媒體共同的表示的方法，它能夠在一個統(tǒng)一的優(yōu)化框架中共同挖掘相關(guān)信息和語義信息。統(tǒng)一補(bǔ)丁圖正則化的半監(jiān)督跨媒體特征學(xué)習(xí)( Semi-Supervised cross-media feature learning with Unified Patch Graph regularization, S2UPG)[12]利用一個聯(lián)合圖同時對所有媒體類型進(jìn)行建模，并充分利用跨媒體未標(biāo)記實(shí)例及其補(bǔ)丁。聯(lián)合特征選擇和子空間學(xué)習(xí)(Joint Feature Selection and Subspace Learning, JFSSL)[13]使用了一個多模態(tài)圖正則化項(xiàng)去保存模態(tài)之間和模態(tài)內(nèi)部的相似關(guān)系。文獻(xiàn)[14]為跨模態(tài)檢索研究了一個用于構(gòu)建語義相關(guān)性的語義模型。文獻(xiàn)[15]提出了一種直推式學(xué)習(xí)方法來挖掘不同模態(tài)的媒體對象之間的語義相關(guān)性，從而實(shí)現(xiàn)跨媒體檢索。文獻(xiàn)[16]提出一種支持海量跨媒體檢索的集成索引結(jié)構(gòu)，該方法首先通過對網(wǎng)頁的預(yù)處理,分析其中不同模態(tài)媒體對象之間的鏈接關(guān)系,生成交叉參照圖，然后通過用戶相關(guān)反饋進(jìn)行調(diào)節(jié)。文獻(xiàn)[17]提出的跨媒體檢索方法分析了不同模態(tài)的內(nèi)容特征之間在統(tǒng)計(jì)意義上的典型相關(guān)性，并通過子空間映射解決了特征向量的異構(gòu)性問題。

為了去學(xué)習(xí)不同模態(tài)數(shù)據(jù)之間的內(nèi)在相關(guān)性，本文提出了一種基于語義相關(guān)性與拓?fù)潢P(guān)系的跨媒體檢索算法。該算法的主要流程如下：

1)提出一個需要優(yōu)化的目標(biāo)函數(shù)，需要優(yōu)化的是為每種媒體數(shù)據(jù)投影到一個共同空間所需要的投影矩陣。

2)通過一個迭代算法求解這個目標(biāo)函數(shù)，得到每種媒體類型最優(yōu)化的投影矩陣。

3)通過得到的每種媒體類型的投影矩陣將各種媒體數(shù)據(jù)的特征向量投影到一個共同的空間中，然后在這個空間中計(jì)算投影后的向量之間的相似度，進(jìn)行實(shí)現(xiàn)跨媒體檢索。

1 目標(biāo)函數(shù)的構(gòu)建與優(yōu)化

1.1 目標(biāo)函數(shù)的構(gòu)建

定義完這些變量之后，開始構(gòu)建需要優(yōu)化的目標(biāo)函數(shù)。為了迫使每種媒體數(shù)據(jù)的特征向量投影后都接近其標(biāo)簽向量，本文定義了一個與文獻(xiàn)[11]一樣的標(biāo)簽損失項(xiàng)如下：

(1)

其中‖Z‖F(xiàn)表示矩陣Z的Frobenius范數(shù)。這個標(biāo)簽損失項(xiàng)僅僅考慮了每種媒體類型中有標(biāo)簽數(shù)據(jù)的語義信息，而沒有考慮不同媒體類型和相同媒體類型中的全部有標(biāo)簽數(shù)據(jù)之間的語義相關(guān)性，因而本文定義了一個多媒體語義相關(guān)超圖，就是將不同媒體類型和相同媒體類型中的全部有標(biāo)簽數(shù)據(jù)之間的語義相關(guān)性融合在一個超圖中。

為了構(gòu)建這個多媒體語義相關(guān)超圖，本文定義了一個語義相似度矩陣如下：

(2)

其中：i=1,2,…,s；j=1,2,…,s；s表示多媒體數(shù)據(jù)集中的媒體類型種數(shù)，p=1,2,…,H；q=1,2,…,H；而H=n(1)+n(2)+…+n(s)表示多媒體數(shù)據(jù)集中所有模態(tài)中有標(biāo)簽數(shù)據(jù)的總個數(shù)。由于前面的語義相似度矩陣的定義，整個語義相似度矩陣W定義如下：

(3)

為了使所有模態(tài)數(shù)據(jù)中相同語義類別數(shù)據(jù)投影后的數(shù)據(jù)點(diǎn)之間的歐氏距離最小，定義了一個多媒體數(shù)據(jù)的語義相關(guān)超圖正則化項(xiàng)如下：

(4)

進(jìn)一步地，為了利用多媒體數(shù)據(jù)之間的近鄰關(guān)系，需要構(gòu)建一個多媒體近鄰關(guān)系超圖。為了構(gòu)建這個多媒體近鄰關(guān)系超圖，定義一個近鄰關(guān)系相似度矩陣如下：

(5)

由于前面的近鄰關(guān)系相似度矩陣的定義，整個近鄰關(guān)系相似度矩陣U定義如下：

(6)

為了使所有模態(tài)數(shù)據(jù)投影到共同空間后的數(shù)據(jù)點(diǎn)的k近鄰靠得近，定義了一個多媒體數(shù)據(jù)的近鄰關(guān)系超圖正則化項(xiàng)，如下：

(7)

接著，為了使每個投影矩陣P(i)(i=1,2,…,s)稀疏，定義了一個稀疏正則化項(xiàng)，為所有投影矩陣的l2,1范數(shù)之和如下：

(8)

(9)

其中:α、β、λ1和λ2是正的參數(shù)。該目標(biāo)函數(shù)的第一項(xiàng)是標(biāo)簽損失項(xiàng)，第二項(xiàng)是稀疏正則化項(xiàng)，第三項(xiàng)是多媒體數(shù)據(jù)的語義相關(guān)超圖正則化項(xiàng)，第四項(xiàng)是多媒體數(shù)據(jù)的近鄰關(guān)系超圖正則化項(xiàng)。

1.2 目標(biāo)函數(shù)的優(yōu)化

用Φ表示式子(9)，Φ對P(i)求偏導(dǎo)并置為0，則有：

(10)

整理式(10)得：

P(i)=[αX(i)X(i)T+βR(i)+λ1X(i)LiiX(i)T+

(11)

(12)

其中ε是一個很小的正數(shù)。

算法1 基于語義相關(guān)性與拓?fù)潢P(guān)系的跨媒體檢索算法。

輸出：s種媒體類型的s個投影矩陣P(i)∈Rd(i)×c(i=1,2,…,s)。

過程：

1)計(jì)算多媒體語義相關(guān)超圖中的拉普拉斯矩陣L；

3)重復(fù)

(13)

④t=t+1；

4)直到收斂

2 跨媒體檢索的相似度

(14)

(15)

3 實(shí)驗(yàn)分析

3.1 數(shù)據(jù)集描述

在本實(shí)驗(yàn)中，采用廣泛使用的跨媒體數(shù)據(jù)集，分別為Wikipedia數(shù)據(jù)集和XMedia數(shù)據(jù)集。分別介紹如下。

Wikipedia[18]數(shù)據(jù)集是從2 700個“專題文章”中選出的，而這些專題文章是經(jīng)過維基百科編輯自2009年以來挑選和審閱得到的。Wikipedia數(shù)據(jù)集最后由2 866個圖像-文本對組成，且包含10個語義類別，這個數(shù)據(jù)集被隨機(jī)分成2 173個圖像-文本對的訓(xùn)練集和693個圖像-文本對的測試集。

在本文中使用的XMedia[11-12]數(shù)據(jù)集包括5 000個文本、5 000個圖像、1 140個視頻、1 000個音頻和500個3D模型。與在文獻(xiàn)[11-12]中使用的XMedia數(shù)據(jù)集唯一的不同是：文獻(xiàn)[11-12]中使用的視頻個數(shù)為500，而本文中使用的視頻個數(shù)是1 140，但這些視頻數(shù)據(jù)都屬于XMedia數(shù)據(jù)集，更多實(shí)驗(yàn)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)更有說服力。隨機(jī)劃分每種媒體類型的訓(xùn)練集與測試集的數(shù)據(jù)，且每種媒體類型的訓(xùn)練集與測試集的數(shù)據(jù)的個數(shù)之比均為4∶1。在Wikipedia和XMedia數(shù)據(jù)集中，每個圖像由4 096維的卷積神經(jīng)網(wǎng)絡(luò)(Convolutional Neural Network, CNN)特征向量表示，每個文本由3 000維的詞袋(Bag of Words, BOW)特征向量表示。另外，在XMedia數(shù)據(jù)集中，每個音頻由29維的MFCC(Mel-Frequency Cepstral Coefficients)特征向量表示，每個視頻由4 096維的CNN特征向量表示，每個三維模型由文獻(xiàn)[19]中描述的一組光場描述符級聯(lián)的4 700維的特征向量表示。

3.2 評估指標(biāo)

關(guān)于跨媒體檢索的評估指標(biāo)，采用與文獻(xiàn)[11-12]相同的評估方法，即使用準(zhǔn)確率-召回率( Precision-Recall, PR)曲線和平均準(zhǔn)確率( Mean Average Precision, MAP)來評估檢索的結(jié)果。MAP在圖像檢索和跨媒體檢索中被廣泛使用。一組查詢的MAP是每個查詢的平均精度(Average Precision, AP)的平均值。AP定義為：

(16)

其中:n表示測試集數(shù)據(jù)的個數(shù)，R表示檢索返回的相關(guān)項(xiàng)的個數(shù)，Rk表示在前k個返回結(jié)果中相關(guān)項(xiàng)的個數(shù)；并且如果排在第k位的返回結(jié)果是相關(guān)的，那么relk=1，否則relk=0。

3.3 參數(shù)設(shè)置

在式(9)中的參數(shù)α、β、λ1和λ2，和在式(5)、(15)中的參數(shù)k需要設(shè)置，對于XMedia數(shù)據(jù)集和Wikipedia數(shù)據(jù)集，實(shí)驗(yàn)檢索結(jié)果最好(即MAP值最大)時的參數(shù)均為α=10，β=1 000，λ1=0.01，λ2=0.001，k=100。

3.4 復(fù)雜度分析

分析本文算法的時間復(fù)雜度，從算法1中可看出，此算法主要的時間復(fù)雜度在于計(jì)算多媒體數(shù)據(jù)的近鄰關(guān)系超圖中的拉普拉斯矩陣Ct和式(13)中的矩陣的逆。這里將一維數(shù)據(jù)之間的乘法運(yùn)算作為一個基本運(yùn)算單元，經(jīng)分析可知，計(jì)算Ct需要執(zhí)行基本運(yùn)算單元O(c*E2)次，E表示多媒體數(shù)據(jù)集中所有模態(tài)中有標(biāo)簽數(shù)據(jù)和無標(biāo)簽數(shù)據(jù)的總個數(shù)，c表示多媒體數(shù)據(jù)集中語義類別的個數(shù)；計(jì)算式(13)中的矩陣的逆需要執(zhí)行基本運(yùn)算單元O(d3)次，d=max(d(1),d(2),…,d(s))，而其中d(i)表示第i種媒體數(shù)據(jù)的特征向量的維度，s表示多媒體數(shù)據(jù)集中的媒體類型種數(shù)。因此，算法的時間復(fù)雜度為max(O(c*E2),O(d3))。

3.5 實(shí)驗(yàn)結(jié)果的分析

在Wikipedia和XMedia兩個數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，且將本文提出的算法(SCTR)與4個主流的跨媒體檢索算法在跨媒體檢索任務(wù)中比較MAP值和PR曲線，這4個跨媒體檢索算法為JGRHML算法、CMCP算法、HSNN算法、JRL算法。在所有的檢索任務(wù)中A→B表示查詢例子的媒體類型為A，檢索結(jié)果的媒體類型為B。表1提供了所有實(shí)驗(yàn)方法在Wikipedia和XMedia數(shù)據(jù)集上跨媒體檢索任務(wù)中的MAP值，表1最右邊一欄是本文提出方法所獲得的MAP值。從表1中對應(yīng)Wikipedia數(shù)據(jù)集中結(jié)果可看出，本文提出的算法將其他4種算法獲得的最高的MAP的平均值從0.455 6提高到0.493 0，提高了3.74%。從表1中的對應(yīng)XMedia數(shù)據(jù)集中結(jié)果可看出，本文提出的算法將其他4種算法獲得的最高的MAP的平均值從0.426 2提高到0.517 3，提高了9.11%。因此從表1可看出本文提出的算法性能明顯優(yōu)于對比算法的性能。

實(shí)驗(yàn)中的所有方法在XMedia數(shù)據(jù)集中圖像與文本之間獲得的MAP值明顯高于在Wikipedia數(shù)據(jù)集中圖像與文本之間獲得的MAP值，可能由于Wikipedia數(shù)據(jù)集中有許多圖像是黑白圖像，圖像內(nèi)容模糊，導(dǎo)致提取到的圖像特征的表示能力較弱，一定程度上影響了檢索的準(zhǔn)確率。圖1展示了在Wikipedia數(shù)據(jù)集上實(shí)驗(yàn)中各種算法在圖像檢索文本、文本檢索圖像任務(wù)中的PR曲線，可以看出本文提出的SCTR算法與其他四種算法相比，在絕大多數(shù)召回率相同時，SCTR算法的準(zhǔn)確率要高于其他四種算法的準(zhǔn)確率。圖2展示了在XMedia數(shù)據(jù)集上實(shí)驗(yàn)中各種算法在圖像檢索文本、圖像檢索音頻、圖像檢索視頻、圖像檢索3D模型任務(wù)中的PR曲線，由于篇幅的限制，就沒有給出在XMedia數(shù)據(jù)集上其他檢索任務(wù)的PR曲線，但是其他檢索任務(wù)的PR曲線是與圖2的PR曲線類似。從圖2中可以看出在XMedia數(shù)據(jù)集上，本文提出的SCTR算法與其他4種算法相比，在所有召回率相同時，SCTR算法的準(zhǔn)確率要高于其他四種算法的準(zhǔn)確率。從圖1(a)與圖2(a)對比中可看出，在圖像檢索文本的任務(wù)中，當(dāng)召回率相同時，各種算法在XMedia數(shù)據(jù)集上的準(zhǔn)確率要高于在Wikipedia數(shù)據(jù)集上的準(zhǔn)確率，這與在表1中發(fā)現(xiàn)的關(guān)于圖像與文本的MAP值的規(guī)律一致。

表1 各算法在Wikipedia和XMedia數(shù)據(jù)集中MAP值比較

圖1 Wikipedia數(shù)據(jù)集中的準(zhǔn)確率-召回率曲線

圖2 XMedia數(shù)據(jù)集中的準(zhǔn)確率-召回率曲線

實(shí)驗(yàn)還給出了在Wikipedia數(shù)據(jù)集中不同類別樣例的MAP值。圖3展示了在Wikipedia數(shù)據(jù)集中所有實(shí)驗(yàn)的方法在各種類別上的MAP值和在各種類別中的MAP值的平均值，對于大多數(shù)類別來說，本文提出的方法的MAP值要高于其他四種方法的MAP值，圖3的(a)和(b)中的最右邊那欄表示實(shí)驗(yàn)中的方法在各種類別中的MAP值的平均值，明顯可看出本文提出的方法在各種類別中的MAP值的平均值要高于其他四種方法在各種類別中的MAP值的平均值。

4 結(jié)語

在Wikipedia和XMedia數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明本文提出的方法能有效提高跨媒體檢索的準(zhǔn)確率。本文算法利用多媒體數(shù)據(jù)語義相關(guān)超圖、近鄰關(guān)系超圖和語義信息來學(xué)習(xí)不同媒體類型的投影矩陣，以使不同媒體類型的數(shù)據(jù)投影到一個共同的空間而獲得共同的表示，進(jìn)而實(shí)現(xiàn)跨媒體檢索，但本文采用的線性投影不能捕獲具有高度非線性的復(fù)雜的跨模態(tài)相關(guān)性，所以如何獲取具有高度非線性的復(fù)雜的跨模態(tài)相關(guān)性還有待進(jìn)一步地探索。

圖3 Wikipedia中不同類別樣例的平均準(zhǔn)確率