古楠楠
(首都經濟貿易大學 統計學院,北京 100070)
在計算機視覺、醫學數據處理、多媒體信息處理等領域通常面臨很多高維數據,傳統數據分析處理方法往往會遭遇維數災難。降維是數據建模與數據挖掘的基本問題,根本任務是將樣本從高維表示空間通過線性或非線性方法投影到低維本質特征空間,從而得到原高維數據的本質低維表示[1-3]。降維有利于節省數據的存儲空間,在降低后續數據分析的時間代價的同時提升數據分析性能。從是否使用數據類別標簽的角度可將降維方法分為無監督降維[4-6]、有監督降維[7-9]以及半監督降維[10-12]3 類。半監督降維同時利用少量有標簽數據與大量無標簽數據中蘊含的信息進行降維,在保持數據本質結構的同時提高所獲低維表示的可分性與判別性。
基于圖的半監督降維方法是一類重要且有效的半監督降維方法[10-12],已經獲得了成功應用,但仍有一些尚未解決的問題,例如標簽噪聲問題。數據標記通常是一項乏味且主觀的任務,費時費力,有時還需要專業知識背景,有些復雜數據還可能會因為具有較大的類內類間變化而增加標記難度,這些情況都會導致出現部分數據標記錯誤。事實上,標簽噪聲問題在實際應用中非常普遍,例如對于ImageNet等大規模圖像數據集可能需要眾包工人手工標注,由于知識受限或工作乏味,眾包員工無法完全準確地注釋特定任務,由此帶來標簽噪聲[13]。當前已有一些針對噪聲標簽的研究[14],但在半監督降維領域,很少有專門針對具有標簽噪聲的數據進行處理的研究。當面對部分錯誤標記的訓練數據時,半監督降維算法的性能可能會受到較大的影響,從而導致錯誤的模型預測或決策。
自步學習(Self-Paced Learning,SPL)[15]模仿人類由簡單到復雜的學習方式,最開始利用簡單樣本訓練模型以獲取簡單可靠的知識,然后反復地更新樣本的簡單度,以一種自步的方式逐漸將越來越多的從簡單到復雜的樣本納入訓練來學習更復雜與更專業的知識,實現對復雜事物的認知。自步學習能深層挖掘數據本質結構信息,對非凸優化問題可以避免局部最小值,提升算法性能,且對帶噪聲或奇異點的數據具有良好的魯棒性[16]。
本文將自步學習機制融入用于降維的流形正則化框架[17-18],提出一個新的對標簽噪聲魯棒的自步半監督降維(Self-Paced Semi-Supervised Dimensionality Reduction,SPSSDR)框架。在該框架下,設計SPSSDR 算法,基于交替優化策略,在更新降維映射函數和計算樣本重要度兩個步驟之間進行迭代。在計算降維映射函數時,基于流形正則化框架,考慮低維有標簽數據的加權類內分散程度、降維映射的函數復雜度以及降維映射關于數據稀疏結構的光滑度。在計算樣本重要度時,基于自步學習機制,計算有標簽數據的低維表示與其所在類的錨點之間的距離,根據該距離進行樣本重要度賦值。
基于圖的半監督降維方法通常先根據訓練樣本間的某種相似性度量建立一個或多個數據結構圖,再在有標簽數據的監督信息與結構圖中隱藏的數據分布信息的協同指導下,獲得數據的低維表示或高維空間到低維空間的特征映射。
SONG 等[19]提出半監督線性判別分析(Semi-Supervised Linear Discriminant Analysis,SSLDA)方法與半監督最大間距準則(Semi-Supervised Maximum Margin Criterion,SSMMC),它們在低維特征空間中最大化類間散度且最小化類內散度,同時保持數據結構圖中隱藏的本質流形結構信息,以此獲得降維映射函數。NIE 等[10]提出靈活的流形嵌入(Flexible Manifold Embedding,FME)方法,可以同時求出訓練數據的預測標簽、將數據映射到標簽的線性回歸函數以及兩者之間的回歸殘差。NIE 等[11]提出基于圖優化的半監督映射(Semisupervised Projection with Graph Optimization,SPGO)方法,該方法依據給定的高維數據的鄰接矩陣、低維數據間的關系以及類別標簽關于圖拉普拉斯的光滑性,同時獲得數據結構圖與降維映射。WANG 等[12]針對半監督降維問題,提出一種基于結構圖學習的標簽傳播(Label Propagation with Structured Graph Learning,LPSGL)方法,該方法同時執行標簽傳播、半監督結構圖學習與降維,對有標簽樣本賦予不同的重要度來區分它們在降維映射學習中的不同影響。
受人類和動物學習原理的啟發,KUMAR 等[15]提出自步學習。自步學習引入自步參數(相當于人類的學習年齡)來控制學習的步調,從簡單樣本開始,不斷增大自步參數(即增大學習年齡),使越來越多的從簡單到復雜的樣本被自動納入模型進行訓練,從而得到越來越成熟的模型。MENG 等[16]將SPL 問題歸納為如下的優化問題:
其 中:f:RD→R 是二分 類問題 的判別函數;L(zi,f(xi))為度量訓練數據xi(i=1,2,???,m)的真實標簽zi和預測標簽之間差異的損失函數;vi為反映訓練數據xi重要度的權重;g(vi,λ)為決定學習機制的自步函數;λ是控制模型學習步調的自步參數。
目前,研究者們[20-22]已經提出了一系列自步學習方法,且已將自步學習成功應用于人臉[23]、臨床疾病[24]、動作[25]等識別任務,自步學習機制對于實際應用中的復雜數據具有優越的處理能力,且對于有噪聲或奇異點的數據具有良好的魯棒性。
對于半監督降維問題,設訓練數據集為{(xi,zi),xm+u,i=1,2,???,m,u=1,2,???,n-m},m為有標簽數據的個數,n為樣本總數,xi?RD(i=1,2,???,n)為高維訓 練數據,D為高維 數據的維數,X=[x1,x2,???,xm,???,xn]?RD×n為高維的訓練數據矩陣,zi?{1,2,…,C}為xi的類別標簽,C為數據的類別總數。設d為低維空間的維數,yi?Rd(i=1,2,…,n)為xi的低維表示,Y=[y1,y2,???,ym,???,yn]?Rd×n為低維的數據矩陣。設高維空間到低維空間的降維映射函數為f=[f1,f2,…,fd]T:RD→Rd,則yi=f(xi)。向 量ai=[ai1,ai2,???,ain]T?Rn的L2 范數定義為為簡便起見,將L2 范數用‖ ? ‖表示,向量ai?Rn的L1 范數定義為向量ai?Rn的L0 范數定義為ai的非零元素的個數。
針對標簽噪聲魯棒的自步半監督降維框架表示如下:
其中:優化變量f=[f1,f2,…,fd]T:RD→Rd為高維空間到低維空間的降維映射函數;優化變量v=[v1,v2,…,vm]?Rm是反映有標簽數據重要度的權重向量;γK和γI是兩個正則化參數。
目標函數的第1 項為有標簽數據的加權擬合損失項,度量了先驗的指導信息yzi與通過降維映射所得的低維表示f(xi)之間的差異。L(?,?)是損失函數,如平方損失、Hinge 損失等。yj(j=1,2,…,C)為第j類數據的錨點,是利用某種方法預先得到并指派給第j類數據的先驗低維表示指導信息。例如可以利用某種降維方法對數據進行預降維,計算每類低維數據的均值,將其作為該類的錨點。對于第j類有標簽數據,使其低維表示集中在錨點yj附近。通過該方式,使降維后的同類數據盡可能靠近,異類數據盡可能分散,從而保留豐富的判別信息,使投影后的低維數據具有較大的可分性。
目標函數的第2 項為復雜度正則化項,度量了降維函數f在周圍空間中的函數復雜度[17-18]。例如:若限制f屬于某個再生核希爾伯特空間HK,則可以將‖f‖K定義為f在HK中的范數;若f是線性映射函數,即f(x)=WTx,則可以將‖f‖K定義為系數矩陣W的Frobenius 范數或L1 范數。
目標函數的第3 項為結構化信息正則化項,度量了降維函數f保持數據的結構化信息的能力。對訓練數據構造結構化數據圖,首先刻畫數據間的結構化關系,例如可以構造刻畫數據局部結構信息的K-近鄰圖,或者構造刻畫數據全局結構信息的稀疏圖[26]、低秩圖[27]等,然后可以度量f在數據圖上的光滑度,以此刻畫f保持數據的結構化信息的能力。
目標函數的第4 項為自步學習正則化項,g(vi,λ)為決定學習機制的自步函數,λ是控制模型學習步調的自步參數。自步函數決定了模型學習新樣本的模式,MENG 等[16]給出了自步函數的具體定義,研究者們也提出了不同的自步函數,如硬自步函數、軟自步函數、混合自步函數等[15-16]。不同的學習場景與學習任務需要使用不同的自步學習機制,從而需要不同的自步函數。
在優化問題式(2)的約束項中的Ψi代表對有標簽樣本xi預先設定的課程,可以被視為一種先驗知識。它是對有標簽訓練樣本的權重的約束,模型在該約束下,反復調整有標簽樣本的權重,逐步從簡單樣本學習到復雜樣本,得到一個成熟的模型。課程設計可以與先驗、自步函數及特定任務相關,不同的樣本也可以具有不同的課程。
在所提的降維框架下,提出一種針對標簽噪聲魯棒的自步半監督降維算法。
對于優化問題式(2)的目標函數的第1 項,即損失項,選用平方損失來度量數據的低維表示與其所在類的錨點之間的距離,如式(3)所示:
對于C類數據的錨點,利用局部保持投影(Locally Preserving Projections,LPP)[28]方法給 定。LPP 是一種經典的無監督線性降維方法,主要思想是將高維空間中鄰近的點映射為低維空間中鄰近的點。對于訓練數據{x1,x2,…,xn},利用LPP 進行降維,得到低維表示然后對于每一類的錨點yj(j=1,2,…,C),將其設置為該類中的有標簽數據的低維表示的均值,如式(4)所示:
其中:mj為屬于第j類的有標簽數據的個數。
對于優化問題式(2)的目標函數的第2 項,即復雜度正則化項,將‖f‖K定義為f在再生核希爾伯特空間HK中的范數。由于給定一個半正定的核函數K(?,?),會生成一個對應的再生核希爾伯特空間HK,因此假設fs?HK(s=1,2,…,d),則函數f=[f1,f2,…,fd]T在HK中的范數的平方如式(5)所示,可以度量f在再生核希爾伯特空間中的復雜度。
對于優化問題式(2)的目標函數的第3 項,即結構化信息正則化項,利用f在結構化稀疏圖上的光滑度來定義。數據xi的稀疏表示是指將xi用一個過完備字典中的一小部分元素的線性組合來表示。特別地,將訓練數據作為字典,則xi的稀疏表示可通過如下的魯棒L1 范數最小化問題來求解:
其 中:ai=[ai1,ai2,???,ai,i-1,0,ai,i+1,???,ain]T?Rn為xi的稀疏表示系數向量;ei為考慮噪聲或奇異點所設置的誤差項。
然后構建結構化稀疏圖[26],圖的頂點集為訓練數據集{x1,x2,???,xm,???,xn},由xj指向xi的邊的權重為aij。已有理 論[29]證 明:xi的稀疏 表示系 數ai中 的非零元素自動對應xi同類的點,因此數據的稀疏圖具有較強的判別性,有利于數據分類。為了使低維數據也具有同樣的稀疏表示關系,可以將定義為f在稀疏圖上的光滑度,以此來度量f保持數據稀疏表示結構的能力,如式(7)所示:
對于優化問題式(2)的目標函數的第4 項,即自步正則化項,將自步函數定義為硬自步函數[如式(8)所示],并將優化問題式(2)的約束項中的課程定義為Ψ[i如式(9)所示]。
在這樣的設置下,所得的有標簽數據的重要度為0 或1。當數據的類別標簽錯誤時,自步學習機制會將數據的重要度賦值為0,這樣就能消除錯誤類別標簽造成的影響。當數據的類別標簽正確時,自步學習機制會將數據的重要度賦值為1,此時能夠充分利用數據類別標簽中蘊含的判別信息,提升所得低維表示的判別性,有利于數據分類。
綜上所述,在降維框架下,本文所提的針對標簽噪聲魯棒的自步半監督降維算法可以表示如下:
對于自步半監督降維問題式(10),利用交替優化策略(Alternative Optimization Strategy,AOS)[15,30]進行求解。該方法將優化變量劃分為k個互不相交的塊,然后在迭代過程中交替優化每一個塊中的變量。對于式(10),將變量分為兩個互不相交的塊:降維映射f與樣本重要度v,并對它們進行交替求解。具體求解過程如下:
1)固定樣本重要度v,優化降維映射f。此時式(10)轉化為式(11):
定理1問題式(11)的最優解具有如下形式:
其中:bi=[b1i,b2i,???,bdi]T?Rd。
證明定理1 證明與文獻[18]中定理2 的證明類似,因此不再詳述。
設K=(K(xi,xj))?Rn×n為核矩 陣,B=[b1,b2,…,bn]?Rd×n為核函 數的系 數矩陣,A=[a1,a2,???,an]T=(aij) ?Rn×n為稀疏表示系數矩陣,tr(?)為矩陣的跡,V?Rn×n為第i(i=1,2,???,m)個對角元素是vi、其余元素是0 的對角矩陣,I為n階單位矩陣,YAnchor=為訓練數據對應的類錨點矩陣。在式(12)的最優解表示形式下,問題式(11)可轉化為關于矩陣B的優化問題:
令目標函數對B的偏導等于0,可得:
2)固定降維映射f,優化樣本重要度v。此時式(10)轉化為式(16):
該問題對于vi(i=1,2,???,m)是可分離的,因此考慮如下的子優化問題:
推導得出該問題的最優解:
從式(18)可以看出,若有標簽樣本xi的低維表示與其對應類錨點之間的距離平方大于等于當前的年齡參數λ,意味著樣本的類別標簽可能是錯誤的或者樣本是復雜難以學習的,則令其重要度。在下次迭代求降維映射f時:式(10)的目標函數的第1 項中的系數,意味著不考慮xi的類別標簽zi;式(10)的目標函數的第3 項不受影響,意味著仍然考慮樣本xi所刻畫的數據結構信息。通過該方式,樣本的錯誤標簽會被過濾,只考慮正確的類別標簽所提供的判別信息,同時無論具有正確標簽還是錯誤標簽的樣本,都考慮其所刻畫的數據稀疏結構信息。因此,所提算法對標簽噪聲具有較好的魯棒性。
算法1針對標簽噪聲魯棒的自步半監督降維算法
算法1 展示了本文所提的對標簽噪聲魯棒的自步半監督降維算法。在該算法中,第1 和2 行是利用LPP 算法計算類錨點;第3 行是重要度的初始化;第4~8 行是利用交替優化策略求解自步半監督降維問題式(10),即對降維映射f與樣本重要度v,每次固定一個,優化另一個。按照該優化策略,自步半監督降維問題式(10)的目標函數單調遞減且具有下界,因此算法是收斂的。在算法最開始,自步參數λ被設定為一個很小的值,只考慮極少量的具有高可信度的樣本類別標簽。隨著迭代次數的增加,λ逐漸增大,根據模型所學習到的信息,考慮越來越多具有判別性的可靠樣本,而非可能具有誤導性的模糊樣本。通過該自步方式訓練一個越來越成熟的模型,最終得到一個對噪聲標簽具有良好魯棒性且具有較好判別性能的降維映射函數。
在公開的標準數據集上測試所提算法的性能,并與一些主流算法進行比較。實驗采用的編程軟件為MATLAB 2021b,操作系統為Windows 11,CPU為AMD Ryzen 7 5800H。
在半監督降維常用的5 個數據集上進行實驗:
1)YaleB 人臉數據集。該數據集中共有2 114 張圖像,是38 個人分別在不同的光照條件下拍攝的臉部正面圖像。每張圖像都被處理為32×32 像素的灰度圖并轉換為1 024 維的向量。
2)CBCL 人臉數據集。使用的數據集中包含人臉圖像和非人臉圖像各1 000 張。每張圖像都被處理為19×19 像素的灰度圖并轉換為361 維的向量。
3)ORL 人臉數據集。該數據集包含400 張人臉圖像,是40 個人在不同的時間,通過改變光照方向、面部表情與面部細節拍攝的。每張圖像都被處理為32×32 像素的灰度圖并轉換為1 024 維的向量。
4)USPS 手寫數字數據集。該數據集包括了手寫數字0 到9 的圖像,每類有1 100 張分辨率為16×16 像素的圖像并被轉換為256 維的向量。在實驗中,對于每個數字,隨機選取了10%的圖像進行實驗。
5)CANE-9 文本數據集。該數據集來源于UCI數據集,包含屬于9 個類別的共1 080 份文檔,來源于一個名為“國家經濟活動分類”表中的9 類巴西公司的自由文本業務描述。每個文檔都被表示為一個856 維的向量,其分量表示關鍵詞的權重,即該詞在文檔中出現的頻率。
對比算法共計10 種,包括本文所提的自步半監督降維算法、Baseline、LPP[28]、線性判別分析(Linear Discriminant Analysis,LDA)、SSLDA[19]、SSMMC[19]、FME[10]、SPGO_KNN[11]、SPGO_sparse[11]、LPSGL[12],其中,Baseline 是指不進行降維而直接使用原始數據的算法,LPP 是無監督降維算法,LDA 是有監督降維算法,其他算法均為半監督降維算法。SPGO_KNN與SPGO_sparse 分別代表使用K-近鄰圖與稀疏圖方法構造數據圖,然后在此圖上采用SPGO 進行半監督降維。與所提算法類似,LPSGL 也考慮了數據的重要度,但是從預先給定的候選集中選擇樣本的重要度。
對 于SSLDA、SSMMC、FME、SPGO_KNN 與SPGO_sparse 算法的 正則化參數,從{10-9,10-6,10-3,100,103,106,109}中進行選擇。對于LPSGL算法,按照文獻[12]所采取的策略,從{10-6,10-5,10-4,…,100,…,104,105,106} 中選擇參數α與λ,從{100,101,102,103,104}中選擇樣本的重要度值v。對于所提算法,采取文獻[18]所采取的策略,令并從{10-3,10-2,10-1,100}中選擇CCK與CCI。對于基于K-近鄰圖的算法,按照文獻[11-12]采取的策略,將鄰域尺寸取為10,并利用高斯核來計算邊的權重。
實驗步驟具體如下:首先,利用PCA 對數據進行預處理,保持98%的數據信息;之后,隨機選取占比為p的樣本,賦予其錯誤的類別標簽,即從其他C-1 個類中隨機選擇一個類別標簽賦予該樣本,利用五倍交叉驗證來選擇各算法的最優參數以及降維維數;隨后,隨機選擇80%的數據作為訓練數據,剩下的作為測試數據,在訓練數據中隨機選取30%的數據作為有標簽數據,剩下的數據作為無標簽數據,在訓練數據上構造模型并利用所得的降維映射,獲取無標簽訓練數據及測試數據的低維表示;最后,利用最近鄰分類器來度量各算法的判別性能,即在低維空間中利用有標簽訓練數據構造分類器,再分別在無標簽訓練數據及測試數據上進行最近鄰分類。
對于每個實驗數據集,將其隨機進行20 次劃分,得到不同的標簽訓練數據、無標簽訓練數據與測試數據,然后在每次劃分上進行降維與分類。
3.2.1 分類結果
首先,計算各數據集在20 次隨機劃分上的平均分類準確率與標準差。所得結果如表1~表5 所示,其中,U 表示無標簽訓練數據上的分類結果,T 表示測試數據上的分類結果,每行的最優分類結果用粗體表示,次優結果用下劃線表示(下同)。由表1~表5 可以看出,從平均分類準確率來看,所提算法具有最好的表現,尤其是對于有噪聲標簽的數據,在表1~表5 共計50 種情況中,只有在6 種情況下所提算法并非最優。

