本文正在参与 人工智能创作者扶持计划
4.3 分析实例
理论回顾
定理3.6
Rd\mathbb{R}^dRd 中由非齐次线性超平面构成的假定空间 H\mathcal{H}H 的 VC维为 d+1
定理3.7
若 ∥x∥≤r\lVert x\rVert\le r∥x∥≤r，D 为巨细为 m 的数据集，则超平面族 H={x↦wTx:∥w∥≤}\mathcal{H}=\{x\mapsto \mathbf{w}^T\mathbf{x}:\lVert \mathbf{w}\rVert\le\Lambda\}H={x↦wTx:∥w∥≤} 的经历 Rademacher复杂度满意
RD(H)≤r22m\hat{\mathcal{R}_D}(\mathcal{H})\le\sqrt{\frac{r^2\Lambda^2}{m}}RD(H)≤mr22
定理3.8
若 ∥x∥≤r\lVert \mathbf{x}\rVert\le r∥x∥≤r，则超平面族 {x↦sign(wTx):minx∣wTx∣=1∧∥w∥≤}\{\mathcal{x}\mapsto\text{sign}(\mathbf{w}^T\mathbf{x}):\min_\mathbf{x}|\mathbf{w}^T\mathbf{x}|=1\land\lVert \mathbf{w}\rVert\le\Lambda\}{x↦sign(wTx):minx∣wTx∣=1∧∥w∥≤} 的 VC维 d满意
d≤r22d\le r^2\Lambda^2d≤r22
界说 3.3
函数空间 F\mathcal{F}F 关于 的经历 Rademacher 复杂度为
界说 3.4
函数空间 F\mathcal{F}F 关于 Z\mathcal{Z}Z 在散布 m 上的 Rademacher 复杂度为
引理 (第一章中的 Hoeffding 不等式)
若训练集 D\mathcal{D}D 包含 m 个从散布 D\mathcal{D}D 上独立同散布采样而得的样本，0<<10<\epsilon<10<<1，则对恣意 h∈Hh\in\mathcal{H}h∈H，有
P(E(h)−E(h)≥)≤exp(−2m2)P(E(h)−E(h)≤−)≤exp(−2m2)P(∣E(h)−E(h)∣≥)≤2exp(−2m2)P\left(\hat{E}(h)-E(h)\ge\epsilon\right)\le\exp{(-2m\epsilon^2)}\\
P\left(\hat{E}(h)-E(h)\le-\epsilon\right)\le\exp{(-2m\epsilon^2)}\\
P\left(|\hat{E}(h)-E(h)|\ge\epsilon\right)\le2\exp{(-2m\epsilon^2)}P(E(h)−E(h)≥)≤exp(−2m2)P(E(h)−E(h)≤−)≤exp(−2m2)P(∣E(h)−E(h)∣≥)≤2exp(−2m2)
学习方法的泛化才能分析往往是经过研讨泛化差错的概率上界进行的，具体来说，就是经过比较两种学习方法的泛化差错上界的巨细来比较它们的好坏。
泛化差错上界是样本容量和空间容量的函数，样本容量越大，空间容量越小，泛化差错上界越小。
距离丢失函数
引进距离使得泛化差错界与数据散布相关。
界说 4.1
对恣意 >0\rho>0>0，−\rho−− 距离丢失为界说在 z,z′∈Rz,z’\in\mathbb{R}z,z′∈R 上的丢失函数 ℓ:RR↦R+,ℓ(z,z′)=(zz′)\ell_\rho : \mathbb{R} \times \mathbb{R} \mapsto \mathbb{R}_+, \ell_\rho (z, z’) = \Phi_\rho(zz’)ℓ:RR↦R+,ℓ(z,z′)=(zz′)，其间
(x)={0⩽x1−x/0⩽x⩽1x⩽0\Phi_\rho(x)=\begin{cases}
0&\rho\leqslant x\\
1-x/\rho&0\leqslant x\leqslant\rho\\
1&x\leqslant0
\end{cases}(x)=⎩⎨⎧01−x/1⩽x0⩽x⩽x⩽0
关于集合 D=x1,…,xmD = x_1,\ldots, x_mD=x1,…,xm 与假定 hhh，经历距离丢失表明为
E(h)=1m∑i=1m(yih(xi))\widehat{E}_\rho(h)=\frac{1}{m}\sum_{i=1}^m\Phi_\rho(y_ih(x_i))E(h)=m1i=1∑m(yih(xi))
又 (yih(xi))⩽Iyih(xi)⩽\Phi_\rho (y_ih(x_i)) \leqslant \mathbb{I}_{y_ih(x_i)\leqslant\rho}(yih(xi))⩽Iyih(xi)⩽，由拉格朗日定理可得
∣(x1)−(x2)∣⩽∣′()∣∣x1−x2∣\lvert\Phi_\rho(x_1)-\Phi_\rho(x_2)\rvert\leqslant\lvert\Phi^{‘}_{\rho}(\xi)\rvert\lvert x_1-x_2\rvert∣(x1)−(x2)∣⩽∣′()∣∣x1−x2∣
由距离丢失函数界说可得
∣′()∣⩽1\lvert\Phi^{‘}_{\rho}(\xi)\rvert\leqslant\frac{1}{\rho}∣′()∣⩽1
(补充:关于在实数集的子集的函数 f:D⊆R→Rf : D\subseteq \mathbb{R}\rightarrow\mathbb{R}f:D⊆R→R，若存在常数 KKK，使得 ∣f(a)−f(b)∣⩽∣a−b∣,∀a,b∈D|f(a) − f(b)| \leqslant |a − b|,\forall a, b\in D∣f(a)−f(b)∣⩽∣a−b∣,∀a,b∈D，则称 fff 符合 Lipschitz 条件，关于 fff 最小的常数 KKK 称为 fff 的 Lipschitz 常数) 可知 \Phi_{\rho} 最多是 1\frac{1}{\rho}1-Lipschitz
Talagrand 缩短引理
引理 4.4 (Talagrand 缩短引理)
若 :R↦R\Phi : \mathbb{R} \mapsto \mathbb{R}:R↦R 为 ℓ\ell_{\rho}ℓ− Lipschitz 函数，则关于恣意实值假定空间 H\mathcal{H}H 有下式建立:
RD(∘H)⩽LRD(H)\widehat{\mathfrak{R}}_D(\Phi \circ \mathcal{H}) \leqslant L \hat{\mathfrak{R}}_D(\mathcal{H})RD(∘H)⩽LRD(H)
说明 Lipschitz 函数与假定空间 H\mathcal{H}H 复合后的经历 Rademacher 复杂度能够基于假定空间 H\mathcal{H}H 的经历 Rademacher 复杂度表明
证明
固定样本空间 D=(x1,…,xm)D = (x_1,\ldots, x_m)D=(x1,…,xm)，依据界说
ℜS(∘H)=1mE[suph∈H∑i=1mi(∘h)(xi)]=1m1,…,m−1E[Em[suph∈Hum−1(h)+m(∘h)(xm)]]\begin{aligned}
\Re_S(\Phi \circ H) & =\frac{1}{m} \mathrm{E}\left[\sup _{h \in H} \sum_{i=1}^m \sigma_i(\Phi \circ h)\left(x_i\right)\right] \\
& =\frac{1}{m} \sigma_{\sigma_1, \ldots, \sigma_{m-1}}^{\mathrm{E}}\left[\underset{\sigma_m}{\mathrm{E}}\left[\sup _{h \in H} u_{m-1}(h)+\sigma_m(\Phi \circ h)\left(x_m\right)\right]\right]
\end{aligned}ℜS(∘H)=m1E[h∈Hsupi=1∑mi(∘h)(xi)]=m11,…,m−1E[mE[h∈Hsupum−1(h)+m(∘h)(xm)]]
um−1(h)=∑i=1m−1i(∘h)(xi)u_{m−1}(h) =\sum^{m−1}_{i=1} \sigma_i(\Phi\circ h)(x_i)um−1(h)=∑i=1m−1i(∘h)(xi) 假定上确界能够达到，令 h1,h2∈Hh_1, h_2\in Hh1,h2∈H 满意
um−1(h1)+m(h1(xm))=suph∈Hum−1(h)+m(h(xm))um−1(h2)−m(h2(xm))=suph∈Hum−1(h)−m(h(xm))\begin{aligned}
& u_{m-1}\left(h_1\right)+\Phi_m\left(h_1\left(x_m\right)\right)=\sup _{h \in H} u_{m-1}(h)+\Phi_m\left(h\left(x_m\right)\right) \\
& u_{m-1}\left(h_2\right)-\Phi_m\left(h_2\left(x_m\right)\right)=\sup _{h \in H} u_{m-1}(h)-\Phi_m\left(h\left(x_m\right)\right)
\end{aligned}um−1(h1)+m(h1(xm))=h∈Hsupum−1(h)+m(h(xm))um−1(h2)−m(h2(xm))=h∈Hsupum−1(h)−m(h(xm))
假如上确界达不到，能够考虑挨近 \epsilon 的上确界，能够得到相似下面的定论。由于 m\sigma_mm 是 {−1,+1}\{−1, +1\}{−1,+1} 上的均匀散布，依据期望的界说有
E[supm∈Hum−1(h)+m(∘h)(xm)]]=12[um−1(h1)+(∘h1)(xm)]+12[um−1(h2)−(∘h2)(xm)]≤12[um−1(h1)+um−1(h2)+sL(h1(xm)−h2(xm))]=12[um−1(h1)+sLh1(xm)]+12[um−1(h2)−sLh2(xm)]≤12suph∈H[um−1(h)+sLh(xm)]+12suph∈H[um−1(h)−sLh(xm)]=Em[suph∈Hum−1(h)+mLh(xm)]\begin{aligned}
& \left.\mathrm{E}\left[\sup _{m \in H} u_{m-1}(h)+\sigma_m(\Phi \circ h)\left(x_m\right)\right]\right] \\
& =\frac{1}{2}\left[u_{m-1}\left(h_1\right)+\left(\Phi \circ h_1\right)\left(x_m\right)\right]+\frac{1}{2}\left[u_{m-1}\left(h_2\right)-\left(\Phi \circ h_2\right)\left(x_m\right)\right] \\
& \leq \frac{1}{2}\left[u_{m-1}\left(h_1\right)+u_{m-1}\left(h_2\right)+s L\left(h_1\left(x_m\right)-h_2\left(x_m\right)\right)\right] \\
& =\frac{1}{2}\left[u_{m-1}\left(h_1\right)+s L h_1\left(x_m\right)\right]+\frac{1}{2}\left[u_{m-1}\left(h_2\right)-s L h_2\left(x_m\right)\right] \\
& \leq \frac{1}{2} \sup _{h \in H}\left[u_{m-1}(h)+s L h\left(x_m\right)\right]+\frac{1}{2} \sup _{h \in H}\left[u_{m-1}(h)-s L h\left(x_m\right)\right] \\
& =\underset{\sigma_m}{\mathrm{E}}\left[\sup _{h \in H} u_{m-1}(h)+\sigma_m L h\left(x_m\right)\right]
\end{aligned}E[m∈Hsupum−1(h)+m(∘h)(xm)]]=21[um−1(h1)+(∘h1)(xm)]+21[um−1(h2)−(∘h2)(xm)]≤21[um−1(h1)+um−1(h2)+sL(h1(xm)−h2(xm))]=21[um−1(h1)+sLh1(xm)]+21[um−1(h2)−sLh2(xm)]≤21h∈Hsup[um−1(h)+sLh(xm)]+21h∈Hsup[um−1(h)−sLh(xm)]=mE[h∈Hsupum−1(h)+mLh(xm)]
令 s=sgn(h1(xm)−h2(xm))s =\text{sgn} (h_1 (x_m) − h2 (x_m))s=sgn(h1(xm)−h2(xm))，对一切其他 i(i≠m)i(i\ne m)i(i=m) 以相同的方法进行，得证。
二分类 SVM 的泛化差错界
定理 4.8 (关于 Rademacher 复杂度的泛化上界)
令 H\mathcal{H}H 为实值假定空间，给定 >0\rho > 0>0，关于 0<<10 < \delta < 10<<1 和 h∈Hh\in\mathcal{H}h∈H，以至少 1−1 − \delta1− 的概率有
E(h)⩽E(h)+2ℜm(H)+ln12mE(h)⩽E(h)+2ℜD(H)+3ln22m\begin{gathered}
E(h) \leqslant \widehat{E}_\rho(h)+\frac{2}{\rho} \Re_m(\mathcal{H})+\sqrt{\frac{\ln \frac{1}{\delta}}{2 m}} \\
E(h) \leqslant \widehat{E}_\rho(h)+\frac{2}{\rho} \widehat{\Re}_D(\mathcal{H})+3 \sqrt{\frac{\ln \frac{2}{\delta}}{2 m}}
\end{gathered}E(h)⩽E(h)+2ℜm(H)+2mln1E(h)⩽E(h)+2ℜD(H)+32mln2
证明
结构 H~={z=(x,y)↦yh(x):h∈H}\tilde{\mathcal{H}} = \{z = (x, y)\mapsto yh(x) : h \in \mathcal{H}\}H~={z=(x,y)↦yh(x):h∈H}，考虑值域为 [0,1][0,1][0,1] 的假定空间 F={∘f:f∈H~}\mathcal{F} =\left\{\Phi_{\rho} \circ f : f \in \tilde{\mathcal{H}}\right\}F={∘f:f∈H~} 由定理 4.4 知，对一切 g∈Fg\in \mathcal{F}g∈F，以至少 1−1 − \delta1− 的概率有 :
E[g(z)]⩽1m∑i=1mg(zi)+2ℜm(F)+ln12m\mathbb{E}[g(z)]\leqslant\frac{1}{m}\sum_{i=1}^mg(z_i)+2\Re_m(\mathcal{F})+\sqrt{\frac{\ln \frac{1}{\delta}}{2 m}}E[g(z)]⩽m1i=1∑mg(zi)+2ℜm(F)+2mln1
因而关于 h∈Hh\in\mathcal{H}h∈H，以至少 1−1 − \delta1− 的概率有:
E[(yh(x))]⩽E(h)+2ℜm(∘H~)+ln12m\mathbb{E}[\Phi_{\rho}(yh(x))]\leqslant\widehat{E}_{\rho}(h)+2\Re_m\left(\Phi_{\rho}\circ\tilde{\mathcal{H}}\right)+\sqrt{\frac{\ln \frac{1}{\delta}}{2 m}}E[(yh(x))]⩽E(h)+2ℜm(∘H~)+2mln1
由于对 ∀u∈R,Iu⩽0⩽(u)\forall u\in\mathbb{R},\mathbb{I}_{u\leqslant0}\leqslant\Phi_{\rho}(u)∀u∈R,Iu⩽0⩽(u) 建立，所以
E(h)=E[Iyh(x)⩽0]⩽E[(yh(x))]E(h)=\mathbb{E}\left[\mathbb{I}_{yh(x)\leqslant0}\right]\leqslant\mathbb{E}\left[\Phi_{\rho}(yh(x))\right]E(h)=E[Iyh(x)⩽0]⩽E[(yh(x))]
代入可知，以至少 1−1 − \delta1− 的概率有:
E(h)⩽E(h)+2ℜm(∘H~)+ln12mE(h)\leqslant\widehat{E}_{\rho}(h)+2\Re_m\left(\Phi_{\rho}\circ\tilde{\mathcal{H}}\right)+\sqrt{\frac{\ln \frac{1}{\delta}}{2 m}}E(h)⩽E(h)+2ℜm(∘H~)+2mln1
由于 \Phi_{\rho} 是 1\frac{1}{\rho}1-Lipschitz，由引理 4.4 可知
ℜm(∘H~)⩽1ℜm(H~)\Re_m\left(\Phi_{\rho}\circ\tilde{\mathcal{H}}\right)\leqslant\frac{1}{\rho}\Re_m(\tilde{\mathcal{H}})ℜm(∘H~)⩽1ℜm(H~)
又由 Rademacher 复杂度界说知
ℜm(H~)=1mED,[suph∈H∑i=1miyih(xi)]=1mED,[suph∈H∑i=1mih(xi)]=ℜm(H)\begin{aligned}
\Re_m(\tilde{\mathcal{H}})= &\frac{1}{m}\mathbb{E}_{D,\sigma}\left[\sup_{h\in\mathcal{H}}\sum_{i=1}^m\sigma_iy_ih(x_i)\right]\\
= & \frac{1}{m}\mathbb{E}_{D,\sigma}\left[\sup_{h\in\mathcal{H}}\sum_{i=1}^m\sigma_ih(x_i)\right]\\
= & \Re_m(\mathcal{H})
\end{aligned}ℜm(H~)===m1ED,[h∈Hsupi=1∑miyih(xi)]m1ED,[h∈Hsupi=1∑mih(xi)]ℜm(H)
代入得，以至少 1−1 − \delta1− 的概率有:
ℜm(∘H~)⩽1ℜm(H)⇒E(h)⩽E(h)+2ℜm(∘H~)+ln12m⩽E(h)+2ℜm(H)+ln12m\Re_m\left(\Phi_{\rho}\circ\tilde{\mathcal{H}}\right)\leqslant\frac{1}{\rho}\Re_m(\mathcal{H})\\
\Rightarrow{\color{blue}E(h)}\leqslant\widehat{E}_{\rho}(h)+2\Re_m\left(\Phi_{\rho}\circ\tilde{\mathcal{H}}\right)+\sqrt{\frac{\ln \frac{1}{\delta}}{2 m}}\\{\color{blue}\leqslant\widehat{E}_\rho(h)+\frac{2}{\rho} \Re_m(\mathcal{H})+\sqrt{\frac{\ln \frac{1}{\delta}}{2 m}}}ℜm(∘H~)⩽1ℜm(H)⇒E(h)⩽E(h)+2ℜm(∘H~)+2mln1⩽E(h)+2ℜm(H)+2mln1
得证。由定理 4.4 可知，以至少 1−1 − \delta1− 的概率有:
E[g(z)]⩽1m∑i=1mg(zi)+2ℜD(F)+3ln22m\mathbb{E}[g(z)]\leqslant\frac{1}{m}\sum_{i=1}^mg(z_i)+2\widehat{\Re}_D(\mathcal{F})+3\sqrt{\frac{\ln \frac{2}{\delta}}{2 m}}E[g(z)]⩽m1i=1∑mg(zi)+2ℜD(F)+32mln2
同理可证，以至少 1−1 − \delta1− 的概率有:
E(h)⩽E(h)+2ℜD(∘H)+3ln22mE(h) \leqslant \widehat{E}_\rho(h)+2\widehat{\Re}_D\left(\Phi_{\rho}\circ\mathcal{H}\right)+3 \sqrt{\frac{\ln \frac{2}{\delta}}{2 m}}E(h)⩽E(h)+2ℜD(∘H)+32mln2
关于经历 Rademacher 复杂度，由于 \Phi_{\rho} 是 1\frac{1}{\rho}1-Lipschitz，相似地有
RD(∘H~)⩽1RD(H~)RD(H~)=1mE[suph∈H∑i=1miyih(xi)]=1mE[suph∈H∑i=1mih(xi)]=RD(H)\begin{aligned}
& \hat{\mathfrak{R}}_D\left(\Phi_\rho \circ \tilde{\mathcal{H}}\right) \leqslant \frac{1}{\rho} \widehat{\mathfrak{R}}_D(\tilde{\mathcal{H}}) \\
& \widehat{\mathfrak{R}}_D(\tilde{\mathcal{H}})=\frac{1}{m} \mathbb{E}_\sigma\left[\sup _{h \in \mathcal{H}} \sum_{i=1}^m \sigma_i y_i h\left(\boldsymbol{x}_i\right)\right] \\
&=\frac{1}{m} \mathbb{E}_{\boldsymbol{\sigma}}\left[\sup _{h \in \mathcal{H}} \sum_{i=1}^m \sigma_i h\left(\boldsymbol{x}_i\right)\right] \\
&=\hat{\mathfrak{R}}_D(\mathcal{H})
\end{aligned}RD(∘H~)⩽1RD(H~)RD(H~)=m1E[h∈Hsupi=1∑miyih(xi)]=m1E[h∈Hsupi=1∑mih(xi)]=RD(H)
则以至少 1−1 − \delta1− 的概率有:
E(h)⩽E(h)+2ℜD(H)+3ln22m\color{blue}E(h) \leqslant \widehat{E}_\rho(h)+\frac{2}{\rho} \widehat{\Re}_D(\mathcal{H})+3 \sqrt{\frac{\ln \frac{2}{\delta}}{2 m}}E(h)⩽E(h)+2ℜD(H)+32mln2
定理 4.9
令 H\mathcal{H}H 为实值假定空间，关于 0<<10 < \delta < 10<<1 和 h∈Hh\in\mathcal{H}h∈H，以及恣意 ∈(0,1)\rho\in(0, 1)∈(0,1)，以至少 1−1-\delta1− 的概率有:
E(h)⩽E(h)+4ℜm(H)+lnlog22m+ln22mE(h)⩽E(h)+4RD(H)+lnlog22mm+3ln42m\begin{aligned}
& E(h) \leqslant \widehat{E}_\rho(h)+\frac{4}{\rho} \Re_m(\mathcal{H})+\sqrt{\frac{\ln \log _2 \frac{2}{\rho}}{m}}+\sqrt{\frac{\ln \frac{2}{\delta}}{2 m}} \\
& E(h) \leqslant \widehat{E}_\rho(h)+\frac{4}{\rho} \widehat{\mathfrak{R}}_D(\mathcal{H})+\sqrt{\frac{\ln _{\log _2 \frac{2}{\rho}}^m}{m}}+3 \sqrt{\frac{\ln \frac{4}{\delta}}{2 m}}
\end{aligned}E(h)⩽E(h)+4ℜm(H)+mlnlog22+2mln2E(h)⩽E(h)+4RD(H)+mlnlog22m+32mln4
由定理 3.7 可知 RD(H)⩽r22m\widehat{\mathfrak{R}}_D(\mathcal{H})\leqslant\sqrt{\frac{r^2\Lambda^2}{m}}RD(H)⩽mr22，两边取期望得到，Rm(H)⩽r22m\mathfrak{R}_m(\mathcal{H})\leqslant\sqrt{\frac{r^2\Lambda^2}{m}}Rm(H)⩽mr22
推论 4.1
令 H={x↦w⋅x:∣w∣⩽}\mathcal{H}=\{x\mapsto w \cdot x : \lvert w\rvert\leqslant\Lambda\}H={x↦w⋅x:∣w∣⩽} 且 ∥x∥⩽r\lVert x\rVert \leqslant r∥x∥⩽r，关于 0<<10 < \delta < 10<<1 和 h∈Hh\in\mathcal{H}h∈H 和固定的 >0\rho > 0>0，以至少 1−1-\delta1− 的概率有:
E(h)⩽E(h)+2r22/2m+ln12mE(h)\leqslant\widehat{E}_{\rho}(h)+2\sqrt{\frac{r^2\Lambda^2/\rho^2}{m}}+\sqrt{\frac{\ln \frac{1}{\delta}}{2 m}}E(h)⩽E(h)+2mr22/2+2mln1
推论 4.2
令 H={x↦w⋅x:∣w∣⩽}\mathcal{H}=\{x\mapsto w \cdot x : \lvert w\rvert\leqslant\Lambda\}H={x↦w⋅x:∣w∣⩽} 且 ∥x∥⩽r\lVert x\rVert \leqslant r∥x∥⩽r，关于 0<<10 < \delta < 10<<1 和 h∈Hh\in\mathcal{H}h∈H 和恣意的的 ∈(0,1)\rho\in(0,1)∈(0,1)，以至少 1−1-\delta1− 的概率有:
E(h)⩽E(h)+4r22/2m+lnlog22m+ln22mE(h)\leqslant\widehat{E}_{\rho}(h)+4\sqrt{\frac{r^2\Lambda^2/\rho^2}{m}}+\sqrt{\frac{\ln\log_2\frac{2}{\rho}}{m}}+\sqrt{\frac{\ln \frac{2}{\delta}}{2 m}}E(h)⩽E(h)+4mr22/2+mlnlog22+2mln2
经历危险最小化
界说 4.2
假如学习算法 L\mathfrak{L}L 输出 H\mathcal{H}H 中具有最小经历差错的假定 hhh，即 E(h)=minh′∈HE(h′)\hat{E}(h)=\min_{h’\in\mathcal{H}}\widehat{E}(h’)E(h)=minh′∈HE(h′)，则称 L\mathfrak{L}L 为满意经历危险最小化准则的算法
假定 L\mathfrak{L}L 为满意经历危险最小化准则的算法，令 ggg 表明 H\mathcal{H}H 中具有最小泛化差错的假定，即 E(h)=minh′∈HE(h′)E(h)= \min_{h’\in\mathcal{H}}\widehat{E}(h’)E(h)=minh′∈HE(h′) 由引理 2.1 可知，
P(∣E(g)−E(g)∣⩾2)⩽2exp(−m22)P(\lvert\widehat{E}(g)-E(g)\rvert\geqslant\frac{\epsilon}{2})\leqslant2\exp\left(-\frac{m\epsilon^2}{2}\right)P(∣E(g)−E(g)∣⩾2)⩽2exp(−2m2)
由于 ′=2,(ln2/′)2m⩽2\delta’=\frac{\delta}{2},\sqrt{\frac{(\ln2/\delta’)}{2m}}\leqslant\frac{\epsilon}{2}′=2,2m(ln2/′)⩽2，即 2exp(−m22)⩽′2\exp\left(-\frac{m\epsilon^2}{2}\right)\leqslant\delta’2exp(−2m2)⩽′ 以至少 1−21-\frac{\delta}{2}1−2 的概率有:
E(g)−2⩽E(g)⩽E(g)+2\widehat{E}(g)-\frac{\epsilon}{2}\leqslant E(g)\leqslant\widehat{E}(g)+\frac{\epsilon}{2}E(g)−2⩽E(g)⩽E(g)+2
由定理 4.3 可知，以至少 1−21-\frac{\delta}{2}1−2 的概率有:
∣E(h)−E(h)∣⩽2\lvert E(h)-\widehat{E}(h) \rvert\leqslant\frac{\epsilon}{2}∣E(h)−E(h)∣⩽2
即 E(h)⩽E(h)+2E(h)\leqslant\widehat{E}(h)+\frac{\epsilon}{2}E(h)⩽E(h)+2 (依据经历最小化准则，E(h)⩽E(g)\widehat{E}(h)\leqslant\widehat{E}(g)E(h)⩽E(g))，所以以至少 1−1-\delta1− 的概率有:
E(h)−E(g)⩽E(h)+2−(E(g)+2)=E(h)−E(g)+⩽\begin{aligned}
E(h)-E(g) & \leqslant \widehat{E}(h)+\frac{\epsilon}{2}-\left(\widehat{E}(g)+\frac{\epsilon}{2}\right) \\
& =\widehat{E}(h)-\widehat{E}(g)+\epsilon \\
& \leqslant \epsilon
\end{aligned}E(h)−E(g)⩽E(h)+2−(E(g)+2)=E(h)−E(g)+⩽
所以若学习算法 L\mathfrak{L}L 输出 H\mathcal{H}H 中具有最小经历差错的假定 hhh，其泛化差错
E(h)E(h)E(h) 以至少 1−1-\delta1− 的概率不大于最小泛化差错 E(h)+E(h) +\epsilonE(h)+
定论
- 泛化差错边界不取决于维度，而取决于距离
- 这需求咱们在更高维的特征空间中寻觅大距离的超平面
计算问题
- 高维特征空间上运用点积是很贵重的
- 能够运用核函数来处理
Orz 快累死了。
