动机
学习问题至少有两个几何选择。表示方式决定能写出什么预测,拟合规则则决定数据、惩罚或算法偏好其中哪一个。核方法用特征向量的内积作第一个选择;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 单元实现线性部分。