表1 YaleB 數據集上的分類準確率與標準差Table 1 Classification accuracy and standard deviation on the YaleB dataset %

表4 USPS 數據集上的分類準確率與標準差Table 4 Classification accuracy and standard deviation on the USPS dataset %

表5 CANE-9 數據集上的分類準確率與標準差Table 5 Classification accuracy and standard deviation on the CANE-9 dataset %
其次,計算各數據集在20 次隨機劃分上的平均Macro-F1 值,實驗結果如表6~表10 所示。具體而言,分別計算無標簽訓練數據與測試數據中每個類別的分類準確率與召回率,由此得到每個類別的F1 值,然后計算所有類別的F1 值的算術平均值,即為Macro-F1 值。由表6~表10 可以看出,從Macro-F1 值來看,所提算法具有最好的表現,在表6~表10 共計50 種情況中,只有在4 種情況下所提算法并非最優,具體為CANE-9 訓練與測試數據下噪聲標簽所占比率為0% 和10%,且在這4 種情況中,所提算法在3 種情況下為次優。

表6 YaleB 數據集上的Macro-F1 值Table 6 Macro-F1 values on the YaleB dataset

表7 CBCL 數據集上的Macro-F1 值Table 7 Macro-F1 values on the CBCL dataset

表8 ORL 數據集上的Macro-F1 值Table 8 Macro-F1 values on the ORL dataset

