徐 猛，王 靖

(華僑大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，福建 廈門 361021)

1 引言

隨著科學(xué)技術(shù)的飛速發(fā)展，現(xiàn)實(shí)中所獲取、存儲(chǔ)和需要處理的數(shù)據(jù)往往以非結(jié)構(gòu)化的形式存在于高維觀察空間中，如高分辨率圖像數(shù)據(jù)、金融統(tǒng)計(jì)數(shù)據(jù)、視頻音頻數(shù)據(jù)、全球氣候數(shù)據(jù)及網(wǎng)絡(luò)文本數(shù)據(jù)等。這些數(shù)據(jù)不僅數(shù)據(jù)量龐大，而且更新速度快。因此，它們的內(nèi)在規(guī)律往往難以直接觀察和學(xué)習(xí)，使得原有的機(jī)器學(xué)習(xí)[1]算法很難對(duì)這些數(shù)據(jù)進(jìn)行有效的處理。

如何在保持信息完整的情況下從大量數(shù)據(jù)中提取有效信息，發(fā)現(xiàn)其內(nèi)在規(guī)律，一直是模式識(shí)別和機(jī)器學(xué)習(xí)研究的熱點(diǎn)問題。

近年來，流形學(xué)習(xí)[2,3]在高維數(shù)據(jù)降維和數(shù)據(jù)可視化方面取得了巨大成功。這些算法包括等距映射算法(Isomap)[4]、局部線性嵌入算法LLE(Locally Linear Embedding)[5]、局部切空間排列算法LTSA(Local Tangent Space Alignment)[6]、拉普拉斯特征映射LE(Laplacian Eigen maps)[7]等。盡管這些流形學(xué)習(xí)算法在機(jī)器學(xué)習(xí)、模式識(shí)別、計(jì)算機(jī)視覺等領(lǐng)域得到了廣泛應(yīng)用，但是只能學(xué)習(xí)分布于單個(gè)流形數(shù)據(jù)的非線性特征。在現(xiàn)實(shí)世界的許多應(yīng)用中，如跨語言信息檢索[8 - 10]、姿態(tài)估計(jì)[11]、圖像和文本的匹配[12]等，數(shù)據(jù)分布于多個(gè)不同流形，需要同時(shí)學(xué)習(xí)兩個(gè)或者更多的數(shù)據(jù)集的非線性特征。此時(shí)，傳統(tǒng)的流形學(xué)習(xí)算法并不適用。

為了解決這個(gè)問題，近年來學(xué)者們提出了流形對(duì)齊算法[13 - 15]。多數(shù)流形對(duì)齊算法首先學(xué)習(xí)每個(gè)流形數(shù)據(jù)集的局部幾何結(jié)構(gòu)，如局部近鄰關(guān)系[16]、稀疏重構(gòu)權(quán)[17]或基于測(cè)地距離的全局幾何結(jié)構(gòu)[18]；然后，利用已知數(shù)據(jù)集之間的對(duì)應(yīng)點(diǎn)信息[19]或樣本點(diǎn)的幾何結(jié)構(gòu)[18,20,21]挖掘不同數(shù)據(jù)集樣本點(diǎn)之間的關(guān)聯(lián)性；最后，將不同的流形數(shù)據(jù)集投影到共同的低維空間中，并在低維空間中從特征層[3,18]或?qū)嵗龑覽22]保持每個(gè)流形的局部幾何結(jié)構(gòu)和不同數(shù)據(jù)集之間樣本點(diǎn)的關(guān)聯(lián)性。

