如果一個函數類能匹配許多任意標籤模式,它既可能擬合信號,也可能擬合噪聲。Rademacher 複雜度在觀察到的輸入上提出一個定量問題:類中的函數能與獨立隨機符號有多強的相關性?與簡單計算假設個數不同,其值可以依賴樣本所在的位置。
固定樣本上的隨機符號
設 從固定分布 獨立同分布抽取,;設 是抽樣前固定的非空可測函數類,成員為 。記 、。假設下文用到的上確界均可測,包括涉及獨立幽靈樣本和符號的上確界;有限或可數類滿足要求,下文的連續緊緻參數例子也滿足要求。
下文對數均為自然對數。
定義 2.5.1
(經驗與期望 Rademacher 複雜度)
給定樣本 ,令 是獨立均勻的 符號,並獨立於樣本。定義
所有樣本點必須使用同一個 。符號是分析工具,不是提供給訓練算法的標籤。對符號取期望在上確界之外:每個符號向量可以選擇不同的上確界函數。對任一固定成員,其帶符號和的期望為零,因此 。
例題 2.5.2
(兩個常值函數)
設 由恆零和恆一函數組成。當 時,上確界為 。其期望為 :只有兩個符號均為正的情形有貢獻。這是類在樣本上的複雜度,不是訓練誤差,也不是誤分類的概率。
從對稱化得到一致界
定理 2.5.3
(經驗 Rademacher 泛化界)
對 ,以樣本為隨機性、概率至少為 ,對所有 同時有
對固定的損失函數類,這用經驗損失控制總體損失;複雜度必須針對該損失函數類計算,不能自動以底層預測器類的複雜度代替。即使函數是在看到樣本後從類中選出的,結論仍成立,因為該事件對所有成員同時成立。
證明
(幽靈樣本、對稱化與有界差)
令 ,引入與樣本獨立、同分布的幽靈樣本 。由於 ,將期望移到上確界之外得到
每對 可交換。根據隨機符號獨立交換每對中的元素,不改變聯合分布,因此
不等式把差的上確界拆成兩個上確界;符號向量與其相反數同分布。這就是對稱化步驟。
我們使用有界差不等式:若改變第 個獨立輸入使函數變化至多 ,則它超過均值 的概率至多為 ;低於均值的同等偏差也有此界。例如,可對逐次條件期望構成的鞅差應用 Hoeffding 引理得到此結論。由於所有函數值都在 ,改變一個樣本點使 或 的變化均至多為 。令 , 的上偏差和 的下偏差各以至多 的概率失敗。在兩者共同成立的事件上,
對每個成員都有 ,故定理成立。
證明透視
幽靈樣本和符號為何出現
幽靈樣本只用於證明。逐對交換把兩個經驗均值的差變成帶符號的差。拆分所得上確界後得到兩份複雜度。完成這個期望論證後,才用有界差把未知的期望複雜度換成經驗版本。
這個不等式是單側的。它不保證每個樣本的右側都很小:經驗複雜度本身可以很大,且仍有概率至多 的例外事件。如果看過同一份樣本後才構造 ,就不能不加額外論證地應用這個固定類定理。
有限類與範數有界的無限類
引理 2.5.4
(有限類的複雜度很小)
對於大小為 的固定有限類,每個樣本都滿足
證明
(矩母函數論證)
當 時,令 。對任意 ,Jensen 不等式及非負數的 給出
這裏 ,因為 且 。取 使右側最小。當 時帶符號和的均值為零,所以同一個界成立。該界可能大於由值域直接得到的平凡界,也不一定緊。
無限類不能直接使用基數界。但令定義域與分布支撐在球 上,並考慮 ,其中 、,並令 。這些函數的值在 。對任何樣本,
常數項的帶符號期望為零; 在歐氏(Euclidean)球上的上確界為 。Jensen 不等式及交叉項抵消給出中間的界。該類雖然無限,其複雜度仍受範數約束控制。維數仍可能通過 、 和數據的尺度間接影響結果。
例題 2.5.5
(有限類,以及界何時沒有意義)
取 、,並設所選函數的經驗均值為 。當 時,有限類界給出 ,置信項為 。因此定理右側至多為 ,超過平凡值 :在這個樣本量下它甚麼也沒有說明。當 時,相應的量為 和 ,所以右側至多為 。在退化情形 時,界為 ,與單個函數的 Rademacher 複雜度為零這一事實一致。
例題 2.5.6
(範數有界的線性類在兩種樣本量下的情形)
取 、,故 ,函數 取值於 。複雜度界為 ,在 時為 ,在 時為 。取 ,定理中複雜度的貢獻 分別至多為 和 ,而置信項分別為 和 。在 時,起主導作用的是置信項,而不是這個無限類的複雜度。這個類含有無限多個函數,貢獻卻比上面八個函數的有限界更小。
反例模式
依樣本選出的類可能使定理失效
設定義域有 個等概率點,每個點的「標籤」就是某個函數在該點的值。觀察 後,選擇只含函數 的單元素類,其中 在觀察到的點取零,在其他點取一。其經驗複雜度為零,因為類中只有一個函數,且 ,但 。當 、 時,定理所示右側約為 ,所以若在此應用,便會對每個樣本失敗。函數類是根據樣本選出的,因此固定類定理不適用。遺漏的複雜度在於對許多可能函數進行適應性選擇。
常見錯誤
(把上確界放到對符號的期望之外)
對每個固定的 ,帶符號的和均值為零,所以對任何類都有 。複雜度是 ,其中上確界可以隨符號調整。對 的兩個常值函數,正確值為 ,而不是 。交換這兩個運算,會使每個類看起來都沒有擬合噪聲的能力。
常見錯誤
(用預測器的複雜度代替損失類的複雜度)
定理控制的是取值於 的損失函數類 。對標籤 和 0-1 損失,。常數 的貢獻均值為零,而 仍是均勻符號,所以損失類的複雜度恰好是同一批輸入上預測器類複雜度的一半。直接代入 的複雜度會使複雜度項加倍;必須指明正確的類。
練習與解答
快速檢查
(對只含恆等於 的函數的類,計算任意 下的經驗 Rademacher 複雜度。)
上確界遍歷多少個函數?
解答 · 答案
為零:帶符號和的均值為零。
快速檢查
(當 、 時,寫出有限類上界。)
代入 。
解答 · 答案
。
快速檢查
(若 、、,給出上述線性類的複雜度界。)
用 。
解答 · 答案
至多為 。
快速檢查
(為甚麼定理允許依據數據選擇 ,卻不允許未計入代價地依據數據選擇整個類?)
抽樣之前固定的是哪個對象?
解答 · 答案
一個同時成立的事件覆蓋了抽樣前固定的類中的每個成員;看到樣本之後才改變類本身,則超出了該事件的量詞範圍。