基于語義相關性與拓撲關系的跨媒體檢索算法

代 剛，張 鴻

(1.武漢科技大學 計算機科學與技術學院，武漢 430065； 2.智能信息處理與實時工業系統湖北省重點實驗室(武漢科技大學)，武漢 430065)

0 引言

如今，非結構化的異構多媒體內容(如圖像、文本、音頻、視頻和3D模型)正在迅猛地涌入互聯網中，有效地分析這些多媒體數據是有必要的。雖然許多研究致力于多模態數據分析[1-3]，這些研究共同的策略是整合多種模態來提高學習性能。本文集中在與多模態數據分析相關的跨媒體檢索。跨媒體檢索指用某一種類型的媒體數據作為查詢去檢索其他媒體類型相關的媒體數據。例如，用戶能使用一個文本去檢索相關的圖片或視頻，或者使用一張圖片去檢索相關的文本描述或視頻。

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

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

為了去學習不同模態數據之間的內在相關性，本文提出了一種基于語義相關性與拓撲關系的跨媒體檢索算法。該算法的主要流程如下：

1)提出一個需要優化的目標函數，需要優化的是為每種媒體數據投影到一個共同空間所需要的投影矩陣。

2)通過一個迭代算法求解這個目標函數，得到每種媒體類型最優化的投影矩陣。

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

1 目標函數的構建與優化

1.1 目標函數的構建

定義完這些變量之后，開始構建需要優化的目標函數。為了迫使每種媒體數據的特征向量投影后都接近其標簽向量，本文定義了一個與文獻[11]一樣的標簽損失項如下：

(1)

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

為了構建這個多媒體語義相關超圖，本文定義了一個語義相似度矩陣如下：

(2)

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

(3)

為了使所有模態數據中相同語義類別數據投影后的數據點之間的歐氏距離最小，定義了一個多媒體數據的語義相關超圖正則化項如下：

(4)

進一步地，為了利用多媒體數據之間的近鄰關系，需要構建一個多媒體近鄰關系超圖。為了構建這個多媒體近鄰關系超圖，定義一個近鄰關系相似度矩陣如下：

(5)

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

(6)

為了使所有模態數據投影到共同空間后的數據點的k近鄰靠得近，定義了一個多媒體數據的近鄰關系超圖正則化項，如下：

(7)

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

(8)

(9)

其中:α、β、λ1和λ2是正的參數。該目標函數的第一項是標簽損失項，第二項是稀疏正則化項，第三項是多媒體數據的語義相關超圖正則化項，第四項是多媒體數據的近鄰關系超圖正則化項。

1.2 目標函數的優化

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

(10)

整理式(10)得：

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

(11)

(12)

其中ε是一個很小的正數。

算法1 基于語義相關性與拓撲關系的跨媒體檢索算法。

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

過程：

1)計算多媒體語義相關超圖中的拉普拉斯矩陣L；

3)重復

(13)

④t=t+1；

4)直到收斂

2 跨媒體檢索的相似度

(14)

(15)

3 實驗分析

3.1 數據集描述

在本實驗中，采用廣泛使用的跨媒體數據集，分別為Wikipedia數據集和XMedia數據集。分別介紹如下。

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

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

3.2 評估指標

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

(16)

其中:n表示測試集數據的個數，R表示檢索返回的相關項的個數，Rk表示在前k個返回結果中相關項的個數；并且如果排在第k位的返回結果是相關的，那么relk=1，否則relk=0。

3.3 參數設置

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

3.4 復雜度分析

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

3.5 實驗結果的分析

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

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

表1 各算法在Wikipedia和XMedia數據集中MAP值比較

圖1 Wikipedia數據集中的準確率-召回率曲線

圖2 XMedia數據集中的準確率-召回率曲線

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

4 結語

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

圖3 Wikipedia中不同類別樣例的平均準確率