動機
訓練程序只能看見有限樣本,所得預測器卻要處理尚未出現的觀察。經驗平均可以由數據計算,因此不可或缺;但若同一批數據同時用來搜尋預測器,這個平均亦可能令人誤判。訓練誤差小,回答的是樣本上的問題。泛化則問:換上來自同一分佈的新觀察,答案是否仍然可靠?
問題即使在簡單分類中也會出現。假如分類器可以任意指定一個巨大有限定義域上每點的標籤,它便能記住已觀察的答案,並在其他地方任意作答。對一個預先固定的分類器,平均值未必不可靠;真正需要控制的是利用樣本從整個假設類中挑選成員的過程。因此,我們要同時控制所有候選者,或者另行分析選擇程序。
本節用三種方法描述搜尋的規模:有限類可以計數;Rademacher 平均衡量函數在樣本上迎合獨立隨機符號的能力;覆蓋數則用有限個近似向量代替無限集合。它們各有適用條件,並非對任何損失及任何數據都自動成立的保證。
定義
定義 1.1.1
(總體風險、經驗風險與近似 ERM)
設 Z 1 , … , Z n Z_1,\ldots,Z_n Z 1 , … , Z n 是來自同一分佈 P P P 的獨立觀察。固定假設類 H \mathcal H H 及可測損失 ℓ ( h , z ) \ell(h,z) ℓ ( h , z ) 後,定義
R ( h ) = E P ℓ ( h , Z ) , R ^ S ( h ) = 1 n ∑ i = 1 n ℓ ( h , Z i ) . R(h)=\mathbb E_P\ell(h,Z),\qquad
\widehat R_S(h)=\frac1n\sum_{i=1}^n\ell(h,Z_i). R ( h ) = E P ℓ ( h , Z ) , R S ( h ) = n 1 i = 1 ∑ n ℓ ( h , Z i ) . 若 ε o p t ≥ 0 \varepsilon_{\rm opt}\ge0 ε opt ≥ 0 ,近似經驗風險最小化所得的 h ^ \widehat h h 滿足
R ^ S ( h ^ ) ≤ inf h ∈ H R ^ S ( h ) + ε o p t . \widehat R_S(\widehat h)\le\inf_{h\in\mathcal H}\widehat R_S(h)+\varepsilon_{\rm opt}. R S ( h ) ≤ h ∈ H inf R S ( h ) + ε opt .
下確界未必取到,近似定義避免偷偷假設精確最小點存在。下文亦假設所用的上確界及選出的預測器可測,例如使用有限、可數或適當可分的函數類。任意函數族的上確界未必可測,不能直接把這個問題藏在期望符號裏。
令 G = { z ↦ ℓ ( h , z ) : h ∈ H } \mathcal G=\{z\mapsto\ell(h,z):h\in\mathcal H\} G = { z ↦ ℓ ( h , z ) : h ∈ H } 。對固定樣本 s = ( z 1 , … , z n ) s=(z_1,\ldots,z_n) s = ( z 1 , … , z n ) ,另取獨立符號 σ i \sigma_i σ i ,每個等概率取正一或負一,並定義絕對值版本的經驗 Rademacher 平均:
R ^ s a b s ( G ) = E σ sup g ∈ G ∣ 1 n ∑ i = 1 n σ i g ( z i ) ∣ . \widehat{\mathfrak R}^{\rm abs}_s(\mathcal G)
=\mathbb E_\sigma\sup_{g\in\mathcal G}
\left|\frac1n\sum_{i=1}^n\sigma_i g(z_i)\right|. R s abs ( G ) = E σ g ∈ G sup n 1 i = 1 ∑ n σ i g ( z i ) .
絕對值是本節約定的一部分,等價於對稱類 G ∪ ( − G ) \mathcal G\cup(-\mathcal G) G ∪ ( − G ) 的單邊定義。閱讀其他文獻時,要先核對這個約定再比較常數。輔助符號獨立於數據,並非把真實標籤換成隨機標籤。
對評估向量 v g = ( g ( z 1 ) , … , g ( z n ) ) v_g=(g(z_1),\ldots,g(z_n)) v g = ( g ( z 1 ) , … , g ( z n )) ,用樣本距離 d s ( g , q ) = ∥ v g − v q ∥ 2 / n d_s(g,q)=\|v_g-v_q\|_2/\sqrt n d s ( g , q ) = ∥ v g − v q ∥ 2 / n 。若有限個中心讓每個評估向量與其中一個中心的距離不超過 ϵ \epsilon ϵ ,便稱為 ϵ \epsilon ϵ -網;最少中心數稱為覆蓋數 N ( ϵ , G , d s ) N(\epsilon,\mathcal G,d_s) N ( ϵ , G , d s ) 。這個距離依賴樣本,而且可能只是偽度量:不同函數可以在所有樣本點上相同。
定理/命題
若 ∣ H ∣ = m ≥ 1 |\mathcal H|=m\ge1 ∣ H ∣ = m ≥ 1 、0 ≤ ℓ ( h , z ) ≤ 1 0\le\ell(h,z)\le1 0 ≤ ℓ ( h , z ) ≤ 1 ,則對 0 < δ < 1 0<\delta<1 0 < δ < 1 ,以至少 1 − δ 1-\delta 1 − δ 的概率有
sup h ∈ H ∣ R ( h ) − R ^ S ( h ) ∣ ≤ a n , a n = log ( 2 m / δ ) 2 n . \sup_{h\in\mathcal H}|R(h)-\widehat R_S(h)|
\le a_n,\qquad
a_n=\sqrt{\frac{\log(2m/\delta)}{2n}}. h ∈ H sup ∣ R ( h ) − R S ( h ) ∣ ≤ a n , a n = 2 n log ( 2 m / δ ) . 在同一事件上,每個近似 ERM 均滿足
R ( h ^ ) − min h ∈ H R ( h ) ≤ 2 a n + ε o p t . R(\widehat h)-\min_{h\in\mathcal H}R(h)
\le2a_n+\varepsilon_{\rm opt}. R ( h ) − h ∈ H min R ( h ) ≤ 2 a n + ε opt .
假設損失類有界,且有關上確界可測,則
E S sup g ∈ G ∣ P g − P n g ∣ ≤ 2 E S R ^ S a b s ( G ) . \mathbb E_S\sup_{g\in\mathcal G}|Pg-P_ng|
\le2\mathbb E_S\widehat{\mathfrak R}^{\rm abs}_S(\mathcal G). E S g ∈ G sup ∣ P g − P n g ∣ ≤ 2 E S R S abs ( G ) . 因此,最優化容許誤差為固定常數的近似 ERM 滿足
E R ( h ^ ) − inf h ∈ H R ( h ) ≤ 4 E S R ^ S a b s ( G ) + ε o p t . \mathbb E R(\widehat h)-\inf_{h\in\mathcal H}R(h)
\le4\mathbb E_S\widehat{\mathfrak R}^{\rm abs}_S(\mathcal G)
+\varepsilon_{\rm opt}. E R ( h ) − h ∈ H inf R ( h ) ≤ 4 E S R S abs ( G ) + ε opt .
第二個定理控制期望,不能直接讀成「以百分之九十五概率成立」。高概率版本需要額外的集中不等式。這裏計算的亦是損失類 的複雜度;若未控制損失變換,不能擅自改用預測函數類。
證明思路
先固定一個假設。有界變量的指數估計給出
P { ∣ R ^ S ( h ) − R ( h ) ∣ > t } ≤ 2 e − 2 n t 2 . \mathbb P\{|\widehat R_S(h)-R(h)|>t\}
\le2e^{-2nt^2}. P { ∣ R S ( h ) − R ( h ) ∣ > t } ≤ 2 e − 2 n t 2 . 關鍵是 X ∈ [ 0 , 1 ] X\in[0,1] X ∈ [ 0 , 1 ] 時有 E e λ ( X − E X ) ≤ e λ 2 / 8 \mathbb E e^{\lambda(X-\mathbb EX)}\le e^{\lambda^2/8} E e λ ( X − E X ) ≤ e λ 2 /8 。把對數矩母函數微分兩次,所得為指數傾斜分佈下的方差。傾斜後仍支持在 [ 0 , 1 ] [0,1] [ 0 , 1 ] ,方差不超過 1 / 4 1/4 1/4 。在零點的值及一階導數均為零,積分兩次便得到所需上界。獨立性讓矩母函數相乘,再用指數 Markov 不等式及最佳的正參數控制上尾;下尾對負變量重做即可。
對預先固定的 m m m 個假設取聯集界,失敗概率不超過 2 m e − 2 n t 2 2m e^{-2nt^2} 2 m e − 2 n t 2 。令它等於 δ \delta δ ,便得第一個結論。若 h ⋆ h_\star h ⋆ 是總體最小點,在一致事件上有
R ( h ^ ) ≤ R ^ S ( h ^ ) + a n ≤ R ^ S ( h ⋆ ) + ε o p t + a n ≤ R ( h ⋆ ) + ε o p t + 2 a n . R(\widehat h)\le\widehat R_S(\widehat h)+a_n
\le\widehat R_S(h_\star)+\varepsilon_{\rm opt}+a_n
\le R(h_\star)+\varepsilon_{\rm opt}+2a_n. R ( h ) ≤ R S ( h ) + a n ≤ R S ( h ⋆ ) + ε opt + a n ≤ R ( h ⋆ ) + ε opt + 2 a n .
證明透視
一致事件為何容許從數據選擇假設 固定假設的尾界只用到獨立性與取值範圍 [ 0 , 1 ] [0,1] [ 0 , 1 ] ;單憑它,對依賴數據的 h ^ \widehat h h 甚麼也說不出。關鍵一步是聯集界:它換來一個所有 m m m 個偏差同時都小的事件,代價是對數內的 δ \delta δ 換成 δ / m \delta/m δ / m 。在這個事件上,三個不等式組成的鏈條用了兩次一致界(分別在選出的 h ^ \widehat h h 與比較點 h ⋆ h_\star h ⋆ ),中間用了一次近似 ERM 的定義。比較點是固定的,單是它的偏差用單一假設的界便可控制;需要一致性的是被選出的預測器。類的有限性只透過 log m \log m log m 進入,所以當 log m \log m log m 與 n n n 同量級時,這個界便失效。
對稱化先加入獨立的「幽靈樣本」S ′ S' S ′ 。由 P g = E S ′ P n ′ g Pg=\mathbb E_{S'}P'_ng P g = E S ′ P n ′ g ,及上確界絕對值的凸性,得到
E S sup g ∣ P g − P n g ∣ ≤ E S , S ′ sup g ∣ P n ′ g − P n g ∣ . \mathbb E_S\sup_g|Pg-P_ng|
\le\mathbb E_{S,S'}\sup_g|P'_ng-P_ng|. E S g sup ∣ P g − P n g ∣ ≤ E S , S ′ g sup ∣ P n ′ g − P n g ∣. 獨立交換每一對 Z i , Z i ′ Z_i,Z'_i Z i , Z i ′ 不改變聯合分佈,所以每對差可以乘上隨機符號。三角不等式把差拆成兩項,而兩項期望相同,各為經驗絕對 Rademacher 平均的期望。這給出因子二。超額風險的確定性比較再用兩次一致偏差,便得到因子四。若總體下確界不取到,先與距下確界不超過 τ \tau τ 的假設比較,再令 τ \tau τ 趨零;這個證明沒有聲稱常數最佳。
證明透視
幽靈樣本與隨機符號在哪裏進入 總體平均 P g Pg P g 不是樣本量,所以第一步把它寫成一個獨立幽靈樣本上的平均;再對「把一族數映到其絕對值上確界」這個凸映射使用 Jensen 不等式,便把對 S ′ S' S ′ 的期望移到外面。真正的想法在下一步。由於 Z i Z_i Z i 與 Z i ′ Z_i' Z i ′ 獨立同分佈,交換任何一組配對都不改變聯合分佈,所以把第 i i i 個差乘以一個獨立符號,在分佈上毫無改變;這裏同時用到獨立性和同分佈。只有到這時,三角不等式才把兩個樣本分開,各自給出一個 Rademacher 平均,這就是因子二的來源。
用有限網控制無限類
在固定樣本上,也可以用有限個評估向量近似整個類,從而控制同一個 Rademacher 平均。
設 s s s 是固定樣本,且對每個 g ∈ G g\in\mathcal G g ∈ G 及每個 i i i 都有 ∣ g ( z i ) ∣ ≤ 1 |g(z_i)|\le1 ∣ g ( z i ) ∣ ≤ 1 。若 G \mathcal G G 中 N N N 個成員的評估向量構成 d s d_s d s 下的 ϵ \epsilon ϵ -網,則
R ^ s a b s ( G ) ≤ ϵ + 2 log ( 2 N ) n . \widehat{\mathfrak R}^{\rm abs}_s(\mathcal G)
\le\epsilon+\sqrt{\frac{2\log(2N)}n}. R s abs ( G ) ≤ ϵ + n 2 log ( 2 N ) .
設 ∣ g ( z i ) ∣ ≤ 1 |g(z_i)|\le1 ∣ g ( z i ) ∣ ≤ 1 ,並取大小為 N N N 、中心亦來自評估向量集合的 ϵ \epsilon ϵ -網。Cauchy–Schwarz 不等式給出
∣ 1 n ∑ i σ i ( g ( z i ) − q ( z i ) ) ∣ ≤ ϵ . \left|\frac1n\sum_i\sigma_i(g(z_i)-q(z_i))\right|\le\epsilon. n 1 i ∑ σ i ( g ( z i ) − q ( z i )) ≤ ϵ . 對固定中心,獨立性及 cosh t ≤ e t 2 / 2 \cosh t\le e^{t^2/2} cosh t ≤ e t 2 /2 令其帶符號平均的矩母函數不超過 e λ 2 / ( 2 n ) e^{\lambda^2/(2n)} e λ 2 / ( 2 n ) 。同時考慮全部中心的正負兩種符號,取對數及最佳參數,得到
R ^ s a b s ( G ) ≤ ϵ + 2 log ( 2 N ) n . \widehat{\mathfrak R}^{\rm abs}_s(\mathcal G)
\le\epsilon+\sqrt{\frac{2\log(2N)}n}. R s abs ( G ) ≤ ϵ + n 2 log ( 2 N ) .
第一項是近似誤差,第二項是有限搜尋成本。半徑愈小,中心可能愈多,故需要平衡。這只是單尺度論證,尚未建立鏈式估計或熵積分。
這個網是在固定樣本上構造的,所以可隨樣本改變。近似距離也只量度樣本評估值,沒有聲稱兩個函數在整個定義域上一致接近。由樣本複雜度推至總體一致偏差,需要前面的幽靈樣本及對稱化論證,不能單靠網格圖像直接跳到總體結論。
統計保證比較甚麼
超額風險的比較對象是指定類中最好的成員,未必是觀察空間上可以定義的最佳預測器。如果整個類都不能描述目標,超額風險小仍可伴隨很大的絕對風險。擴大假設類可能改善近似能力,也可能增加估計成本;單看訓練誤差無法評估這個取捨。
所有定理亦假設將來觀察與訓練樣本來自同一分佈;部署分佈改變後,對訓練分佈的一致收斂論證在數學上仍然正確,但估計的已是另一個量。問題在於所估計的量不符,而非聯集界有缺陷。
若所得上界超過一,有界損失的平凡界反而更好。沒有資訊的數值界仍然成立,但應如實報告為沒有資訊;這表示論證在該樣本量下未能認證所需精度,並不表示預測器必定失敗。
例題詳解
在看數據前固定八個分類器,以零一損失及 n = 400 n=400 n = 400 個獨立觀察作訓練,取 δ = 0.05 \delta=0.05 δ = 0.05 。因 log 320 ≈ 5.7683 \log320\approx5.7683 log 320 ≈ 5.7683 ,有 a n ≈ 0.08491 a_n\approx0.08491 a n ≈ 0.08491 。精確 ERM 的超額風險界是 0.16983 0.16983 0.16983 ;若訓練誤差只做到距最小值 0.01 0.01 0.01 ,便是 0.17983 0.17983 0.17983 。如果選出的訓練誤差為 0.04 0.04 0.04 ,亦有其總體風險不超過 0.12491 0.12491 0.12491 。前者比較類中最佳成員,後者控制自身風險,兩者並不相同。
設 g w ( x ) = w ⊤ x g_w(x)=w^\top x g w ( x ) = w ⊤ x 、∥ w ∥ 2 ≤ B \|w\|_2\le B ∥ w ∥ 2 ≤ B ,每個樣本特徵滿足 ∥ x i ∥ 2 ≤ A \|x_i\|_2\le A ∥ x i ∥ 2 ≤ A 。參數球對稱,絕對值上確界等於 B ∥ ∑ i σ i x i ∥ 2 / n B\|\sum\limits_i\sigma_i x_i\|_2/n B ∥ i ∑ σ i x i ∥ 2 / n 。Jensen 不等式及交叉項期望為零給出
R ^ s a b s ≤ B n ∑ i ∥ x i ∥ 2 2 ≤ B A n . \widehat{\mathfrak R}^{\rm abs}_s
\le\frac Bn\sqrt{\sum_i\|x_i\|_2^2}\le\frac{BA}{\sqrt n}. R s abs ≤ n B i ∑ ∥ x i ∥ 2 2 ≤ n B A . 當 B = 2 , A = 3 , n = 900 B=2,A=3,n=900 B = 2 , A = 3 , n = 900 ,預測類的界為 0.2 0.2 0.2 ,不直接依賴維數。這仍不是平方損失的界:對無界預測及標籤,平方損失並非全域 Lipschitz。需要有界範圍或另一個轉移論證。
在 ∣ x i ∣ ≤ 1 |x_i|\le1 ∣ x i ∣ ≤ 1 的樣本上,取 g w ( x ) = w x g_w(x)=wx g w ( x ) = w x 、w ∈ [ − 1 , 1 ] w\in[-1,1] w ∈ [ − 1 , 1 ] 。因 d s ( g w , g v ) ≤ ∣ w − v ∣ d_s(g_w,g_v)\le|w-v| d s ( g w , g v ) ≤ ∣ w − v ∣ ,間距不超過 ϵ \epsilon ϵ 的網格給出至多 ⌈ 2 / ϵ ⌉ + 1 \lceil2/\epsilon\rceil+1 ⌈ 2/ ϵ ⌉ + 1 個中心。取 ϵ = 0.1 , n = 1000 \epsilon=0.1,n=1000 ϵ = 0.1 , n = 1000 ,上界為 0.1 + 2 log 42 / 1000 ≈ 0.18646 0.1+\sqrt{2\log42/1000}\approx0.18646 0.1 + 2 log 42/1000 ≈ 0.18646 。直接用線性類計算則得 1 / 1000 ≈ 0.03162 1/\sqrt{1000}\approx0.03162 1/ 1000 ≈ 0.03162 。兩者均正確,粗糙的網格論證可以不銳利。
常見錯誤
如果模型設計亦使用同一批觀察,原先「抽樣前固定的有限類」已不是完整的搜尋範圍。未使用的驗證樣本可以評估獨立選出的預測器,但反覆根據驗證結果再作選擇,又形成新的搜尋。
下一個例子顯示:即使假設類預先固定,若它過於豐富,結論仍會失效。
反例模式
在全部標記組成的類上取得零訓練誤差 零訓練誤差本身不保證泛化。在 N N N 個點的均勻定義域上,令所有真標籤為零,假設類包含全部二元函數。選取在已抽到的點為零、其他點為一的函數,便是精確 ERM,總體誤差卻至少為 1 − n / N 1-n/N 1 − n / N 。若 N = 10000 , n = 100 N=10000,n=100 N = 10000 , n = 100 ,此值至少為 0.99 0.99 0.99 。損失有界、抽樣獨立,問題出在類太豐富。 這並不違反有限類定理:此時 log m = N log 2 \log m=N\log2 log m = N log 2 ,只有當 n n n 遠大於 N N N 時,該界才有意義。
覆蓋數及 Rademacher 平均並不只是參數個數;範數限制、特徵幾何、樣本及所用距離都會影響它們。把經驗最優化做得更準確,只會直接減少 ε o p t \varepsilon_{\rm opt} ε opt ,不會自行縮小複雜度項。
總結
一致收斂控制從同一樣本挑選假設所造成的偏差。計數、隨機符號及有限網提供三種相關工具。使用結論時,要同時保留有界損失、可測性、抽樣分佈及覆蓋距離等條件,並分清期望界和高概率界。
練習
快速檢查
(設 m = 32 m=32 m = 32 、損失在 [ 0 , 1 ] [0,1] [ 0 , 1 ] 、δ = 0.1 \delta=0.1 δ = 0.1 。依有限類定理,要保證精確 ERM 的超額風險至多 0.2 0.2 0.2 ,找出一個充分的整數樣本量。)
由 2 a n ≤ 0.2 2a_n\le0.2 2 a n ≤ 0.2 解出 n n n 。
解答 · 答案 要求 2 log 640 / ( 2 n ) ≤ 0.2 2\sqrt{\log640/(2n)}\le0.2 2 log 640/ ( 2 n ) ≤ 0.2 ,平方整理得 n ≥ 50 log 640 ≈ 323.0734 n\ge50\log640\approx323.0734 n ≥ 50 log 640 ≈ 323.0734 ,故 n = 324 n=324 n = 324 足夠。這是用自然對數得到的充分條件,未聲稱必要。
快速檢查
(一致偏差界為 a a a ,所選預測器的訓練風險距經驗下確界不超過 b b b 。不假設總體下確界取到,推導總體比較。)
解答 · 答案 任取 τ > 0 \tau>0 τ > 0 ,選 R ( h τ ) ≤ inf h R ( h ) + τ R(h_\tau)\le\inf\limits_hR(h)+\tau R ( h τ ) ≤ h inf R ( h ) + τ 。一致事件上有 R ( h ^ ) ≤ R ^ ( h ^ ) + a ≤ R ^ ( h τ ) + b + a ≤ R ( h τ ) + b + 2 a R(\widehat h)\le\widehat R(\widehat h)+a\le\widehat R(h_\tau)+b+a\le R(h_\tau)+b+2a R ( h ) ≤ R ( h ) + a ≤ R ( h τ ) + b + a ≤ R ( h τ ) + b + 2 a 。減去總體下確界,再令 τ \tau τ 趨零,得 2 a + b 2a+b 2 a + b 。
快速檢查
(在線性類例子中,全部樣本特徵均為同一單位向量 u u u 。用純量期望表示精確複雜度,並計算 n = 2 n=2 n = 2 的值。)
球上的上確界等於 B B B 乘以 ∑ i σ i x i \sum\limits_i\sigma_ix_i i ∑ σ i x i 的範數,再除以 n n n 。
解答 · 答案 向量和為 u ∑ i σ i u\sum\limits_i\sigma_i u i ∑ σ i ,所以精確值是 B E ∣ ∑ i σ i ∣ / n B\mathbb E|\sum\limits_i\sigma_i|/n B E ∣ i ∑ σ i ∣/ n 。兩個符號之和為 2 , 0 , − 2 2,0,-2 2 , 0 , − 2 的概率分別為 1 / 4 , 1 / 2 , 1 / 4 1/4,1/2,1/4 1/4 , 1/2 , 1/4 ,絕對值期望是一,故複雜度為 B / 2 B/2 B /2 。一般界 B / 2 B/\sqrt2 B / 2 仍成立,只是較大。
快速檢查
(記憶分類器為何不違反有限類定理?寫出假設類大小及其對數的量級。)
解答 · 答案 N N N 個點共有 2 N 2^N 2 N 個二元函數,故 log m = N log 2 \log m=N\log2 log m = N log 2 。界的量級為 N / n \sqrt{N/n} N / n ,當 N N N 遠大於 n n n 時沒有資訊。定理沒有承諾每個有限類在任何樣本量都能良好泛化。