主成分提取信息準則的加權規則

杜柏陽 孔祥玉 羅家宇

在信息處理領域,主成分分析(Principal component analysis,PCA)又稱為KL 變換(Karhunen-Loéve transform),廣泛應用于信號壓縮[1]、模式識別[2]、圖像處理[3]、噪聲估計[4]、神經網絡建模[5]等問題.通常,主成分(Principal component,PC)可以通過求解自相關矩陣的特征分解求得,具體是指自相關矩陣中前個最大特征值對應的特征向量.由這些特征向量張成的特征子空間被稱為主子空間(Principal subspace,PS).

當前,在大量跟蹤輸入信號主成分主子空間的算法中,神經網絡算法因為計算復雜度低等多種優良的性能而引起許多學者的興趣[6].學者們提出大量的神經網絡學習算法,用于提取主成分或者跟蹤主子空間.例如,建立在啟發推理機制上的Oja 主子空間跟蹤算法[7]、對稱誤差校正算法[8],以及建立在信息準則基礎上的最小均方誤差重構(Least mean square error reconstruction,LMSER) 算法[9]、投影近似子空間跟蹤(Projection approximation subspace tracking,PAST)算法[10].

早期的算法結構簡單,但是在自穩定性、平滑性以及魯棒性等方面還有待于優化.針對這些問題,Kong 等[11]提出了雙目的的自穩定主成分提取神經網絡算法,Kakimoto 等[12]提出了基于最小噪聲準則的平滑自適應特征提取方法,Ouyang 等[13]提出了遞歸的魯棒主成分分析算法.不僅如此,算法提取的對象還擴展到信號次成分[14]和廣義特征成分[15].通過研究這些算法,可以知道提取信號多個成分和跟蹤信號子空間的算法雖然實現提取的對象不同,但是在算法的原理上存在一定程度的關聯.以主成分提取算法為例分析,多個主成分提取算法和主子空間跟蹤算法都能夠退化為單一主成分的提取算法,這反映出兩個類型的算法具有某種相同的基本特性.反過來,如果存在一個能夠提取單個主成分的提取算法,是否能遵循一定的原理或者規律,使得該算法能夠轉化為提取多個主成分或者跟蹤主子空間的算法？這個問題的解答對靈活轉換各種先進的成分提取算法,增加人們對提取算法本質和多種性質的理解具有十分重要的意義.

多個主成分可以張成一個主子空間,因而通常認為多個主成分的提取算法是主子空間跟蹤算法的進步.一般而言,多個主成分的提取算法的提出方式有兩種.一種是根據實際需求直接提出一種新的信息準則,通過推導信息準則的梯度函數得出對應的提取算法;另一種是在已有的主子空間跟蹤算法的基礎上,引入加權規則,使得轉變后的算法能夠提取多個主成分.Tanaka[16]通過研究多個主成分提取算法的廣義加權規則,分析出廣義加權規則的參數對提取算法的收斂速度有影響.加權規則的參數變化會引起算法的性質變化.當參數的取值沿著實數軸負方向變化時,加權矩陣則逐漸近似為單位陣,算法的提取能力逐漸由多個主成分提取退化為主子空間跟蹤.

實際上,有的主子空間提取算法在使用加權規則后可以轉化為多個主成分的提取算法,而有的算法則不具有這種能力.主子空間的組成向量與主成分之間的夾角能夠說明主子空間與主成分的偏離程度.有的主子空間跟蹤算法能夠轉化為多個主成分提取算法,原因在于這些跟蹤算法在運行過程中能夠減小夾角的大小.而本質上,確定這個夾角關系的是信息準則,信息準則函數在算法對信息的歸類方式、算法提取信息的方式等具有非直接的規定.因此,在信息準則的角度分析加權規則對主子空間跟蹤算法和多個主成分提取算法的作用能夠反映算法的一些本質特性.

本文主要針對加權規則對主成分提取算法的信息準則的作用進行分析,以Oja 主子空間跟蹤算法為例,通過構建提取算法的動力學表達,對比存在和缺失加權規則下的主子空間跟蹤信息準則,挖掘出信息準則對狀態矩陣與主成分的方向夾角的梯度差異.

1 加權規則

根據文獻[7]和文獻[17]可知,Oja 算法的信息準則為

