基于子空間距離的局部切空間增量學(xué)習(xí)

李德宜，曾 弦，周 勇

(武漢科技大學(xué)理學(xué)院，湖北 武漢，430065)

流形學(xué)習(xí)作為一種新穎的非線性降維工具而受到研究者的熱切關(guān)注。局部切空間排列(local tangent space alignment, LTSA)[1-3]是經(jīng)典的流形學(xué)習(xí)算法之一，其思想樸素、幾何意義直觀。LTSA假設(shè)數(shù)據(jù)集的局部幾何特性可由樣本點(diǎn)的局部切空間得到，該局部切空間經(jīng)過(guò)旋轉(zhuǎn)、伸縮、平移等線性變換之后可排列出全局的低維流形。與ISOMAP[4]和LLE[5]等流形算法相比，LTSA對(duì)鄰域點(diǎn)個(gè)數(shù)不敏感，具有穩(wěn)定的非線性學(xué)習(xí)能力[6]，已成功應(yīng)用于圖像識(shí)別[7-8]、故障診斷[9-11]等領(lǐng)域。但是，LTSA同樣缺乏高維到低維的顯式映射，當(dāng)新的數(shù)據(jù)到來(lái)時(shí)只能重新計(jì)算，無(wú)法滿足實(shí)時(shí)在線運(yùn)算的需求。實(shí)際應(yīng)用中，大量數(shù)據(jù)如語(yǔ)音數(shù)據(jù)、視頻數(shù)據(jù)、在線監(jiān)控?cái)?shù)據(jù)等是逐漸獲取的，設(shè)計(jì)有效的增量學(xué)習(xí)方法是LTSA等流形學(xué)習(xí)算法走向?qū)嵱没年P(guān)鍵。

增量學(xué)習(xí)可簡(jiǎn)單表述為：假定高維空間數(shù)據(jù)集X={x1,x2,…,xn}所在低維流形已經(jīng)得到，記為Y={y1,y2,…,yn}，則根據(jù)新來(lái)的觀測(cè)值xn+1，如何更新已有的低維流形上的點(diǎn)集Y以及發(fā)現(xiàn)yn+1。尋找高維空間和低維空間的顯式映射關(guān)系的方法可用于增量學(xué)習(xí)，代表性的有鄰域保護(hù)嵌入(NPE)[12]、局部保持映射(LPP)[13]等。這類算法將學(xué)習(xí)目標(biāo)轉(zhuǎn)化為尋求滿足一定約束關(guān)系(如保持局部鄰域線性關(guān)系)的線性子空間，新的數(shù)據(jù)點(diǎn)可以直接投影至低維空間。線性方法存在的問(wèn)題是，隨著數(shù)據(jù)集的不斷擴(kuò)充，矩陣求取特征值的計(jì)算復(fù)雜度呈幾何數(shù)量級(jí)增加。

流形的增量學(xué)習(xí)問(wèn)題也可視為：在已有的鄰接圖上，采取怎樣的策略為新的數(shù)據(jù)點(diǎn)尋找一個(gè)合適的鄰域位置。這樣低維坐標(biāo)就可由鄰域的幾何特性計(jì)算得到，其代表性方法是ISOMAP的增量學(xué)習(xí)方法[14]。受此啟發(fā)，Liu等[15]提出了增量式LTSA算法和帶標(biāo)志點(diǎn)的增量式LTSA算法。這類方法的關(guān)鍵是對(duì)測(cè)地線距離的增量估計(jì)，故前期學(xué)習(xí)結(jié)果得到利用。但是測(cè)地線距離的計(jì)算復(fù)雜度高，并且依賴k近鄰法選擇鄰域。真實(shí)數(shù)據(jù)集具有維數(shù)高、分布不均的特點(diǎn)，通過(guò)常用的k近鄰法選擇的近鄰點(diǎn)往往不能正確表征局部幾何特性，即由鄰域得到的局部切空間本征維數(shù)不一致，導(dǎo)致學(xué)習(xí)失敗。

如果新觀測(cè)點(diǎn)在已有數(shù)據(jù)集中的近鄰關(guān)系構(gòu)建正確，將高階矩陣特征分解轉(zhuǎn)化為低階矩陣特征分解的方法就可用于更新全局坐標(biāo)。楊慶等[16]采用特征值迭代方法更新全局坐標(biāo)，提出增量式局部切空間排列算法用于滾動(dòng)軸承故障診斷。佘博等[17]也根據(jù)特征值迭代的思路提出增量式監(jiān)督局部切空間排列算法，并應(yīng)用于齒輪箱的故障診斷中。但通過(guò)矩陣分解特征值迭代求得新觀測(cè)點(diǎn)的全局坐標(biāo)仍然要以準(zhǔn)確估計(jì)新觀測(cè)點(diǎn)的局部幾何特性為前提，尤其對(duì)于真實(shí)數(shù)據(jù)集而言，鄰域選擇策略非常關(guān)鍵，決定了增量學(xué)習(xí)算法的成敗。為了保證每個(gè)樣本點(diǎn)所在的局部切空間維數(shù)相同，董冀媛等[7-8,18]提出了自適應(yīng)局部切空間排列算法ALTSA，并進(jìn)一步簡(jiǎn)化，提出了基于劃分的局部切空間排列算法SLTSA，用于人耳多姿態(tài)圖像識(shí)別，取得了較好的識(shí)別結(jié)果。SLTSA 把數(shù)據(jù)集劃分為數(shù)量遠(yuǎn)少于樣本點(diǎn)個(gè)數(shù)的局部最大線性片，使用重疊點(diǎn)來(lái)引導(dǎo)并建立排列矩陣，非重疊點(diǎn)則直接通過(guò)仿射變換求得全局坐標(biāo)。這種思想為L(zhǎng)TSA的增量學(xué)習(xí)提供了便利條件。

本文根據(jù)真實(shí)數(shù)據(jù)集的特點(diǎn)引入向量與子空間的距離度量，提出一種基于子空間距離的局部切空間增量學(xué)習(xí)方法(incremental-SLTSA,ISLTSA)來(lái)進(jìn)一步簡(jiǎn)化SLTSA，并在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，以驗(yàn)證ISLTSA的非線性學(xué)習(xí)能力。

1 局部切空間排列算法

1.1 LTSA基本原理

LTSA算法分為3個(gè)步驟：

(1)找到每個(gè)樣本點(diǎn)的k個(gè)最近鄰點(diǎn)。記Xi=[xi1,…,xik]為包括樣本點(diǎn)xi在內(nèi)的最近鄰所構(gòu)成的矩陣。

(1)

(2)

=trace(TΦTT)

(3)

其中

(4)

矩陣Φ的第 2到d+1個(gè)最小特征值所對(duì)應(yīng)的特征向量即為使重建誤差E(T)最小的低維嵌入。

1.2 基于劃分的局部切空間排列算法SLTSA

與LTSA不同，基于劃分的簡(jiǎn)化局部切空間排列算法SLTSA[18]采用分段線性化的思想，以數(shù)量遠(yuǎn)少于樣本個(gè)數(shù)的局部最大線性片擬合原始數(shù)據(jù)集，減少了LTSA逐點(diǎn)計(jì)算局部切空間的計(jì)算量。SLTSA采用自適應(yīng)鄰域選擇策略構(gòu)建局部最大線性片，為了保證局部線性片的本征維數(shù)與目標(biāo)維數(shù)相同，首先使用較小的k值構(gòu)建鄰域，如果鄰域所在局部切空間本征維數(shù)小于低維嵌入的維數(shù)d，說(shuō)明k個(gè)近鄰點(diǎn)不能表達(dá)真實(shí)的局部結(jié)構(gòu)，于是就逐漸擴(kuò)充近鄰點(diǎn)，直到鄰域所在局部切空間維數(shù)達(dá)到d。

為了以最少的局部線性片擬合數(shù)據(jù)集，SLTSA算法中局部線性片包含了使所在切空間本征維數(shù)為d的最多的近鄰點(diǎn)。如果擴(kuò)入的近鄰點(diǎn)使切空間維數(shù)大于目標(biāo)維數(shù)d，則達(dá)到局部線性片最大的邊界，從這個(gè)點(diǎn)開(kāi)始重新構(gòu)建新的局部線性片，直到所有的樣本點(diǎn)都有局部線性片的歸屬為止。

為了降低對(duì)每一個(gè)樣本點(diǎn)反復(fù)計(jì)算本征維數(shù)的計(jì)算量，并考慮到自適應(yīng)擴(kuò)張策略大大增加了近鄰樣本點(diǎn)彼此之間鄰域的重疊程度，SLTSA還將數(shù)據(jù)分為同時(shí)屬于兩個(gè)及以上局部線性片的重疊點(diǎn)和僅屬于一個(gè)線性片的非重疊點(diǎn)，利用重疊點(diǎn)求取這些線性片到全局低維流形的仿射變換Li。非重疊點(diǎn)的全局坐標(biāo)利用仿射變換Li直接計(jì)算；重疊點(diǎn)的全局坐標(biāo)由矩陣Φ的特征向量得到，矩陣Φ維數(shù)因此減少為重疊點(diǎn)個(gè)數(shù)，計(jì)算復(fù)雜度大大降低。對(duì)于真實(shí)數(shù)據(jù)集，尤其是圖像數(shù)據(jù)，相對(duì)于樣本維數(shù)，樣本數(shù)量不足，幾乎每個(gè)樣本點(diǎn)都屬于兩個(gè)以上的局部線性片，而且初始訓(xùn)練集采用離線訓(xùn)練模式，沒(méi)有實(shí)時(shí)性要求，因此重疊點(diǎn)和非重疊點(diǎn)的標(biāo)記步驟可以省去，采用全部數(shù)據(jù)參與全局排列。

2 基于子空間距離的局部切空間增量學(xué)習(xí)方法

在SLTSA的基礎(chǔ)上，本文提出了基于子空間距離的局部切空間排列算法的增量學(xué)習(xí)方法ISLTSA，當(dāng)新的數(shù)據(jù)點(diǎn)到來(lái)時(shí)，判定其局部線性片的歸屬后可以直接通過(guò)仿射變換求取全局坐標(biāo)。為了判別新數(shù)據(jù)點(diǎn)的歸屬，本文引入向量到子空間的距離度量方法以衡量新數(shù)據(jù)點(diǎn)與已有局部切空間的距離，將新數(shù)據(jù)點(diǎn)劃分到距離最近的局部最大線性片中，再利用該線性片到全局低維流形的仿射變換計(jì)算出新數(shù)據(jù)點(diǎn)的低維坐標(biāo)。

2.1 新數(shù)據(jù)點(diǎn)到局部線性子空間的距離度量

設(shè)x∈RD是D維向量，V∈Rd是歐氏空間的d維線性子空間(D?d)，x到V的距離dis(x,V)定義為：

(5)

式中：| · |表示長(zhǎng)度；δ是子空間V的向量；x′為x在V中的投影。

式(5)表示向量x到子空間V的距離dis(x,V)是x與V中所有向量端點(diǎn)之間長(zhǎng)度的下確界，即x與投影x′之間的距離。

考慮高維數(shù)據(jù)集X∈RD的任一最大線性片Mi。設(shè)Mi可由一組正交基向量{q1,q2,...,qd}張成的子空間Q表示，則向量x到子空間Q的投影x′可表示為：

(6)

(7)

式中：‖·‖2表示長(zhǎng)度取歐氏距離。

2.2 ISLTSA學(xué)習(xí)步驟

