基于雙向稀疏的多視圖子空間學習算法

楊 凡 饒雨泰

(湖北廣播電視大學軟件工程學院 湖北 武漢 430074)

0 引 言

隨著多視點數據采集技術的不斷完善,多視點學習已成為一個研究熱點,如何處理多樣化和復雜的數據是多視圖學習中一個具有挑戰性的問題[1-2]。

不同類型的視覺描述可以代表不同的特征,這種對同一對象通過不同方法或不同層次獲得的數據稱為多視圖數據現實世界數據具有高維、復雜和冗余的特點[3]。因此,對多視圖數據的內在結構進行分析是非常困難的。由于在許多情況下數據的標簽難以獲取,為了解決這一問題,提出一系列無監督多視圖學習方法。主要分為兩類:(1) 基于圖的多視圖學習:這類方法的目的是利用所有視圖學習一個融合圖,然后在融合圖上使用特殊聚類等有效算法得到結果[4-5];(2) 基于共享子空間的多視圖學習,即基于所有視圖共享一個共同表示的假設,這類方法旨在學習所有視圖的統一特征表示[6-7]。為了進一步提升傳統的無監督學習方法的性能,研究如何處理異常值成為了無監督學習的難點之一。為了減少數據中異常值的影響,提高多視圖方法的魯棒性。主要包括兩種方法:(1) 基于稀疏范數的魯棒多視圖學習。例如,Pu等[8]采用L1范數代替L2范數,提高了模型的魯棒性。(2) 基于低秩稀疏分解的魯棒多視圖學習。例如,洪敏等[9]提出一種魯棒的學習方案來去除錯誤和噪聲,并學習可靠的低階表示。傳統的多視圖方法很難選擇一個合適的統一表示維數,許多方法使得統一表示的維數與簇的個數相同。但是,如果多視圖數據是高維的,且簇數較少,那么采用上述方案可能會丟失太多的信息。如果選擇大維數的特征提取,可能無法完全去除冗余特征。因此,如何選擇合適的特征維數也是多視圖學習的難點之一。

為了有效解決傳統的多視圖子空間學習方法不能同時找到有效的子空間維數和處理孤立點問題,提出一種基于雙向稀疏性的多視點子空間學習方法。通過多個數據集驗證了本文方法的有效性。

1 基于雙向稀疏的多視圖子空間學習

1.1 建立模型

假設現在有V個視圖。令χ={X(1),X(2),…,X(V)}表示所有視圖的數據。X(v)∈Rdv×n代表第v個視圖的數據矩陣,在傳統的矩陣分解中,可以找到兩組矩陣因子U(v)∈Rdv×rv和L(v)∈Rrv×n來近似每個視圖,U(v)∈Rdv×r代表第v個視圖的投影矩陣,dv表示第v個視圖的維數,n表示數據大小,r代表特征提取的維數,V代表視圖數。

R(v)≈U(v)L(v)

(1)

可以將L(v)視為X(v)的一個潛在低維表示。由于不同視圖之間存在相關性,該方法不適用于多視圖問題。為了解決這個問題,假設多視圖數據的不同特征來自相同的潛在空間,即低維表示。當將不同的數據映射到一個共享的、低維的和潛在的空間時,便可以得到一個緊湊的數據分布,揭示不同視圖之間的統計關系和基本結構。因此,對于所有視圖,存在:

X(v)≈U(v)L

(2)

式中:L∈Rr×n。然后,可以使用共享的低維表示來解決多視圖問題。其中一個常見的重構過程可以表述為一個Frobenius范數優化問題,其定義如下:

(3)