其中,Ir∈Rr×r表示單位陣,W∈Rn×r為算法的狀態矩陣,n為輸入信號的維數,r為需要提取的主成分個數,R=E[xxT]∈Rr×r為隨機輸入信號x的自相關矩陣,E[·] 表示計算方括號內的數學期望.假設R是滿秩矩陣,特征值互不相同.那么,輸入信號有n個特征向量φi,i=0,1,···,n-1,容易理解,當存在一個矩陣W=Wn,使得信息準則函數值J1(W)能夠取得最大時,Wn就等價于信號的主子空間,也就是前r個特征向量φi張成的子空間.

另外,Oja 還首先提出加權規則下的信息準則[18]

其中,D=diag{d1,d2,···,dr}∈Rr×r為一個對角矩陣,它的作用就是為狀態向量加權.在主成分提取的算法中,加權矩陣的各個元素通常設置為d1＞d2＞···＞dr.其余變量的含義與式(1)相同.類似于Oja 算法的信息準則,當W=Wn時,J2(W)能夠取得最大時,此時Wn不僅是前r個特征向量φi張成的子空間,而且組成Wn的各個向量與對應的特征向量φi相同.

通過以往研究可知,由以上兩個信息準則求取相應跟蹤或者提取算法通過梯度下降法實現,其基本的表達式為

其中,ηΔW(k)為算法的搜索方向,根據文獻[16]可知,該方向為信息準則的梯度下降方向ηΔW(k)=;W(k)為第k步迭代中的狀態矩陣,維度與式(1)中W相同;η∈(0,1)為算法的學習因子.實際上,有的加速算法中的學習因子并不是固定長度的,為了簡化算法分析過程,此處假設學習因子是固定長度的.

相應地,由信息準則(1)推導得到的算法常微分方程形式[7]為

該算法能夠有效地在線跟蹤信號的主子空間.假設子空間相對于多個主成分的旋轉矩陣為M1∈Rn×r,P=[φ0,φ1,···,φr-1],于是有W=PM1,主子空間的跟蹤過程就是M1的前r行元素變化為某個旋轉矩陣,后n-r行元素變化為零的過程.

由信息準則(2)推導得到的算法常微分方程形式[18]為

該算法也能夠有效地在線跟蹤信號的主子空間.與上文相似,存在一個M2∈Rn×r,W=PM2.這說明兩種算法的信息準則都能夠敏感到前r個特征值對應的特征信息.而不同之處在于,主子空間的跟蹤過程中,M2的前r行元素變化為一個對角陣.本文主要針對M1和M2變化的差別展開分析,從微觀角度探究加權規則對算法作用的動力學變化.

2 主成分提取過程動力學分析

只考慮一維特征的情況可以通過確定離散時間(Determinate discrete time,DDT)方法分析[19].直接分析高維特征提取過程非常復雜,不容易說明清楚.因而首先從二維特征情況開始.

定理1.信息準則J2(W)不能確定狀態矩陣的各個向量與信號主成分方向之間的關系.

證明.假設M1的旋轉角度為θ,那么M1可以寫為

此時,信息準則(1)表示為

那么,信息準則對角度的梯度需要通過梯度下降公式解為

因而可以計算得

注1.定理1 可得的另外一個結論是,信息準則(1)的梯度算法提取出的主子空間與信號主成分存在一個夾角,并且該夾角與算法設置的狀態矩陣初值有關.

注2.信息準則J1(W)并不能直接導出狀態矩陣的變化方式,通常是通過梯度下降法、牛頓法、Nestrove 加速下降法等等利用信息準則的一階、二階甚至是高階導數或者偏導數得到迭代更新公式.當迭代公式收斂時,對信息準則J1(W) 而言,收斂結果只能確保狀態矩陣的模值收斂到某固定值而不能確定狀態矩陣的各個向量與輸入信號自相關矩陣的主成分方向的關系.信息準則在本質上規定了狀態矩陣的變化方式.

實際上,加權規則能夠改變信息準則的這個性質.具體過程可以通過定理2 說明.

定理2.信息準則J2(W)能夠確定狀態矩陣的各個向量與信號主成分方向之間的關系.

證明.假設M2的旋轉角度為θ,那么M2可以寫為

此時,信息準則(2)表示為

同樣地,該信息準則對角度的梯度也可通過梯度下降公式解為

此時,可得

以上分析本質上是在n=2,r=2 這種特殊情況的討論.下面需要對上述結論推廣到n ＞2,r=2的情況.

推論1.對于n＞2,r=2, 信息準則J1(W)不能規定狀態向量與信號主成分方向的關系,而信息準則J2(W)能夠規定狀態向量與信號主成分方向的關系.

