Hoeffding不等式的认识以及泛化误差上界的证明

在机器学习中我们知道学习方法的泛化能力往往是通过研究泛化误差的概率上界所进行的，这个就简称为泛化误差上界。用直观的理解，在有限的训练数据中得到一个规律，认为总体也是近似这个规律的，那么就能用这个规律进行预测。比如一个大罐子里装满了红球和白球，各一半，我随手抓了一把，然后根据这些红球白球的比例预测整个罐子也是这样的比例，这样做不一定很准确，但结果总是近似的，而且如果抓出的球越多，预测结果也就越可信。具体来说就是通过比较两种学习方法的误差上界来比较他们的优劣。

1：二分类问题的泛化误差上界
考虑到二分类问题。现在假设给定一组训练数据集合T。这组数据集时从联合概率分布P(x，y)独立同时分布产生的。现在假设这个小空间是一个函数的有限集F={f1,f2,…,fd}，d是函数个数。设f是从F中选取的函数。现在的损失函数我们定义为0-1损失。

这样关于f的期望损失和经验损失分别是：

对于f（n）的泛化能力：

现在对F中有限集合中任意选出函数f的泛化误差上界：
泛化误差上界定理：假设当前空间是有限个函数的集合，对任意一个函数f∈F，至少以概率1−σ，以下的不等式成立：

不等式左端R(f)是泛化误差，右端为泛化误差上界。泛化误差上界中，第一项是训练误差，训练误差越小，泛化误差也越小。第二项ε(d,N,δ)，N越大，值越小，假设空间F包含的函数越多，值越大。这个定理可以从概率上说明使用经验风险近似期望风险的可信度，它与样本数量以及假设空间的复杂度有关。这个定理可以从概率上说明使用经验风险近似期望风险的可信度，它与样本数量以及假设空间的复杂度有关。
上述的定理可以用Hoeffding不等式来证明：
对于Hoeffding定理的一些理解：
Hoeffding不等式是关于一组随机变量均值的概率不等式。 如果X1,X2,⋯,Xn为一组独立同分布的参数为p的伯努利分布随机变量，n为随机变量的个数。定义这组随机变量的均值为：

对于任意δ>0, Hoeffding不等式可以表示为：

在《统计机器学习》中的Hoeffding的公式为如下所示，好像有很多的版本。

令X1,…,Xn为独立同分布随机变量，满足ai≤Xi≤bi。则对于任意t>0有

至于这个公式怎么推导，其实我也不会，建议大家还是不要为难自己了。哈哈

而这个公式的用途：

在统计推断中，我们可以利用样本的统计量(statistic)来推断总体的参数(parameter)，譬如使用样本均值来估计总体期望。如下图所示，我们从罐子里抽球，希望估计罐子里不同颜色球的比例。

直觉上，如果我们有更多的样本(抽出更多的球)，则样本期望ν应该越来越接近总体期望μ。事实上，这里可以用hoeffding不等式表示如下：

从hoeffding不等式可以看出，当n逐渐变大时，不等式的UpperBound越来越接近0，所以样本期望越来越接近总体期望。

回到我们的泛化误差上界的推导中：

对任意函数f∈F，R^(f) 是N个独立随机变L(Y,f(X))的样本均值（经验期望），R(f)是期望，如果损失函数取之区间为[0, 1]，则根据上述Hoeffding不等式，得到：

由于F={f1,f2,…,fd}是一个有限集合，容易得到：

令

然后就得到了：
上面的讨论只是假设空间包含有限个函数的情况下的泛化误差上界，对于一般的假设空间要找到泛化误差界应该就没这么简单了。