机器学习：Rademacher复杂度

1，记号样例集：独立同分布样本, 仅考虑二分类问题。泛化误差和经验误差：设为从到的一个映射。泛化误差：分类器的期望误差，模型在新样本集（测试集）上的误差。含义：在测试集（可以是整个集合）中任取一个则的概率或期望（因为当值取1或0时，期望=概率），经验误差（经验误差期望）：分类器在给定样例集上的平均误差，模型在训练集上的误差。其中表示满足则输出1，否则输出0。含义：训练集上所有的数据数/训练集样本

燕双嘤

3924人浏览 · 2021-11-11 07:45:36

燕双嘤 · 2021-11-11 07:45:36 发布

1，记号

样例集：独立同分布样本, 仅考虑二分类问题。

$D=\left \{ (x_1,y_1), (x_2,y_2),... ,(x_m,y_m)\right \},x_i\in X,y_i\in Y=\left \{ -1,+1 \right \}$

泛化误差和经验误差：设 $h$ 为从 $X$ 到 $Y$ 的一个映射。

泛化误差：模型在新样本集（测试集）上的误差。

$E(h;D)=P_{x\sim D}(h(x)\neq y)$

含义：在测试集（可以是整个集合） $D$ 中任取一个 $x$ 则 $h(x)\neq y$ 的概率或期望（因为当值取1或0时，期望=概率）。

经验误差（经验误差期望）：模型在训练集上的误差。

$\hat{E}(h;{D}')=\frac{1}{m}\sum_{i=1}^{m}\mathbb{I}(h(x_i)\neq y_i)$

其中 $\mathbb{I}(*)$ 表示满足 $*$ 则输出1，否则输出0。

含义：训练集 ${D}'$ 上所有 $h(x_i)\neq y_i$ 的数据数/训练集样本数，不能写为概率的原因是，给定 $x_i$ 则有确定的 $y_i$ 与之对应。

PS：由于 $D$ 是 ${D}'$ 的独立同分布采样，因此 $h$ 的经验误差的期望等于其泛化误差。在上下文明确时，将 $E(h;D)$ 和 $\hat{E}(h;{D}')$ 分别简记为 $E(h)$ 和 $\hat{E}(h)$ 。

误差参数 $\epsilon$ ：

$\epsilon$ 为 $E(h)$ 的上限，即 $E(h) \leqslant \epsilon$ 。
表示预先设定的学得模型所应满足的误差要求。

一致性：若 $h$ 在数据集 $D$ 上的经验误差为0，则称 $h$ 与 $D$ 一致，否则不一致。

不合：对于任意两个映射 $h1,h2 \in X \rightarrow Y$ ，通过“不合”度量它们的差别：

$d(h1,h2)=P_{x\sim D}(h_1(x)\neq h_2(x))$

2，学习

概念：概念是从样本空间 $X$ 到标记空间 $Y$ 的映射，它决定示例 $x$ 的真实标记 $y$ 。

目标概念：如果对任何样例 $(x,y)$ 均有 $c(x)=y$ 成立，则称 $c$ 为目标概念。
概念类：所有我们希望学得的目标概念所构成的集合称为”概念类”, 用符号 $C$ 表示。

假设空间：给定学习算法 $L$ ，它所考虑的所有可能概念的集合, 用符号 $H$ 表示。

由于学习算法事先并不知道概念类的真实存在, 因此 $H$ 和 $C$ 通常是不同的, 学习算法会把自认为可能的目标概念集中起来构成 $H$ 。
对于 $h \in H$ ，由于并不能确定它是否真的是目标概念，因此称为“假设”。显然， $h$ 也是从样本空间 $X$ 到标记空间 $y$ 的映射。
学习过程可以视为 $L$ 在 $H$ 中进行的搜索过程。

可分的与不可分的：

可分的：若目标概念 $c \in H$ ，即 $H$ 中存在假设能将所有的示例完全正确分开(按照与真实标记一致的方式)，则称该问题对学习算法 $L$ 是“可分的”，也称“一致的”。
不可分的：若目标概念 $c\notin H$ ，则 $H$ 中不存在任何假设能将所有的示例完全正确分开，则称该问题对学习算法 $L$ 是“不可分的”，也称“不一致的”。

对于给定训练集 ${D}'$ ，我们希望基于学习算法 $L$ 学得的模型所对应的假设 $h$ 尽可能接近目标概念 $c$ 。

