動機
核方法不用逐一寫出所有特徵,也能表示非線性函數。不過,這項便利仍留下必須處理的計算對象:訓練輸入之間的核值矩陣。若有 個輸入,矩陣便有 個元素。隨機特徵構造以 代替它,其中 只有 列。當 適中時,儲存特徵矩陣並在這些列上擬合線性模型,可以減少計算負擔。
我們要分開回答三個問題。近似是否保留核方法所需的半正定幾何?要抽多少特徵,才能在指定數據集上控制近似誤差?矩陣的誤差又會怎樣改變擬合預測?以下會給出條件完整的初等界。這三個答案本身都不是對新觀察預測能力的保證。
這裏的隨機性首先來自特徵抽樣;輸入及標籤暫時固定。因此,觀察數 與隨機特徵數 有不同作用。增加 是改善一個指定的計算近似,並沒有增加訓練觀察。
定義
定義 12.1.1
(純量隨機特徵表示)
設 為輸入集, 為概率空間。對每個固定 ,實值特徵 對 可測,並假設每個 均有 。定義
令 ,獨立抽取同分佈於 的 ,並設
由 Cauchy–Schwarz 不等式,定義 的期望存在。固定 個輸入 ,容許重複。定義 、,以及 。每一列是同一次特徵抽樣在所有輸入上的值。同一個擬合模型的訓練及測試特徵映射,必須使用同一組抽樣。
集中定理另假設存在已知 ,使選定輸入同時滿足:對 -幾乎處處的 ,有 。整個輸入域上的一致界當然足夠,但比這個有限數據假設更強。記 ,並以 表示歐氏(Euclidean)算子範數。全文的 表示自然對數。除非另有說明,下文的概率只針對獨立特徵抽樣。
概念視角結構
把 Gram 矩陣看成二階矩矩陣
令 。則 是這個隨機向量的二階矩矩陣,而 是它的樣本二階矩矩陣。於是半正定性、秩上界和無偏性,都只是 個秩一外積平均的熟悉性質;近似 也就變成估計 中一個隨機向量的矩的問題。
定理/命題
定理 12.1.2
(無偏半正定近似與有限數據集中)
與 都半正定,且 。逐元素有 。在上述有界假設下,對任意 ,
因此,若 且
則至少以 的概率,每個元素的誤差都不超過 ,算子誤差不超過 。此外,
因子 是元素數目,不表示各元素獨立。概率上界可以大於一;此時它只是沒有提供有效資訊。利用對稱性可略微改善計數,這裏保留較簡單而仍正確的常數。
定理 12.1.3
(半正定 Gram 擾動下的嶺迴歸預測穩定性)
設 為任意實對稱半正定 矩陣,,。令 ,定義
若 ,則
特別地,在首個定理的事件上,。這些都是給定矩陣後的確定性擾動結論,不需假設標籤的分佈。
若 , 正是特徵嶺迴歸的訓練預測;其目標為最小化 。正規方程是 。直接相乘可核對,唯一解為 。因子 已包含在 中;這個約定不需要再把 除以 。
證明思路或證明
幾何與無偏性的真正意思
證明
(半正定性、秩與無偏性)
對任意 ,利用有限求和及特徵表示可得
因此,即使抽出的近似很不準確,它仍然半正定。 的列數立即給出秩上界。對每個元素的平均取期望,便證明無偏性;這一步其實不需獨立性。獨立性會在方差及指數界出現。無偏的對象是矩陣,不是對矩陣求逆或擬合預測等非線性操作。
有界變量的指數估計
以下直接證明集中步驟,而不訴諸一個未具名的不等式。
證明
(傾斜方差界,再對元素用聯集界)
設實隨機變量 落在 ,定義 。有界性容許對每個實數 微分。在密度正比於 的傾斜概率測度下, 就是 的方差。取 ,則
因為 ,把二階導數界積分兩次,就得到對所有實數 都成立的 。若 ,沿 到零的線段積分,同樣得到這個非負二次界。
固定 ,設 。這些變量獨立,落在 ,期望為 。聯合指數矩因此分解成乘積。對 應用 Markov 不等式,得
選 ,右側成為 。對 重複論證,再加上兩側尾概率。最後對 對指標用聯集界,便得到矩陣概率估計。解出令右側不超過 的條件,就是特徵預算;實作時須向上取整數。
若 ,則對任意單位向量 ,先用三角不等式、再用 Cauchy–Schwarz,給 。把 個座標界平方後相加,得到 。至於均方結論,獨立性給出每個平均元素的方差等於單次方差除以 。把這些方差沿所有元素相加即可;又因 ,每個方差至多 。平方 Frobenius 範數本來就是元素平方和,所以不會出現跨元素的協方差。
證明透視
真正需要哪一種獨立性?
三個不同的事實支撐這個證明,各用不同的假設。有界性 (只在所選輸入上)只經由每個乘積 的範圍 進入,供傾斜方差界使用。抽樣的獨立性只用來把指數矩 分解成 個相同因子;正是這個分解把單次抽樣的控制變成關於 的速率。
矩陣各元素共享這些抽樣,通常並不獨立。最後的聯集界只是把概率相加,不需要元素之間獨立,所以代價是計數 ,而不是任何協方差計算。若每一列都複製同一個隨機特徵,沿 的分解便失效;增加列數也未必改善準確度。算子界 是另一個確定性步驟,與概率無關。
從矩陣誤差到擬合預測
證明
(解算子恆等式與預測的消去)
半正定性保證 及 的所有特徵值都至少為 ,故兩個逆矩陣的範數至多 。設 、。直接相乘可證解算子恆等式
把恆等式作用於 ,再乘上三個算子範數界,便得到係數估計。對預測而言,關鍵消去是
相減得到 ,從而得到預測界。此證明不要求兩個 Gram 矩陣有共同特徵向量,也不要求誤差小於 。即使 或輸入有重複,正則化參數為正仍保證可逆。
同一個位移 也可以逐個特徵值理解。
概念視角代數
正則化如何提供譜緩衝
在 Gram 特徵值為 的方向,訓練嶺迴歸把標籤座標乘以 。正位移 防止除以接近零的特徵值。上面的擾動證明即使沒有共同特徵基也成立;純量圖像則解釋了正則化參數趨近零時,界為何變差。這個圖像不能用來把定理的參數直接設成零。
例題
例題 12.1.4
(兩點核與一次精確的 Gram 抽樣)
取 ,以相同概率抽 ,定義 、。此時 ,。在輸入 上,精確 Gram 矩陣是 。
抽四個特徵,其中三個 ,一個 。依此排序,
特徵值為 及 ,均非負。逐元素及算子誤差都等於 。若 次抽樣中有 次是常數特徵,非對角估計便是 ,而兩個對角元素一直精確等於一。由 ,非對角元素無偏。 時恰有 個常數特徵的概率是 。上面的矩陣是一個可能結果,不是平均矩陣。
例題 12.1.5
(三角特徵與保守的特徵預算)
輸入為實數,令 均勻分佈於 ,設 。乘積恆等式給
第二項積分為零,所以核是 。核值可以是負數,但特徵表示保證 Gram 矩陣半正定。這裏 ,;這個有界估計不用限制固定輸入座標的大小。
若 、、,特徵界為 時,充分預算是 。對本例的三角特徵,則是 。這些是最壞情況的充分預算,並非聲稱較少特徵一定失敗。所得矩陣範數界只有 ;每個元素都準確,不表示算子誤差同樣小。
例題 12.1.6
(同一矩陣誤差經嶺迴歸後的影響)
回到兩點例,選 、,所以 。標籤向量在 的特徵值一方向,亦在抽樣矩陣的特徵值二分之一方向。因此
預測差的範數為 。確定性算子誤差界用 ,給出 ,正確但不緊。由一般逐元素誤差推出的界更鬆。保證可以有用,卻未必要精確預測實際誤差。本例也分清兩種改動:輸入與標籤完全不變,只改變特徵近似,擬合預測也會改變。
常見錯誤
反例模式
特徵二階矩有限,不等於指數集中
令 的密度為 ,對所有 設 。此時 而 。特徵二階矩存在,核是常數 。估計器是 個獨立 的平均,所以仍然無偏且半正定。
對每個整數 ,事件 迫使平均值超過四。由 時的 ,可得
此多項式下界最終超過任何固定正常數 所給的 。所以不能只把有界特徵假設換成特徵二階矩有限,然後保留原集中定理。其他尾部條件或穩健估計器需要另外論證。
常見錯誤
(把有限列表的界推廣到整個輸入域)
有限數據集亦是這個聯集界結論的重要部分。看一個極端但有界的例子:輸入是 的所有有限子集 , 在 均勻抽取,設 。對每個固定有限 ,特徵幾乎必然為零,故真核恆為零。但在 次抽樣後選 ,就有 。於是對整個輸入族取上確界,對每一份實現的抽樣列表,誤差都等於一。這沒有違反固定有限列表定理,因為 是看過抽樣後才選的。要從有限網推廣到連續域,需要規律性及覆蓋論證等額外控制;單靠有界性並不夠。
若 配備 sigma-代數, 聯合可測, 固定,訓練輸入隨機且與特徵抽樣獨立,而且同一個 對所有可能輸入都有效,便可先以輸入為條件應用定理,再平均條件失敗概率,保留相同概率界。如果輸入是看過這批特徵抽樣後才選的,這個條件化論證便不適用。
常見錯誤
(把訓練預測比較誤讀為測試或總體保證)
嶺迴歸結論比較的是同一數據上的兩個訓練預測向量。對新測試輸入,還需要控制它與訓練輸入之間的核值近似;有限個事先指定的測試點可加入原固定列表。即使如此,核近似仍只是比較兩個預測器。要談總體風險,必須另設觀察抽樣、損失及訓練程序的條件,再作統計論證。核估計無偏或訓練矩陣誤差小,都不會自行證明泛化。
總結
同一組獨立隨機特徵給出無偏半正定 Gram 近似。有界特徵包絡給固定有限輸入列表上的明確指數逐元素界,再給較保守的算子界。正的嶺正則化把算子誤差轉成確定性的訓練預測比較。特徵數控制的是計算近似,不能代替從觀察學習的統計分析。
練習
快速檢查
(在兩點特徵模型中,求任意 下非對角估計的精確方差。若全部 列複製同一個隨機抽樣,無偏性與集中會怎樣?為甚麼對每個矩陣元素分別抽取新特徵也可能破壞半正定保證?)
解答 · 答案
每個非對角求和項以相同概率為一或負一,故期望零、方差一。獨立平均的方差是 。若只重複同一次抽樣,估計一直等於一或負一,與聲稱的列數無關;期望仍為零,方差卻一直是一,絕對誤差也一直是一。獨立性,或更一般的兩兩不相關性,都給出 的方差;本例的完全相依則破壞這個改善。其他相依結構需要另行分析。
按元素分別抽樣甚至未必對稱:兩點模型的兩個有序非對角估計可能不同。更強的是,一般而言即使強制對稱,也不保證半正定。取輸入 ,抽取座標彼此獨立、各為 Rademacher 正負號的 ,定義 ,則真 Gram 矩陣為 。對每個無序非對角對,分別用一次獨立特徵抽樣估計,然後把結果對稱放置,對角定為一。每個元素都無偏,卻以正概率得到
這個對稱矩陣不定,行列式為 。共享完整特徵向量並取外積,才在每次抽樣保留半正定性。元素分別抽樣,即使對稱而無偏,也沒有這個保證。
快速檢查
(目標 Gram 矩陣為 ,且 。證明任何只有 列的近似 ,算子誤差至少為一。逐元素誤差 因而受甚麼限制?這是否推翻集中定理?)
解答 · 答案
的秩至多 ,故其零空間含一個單位向量 。於是 ,算子誤差至少一。由逐元素到算子的界,得到 。所以在此秩範圍下,逐元素誤差不可能小於 。沒有矛盾。在 的任何有界表示中,對角條件 迫使 。若 ,我們的充分特徵預算超過 。保守算子估計亦保留因子 。低秩、逐元素準確及算子準確是不同要求。
快速檢查
(在抽特徵前固定測試輸入 。設訓練區塊有 ,測試點對訓練點的核值有 ,而這些點的特徵都以 為界。以 、、、 及 給出 的界。)
解答 · 答案
設 。預測差為 。假設給 、,以及 。訓練區塊界給 ,因此嶺定理給 。所以
這是在所述近似事件上的確定性界。對擴大的固定列表應用集中定理,可給該事件的概率。這兩步都不是總體風險界。
快速檢查
(只有一個輸入,特徵平方以相同概率為 或 。取 、標籤 、,計算核估計及嶺預測的期望,並與精確值比較。這排除了哪個推論?)
解答 · 答案
精確核為一,而估計為零或二,期望確實是一。精確嶺預測是 ;抽樣預測則為零或 ,期望為 。核近似無偏,不表示擬合預測無偏:求逆及矩陣乘法合起來,是隨機 Gram 矩陣的非線性映射。這裏所有期望都精確算出,並未使用有限樣本集中近似。