證明.顯然對于n＞2,r=2情況下的J1(W)和J2(W)而言,對應的梯度算法都能夠跟蹤主子空間,這在原作者的論文中已有明確的證明.也就是說,W的后n-r行元素總是逐漸變化為零.不妨認為,當迭代次數大于某一個大數時,狀態矩陣可以表達為W=P[0]T, 其中,* 位置為1或2.此時根據定理1和定理2 的分析過程得知,信息準則J1(W) 不能敏感狀態向量與信號主成分方向的變化,而信息準則J2(W) 能夠敏感狀態向量與信號主成分方向的變化.□

對于n=r,r ＞2 的情況而言,主要考慮歐拉轉角描述所有的角度變化.第1 個相角變化為θ1,第2 個相角變化為θ2, 以至于第r個相角變化為θr.每一個角總是在上一個旋轉角度基礎上繼續旋轉,例如r=3時旋轉矩陣M*表示為

以此類推.即將1 放在不動軸的位置,并且該元素所在行和列的其他元素均為0.不動軸的數量為r-2. 旋轉次數為.

推論2.對于n=r,r ＞2, 信息準則J1(W)不能敏感狀態向量與信號主成分方向的變化,而信息準則J2(W)能夠敏感狀態向量與信號主成分方向的變化.

證明.與定理1 和定理2 的證明步驟相似,信息準則(1)表示為

此時的旋轉矩陣變為

同時信息準則對角度的梯度表達為多個公式

因為M1*具有旋轉對稱性,為了描述簡便,此處僅以θ1為例進行說明.

由此可得,

顯然,對于未加權的信息準則J1(W)而言,對于任意θ1恒成立.與此同時,對于加權信息準則J2(W) 而言,經過與上述推導過程相似的步驟可得,

注3.對于n＞r,r ＞2 情況的討論,其基本思路同推論1,都是考慮在一定條件下,狀態矩陣各個向量的長度發生變化,最終轉化為n=r,r ＞2 的情況,結合推論2 的結論實現對該情況的討論.

注4.通過定理和推論的分析可知,加權規則對提取算法產生影響的本質因素是加權算法改變信息準則在方向上的梯度變化.這對后續該類算法研究的啟發是,在考慮將主子空間提取算法轉變成并行提取算法時,其核心步驟是使算法在狀態矩陣與實際主成分的夾角方向上產生梯度.為驗證該思路對于Oja 信息準則以外的信息準則也有效,本文考察M iao 信息規則在加權規則下的性質變化.

3 數值分析與仿真實驗

為保證算法具有可比性,在生成數據的時候對輸入信號做出統一規定.各個仿真實驗的輸入信號自相關矩陣的特征值為同一組數值,在此考慮Λ=diag{1.052,2.335,5.002,5.251,6.012,6.123}.通過算法提取出信息的主成分P=[φ0,φ1,···,φn-1].另外,加權矩陣的數值也是任意選取一組滿足定義的 數值,此處選為P=diag{1,2}.

3.1 Oja信息準則與Oja加權信息準則

如圖1 所示,外側的曲面圓錐為Oja 信息準則函數值變化,內側的曲面圓錐為加權Oja 信息準則函數值變化.首先,兩個函數值變化情況共同印證了信息準則能夠良好地敏感狀態矩陣的模值變化.為更加清晰地表征這個特點,該算例在某一個固定的角度投影兩個信息準則函數,如圖2.其次,兩個曲面變化都具有對稱性.其中,內側的曲面圓錐是隨著θ周期對稱的,印證了定理2 中的一個結論,外側的曲面圓錐是處處對稱的.

另外,兩個曲面的變化也是存在差別的.這首先表現在θ從 (0,2π] 變化的過程中,外側的曲面圓錐在固定模值下,數值沒有變化,如圖3 所示,以θ為橫坐標,將圖1 中狀態矩陣模長為 1.5 處的曲面函數值投影并展開,作為縱坐標;內側的曲面圓錐在固定模值下,數值一直處在變化中,如圖4 所示,以θ為橫坐標,將圖1 中狀態矩陣模長為1.5 處的曲面函數值投影并展開作為縱坐標.其次,在θ固定的時候,兩個曲面函數變化的梯度也不相同,如圖2 所示,明顯外側的曲面圓錐的下降坡度小于內側的曲面圓錐的下降坡度.這一點能夠解釋所有以Oja 信息準則為基礎的梯度下降算法,加權規則下的信息準則具有更好的收斂速度.