雖然流形對(duì)齊已在機(jī)器學(xué)習(xí)的許多領(lǐng)域中得到有效應(yīng)用，但現(xiàn)有的流形對(duì)齊算法面臨一個(gè)普遍的挑戰(zhàn)。當(dāng)數(shù)據(jù)集之間的對(duì)應(yīng)點(diǎn)信息不充分時(shí)，僅僅利用流形數(shù)據(jù)的局部結(jié)構(gòu)[20,21]或全局結(jié)構(gòu)[18]難以準(zhǔn)確挖掘不同數(shù)據(jù)集樣本點(diǎn)之間的關(guān)聯(lián)性。而這往往導(dǎo)致了不同流形數(shù)據(jù)集的樣本無法在低維空間中準(zhǔn)確對(duì)齊。因此，本文提出一種基于全局和局部特征匹配的流形對(duì)齊算法。首先，計(jì)算不同流形樣本點(diǎn)之間的測(cè)地距離，并以此表示樣本點(diǎn)之間的關(guān)聯(lián)性；然后，構(gòu)造每個(gè)流形樣本點(diǎn)的局部結(jié)構(gòu)，并基于局部結(jié)構(gòu)計(jì)算樣本點(diǎn)之間的相似性；最后，利用樣本點(diǎn)之間局部特征的相似性對(duì)不同流形樣本點(diǎn)之間的測(cè)地距離進(jìn)行修正，從而更為準(zhǔn)確地挖掘不同流形樣本點(diǎn)之間的關(guān)聯(lián)性。

本文其它章節(jié)安排如下：在第2節(jié)中，簡(jiǎn)單回顧了一種保持全局結(jié)構(gòu)的流形對(duì)齊算法PGGMA(Preserving Global Geometry for Mainfold Alignment)，并提出了該算法的不足之處；在第3節(jié)中，提出了基于PGGMA的改進(jìn)算法,即基于全局和局部特征匹配的流形對(duì)齊算法；在第4節(jié)中，通過實(shí)驗(yàn)驗(yàn)證了本文算法的有效性；最后，對(duì)本文算法進(jìn)行了總結(jié)和展望。

2 保持全局結(jié)構(gòu)的流形對(duì)齊算法

2.1 算法回顧

在這一節(jié)中，對(duì)PGGMA算法做簡(jiǎn)單回顧。給定兩個(gè)采自流形X和Y上的數(shù)據(jù)集X={x1,…,xm}，Y={y1,…,yn}，其中X∈Rpx×m,Y∈Rpy×n,px、py分別表示數(shù)據(jù)集X和Y中樣本點(diǎn)的維度。PGGMA為半監(jiān)督流形學(xué)習(xí)算法，需要預(yù)先給定部分樣本點(diǎn)的對(duì)應(yīng)信息作為先驗(yàn)知識(shí)。假設(shè)X、Y中給定的對(duì)應(yīng)點(diǎn)表示為，xai?ybi，ai∈[1,m],bi∈[1,n],i∈[1,l],其中l(wèi)是給定的對(duì)應(yīng)點(diǎn)個(gè)數(shù)。PGGMA算法首先估計(jì)每個(gè)樣本點(diǎn)到其余樣本點(diǎn)的測(cè)地距離，并以此表示樣本點(diǎn)的全局幾何結(jié)構(gòu)，然后將所有樣本點(diǎn)投影到一個(gè)共同的低維空間，并在低維空間中盡可能地保持樣本點(diǎn)的全局幾何結(jié)構(gòu)。算法主要包括下面三個(gè)步驟：

(1)

由于xi與yj的維度不同，無法直接計(jì)算兩者之間的距離。在文獻(xiàn)[18]中，利用對(duì)應(yīng)點(diǎn)xau?ybu,u∈[1,l]構(gòu)造xi與yj間測(cè)地距離最短的通路，并以此計(jì)算xi與yj的測(cè)地距離，即:

(2)

(3)

的最大d個(gè)特征值以及對(duì)應(yīng)的特征向量γ=[γ1,…,γd]。記[α,β]T=[γ1,…,γd]，則可以獲得線性映射α和β，以及X和Y在d維空間中的投影坐標(biāo)αTX和βTY。

2.2 存在的問題

在PGGMA算法中，算法的核心在于如何有效地聯(lián)結(jié)兩個(gè)不同流形。PGGMA利用式(2)估計(jì)兩個(gè)流形樣本點(diǎn)之間的測(cè)地距離，用于聯(lián)結(jié)兩個(gè)不同的流形。但是，當(dāng)給定少量對(duì)應(yīng)點(diǎn)時(shí)，這種測(cè)地距離的估計(jì)方式可能無法準(zhǔn)確反映不同流形樣本點(diǎn)之間的關(guān)聯(lián)性。接下來，本文以一個(gè)模擬例子來說明這個(gè)問題。

假設(shè)數(shù)據(jù)集X和Y采自于兩條不同的曲線，即:

yi=[0.5sin(tj),0.5cos(tj)]T,

