為甚麼有些地標較有資訊量?
一個地標保留一個特徵方向。如果所有地標都在同一方向上,重複選取它們仍無法恢復另一個方向,即使所選對角元素很大也一樣。因此,我們需要一個把各列之間的相關性考慮在內的抽樣準則。嶺槓桿分數便在指定尺度下衡量每一列:比這尺度小得多的方向權重較低,比它大得多的方向則接近計作一個方向。
本節的保證只針對一個固定、有限的正半定(PSD)Gram 矩陣。我們刻意使用初等方法:以二階矩計算和 Markov 不等式取代更精細的矩陣集中不等式。所得的地標數目可能很保守,但能清楚展示有效維數、正則化尺度,以及漏掉某些方向的非零概率為甚麼出現在結論中。
分數和獨立抽樣
定義 16.1.1
(嶺槓桿分數與有效維數)
設 為對稱 PSD 矩陣,。定義
稱為索引 在尺度 下的嶺槓桿分數, 稱為有效維數。
若 ,則 。因此 、,而 。所以 :它按所選尺度,以分數計算每個特徵向量的貢獻,一般不是整數。
概念視角分析
把槓桿分數看作正則化重構代價
令 ,每個分數都是一個小型嶺問題的最優值:
令梯度為零得 ;由於各矩陣可交換,代入這個最小點便得最優值 。取 的代價是 ,取 的代價是 ,所以 。若某列的特徵向量可以由一個範數小的特徵向量組合重現(誤差以 計價),該列的分數便小;這正是分數「考慮各列之間相關性」的精確含義。
當 時,。獨立地、有放回地抽取 ,其中
重複抽中同一索引仍是有效抽樣,但不會增加新方向。設 為抽中過的不同索引所組成的集合,,。近似矩陣是 。等價地,令 ,而 為到所有 對應向量 的生成空間的正交投影;先前的地標投影恆等式給出 ,所以 。
如果 ,則 為零向量。第一個因子可逆,故 ;這列沒有特徵方向,給它零概率不會遺漏任何方向。若 ,不必抽樣,直接設 ;以下殘差結論自然成立。
例題 16.1.2
(重複的列分享槓桿)
設 、。特徵值為 和 ,對應 的單位特徵向量是 ,所以
單獨一列 的分數是 。把它重複一次,每個分數降至 ,總和 仍小於一:兩列只帶一個方向,在此尺度下按分數計算。以上述觀點看, 是第一個特徵向量的最優重構,代價為 。兩個概率都是 ;由於 秩為一,任何一次抽樣都給出 。定理在 、 時要求 ,即 :這個充分抽樣數目正確,卻沒有利用這種精確結構。
常見錯誤
(按對角元素抽樣)
對角元素忽略了相關性。對 和 ,按 成比例抽樣使用 ;槓桿分數為 、,給出 。抽五次時,對角抽樣漏掉第三個方向的概率是 ,槓桿抽樣只有 。
有限樣本定理
定理 16.1.3
(初等嶺槓桿分數保證)
假設 、、 和 。如果
則上述獨立槓桿抽樣以至少 的概率滿足
這是在尺度 下的絕對譜誤差界,並非每個方向相對於 的誤差界。
證明分兩步:先估計白化向量的樣本協方差,再把這個估計轉化為 Nyström 殘差。
證明
(第一步:白化座標中的樣本協方差)
令 。各矩陣均為 的函數,故可交換;因此
對一次抽樣 ,定義 。其分母幾乎必然為正,且 。若 ,利用獨立性和 的零均值,得到
這裏 ,而交叉項因獨立而消失。由 ,對 Frobenius 範數的平方使用 Markov 不等式,可知 的概率至少為 。
第二步只用到剛得到的事件,不再涉及其他概率。
證明
(第二步:由方向覆蓋得到 Nyström 殘差)
在該事件上,取任意與全部抽中 正交的 ,設 。此時 與每個抽中的 正交,所以 。因此
移項得 ,其中 。對任意 ,取 。這個 與地標生成空間正交,且
若 ,所需不等式立即成立;否則除以 再取平方。於是對所有 有 ,即 。結合概率界和所假設的抽樣數目,定理得證。
證明透視
白化的作用
概率一步只用到抽樣獨立,以及 時 ,從而 ;具體選擇 則使 恰好等於 ,由 Cauchy–Schwarz 不等式,任何其他選擇都會使這個和更大。關鍵一步在第二步。樣本協方差只控制抽中的白化向量所生成的空間,殘差卻關乎未被覆蓋的原始特徵方向。對未覆蓋的方向 ,改用 檢驗;正因為白化與反白化互相抵消, 與每個抽中的 正交,於是 在 上為零,而算子範數事件便控制了 。假設 使 可逆,這是座標轉換所需的; 則容許移項。最後的 Cauchy–Schwarz 一步把對未覆蓋方向的控制轉為 。單純計算地標個數無法提供這些。
兩個方向和具體抽樣數目
例題 16.1.4
(對角 Gram 矩陣)
設 、。分數為 和 ,故 ,。抽一次時,選第一個索引的殘差為 ;選第二個時為 。後者以 的概率出現,說明為何需要概率形式的保證。
取 、,定理給出的充分抽樣數目為 ,故 足夠。它保證誤差不超過 的概率至少為 。這不是說需要 79 個不同地標:這裏只有兩個。事實上,誤差大於 當且僅當 79 次都選中索引 2,概率為 。本例中的定理雖正確,卻非常保守。
反例模式
高概率並非必然
同一對角例子說明:不論有限的 有多大,獨立抽樣仍可能漏掉主要方向,其概率為 。而 亦不會給出某個 的相對界 :一旦漏掉正的對角方向,該方向的殘差恰等於 的該方向。
這對嶺預測有甚麼意義?
固定響應向量 ,比較訓練點上的擬合向量
兩個矩陣均為 PSD,故各正則化逆矩陣的算子範數不超過 。利用預解式恆等式,
所以在定理的同一事件上,。若 並要求誤差不超過 ,取 便足夠。比較中兩處採用同一個 和上述未正規化慣例;若損失函數使用 ,須一致地代入 。結果本身沒有說明未見輸入、帶噪標籤或總體泛化的表現。
例題 16.1.5
(漏掉一個方向後比較擬合向量)
回到 、,並假設每次都抽中索引 1,於是 、。對 ,
預解式公式與此一致:。這裏 ,恰好是 時定理的水平 ,而上界給出 。它鬆了約 倍,因為它把在漏掉方向上等於 的 換成範數界 ,而且 並非集中在該方向上。
常見錯誤
(把分數或有效維數當作誤差估計)
分數 決定抽取哪個索引; 控制上述充分抽樣數目; 衡量實際得到的有限矩陣誤差。它們都不是測試風險的估計。此外,計算精確分數需要完整矩陣的資訊,因此這定理本身不構成快速算法。
練習與解答
快速檢查
(設 、。求各分數、有效維數及正的抽樣概率。)
對角矩陣有 。
解答 · 答案
分數為 ,。所以 、、。零座標不會被抽中,亦不帶特徵方向。
快速檢查
(對例中的 和相應概率, 次抽樣後 Nyström 近似等於 的精確概率是多少?)
只有兩個索引都出現過,近似才精確。
解答 · 答案
兩個索引必須都出現。兩個互斥的失敗事件分別是每次都抽中 1 和每次都抽中 2,因此答案為 。當 時結果為零。
快速檢查
(設 且 。證明一次槓桿抽樣幾乎必然給出 。)
先求 的特徵分解。
解答 · 答案
有唯一正特徵值 ,而 。分數為正的索引恰好是 的索引。任何這樣的一列都生成整個秩一特徵空間,因此投影恆等式給出零殘差。
快速檢查
(如果 而 奇異,上述證明在哪裏失效?)
證明中哪個矩陣必須可逆?
解答 · 答案
及其逆不再存在於整個空間上。特別是,用來比較未覆蓋特徵方向和白化方向的變量替換不再按上述形式有效。或可在 的值域上另作證明,但那不是本定理的證明。