非線性二維主成分分析方法

2022-01-23 07:28:08高宇夏志明劉歡

純粹數學與應用數學 2021年4期

高宇,夏志明,劉歡

(1.西北大學數學學院,陜西西安 710127;2.西安交通大學數學與統計學院,陜西西安 710049)

1 引言

隨著社會的快速發展和信息的加速流動,數據這一生產要素正在迅速擴大.自2012年以來,“大數據”一詞被越來越多地提及,各行各業產生的海量數據已經成為經濟社會的新石油.學術研究者及商業締造者通過對數據的共享和交叉互用,實現其學術及經濟價值的最大化.然而這些數據數量眾多,種類繁雜,因此如何以最小的成本對其進行傳輸和存儲是社會各大領域需要思考的問題.在這種背景下,“數據壓縮”再一次吸引了廣大研究者們的目光.它是指在有損或無損壓縮的前提下,刪減數據中包含的冗余信息,進而提高有效信息的占比,減少同等信息量下數據的存儲空間.早在19世紀,就有相關研究者做了大量工作,特別是在機器學習、計算機視覺和信息檢索領域[1-6].因此,用于“數據壓縮”的手段和工具有很多,但這些方法難易程度不一,其中有一類操作簡單且應用廣泛的方法是主成分分析類方法.這類方法的基本思想是在保證數據投影變異性最大的前提下,沿著特定方向將數據投影到一個低維空間中,而方差則作為度量投影變異性的指標,以此達到用較少空間存儲較多信息的目的.前輩們一直在該領域探索前進,這類方法也在逐漸發展完善.

主成分分析(Principal Component Analysis,PCA)是該類方法中最原始、最經典的一種.文獻[7]最先引入這一概念,隨后文獻[8]將這一情形推廣到隨機向量.其數據壓縮能力在文獻[9]中得以展示.簡單的結構及有效的壓縮能力使得主成分分析得到了眾多領域的普遍認可,其中值得一提的是其在計算機視覺領域做出的貢獻.在該領域,研究者們關注如何處理圖像,致力于挖掘PCA應用于人臉識別的潛能.在文獻[10-11]中,PCA首次被用于人臉識別.文獻[12]提出了著名的特征臉方法.自此,PCA在人臉識別領域引起了廣泛關注,并逐漸發展成為該領域最成功的方法之一.同樣被用于人臉識別的還有主成分分析的一些變種,包括獨立分量分析(Independent Component Analysis,ICA)和核主成分分析(kernel Principal Component Analysis)[13-15].尋找投影變異性最大的方向并沿著這些方向進行投影是PCA的核心目標,可以借助“K-L變換”或“Hotelling變換”構造一組標準正交的方向,而這組方向恰好是樣本協方差矩陣的特征向量,詳見文獻[16],文獻[17]詳述了張量數據的主成分分析方法.具體來說,對于給定的樣本X∈Rm,PCA往往被定義為Z=UX[18-19],其中U為正交投影矩陣,Z為投影后所得向量.

PCA是一種基于向量數據構造的壓縮方法,但在現實生活中很多數據以矩陣形式存在.將矩陣拉直為向量是一種普遍的做法,但不可否認的是,在拉直過程中原有數據結構會被割裂,這可能會導致結構中隱含信息的丟失.除此之外,拉直后向量維數的增加會導致“維數詛咒”(Curse of dimension).文獻[20]也曾表示PCA無法捕捉投影方向的不變性.針對PCA的這些局限,文獻[21]提出了一種基于矩陣數據建立的數據壓縮方法—二維主成分分析(Two-dimensional PCA,2DPCA).該方法在投影前無需將矩陣轉化為向量,從而規避了矩陣向量化導致的信息損失及“維數詛咒”.與PCA類似,對于給定的樣本A∈Rm×n,2DPCA被表示為Z2D=AU2D,其中U2D為投影矩陣,Z2D為投影后所得矩陣.