已知兩個(gè)數(shù)據(jù)集中有三組對(duì)應(yīng)點(diǎn)x10?y10、x70?y70、x130?y130，如圖1所示?；谶@三組對(duì)應(yīng)點(diǎn)并利用式(2)可以計(jì)算出所有xi與yi之間的距離。比如，x17和y20、x20和x20之間的距離為:

Figure 1 Manifold curves X and Y圖1 流形曲線X和Y

從計(jì)算結(jié)果看，x17和y20的距離小于x20和y20之間的距離，即x17和y20更有可能是匹配點(diǎn)。但實(shí)際上，x20和y20是對(duì)應(yīng)點(diǎn)。

從這個(gè)例子可以看出，當(dāng)已知的對(duì)應(yīng)點(diǎn)信息不夠充分時(shí)，按照式(2)估計(jì)的測(cè)地距離難以準(zhǔn)確聯(lián)結(jié)兩個(gè)流形。

3 基于全局和局部特征匹配的流形對(duì)齊算法

(4)

(5)

其中，φ是正則化參數(shù)，和分別表示曲線和的梯度。在本文的實(shí)驗(yàn)中，φ固定設(shè)置為1。從式(4)和式(5)可以看出，如果xi和yj具有相似的局部結(jié)構(gòu)，則會(huì)較小，從而減小xi和yj的距離。

Figure 2 Alignment results of several manifold alignment algorithms on FacePix data set圖2 幾種不同流形對(duì)齊算法在FacePix數(shù)據(jù)集上的對(duì)齊結(jié)果

在新的距離計(jì)算公式下，x20和y20之間距離小于x17和y20，表明x20比x17更有可能是y20的匹配點(diǎn)。這說明綜合利用樣本點(diǎn)的全局和局部特征，能更好地聯(lián)結(jié)兩個(gè)不同流形。

4 數(shù)值實(shí)驗(yàn)

為了體現(xiàn)本文算法的有效性，本文在FacePix和COIL-20兩個(gè)實(shí)際數(shù)據(jù)集上，同三種半監(jiān)督的算法PGGMA[18]、PAMA(Procrustes Analysis for Manifold Alignment)[22]、SSMA(Semi-Supervised Manifold Alignment)[19]和一種非監(jiān)督的算法UNMA(UN-supervised Manifold Alignment)[21]進(jìn)行實(shí)驗(yàn)對(duì)比。

4.1 度量方式和參數(shù)設(shè)置

本文實(shí)驗(yàn)?zāi)康氖菍?duì)目標(biāo)領(lǐng)域數(shù)據(jù)集X={xi|i=1,…,m}和輔助領(lǐng)域的數(shù)據(jù)集Y={yj|1,…,n}中的圖像進(jìn)行匹配。對(duì)目標(biāo)領(lǐng)域中的圖像xi，如果輔助領(lǐng)域數(shù)據(jù)集中的圖像yj是其在低維投影空間的最近點(diǎn)，則yj是xi的匹配圖像。記θxi和θyj為圖像xi與yj中人臉或物體的旋轉(zhuǎn)角度。如果|θxi-θyj|≤θ，則yj為xi的準(zhǔn)確匹配圖像。為了量化圖像匹配的結(jié)果，本文提出匹配準(zhǔn)確率和平均角度差兩種度量方式：

其中，n是目標(biāo)領(lǐng)域圖像的數(shù)目。

鄰域參數(shù)k和目標(biāo)維度d是本文算法和對(duì)比算法PGGMA、PAMA、SSMA均涉及的參數(shù)。在本文實(shí)驗(yàn)中，均設(shè)置k=10,d=10。

4.2 FacePix人臉圖像數(shù)據(jù)集

在這個(gè)實(shí)驗(yàn)中，將流形對(duì)齊算法用于人臉姿態(tài)的對(duì)齊。所用到的圖像數(shù)據(jù)來自于FacePix人臉圖像數(shù)據(jù)，一共含有30個(gè)人不同人臉姿態(tài)下的圖像。本文選取其中兩組男女頭像進(jìn)行對(duì)比實(shí)驗(yàn)。每組數(shù)據(jù)集包含181個(gè)128*128規(guī)模的圖像，由攝像機(jī)圍繞頭部從-90°旋轉(zhuǎn)到+90°，每間隔1°拍攝而成。將每張圖像縮小成32*32圖像，再進(jìn)行向量化，由此得到兩個(gè)1024*181的數(shù)據(jù)集。

