動機
學習問題至少有兩個幾何選擇。表示方式決定能寫出甚麼預測,擬合規則則決定數據、懲罰或算法偏好其中哪一個。核方法用特徵向量的內積作第一個選擇;ReLU 網絡把折點函數相加來建立預測。過度參數化的線性模型尤其清楚顯示第二個選擇仍然必要:很多參數都可以完全符合相同的訓練觀察。
表示能力不可直接當作泛化保證。能在區間上一致近似所有連續函數的類,未必容易從有限數據擬合。最小範數插值器明確選出一個精確擬合,但總體表現仍依賴特徵、目標、抽樣及雜訊。本節證明可掌握的表示與選擇結果,同時指出尚未解答的統計問題。
我們先用核把特徵空間問題化為有限矩陣問題,再構造一維神經網絡近似,最後以奇異值分析梯度下降的隱含選擇。這些結果並不構成完整的神經網絡學習理論。
定義
集合 X \mathcal X X 上的實核是對稱函數 k : X × X → R k:\mathcal X\times\mathcal X\to\mathbb R k : X × X → R 。若對每個有限點集及每組實係數都有
∑ i , j = 1 n c i c j k ( x i , x j ) ≥ 0. \sum_{i,j=1}^nc_ic_jk(x_i,x_j)\ge0. i , j = 1 ∑ n c i c j k ( x i , x j ) ≥ 0. 便稱它為半正定核。再生核 Hilbert 空間 H k \mathcal H_k H k 是一個函數 Hilbert 空間,其中 k x = k ( x , ⋅ ) ∈ H k k_x=k(x,\cdot)\in\mathcal H_k k x = k ( x , ⋅ ) ∈ H k ,而 f ( x ) = ⟨ f , k x ⟩ H k f(x)=\langle f,k_x\rangle_{\mathcal H_k} f ( x ) = ⟨ f , k x ⟩ H k 。特別地,⟨ k x , k z ⟩ = k ( x , z ) \langle k_x,k_z\rangle=k(x,z) ⟨ k x , k z ⟩ = k ( x , z ) 。
K i j = k ( x i , x j ) K_{ij}=k(x_i,x_j) K ij = k ( x i , x j ) 稱為 Gram 矩陣。半正定容許零特徵值,不保證每個矩陣可逆。特徵映射 ϕ : X → R p \phi:\mathcal X\to\mathbb R^p ϕ : X → R p 定義的 k ( x , z ) = ⟨ ϕ ( x ) , ϕ ( z ) ⟩ k(x,z)=\langle\phi(x),\phi(z)\rangle k ( x , z ) = ⟨ ϕ ( x ) , ϕ ( z )⟩ 必為核,因相應二次型等於 ∥ ∑ i c i ϕ ( x i ) ∥ 2 2 \|\sum\limits_i c_i\phi(x_i)\|_2^2 ∥ i ∑ c i ϕ ( x i ) ∥ 2 2 。例如 ( 1 + x z ) 2 (1+xz)^2 ( 1 + x z ) 2 的特徵映射是 ( 1 , 2 x , x 2 ) (1,\sqrt2x,x^2) ( 1 , 2 x , x 2 ) ;中間的 2 \sqrt2 2 才會產生交叉項係數二。
以下假設已給定具此核的再生空間。「每個半正定核都可構造這樣的空間」是另一個基礎定理,這裏未證明。已知有限維特徵映射時,以下論證已有具體例子,無須先使用一般構造。
定義 ReLU 為 σ ( t ) = max { 0 , t } \sigma(t)=\max\{0,t\} σ ( t ) = max { 0 , t } 。容許仿射項的單隱藏層純量輸入表示是 a + b x + ∑ j c j σ ( x − t j ) a+bx+\sum\limits_jc_j\sigma(x-t_j) a + b x + j ∑ c j σ ( x − t j ) 。若架構不容許仿射旁路,可用 x = σ ( x ) − σ ( − x ) x=\sigma(x)-\sigma(-x) x = σ ( x ) − σ ( − x ) 加兩個單元實現線性部分,常數則需輸出偏置。應先說明架構,避免無聲改變可表示的函數。
對 X ∈ R n × d X\in\mathbb R^{n\times d} X ∈ R n × d ,若 ker X \ker X ker X 非平凡,例如 d > n d>n d > n ,則線性模型 X w Xw X w 在線性代數意義下過度參數化,不同參數可給相同觀察預測。精確插值還需要 y ∈ range X y\in\operatorname{range}X y ∈ range X ;參數多於觀察並不單獨保證插值。
定理/命題
設 x i ∈ X x_i\in\mathcal X x i ∈ X 、y ∈ R n y\in\mathbb R^n y ∈ R n 、λ > 0 \lambda>0 λ > 0 。目標函數
J ( f ) = 1 2 n ∑ i = 1 n ( f ( x i ) − y i ) 2 + λ 2 ∥ f ∥ H k 2 J(f)=\frac1{2n}\sum_{i=1}^n(f(x_i)-y_i)^2
+\frac\lambda2\|f\|_{\mathcal H_k}^2 J ( f ) = 2 n 1 i = 1 ∑ n ( f ( x i ) − y i ) 2 + 2 λ ∥ f ∥ H k 2 在 H k \mathcal H_k H k 中有唯一最小函數,且位於 V = span { k x 1 , … , k x n } V=\operatorname{span}\{k_{x_1},\ldots,k_{x_n}\} V = span { k x 1 , … , k x n } 。它可寫成
f λ ( ⋅ ) = ∑ i = 1 n c i k ( x i , ⋅ ) , ( K + n λ I ) c = y . f_\lambda(\cdot)=\sum_{i=1}^nc_i k(x_i,\cdot),\qquad
(K+n\lambda I)c=y. f λ ( ⋅ ) = i = 1 ∑ n c i k ( x i , ⋅ ) , ( K + nλ I ) c = y . 線性系統的解唯一;但若 K K K 奇異,同一函數仍可能有其他係數表示。
以 t 0 < ⋯ < t m t_0<\cdots<t_m t 0 < ⋯ < t m 分割 [ a , b ] [a,b] [ a , b ] ,令 p p p 在節點處線性插值連續函數 u u u 。記 s j = [ u ( t j + 1 ) − u ( t j ) ] / ( t j + 1 − t j ) s_j=[u(t_{j+1})-u(t_j)]/(t_{j+1}-t_j) s j = [ u ( t j + 1 ) − u ( t j )] / ( t j + 1 − t j ) ,則
p ( x ) = u ( t 0 ) + s 0 ( x − t 0 ) + ∑ j = 1 m − 1 ( s j − s j − 1 ) σ ( x − t j ) . p(x)=u(t_0)+s_0(x-t_0)
+\sum_{j=1}^{m-1}(s_j-s_{j-1})\sigma(x-t_j). p ( x ) = u ( t 0 ) + s 0 ( x − t 0 ) + j = 1 ∑ m − 1 ( s j − s j − 1 ) σ ( x − t j ) . 若 h = max j ( t j + 1 − t j ) h=\max\limits_j(t_{j+1}-t_j) h = j max ( t j + 1 − t j ) 且 u u u 為 A A A -Lipschitz,則 ∥ u − p ∥ ∞ ≤ A h / 2 \|u-p\|_\infty\le Ah/2 ∥ u − p ∥ ∞ ≤ A h /2 。每個 [ a , b ] [a,b] [ a , b ] 上的連續函數,都可在網格趨細時被此類網絡一致近似,即使未假設 Lipschitz。
最後一句使用一致連續性,並不是說每個連續函數都 Lipschitz。速率 A h / 2 Ah/2 A h /2 只適用於 Lipschitz 情況。這個構造只有一個輸入維度,未提供多變量目標與維數無關的複雜度保證。
證明思路
核方法的證明先把搜尋範圍縮到有限生成空間 V V V ,再求係數。
V V V 有限維,因此是閉子空間。把任意 f f f 正交分解為 f = v + r f=v+r f = v + r ,其中 v ∈ V , r ⊥ V v\in V,r\perp V v ∈ V , r ⊥ V 。再生性給 r ( x i ) = ⟨ r , k x i ⟩ = 0 r(x_i)=\langle r,k_{x_i}\rangle=0 r ( x i ) = ⟨ r , k x i ⟩ = 0 ,故 f f f 與 v v v 的訓練損失相同,但 ∥ f ∥ 2 = ∥ v ∥ 2 + ∥ r ∥ 2 \|f\|^2=\|v\|^2+\|r\|^2 ∥ f ∥ 2 = ∥ v ∥ 2 + ∥ r ∥ 2 。正的懲罰使最優時必有 r = 0 r=0 r = 0 。只要最小點存在,同一論證亦適用於僅依賴這些評估值的其他損失,以及隨範數嚴格增加的懲罰。
對本節平方目標,現在只需在有限維 V V V 上最小化連續函數。由 J ( v ) ≥ λ ∥ v ∥ 2 / 2 J(v)\ge\lambda\|v\|^2/2 J ( v ) ≥ λ ∥ v ∥ 2 /2 ,最小化序列有界,收斂子序列便給出最小點。平方範數嚴格凸,損失凸,因此最小函數唯一。
沿每個 Hilbert 空間方向微分,得到駐點方程
λ f λ + 1 n ∑ i ( f λ ( x i ) − y i ) k x i = 0. \lambda f_\lambda+\frac1n\sum_i(f_\lambda(x_i)-y_i)k_{x_i}=0. λ f λ + n 1 i ∑ ( f λ ( x i ) − y i ) k x i = 0. 取 c i = ( y i − f λ ( x i ) ) / ( n λ ) c_i=(y_i-f_\lambda(x_i))/(n\lambda) c i = ( y i − f λ ( x i )) / ( nλ ) ,代入表示並在數據點評估,便得 ( K + n λ I ) c = y (K+n\lambda I)c=y ( K + nλ I ) c = y 。反過來,方程的解滿足駐點條件,故最小化凸目標。因 c ⊤ ( K + n λ I ) c ≥ n λ ∥ c ∥ 2 c^\top(K+n\lambda I)c\ge n\lambda\|c\|^2 c ⊤ ( K + nλ I ) c ≥ nλ ∥ c ∥ 2 ,矩陣正定。若直接對係數微分,只會得到 K [ ( K + n λ I ) c − y ] = 0 K[(K+n\lambda I)c-y]=0 K [( K + nλ I ) c − y ] = 0 ;K K K 奇異時不能約去它,這是常見的錯誤證明。
證明透視
再生性提供了甚麼,懲罰又在哪裏不可缺少 再生性只在一處使用:它把 r ⊥ V r\perp V r ⊥ V 化成 r ( x i ) = 0 r(x_i)=0 r ( x i ) = 0 ,所以與數據截面正交的分量對損失不可見。其餘都是 Hilbert 空間幾何,這個化約也不依賴平方損失。懲罰隨後擔當兩個不同角色。範數上的嚴格單調性令 r = 0 r=0 r = 0 最優,這就是表示原理;界 J ( v ) ≥ λ ∥ v ∥ 2 / 2 J(v)\ge\lambda\|v\|^2/2 J ( v ) ≥ λ ∥ v ∥ 2 /2 令最小化序列有界,給出存在性,再配合嚴格凸性給出函數的唯一性。
係數方程的關鍵一步,是在無窮維空間中微分,而不是對 c c c 微分。Hilbert 空間梯度是 λ f + 1 n ∑ i ( f ( x i ) − y i ) k x i \lambda f+\tfrac1n\sum\limits_i(f(x_i)-y_i)k_{x_i} λ f + n 1 i ∑ ( f ( x i ) − y i ) k x i ;選 c c c 令它恆為零,便得到 ( K + n λ I ) c = y (K+n\lambda I)c=y ( K + nλ I ) c = y ,無須約去 K K K 。當 λ = 0 \lambda=0 λ = 0 ,矩陣 K + n λ I K+n\lambda I K + nλ I 可以奇異,標準方程可以失效,下面的反例正說明這點。
ReLU 的證明是直接驗證,再加一個凸組合估計。
ReLU 公式在第一段的初值及斜率正確,每跨過 t j t_j t j ,斜率改變 s j − s j − 1 s_j-s_{j-1} s j − s j − 1 。函數又連續,因此每段都與插值器相同。為估計誤差,寫 x = ( 1 − θ ) t j + θ t j + 1 x=(1-\theta)t_j+\theta t_{j+1} x = ( 1 − θ ) t j + θ t j + 1 ,0 ≤ θ ≤ 1 0\le\theta\le1 0 ≤ θ ≤ 1 。由插值及三角不等式,
∣ u ( x ) − p ( x ) ∣ ≤ ( 1 − θ ) ∣ u ( x ) − u ( t j ) ∣ + θ ∣ u ( x ) − u ( t j + 1 ) ∣ ≤ 2 A θ ( 1 − θ ) ( t j + 1 − t j ) ≤ A h / 2. |u(x)-p(x)|
\le(1-\theta)|u(x)-u(t_j)|+\theta|u(x)-u(t_{j+1})|
\le2A\theta(1-\theta)(t_{j+1}-t_j)\le Ah/2. ∣ u ( x ) − p ( x ) ∣ ≤ ( 1 − θ ) ∣ u ( x ) − u ( t j ) ∣ + θ ∣ u ( x ) − u ( t j + 1 ) ∣ ≤ 2 A θ ( 1 − θ ) ( t j + 1 − t j ) ≤ A h /2. 對一般連續目標,兩個端點差均不超過連續模 ω u ( h ) \omega_u(h) ω u ( h ) ,所以加權後亦不超過它。緊緻區間上一致連續,令此量隨 h h h 趨零。這證明合適權重存在,未證明某訓練算法能從指定數據找到它們。
反例模式
沒有正懲罰,標準方程可以不相容 聲稱:當 λ = 0 \lambda=0 λ = 0 時,J J J 的最小點仍是 ∑ i c i k x i \sum\limits_ic_ik_{x_i} i ∑ c i k x i ,且 ( K + n λ I ) c = y (K+n\lambda I)c=y ( K + nλ I ) c = y 。取第一個例題的 k ( x , z ) = x z k(x,z)=xz k ( x , z ) = x z 、x 1 = 1 x_1=1 x 1 = 1 、x 2 = 2 x_2=2 x 2 = 2 、y = ( 1 , 0 ) ⊤ y=(1,0)^\top y = ( 1 , 0 ) ⊤ 。當 λ = 0 \lambda=0 λ = 0 ,方程是 K c = y Kc=y K c = y ,而 K c = ( c 1 + 2 c 2 ) ( 1 , 2 ) ⊤ Kc=(c_1+2c_2)(1,2)^\top K c = ( c 1 + 2 c 2 ) ( 1 , 2 ) ⊤ 永遠不能等於 ( 1 , 0 ) ⊤ (1,0)^\top ( 1 , 0 ) ⊤ ,所以無解。可是最小點存在:函數是 f ( x ) = w x f(x)=wx f ( x ) = w x ,而 1 4 [ ( w − 1 ) 2 + 4 w 2 ] \tfrac14[(w-1)^2+4w^2] 4 1 [( w − 1 ) 2 + 4 w 2 ] 在 w = 1 / 5 w=1/5 w = 1/5 取最小值。修正方法是要求 λ > 0 \lambda>0 λ > 0 ;或在 λ = 0 \lambda=0 λ = 0 時改用正規方程 K ( K c − y ) = 0 K(Kc-y)=0 K ( K c − y ) = 0 ,此處化為 5 ( c 1 + 2 c 2 ) = 1 5(c_1+2c_2)=1 5 ( c 1 + 2 c 2 ) = 1 。
過度參數化模型中的精確隱含選擇
第三個結果關乎算法,而不是函數類。
命題 3.1.4
(梯度下降選出最小範數最小二乘解)
設 X ∈ R n × d X\in\mathbb R^{n\times d} X ∈ R n × d 非零,y ∈ R n y\in\mathbb R^n y ∈ R n ,F ( w ) = 1 2 ∥ X w − y ∥ 2 2 F(w)=\tfrac12\|Xw-y\|_2^2 F ( w ) = 2 1 ∥ X w − y ∥ 2 2 ,且 0 < η < 2 / ∥ X ∥ o p 2 0<\eta<2/\|X\|_{\rm op}^2 0 < η < 2/∥ X ∥ op 2 。由任意 w 0 w_0 w 0 出發的梯度下降 w k + 1 = w k − η ∇ F ( w k ) w_{k+1}=w_k-\eta\nabla F(w_k) w k + 1 = w k − η ∇ F ( w k ) 收斂至 X † y + Π ker X w 0 X^\dagger y+\Pi_{\ker X}w_0 X † y + Π k e r X w 0 。特別地,由 w 0 = 0 w_0=0 w 0 = 0 出發時收斂至 X † y X^\dagger y X † y ,即歐幾里得(Euclid)範數最小的唯一最小二乘解。
先取 w 0 = 0 w_0=0 w 0 = 0 。取只保留正奇異值 s j s_j s j 的緊奇異值分解 X = U Σ V ⊤ X=U\Sigma V^\top X = U Σ V ⊤ 。梯度總在 range X ⊤ \operatorname{range}X^\top range X ⊤ ,所以迭代亦留在此子空間。座標 a k , j = v j ⊤ w k a_{k,j}=v_j^\top w_k a k , j = v j ⊤ w k 滿足
a k + 1 , j = ( 1 − η s j 2 ) a k , j + η s j u j ⊤ y . a_{k+1,j}=(1-\eta s_j^2)a_{k,j}+\eta s_j u_j^\top y. a k + 1 , j = ( 1 − η s j 2 ) a k , j + η s j u j ⊤ y . 每個乘數絕對值小於一,故座標趨向 u j ⊤ y / s j u_j^\top y/s_j u j ⊤ y / s j ,即 w k → X † y = V Σ − 1 U ⊤ y w_k\to X^\dagger y=V\Sigma^{-1}U^\top y w k → X † y = V Σ − 1 U ⊤ y 。預測等於正交投影 U U ⊤ y UU^\top y U U ⊤ y ,即使不能插值仍是最小二乘解。其他解都加上一個與此解正交的零空間向量;由 Pythagoras 定理,此極限是唯一最小歐幾里得範數解。
一般初始化時,梯度 X ⊤ ( X w − y ) X^\top(Xw-y) X ⊤ ( X w − y ) 沒有零空間分量,所以每步都有 Π ker X w k = Π ker X w 0 \Pi_{\ker X}w_k=\Pi_{\ker X}w_0 Π k e r X w k = Π k e r X w 0 ,而 range X ⊤ \operatorname{range}X^\top range X ⊤ 中的分量服從同一遞推。極限是 X † y + Π ker X w 0 X^\dagger y+\Pi_{\ker X}w_0 X † y + Π k e r X w 0 。
反例模式
步長太大時迭代不會穩定 聲稱:從 w 0 = 0 w_0=0 w 0 = 0 出發,任何正步長的梯度下降都收斂到 X † y X^\dagger y X † y 。取第三個例題的 X = ( 1 , 1 ) X=(1,1) X = ( 1 , 1 ) 、y = 2 y=2 y = 2 ,則 ∥ X ∥ o p 2 = 2 \|X\|_{\rm op}^2=2 ∥ X ∥ op 2 = 2 ,定理要求 η < 1 \eta\lt1 η < 1 。取 η = 1 \eta=1 η = 1 ,梯度為 ( w 1 + w 2 − 2 ) ( 1 , 1 ) ⊤ (w_1+w_2-2)(1,1)^\top ( w 1 + w 2 − 2 ) ( 1 , 1 ) ⊤ ,迭代依次為 ( 0 , 0 ) ⊤ , ( 2 , 2 ) ⊤ , ( 0 , 0 ) ⊤ , … (0,0)^\top,(2,2)^\top,(0,0)^\top,\ldots ( 0 , 0 ) ⊤ , ( 2 , 2 ) ⊤ , ( 0 , 0 ) ⊤ , … :乘數 1 − η s 2 = − 1 1-\eta s^2=-1 1 − η s 2 = − 1 的絕對值為一,序列來回振盪。若 η > 1 \eta\gt1 η > 1 ,乘數 1 − 2 η 1-2\eta 1 − 2 η 的絕對值大於一,迭代發散。修正就是定理中的條件 0 < η < 2 / ∥ X ∥ o p 2 0\lt\eta\lt2/\|X\|_{\rm op}^2 0 < η < 2/∥ X ∥ op 2 ,它令每個乘數 1 − η s j 2 1-\eta s_j^2 1 − η s j 2 嚴格落在 − 1 -1 − 1 與 1 1 1 之間。
因此最小範數是目標函數、歐幾里得參數幾何及零初始化共同產生的結論。改變特徵參數化,可能改變所選預測器。
顯式與隱式正則化
嶺迴歸以平方範數懲罰明確表達偏好。在固定有限維特徵下,正懲罰趨零時,其奇異方向係數因子由「奇異值除以其平方加適當懲罰」趨向偽逆因子,零方向保持零,因而趨向最小範數最小二乘解。這個極限不能同時無聲改變特徵映射。
概念視角 代數
核嶺迴歸就是特徵上的嶺迴歸 設 k ( x , z ) = ⟨ ϕ ( x ) , ϕ ( z ) ⟩ k(x,z)=\langle\phi(x),\phi(z)\rangle k ( x , z ) = ⟨ ϕ ( x ) , ϕ ( z )⟩ ,其中 ϕ : X → R p \phi:\mathcal X\to\mathbb R^p ϕ : X → R p ;令 Φ ∈ R n × p \Phi\in\mathbb R^{n\times p} Φ ∈ R n × p 的第 i i i 行為 ϕ ( x i ) ⊤ \phi(x_i)^\top ϕ ( x i ) ⊤ ,則 K = Φ Φ ⊤ K=\Phi\Phi^\top K = Φ Φ ⊤ 。對 f ( x ) = ⟨ w , ϕ ( x ) ⟩ f(x)=\langle w,\phi(x)\rangle f ( x ) = ⟨ w , ϕ ( x )⟩ 以相同正規化做嶺迴歸,要解 ( Φ ⊤ Φ + n λ I ) w = Φ ⊤ y (\Phi^\top\Phi+n\lambda I)w=\Phi^\top y ( Φ ⊤ Φ + nλ I ) w = Φ ⊤ y 。恆等式 ( Φ ⊤ Φ + n λ I ) Φ ⊤ = Φ ⊤ ( Φ Φ ⊤ + n λ I ) (\Phi^\top\Phi+n\lambda I)\Phi^\top=\Phi^\top(\Phi\Phi^\top+n\lambda I) ( Φ ⊤ Φ + nλ I ) Φ ⊤ = Φ ⊤ ( Φ Φ ⊤ + nλ I ) 表明 w = Φ ⊤ c w=\Phi^\top c w = Φ ⊤ c ,其中 ( K + n λ I ) c = y (K+n\lambda I)c=y ( K + nλ I ) c = y ,所以兩個方程組給出同一個預測函數。前者是 p × p p\times p p × p ,後者是 n × n n\times n n × n ;在第一個例題中,Φ = ( 1 , 2 ) ⊤ \Phi=(1,2)^\top Φ = ( 1 , 2 ) ⊤ 給出 6 w = 1 6w=1 6 w = 1 ,同樣得 w = 1 / 6 w=1/6 w = 1/6 。
零初始化梯度下降亦透過軌跡選最小範數。有限停止時間下,小奇異值方向可能尚未接近極限;遞推中的乘數冪描述了各方向的不同進度。這啟發早停與正則化的比較,但並不表示某一次停止,能在所有方向精確等價於同一個嶺參數。
例題詳解
例題 3.1.5
(奇異 Gram 矩陣仍有唯一嶺函數)
取 k ( x , z ) = x z k(x,z)=xz k ( x , z ) = x z 、x 1 = 1 , x 2 = 2 x_1=1,x_2=2 x 1 = 1 , x 2 = 2 、y = ( 1 , 0 ) ⊤ y=(1,0)^\top y = ( 1 , 0 ) ⊤ 、λ = 1 / 2 \lambda=1/2 λ = 1/2 。Gram 矩陣兩行為 ( 1 , 2 ) , ( 2 , 4 ) (1,2),(2,4) ( 1 , 2 ) , ( 2 , 4 ) ,秩為一。因 n λ = 1 n\lambda=1 nλ = 1 ,嶺方程矩陣兩行是 ( 2 , 2 ) , ( 2 , 5 ) (2,2),(2,5) ( 2 , 2 ) , ( 2 , 5 ) ,行列式為六,解為 c = ( 5 / 6 , − 1 / 3 ) ⊤ c=(5/6,-1/3)^\top c = ( 5/6 , − 1/3 ) ⊤ 。函數是 ( c 1 + 2 c 2 ) x = x / 6 (c_1+2c_2)x=x/6 ( c 1 + 2 c 2 ) x = x /6 。加上任意倍數的 ( − 2 , 1 ) ⊤ (-2,1)^\top ( − 2 , 1 ) ⊤ 仍表示同一函數,但不再解同一個標準嶺系統。直接對 1 4 [ ( w − 1 ) 2 + ( 2 w ) 2 ] + 1 4 w 2 \tfrac14[(w-1)^2+(2w)^2]+\tfrac14w^2 4 1 [( w − 1 ) 2 + ( 2 w ) 2 ] + 4 1 w 2 微分得 3 w − 1 / 2 3w-1/2 3 w − 1/2 ,亦驗證 w = 1 / 6 w=1/6 w = 1/6 。
在 [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] 近似 u ( x ) = x 2 u(x)=x^2 u ( x ) = x 2 ,取節點 − 1 , 0 , 1 -1,0,1 − 1 , 0 , 1 ,斜率是負一及正一,故 p ( x ) = 1 − ( x + 1 ) + 2 σ ( x ) = ∣ x ∣ p(x)=1-(x+1)+2\sigma(x)=|x| p ( x ) = 1 − ( x + 1 ) + 2 σ ( x ) = ∣ x ∣ 。在 [ 0 , 1 ] [0,1] [ 0 , 1 ] 的誤差為 x ( 1 − x ) x(1-x) x ( 1 − x ) ,於 1 / 2 1/2 1/2 最大,值為 1 / 4 1/4 1/4 ;負半軸對稱。取 Lipschitz 常數 A = 2 A=2 A = 2 給出有效但較鬆的界一。長為 h h h 的一段上,直接展開可得平方插值誤差 ( x − t j ) ( t j + 1 − x ) (x-t_j)(t_{j+1}-x) ( x − t j ) ( t j + 1 − x ) 。網格減半至 h = 1 / 2 h=1/2 h = 1/2 ,精確最大誤差便為 1 / 16 1/16 1/16 。此構造使用了節點處的真實目標值。
設 X = ( 1 , 1 ) , y = 2 X=(1,1),y=2 X = ( 1 , 1 ) , y = 2 。全部 ( 1 + t , 1 − t ) ⊤ (1+t,1-t)^\top ( 1 + t , 1 − t ) ⊤ 都可插值,平方範數為 2 + 2 t 2 2+2t^2 2 + 2 t 2 ,在 ( 1 , 1 ) ⊤ (1,1)^\top ( 1 , 1 ) ⊤ 最小。從零作梯度下降會保持兩座標相等,當 0 < η < 1 0<\eta<1 0 < η < 1 便收斂至此解。若從 ( 3 , − 1 ) ⊤ (3,-1)^\top ( 3 , − 1 ) ⊤ 開始,因已精確擬合而永遠不動,平方範數為十。在新特徵 ( 1 , − 1 ) (1,-1) ( 1 , − 1 ) 上,兩個預測分別為零及四。相同訓練插值未能決定誰較接近未知總體目標。
常見錯誤
公式看似「正」不等於核半正定。條件必須對全部有限點集及全部係數成立。例如 k ( x , z ) = − x z k(x,z)=-xz k ( x , z ) = − x z 在單點 x = 1 x=1 x = 1 的 Gram 值已是負一,立即失敗。只檢查幾個相似度不足夠;有效特徵分解則一次證明所有情況。
正則化係數依賴損失正規化。本節使用 1 / ( 2 n ) 1/(2n) 1/ ( 2 n ) ,故系統含 n λ n\lambda nλ ;若改用未平均的損失 1 2 ∑ i ( f ( x i ) − y i ) 2 + λ 2 ∥ f ∥ 2 \tfrac12\sum\limits_i(f(x_i)-y_i)^2+\tfrac\lambda2\|f\|^2 2 1 i ∑ ( f ( x i ) − y i ) 2 + 2 λ ∥ f ∥ 2 ,方程便是 ( K + λ I ) c = y (K+\lambda I)c=y ( K + λ I ) c = y ;把一個方程配上另一個目標,有效懲罰便差了因子 n n n 。Gram 矩陣奇異與最小函數唯一並不矛盾,係數唯一與函數唯一是兩件事。
近似問函數是否存在,最優化問算法是否找到權重,泛化問新數據上如何。折點構造只證明第一件事;線性最小範數分析證明特定算法選擇,未證明任意網絡或任意插值器的泛化。更強結論需要更多條件。
總結
核擬合落在有限生成空間,因正交分量不改變觀察預測卻增加懲罰。ReLU 以斜率跳躍構造分段線性近似。過度參數化最小二乘分開觀察預測與不可見的零空間分量,顯示初始化的作用。這些表示與選擇工具各自留下明確的統計限制。
練習
快速檢查
(若 k 1 , k 2 k_1,k_2 k 1 , k 2 半正定且 a , b ≥ 0 a,b\ge0 a , b ≥ 0 ,證明 a k 1 + b k 2 ak_1+bk_2 a k 1 + b k 2 半正定。若原特徵映射有限維,給出新映射。)
解答 · 答案 任意 Gram 二次型都是兩個非負二次型的非負加權和,且對稱性保留。把 a ϕ 1 ( x ) \sqrt a\phi_1(x) a ϕ 1 ( x ) 與 b ϕ 2 ( x ) \sqrt b\phi_2(x) b ϕ 2 ( x ) 串接,內積便是所需核;某係數為零亦成立。
快速檢查
(在 [ 0 , 1 ] [0,1] [ 0 , 1 ] 以節點 0 , 1 / 3 , 1 0,1/3,1 0 , 1/3 , 1 插值 u ( x ) = ∣ x − 1 / 3 ∣ u(x)=|x-1/3| u ( x ) = ∣ x − 1/3∣ ,求折點表示及一致誤差。)
解答 · 答案 初值 1 / 3 1/3 1/3 ,斜率負一及正一,跳躍為二,故 p ( x ) = 1 / 3 − x + 2 σ ( x − 1 / 3 ) p(x)=1/3-x+2\sigma(x-1/3) p ( x ) = 1/3 − x + 2 σ ( x − 1/3 ) 。目標僅有一個折點,兩側皆完全相等,一致誤差為零。折點不可微並不妨礙插值或表示。
快速檢查
(對 X = ( 1 , 1 ) , y = 2 X=(1,1),y=2 X = ( 1 , 1 ) , y = 2 ,從 ( 2 , 0 ) ⊤ (2,0)^\top ( 2 , 0 ) ⊤ 開始梯度下降,求極限並解釋零初始化最小範數結論為何不適用。)
解答 · 答案 初始點已滿足 X w = 2 Xw=2 X w = 2 ,梯度為零,故每步均為 ( 2 , 0 ) ⊤ (2,0)^\top ( 2 , 0 ) ⊤ 。它的零空間分量是 ( 1 , − 1 ) ⊤ (1,-1)^\top ( 1 , − 1 ) ⊤ ,與 X † y = ( 1 , 1 ) ⊤ X^\dagger y=(1,1)^\top X † y = ( 1 , 1 ) ⊤ 相加給同一答案。其範數大於零初始化所得的解。
快速檢查
(在 [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] 近似平方,多少個等長區間足以令精確一致誤差不超過 0.01 0.01 0.01 ?寫出所用架構的內部折點數。)
解答 · 答案 m m m 段時 h = 2 / m h=2/m h = 2/ m ,精確最大誤差為 h 2 / 4 = 1 / m 2 h^2/4=1/m^2 h 2 /4 = 1/ m 2 ,故 m ≥ 10 m\ge10 m ≥ 10 足夠,有九個內部折點。表示仍包括仿射項;若架構禁止線性旁路,須用前述額外 ReLU 單元實現線性部分。