2DPCA彌補了PCA的不足,有著深刻的應用場景,如掌紋識別[22]、圖像去噪[23]及圖像降維[24]等.其通過對原始數據做單側投影實現了數據壓縮的目的,但同時卻忽視了數據沿另一側壓縮的可能性.譬如,矩陣數據右乘投影矩陣,則列結構得以壓縮,但行結構卻并未發生改變.這樣的壓縮方式一方面會限制模型的壓縮性能,另一方面會造成壓縮后行列信息之間的不平衡.文獻[25]發表廣義主成分分析方法(GPCA)解決了這一問題并在次年提出了對應的改進算法—矩陣的廣義低秩近似(GLRAM)[26].對于給定的樣本A∈Rm×n,GPCA通過雙邊投影矩陣UL∈Rr×l1和UR∈Rc×l2實現對數據兩個方向的同時壓縮,并記壓縮后的樣本ZG=UTLAUR.

如果從優化視角出發考慮PCA、2DPCA及GPCA,這些方法均屬于“平方損失最小”準則下的擬合問題[16].而在相同復雜度下,非線性方法相比于線性壓縮方法而言,具有更強的擬合能力.盡管主成分分析類方法從未停止發展的腳步,但不論是PCA,2DPCA還是GPCA,都屬于線性壓縮方法.為此,也曾有專家、學者提出了一系列非線性主成分分析方法,如多層感知器、核主成分分析方法[27]以及自編碼器[28]等.多層感知器最初是為了克服感知機無法解決線性不可分問題而提出的一種設想,隨著反向傳播算法的提出,該方法突破了發展瓶頸,解決了隱層的權值訓練問題,但該方法解釋性不強;核主成分分析方法則是先將數據映射到高維特征空間中,再對數據進行主成分分析以實現降維,無疑在高維特征空間中,數據更容易被劃分,但在這個過程中,核函數沒有顯式表達式;自編碼器是在1985年,由 David H.等人在玻爾茲曼機上進行了首次嘗試,與大多數神經網絡模型一樣,該方法可解釋性弱,編碼與解碼過程類似于黑箱操作.因此,本文將基于二維主成分分析方法,探索一種可以自由變換壓縮方向且具有顯式表達式的非線性數據壓縮方法—非線性二維主成分分析(Two-Dimensional Nonlinear Principal Component Analysis,2DNPCA),并從網絡模型角度對方法進行直觀地解釋.

本文剩余部分的結構組織如下:第二節中首先描述了非線性二維主成分分析的核心思想,緊接著建立了該方法所對應的可解釋網絡模型;第三節中推導了基于梯度下降法所設計的形變反向傳播算法并證明了其收斂性;第四節中呈現了基于ORL數據庫公開數據集進行的數值實驗結果;第五節則在總結全文的基礎上,提出了方法可改進之處及未來的工作重心.本文所涉及的所有證明均在附錄中給出.

2 非線性二維主成分分析方法

2.1 核心思想

該方法延續了主成分分析類方法的一般做法,即通過特定的投影矩陣對數據進行壓縮.在此基礎上,每次投影之后通過引入激活函數對數據進行二次變換,在盡可能保留有效信息的原則下提高模型的壓縮能力.而引入什么樣的激活函數,需要根據數據特征而定.比如,對于一張像素值位于0-255之間的黑白照片而言,假設出現了像素值為負的異常點,想要將其就近修正,此時可以選擇Sigmoid函數,將負值點賦為一個無限接近于0的正數;另外,由于Sigmoid函數值域的特殊性,此文中省略數據歸一化的步驟.

因此,對于一個給定的黑白圖片樣本A∈Rr×c,非線性二維主成分被定義為

其中,f(i)(·),i=1,2為被選擇的激活函數.在深度學習領域,Sigmoid函數是一個被廣泛使用的激活函數,該函數可以將變量映射到(0,1)之間,呈現為S型曲線,具有單調遞增性和可微性.鑒于Sigmoid函數的優越性與普適性,本文取