为什么不是希望精确地学到目标概念c呢？因为机器学习过程受到很多因素的制约：

获得训练结果集 ${D}'$ 往往仅包含有限数量的样例，因此通常会存在一些在 ${D}'$ 上“等效”的假设，学习算法无法区别这些假设。
从分布 $D$ 采样得到的 ${D}'$ 的过程有一定偶然性，即便对同样大小的不同训练集，学得结果也可能有所不同。

3，可学习的

概率近似正确（PAC）

我们希望以比较大的把握学得比较好的模型, 即以较大概率学得，且误差满足预设上限的模型。

令 $\delta$ 表示置信度，则上述要求可以表示为：

PAC辨识：对 $0 < \epsilon ,\delta <1$ ，所有 $c \in C$ 和分布 ${D}'$ ，若存在学习算法 $L$ ，其输出假设 $h \in H$ 满足：

$P(E(h)\leqslant \epsilon ) \geqslant 1-\delta$

则称学习算法 $L$ 能从假设空间 $H$ 中PAC辨识概念类 $C$ 。

换句话说：这样的学习算法 $L$ 能以较大概率（至少 $1-\delta$ ）学得目标概念 $c$ 的近似（误差最多为 $\epsilon$ ）。

PAC可学习：令 $m$ 表示从分布 ${D}'$ 中独立同分布采样得到的样例数目， $0 < \epsilon ,\delta <1$ ，对所有分布 $D$ ，若存在学习算法 $L$ 和多项式函数 $poly(\cdot ,\cdot ,\cdot ,\cdot )$ ，使得对于任何 $m \geqslant poly(\frac{1}{\epsilon } ,\frac{1}{\delta } ,size(x),size(c) )$ ， $L$ 能从假设空间 $H$ 中PAC辨识概念类 $C$ ，则称概念类 $C$ 对假设空间 $H$ 而言是PAC可学习的，有时也简称概念类 $C$ 是PAC可学习的。

PAC可学习性描述的是概念类 $C$ 的性质，若考虑到对应学习算法 $L$ 的时间复杂度，则有：

PAC学习算法：若学习算法 $L$ 使概念类 $C$ 为PAC可学习模型，且 $L$ 的运行时间也是多项式函数 $poly(\frac{1}{\epsilon } ,\frac{1}{\delta } ,size(x),size(c) )$ ，则称概念类 $C$ 是高效PAC学习的，称 $L$ 为概念类 $C$ 的PAC学习算法。

假定学习算法 $L$ 处理每个样本的时间为常数，则 $L$ 的时间复杂度等价于其样本复杂度。于是，我们对算法时间复杂度的分析可变为对样本复杂度的分析。

样本复杂度：满足PAC学习算法 $L$ 所需的 $m \geqslant poly(\frac{1}{\epsilon } ,\frac{1}{\delta } ,size(x),size(c) )$ 中最小的 $m$ ，称为学习算法的样本复杂度。

PAC学习的意义：

（1）给出了一个抽象地刻画机器学习能力的框架, 基于这个框架可以对很多重要问题进行理论探讨。

研究某任务在什么样的条件下可学得较好的模型？
某算法在什么样的条件下可进行有效的学习？
需要多少训练样例才能获得较好的模型？

（2）把复杂算法的时间复杂度的分析转变为对样本复杂度的分析。

假设空间 $H$ 的复杂度是影响可学习性的重要因素：

一般而言， $H$ 越大，其包含任意目标概念的可能性越大，但从中找到某个具体概念的难度也越大。
$|H|$ 有限时，我们称 $H$ 为“有限假设空间”，否则称为“无限假设空间”。

假设空间 $H$ 复杂度是影响学习任务难度的重要因素之一：

恰PAC可学习：假设空间 $H$ 包含了学习算法 $L$ 所有可能输出的假设，在PAC学习中假设空间与概念类完全相同，即 $H = C$ 。
直观的看，这意味着学习算法的能力与学习任务“恰好匹配”，即所有候选假设都来自概念类。
然而在现实应用中我们对概念类 $C$ 通常一无所知，设计一个假设空间与概念类恰好相同的学习算法通常是不切实际的。

研究的重点：当假设空间与概念类不同的情形，即 $H\neq C$ 。

4，Rademacher复杂度

给定训练集： $D=\left \{ (x_1,y_1),(x_2,y_2),...,(x_m,y_m) \right \}$

