基于跨模態(tài)檢索的效率優(yōu)化算法

徐明亮，余肖生

(三峽大學(xué) 計(jì)算機(jī)與信息學(xué)院，湖北 宜昌 443002)

0 引 言

隨著互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展變化，人們?cè)絹碓阶⒅赜谛畔⒌慕换?。人們?duì)于信息的需求已從最初的單一新聞上的文字發(fā)展到后來的圖片、視頻、聲音等。在各種網(wǎng)絡(luò)平臺(tái)上，這些不同類型的數(shù)據(jù)相互交織，互為補(bǔ)充，且存在一定的關(guān)聯(lián)。同一信息可能以不同類型的數(shù)據(jù)呈現(xiàn)。為了從不同類型的數(shù)據(jù)中同時(shí)找到表示同一信息的數(shù)據(jù)，跨模態(tài)信息檢索技術(shù)應(yīng)運(yùn)而生。

傳統(tǒng)的信息檢索主要針對(duì)同類型的數(shù)據(jù)提取特征向量，對(duì)其進(jìn)行相似度度量，根據(jù)相似度的排名來實(shí)現(xiàn)單模態(tài)的信息檢索。而跨模態(tài)信息檢索則是建立不同模態(tài)的隱式關(guān)系模型，讓不同模態(tài)能在同一空間下像單模態(tài)度量一樣進(jìn)行相似度度量，從而完成不同模態(tài)間的相互檢索。不同類型的模態(tài)數(shù)據(jù)，由于提取的特征向量的方式不同，導(dǎo)致在同一空間投影和匹配時(shí)工作量巨大。針對(duì)傳統(tǒng)的跨模態(tài)檢索算法在處理高維度計(jì)算量巨大的問題，文中提出了一種跨模態(tài)信息檢索的優(yōu)化方法。實(shí)驗(yàn)表明與原有算法相比，該方法在保證查準(zhǔn)率基本不變的情況下，可以大幅減少原有算法的計(jì)算量，提高檢索效率。

1 相關(guān)研究

跨模態(tài)信息檢索主要包括三個(gè)步驟：一是提取不同模態(tài)的特征信息來構(gòu)建特征子空間；二是采用某種算法判斷不同模態(tài)間特征子空間數(shù)據(jù)的關(guān)聯(lián)性；三是在特征子空間下進(jìn)行相似度度量，得出相應(yīng)結(jié)果。

1.1 模態(tài)信息特征表達(dá)

為了提取不同類型數(shù)據(jù)信息，需對(duì)原始數(shù)據(jù)進(jìn)行特征提取，取出原有數(shù)據(jù)特征向量。根據(jù)圖像的特征表示，圖像類型的特征可分為全局特征和局部特征兩大類。對(duì)全局特征而言，常用的提取結(jié)果主要有顏色直方圖和紋理灰度矩陣；對(duì)局部特征，常用的處理結(jié)果主要有尺度不變特征，方向梯度直方圖等。對(duì)文字類型的特征表達(dá)，常用的有詞袋模型(BOW)，通過計(jì)算詞在文章出現(xiàn)的頻率來比較不同文檔的相似度[1-2]。另有學(xué)者提出了一些基于詞袋模型的特征提取算法[3-4]，如潛在語義分析(LSA)、概率潛在語義分析(PLSA)以及隱含狄利克雷分布(LDA)。這些算法能在一定程度上將多媒體同構(gòu)信息的特征內(nèi)涵信息表示出來。

1.2 異構(gòu)特征關(guān)聯(lián)

要解決不同模態(tài)數(shù)據(jù)之間的相關(guān)性，關(guān)鍵是構(gòu)造一個(gè)公共的特征子空間，將不同模態(tài)的數(shù)據(jù)特征向量映射到該空間中，然后在該空間上對(duì)不同模態(tài)的數(shù)據(jù)進(jìn)行相似度度量。一般有兩種構(gòu)建公共子空間的模式，一種是基于相關(guān)性的特征子空間投影(CM)，該模式下遵循最大相關(guān)性原則，一般使用相關(guān)性算法找出相對(duì)應(yīng)的投影子空間矩陣，通過子空間投影矩陣來挖掘不同模態(tài)間的潛在關(guān)系；一種是基于高層語義的特征子空間學(xué)習(xí)(SM)，這種模式是通過機(jī)器學(xué)習(xí)的方式，使用分類算法在語義層次上對(duì)異構(gòu)數(shù)據(jù)構(gòu)建同型語義特征空間，再在該空間下進(jìn)行相似度處理。此模式通常需要事先安排好分類學(xué)習(xí)參數(shù)，若語義維度發(fā)生變化則需要重新調(diào)整參數(shù)和分類模型，難以進(jìn)行實(shí)際檢索應(yīng)用。因此，文中只探討第一種基于相關(guān)性子空間投影的模式的優(yōu)化算法。其中這兩種方式經(jīng)常使用的是典型相關(guān)性分析法(CCA)[5-7]。

