动机
训练程序只能看见有限样本,所得预测器却要处理尚未出现的观察。经验平均可以由数据计算,因此不可或缺;但若同一批数据同时用来搜索预测器,这个平均亦可能令人误判。训练误差小,回答的是样本上的问题。泛化则问:换上来自同一分布的新观察,答案是否仍然可靠?
问题即使在简单分类中也会出现。假如分类器可以任意指定一个巨大有限定义域上每点的标签,它便能记住已观察的答案,并在其他地方任意作答。对一个预先固定的分类器,平均值未必不可靠;真正需要控制的是利用样本从整个假设类中挑选成员的过程。因此,我们要同时控制所有候选者,或者另行分析选择程序。
本节用三种方法描述搜索的规模:有限类可以计数;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 时没有信息。定理没有承诺每个有限类在任何样本量都能良好泛化。