假設(shè)兩個(gè)數(shù)據(jù)集已知對(duì)應(yīng)點(diǎn)有6個(gè)，采用流形對(duì)齊算法將兩個(gè)數(shù)據(jù)集投影到共同的10維空間。圖2列出了本文算法和PGGMA、PAMA、SSMA、UNMA的匹配結(jié)果。圖中用黑色加粗邊框標(biāo)注出錯(cuò)誤匹配的圖像，即與原圖像的角度差大于10°的匹配圖像。本實(shí)驗(yàn)中，由于無監(jiān)督算法UNMA只利用樣本點(diǎn)的局部幾何結(jié)構(gòu)進(jìn)行匹配，實(shí)驗(yàn)結(jié)果并不理想。在半監(jiān)督算法中，本文算法明顯優(yōu)于其余算法，能很好地在輔助領(lǐng)域中尋找到目標(biāo)領(lǐng)域圖像的匹配點(diǎn)。進(jìn)一步地，本文設(shè)計(jì)實(shí)驗(yàn)對(duì)匹配結(jié)果進(jìn)行量化。圖3a列出了角度差從0°到10°變化時(shí)，幾種算法的圖像匹配準(zhǔn)確率。顯然，在不同的角度差下，本文算法的圖像匹配準(zhǔn)確率明顯高于其它流形對(duì)齊算法。

Figure 5 Alignment results of several manifold alignment algorithms on the objects obj1 and obj13 from the COIL-20 database圖5 幾種流形對(duì)齊算法在COIL-20數(shù)據(jù)庫(kù)上目標(biāo)obj1和obj13的對(duì)齊結(jié)果

Figure 3 Maching accuracies on FacePix data set圖3 FacePix數(shù)據(jù)集上的匹配準(zhǔn)確率

衡量半監(jiān)督流形對(duì)齊算法性能的一個(gè)重要指標(biāo)是算法對(duì)先驗(yàn)信息的依賴性。本文設(shè)計(jì)實(shí)驗(yàn)以驗(yàn)證半監(jiān)督流形對(duì)齊算法在給定不同個(gè)數(shù)對(duì)應(yīng)點(diǎn)情況下的效果。圖3b列出了幾種半監(jiān)督流形對(duì)齊算法在對(duì)應(yīng)點(diǎn)個(gè)數(shù)從2到10時(shí)的圖像匹配準(zhǔn)確率(角度差θ=5)。從圖3中可以看出，PGGMA、PAMA、SSMA對(duì)先驗(yàn)信息有較高的要求。要達(dá)到60%的匹配準(zhǔn)確率，三種算法分別要求給定9個(gè)、6個(gè)和10個(gè)對(duì)應(yīng)點(diǎn)作為先驗(yàn)信息。而本文算法在少量先驗(yàn)信息的情況下(l=3)，圖像匹配準(zhǔn)確率就可以超過80%。這主要是因?yàn)楸疚乃惴ňC合樣本點(diǎn)的局部特征和全局特征以聯(lián)結(jié)不同流形。當(dāng)獲取的先驗(yàn)信息不充分時(shí)，這比只依賴給定對(duì)應(yīng)點(diǎn)聯(lián)結(jié)流形具有更高的可靠性。

4.3 COIL-20數(shù)據(jù)庫(kù)

在這個(gè)實(shí)驗(yàn)中,將流形對(duì)齊算法用于COIL-20數(shù)據(jù)庫(kù)。此數(shù)據(jù)庫(kù)由20個(gè)不同物體在不同旋轉(zhuǎn)角度下的圖像構(gòu)成。相機(jī)圍繞物體旋轉(zhuǎn)360°，每次旋轉(zhuǎn)5°共拍攝72幅128*128大小的圖像。本實(shí)驗(yàn)選擇7個(gè)不同的物體進(jìn)行實(shí)驗(yàn)，物體圖像見圖4。將每張圖像縮小為32*32規(guī)模，再轉(zhuǎn)化成一個(gè)1 024維向量，這樣得到7個(gè)規(guī)模為1024*72的數(shù)據(jù)集。