當然,根據具體需求不同,也可以選擇其他類型的激活函數,比如Sgn函數,ReLU函數等.U(1)∈Rr×l1為行維度所對應的投影矩陣,實現行方向信息的壓縮;類似地,U(2)∈Rc×l2為實現列方向壓縮所對應的列投影矩陣.為了達到數據壓縮的目的,往往令l1＜r,l2＜c.對于給定的n個大小為r×c的樣本,原始情況下n*r*c的存儲空間需要被占用,按照上述方式壓縮后所需的存儲空間則變為n*l1*l2+r*l1+c*l2.衡量數據壓縮成功與否的重要標志之一為數據是否可以在一個誤差可接受的范圍內被重構,若U(1),U(2)為正交矩陣,f(1),f(2)為可逆函數,則原始數據可以按照如下步驟被完全復原:

但如果對模型加入過多假設,則會增加模型的計算復雜度,削弱模型的可推廣性.因此,考慮如下過程:

不妨直接令g(1),g(2)與f(1),f(2)保持一致,設為Sigmoid函數,使用過程中根據任務的不同,g(1),g(2)也可以被替換為其他激活函數.上述整個過程稱為前向傳播,執行前向傳播過程便得到重構數據?A,而?A與A之間的差異將被作為衡量方法壓縮性能的重要指標之一.

2.2 網絡結構

提及非線性數據壓縮方法,自編碼器是極具代表性的一種.而非線性二維主成分分析作為一種非線性數據壓縮方法,是否可以從網絡的角度去理解？答案是肯定的.在這一節中,將建立一個特殊的網絡模型以詮釋該方法,也將指出其與自編碼器的不同之處.根據前向傳播過程,本文得到一個包含三個隱層的網絡模型,圖1展示了最終的模型結構.按照自編碼器的定義方式,該結構可以視為由編碼器及解碼器兩部分組成,其中輸入層及第一、二隱層構成編碼器;第二、三隱層及輸出層構成解碼器.觀察模型不難發現,一個基于形變的子隱層在第一、三隱層的內部被引入,稱之為形變子層,它的引入使得網絡可以靈活改變數據的壓縮維度.除此之外,不同于一般網絡的黑箱性,該網絡是基于非線性二維主成分分析所構建,因此網絡中的各隱層各節點都有其存在的實際意義及顯示表達.

圖1 非線性二維主成分分析的網絡結構

接下來將對參數進行求解.

3 參數估計及其形變反向傳播算法

問題(11)是一個無約束最優化問題,通常使用最優化方法來求解,梯度下降法是其中極具代表性的一種.該方法的思想是沿著當前點的梯度反方向尋找新的迭代點,直到抵達某個局部最小值.對于凸優化問題而言,局部最優即為全局最優,這一結論的成立已經得到證明;然而對于如問題(11)的非凸優化問題,會出現多個局部最優解的情況.目前包含梯度下降法在內的大多數優化算法都無法保證一定能使得計算結果收斂到全局最優,但實驗部分的結果表明本文所設計的算法能夠得到一個較優的解.另外,梯度下降法雖適用于大多數情境,但它的一些變種,比如:批量梯度下降法、小批量梯度下降法及隨機梯度下降法等在數據集較大的情況下能夠取得優異的表現.因此,根據數據集的大小以及實際需要可以選擇恰當的算法以取得更優的性能.考慮到本文所用數據集較小,故選用梯度下降法.

根據梯度下降法的步驟,對于一個包含有n個樣本點A(1),···,A(n)的數據集,在每一個樣本點上按照如下方式更新參數:

其中f(·)為目標函數,η為學習率,也被稱為步長.結合(11)式易得

在第二節所建立的網絡結構中,直接計算損失函數關于投影矩陣的導數是非常困難的,而根據(1)-(10)式,利用復合函數求導的鏈式法則有

