動機
低秩近似定理描述最優解,卻未單憑這個描述告訴我們如何準備觀測、計算表示,或處理一個新觀測。在特徵值計算開始之前,已有三項選擇:哪些觀測可以決定中心、哪些座標決定重建損失,以及保留多少個方向。這些都是建模決定。即使特徵值計算十分準確,也不能修補不合目的的損失,或從評估數據洩漏進來的資訊。
良好重建與穩定方向亦是兩回事。當最大的兩個方差非常接近時,許多方向的重建表現幾乎一樣;數據稍有改動,所報告的載荷向量便可能大幅轉動,而目標值只改變很少。反過來,迭代計算可以找到精確的特徵向量,卻找到並非最大的那一個。要負責任地解讀輸出,我們需要說明最優化問題、有限的收斂論證,以及譜間隙究竟控制甚麼。
本節處理實有限矩陣。以下結果只涉及觀測到的矩陣及指定的擾動。若要把它們變成總體保證,還須另行提出抽樣模型及協方差估計誤差界;這裏沒有假設這兩項條件已經成立。
定義
定義 21.1.1
(以訓練數據為中心的矩陣與重建損失)
設 為訓練觀測,且 。定義
以 作除數,令 的特徵值等於分數的均方值;改用 只會縮放特徵值,不改變特徵向量。若 各列標準正交,令 。分數矩陣為 ,重建的中心化各行為 ,每個觀測的訓練重建損失為 。
把 加回每一行,便得到原座標下的重建觀測。對新的列向量觀測 ,鎖定的訓練表示給出分數 及重建 。若改用評估集的均值,便已改變擬合程序。可以利用驗證數據選擇 或座標縮放,但整個選擇過程必須留在模型選擇之內,最終測試觀測則必須留在這個過程之外。
定義 21.1.2
(奇異值與兩種不同的誤差)
把奇異值分解寫成 ,其中 ,。把奇異值序列補零至 ,並在需要時把奇異向量補成標準正交基底。對 ,截斷矩陣為 。Frobenius 範數是全部矩陣元素平方和的平方根,所以 。譜範數則為
所以,譜近似控制單位輸入組合中最大的誤差;Frobenius 近似控制總平方誤差。兩者是不同目標,即使截斷奇異值分解同時解出兩個問題。
當 ,前列右奇異向量就是 的前列特徵向量,特徵值為 。當 ,可用零空間內的方向補足基底。兩種情況下,保留前列的 維特徵子空間都給出 ,但所選奇異值分解的首右奇異向量須生成該選定空間。在重複奇異值處,任意固定的分解未必符合這個配合條件。下方證明部分再次完整證明的 Frobenius 近似結果,因此給出訓練損失 。中心化亦保證 ;小樣本可以迫使某些特徵值為零,卻不表示總體在那些方向完全沒有變異。
定理與命題
定理 21.1.3
(譜範數下精確的最佳秩界)
對任何實 矩陣 及整數 ,
截斷奇異值分解達到譜誤差下界。截斷位置若有相等的奇異值,可以選擇不同的前列子空間。本定理不聲稱譜範數最小化解唯一;即使有間隙,亦不作這個聲稱。
定理 21.1.4
(有限的首特徵方向擾動界)
設 為實對稱 矩陣,,特徵值為 ,單位首特徵向量為 ,間隙為 。設對稱矩陣 滿足 。它的首特徵向量 除正負號外唯一。以 定義不分正負方向的夾角 ,則
若確實掌握所列的誤差界與間隙,定理特別適用於樣本協方差矩陣。但定理本身不會只憑數據便提供估計誤差界。
定理 21.1.5
(冪次迭代需要初始的首方向分量)
設正半定 滿足 。把單位初始向量展開為 ,其中 構成標準正交特徵基底,並假設 。定義 。若 為它與 不分正負方向的夾角,則對 ,
在精確算術中,每次乘法之後正規化會產生相同方向。若 ,此命題不保證得到首特徵方向。重複的最大特徵值不符合嚴格間隙假設;只把比值代成一,不能為指定的載荷給出嚴格壓縮界。我們把界寫於 ,以避免在 時另訂零的零次方慣例。
證明與思路
證明
(低秩映射必定漏掉一個前列組合)
當 ,用標準正交的零空間基底把右奇異向量補至 ;由於 ,這是可行的。令 為首 個右奇異向量的生成空間,維數為 。秩不超過 的 不可能在 上單射,所以存在單位 滿足 。利用左奇異向量的正交性,
因此每個容許的 都有至少 的譜誤差。餘項 的奇異值是 ,故其譜範數恰好達到下界,Frobenius 範數平方亦等於所列的和。零奇異值同樣包含在論證之內。證明給出最小值與可達性,並沒有找出每一個最小化矩陣。
為求完整,這裏亦證明 Frobenius 最優性。令 為投影至 行空間的正交投影矩陣。因為 ,互補右投影的正交性給出
在完整標準正交右奇異基底中,對 取 ,並寫 。每個 都在 內,總和為 。因此 :把至多 單位質量分配至最大的非負權重,可以令和最大。相減便證明 Frobenius 下界,並由 達到。這個證明不要求滿秩,亦清楚分開兩種近似目標。
證明透視
先數維數,再取加權平均
真正的想法是維數計算:秩至多為 的矩陣 不可能在 維空間 上是單射,所以 中有單位向量 滿足 ,而在 上的誤差就是 。左奇異向量的正交性把 變成 的加權平均,按次序它至少是 。秩的假設只在維數計算中用到。這個論證給出最小值,但沒有說明哪些矩陣能達到它。
證明
(間隙只讓我們在首方向以外作逆運算)
對每個單位 ,都有 。在 處計算 的 Rayleigh 商,得到 。第二特徵值至多為 :把 Rayleigh 商限制在 ,此處 ,再用對稱矩陣的極小極大刻畫便可。因此 ,證明首方向除正負號外唯一。
令 及 。把 投影至 ,得到
在這個子空間上,左邊算子的每個特徵值至少為 ,故逆算子的範數至多為 。所以 ,就是所需的角度界。要證明投影矩陣等式,必要時先改變 的正負號,再寫成 ,其中單位 。在 的生成空間上,兩投影之差的跡為零,行列式為 ,故特徵值為 ;在正交補空間上則為零。若兩方向重合,兩投影直接相等。逆算子這一步只需 ;定理較強的半間隙條件還保證擾動後首特徵值單一,並使角度界嚴格小於一。
證明透視
觀測到的間隙與統計保證是兩項條件
逆算子界使用總體或參照矩陣的間隙 ,以及另有根據的擾動大小 。只有最大的特徵值很大並不足夠,因為它可能與第二個幾乎相等。若 是總體協方差, 是估計,首先須用抽樣論證建立 的界,然後這裏的代數才把該界轉為方向界。一幅看來漂亮的載荷圖不能補上缺失的前提。
證明
(先追蹤不需要的特徵分量,再正規化)
的首係數為 。其餘係數的平方和為 。兩者的比值證明正切界,亦證明正規化的分母非零。在同一特徵基底展開單位 ,得到
因為全部特徵值非負,不需要的分量中最大模長就是 。對一般對稱矩陣則未必如此:普通冪次迭代追隨絕對值最大的特徵值,而它可以是負數。協方差矩陣避免了這個問題,卻不會避免初始首分量為零或有限精度誤差。
完整例子
例題 21.1.6
(逐一擬合、壓縮並重建全部觀測)
取四個訓練觀測 、、、。均值為 。中心化各行為 、、、,所以
單位特徵向量為 、,特徵值分別為八及二。 的奇異值是 及 。保留一個方向,分數為 。把每個分數乘以 ,得到重建中心化各行 。加回訓練均值,便得到 。
每個殘差的長度平方為二,故總平方重建誤差為八,每個觀測的誤差為二,正好等於 。譜誤差則為 ;它既不是 Frobenius 範數平方,也不是每個觀測的損失。所保留的方差比例是 ,只描述訓練重建,不是分類準確率。
對新觀測 ,中心化向量為 ,分數為 ,重建為 ,平方重建誤差為二。計算中沒有利用評估集重新定中心,也沒有重新計算方向。
例題 21.1.7
(執行冪次迭代並解讀停止證據)
對同一 ,從 開始。 與 成比例,所以 ,而
一次乘法給出 ,商為 。兩次給出 ,商為 。以下只用 Python 標準程式庫的程式執行逐次正規化迭代。程式明確指定四步預算,並沒有從輸出暗中推論停止準則。
from math import sqrt
z = (1.0, 0.0)
for t in range(5):
Cz = (5*z[0] + 3*z[1], 3*z[0] + 5*z[1])
rayleigh = z[0]*Cz[0] + z[1]*Cz[1]
residual = sqrt(sum((Cz[j] - rayleigh*z[j])**2 for j in range(2)))
print(t, f"{rayleigh:.9f}", f"{residual:.9f}")
if t < 4:
length = sqrt(Cz[0]**2 + Cz[1]**2)
z = (Cz[0]/length, Cz[1]/length)
0 5.000000000 3.000000000
1 7.647058824 1.411764706
2 7.976653696 0.373540856
3 7.998535514 0.093727117
4 7.999908449 0.023437142
殘差衡量是否接近某個特徵向量。要把它辨認為首特徵向量,仍須使用非零的初始首分量及正譜間隙。對大矩陣,可以直接計算 ,不必儲存 。直接奇異值分解則避免明確形成協方差矩陣,後者最大與最小非零特徵值的比值,是 相應奇異值比值的平方。兩種方法都不會消除訓練中心化或遵守所選損失的需要。程式使用浮點算術;所印數字與精確量 及 在所列精度一致。一般浮點誤差分析與通用特徵值求解器,不屬這個二維例子的範圍。
例題 21.1.8
(間隙把非對角擾動轉為角度界)
設 , 的對角元素為零,兩個非對角元素都為 。其譜範數為 ,而 。所以定理給出 。直接對角化得到
精確角度符合界,但界不是等式。相反, 加上 後,首方向會由 變成 ,而擾動範數只有 。當 ,任意小的擾動都可造成直角改變,因為參照間隙也同時趨近零。小擾動的嚴格假設恰好在這裏失效。
概念視角結構
子空間穩定性、重建及標籤資訊回答不同問題
重複的首特徵值可以令個別載荷無法唯一辨認,但整個特徵空間仍有意義。很小的間隙可以令載荷不穩定,而重建仍然良好。即使一個高方差方向十分穩定,也可以遺失類別資訊。例如,兩個等先驗高斯(Gaussian)類別的均值為 及 ,共同類內協方差為 ,總協方差便是 。最大的主座標在兩類中有完全相同的分佈,因此不含標籤資訊。應分別報告所選秩、訓練損失、間隙及評估目標;任何一項都不能取代其餘幾項。
常見誤解
反例模式
零殘差也可以對應錯誤的特徵向量
對 ,若從 開始,冪次迭代永遠留在 。殘差 精確等於零,但 Rayleigh 商只是一而非四。只有小殘差並不能證明找到首分量。定理需要非零的初始首係數,而例子違反這個條件。在適當分佈下隨機起點可以降低此失敗風險,但確定性成功的聲稱仍須交代前提。
常見錯誤
(中心化與改變單位會改變最優化問題)
對觀測 、,未中心化的二階矩矩陣是 。未中心化秩一擬合保留第一軸,把表示能力花在均值上。中心化協方差是 ,因此中心化主成分保留第二軸,加回均值後可以精確重建兩個觀測。兩個計算都可以數值正確,卻解答不同問題。
同樣,若中心化協方差為 ,把第一座標乘以 ,協方差便變成 ,首方向由第一軸轉為第二軸。縮放後的歐幾里得(Euclidean)重建,會按縮放因子的平方加權原座標平方誤差。因此,在稱一個表示最優之前,必須交代單位與損失。用訓練數據估計標準化,是合理的另一種度量,並不是原座標主成分的不變版本。
小結
以訓練數據為中心的奇異值分解,給出分數及處理新觀測的完整重建規則。截斷同時最小化總平方矩陣誤差與最壞單位組合誤差,但兩者報告的數值不同。譜間隙把有根據的矩陣擾動界轉為方向穩定性。對正半定矩陣,所證明的界保證:當起點包含非零首分量且 ,迭代按幾何速率收斂至首方向。重複的最大特徵值不在這個定理的範圍,所以此界不會在該情況下選定事先指定的載荷。這些有限結果支持謹慎計算,卻不證明預測表現或未知的總體協方差。
練習
快速檢查
(在四觀測擬合例中,用鎖定的秩一表示重建新觀測 。計算平方誤差,並解釋為何不一定要保留它的第二分數。)
先減去訓練均值,再計算首分數。
解答 · 答案
中心化觀測為 ,首分數為 。重建中心化向量為 ,故重建是 。殘差為 ,平方誤差為八。被捨棄的第二分數是 ,其平方同樣為八。秩一是刻意捨棄這個座標;這個觀測的誤差大,不會推翻訓練最優性,只表示所選表示對它的重建可能欠佳。若因此改變秩,便是一項新的建模決定,須遵守原定的選擇程序。
快速檢查
(對冪次迭代例,找出最小非負整數 ,使首方向夾角的正切至多為 。計算該次迭代精確的 Rayleigh 誤差。)
精確正切是四分之一的冪。
解答 · 答案
需要 。因為 而 ,最小迭代次數為五。精確 Rayleigh 誤差為 ,約為 。這是指定矩陣及起點下的確定性計算,不是普遍的五步規則。若起點更靠近首方向的正交補,初始正切因子便會令所需步數增加。
快速檢查
(對稱參照協方差的首兩個特徵值為 及 。另一個論證把協方差擾動的譜範數限制在 以內。求首投影矩陣誤差的譜範數界。若只知道擾動界為 ,同一論證能否保證嚴格小於一的界?)
代入數字之前,先檢查定理的嚴格假設。
解答 · 答案
間隙為二,且 ,故投影矩陣誤差至多為 。若只有 ,便不符合嚴格假設 。形式上代入會得到一,但那只是秩一正交投影之間的平凡上界,沒有給出嚴格的方向控制。事實上, 加上 後,最大的特徵值重複為六,此時可以選取與原方向正交的首方向。因此不能保證唯一的擾動後首直線。
快速檢查
(設 ,只保留秩一。給出一個截斷最優解、兩種近似誤差,以及另一個譜範數最優解。解釋為何這裏的 Frobenius 最優秩一矩陣仍然唯一。)
譜目標容許保留的對角元素稍有改動,只要被捨棄的三仍是最大誤差。
解答 · 引導解答
截斷矩陣為 。譜誤差為三,Frobenius 誤差平方為 ,Frobenius 誤差為 。另一個秩一矩陣 的譜誤差仍為 ,故同樣譜最優,事實上,每個 在 時都有譜誤差三; 的 Frobenius 誤差平方是十一。對 Frobenius 秩一近似,嚴格間隙 迫使上述行空間跡界採用 ,而互補投影界取等號又要求 。這固定係數為五及兩條首奇異直線,所以最優矩陣唯一。不過兩個單位奇異向量仍可同時反號。談唯一性時,必須說清楚目標,並區分矩陣與它的分解因子。