盡管上述方法可以得到良好的多視圖數據的低維表示,但它僅考慮多視圖數據具有共享空間,而忽略了共享子空間本身的固有結構。另外即使已經將多視圖數據降到低維,低維表示也可能存在冗余特征或相關特征。因此,固有表示應該是用于特征提取的行稀疏矩陣。此外,實際數據并非都是理想的,可能存在一些異常值。因此,固有表示應為樣本的列稀疏矩陣。但是固有的低維表示不是一個具有稀疏行和稀疏列的矩陣。因為如果是這樣,則低維表示也會優化異常值。考慮到以上幾點,將低維表示分為兩部分:第一部分是用于優化特征的行稀疏矩陣,第二部分是用于優化樣本的列稀疏矩陣。目標函數可以表述為:

(4)

式中:P、Q∈Rr×n代表公共表示矩陣,P是行稀疏矩陣,Q是列稀疏矩陣。由于P是一個行稀疏矩陣,然后通過應用正則化,可以將其表示為:

(5)

考慮到這是一個NP難題,很難解決,決定把它放寬為:

(6)

式中:p∈(0,1)表示稀疏性。那么本文方法的目標函數可以表示為:

(7)

由于P和Q在公式中具有相似的狀態,因此設λ=β1=β2。考慮到不同的視圖應該在問題中扮演不同的角色,使用參數來平衡不同視圖的有效性。在數學上,目標函數是:

(8)

式中:γ是一個平滑因子,并將其設置為1。最后,在目標函數上添加U(v)的Frobenius范數,以避免出現病態問題并減少變量的自由度。所以本文方法的最終目標函數是:

(9)

1.2 優化算法

從式(9)可以看到需要求解四組變量。U(v)是所有視圖X(v)的投影矩陣。P和Q是所有視圖的統一表示。α是包含平衡不同視圖重要性的權重系數。但由于公式中所有變量都是耦合的,直接求解式(9)比較困難。因此,提供了一種有效的變量交替更新算法,即固定了三組變量,只對剩下的一組變量進行了交替優化。

(1) 固定P、Q和α,優化U(v)。當P、Q和α固定時,需要優化一組投影矩陣U(v)。顯然,目標函數中的第二項和第三項與U(v)不相關。然后,優化子問題變為:

(10)

上述規劃問題是凸的,并且可導,因此可以通過其導數得到封閉形式的解,即:

(11)

將導數設置為零,可以得到:

(12)

(13)

(14)

式中:D∈Rr×r是一個對角矩陣,第i個對角元素為:

(15)

因此,可以通過迭代地解決以下問題來解決式(13)。

(16)

新問題是凸的,可以得到它的封閉形式的解。

(17)

(18)

與P相似,式(18)可以通過迭代解決以下問題來解決。

(19)

其中S與D相似,S∈Rn×n,且:

(20)

式(19)是一個西爾維斯特方程,難以用封閉形式求解。因此,采用梯度下降法對其進行求解。假設已經完成了第k次迭代。那么第(k+1)次迭代是:

(21)

(22)

式中:tk是迭代步長,并通過精確線性搜索方法進行固定。即:

(23)

(24)

(25)

可以對α(v)取導數并將其設置為零。

(26)

然后可以得到α(v)如下:

(27)

由于h(v)≥0且c<0,因此α(v)的導出結果滿足其非負性條件。算法1中列出了本文方法的過程。

算法1本文算法

輸入:數據矩陣X(v)∈Rdv×n,參數λ1,p,λ2,c。

輸出:稀疏矩陣P,Q∈Rr×n。

循環:

2.利用式(12)更新投影矩陣U(v);

3.利用式(17)更新行稀疏公共矩陣P;

4.利用式(21)更新列稀疏公共矩陣Q;

5.利用式(27)更新權值系數α(v);

6.直到收斂, 算法結束。

2 算法分析

2.1 收斂性分析

引理1假設a、b是非零向量,那么對于任何p∈(0,2],有:

(28)

φ′(t)=ptp-1-pt=pt(tp-2-1)

(29)

分析式(29)。對于任何p∈(0,2],如果t∈(0,1],φ′(t)≥0且如果t>1,φ′(t)<0。所以t=1是最大值點。可以發現,當t=1時,φ(t)=0。即當t>0時,φ(t)≤0始終成立。

(30)

等價于以下不等式:

(31)

引理2通過引理1,可以證明由式(16)獲得的最優解也是使式(13)不增加的解。

F(P*)+λtr((P*)TDP*)≤F(P)+λtr((P)TDP)

(32)

(33)

通過引理1,可以得到:

(34)

將式(34)代入式(33),結果得到:

(35)

等價于:

(36)

定理1通過采用算法1中的優化程序,式(9)中SLBS的目標函數值不會增加。

證明:設

(37)

(38)

(39)

然后,由于更新的α(v)分別是式(25)中問題的最優解,因此以下不等式成立。

(40)

結合以上結論,可以得到結果。

2.2 計算復雜度

由于SLBS是以一種替代的方式解決的,因此可以對每個子步驟的計算復雜度求和,以計算它們的總計算復雜度。每個子步驟的計算復雜度如下:

2.3 參數確定

參數是模型的重要部分,參數的確定與模型的性能密切相關。有許多參數需要在式(9)中確定。但是可以將它們分為兩部分。其中一部分是優化變量,例如P、Q、α和U(v),它們需要在每次迭代中進行優化。另一部分是需要在SLBS迭代之前確定的超參數,例如λ1、λ2、p和c。

由于每個超參數都有其獨特的影響,因此可以根據先前的研究憑經驗確定一些超參數。對于所提出的模型,將列出每個超參數如何確定。對于p,它是為了保證P和Q的稀疏性而設計的。最佳稀疏近似為p=0,但這是一個NP難題,難以解決。大多數論文將p設為1,因為它是最佳凸逼近。這里設置p=1/2而不是p=1,以獲得更精確的稀疏近似p=0。至于c,它是用來衡量視圖的重要性的。不同的c可以改變視圖的權重。

對于參數λ1和λ2,由于它們被用來平衡損失函數、稀疏表示和正則化因子的重要性,因此對于最終性能非常重要。由于沒有關于這些參數的先驗信息,因此在[10-5,10]中進行了試湊驗證。

3 實驗與結果分析

3.1 數據集描述

選擇6個具有不同特征的標準數據集來評估本文方法的有效性。在許多實際應用中,通常使用6個多視圖數據集。

(1) MSRC_v1數據集由240幅圖像組成,分為8類。根據文獻[10],選取了由人臉、樹木、飛機、建筑、自行車、奶牛、汽車組成的7個類別,每個類別有30幅圖像。為了區分所有場景,提取了256個局部二值模式(LBP)、48個顏色矩(CMT)、1 302個中心點、100個方向梯度直方圖(HOG)、512個GIST和200個SIFT特征。

(2) Handwritten numerals(HW)數據集由0～9個10位數類的2 000個數據點組成,每個類有200個數據點。6個特征可用于聚類:47個Zernike矩(ZER)、240個像素在2×3窗口中的平均值(PIX)、64個Karhunen-love系數(KAR)、216個輪廓相關性(FAC)、76個字符形狀的傅里葉系數(FOU)和6個形態學(MOR)特征。

(3) Caltech_7數據集包含8 677幅圖片,屬于101個類別。根據文獻[11],選擇了最常用的7類,即人臉、多拉比爾、史努比、溫莎椅、摩托車、加菲貓和停車標志。對數據進行采樣并選取了441幅圖片作為Caltech_7,并提取了相同的視覺特征:LBP、HOG、GIST、CMT、CENTRIST和SIFT。

(4) Scene15由4 485幅圖像組成,這些圖像屬于15個類別:高速公路、城市內部、高層建筑、街道、郊區住宅、森林、海岸、山脈、野外、臥室、廚房、客廳、辦公室、工業和商店,提取了6個視覺特征:SIFT、SURF、PHOG、LBP、GIST和小波紋理(WT)。

(5) MvYale包含了15位志愿者的165幅圖片,每個人都有15幅圖片。該數據集是一個灰度數據集,主要包括光照、面部表情和姿勢的變化。為了有效地分析數據,提取了5種視覺特征:SIFT、HOG、LBP、WT和GIST。