為了探究不同變量組間的相關(guān)關(guān)系，傳統(tǒng)的典型性相關(guān)法的基本思路是將變量組間的每一組變量進(jìn)行線性組合，得到新的典型變量，找到該線性組合中具有最大相關(guān)性的一組作為典型變量進(jìn)行處理。如：有兩組變量x=[x1,x2,…,xm]，y=[y1,y2,…,yn]，將其中每一組變量進(jìn)行線性組合：

此外，為了解決原有數(shù)據(jù)非線性、非正交的問題，有學(xué)者提出了處理非線性的核化典型相關(guān)性分析(KCCA)[12]、混合概率相關(guān)性分析(mixPCCA)[13]、深度典型相關(guān)性分析(DCCA)[14]等方法。

1.3 空間信息相關(guān)性檢索

根據(jù)在同一特征子空間的投影，用投影之間的相似度來度量查詢信息與被檢索信息之間的相關(guān)性，根據(jù)相關(guān)度的大小來判斷與查詢信息最匹配的相關(guān)信息[15]。一般相似度采用的度量距離有歐氏距離、余弦距離、L1范式距離等。

2 基于降維的跨模態(tài)信息檢索模型

針對(duì)傳統(tǒng)算法在進(jìn)行高維度計(jì)算時(shí)計(jì)算量過大的問題，提出一種新的跨模態(tài)相似度學(xué)習(xí)方法，對(duì)傳統(tǒng)的基于特征子空間關(guān)聯(lián)算法進(jìn)行改進(jìn)優(yōu)化，以減少原有算法的計(jì)算量，提高算法效率。

2.1 模型構(gòu)建

假設(shè)數(shù)據(jù)存在兩種類型X和Z，其特征向量分別為X={x1,x2,…,xn}∈RDx×n和Z={z1,z2,…,zm}∈RDz×m，存在一個(gè)跨模態(tài)數(shù)據(jù)集O，使其中每個(gè)數(shù)據(jù)由這兩種模態(tài)組成。為簡(jiǎn)單起見，假設(shè)每個(gè)數(shù)據(jù)僅包括兩個(gè)單數(shù)據(jù)類型，即oi={xi,zi}[16]。

2.2 相關(guān)性分析改進(jìn)及投影子空間

傳統(tǒng)的特征子空間投影技術(shù)是指先將不同類型數(shù)據(jù)的特征空間正交化聯(lián)系在一起，然后挖掘異構(gòu)數(shù)據(jù)特征之間的內(nèi)在關(guān)系，找出能將異構(gòu)數(shù)據(jù)投影到同一特征子空間內(nèi)的方法。相關(guān)性子空間投影技術(shù)則是設(shè)法學(xué)習(xí)找到最優(yōu)子空間投影矩陣，從而實(shí)現(xiàn)將異構(gòu)數(shù)據(jù)特征轉(zhuǎn)換到同形特征空間，并保留最大關(guān)聯(lián)性。在這一子空間上可對(duì)投影數(shù)據(jù)進(jìn)行直接的相似度度量處理。這一過程是對(duì)原有特征直接進(jìn)行投影。而文中優(yōu)化算法則是先利用主成分分析法將原共生矩陣進(jìn)行降維，將其矩陣O先進(jìn)行中心化。中心化是指先計(jì)算每個(gè)維度平均值，再把每個(gè)維度的特征值都減去該均值。之后再計(jì)算中心化樣本矩陣的協(xié)方差矩陣，計(jì)算其協(xié)方差矩陣的特征值和特征向量(假設(shè)求出的特征值共有20個(gè)，選定一個(gè)合適的特征值最大區(qū)間，比如前90%，即前18個(gè)最大特征值對(duì)應(yīng)的特征向量)，得到對(duì)應(yīng)矩陣U，再根據(jù)降維轉(zhuǎn)換公式J=OU，就得到轉(zhuǎn)換后的降維矩陣J。與原矩陣相比，降維后的矩陣處理速度大大提高，雖然可能有信息損失，但可以接受。

2.3 相似度度量

投影后的矩陣就可以對(duì)其進(jìn)行距離度量，常用的有L1范數(shù)、歐氏距離、KL距離、余弦距離等。

最后為度量查詢數(shù)據(jù)與被查詢數(shù)據(jù)之間的關(guān)聯(lián)性，要對(duì)相似度大小進(jìn)行排序。具體是統(tǒng)計(jì)每一組查詢數(shù)據(jù)與被查詢數(shù)據(jù)之間相似度距離，根據(jù)相似度距離進(jìn)行排序，找到相似度最高的作為檢索結(jié)果展示。

3 實(shí)驗(yàn)結(jié)果及分析

3.1 實(shí)驗(yàn)數(shù)據(jù)和流程

實(shí)驗(yàn)選取文本、圖像作為跨模態(tài)信息檢索的數(shù)據(jù)，以“文本搜圖像”和“圖像搜文本”作為實(shí)驗(yàn)任務(wù)。選取的數(shù)據(jù)集是Wikipedia跨模態(tài)信息檢索數(shù)據(jù)集，包含兩千多份文檔和10個(gè)主題。

特征提取部分：對(duì)文本數(shù)據(jù)，利用gensim工具包提取主題空間的特征，構(gòu)建特征空間W，維度為10。對(duì)圖像數(shù)據(jù)，利用VLFeat機(jī)器視覺庫計(jì)算出其在BOVW圖像空間上的特征，構(gòu)建特征空間G，維度為128。

對(duì)特征子空間投影，將得到的圖像特征X和文本特征Y先進(jìn)行中心化處理，再將處理后的數(shù)據(jù)進(jìn)行主成分分析，選取一個(gè)合適的提取量，得到降維后的圖像和文本特征向量，再對(duì)降維后的數(shù)據(jù)進(jìn)行典型性分析，得到相應(yīng)文本和圖像的投影函數(shù)XCCA和YCCA。再分別與降維后的圖像文本特征相乘，得到相應(yīng)投影在公共子空間的圖像文本向量。最后根據(jù)相似度進(jìn)行度量，可分別運(yùn)用KL距離，第一、第二范式，歸一化相關(guān)性(NC)和歸一化交叉相關(guān)性度量(NCC)來進(jìn)行度量。文中主要選取NC與NCC進(jìn)行度量。為方便起見，選取主成分分析的特征值比例為前95%和90%。

3.2 實(shí)驗(yàn)結(jié)果對(duì)比

為方便計(jì)算，選定子空間的維度為6維、8維，相似度度量選取歸一化相關(guān)性NC，然后比較不同方法之間的區(qū)別。計(jì)算結(jié)果分別如表1和表2所示，將時(shí)間分別進(jìn)行統(tǒng)計(jì)比較后，結(jié)果如圖1～圖3所示。

表1 維度為6時(shí)的計(jì)算結(jié)果

表2 維度為8的計(jì)算結(jié)果

圖1 總時(shí)間統(tǒng)計(jì)

圖2 相應(yīng)的投影時(shí)間比較

圖3 相似度計(jì)算時(shí)間度量

從圖中可看出，改進(jìn)后的算法所需時(shí)間明顯低于傳統(tǒng)算法的計(jì)算時(shí)間。總體優(yōu)化比例平均為1-(16.3/16.9)=3%。由于實(shí)驗(yàn)源數(shù)據(jù)量不大，在進(jìn)行數(shù)據(jù)樣本預(yù)處理時(shí)，實(shí)驗(yàn)所做的是對(duì)樣本整體都進(jìn)行主成分分析，而在之后的檢索比較過程中只是選取部分樣本進(jìn)行了檢索，因此在總體時(shí)間上優(yōu)化效率不是特別明顯。但該優(yōu)化算法的優(yōu)勢(shì)在于，在進(jìn)行后續(xù)向量投影和相似度度量方面，使用時(shí)間明顯比傳統(tǒng)算法要少。所以，在進(jìn)行跨模態(tài)信息檢索時(shí)，如果數(shù)據(jù)源數(shù)據(jù)越大，相比傳統(tǒng)算法，此優(yōu)化算法檢索結(jié)果的時(shí)間越少。

4 結(jié)束語

針對(duì)傳統(tǒng)跨模態(tài)檢索算法存在處理高維度計(jì)算量巨大的問題，提出的算法在向量投影和相似度度量方面進(jìn)行了改進(jìn)并進(jìn)行了實(shí)驗(yàn)驗(yàn)證。實(shí)驗(yàn)結(jié)果表明，該算法明顯提高了跨模態(tài)信息檢索的效率，在大數(shù)據(jù)量的情況使用，效率可以提高到6%左右。同時(shí)在處理更大數(shù)據(jù)的情況下，該算法在檢索時(shí)間上有更大優(yōu)勢(shì)。

算法的不足之處在于在處理數(shù)據(jù)時(shí)，沒有解決數(shù)據(jù)非線性非正交的問題。在處理主成分比例時(shí)，選取的比例不是相對(duì)最好的，需要人工選取比例。之后的工作將對(duì)這些不足之處進(jìn)行研究。