表9 USPS 數據集上的Macro-F1 值Table 9 Macro-F1 values on the USPS dataset

表10 CANE-9 數據集上的Macro-F1 值Table 10 Macro-F1 values on the CANE-9 dataset
從平均分類準確率與Macro-F1 值的結果可以看出,所提算法對標簽噪聲具有較好的魯棒性。例如:對于CANE-9 數據集,當p較小時所提算法并非最優,隨著p的增大,優勢逐漸明顯,成為最優算法;對于CBCL 數據集,在原始數據(p=0%)上所提算法比次優算法的分類準確率高0.4 個百分點(U)與0.5 個百分點(T),Macro-F1 值高0.004 5(U 和T);對于p=40%的噪聲數據,所提算法比次優算法的分類準確率高2.8 個百分點(U)與3.2 個百分點(T),Macro-F1值高0.027 0(U)與0.031 6(T),與原始數據集相比提升幅度更大。
3.2.2 統計檢驗
在3.2.1 節中,從平均分類準確率與Macro-F1 值的角度驗證了所提算法的有效性。為了進一步驗證該有效性的統計顯著性,將所提算法與其他算法的準確率進行成對T-檢驗。所得結果如表11~表15 所示,其中的數值表示該算法與所提算法的成對T-檢驗的P 值。由表11~表15 可以看出,在絕大多數情況下,T-檢驗的P 值小于0.01,說明從統計學意義來看,所提算法是具有顯著優勢的。