(6) KSA包括4個受試者,他們執行5個動作。在這里,每個動作都被視為一個類。從每個動作中選擇2 000個視頻幀,形成10 000個示例的子集。這里使用了4個姿勢特征,即文獻[12]中提取的fJJ_d、fJL_d、fLL_a和fPP_a。

在6個數據集中,本文方法的4個需要提前確定的超參數如表1所示。

表1 各個數據集的超參數選擇

3.2 實驗對比

由于本文關注的是無監督學習,因此將SLBS與一些可預期的方法進行了比較,并使用K-means聚類方法來評估本文方法的有效性。比較方法如下。

(1) 最佳單視圖(BSV):在每個單一視圖上使用SLBS,并在低維表示上使用K-means來獲得聚類結果。

(2) 組結構稀疏矩陣分解(GSSMF):在文獻[13]中提出的一種通過結構稀疏來學習將潛在空間分解成維度的方法。

(3) 多視圖光譜嵌入(MSE):在文獻[14]中提出的一種多視圖圖學習方法。

(4) 多視圖非負矩陣分解(MVNMF):在文獻[15]中提出的一種基于NMF的多視圖聚類方法。

(5) 自動加權多圖學習(AMGL):在文獻[16]中提出的另一種多視圖圖學習方法。

(6) 大規模多視圖子空間聚類(LMVSC):在文獻[17]中提出了一種具有線性時間的新穎的多視圖子空間學習方法。

對于實驗結果,采用兩種不同的度量來評估所提出的SLBS聚類方法的性能,即聚類準確度(ACC)和標準化互信息(NMI)。

所有實驗都是在配置為64位Intel Core i7-6700CPU@3.4 GHz/16 GB RAM計算機上的MATLAB2016A上進行的。

3.3 SLBS與其他算法之間的比較

表2和表3分別給出了不同特征提取維度下所有比較方法的NMI和ACC結果。就聚類結果而言,有以下觀察結果:

表2 不同方法對6個不同子空間維數數據集的ACC

表3 不同方法對6個不同子空間維數數據集的NMI

與度量標準ACC的其他特征提取方法相比,SLBS在大多數情況下在大多數數據集上表現最佳。特別是在Scene15數據集上,SLBS比其他方法的最佳ACC高出近0.1,在大多數數據集中超過其他方法的平均ACC 0.05以上。對于另一個度量指標NMI,可以得到類似的結論。實驗結果表明了本文方法的有效性。

至于最佳單視圖方法(BSV)與以前的多視圖方法的比較,后者并不總是表現得更好。這可能是由于以前的方法分別表征每個視圖數據的結構并通過簡單的加法運算將它們組合在一起所引起的。但是與加權多視圖方法相比,最佳單視圖方法有時也會有更好的性能。這可能是由于統一子空間的雙向稀疏性所導致的。

基于圖的多視圖特征選擇方法在所選特征維數與數據類別數目相同的情況下表現得非常好。還將本文方法與基于圖的方法進行了比較,發現本文方法在大多數情況下都優于它們的最佳結果。這有效地證明了本文算法的有效性。

通過對基于矩陣分解方法的ACC和NMI的分析,可以得出ACC和NMI隨著維數的增加先增大后減小。由于隨著維數的增加,學習的子空間首先更接近于本征維數,并且當子空間的維數大于本征維數時,就會出現冗余特征。但是本文方法在大多數數據集中也能很好地處理高維數據。這表明了雙向稀疏性在SLBS中的有效性。

3.4 收斂效果

在圖1中繪制了MSRC_v1、Caltech_7和HW數據集的迭代收斂曲線,以驗證算法SLBS的收斂性。通過對迭代收斂曲線的分析,本文算法在迭代過程中是非遞增的,并逐漸收斂到一個確定的值。此外,本文算法在約10次迭代中收斂良好,因此收斂速度快是本文方法的優勢。

圖1 具有不同迭代次數的SLBS的目標值