圖1 Oja 信息準則和加權Oja 信息準則在 θ 變化情況下的數值變化Fig.1 Curves of the information criterion Oja and weighted Oja algorithms on θ

圖2 Oja信息準則和加權Oja 信息準則在處的投影Fig.2 Projection of the information criterion Oja and weighted Oja algorithms when

圖3 Oja 信息準則在θ變化情況下的數值變化Fig.3 Curves of Oja information criterion on θ

圖4 加權Oja 信息準則在θ變化情況下的數值變化Fig.4 Curves of weighted Oja information criterion on θ

綜合上述分析,該算例能夠驗證Oja 信息準則與加權Oja 信息準則對提取算法在理論上分析的結論.

3.2 Miao信息準則與Ouyang信息準則

本文所研究的結論不僅適用于Oja 信息準則,還適用于其他信息準則,此處考慮Miao 信息準則[20]和Ouyang 信息準則[21].的初始設置與第3.1節中的算例相同.

Miao 信息準則的基本表達式為

Ouyang 信息準則的基本表達式為

從上述公式可以看出,Miao 信息準則在加權規則下的討論就是Ouyang 信息準則.從圖5～8 中可以看出,Miao 和Ouyang 信息準則的變化特性都能夠呈現出第3.1 節的三個特性,這表明經過與Oja 及加權Oja 信息準則相似的動力學分析過程,也能夠得到一致的結論.實際上,不僅Oja 算法、Miao 算法和Ouyang 算法,作者經過仿真驗證,Yang[10]和Lei[9]的LMSER 算法也具有相似的動力學特性,由于篇幅限制在這里不做展示.這些算法的不同之處在下降的速度以及在平衡位置的信息準則函數值上.

圖5 Miao 信息準則和Ouyang 信息準則在θ變化情況下的數值變化Fig.5 Curves of the information criterion Miao and Ouyang algorithms on θ

圖6 Miao信息準則和Ouyang 信息準則在處的投影Fig.6 Projection of the information criterion Miao and Ouyang algorithms when

圖7 Miao 信息準則在θ變化情況下的數值變化Fig.7 Curves of Miao information criterion on θ

圖8 Ouyang 信息準則在θ變化情況下的數值變化Fig.8 Curves of Ouyang information criterion on θ

3.3 加權規則的應用案例

圖像壓縮是計算機圖形圖像學領域的熱點問題.通過圖像壓縮技術都可通過壓縮圖像數據實現更加高效地存儲和傳輸.基于主成分分析方法的壓縮是圖像壓縮領域中的常用方法[22].本節采用主成分分析對Lena 圖像進行壓縮和重構.Lena 的原圖如圖9 左上角所示,分辨率為 512×512 像素.這里將圖像分解為 4× 4 像素的不重疊小塊.這些小塊是按照從左到右由上到下的順序排列,可得一個16×16 384 的數據向量.該數據經過預處理后作為主成分分析算法的輸入序列.采用本文研究的加權Oja算法和Ouyang 算法對圖像壓縮后重建.

圖9 原始和重建的Lena 圖像Fig.9 Original and reconstructed Lena images

加權Oja 算法使用兩次.第1 次只取一個主元,學習因子為 0.01,第2 次并行提取兩個主元,學習因子也為 0.01,主要對比單個主元和多個主元情況的重建誤差.Ouyang 算法使用一次,提取兩個主元,學習因子也取 0.01.兩個主元提取的算法加權矩陣為D.比較不同算法提取主元的精度.圖9 右上角為一元Oja 提取算法的重建效果,重建誤差為0.0829.圖9 左下角為二元Oja 提取算法的重建效果,重建誤差為0.0602.圖9 右下角為二元Ouyang提取算法的重建效果,重建誤差為0.0402.對比實驗效果可以發現,多元并行提取算法相比單個主元提取算法具有優勢,Ouyang 算法相比Oja 算法具有優勢.這進一步表明先進算法需要通過加權算法確 保算法具有并行提取多個主成分的能力.

4 結論

本文通過分析Oja 信息準則和加權Oja 信息準則的差異,推導出加權規則能夠改變狀態矩陣和信號主成分的旋轉矩陣梯度的結論.一方面這對于其他主子空間跟蹤算法的轉變提供了理論支撐,提高在信息準則層次影響算法性能的認識;另一方面,對于不能通過加權規則轉化為多個主成分提取算法的主子空間跟蹤算法,本文也給出轉變的基本思路.研究為推進未來并行提取多個主成分分析算法發展提供了研究思路和轉變方向,最后通過數值實例仿真驗證了理論的有效性.