Figure 4 Seven experiment objects in the COIL-20 database圖4 COIL-20數(shù)據(jù)庫(kù)中的七個(gè)實(shí)驗(yàn)?zāi)繕?biāo)

本文首先用obj1和obj13進(jìn)行可視化匹配效果實(shí)驗(yàn)。給定7個(gè)對(duì)應(yīng)點(diǎn)，采用不同流形對(duì)齊算法將兩個(gè)數(shù)據(jù)集投影到共同的10維空間。圖5列出了本文算法和PGGMA、PAMA、SSMA、UNMA的匹配結(jié)果。圖中用黑色加粗邊框標(biāo)注了錯(cuò)誤匹配的圖像，即與原圖像角度差大于15°的匹配圖像。顯然，本文算法能在obj13中找到所列出的obj1匹配圖像。進(jìn)一步地，本文對(duì)匹配結(jié)果進(jìn)行量化實(shí)驗(yàn)。圖6a列出了幾種算法在角度差θ從0°到25°的圖像匹配準(zhǔn)確率。如圖6所示，本文算法的匹配準(zhǔn)確率高于其它流形對(duì)齊算法。當(dāng)θ=20°時(shí)，本文算法的匹配準(zhǔn)確率超過90%。

Figure 6 Maching accuracies on COIL-20 database圖6 COIL-20數(shù)據(jù)庫(kù)上的匹配準(zhǔn)確率

本文算法和PGGMA、PAMA、SSMA、UNMA等算法都涉及到目標(biāo)維度參數(shù)d。本文設(shè)計(jì)實(shí)驗(yàn)以驗(yàn)證不同流形對(duì)齊算法對(duì)參數(shù)d的敏感性。給定l=7個(gè)對(duì)應(yīng)點(diǎn)并固定角度差θ=15°，圖6b列出了不同流形對(duì)齊算法在d從5增大到45時(shí)的圖像匹配準(zhǔn)確率結(jié)果。顯然，本文算法在不同d下的結(jié)果均明顯優(yōu)于其它算法。更重要的是，當(dāng)d從10增大到45時(shí)，本文算法的結(jié)果變化不大。

這表明本文算法對(duì)參數(shù)并不敏感。

最后，本文將obj1對(duì)應(yīng)的數(shù)據(jù)集作為目標(biāo)數(shù)據(jù)集，obj2、obj3、obj4、obj7、obj9、obj13等6個(gè)物體對(duì)應(yīng)的數(shù)據(jù)集作為輔助數(shù)據(jù)集進(jìn)行對(duì)齊實(shí)驗(yàn)。給定l=5,8,11等不同個(gè)數(shù)的對(duì)應(yīng)點(diǎn)，表1列出了本文算法和PGGMA、PAMA、SSMA、UNMA在這6個(gè)輔助數(shù)據(jù)集上的平均角度差。顯然，越小的平均角度差意味著越好的對(duì)齊效果。從表1可以看出，所有算法在6個(gè)輔助數(shù)據(jù)集上的平均角度差都隨著l的增大而減小。這表明對(duì)應(yīng)點(diǎn)個(gè)數(shù)的增加能幫助流形對(duì)齊算法更好地聯(lián)結(jié)不同流形。值得注意的是，當(dāng)只給定很少的對(duì)應(yīng)點(diǎn)時(shí)(l=5)，本文算法在6個(gè)輔助數(shù)據(jù)集上都能取得較小的平均角度差。這進(jìn)一步說明了本文算法在少量先驗(yàn)信息情況下的有效性。

5 結(jié)束語

本文提出了一種新的算法，利用測(cè)地距離構(gòu)造不同流形樣本點(diǎn)之間的關(guān)聯(lián)性，再利用樣本點(diǎn)之間局部幾何結(jié)構(gòu)的相似性進(jìn)行修正，以更為準(zhǔn)確地挖掘不同流形樣本點(diǎn)之間的關(guān)聯(lián)性。在本文提出的半監(jiān)督流形對(duì)齊算法中，需要利用給定點(diǎn)的信息構(gòu)造兩個(gè)流形樣本點(diǎn)之間的測(cè)地距離。如何擴(kuò)展到在無監(jiān)督流形對(duì)齊算法下，保持全局和局部特征樣本點(diǎn)關(guān)系，是將來本文需要研究的內(nèi)容。此外，當(dāng)流形采樣比較稀疏或數(shù)據(jù)存在噪聲時(shí)，基于局部距離度量流形樣本之間的相似性可能并不準(zhǔn)確。如何挖掘更魯棒的局部結(jié)構(gòu)以衡量流形樣本點(diǎn)之間的相似性，也是將來的研究?jī)?nèi)容。

