《机器学习理论导引》笔记目录
0 补充感言
我是真的没有想到这章的内容竟然这么多,之前 (上) 的部分其实在本地我分了两个 markdown 文件,因为单一 markdown 文件太大甚至已经影响到预览的响应速度了。
4.2 泛化误差下界
泛化误差下界的意义
- 指出学习算法能力的极限
- 对于任何学习算法存在一个数据分布,样本数量有限时,学习算法不能以较大概率输出目标概念的近似。
一般证明方法
- 通常采用构造法证明
- 证明的要点 : 如何构造这样的数据分布
4.2.1 可分情形
Fubini 定理
若函数 f(x,y)f(x,y) 的期望 Ex,y[∣f(x,y)∣]<∞mathbb{E}_{x,y}[|f(x, y)|] < infty,则 Ex[Ey[f(x,y)]]=Ey[Ex[f(x,y)]]mathbb{E}_x[mathbb{E}_y[f(x, y)]]=mathbb{E}_y[mathbb{E}_x[f(x, y)]]
定理 4.6
若假设空间 Hmathcal{H} 的 VC 维 d>1d>1,则对任意 m>1m>1 和学习算法 Lmathcal{L},存在分布 Dmathcal{D} 和目标概念 c∈Hcinmathcal{H} 使得
P(E(hD,c)>d−132m)⩾1100Pleft(E(h_D,c)>frac{d-1}{32m}right)geqslantfrac{1}{100}
其中 hDh_D 为学习算法 Lmathcal{L} 基于大小为 mm 的训练集 DD 输出的假设。
证明
对于给定的 D∈ADin A,考虑来自均匀分布 Umathcal{U} 的目标概念 c:S↦{−1,+1}c : mathcal{S}mapsto{−1, +1},我们可以得到以下结论 :
EU[E(hD,c)]=∑c∑x∈SI(hD(x)≠c(x))Px∼D(x)Pc∼U(c)⩾∑c∑x∈S−Dˉ−{x0}I(hD(x)≠c(x))Px∼D(x)Pc∼U(c)=∑x∈S−Dˉ−{x0}(∑cI(hD(x)≠c(x))Pc∼U(c))Px∼D(x)=12∑x∈S−Dˉ−{x0}Px∼D(x)⩾12d−128ϵd−1=2ϵbegin{aligned}
mathbb{E}_Uleft[Eleft(h_D, cright)right] & =sum_c sum_{x in S} mathbb{I}left(h_D(x) neq c(x)right) P_{x sim mathcal{D}}(x) P_{c sim mathcal{U}}(c) \
& geqslant sum_c sum_{x in S-bar{D}-left{x_0right}} mathbb{I}left(h_D(x) neq c(x)right) P_{x sim mathcal{D}}(x) P_{c sim mathcal{U}}(c) \
& =sum_{x in S-bar{D}-left{x_0right}}left(sum_c mathbb{I}left(h_D(x) neq c(x)right) P_{c sim mathcal{U}}(c)right) P_{x sim D}(x) \
& =frac{1}{2} sum_{x in S-bar{D}-left{x_0right}} P_{x sim D}(x) \
& geqslant frac{1}{2} frac{d-1}{2} frac{8 epsilon}{d-1}=2 epsilon
end{aligned}
上式对于任意 D∈ADin A 均成立,因此关于 AA 的期望也成立,有 ED∈A[EU[E(hD,c)]]⩾2ϵmathbb{E}_{Din A}[mathbb{E}_{mathcal{U}}[E (h_D,c)]]geqslant2epsilon。
可知交换期望计算顺序不等式依然成立, 即有 ED∈A[EU[E(hD,c)]]⩾2ϵmathbb{E}_{Din A}[mathbb{E}_{mathcal{U}}[E (h_D,c)]]geqslant2epsilon 期望的下界为 2ϵ2epsilon,必定存在一个目标概念 c∗∈Hc^∗inmathcal{H} 满足 ED∈A[EU[E(hD,c∗)]]⩾2ϵmathbb{E}_{Din A}[mathbb{E}_{mathcal{U}}[E (h_D,c^*)]]geqslant2epsilon
ED∈A[E(hD,c∗)]=∑D:E(hD,c∗)>ϵE(hD,c∗)P(D)+∑D:E(hD,c∗)⩽ϵE(hD,c∗)P(D)⩽Px∼D(x∈(S−{x0}))PD∈A(E(hD,c∗)>ϵ)+ϵ(1−PD∈A(E(hD,c∗)>ϵ))=8ϵPD∈A(E(hD,c∗)>ϵ)+ϵ(1−PD∈A(E(hD,c∗)>ϵ))=7ϵPD∈A(E(hD,c∗)>ϵ)+ϵbegin{aligned}
& mathbb{E}_{D in A}left[Eleft(h_D, c^*right)right] \
= & sum_{D: Eleft(h_D, c^*right)>epsilon} Eleft(h_D, c^*right) P(D)+sum_{D: Eleft(h_D, c^*right) leqslant epsilon} Eleft(h_D, c^*right) P(D) \
leqslant & P_{x sim mathcal{D}}left(x inleft(S-left{x_0right}right)right) P_{D in A}left(Eleft(h_D, c^*right)>epsilonright) \
& +epsilonleft(1-P_{D in A}left(Eleft(h_D, c^*right)>epsilonright)right) \
= & 8 epsilon P_{D in A}left(Eleft(h_D, c^*right)>epsilonright)+epsilonleft(1-P_{D in A}left(Eleft(h_D, c^*right)>epsilonright)right) \
= & 7 epsilon P_{D in A}left(Eleft(h_D, c^*right)>epsilonright)+epsilon
end{aligned}
通过上面两个式子,我们有
PD∈A(E(hD,c∗)>ϵ)⩾17ϵ(2ϵ−ϵ)=17P_{D in A}left(Eleft(h_D, c^*right)>epsilonright) geqslant frac{1}{7epsilon}(2epsilon-epsilon)=frac{1}{7}
借助于这个不等式,有
PD∼Dm(E(hD,c∗)>ϵ)⩾PD∈A(E(hD,c∗)>ϵ)PD∼Dm(D∈A)⩾17PD∼Dm(D∈A)P_{Dsimmathcal{D}^m}left(E(h_D,c^*)>epsilonright)\
geqslant P_{Din A}left(E(h_D,c^*)>epsilonright)P_{Dsimmathcal{D}^m}(Din A)\
geqslantfrac{1}{7}P_{Dsimmathcal{D}^m}(Din A)\
接下来,只要找到 PD∼Dm(D∈A)P_{Dsimmathcal{D}^m}(Din A) 的下界即可证明定理。令 lml_m 表示 Dˉbar{D} 的数目,根据 Chernoff 不等式可知,对于 γ>1gamma>1,有
PD∼Dm(lm⩾8ϵm(1+γ))⩽exp(−8ϵmγ23)P_{Dsimmathcal{D}^m}(l_mgeqslant8epsilon m(1+gamma))leqslantexpleft(-frac{8epsilon mgamma^2}{3}right)
令 ϵ=(d−1)/(32m),γ=1epsilon = (d − 1)/(32m),gamma = 1,可得
1−PD∼Dm(D∈A)=PD∼Dm(lm⩾d−12)⩽exp(−d−112)⩽exp(−112)1-P_{Dsimmathcal{D}^m}(Din A)\
=P_{Dsimmathcal{D}^m}(l_mgeqslantfrac{d-1}{2})leqslantexpleft(-frac{d-1}{12}right)leqslantexpleft(-frac{1}{12}right)
令 exp(−112)⩽1−7δexpleft(-frac{1}{12}right)leqslant1-7delta,可得 PD∼Dm(D∈A)⩾7δP_{Dsimmathcal{D}^m}(Din A)geqslant7delta,再根据
PD∼Dm(E(hD,c∗)>ϵ)⩾17PD∼Dm(D∈A)P_{Dsimmathcal{D}^m}left(E(h_D,c^*)>epsilonright)
geqslantfrac{1}{7}P_{Dsimmathcal{D}^m}(Din A)
可知
PD∼Dm(E(hD,c∗)>ϵ)⩾δP_{Dsimmathcal{D}^m}left(E(h_D,c^*)>epsilonright)geqslantdelta
取 δ=1100delta=frac{1}{100},从而定理得证。
4.2.2 不可分情形
对于不可分假设空间的泛化误差下界,主要比较学习算法 Lmathcal{L} 的泛化误差与贝叶斯最优分类器泛化误差之间的关系。
引理 4.2
令 σsigma 为服从 {−1,+1}{-1,+1} 上均匀分布的随机变量,对于 0<α<10<alpha<1 构造随机变量 ασ=12+ασ2alpha_{sigma}=frac{1}{2}+frac{alphasigma}{2}, 基于 σsigma 构造 X∼DσXsimmathcal{D}_{sigma},其中 Dσmathcal{D}_{sigma} 为伯努利分布 Bernoulli(ασ)text{Bernoulli} (alpha_sigma),即 P(X=1)=ασP(X=1)=alpha_sigma。令 S={X1,…,Xm}mathcal{S}={X_1,ldots,X_m} 表示从分布 Dσmmathcal{D}_{sigma}^m 独立同分布采样得到的大小为 mm 的集合, 即 S∼Dσmmathcal{S}sim mathcal{D}_{sigma}^m,则对于函数 f:Xm↦{−1,+1}f : X^mmapsto {-1,+1} 有
Eσ[PS∼Dgm(f(S)≠σ)]⩾Φ(2⌈m2⌉,α)mathbb{E}_{sigma}left[P_{mathcal{S}sim D_g^m}(f(mathcal{S})nesigma)right]geqslantPhi(2lceilfrac{m}{2}rceil,alpha)
其中 Φ(m,α)=14(1−1−exp(−mα21−α2))Phi(m,alpha)=frac{1}{4}left(1-sqrt{1-expleft(-frac{malpha^2}{1-alpha^2}right)}right)
引理 4.2 可以从投硬币的角度理解 :
- 我们可以将每个样本的标记视为投硬币的结果
- 红硬币投到正面概率为 1+α2frac{1+alpha}{2},对应于 σ=+1sigma =+1
- 蓝硬币投到正面概率为 1−α2frac{1-alpha}{2},对应于 σ=−1sigma =-1
- 算法需要通过硬币的投掷结果来判断,样本是由红硬币产生的还是蓝硬币产生的,对应于 ff
引理 4.2 告诉我们 : 为了区分样本对应哪个硬币,需要其在训练集中出现足够多的次数 (Ω(1/α2)Omega(1/alpha^2) 次)
引理 4.3
令 ZZ 为取值范围为 [0,1][0,1] 的随机变量,对于 γ∈[0,1)gammain[0,1) 有
P(Z>γ)⩾E[Z]−γ1−γ⩾E[Z]−γP(Z>gamma)geqslantfrac{mathbb{E}[Z]-gamma}{1-gamma}geqslantmathbb{E}[Z]-gamma
证明
E[Z]=∑z⩽γP(Z=z)z+∑z>γP(Z=z)z⩽∑z⩽γP(Z=z)γ+∑z>γP(Z=z)=γP(Z⩽γ)+P(Z>γ)=γ(1−P(Z>γ))+P(Z>γ)=(1−γ)P(Z>γ)+γbegin{aligned}
mathbb{E}[Z] & =sum_{zleqslantgamma}P(Z=z)z+sum_{z>gamma}P(Z=z)z\
& leqslantsum_{zleqslantgamma}P(Z=z)gamma+sum_{z>gamma}P(Z=z)\
&=gamma P(Zleqslantgamma)+P(Z>gamma)\
&=gammaleft(1-P(Z>gamma)right)+P(Z>gamma)\
&=(1-gamma)P(Z>gamma)+gamma
end{aligned}
定理 4.7
若假设空间 Hmathcal{H} 的 VC 维 d>1d>1,则对任意 m>1m>1 和学习算法 Lmathfrak{L},存在分布 Dmathcal{D} 使得
证明
S^={x1,…,xd}⊂Xhat{S}={x_1,ldots,x_d}subset X 表示能被 Hmathcal{H} 打散的集合。对于 α∈[0,1]alphain[0, 1] 和向量 σ=(σ1;…;σd)∈{−1,+1}dsigma=(sigma_1;ldots;sigma_d)in{−1,+1}^d,在 S×Ymathcal{S}timesmathcal{Y} 上构造如下分布 Dσmathcal{D}_{sigma}
PDσ(z=(xi,+1))=1d(12+σiα2)(i∈[d])PDσ(z=(xi,−1))=1d(12−σiα2)(i∈[d])P_{mathcal{D}_{sigma}}(z=(x_i,+1))=frac{1}{d}left(frac{1}{2}+frac{sigma_ialpha}{2}right)quad (iin[d])\
P_{mathcal{D}_{sigma}}(z=(x_i,-1))=frac{1}{d}left(frac{1}{2}-frac{sigma_ialpha}{2}right)quad (iin[d])
因为 Smathcal{S} 能被 Hmathcal{H} 打散,所以我们可以构造该数据下的贝叶斯最优分类器 hDσ∗(xi)=arg maxy∈{−1,+1}P(y∣xi)=sign(I(σi>0)−1/2),i∈[d]h^∗_{mathcal{D}_{sigma}}(x_i) = argmax_{yin{−1,+1}}P(y|x_i)=text{sign}(mathbb{I}(sigma_i>0) −1/2),iin[d],可知 hDσ∗∈Hh^∗_{mathcal{D}_{sigma}}inmathcal{H},对于 hDσ∗h^∗_{mathcal{D}_{sigma}} 计算可得
E(hDσ∗)=∑xi∈S(PDσ(z=(xi,+1))I(hDσ∗(xi)=−1)+PDσ(z=(xi,−1))I(hDσ∗(xi)=+1))=∑xi∈S(PDσ(z=(xi,+1))I(σi<0)+PDσ(z=(xi,−1))I(σi>0))=∑xi∈S1d(12−α2)=12−α2begin{aligned}
Eleft(h_{mathcal{D}_sigma}^*right)= & sum_{boldsymbol{x}_i in S}left(P_{mathcal{D}_sigma}left(z=left(boldsymbol{x}_i,+1right)right) mathbb{I}left(h_{mathcal{D}_sigma}^*left(boldsymbol{x}_iright)=-1right)right. \
& left.+P_{mathcal{D}_sigma}left(z=left(boldsymbol{x}_i,-1right)right) mathbb{I}left(h_{mathcal{D}_sigma}^*left(boldsymbol{x}_iright)=+1right)right) \
= & sum_{boldsymbol{x}_i in S}left(P_{mathcal{D}_sigma}left(z=left(boldsymbol{x}_i,+1right)right) mathbb{I}left(sigma_i<0right)+P_{mathcal{D}_sigma}left(z=left(boldsymbol{x}_i,-1right)right) mathbb{I}left(sigma_i>0right)right) \
= & sum_{boldsymbol{x}_i in S} frac{1}{d}left(frac{1}{2}-frac{alpha}{2}right)=frac{1}{2}-frac{alpha}{2}
end{aligned}
对于任意 h∈Hhinmathcal{H} 计算可得
E(h)=∑xi∈S(PDσ(z=(xi,+1))I(h(xi)≠hDσ∗(xi))I(hDσ∗(xi)=+1)+PDσ(z=(xi,+1))I(h(xi)=hDσ∗(xi))I(hDσ∗(xi)=−1)+PDσ(z=(xi,−1))I(h(xi)≠hDσ∗(xi))I(hDσ∗(xi)=−1)+PDσ(z=(xi,−1))I(h(xi)=hDσ∗(xi))I(hDσ∗(xi)=+1)=∑xi∈S(1+α2dI(h(xi)≠hDσ∗(xi))+1−α2dI(h(xi)=hDσ∗(xi)))=αd∑xi∈SI(h(xi)≠hDσ∗(xi))+12−α2begin{aligned}
E(h)= & sum_{x_i in S}left(P_{mathcal{D}_sigma}left(z=left(x_i,+1right)right) mathbb{I}left(hleft(x_iright) neq h_{mathcal{D}_sigma}^*left(x_iright)right) mathbb{I}left(h_{mathcal{D}_sigma}^*left(x_iright)=+1right)right. \
& +P_{mathcal{D}_sigma}left(z=left(x_i,+1right)right) mathbb{I}left(hleft(x_iright)=h_{mathcal{D}_sigma}^*left(x_iright)right) mathbb{I}left(h_{mathcal{D}_sigma}^*left(x_iright)=-1right) \
& +P_{mathcal{D}_sigma}left(z=left(x_i,-1right)right) mathbb{I}left(hleft(x_iright) neq h_{mathcal{D}_sigma}^*left(x_iright)right) mathbb{I}left(h_{mathcal{D}_sigma}^*left(x_iright)=-1right) \
& +P_{mathcal{D}_sigma}left(z=left(x_i,-1right)right) mathbb{I}left(hleft(x_iright)=h_{mathcal{D}_sigma}^*left(x_iright)right) mathbb{I}left(h_{mathcal{D}_sigma}^*left(x_iright)=+1right) \
= & sum_{x_i in S}left(frac{1+alpha}{2 d} mathbb{I}left(hleft(x_iright) neq h_{mathcal{D}_sigma}^*left(x_iright)right)+frac{1-alpha}{2 d} mathbb{I}left(hleft(x_iright)=h_{mathcal{D}_sigma}^*left(x_iright)right)right) \
= & frac{alpha}{d} sum_{x_i in S} mathbb{I}left(hleft(x_iright) neq h_{mathcal{D}_sigma}^*left(x_iright)right)+frac{1}{2}-frac{alpha}{2}
end{aligned}
从而可知
E(h)−E(hDσ∗)=αd∑xi∈SI(h(xi)≠hDσ∗(xi))E(h)-Eleft(h_{mathcal{D}_sigma}^*right)=frac{alpha}{d} sum_{x_i in S} mathbb{I}left(hleft(x_iright) neq h_{mathcal{D}_sigma}^*left(x_iright)right)
∣Z∣xlvert Zrvert_x 表示样本 xx 在 ZZ 中出现的次数
Eσ∼u,Z∼Dσm[1α(E(hZ)−E(hDσ∗))]=1d∑x∈SEσ∼u,Z∼Dσm[I(hZ(x)≠hDσ∗(x))]=1d∑x∈SEσ∼u[PZ∼Dσm(hZ(x)≠hDσ∗(x))]=1d∑x∈S∑n=0mEσ∼u[PZ∼Dσm(hZ(x)≠hDσ∗(x)∣∣Z∣x=n)P(∣Z∣x=n)]⩾1d∑x∈S∑n=0mΦ(2[n/2⌉,α)P(∣Z∣x=n)⩾1d∑x∈S∑n=0mΦ(n+1,α)P(∣Z∣x=n)⩾1d∑x∈SΦ(m/d+1,α)=Φ(m/d+1,α)begin{aligned}
& mathbb{E}_{sigma sim u, Z sim D_sigma^m}left[frac{1}{alpha}left(Eleft(h_Zright)-Eleft(h_{D_sigma}^*right)right)right] \
& =frac{1}{d} sum_{x in S} mathbb{E}_{sigma sim u, Z sim D_sigma^m}left[mathrm{I}left(h_Z(x) neq h_{D_sigma}^*(x)right)right] \
& =frac{1}{d} sum_{x in S} mathbb{E}_{sigma sim u}left[P_{Z sim D_sigma^m}left(h_Z(x) neq h_{D_sigma}^*(x)right)right] \
& =frac{1}{d} sum_{x in S} sum_{n=0}^m mathbb{E}_{sigma sim u}left[P_{Z sim D_sigma^m}left(h_Z(x) neqleft. h_{D_sigma}^*(x)|| Zright|_x=nright) Pleft(|Z|_x=nright)right] \
& geqslant frac{1}{d} sum_{x in S} sum_{n=0}^m Phi(2[n / 2rceil, alpha) Pleft(|Z|_x=nright) geqslant frac{1}{d} sum_{x in S} sum_{n=0}^m Phi(n+1, alpha) Pleft(|Z|_x=nright) \
& geqslant frac{1}{d} sum_{x in S} Phi(m / d+1, alpha)=Phi(m / d+1, alpha)
end{aligned}
由于上述关于 σsigma 期望的下界被 Φ(m/d+1,α)Phi(m/d + 1,alpha) 限制住,则必定存在 σ∗∈{−1,+1}dsigma^*in{-1,+1}^d 使得下式成立
EZ∼Dσ′[1α(E(hZ)−E(hDσ∗∗))]⩾Φ(m/d+1,α)mathbb{E}_{Zsimmathcal{D}’_{sigma}}left[frac{1}{alpha}left(Eleft(h_Zright)-Eleft(h_{mathcal{D}_sigma^*}^*right)right)right] geqslant Phi(m / d+1, alpha)
根据引理 4.3 可知,对于 σ∗sigma^* 以及任意 γ∈[0,1)gammain[0,1) 有
PZ∼Dσ∗m(1α(E(hZ)−E(hDσ∗∗))>γμ)⩾(1−γ)uP_{Zsim D^m_{sigma^*}}left(frac{1}{alpha}left(E(h_Z)-Eleft(h_{mathcal{D}_sigma^*}^*right)right)>gammamuright)geqslant(1-gamma)u
其中 u=Φ(m/d+1,α)u=Phi(m/d + 1,alpha),令 δdelta 与 ϵepsilon 满足条件 δ⩾(1−γ)udeltageqslant(1-gamma)u 以及 ϵ⩾γαuepsilongeqslantgammaalpha u,则有
PZ∼Dσ∗m(E(hZ)−E(hDσ∗∗)>ϵ)⩾δP_{Zsim D^m_{sigma^*}}left(E(h_Z)-Eleft(h_{mathcal{D}_sigma^*}^*right)>epsilonright)geqslantdelta
为了找到满足条件的 δdelta 与 ϵepsilon,令 γ=1−8δgamma= 1 − 8delta,则
δ⩽(1−γ)u⇔u⩾18⇔14(1−1−exp(−(m/d+1)α21−α2))⩾18⇔(m/d+1)α21−α2⩽ln43⇔md⩽(1α2−1)ln43−1begin{aligned}
deltaleqslant(1-gamma)uLeftrightarrow & ugeqslant frac{1}{8}\
Leftrightarrow & frac{1}{4}left(1-sqrt{1-expleft(-frac{(m/d+1)alpha^2}{1-alpha^2}right)}right)geqslantfrac{1}{8}\
Leftrightarrow & frac{(m/d+1)alpha^2}{1-alpha^2}leqslantlnfrac{4}{3}\
Leftrightarrow & frac{m}{d}leqslantleft(frac{1}{alpha^2}-1right)lnfrac{4}{3}-1
end{aligned}
令 α=8ϵ/(1−8δ)alpha= 8epsilon/(1 − 8delta),即 ϵ=γα/8epsilon=gammaalpha/8,即
md⩽((1−8δ)264ϵ2−1)ln43−1frac{m}{d}leqslantleft(frac{(1-8delta)^2}{64epsilon^2}-1right)lnfrac{4}{3}-1
令 δ⩽1/64deltaleqslant1/64,可得
((1−8δ)264ϵ2−1)ln43−1⩾(764)21ϵ2ln43−ln43−1left(frac{(1-8delta)^2}{64epsilon^2}-1right)lnfrac{4}{3}-1geqslantleft(frac{7}{64}right)^2frac{1}{epsilon^2}lnfrac{4}{3}-lnfrac{4}{3}-1
上式右端为关于 1ϵ2frac{1}{epsilon^2} 的函数 f(1ϵ2)f(frac{1}{epsilon^2}),可寻找 ww 使得 m/d⩽w/ϵ2m/dleqslant w/epsilon^2。令 ϵ⩽1/64epsilonleqslant1/64,由 w(1/64)2=f(1(1/64)2)frac{w}{(1/64)^2} = fleft(frac{1}{(1/64)^2}right) 可得
(764)2ln43−(164)2(ln43+1)≈0.003127⩾1320left(frac{7}{64}right)^2lnfrac{4}{3}-left(frac{1}{64}right)^2left(lnfrac{4}{3}+1right)approx 0.003127geqslantfrac{1}{320}
因此, 当 ϵ2⩽1320m/depsilon^2leqslant frac{1}{320m/d} 时,满足 δ⩽(1−γ)udeltaleqslant(1 − gamma)u 以及 ϵ⩽γαuepsilonleqslant gammaalpha u。取ϵ=d320mepsilon = sqrt{frac{d}{320m}} 和 δ=1/64delta = 1/64,定理得证