動機
數據表雖然有很多欄,獨立的變化模式卻可能少得多。兩項量度可以一起變動;位於高維空間的觀測,也可以大致集中在一個平面附近。降維要用較少座標描述這些結構。要把這個要求寫成數學問題,我們須說清楚:保留甚麼資訊,以及怎樣量度重建誤差。
主成分分析(PCA)選取互相正交的方向,盡量保留數據的變異。奇異值分解(SVD)提供這些座標,也精確記錄捨棄的變異。同一計算還可以理解為:用一個低維仿射子空間擬合觀測。這種連繫解釋了為何要先中心化,以及為何方差公式使用奇異值的平方。
PCA 不像迴歸那樣,指定某一欄為因變量;各項特徵共同決定幾何。因此,量度單位會影響答案。把米改成厘米,如果不相應調整預處理,就會改變普通歐氏距離。選取哪些特徵、使用甚麼尺度,都是數學模型的一部分。
定義
設 X∈Rn×d 包含 n≥2 個觀測。第 i 行是 xiT,其中 xi∈Rd 是特徵的列向量。以下一直採用「行代表觀測、欄代表特徵」的約定:方向屬於特徵空間 Rd,全體觀測的得分則組成 Rn 中的向量。
定義
中心化與樣本協方差
平均特徵向量與中心化矩陣定義為
μ=n1XT1,H=In−n111T,A=HX=X−1μT.這裏 1∈Rn 的每項都是一。樣本協方差矩陣是
C=n−11ATA∈Rd×d.
由 1TH=0,可知 A 每欄的總和都是零。另外 HT=H、H2=H,所以再次中心化不會改變結果。常數向量位於 H 的零空間,故 rank(A)≤min(n−1,d)。這解釋了為何原表即使具有滿行秩,中心化後也可能出現零奇異值。減去平均值移除的是整體位置,而非圍繞該位置的變化方向。
給定單位方向 v∈Rd,觀測 i 的得分是 (xi−μ)Tv。得分向量為 Av,其平均值是零,所以樣本方差為
Varsample(Av)=n−1∥Av∥22=vTCv.
定義
奇異值、載荷方向與得分
把約化 SVD 寫成
A=UΣVT,p=min(n,d),其中 U∈Rn×p、V∈Rd×p 的欄向量各自正交歸一,而 Σ=diag(σ1,…,σp),滿足 σ1≥⋯≥σp≥0。正奇異值的數目是 r=rank(A)。右奇異向量 vj 是 PCA 的載荷方向,Avj=σjuj 是對應的得分向量。
完整 SVD 的 U、V 都是方形正交矩陣,中間則是長方形對角矩陣;它按需要補入零方向。對任何 k≤r,兩種分解都給出相同的首 k 個載荷所成矩陣 Vk=[v1 ⋯ vk],以及降維座標 Z=AVk=UkΣk。載荷是用來量度座標的方向,得分是某個觀測在該方向的座標;兩者的維數亦不同。
定理/命題
定理
主方向使保留方差最大
設 A 已中心化,C=ATA/(n−1)。如有需要,把奇異值序列補零至第 d 項。協方差特徵值為
λj=n−1σj2.在所有單位方向中,v1 使得分方差最大。更一般地,若 W∈Rd×k 滿足 WTW=Ik,則 tr(WTCW) 的最大值為 ∑j=1kλj,由首 k 個右奇異向量達到。
總變異非零時,第 j 個主成分的解釋方差比例,以及首 k 個主成分的累積比例,分別是
ρj=∑ℓ=1rσℓ2σj2,Rk=∑ℓ=1rσℓ2∑j=1kσj2.
比例中的 n−1 約去。若以 n 作總體協方差的分母,特徵值會改變,主方向及上述比例則不變。若全部觀測相同,便有 A=0;所有得分都是零,沒有正的總變異可用來定義百分比。
定理
投影誤差與截斷 SVD
對正交歸一的 W,中心化座標中的重建為 AWWT,而
∥A−AWWT∥F2=∥A∥F2−∥AW∥F2.因此 PCA 也使總平方重建誤差最小。其解為
Ak=AVkVkT=UkΣkVkT,∥A−Ak∥F2=j=k+1∑rσj2.此外,在所有秩不超過 k 的矩陣 B 中,Ak 使 ∥A−B∥F 最小。返回原來座標時,重建為 X=1μT+Ak。
Frobenius 範數的平方等於矩陣各項的平方和,所以上式合計全部觀測、全部特徵的偏差,並非每個觀測的方差,也不是每項數據的平均誤差。解讀秩的選擇時,要一起說明這個尺度。保留八成變異是否足夠,取決於用途;一個方差較小的特徵仍可能很重要。最優化結論精確說明 PCA 所解的是哪一種平方距離問題。
降維座標保留甚麼
得分表除了各欄平均值為零,欄與欄亦互相正交。事實上,
n−11ZTZ=n−11Σk2=diag(λ1,…,λk).
因此不同得分的樣本協方差為零,方差按大小排列,可從對角線直接讀出每個保留座標的貢獻。零協方差描述的是這個得分表的二階矩,單憑它不能推斷原來量度在統計上獨立。PCA 建構正交線性座標,使總變異最大,並沒有為觀測指定概率模型。
重建時沿相同載荷反向變換:把得分行乘以載荷矩陣的轉置,便返回特徵空間。重建行位於所選子空間,殘差垂直於每個保留方向。這也提供計算檢查:殘差表乘以載荷矩陣,結果應為零(數值計算容許捨入誤差)。投影會把不同原始觀測映成同一得分,所以單靠保留得分不能恢復被捨棄的部分。
PCA 擬合直線時量度的是指定特徵度量下最短的垂直距離;普通迴歸則把解釋變量視為給定,沿因變量方向量度誤差。因此,即使只有兩項特徵和一條直線,兩種目標仍可能選取不同直線。使用算法前,要辨明誤差模型容許哪些量度變動,以及最終需要的是預測,還是數據的幾何表示。
證明思路
證明
由譜定理到主成分
ATA 對稱且半正定,因為 vTATAv=∥Av∥2≥0。按特徵值由大至小選取一組正交歸一特徵向量。對正特徵值 σj2,令 uj=Avj/σj。於是 uiTuj=viTATAvj/(σiσj),在 i=j 時為一,其餘為零。零特徵值則給出 ∥Avj∥2=0,故 Avj=0,不用除以零。這 r 個 uj 張成欄空間,補成 Rn 的正交歸一基底得到方形 U,並保留完整特徵基底 V。取 Σ∈Rn×d,首 r 個對角項為正 σj,其餘為零。逐欄有 AV=UΣ,所以 A=UΣVT;長方形或秩不足矩陣亦成立。
把單位向量展開為 v=∑jajvj,則 vTCv=∑jλjaj2≤λ1,因為 ∑jaj2=1。若選取多個方向,令 qj=∥WTvj∥2。正交投影給出 0≤qj≤1、∑jqj=k,故 tr(WTCW)=∑jλjqj 不超過最大 k 個特徵值的總和。選取它們的特徵向量便達到上界。
投影等式可逐個觀測證明:每個中心化行向量分成子空間內的投影,以及與該空間垂直的餘項;畢氏定理把兩部分的平方長度相加。再對所有行求和,就得到 Frobenius 等式。在 SVD 座標中,被捨棄的各個秩一項亦在 Frobenius 內積下正交,所以每項對誤差的貢獻恰是奇異值的平方。
為何任意秩 k 矩陣也不能給出更好的結果?其所有行都位於某個維數不超過 k 的子空間 S。把 A 每行正交投影到 S,誤差不會大於選取該候選矩陣的對應行。而在所有這些子空間中,上述方差論證已找出最佳者。這同時證明了低秩近似和幾何 PCA 的結論。
截斷對譜範數 ∥E∥2=max∥w∥2=1∥Ew∥2 亦最優。對 0≤k<r,
rank(B)≤kmin∥A−B∥2=∥A−Ak∥2=σk+1.
把秩不超過 k 的候選 B 限制在 span{v1,…,vk+1},因定義域維數為 k+1,其零空間含單位向量 w。故 Bw=0,而 ∥(A−B)w∥2=∥Aw∥2≥σk+1。截斷餘項的最大奇異值恰為首個捨棄值,達到下界。譜誤差量度單位方向的最壞放大,Frobenius 誤差的平方則合計全部捨棄方向的平方損失。
例題
例題
1. 完整計算兩項特徵的 PCA
考慮四個觀測:
X=12810105564,μ=[105],A=2−200001−1.A 的兩欄正交,故
ATA=[8002],C=[8/3002/3].取 v1=(1,0)T、v2=(0,1)T,則 σ1=22、σ2=2,而
U=1/2−1/200001/2−1/2,V=I2.相乘 Udiag(22,2)VT 可重得 A。第一個得分向量是 (2,−2,0,0)T,樣本方差為 8/3,保留的變異比例是 8/(8+2)=4/5。只保留此座標,再加回平均值,得到
X=12810105555.最後兩個觀測各有大小為一的誤差,總平方誤差是 2,等於被捨棄的 σ22。除以八項數據後,均方誤差是 1/4,逐項的均方根誤差是 1/2。
這例子區分了四個常被混用的量:奇異值、奇異值平方、樣本方差、解釋比例。它們描述同一方向,卻回答不同問題。奇異值是得分空間的長度;把它平方再除以 n−1 才是樣本方差。比例亦要使用平方,因為正交分解中可相加的是平方能量,並非未平方的長度。
例題
2. 中心化改變擬合的幾何
同一批原始觀測滿足
XTX=ATA+nμμT=[408200200102].非對角項變成 200,所以 (1,0)T 不是 XTX 的特徵向量。直接分解 X,會選到另一個受整體位置影響的首方向。若只把原始觀測投影到通過原點的橫軸,整個第二座標都被捨棄,平方誤差為 25+25+36+16=102。
中心化 PCA 擬合的是通過 (10,5) 的水平線,誤差只有 2。兩者所解的擬合問題不同;最佳原始秩一方向也不一定水平。上述比較說明,原始橫軸投影並不等於中心化後的重建。
對新觀測 (11,7),先減去訓練數據的平均值得到 (1,2)。第一得分為 1,用一個主成分重建後是 (11,5)。處理後續觀測時,要沿用相同的平均值和載荷,使所有得分使用同一座標系。
仿射觀點在此很清楚:保留的中心化子空間通過零,加回平均值後才移回觀測所在的位置。因此,維度可以用來描述數據周圍的變化,而不用花一個方向描述整體離開原點的位移。若要從得分表解碼回原座標,除了載荷,還須保存平均向量。
例題
3. 特徵單位與重複特徵值
把第二項特徵乘以三。中心化後的行為 (2,0)、(−2,0)、(0,3)、(0,−3),散佈矩陣為 diag(8,18)。首載荷變成 (0,1)T,保留比例為 18/26=9/13,秩一平方誤差為 8。
另一個選擇是把原來每欄除以其樣本標準差,即 8/3 和 2/3。標準化後的散佈矩陣是 3I2,協方差矩陣是 I2。每個單位方向的得分方差都為一,沒有特別優先的單一首主成分;任意正交歸一的一對方向都張成同一個二維空間。
標準化選取了另一個距離度量,讓不同特徵使用可比較的尺度。當單位較任意時,這可能有用;但如果變異大小本身有意義,標準化也會消除這項差異。解讀保留比例前,先說清楚誤差在原單位還是標準化單位中量度。零方差的欄沒有正標準差可除,它對中心化變異的貢獻亦是零。
冪迭代與偽逆
從實特徵基到冪迭代
先備概念見 特徵值、實對角化及可對角化判準。設實方陣 B=VDV−1 有實特徵基,各欄 vj 長度取一,但未必正交。一組模最大條件是
∣λ1∣>j>1max∣λj∣,c=V−1q0,c1=0.
從單位初值 q0 開始,每次相乘後歸一化;在固定特徵基中展開得
qk+1=∥Bqk∥2Bqk,Bkq0=c1λ1k(v1+j>1∑c1cj(λ1λj)kvj).
其餘係數相對首項幾何衰減,方向便趨近首特徵線;首係數非零亦保證歸一化分母不為零。這些比例屬於特徵基座標,歐氏範數界還取決於基底幾何。下文對稱散佈矩陣才可使用正交座標的較強估計。
c1 由解 Vc=q0 得到,不能以 v1Tq0 代替:非正交基中,點積為零仍可有首係數,點積非零也未必有。缺少的首係數不會在相乘中出現;嚴格模間隔則排除另一個同量級模式持續競爭。
若 λ1<0,歸一化向量可正負交替,收斂的是直線。Rayleigh 商 ρ(q)=qTBq/(qTq) 在該直線兩個單位代表附近連續,且不受符號影響,故趨近 λ1。非對稱時沒有對稱矩陣的方差極值解釋,中途商值亦可超出實特徵值範圍。
例題
負主特徵值與非正交基
取
B=[−3041],V=[1011],D=diag(−3,1).此處基底欄尚未歸一化。q0=(0,1)T 的座標為 (−1,1)T,含首係數;把基底歸一化只會縮放係數,不改變零與非零。原始迭代為 (4,1)T、(−8,1)T,而 q2=(−8,1)T/65 有 ρ(q2)=−223/65<−3。方向趨近橫線,符號交替。若沿 (1,1)T 開始,則一直留在特徵值一的方向,雖與橫向特徵向量點積非零。
對單位右特徵向量,減去 λ1v1v1T 仍把首向量映成零,但通常改變其他原特徵向量。要保留其餘特徵對,可取左特徵向量 w1TB=λ1w1T、w1Tv1=1,減去 λ1v1w1T。本例 v1=(1,0)T、w1=(1,−1)T 給出
B+3v1v1T=[0041],B+3v1w1T=[0011].
前者把原向量 (1,1)T 映成 (4,1)T,配對更新則保留它。對稱矩陣可取相同的左右單位特徵向量,便回復正交消去公式。
近似首 PCA 方向
只需要首主方向時,可用冪迭代代替完整分解。設 S=ATA 的特徵值為 λ1>λ2≥⋯≥λd≥0,正交歸一特徵向量為 vj。取單位初值 q0=∑jcjvj,要求 c1=0,反覆計算
qk+1=∥Sqk∥2Sqk.
迭代方向與 Skq0 相同。提出 λ1k 後,其餘方向的係數帶有 (λj/λ1)k,故垂直部分與首分量之比不超過
(λ1λ2)k∣c1∣∑j=2dcj2.
方向因此以幾何速率趨近 v1,容許符號相反。歸一化控制長度,不改變比例;譜間隔越小,收斂越慢。初值若垂直首方向,就永遠沒有該分量。單位向量的 qkTSqk 近似首特徵值;已知精確首特徵對後,S−λ1v1v1T 可移除該模式。大型數據可直接計算 Sq=AT(Aq),不用明確建立散佈矩陣。
例題
4. 追蹤主要散佈方向
取 S=diag(4,1)、q0=(1,1)T/2。兩次迭代給出
q1=17(4,1)T,q2=257(16,1)T.第二座標與第一座標之比依次為 1、1/4、1/16,展示譜比 λ2/λ1 的作用;方向趨近首載荷 (1,0)T。
選取最小範數最小二乘係數
對實矩陣 M∈Rm×p,以正奇異值寫成 M=UrΣrVrT,定義
M+=VrΣr−1UrT,z∗=M+y.
直接相乘 SVD,可核對四條 Penrose 等式:
MM+M=M,M+MM+=M+,(MM+)T=MM+,(M+M)T=M+M.
其中 MM+=UrUrT、M+M=VrVrT 分別正交投影到欄空間和行空間,均對稱且冪等。滿行秩時前者是 Im,滿欄秩時後者是 Ip;方形可逆時 M+=M−1。秩不足時,兩個投影辨明數據決定哪些響應與係數方向。
對任意 y,它是唯一最小範數最小二乘係數。因 Mz∗=UrUrTy 是 y 在欄空間的正交投影,殘差最小。其他最小二乘係數皆為 z∗+h,其中 h∈kerM。而 z∗ 屬於 Vr 張成空間,垂直零空間,故 ∥z∗+h∥22=∥z∗∥22+∥h∥22;只有 h=0 才同範數。
方程相容時,這給出最短精確解;不相容時,則在同樣準確的擬合中選最短係數。只對正奇異值取倒數,毋須逆轉奇異矩陣。同一 SVD 因而兼顧降維和係數選取。
在左奇異座標中,vj 的係數是 (ujTy)/σj。y 垂直欄空間的部分無法擬合,留在殘差;零右奇異方向則容許加入零空間向量。最小範數選擇把自由座標設為零,每個正奇異值只需一次除法。若只保留部分正奇異方向,解的便是該張成空間內的受限擬合,並非原來不受限的最小範數最小二乘問題。
例題
5. 解決欠定擬合
設 M=[1 2]、y=5,則 M+=(1,2)T/5、z∗=(1,2)T。所有精確解是 z=(5−2t,t)T,且
∥z∥22=(5−2t)2+t2=5(t−2)2+5.在 t=2 達最小值,核對了 z∗ 及平方範數 5。與它的差為 (t−2)(−2,1)T,正是垂直 (1,2)T 的零空間方向。
計算得分與重建
以下程式實作第一個例子。數值 SVD 傳回的是 V 的轉置,所以 Vt 的各行存放載荷方向。
import numpy as np
X = np.array([[12., 5.], [8., 5.], [10., 6.], [10., 4.]])
mean = X.mean(axis=0)
A = X - mean
U, s, Vt = np.linalg.svd(A, full_matrices=False)
k = 1
scores = A @ Vt[:k].T
reconstruction = scores @ Vt[:k] + mean
fractions = s**2 / np.sum(s**2)
squared_error = np.sum((X - reconstruction)**2)
print(fractions) # [0.8 0.2]
print(squared_error) # 2.0, up to rounding
數值程式可以同時反轉一個載荷和對應得分欄的符號,兩者相乘的重建不變。比較實作時,可檢查子空間、解釋方差和重建矩陣。若截斷位置兩旁的奇異值相同,最優保留子空間也可能不唯一;若該處存在嚴格間隔,子空間便確定,雖然基底向量的符號仍可改變。
常見錯誤
常見錯誤
把奇異值直接當成方差比例
第一例中,未平方的比例 22/(22+2)=2/3 不是解釋方差比例,正確值是 8/(8+2)=4/5。同時要區分:Vk 的欄描述特徵方向,AVk 的行描述觀測座標。混淆兩者通常首先造成矩陣維數不符。
總結
先中心化各欄、選定距離度量,再對中心化矩陣作 SVD。右奇異向量提供載荷,乘上這些方向便得到得分。協方差特徵值等於奇異值平方除以 n−1。首幾個主成分同時使保留方差最大、正交平方重建誤差最小;返回原特徵座標時,要加回平均值。
練習
思考檢查
1. 四個觀測的例子只保留一個主成分。求解釋比例、總平方重建誤差,以及新觀測 (11,7) 的重建。
思考檢查
2. 某中心化矩陣的正奇異值是 6、3、1。要至少保留 90% 方差,最少須保留多少秩?餘下平方重建誤差是多少?
思考檢查
3. 某協方差矩陣的特徵值是 5、5、0。第一載荷是否唯一?首二維主子空間是否唯一?
區分保留空間內的重複值,以及跨過截斷位置的重複值。
解答
解答 · 1. 投影並加回平均值
解釋比例是 4/5,平方誤差是 2。新觀測的中心化座標為 (1,2),第一得分為 1。中心化重建是 (1,0),加回 (10,5) 後得到 (11,5)。
解答 · 2. 從平方譜選取秩
平方總和為 36+9+1=46。一個主成分保留 36/46,低於 0.9;兩個保留 45/46,高於 0.9,故最少保留秩二。被捨棄的平方奇異值是 1,亦即餘下總平方重建誤差。
解答 · 3. 基底可變,子空間確定
特徵值五的特徵空間中,每個單位向量都使方差最大,故第一載荷除符號外仍不唯一。完整二維特徵空間則唯一,因為其特徵值與零有間隔。任意正交歸一基底都保留總方差 10;改換基底只會旋轉得分,不改變重建。
相關筆記