因此,可以將問題轉化為損失函數關于節點向量的求導.若記

表1 形變反向傳播算法

其中k為任意正數.

根據定理結果可知:當學習率充分小時,參數序列會無限靠近最優解,且在歐幾里得度量(Euclidean Metric)下,收斂速率為參數估計值與最優解之間距離平方的倒數.

注:由于證明過于繁瑣,因此該定理涉及的證明及引理均在附錄中給出.

4 數值實驗

4.1 數據集簡介

數值實驗將基于Olivetti Research Laboratory(ORL)人臉數據庫展開,該數據庫于1992年 4月至1994年4月由英國劍橋Olivetti實驗室創建,是一個在人臉識別領域非常著名的公開數據集.數據集共包含40個文件夾,每個文件夾對應一個人,每個人有10張人臉圖像,共400張.這些照片是在不同時間、不同光照條件以及不同的面部表情(睜眼或閉眼,微笑或不微笑)及面部細節(是否佩戴眼鏡)下拍攝的,所有圖像均在較暗的均勻背景下采集,且為正面拍攝,只有極少數存在稍微的側偏.這些圖像以PGM格式儲存,是高為112,寬為92的灰度圖像.在后續實驗中,所有圖像被縮放為高、寬均為90的灰度圖作為樣本參與實驗.實驗共分為兩個部分:第一部分驗證算法的收斂性;第二部分檢驗方法的壓縮性能.

4.2 算法收斂性實驗

在實驗開始前,需確定壓縮后行、列各自的尺寸.為了敘述簡潔,在下文中用基底對來稱呼每一個給定的行、列組合,比如壓縮后的行尺寸為a,列尺寸為b,則稱(a,b)為一個基底對.希望算法在所有的基底對上都能快速收斂,一個穩妥的檢驗辦法是遍歷所有基底對,觀察RMSRE是否能最終平穩.對于90×90的矩陣數據而言,共需遍歷8100組基底對,這無疑會耗費大量的時間,并且在實際壓縮過程中,壓縮后的尺寸應盡可能小,因此考慮以下選取方式:每個方向在3到50之間每間隔2取1個值,即按照3,6,9,···的方式等間距取值.如此每個方向上有16種選擇,僅需遍歷256組基底對即可.這樣的選擇方式大大減少了實驗的總次數且能保證所選擇的基底對是具有代表性的.

最終實驗結果如圖2所示,其中橫坐標表示迭代次數,縱坐標表示RMSRE的值,每一條不同顏色的曲線對應一組不同的基底對,共256條曲線.觀察圖形不難看出,大部分曲線都能在20次迭代前出現拐點并穩定于某個值附近,剩余的曲線也最終趨于平穩,此實驗結果表明形變反向傳播算法是收斂的.

圖2 不同基底對下RMSRE的變化情況

4.3 壓縮性能對比實驗

該實驗將通過對比非線性二維主成分分析與PCA,2DPCA及GPCA在ORL數據集上的壓縮效果來說明模型的壓縮性能,而壓縮性能的比較通常會涉及重構誤差及壓縮程度這兩個對立的指標,關于度量重構誤差的指標在算法收斂性實驗部分已經給出,在此再引入一個用于衡量壓縮程度大小的指標:壓縮率(compression ratio,CR).通俗來講,壓縮率被定義為

接下來將分別給出上述四種方法所對應壓縮率的具體表達式.通過引言可知,PCA及2DPCA對矩陣數據進行單側投影,而GPCA及本文方法執行雙側投影,因此這些方法壓縮率的表達式在形式上不同.