Table 1 Average errors of matching angles of several manifold alignment algorithms on six different objects from the COIL-20 database

[1] Martinez A M,Kak A C. PCA versus LDA[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2001,23(2):228-233.

[2] Seung H S,Lee D D.The manifold ways of perception[J].Science,2000,290(5500):2268-2269.

[3] Wang C,Mahadevan S.A general framework for manifold alignment[C]∥Proc of AAAI,2009:101-109.

[4] Tenenbaum J,Silva V,Langford J.A global geometric framework for nonlinear dimensionality reduction[J].Science,2000,290(5500):2319-2323.

[5] Roweis S T, SaulL K.Nonlinear dimensionality reduction by locally linear embedding[J].Science,2000,290(5500):2323-2326.

[6] Zhang Z.Principal manifolds and nonlinear dimensionality reduction via tangent space alignment[J].Scientific Computing,2005,6(1):313-333.

[7] Belkin M. Laplacian eigen maps for dimensionality reduction and data representation[J].Neural Computation,2003,15 (6):1373-1396.

[8] Blei D,Ng A,Jordan M.Latent dirichletallocation[J].Journal of Machine Learning Research,2003,3(9):993-1022.

[9] Deerwester S,Dumais S T,Furnas G W,et al.Indexing by latent semantic analysis[J].Journal of the American Society for Information Science,1990,41(6):391-407.

[10] Diaz F,Metzler D.Pseudo-aligned multilingual corpora[C]∥Proc of International Joint Conference on Artificial Intelligence,2007:2727-2732.

[11] Bradski G R,Davis J W.Motion segmentation and pose recognition with motion history gradients[J].Machine Vision and Applications,2002,13(3):174-184.

[12] Nigam K,Ghani R.Analyzing the effectiveness and applicability of cotraining[C]∥Proc of the 9th International Conference on Information and Knowledge Management,2000:86-93.

[13] Zhen C,Hong C,Shiguang S,et al.Generalized unsupervised manifold alignment[C]∥Proc of NIPS,2014:2429-2437.

[14] Dan L P,Yun Q T,Jun Z.Visualization of hyperspectral imaging data based on manifold alignment[C]∥Proc of International Conference on Pattern Recognition,2014:1051-1057.

[15] Heili A.Improving head and body pose estimation through semi-supervised manifold alignment[C]∥Proc of IEEE International Conference on Image Processing,2014:1912-1916.

[16] He X.Locality preserving projections[C]∥Proc of the 16th Advances in Neural Information Processing Systems,2003:153-160.

[17] Jian C L,Zhang Y.Manifold alignment based on sparse local structures of more corresponding pairs[C]∥Proc of the 23rd International Joint Conference on Atificial Intelligence,2013:2862-2868.

[18] Wang C,Mahadevan S.Manifold alignment preserving global geometry[C]∥Proc of the 23rd International Joint Conference on Artificial Intelligence,2013:1743-1749.

[19] Ham J,Lee D,Saul L.Semi-supervised alignment of manifolds[C]∥Proc of International Workshop on Artificial Intelligence and Statistics,2005:120-127.

[20] Yu P,Feng H C,Fu S H,et al.Unsupervised image matching based on manifold alignment[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2012,34(8):1658-1664.

[21] Wang C,Mahadevan S.Manifold alignment without correspondence[C]∥Proc of the 21st International Joint Conference on Artifical Intelligence,2009:1273-1278.

[22] Wang C,Mahadevan S.Manifold alignment using procrustes analysis[C]∥Proc of the 25th International Conference on Machine Learning,2008:1120-1127.

[23] Perth W A, Mian A,Lin L,et al.Unsupervised iterative manifold alignment via local feature histograms[C]∥Proc of IEEE Winter Conference on Applications of Computer Vision,2014:572-579.