ISLTSA的學(xué)習(xí)分為兩個(gè)階段：第一階段(Step 1～Step 3)使用SLTSA求得原始數(shù)據(jù)集X=[x1,…,xN]的低維流形T=[T1,…,TN]，并同時(shí)求得m個(gè)局部最大線性片組成的集合{Mi,i=1,…,m}、線性子空間集合Q={Qi,i=1,…,m}、局部仿射變換集合L={Li,i=1,…,m}；第二階段(Step 4)是增量學(xué)習(xí)階段，求得新數(shù)據(jù)點(diǎn)xnew的全局坐標(biāo)。

詳細(xì)步驟如下：

Step1構(gòu)建局部最大線性片集合{Mi,i=1,…,m}。

Step1.1記h為最大線性片個(gè)數(shù),設(shè)初值h=1;設(shè)置特征維數(shù)d和線性片局部線性逼近精度η;選定一個(gè)初始點(diǎn)xi(i可隨機(jī)選取,本文實(shí)驗(yàn)中取i=1);初始近鄰個(gè)數(shù)k=d+1。

(8)

式中：下標(biāo)li為標(biāo)本點(diǎn)的近鄰點(diǎn)編號(hào)。

Step3計(jì)算全局坐標(biāo)。

Step3.1按照式(9)和式(10)構(gòu)建矩陣Φ：

(9)

(10)

Step3.2對(duì)矩陣Φ做特征值分解，有Φ=UTΛU，其中Λ為按特征值升序排列的對(duì)角陣，U為特征向量矩陣。取U的第2到d+1個(gè)特征向量即為低維嵌入Ti。

Step3.3按照式(11)、式(12)計(jì)算最大線性片Mi的局部坐標(biāo)到全局坐標(biāo)的仿射變換矩陣Li，i=1,…,h。

(11)

(12)

Step4計(jì)算新數(shù)據(jù)點(diǎn)xnew的低維坐標(biāo)。

Step4.1按照式(6)和式(7)計(jì)算xnew到Mi(i=1,…,h)的距離，把xnew劃分到距離最小的局部最大線性片M*中。

Step4.2按照式(13)計(jì)算xnew在M*中的局部坐標(biāo)θnew。

(13)

Step4.3按照式(14)計(jì)算xnew的全局坐標(biāo)τnew。

(14)

從Step 4可知，新數(shù)據(jù)點(diǎn)全局坐標(biāo)的計(jì)算量主要集中在Step 4.1逐個(gè)計(jì)算新數(shù)據(jù)點(diǎn)與各局部最大線性片的距離上。由式(7)可知，新數(shù)據(jù)點(diǎn)與由d維正交基向量張成的局部最大線性空間的距離的計(jì)算復(fù)雜度為O(d2)，而全局坐標(biāo)維度d遠(yuǎn)小于樣本集的數(shù)據(jù)點(diǎn)個(gè)數(shù)N和樣本所在高維觀測(cè)空間的維數(shù)D。因此，新數(shù)據(jù)點(diǎn)全局坐標(biāo)的計(jì)算量大大降低。

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

選取流形學(xué)習(xí)算法驗(yàn)證中廣泛使用的4個(gè)三維數(shù)據(jù)集S-Curve、Punctured Sphere、Twin Peaks、Toroidal Helix和人臉雕塑圖像集[4]進(jìn)行降維實(shí)驗(yàn)。4個(gè)數(shù)據(jù)集采自三維空間的非線性流形，而人臉雕塑圖像代表真實(shí)數(shù)據(jù)集，因此對(duì)這兩類數(shù)據(jù)集的降維實(shí)驗(yàn)可檢驗(yàn)本文算法的有效性。

3.1 三維數(shù)據(jù)集降維實(shí)驗(yàn)

把數(shù)據(jù)集分為初始訓(xùn)練集和增量學(xué)習(xí)測(cè)試集兩個(gè)部分：隨機(jī)選擇n個(gè)樣本點(diǎn)組成初始訓(xùn)練集，再在剩余的樣本點(diǎn)中隨機(jī)選取N個(gè)組成測(cè)試集，用于模擬新到的數(shù)據(jù)。首先在初始訓(xùn)練集的n個(gè)數(shù)據(jù)上訓(xùn)練得到二維坐標(biāo)，然后從測(cè)試樣本集中每次選擇一個(gè)數(shù)據(jù)作為新數(shù)據(jù)，用增量學(xué)習(xí)算法ISLTSA求得低維坐標(biāo)，重復(fù)此過(guò)程，直到所有的N個(gè)數(shù)據(jù)點(diǎn)均得到低維表示為止。