在第一個子實驗中,隨機抽選10組不同的基底對展開實驗,以各自的CR值作為橫坐標,對應的RMSRE值作為縱坐標得到圖3所示實驗結果,圖例中用2DNPCA表示非線性二維主成分分析.觀察圖形可以看出黑色實線始終位于黑色虛線下方,這意味著在同等壓縮程度下,非線性二維主成分分析方法所對應的RMSRE始終小于GPCA所對應的RMSRE,也就是說本文方法的壓縮性能優于GPCA.另外可以看出,在壓縮率小于160時,兩條曲線都呈現出上升趨勢,即誤差隨著壓縮率的逐漸增大而增大,這是符合認知的;但在160之后兩條曲線的變化則不再規律,并且呈現出大致相似的變化趨勢,因此有充足的理由認為這種變化是壓縮本身而非某一種方法所擁有的屬性.對此進行深入思考后,認為這種變化是由于矩陣數據的“各向異性”[16]所造成的,所謂“各向異性”就是高階數據在不同方向上所包含的信息量不同.在同一壓縮率下,對于矩陣數據而言對應著不止一種壓縮方案,如果沿著數據信息量較大的方向進行過度壓縮,則會導致重構誤差的增大,反之誤差則會變小.因此,沿著數據的哪個方向進行多大程度的壓縮是一個值得思考的問題,作者正在進行相關方面的研究工作并且已經有實驗證明在不同方向上確實存在相對應的較優壓縮程度.

圖3 GPCA及2DNPCA的壓縮性能對比

在第二個子實驗中將展示由四種方法重構所得的人臉圖像.與算法收斂性實驗類似,在每次實驗前都需預先確定基底對.為了保證對其他方法的公平,先設定 PCA及2DPCA選取的特征數為m,將m設置為GPCA及2DNPCA壓縮后其中一個方向的尺寸,再將另一個方向的尺寸壓縮為d,如此可以保證本文方法是在同等或較為苛刻的條件下與其他方法進行比較.實驗發現:不同基底對下,實驗結果非常相似,出于文章篇幅的考慮,本文只挑選一組作為展示,所挑選的這組對比圖(圖4)是在m=8,d=26的情況下所得到的.

圖4 重構人臉圖像對比

圖4中第一行為原始圖像,接下來依次為由PCA,2DPCA,GPCA及2DNPCA所對應的重構人臉圖.觀察圖像可以發現,由PCA重構所得圖像的清晰度顯著差于其他三種方法,而另外三種方法對應圖像的清晰度則沒有明顯差異.為了得到一個確切的結論,計算三種方法對應的重構誤差依次為:5.9850,5.9221以及5.7681.重構誤差越小,則意味著與原始圖像之間的差異越小,這就說明除了原始圖像所在行,剩余四行的清晰度依次遞增.基于此,得出本文方法的壓縮性能優于PCA,2DPCA及GPCA的結論.

5 結論

本文基于二維主成分分析提出一種非線性矩陣壓縮方法—非線性二維主成分分析法,該方法通過引入激活函數對投影后數據進行變換,從而實現數據的非線性壓縮;同時,本文從網絡角度出發建立了對應的可解釋網絡模型,模型通過在特定位置加入形變子層對壓縮方向進行改變,進而實現矩陣數據兩個維度的同時壓縮,PCA,2DPCA及GPCA等方法也可從該角度獲得直觀解釋;除此之外,本文設計了模型的“形變反向傳播算法”并給出了收斂性證明.數值實驗則基于ORL數據庫的公開數據集展開,實驗結果表明:非線性二維主成分分析的壓縮性能優于線性主成分分析類方法PCA,2DPCA及GPCA.

在數值實驗中,本文采取遍歷的方式確定每個方向上數據被壓縮后的尺寸,但這樣的方式不夠簡潔,因此作者致力于開展相關方面的研究工作且已經取得不錯的實驗結果;另外“形變反向傳播算法”是基于梯度下降法而設計的,但在樣本量非常大的情況下,小批量梯度下降法及隨機梯度下降法都是更佳的選擇.

附錄A

定理 A.1對于損失函數(11)及網絡模型圖1,有以下結論成立: