• 1.VC维的可学习性分析结果具有一定的普适性（对任何数据分布都成立）
• 2.由于它的普适性，所以没有考虑数据自身，所以基于VC维得到的泛化误差通常比较松
• 3.Rademacher复杂度在一定程度上考虑上了数据自身的分布

给定训练集，假设的经验误差为

解析：这里解释了从第一步到第二部的推导，因为前提假设是2分类问题，，因此。这是因为假如或，由；反之，假如或，有。

其中体现了预测值与样例真实标记之间的一致性，若对于所有都有，则取最大值1，也就是说，经验误差最小的假设是

解析：由公式12.36可知，经验误差和呈反比的关系，因此假设空间中能使经验误差最小的假设即是使最大的。

现实任务中的样例有时会收到噪声的影响，这个时候在假设空间在训练集上表现最好的假设，不如选择中事先考虑了随机噪声影响的假设。
考虑随机变量，它以0.5的概率取值-1，0.5的概率取值+1，称为Rademacher随机变量。基于，可将式子（12.37）重写为

解析：上确界这个概念已经解释过，见式子12.7的解析。由于是随机变量，因此这个式子可以理解为求解随机生成的标签（即）最契合的假设（当和）完全一致时，它们的内积最大。

是无限假设空间，有可能取不到最大值，因此使用上确值代替最大值。考虑中的所有假设，对式子（12.38）取期望可得

解析：这个式子可以用来衡量假设空间的表达能力，对变量求期望可以理解为当变量包含所有可能的结果时，假设空间中最契合的假设和变量的平均契合程度。因为前提假设是2分类的问题，因此一共有种，这些不同的构成了数据集的对分（12.4节），如果一个假设空间的表达能力越强，那么就越有可能对于每一种，假设空间中都存在一个使得和非常接近甚至相同，对所有可能的取期望即可衡量假设空间的整体表达能力，这就是这个式子的含义。

其中。式子（12.39）的取值范围是，它体现了假设空间的表达能力，例如。当时，中仅有一个假设，这时可计算出式子（12.39）的值为0；当且能打散时，对任意总有一个假设使得，这时可计算出式子（12.39）的值为1.
考虑实值函数空间。令，其中，将式子（12.39）中的和替换为和可得

定义12.8

函数空间关于的经验Rademacher复杂度

解析：对比式子（12.39），这里使用函数空间代替了假设空间，函数代替了假设，很容易理解，因为假设即可看作是作用在上的一个映射,通过这个映射可以得到标签.注意前提假设实值函数空间,即映射将样本隐射到了实数空间,这个时候所有的将是一个标量即.

经验Rademacher复杂度衡量了函数空间与随机噪声在集合中的相关性。通常我们希望了解函数空间在上关于分布的相关性，因此，对所有从独立同分布采样而得的大小为的集合求期望可得。

定义12.9

函数空间关于上分布的Rademacher复杂度

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

解析:这里所要求的是关于分布的Rademacher复杂度,因此从中采出不同的样本,计算这些样本对应的Rademacher复杂度的期望.

定理12.5

对实值函数空间,根据分布从中独立同分布采样得到示例集,对任意,以至少的概率有

解析:首先令记号 即表示函数作为假设下的经验误差,表示经验误差和泛化误差的上确界.再令为只与有一个示例(样本)不同的训练集,不妨设和为不同的示例,那么有 第一个不等式是因为上确界的差不大于差的上确界,第四行的等号由于与只有不相同,最后一行的不等式是因为前提假设:,即.同理 综上二式有: 将看作函数(注意这里的不是定义里的),那么可以套用McDiarmid不等式的结论式12.7 令可以求得,所以 由逆事件的概率定义得 即书中式子12.44的结论,下面来估计的上界: 第二行等式是外面套了一个对服从分布的示例集求期望,因为,而采样出来的和相互独立,因此有.第三行不等式基于上确界函数是个凸函数,将看作是凸函数,将看作变量,根据Jensen不等式(式子12.4),有 其中是的简写形式.第五行引入对Rademacher随机变量的期望,由于函数值空间是标量,因为也是标量,即,且总以相同概率可以取到这两个值,因此可以引入而不影响最终结果.第六行利用了上确界的和不小于和的上确界,因为第一项中只含有变量,所以可将去掉,因为第二项中只含有变量,所以可以将去掉.第七行利用是对称的,所以的分布和完全一致,所以可以将第二项中的负号去除,又因为和均是从中采样得到的数据,因此可以将第一项中的替换成,将替换成,最终根据定义式12.41可得,式子12.24得证.

证明,令

同时,令为只与有一个示例不同的训练集,不妨设和为不同示例,可得

同理可得

根据McDiarmid不等式(12.7)可知,对任意

以至少的概率成立,下面来估计的上界:

至此,式子(12.42)得证,由定义12.9可知,改变中的一个示例对的值所造成的改变最多为,由McDiarmid不等式(12.7)可知

以至少的概率成立,再由式子(12.44)可知,

以至少的概率成立,于是

以至少的概率成立,至此,式子(12.43)得证.
需注意的是,定理12.5中的函数空间是区间上的实值函数,因此定理12.5只适用于回归问题,对二分类问题,我们有下面的定理:

定理12.6

对假设空间,根据分布从中独立同分布采样得到示例集,对任意,以至少的概率有


证明 对二分类问题的假设空间,令,则中的假设变形为

于是就可将值域为的假设空间转化为值域为的函数空间.由定义12.8,有

对式(12.50)求期望后可得

由定理12.5和式子(12.50)~(12.51),定理12.6得证
定理12.6给出了基于Rademacher复杂度的泛化误差界.与定理12.3对比可知,基于VC维的泛化误差界是分布无关,数据独立的,而基于Rademacher复杂度的泛化误差界(12.47)与分布有关,式子(12.48)与数据有关,换言之,有点类似于为该学习问题”量身定制”的,因此它通常比基于VC维的泛化误差界更紧一些.
值得一提的是,关于Rademacher复杂度与增长函数,有如下定理:

定理12.7

假设空间的Rademacher复杂度与增长函数满足

证明:比较繁琐,同书上所示,参见Foundations of Machine Learning

由式子(12.47),(12.52)和推论12.2可得

解析:根据式12.28有,根据式子12.52有,因此,再根据式子12.47即证.

也就是说,我们从Rademacher复杂度和增长函数能推导出基于VC维的泛化误差界.