設(shè)置初始數(shù)據(jù)點(diǎn)個(gè)數(shù)n=100，線性片局部線性逼近誤差η取0.01。圖1是S-Curve數(shù)據(jù)集及其降維結(jié)果，分別取N=200、500、1000；圖2是Punctured Sphere數(shù)據(jù)集及其降維結(jié)果，分別取N=100、200、500；圖3是Twin Peaks數(shù)據(jù)集及其降維結(jié)果，分別取N=100、200、500。圖中實(shí)心點(diǎn)是N個(gè)測(cè)試點(diǎn)，空心圓圈是原始的n個(gè)點(diǎn)。由圖1～圖3可以看出，本文提出的ISLTSA算法能夠保持曲面數(shù)據(jù)的局部幾何特性并在二維平面展開(kāi)，即具有非線性學(xué)習(xí)能力，是有效的增量學(xué)習(xí)算法。

在Punctured Sphere和Twin Peaks數(shù)據(jù)集上，當(dāng)N=1000時(shí)，分別使用SLTSA和ISLTSA算法的嵌入結(jié)果如圖4所示。可以看出，隨著數(shù)據(jù)點(diǎn)的增多，與使用SLTSA的降維結(jié)果相比，使用增量學(xué)習(xí)ISLTSA降維時(shí)，二維流形的邊緣有收縮(紅色點(diǎn)部分)的趨勢(shì)，即當(dāng)數(shù)據(jù)較為稠密時(shí)，二維流形邊緣發(fā)生折疊現(xiàn)象，但總體上仍然能夠保持?jǐn)?shù)據(jù)的幾何特性。

(a)S-Curve 數(shù)據(jù)集 (b)N=200 (c)N=500 (d)N=1000

圖1 S-Curve數(shù)據(jù)集采用ISLTSA的二維嵌入結(jié)果

Fig.1 2D -embedding of S-Curve dataset via ISLTSA

(a)Punctured Sphere 數(shù)據(jù)集 (b)N=100 (c)N=200 (d)N=500

圖2 Punctured Sphere數(shù)據(jù)集采用ISLTSA的二維嵌入結(jié)果

Fig.2 2D -embedding of Punctured Sphere dataset via ISLTSA

(a)Twin Peaks 數(shù)據(jù)集 (b)N=100 (c)N=200 (d)N=500

圖3 Twin Peaks數(shù)據(jù)集采用ISLTSA的二維嵌入結(jié)果

Fig.3 2D -embedding of Twin Peaks dataset via ISLTSA

(a)Punctured Sphere 數(shù)據(jù)集，(b)Punctured Sphere 數(shù)據(jù)集， (c)Twin Peaks 數(shù)據(jù)集，(d)Twin Peaks 數(shù)據(jù)集，SLTSA算法 ISLTSA算法 SLTSA算法 ISLTSA 算法

圖4 SLTSA和ISLTSA的二維嵌入結(jié)果對(duì)比(N=1000)

Fig.4 2D -embedding comparison between SLTSA and ISLTSA whenN=1000

Toroidal Helix是非線性較強(qiáng)的三維螺旋曲線，圖5所示的Toroidal Helix二維嵌入結(jié)果表明，ISLTSA算法成功地將曲線在二維平面展開(kāi)，這也說(shuō)明了該算法的兩個(gè)關(guān)鍵步驟是有效的：一是通過(guò)初始訓(xùn)練集構(gòu)建的局部最大線性片集合完全能夠擬合非線性度較高的數(shù)據(jù)集；二是采用向量到子空間距離的度量方法能夠準(zhǔn)確判斷新數(shù)據(jù)點(diǎn)的局部最大線性片的歸屬，從而得到低維流形。