则假设 $h$ 的经验误差为（预测错误）：

$\left\{\begin{matrix} y_ih(x_i) = (-1*1)or(1*-1)=-1 ,h(x_i)\neq y_i\\ y_ih(x_i) = (1*1)or(-1*-1)=1 ,h(x_i)= y_i\end{matrix}\right.$

$\hat{E}(h)=\frac{1}{m}\sum_{i=1}^{m}\mathbb{I}(h(x_i)\neq y_i)$

$=\frac{1}{m}\sum_{i=1}^{m}\frac{1-y_ih(x_i)}{2}$

$=\frac{1}{2}-\frac{1}{2m}\sum_{i=1}^{m}y_ih(x_i)$

其中 $\frac{1}{m}\sum_{i=1}^{m}y_ih(x_i)$ 体现了预测值 $h(x_i)$ 与样例真实标记 $y_i$ 之间的一致性。

若对所有的 $i\in\left \{ 1,2,...,m \right \}$ ，都有 $h(x_i)=y_i$ ，则 $max\frac{1}{m}\sum_{i=1}^{m}y_ih(x_i)=1$ 。

经验误差最小假设函数为：

${h}'=arg \, \, \, \underset{h\in H}{max}\frac{1}{m}\sum_{i=1}^{m}y_ih(x_i)$

表示：当函数值取最大值时， $h$ 的取值。

而我们更关注模型的泛化能力：假设标签 $y_i$ 受到随机因素的影响，不再是 $x_i$ 的真实标记，则应该选择 $H$ 中事先已经考虑了随机噪声影响的假设函数。

${h}''=\underset{h\in H}{sup}\frac{1}{m}\sum_{i=1}^{m}\sigma_ih(x_i)$

$\sigma_i$ 为Rademacher随机变量：以0.5的概率取值-1,0.5的概率取值+1。

考虑 $H$ 中所有的假设，取期望可得：

$E_\sigma = \left [ \underset{h\in H}{sup}\frac{1}{m}\sum_{i=1}^{m}\sigma_ih(x_i) \right ]$

其中 $\sigma =\left \{ \sigma_1,\sigma_2,...,\sigma_m \right \}$

$E_\sigma$ 的取值范围是 $\left [ 0,1 \right ]$ ，体现了假设空间 $H$ 的表达能力：

当 $\left | H \right |=1$ 时， $H$ 中仅有一个假设，则期望值为0，因为 $\sigma$ 取值特殊。
当 $\left | H \right |=2^m$ （因为 $\sigma$ 有m个）且 $H$ 能打散 $D$ 时，对任意的 $\sigma$ 总有一个假设使得： $h(x_i)=\sigma _i(i=1,2,...,m)$ ，此时 $E_\sigma = \left [ \underset{h\in H}{sup}\frac{1}{m}\sum_{i=1}^{m}\sigma_i^2 \right ]=\left [ \underset{h\in H}{sup}\frac{1}{m}\sum_{i=1}^{m}1\right ]=\left [ \underset{h\in H}{sup}\frac{1}{m}m \right ]=1$ ，可计算出期望值为1。

Rademacher复杂度：

函数空间 $F$ 关于 $Z$ 的经验Rademacher复杂度：

$\hat{R}_z(F) = E_\sigma\left [ \underset{f\in F}{sup}\frac{1}{m}\sum_{i=1}^{m}\sigma_ih(z_i) \right ]$

其中 $F:Z\rightarrow R$ 为实值函数空间， ${Z}'=\left \{ z_1,z_2,...,z_m \right \}$ ，其中 $z_i \in {Z}'$ 。

经验Rademacher复杂度衡量了函数空间 $F$ 与随机噪声在集合 ${Z}'$ 中的相关性。

函数空间 $F$ 关于 ${Z}'$ 上分布 $D$ 的经验Rademacher复杂度：

$R_m(F)=E_{{Z}'\subseteq Z:|Z|=m}\left [ \hat{R_z}(F) \right ]$

基于Rademacher复杂度可得关于函数空间 $F$ 的泛化误差界。

回归问题：对实值函数空间 $F:Z\rightarrow \left [ 0,1 \right ]$ ，根据分布 ${D}'$ 从 $Z$ 中独立同分布采样得到示例 ${Z}' =\left \{ z_1,z_2,...,z_m \right \}$ ， $z_i\in Z$ ， $0<\sigma <1$ ，对任意 $f \in F$ ，以至少 $1-\delta$ 的概率有：

$E[f(z)]\leqslant \frac{1}{m}\sum_{i=1}^{m}f(z_i)+2R_m(F)+\sqrt{\frac{In(1/\sigma )}{2m}}$

$E[f(z)]\leqslant \frac{1}{m}\sum_{i=1}^{m}f(z_i)+2\hat{R}_Z(F)+3\sqrt{\frac{In(2/\sigma )}{2m}}$

二分类问题：对假设空间 $H:X\rightarrow \left \{ -1,+1 \right \}$ ，根据分布 $D$ 从 $X$ 中独立同分布采样得到实例集 $D=\left \{ x_1,x_2,...,x_m \right \},x_i\in X,0< \delta < 1$ ，对任意的 $h\in H$ ，以至少 $1-\delta$ 的概率有：

$E(h)\leqslant \hat{E}(h)+R_m(H)+\sqrt{\frac{ln(1/\delta )}{2m}}$

$E(h)\leqslant \hat{E}(h)+\hat R_D(H)+3\sqrt{\frac{ln(2/\delta )}{2m}}$

McDiarmid不等式

存在： $f:R^n\rightarrow n,x\in \left \{ x_1,x_2,...,x_n \right \}$

若 $f$ 满足： $|f(x_1,...,x_i,...,x_n)-f(x_1,...,{x}'_i,...,x_n)| \leqslant c_i$

则下面不等式成立：

$P_r(f(x_1,x_2,...,x_n)-E[f(x_1,x_2,...,x_n)]\geqslant t)\leqslant exp(-\frac{2t^2}{\sum_{i=1}^{n}c^2_i})$

5，证明：公式一

$E[f(z)]\leqslant \frac{1}{m}f(z_i)+2R_m(F)+\sqrt{\frac{In(1/\sigma )}{2m}}$

证明：

令 $\varphi (z) = E[f(z)]-\frac{1}{m}\sum_{i=1}^{m}f(z_i)$

$P_r(\varphi(z)-E_z(\varphi(z))\geqslant t)\leqslant exp(-\frac{2t^2}{\sum_{i=1}^{m}c^2_i})$ （不等式1）

求 $c_i$ ，因为 $f$ 满足： $|f(x_1,...,x_i,...,x_n)-f(x_1,...,{x}'_i,...,x_n)| \leqslant c_i$ （不等式2）

将 $\varphi (z)$ 做同样变换，故：

$|\varphi (z)-\varphi ({z}')|=|E[f(z)]-\frac{1}{m}(f(z_1)+f(z_2)+...+f(z_i)+...+f(z_m))-E_{z'}[f(z)]+\frac{1}{m}(f(z_1)+f(z_2)+...+f(z'_i)+...+f(z_m))|$

因为 $E[f(z)]$ 和 $E_{z'}[f(z)]$ 均表示整个样本集的期望，于是

$|\varphi (z)-\varphi ({z}')|=|-\frac{1}{m}(f(z_1)+f(z_2)+...+f(z_i)+...+f(z_m))+\frac{1}{m}(f(z_1)+f(z_2)+...+f(z'_i)+...+f(z_m))|$

$=\frac{1}{m}|f(z_i)-f(z'_i)|$ 由于 $f(x)=\left \{ 0,1 \right \}$

$\leqslant \frac{1}{m}$

结合（不等式2）此时， $c_i = \frac{1}{m}$ ，带入（不等式1）得

$\Sigma_{i=1}^mc_i^2=\Sigma_{i=1}^m\left ( \frac{1}{m} \right )^2=m*\frac{1}{m^2}=\frac{1}{m}$

进而：

$P_r(\varphi(z)-E_z(\varphi(z))\geqslant t)\leqslant exp(-2mt^2)$ （1）

令 $\delta =exp(-2mt^2)$

$ln\frac{1}{\delta } =2mt^2$

$t=\sqrt{\frac{ln\frac{1}{\delta }}{2m}}$

将 $t=\sqrt{\frac{ln\frac{1}{\delta }}{2m}}$ 反带入（1）得：

$P_r(\varphi(z)-E_z(\varphi(z))\geqslant \sqrt{\frac{ln\frac{1}{\delta }}{2m}})\leqslant \delta$

该概率类似正态分布，可推出：

$P_r(\varphi(z)\leqslant E_z(\varphi(z))+\sqrt{\frac{ln\frac{1}{\delta }}{2m}})\geqslant 1-\delta$ (2)

因为： $\varphi (z) = E[f(z)]-\frac{1}{m}\sum_{i=1}^{m}f(z_i)$

因为： $E[f(z)]-\frac{1}{m}\sum_{i=1}^{m}f(z_i) \leqslant \underset{f\in F}{sup}( E[f(z)]-\frac{1}{m}\sum_{i=1}^{m}f(z_i) )$

$E[f(z)] \leqslant \frac{1}{m}\sum_{i=1}^{m}f(z_i)+\underset{f\in F}{sup}( E[f(z)]-\frac{1}{m}\sum_{i=1}^{m}f(z_i) )$

$\leqslant \frac{1}{m}\sum_{i=1}^{m}f(z_i)+\underset{f\in F}{sup}(\varphi (z))$

由(2)可推出：

$E[f(z)] \leqslant \frac{1}{m}\sum_{i=1}^{m}f(z_i)+E_z(\varphi(z))+\sqrt{\frac{ln\frac{1}{\delta }}{2m}}$ ，概率至少为 $1-\delta$

现在唯一需要确定的是 $E_z(\varphi(z))$

$E_z(\varphi(z)) = E_{z}[\underset{f\in F}{sup}(E_{z}[f(z)]-\frac{1}{m}\sum_{i=1}^{m}f(z_i))]$

因为 $E[f(z)]$ 和 $E_{z'}[f(z)]$ 均表示整个测试集的期望，有：

$E_z(\varphi(z)) = E_{z}[\underset{f\in F}{sup}(E_{z'}[f(z')]-\frac{1}{m}\sum_{i=1}^{m}f(z_i))]$

由于 ${z}'$ 中的点是独立同分布的，所有的 $E_{z'}[f(z')]=E_{z'}[E_{z'}[f(z')]]$ 成立，故：

$= E_{z}(\underset{f\in F}{sup}(E_{z'}[E_{z'}[f(z')]]-\frac{1}{m}\sum_{i=1}^{m}f(z_i)))$

其中 $\frac{1}{m}\sum_{i=1}^{m}f(z_i)$ 与 $z'$ 期望无关，故：

$= E_{z}(\underset{f\in F}{sup}(E_{z'}[E_{z'}[f(z')]-\frac{1}{m}\sum_{i=1}^{m}f(z_i)]))$

由Jensen不等式和上确界函数的凸性，故：

$\leqslant E_{z,z'}(\underset{f\in F}{sup}(E_{z'}[f(z'_i)]-\frac{1}{m}\sum_{i=1}^{m}f(z_i)))$

$= E_{z,z'}(\underset{f\in F}{sup}(\frac{1}{m}\sum_{i=1}^{m}f(z'_i)-\frac{1}{m}\sum_{i=1}^{m}f(z_i)))$

$= E_{z,z'}(\underset{f\in F}{sup}(\frac{1}{m}\sum_{i=1}^{n}(f(z'_i)-f(z_i))))$

引入Rademacher变量 $\sigma$ ，不影响结果。

$= E_{z,z',\sigma }(\underset{f\in F}{sup}(\frac{1}{m}\sum_{i=1}^{m}\sigma_i(f(z'_i)-f(z_i))))$

$\leqslant E_{z',\sigma }(\underset{f\in F}{sup}(\frac{1}{m}\sum_{i=1}^{m}\sigma_if(z'_i)))+E_{z,\sigma }(\underset{f\in F}{sup}(\frac{1}{m}\sum_{i=1}^{m}-\sigma_if(z_i)))$

$=2*E_{{z}',\sigma }(\underset{f\in F}{sup}(\frac{1}{m}\sum_{i=1}^{m}\sigma_if(z'_i)))$

$=2R_m(F)$

故：

$E[f(z)] \leqslant \frac{1}{m}\sum_{i=1}^{m}f(z_i)+E_z(\varphi(z))+\sqrt{\frac{ln1/\delta }{2m}}$ ，概率至少为 $1-\delta$

$E[f(z)]\leqslant \frac{1}{m}\sum_{i=1}^{m}f(z_i)+2R_m(F)+\sqrt{\frac{In(1/\sigma )}{2m}}$ ，概率至少为 $1-\delta$

6，证明：公式二

$E[f(z)]\leqslant \frac{1}{m}\sum_{i=1}^{m}f(z_i)+2\hat{R}_Z(F)+3\sqrt{\frac{In\frac{2 }{\delta})}{2m}}$

同理，令 $\delta '=\frac{\delta }{2}$ ，对于任意的 $\delta >0$ ，下面不等式至少 $1-\frac{\delta }{2}$ 的概率成立。

$\varphi (z)\leqslant E_z[\varphi (z)]+\sqrt{\frac{ln\frac{2 }{\delta}}{2m}}$

再次使用 McDiarmid 不等式，下式至少有 $1-\frac{\delta }{2}$ 的概率成立：

$\hat{R}_z(F)-R_m(F)\leqslant \sqrt{\frac{ln\frac{2 }{\delta}}{2m}}$

$\hat{R}_z(F)-R_m(F)\geqslant -\sqrt{\frac{ln\frac{2 }{\delta}}{2m}}$

$R_m(F)\leqslant \hat{R}_z(F)+\sqrt{\frac{ln\frac{2 }{\delta}}{2m}}$

$\varphi (z)\leqslant 2 R_m(F)+\sqrt{\frac{ln\frac{2 }{\delta}}{2m}}$

$\varphi (z)\leqslant 2 \hat R_z(F)+3\sqrt{\frac{ln\frac{2 }{\delta}}{2m}}$ ，概率至少为 $1-\delta'$

$E[f(z)]\leqslant \frac{1}{m}\sum_{i=1}^{m}f(z_i)+2\hat{R}_Z(F)+3\sqrt{\frac{In\frac{2 }{\delta }}{2m}}$ ，概率至少为 $1-\delta'$

7，证明：公式四

$E(h)\leqslant \hat{E}(h)+\hat R_D(H)+3\sqrt{\frac{ln(2/\delta )}{2m}}$

$\hat{R}_z(F) = E_\sigma\left [ \underset{f\in F}{sup}\frac{1}{m}\sum_{i=1}^{m}\sigma_ih(z_i) \right ]$

$\hat{R}_z(F) = E_\sigma\left [ \underset{f\in F}{sup}\frac{1}{m}\sum_{i=1}^{m}\sigma_i\frac{1-y_ih(z_i)}{2} \right ]$

$=\frac{1}{2} E_\sigma\left [ \underset{f\in F}{sup}\frac{1}{m}\sum_{i=1}^{m}\sigma_i\ \right ]-\frac{1}{2} E_\sigma\left [ \underset{f\in F}{sup}\frac{1}{m}\sum_{i=1}^{m}\sigma_iy_ih(z_i) \right ]$

由于 $\sigma$ 部分数学期望为0

$=-\frac{1}{2} E_\sigma\left [ \underset{f\in F}{sup}\frac{1}{m}\sum_{i=1}^{m}\sigma_iy_ih(z_i) \right ]$

$\sigma$ 下不影响正负

$=\frac{1}{2} E_\sigma\left [ \underset{f\in F}{sup}\frac{1}{m}\sum_{i=1}^{m}\sigma_iy_ih(z_i) \right ]$

$=\frac{1}{2}\hat R_D(H)$

$E[f(z)]\leqslant \frac{1}{m}\sum_{i=1}^{m}f(z_i)+2\hat{R}_Z(F)+3\sqrt{\frac{In\frac{2 }{\delta}}{2m}}$

$E(h)\leqslant \hat{E}(h)+\hat R_D(H)+3\sqrt{\frac{ln\frac{2 }{\delta}}{2m}}$

8，证明：公式三

$E(h)\leqslant \hat{E}(h)+R_m(H)+\sqrt{\frac{ln(1/\delta )}{2m}}$

根据公式四和 $R_m(F)$ 与 $\hat{R}_z(F)$ 之间关系，可得：

$R_m(F)=E_{z'}[\hat R_z(F)]=\frac{1}{2}E_{z'}[\hat R_D(H)]=\frac{1}{2}R_m(H)$

$E[f(z)]\leqslant \frac{1}{m}\sum_{i=1}^{m}f(z_i)+2R_m(F)+\sqrt{\frac{In(1/\sigma )}{2m}}$

$E(h)\leqslant \hat{E}(h)+R_m(H)+\sqrt{\frac{ln(1/\delta )}{2m}}$