表11 YaleB 數據集上的T 檢驗的P 值Table 11 P-values of T-test on the YaleB dataset

表12 CBCL 數據集上的T 檢驗的P 值Table 12 P-values of T-test on the CBCL dataset

表13 ORL 數據集上的T 檢驗的P 值Table 13 P-values of T-test on the ORL dataset

表14 USPS 數據集上的T 檢驗的P 值Table 14 P-values of T-test on the USPS dataset

表15 CANE-9 數據集上的T 檢驗的P 值Table 15 P-values of T-test on the CANE-9 dataset
3.2.3 參數敏感性分析
在本節中,對正則化參數CCK、CCI進行敏感性分析。以CBCL 與USPS 數據集為例,噪聲標簽所占比率p設置為20%,然后改變CCK、CCI的取值,分別計算20 次隨機劃分的無標簽訓練數據及測試數據上的平均分類準確率,實驗結果如圖1 所示。由圖1 可以看出,當正則化參數CCK、CCI在較大范圍內變化時,所提算法都具有較好的效果。

圖1 在正則化參數的不同取值下所提算法的分類準確率Fig.1 Classification accuracy of the proposed algorithm under different values of regularization parameters
本文基于自步學習機制提出一個針對標簽噪聲魯棒的自步半監督降維框架,并在此框架下設計自步半監督降維算法。該算法利用自步學習機制,自適應計算有標簽樣本的重要度且不斷地進行更新,在此基礎上逐步學習從簡單到復雜的樣本,因此對于噪聲具有較好的魯棒性,且可以獲得具有非線性表達式的降維映射函數。然而,在所提算法中利用LPP 方法給定數據的類錨點,若類錨點設置錯誤則會影響后續的數據降維。另外,所提算法基于稀疏表示構建數據圖,該數據圖傾向于刻畫數據的全局結構信息,而忽視了局部信息。下一步將構建更合理有效的數據類錨點以及能夠更精確刻畫數據結構信息且更具判別性的數據圖。