(a)Toroidal Helix 數(shù)據(jù)集 (b)N=100 (c)N=200 (d)N=500

圖5 Toroidal Helix數(shù)據(jù)集采用ISLTSA的二維嵌入結(jié)果

Fig.5 2D -embedding of Toroidal Helix dataset via ISLTSA

3.2 人臉雕塑圖像數(shù)據(jù)集降維實(shí)驗(yàn)

與人工數(shù)據(jù)相比，圖像數(shù)據(jù)維數(shù)高、樣本少。本實(shí)驗(yàn)采用的石膏像數(shù)據(jù)集是檢驗(yàn)流形學(xué)習(xí)算法性能的經(jīng)典數(shù)據(jù)集，其由一頭部雕塑在不同光照和不同姿態(tài)下的照片構(gòu)成，每幅圖片像素大小為64×64，像素的灰度值構(gòu)成4096維圖像向量，共有698張圖片，構(gòu)成698×4096的圖像數(shù)據(jù)矩陣X，其中每個(gè)行向量代表一幅圖像數(shù)據(jù)。取50%的數(shù)據(jù)點(diǎn)即349個(gè)樣本組成初始訓(xùn)練矩陣，剩余的349個(gè)樣本模擬新到的數(shù)據(jù)，逐點(diǎn)輸入計(jì)算低維坐標(biāo)，線性片局部線性逼近誤差η取0.01。石膏像數(shù)據(jù)集的二維嵌入結(jié)果如圖6所示。

圖6中在每個(gè)樣本點(diǎn)給出對(duì)應(yīng)的圖像，可以看出：沿著縱軸的方向由上到下，圖像的亮度逐漸增加，同時(shí)，拍攝的角度從仰視逐漸轉(zhuǎn)為俯視；沿著橫軸方向從左到右，雕塑姿態(tài)從右偏逐漸轉(zhuǎn)向左偏。這兩個(gè)維度很好地體現(xiàn)了光照和姿態(tài)的連續(xù)變化，嵌入結(jié)果表明ISLTSA算法可以找到影響真實(shí)圖像集分布的內(nèi)在參數(shù)。

圖6 人臉圖像數(shù)據(jù)集采用ISLTSA的二維嵌入結(jié)果

4 結(jié)語(yǔ)

由于缺乏高維空間到低維空間的顯式映射，增量學(xué)習(xí)成為經(jīng)典流形學(xué)習(xí)方法走向?qū)嵱没仨毥鉀Q的瓶頸問(wèn)題。本文研究了局部切空間排列的增量學(xué)習(xí)方法，引入向量到子空間的距離用于度量新的數(shù)據(jù)點(diǎn)與已有學(xué)習(xí)結(jié)果的關(guān)系，提出了基于劃分的局部切空間排列增量學(xué)習(xí)算法ISLTSA。在人工數(shù)據(jù)集和真實(shí)圖像數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，使用ISLTSA算法得到的低維流形能夠保持?jǐn)?shù)據(jù)集局部幾何特性，并體現(xiàn)出數(shù)據(jù)集分布參數(shù)的變化，是一種有效的增量學(xué)習(xí)方法。

另外，在人工數(shù)據(jù)集的降維實(shí)驗(yàn)中也發(fā)現(xiàn)了新的問(wèn)題，即當(dāng)新的數(shù)據(jù)點(diǎn)增多時(shí)，如N=1000時(shí)，在二維空間展開(kāi)的數(shù)據(jù)集的邊緣部分出現(xiàn)了收縮和折疊的現(xiàn)象。可能的原因是，在數(shù)據(jù)較少、分布稀疏時(shí)構(gòu)建的局部最大線性片存在虛假連接，隨著數(shù)據(jù)的增多，錯(cuò)誤的局部線性片的影響越來(lái)越明顯。因此，應(yīng)當(dāng)采取一定的策略增加或刪除局部最大線性片，實(shí)現(xiàn)自學(xué)習(xí)。這將是筆者后續(xù)研究?jī)?nèi)容。