動機
一致收斂問整個假設類的每個成員是否都有可靠經驗平均。算法穩定性問的是另一件事:只換一個觀察,指定訓練規則的輸出改變多少?假設類可以很大,而強正則化程序對一個觀察仍反應很小。此時直接分析程序,可能比為全部可表示函數計費更合適。
穩定證明有兩部分。概率恆等式把期望泛化化為相鄰訓練樣本的比較;最優化論證再界住輸出差異。兩者都不能由「正則化防止過擬合」的口號代替。前者需要獨立同分佈抽樣,後者需要確切曲率、梯度及算法條件。
以下固定一個完整模型:緊緻凸參數集上的凸光滑損失、正二次懲罰,以及由共同確定初始點開始的投影完整梯度下降。精確正則化 ERM 與其有限迭代近似便可共用同一組常數。最後的總體比較會保留最優化誤差及正則化偏差,並清楚只控制期望。
定義
設 C⊂Rd 非空、緊緻且凸,包含於半徑 R 的球,直徑不超過 D。每個觀察 z 的損失在包含 C 的開凸鄰域為 C2,並有
0≤ℓ(w,z)≤Bℓ,∥∇ℓ(w,z)∥≤G,0⪯∇2ℓ(w,z)⪯βI(w∈C).假設對 z 可測。樣本 S=(Z1,…,Zn) 獨立同分佈;只相差一個座標稱為相鄰。若確定算法 A 對每個相鄰對及測試點均有 ∣ℓ(A(S),z)−ℓ(A(S′),z)∣≤ϵ,便稱為 ϵ-一致穩定。
令 RP(w)=Eℓ(w,Z)、RS(w)=n−1i∑ℓ(w,Zi)。固定 λ>0,設 FS=RS+λ∥w∥2/2、F=RP+λ∥w∥2/2。緊緻性給存在,強凸性給唯一;另假設所得映射可測,使期望有意義。
迭代用確定初始點 w0∈C、固定步長 0<η≤1/(β+λ),更新 wt+1=ΠC(wt−η∇FS(wt))。相鄰樣本採用同一初始點、步長及步數。記 q=1−ηλ∈[0,1)、At(S)=wt。
定理/命題
定理 10.1.2
(替換一項恆等式與正則化穩定性)
每個 ϵ-一致穩定算法都滿足
ES[RP(A(S))−RS(A(S))]≤ϵ.FS 的精確最小點穩定性至多 2G2/(λn)。投影梯度作 t 次更新後,穩定性至多
ϵt=λn2G2(1−qt).
令 δt=(G+λR)Dqt,則每份樣本都有 FS(At(S))−CminFS≤δt。若 wλ 在 C 最小化 F,則
E[F(At(S))]−F(wλ)≤ϵt+δt.對每個固定比較點 u∈C,
E[RP(At(S))]−RP(u)≤ϵt+δt+2λ∥u∥2.
常數可以保守。損失有界保證可積分,梯度及曲率界則負責敏感度與收縮。結論是期望的絕對值,不是絕對偏差的期望,也不是某份樣本的高概率保證。
證明思路
取獨立替換 Zi′,以 S(i) 代替第 i 項。輸出 A(S(i)) 與原 Zi 獨立,替換樣本又與 S 同分佈,所以
ESRP(A(S))=ES,Zi′ℓ(A(S(i)),Zi).減經驗風險並對指標平均,得到完整恆等式
E[RP(A(S))−RS(A(S))]=n1i∑E[ℓ(A(S(i)),Zi)−ℓ(A(S),Zi)].每個被積項絕對值由一致穩定性控制,第一個結論便成立。獨立性用在確切位置:替換算法不能透過未替換的數據初始化或調參規則,暗中保留已移除觀察。
一致穩定性要求對所有測試觀察及所有相鄰樣本成立,並非只在一個已抽到的測試點看到小變化。這個強量詞讓我們直接把界移進期望,毋須知道輸出與原訓練項的複雜依賴。若只有平均意義的敏感度,仍可能有別的泛化定理,但不能未作相應積分控制就沿用這個證明。
精確 ERM 令 x=argCminFS、y=argCminFS′。強凸性與受約束一階最優性給 FS(y)−FS(x)≥λ∥x−y∥2/2,反向樣本同理。相加消去共同損失及懲罰,得
λ∥x−y∥2≤n1[ℓ(y,zi)−ℓ(x,zi)+ℓ(x,zi′)−ℓ(y,zi′)]≤n2G∥x−y∥.距離為零時直接成立,否則除去距離,得至多 2G/(λn)。梯度界令每個損失沿可行線段為 G-Lipschitz,乘上 G 即得所述穩定性,不需要邊界最優點的梯度為零。
證明透視
把兩個最優性不等式相加
每個最小點都透過自己的目標函數證明自身:FS 的強凸性與 x 處的約束一階條件給出二次增長 FS(y)−FS(x)≥λ∥x−y∥2/2,FS′ 在 y 處亦然。關鍵一步是把兩個不等式相加。兩個目標共有 n−1 個損失和懲罰項,它們全部抵消,只剩下兩個改變了的損失,權重為 1/n。梯度界使這個餘項對 ∥x−y∥ 是線性的,而左邊是二次的,於是迫使 ∥x−y∥≤2G/(λn)。這裏只用到損失的凸性和 λ;曲率上界 β 並未使用。
迭代先比較同一樣本的兩個參數。沿可行線段積分 Hessian,梯度差為 Hxy(x−y),對稱矩陣特徵值在 [λ,β+λ]。合法步長令 I−ηHxy 的特徵值在 [0,q]。投影非擴張,故完整更新收縮距離至少因子 q。非擴張可由兩個投影的變分不等式相加證明:∥p−p′∥2≤⟨p−p′,a−a′⟩≤∥p−p′∥∥a−a′∥。
現在從共同初始點耦合相鄰樣本。相同參數處只有一項梯度不同,懲罰消去,所以梯度差至多 2G/n。插入另一樣本在第一條軌跡目前點的中間更新,再分別用非擴張與收縮,得到
dt+1≤qdt+n2ηG,d0=0,dt≤λn2G(1−qt).最後一步是幾何和。再乘損失 Lipschitz 常數,接替換恆等式,便得到有限步期望保證。
證明透視
先耦合算法,再對樣本取期望
距離比較對每個相鄰樣本對確定成立。共同初始化令初距離零;收縮處理已累積的差異;更換觀察每步注入至多 2ηG/n 的新擾動。只有建立這個統一比較後,才經替換恆等式取期望。不能把兩個擬合參數當成獨立隨機量處理。
第二個定理不再需要概率論證:一個確定性的最優化界,加上插入一次經驗目標,便已足夠。
經驗最小點是投影更新的不動點,因受約束方向最優條件等價於相應投影恆等式。所以 ∥wt−wS⋆∥≤Dqt。目標梯度在 C 範數至多 G+λR,沿線段積分便給 δt。這個線性距離界在邊界仍正確;依賴最優點梯度消失的二次上界則需要額外內點假設。
最後對固定 u 插入經驗目標,有
E[F(At)]−F(u)=E[RP(At)−RS(At)]+E[FS(At)−FS(u)]≤ϵt+δt.等式用的是固定比較點經驗評估無偏,不是錯誤聲稱訓練輸出也無偏。取 u=wλ 得正則化比較;若比較原風險,把兩個懲罰移項,再捨去非正的輸出平方範數項,就得第二個不等式。
三種誤差各指甚麼
運行更久降低最優化界,卻可提高有限步敏感度至其極限。較大懲罰降低穩定界,卻增加比較點懲罰。若比較點範數至多 R,暫不計最優化項,便有 2G2/(λn)+λR2/2。取 λ=2G/(Rn) 可使此和為 2GR/n,但同時改了目標與合法步長,並非固定訓練問題的免費改善。
正規化方式也重要。這裏損失平均,懲罰只加一次,因此換一項的梯度差是 1/n 量級,強凸下界仍為 λ。若把懲罰也除以樣本數,便是不同程序,敏感度與曲率均須重算。
若相鄰初始化已知距離至多 a,同一遞推會多出 qta,損失敏感度還須再乘 G。這精確顯示共同初始化省去了甚麼,但未容許任意預處理被忽略:須先控制其相鄰敏感度,而且套用概率恆等式時要在替換樣本上重新運行整個算法。
Bousquet 與 Elisseeff及Hardt、Recht 與 Singer提供相關穩定性及耦合更新研究。本節自行證明指定投影完整梯度程序的常數,不能自動轉移到任意隨機最優化器或數據調參規則。
例題詳解
在 [−1,1] 取平方損失 (w−z)2/2、標籤正負一、懲罰參數一。最小點為標籤平均的一半。四個平衡標籤給零,換一個負標籤為正,輸出變成 1/4。測試標籤一的損失由 1/2 變 9/32,相差 7/32。一般界用 G=2 得二,比實際差大得多,但仍正確;保守上界不是誤差的精確預測。
同一族取 n=100,R=1,D=2,β=1,λ=1,η=1/2,則 q=1/2。十步後穩定界為 0.08(1−2−10)≈0.079922,最優化界為 6⋅2−10≈0.005859,和約 0.085781,控制正則化總體差距。原風險比較還有已聲明的比較點懲罰,刪掉便是在混用不同目標。
若 G=R=1,n=10000,極限統計加懲罰界是 2/(10000λ)+λ/2。選 λ=0.02 得 0.01+0.01=0.02。若選一,穩定項降至 0.0002,懲罰項卻為 0.5。穩定性更強未必給更佳原風險比較。這是充分界的權衡,不是聲稱觀察測試誤差必沿此曲線變化。
常見錯誤
反例模式
沒有曲率的凸 ERM 可以突變
令 C=[−1,1],損失 ℓ(w,z)=1+wz,標籤正負一。損失非負、凸且一-Lipschitz。奇數樣本量可有相鄰標籤和一及負一,無正則化 ERM 分別選負一及正一。測試標籤一的損失差為二,不隨樣本量消失。凸性本身未給正二次懲罰所提供的 1/n 穩定性。
替換一項定理控制的是 ∣E[RP(A(S))−RS(A(S))]∣,即期望的絕對值。某一份訓練樣本的差距可以大得多,而正負相反的差距可以在平均中互相抵消。這個界也沒有比較部署分佈改變後的表現。要對實際抽到的樣本下結論,須另加集中不等式的論證。
依賴數據的初始化,或在同一批觀察上調出的懲罰,都必須算作被分析算法的一部分:恆等式會在 S(i) 上重新運行整個流程。若替換 Zi 時仍保留由 S 計出的初始化,證明所依賴的「A(S(i)) 與 Zi 獨立」便不再成立。
收縮證明亦需要 Hessian 界及所述步長;改用別的算法卻沿用常數,需要新的耦合證明。最優化與統計可靠性由誤差分解連起來,但仍是不同項。
總結
替換一項恆等式把訓練敏感度連到期望泛化。正曲率控制精確最小點變化,也令相鄰投影梯度軌跡收縮。再接獨立證明的最優化界,便得保留正則化偏差及期望範圍的總體比較。
練習
快速檢查
(替換恆等式中為何輸出與原第 i 項獨立?若隱藏初始化由未替換完整樣本計算,會有甚麼問題?)
問 A(S(i)) 是哪些隨機變量的函數。
解答 · 答案
替換樣本只含其餘獨立原座標及新的獨立替換,全部與原第 i 項獨立。只輸入此樣本的確定算法仍獨立;若另收到原樣本計出的初始化,就可能保留該觀察資訊,獨立評估失效。須在替換樣本重新計算初始化,或另行分析。
快速檢查
(解 dt+1≤qdt+c,d0=0,再代入 c=2ηG/n 及 q=1−ηλ。)
解答 · 答案
遞推給 dt≤cj=0∑t−1qj=c(1−qt)/(1−q)。用 1−q=ηλ 得 2G(1−qt)/(λn)。在零步兩邊均零,約定 q0=1。
快速檢查
(平方損失、懲罰一、n=8,換一個負標籤為正,精確最小點移多遠?用 G=2 界住測試損失差。)
解答 · 答案
標籤平均改變 2/8=1/4,最小點再除以二,所以移動 1/8。測試損失差至多 G/8=1/4。這使用精確解公式,因此比一般最壞穩定常數更銳利。
快速檢查
(為何不能在受約束邊界直接用 (β+λ)∥w−wS⋆∥2/2 當作目標差距上界?)
解答 · 答案
光滑性給二次餘項之外,還有最優點梯度與位移的一次內積。受約束最優點只保證此項非負,不保證零,不能從上界刪去。安全做法是用 (G+λR)∥w−wS⋆∥,在邊界亦成立。