為甚麼要選取核矩陣的若干列?
核 Gram 矩陣記錄觀測特徵向量兩兩之間的內積。有 個觀測時,矩陣便有 個元素,即使其中大部分幾何結構只需要少數方向就能描述。減少計算的一個方法,是挑選 個觀測作為地標,只計算各觀測與這些地標的相似度,再用它們重建其餘內積。
重建不能只把所選的列直接相乘。這些列相當於以地標向量量度的座標,而地標未必互相正交,甚至未必線性無關。地標本身的 Gram 矩陣告訴我們如何校正這套座標。地標線性無關時可用逆矩陣;線性相關時則用偽逆。所得的 Nyström 矩陣有一個很有用的解釋:先把每個特徵向量正交投影到地標的生成空間,再計算 Gram 矩陣。
本節針對一個固定的有限半正定矩陣,完整證明這個解釋。它會準確指出哪些數據被保留、哪些方向被捨去。論證不需要隨機地標,也不表示任意選法都準確,更不表示擬合所得的預測函數能在新數據上有良好表現。
矩陣、地標與奇異情況下的逆運算
設 對稱且半正定,簡記為 PSD;即每個 都滿足 。選取互異指標 ,其中 ,並設
所以 包含所選的列,而 是相同指標的行、列相交所得的主子矩陣。 必須來自同一個 PSD 矩陣,這個假設很重要。不能把一個無關的 階半正定矩陣代入 ,便沿用以下結論。
定義 14.1.1
(半正定偽逆與 Nyström 矩陣)
把 的正特徵值部分寫成正交特徵分解 ,其中 、,而 的對角線包含 個嚴格正的特徵值。定義
偽逆在 上的作用為零。當 ,以上乘積按零矩陣理解,而 有零個列。若 可逆,則 。
即使選了 個地標指標,特徵矩陣 也只有 個列。重複的特徵方向不會產生新資訊。定義直接給出 半正定,而且秩至多為 。但要證明它與 的差仍半正定,以及所選列能精確重現,還需要進一步論證。
對稱矩陣的記號 表示 半正定。這是二次型的大小關係,不是逐元素的不等式。以下以 表示歐氏(Euclidean)算子範數,以 表示跡。
用投影理解整個構造
定理 14.1.2
(地標投影與半正定誤差)
對上述有限 PSD 矩陣與地標集合,選任一分解 ,其中 ,並設 。譜定理保證這種分解存在;例如可以取 、。定義
則 是投影到 的正交投影,而且
此外 。等式 成立,當且僅當 的所有行向量轉置後均屬於地標生成空間 ;等價地,。
實際構造投影,而非直接假定
證明由 的特徵向量構造地標生成空間的一組標準正交基,令 明顯是投影。
證明
(標準正交地標方向給出投影)
首先, 且 。若 是 對應正特徵值 的單位特徵向量,定義 。直接相乘可得
這些向量構成 的一組標準正交基。為甚麼沒有漏掉值域中的方向?因為 ,所以 。任一向量 的零特徵值分量,經 作用後都變成零。因此正特徵值對應的向量已生成整個值域,並且
這個矩陣固定地標生成空間中的向量,並把其正交補中的向量映至零。特別地, 且 。代入 ,便證得 。對每個 ,都有
這樣便證明了誤差半正定;我們沒有假定兩個無關 PSD 矩陣的差仍為 PSD。每個地標行向量本來就在投影目標空間內,所以它與任一投影後數據行的內積,等於原來的內積。以矩陣表示,,於是 。
最後, 等價於 。一個方向直接成立;另一方向可取 的跡,所得正是所有殘差長度平方之和。因此每個數據特徵都在地標生成空間內。地標行空間本來就是數據行空間的子空間,故維數相等就等價於兩個空間相同。這兩個維數分別為 與 。
證明透視
地標矩陣奇異時,為甚麼方程仍然相容?
證明只在一處用到半正定假設:分解 ;之後全是 各行的幾何。第二個假設是 與 來自同一矩陣,這令 與 共用因子 。
關鍵一步是 ,從而 。它用了兩次。第一,它說明 的正特徵向量已生成全部地標方向,所以 沒有遺漏;第二,它說明 奇異不會造成不相容:若 ,則 ,於是 ,即 。偽逆捨去的組合本來就等於零,從不丟掉某個隱藏的非零所選列。一旦知道 是正交投影,半正定殘差與所選列的精確重現都只是一行推論。下面的反例是一個不定矩陣,正好是 的情況。
奇異 Schur 補與不可省略的假設
把觀測重新排序,令地標在前。寫成
式子 稱為廣義 Schur 補。 奇異時,即使已知這個補與 都半正定,仍不足以推出任意對稱區塊矩陣半正定。
定理 14.1.3
(奇異區塊矩陣的準確判準)
實對稱矩陣 半正定,當且僅當以下三個條件同時成立:、,以及 。
兩個方向都建基於同一個二次型計算。
證明
(核向量迫出值域條件,配方完成其餘部分)
若 半正定,其主區塊 也半正定。對 ,固定任一與下方區塊維數相同的向量 ,考慮向量 的二次型。它等於 ,而且對每個實數 都必須非負。因此 。取正交補,並利用 對稱,就得到 。
在這個值域條件下,。配方給出:對任意 ,
取 ,便見到 半正定必然要求 Schur 補半正定。反過來,若三個條件成立,配方後的兩項都非負。判準因而得證,也解釋了 Nyström 殘差為甚麼在非對角區塊等於零。
反例模式
偽逆不能修補不定的輸入矩陣
取 ,並選第一個指標。此時 、、、。廣義 Schur 補等於零,但 是不定矩陣:向量 的二次型等於 。值域條件失效,因為 ,而 。公式產生 ,連所選列也不能重現。原來的 PSD 假設正好排除了這種不相容情況。
地標線性相關時的完整計算
例題 14.1.4
(兩個地標,只保留一個方向)
使用四個特徵行 、、 與 。它們的 Gram 矩陣為
選首兩個觀測,則
唯一的正特徵值為 ,對應特徵向量是 ,所以 。把這個列記作 ,並設 ,便有
把 取為由上述特徵行組成的 矩陣,則 :地標保留第一個座標,捨去第二個。所選列完全準確,但第 項由 變成 。因此,精確重現所選列,比精確重現整個矩陣弱得多。
投影第三個特徵時,解 可得 。每個這樣的係數向量都重建同一個投影特徵 ;偽逆選出歐氏長度最小的係數向量。若把第三個觀測也加入地標,便能生成兩個座標方向,令近似完全準確。只增加另一個首個特徵的倍數,則不會有這個效果。
沒有抽樣定理時,仍能驗證甚麼?
令 是 第 行的轉置,並設 ,則 。特別地,
元素界來自 Cauchy–Schwarz 不等式。範數界則因 的所有特徵值非負,故最大特徵值不超過它們的和。這些都是所選有限矩陣的確定性誤差憑證。計算對角殘差,除了所選列外還需要原矩陣的對角元素,但不必取得所有未選觀測之間的兩兩元素。
例題 14.1.5
(只用所選列計算誤差憑證)
回到以 為地標的四點例子,並假設只知道 的對角及所選列 。第 行有 ,而
所以 。第 行有 ,所以 ;地標行給出 。憑證為 及 。完整計算得 ,其中 、:兩個界在此都達到,因為殘差秩為一。若殘差秩較高,跡界會高估算子範數。
常見錯誤
(把 PSD 次序誤讀為逐元素不等式)
並不表示 。取特徵行 、、,只以第一個作地標。投影到第一座標後,另外兩行都變成 ,於是 ,而 ,。只有對角殘差保證非負;非對角殘差元素只由 控制其絕對值。
在精確算術下,增加地標不會令這個 PSD 誤差變差。若 的每個指標也出現在地標指標組 ,對應的特徵空間就互相包含。把較大的空間分解成較小空間及一個正交補,可知 是正交投影。因此 ,而 。新地標若與原有地標線性相關,空間並無改變,近似也不會改善。
例題 14.1.6
(合法的選法也可以漏掉主要方向)
對 ,只選第二個指標,則 ,算子誤差為 。改選第一個指標,誤差便是 。兩個近似都重現所選列,而且都有 PSD 殘差。把 換成更大的數,可令誤差比任意大。所以對任意選法,僅知道地標數目並不能保證相對精度。
若 來自真正的 PSD 核 ,同一構造亦能在訓練集以外定義核。地標輸入是 。設 ,並用
這個核半正定,因為它有特徵向量 。在原來的再生核空間中,它等於先把核截面 與 投影到地標截面生成空間,再取內積。同一投影證明顯示 在每個有限集合上都是 PSD。不過,這並沒有給出整個定義域上的一致小誤差界。訓練輸入的殘差很小,仍可能與某個未觀測輸入的巨大殘差同時發生。
數值修改會改變結論
定理使用的是精確偽逆。實際數值計算中,極小的正特徵值需要用容許誤差作取捨。只保留部分正特徵模式,相當於投影到更小的子空間;殘差仍然 PSD,但可能失去所選列完全相等的性質。數值容許誤差不能被說成精確的代數秩判定。
另一種修改是以 代替 ,其中 。在 下,中間的矩陣變成 。它在正地標方向的特徵值為 ,其餘特徵值為零。因此它介乎零與單位矩陣之間,而且只有平凡情況 才是正交投影。正則化近似仍介乎零與 之間。若 ,所選的 區塊會改變,所以失去所選列的精確重現。對只有一項的矩陣 ,取 ,近似是 ,並非 。這種地標正則化,也與稍後擬合標籤時使用的嶺懲罰不同。
概念視角結構
三個問題,需要三種不同證據
投影定理問的是近似有沒有尊重核的幾何結構。殘差估計或抽樣定理問的是近似對某個指定矩陣有多準確。學習定理問的則是擬合函數在新觀測上的表現。半正定性回答第一個問題,不能代答另外兩個。Nyström 座標使用選出的數據地標;固定地標後,得到的是確定性的下方近似 。前一篇的隨機特徵構造,則在指定特徵抽樣分佈下給出 的逐元素無偏估計;它在 PSD 次序下未必小於 。
練習
快速檢查
(設 ,其中 ,只選第二個指標作地標。計算 、、 與 。特徵座標的正負號為甚麼無關緊要?若所選的 座標為零,情況有何改變?)
解答 · 答案
此時 ,而 。把這個純量區塊的正特徵值對應單位特徵向量取為 ,便有 ,所以 。把每個特徵都乘以 ,不會改變兩兩內積。若所選座標為零,則 且 ,近似為零;只有整個向量 都為零時才準確。因此一個秩一矩陣可以用一個有資訊的地標恢復,但不是每個地標都可以。
快速檢查
(設 、、。準確求出哪些實數 使整個區塊矩陣半正定,並以前兩個指標作地標,計算 時的 Nyström 殘差。)
解答 · 答案
偽逆為 。列 屬於 的生成空間,亦即 ,而且 。因此奇異區塊判準給出的條件恰為 。當 ,完整殘差為 ,跡與算子範數都等於 。若 ,取 及下方係數 ,二次型便等於負數 。
快速檢查
(未選觀測的對角殘差為 與 ,所有已選觀測的殘差均為零。求這兩個未選觀測之間殘差元素絕對值的上界,以及 的上界。兩個上界能否同時達到?)
解答 · 答案
Cauchy–Schwarz 給出 。跡界給出 。兩界都可由秩一的未選區塊 達到;它是兩個長度分別為 與 、互相共線的殘差特徵之 Gram 矩陣。另加一個與它們正交的地標特徵,即可把它實現為某個 PSD Gram 矩陣的殘差。
快速檢查
(在 上使用線性核 ,唯一的訓練輸入兼地標是 。計算訓練矩陣誤差,以及 處的核對角誤差,其中 。這對推斷整個定義域的誤差界有甚麼啟示?)
解答 · 答案
訓練矩陣及其近似都為 ,所以訓練誤差是零。地標只記錄第一個座標,因此 。在 ,真實對角為 ,近似對角為零,所以對角誤差為 ,在這個無界定義域上可以任意大。若沒有進一步假設控制未觀測方向,有限訓練集上的精確性不會給出定義域上的一致誤差界。