3.5 計算時間和參數影響

為了考察本文方法在計算時間上的效率,在表5中比較了具有不同數據和特征尺度的6個數據集的運行時間。由于所有方法都需要使用K-means算法進行聚類,并且關注的焦點是學習子空間的過程,因此沒有報告聚類算法的計算時間。

在表4中,比較了SLBS和其他方法對于數據大小n的時間復雜度。從表5中,可以發現本文方法在6個數據集上花費的時間最少。討論了該實驗結果的根本原因。(1) 基于圖的方法的計算時間受數據數量n的影響最大,因為它需要分解n維數據矩陣,并且計算復雜度為O(n3)。對于相同的情況,本文方法僅具有線性復雜度。因此,隨著數據大小的增加,本文方法要比基于圖的方法快得多。(2) 盡管MVNMF、GSSMF和LMVSC的計算復雜度與本文方法相同,但是本文方法仍然比它們快。通過分析,發現本文方法具有更快的收斂速度。例如,在MSRC_v1上,本文方法需要進行35次迭代,而MVNMF和GSSMF需要進行50次以上迭代。

表4 關于所有方法的數據大小n的計算復雜度

表5 6個數據集的平均運行時間比較 單位:s

對于超參數確定問題,在MSRC_v1和Caltech_7這兩個數據集上設計了實驗。由于仍然需要確定3個參數,因此在一個數據集上執行了3個實驗,它們的差為c的值。這里從{-1,-2,-3}改變參數c。當參數c固定時,從{0.1,0.2,0.3,0.4,0.5}改變λ1,從{2,4,6,8,10}改變λ2。將所研究的子空間維數設為10,選取ACC作為評價指標。結果如圖2所示。顯示不同的參數會導致不同的結果,這表明了參數選擇的重要性。可以發現,當參數c等于-1時,兩組結果都很好。可能是由于較大的c表示更關注不同視圖的多樣性。此外,兩個數據集的最優解具有不同的λ1和λ2,因為這兩個數據集具有不同的數據特征。

圖2 不同參數c對λ1和λ2的敏感性分析

3.6 可視化和魯棒性分析

在圖3中給出行稀疏矩陣P和列稀疏矩陣Q的可視化。可以看到P的行和具有幾個小值,而Q的列和具有幾個大值。這是合理的,因為第一次降維后的大部分特征都是有用的,并且數據集中沒有太多的異常值。實驗結果表明了本文算法的有效性。

圖3 兩個數據集中的行稀疏矩陣P和列稀疏矩陣Q的可視化

為了分析模型的魯棒性,在兩個數據集上將SLBS與兩種稱為RMSC和RRMA的魯棒多視圖子空間學習方法進行了比較。設計了3種錯誤數據比率,分別為0、10%和20%。即在原始的數據集中隨機替換10%以及20%的相同風景圖片,該圖片不包含數據集中任何一個類別,從而保證錯誤數據集的公平性,以保證實驗的可對比性。如果錯誤數據集被聚類為其中某一類別,則認定該聚類錯誤。進一步利用3種方法進行聚類分析,結果如圖4所示,隨著錯誤數據數量的增加,3種方法的性能趨于降低,但是與RMSC和RRMA相比,SLBS始終表現最佳。這充分表明了本文算法的魯棒性。

圖4 在兩個數據集中具有不同錯誤示例比率的魯棒性分析

4 結 語

傳統的多視圖子空間學習方法很難找到一個有效的子空間維數并同時處理異常值,故提出一種基于雙向稀疏的多視圖子空間學習方法。通過多個數據及驗證得出如下結論:

(1) 本文方法更加有效地解決子空間維數問題,從而高效處理高維數據,這表明了雙向稀疏性在SLBS中的有效性。

(2) 相對于傳統方法,本文方法對異常值具有較強的魯棒性。

(3) 相對于其他傳統方法,本文方法具備較好的收斂性,且收斂速度較快,整體計算效率較高,精度也具備優勢。