泛化误差上界

References

统计学习方法（第2版）李航著 p25~27

定理

对于二分类问题，当假设空间是有限个函数的集合$F=\{f_1,f_2,...,f_d\}$F={f1​,f2​,...,fd​}时，对任意一个函数$f\in F$f∈F，至少以概率$1-\delta$1−δ，$0<\delta<1$0<δ<1，以下不等式成立：$R(f)\leq \hat{R}(f)+\varepsilon(d,N,\delta)$R(f)≤R^(f)+ε(d,N,δ)其中，$\varepsilon(d,N,\delta)=\sqrt{\frac{1}{2N}(\log{d}+\log{\frac{1}{\delta}})}$ε(d,N,δ)=2N1​(logd+logδ1​)​

前置知识

关于$f$f的期望风险：$R(f)=E[L(Y,f(X))]$R(f)=E[L(Y,f(X))]经验风险：$\hat{R}(f)=\frac{1}{N}\sum_{i=1}^NL(y_i,f(x_i))$R^(f)=N1​i=1∑N​L(yi​,f(xi​))其中，$L$L是损失函数。

个人理解

首先，看定理的名字“泛化误差上界”。泛化误差指的是模型$f$f对未知数据预测的误差，大白话来说就是测试集上的cost。事实上，泛化误差就是期望风险$R(f)$R(f)。泛化误差反应了模型的真实性能。用一句话解释泛化误差上界，“模型实际表现最烂能烂到什么程度”。这个解释还不够严谨，继续补充。
接下来，看定理内容。注意到以下几点

1. 定理的适用范围是二分类问题。这使得$L$L为0-1损失函数，$L$L的取值$\in\{0,1\}$∈{0,1}。
2. 集合$F$F为模型的假设空间，包含了有限个备选函数。具体的个数为$d$d。这句话可以在推导过程中有更深刻的体会。
3. $1-\delta$1−δ的通俗含义。 对于集合$F$F中任意的函数$f$f，至少以$1-\delta$1−δ的置信度使不等式成立。$1-\delta$1−δ代表了这个上界的可信程度。
4. 不等式含义。期望风险也就是泛化误差$R(f)$R(f)，小于等于经验风险$\hat{R}(f)$R^(f)加某个数$\varepsilon$ε。经验风险$\hat{R}(f)$R^(f)就是模型$f$f在训练集上的表现。假设我们训练好了一个模型$f$f，那么$\hat{R}(f)$R^(f)就是已知量了。对不等式移项得$R(f)-\hat{R}(f)\leq\varepsilon$R(f)−R^(f)≤ε。根据直觉也能知道，期望风险肯定是比经验风险大的，大多少呢？可以看到，这个差距不超过$\varepsilon$ε。
5. $\varepsilon$ε与$R(f)$R(f)上界的关系。$\varepsilon$ε是推导过程中产生的，仅为了美观。真正影响$R(f)$R(f)上界的是$N,d,1-\delta$N,d,1−δ这三个参数。（1）$N$N是训练样本数，$N$N增大，$\varepsilon$ε减小，$R(f)$R(f)上界也减小，$R(f)$R(f)上界越接近$\hat{R}(f)$R^(f)。对应的解释是样本大，训练就充分，当N取极限趋于无穷时，期望风险就趋于经验风险。（2）$d$d表示假设空间中备选函数的个数，$d$d增大，$\varepsilon$ε增大，$R(f)$R(f)上界也随之增大。这里可以理解为，可选的函数越多，模型就会变得复杂，训练更加困难，有点奥卡姆剃刀的意思。（3）置信度$1-\delta$1−δ增大，$\delta$δ减小，相应$R(f)$R(f)上界也增大。这是显然的，想要增加可信度，相应的也要放宽条件。

至此，我们已经可以用一句话总结定理了。“在有限个备选函数的模型假设空间里，通过训练集训练出来的模型，有一定概率在测试集中的表现是靠谱的”。我认为这个定理证明了机器学习的可行性和有效性。

公式推导

• 首先介绍Hoeffding不等式。

设$X_1,X_2,...,X_N$X1​,X2​,...,XN​是独立随机变量，且$X_i\in[a_i,b_i],i=1,2,...,N$Xi​∈[ai​,bi​],i=1,2,...,N；$\bar{X}$Xˉ是$X_1,X_2,...,X_N$X1​,X2​,...,XN​的经验均值，即$\bar{X}=\frac{1}{N}\sum_{i=1}^NX_i$Xˉ=N1​∑i=1N​Xi​，则对任意$t>0$t>0，以下不等式成立：$P[\bar{X}-E(\bar{X})\geq t]\leq \exp\left({-\frac{2N^2t^2}{\sum_{i=1}^N(b_i-a_i)^2}}\right)$P[Xˉ−E(Xˉ)≥t]≤exp(−∑i=1N​(bi​−ai​)22N2t2​)$P[E(\bar{X})-\bar{X}\geq t]\leq \exp\left({-\frac{2N^2t^2}{\sum_{i=1}^N(b_i-a_i)^2}}\right)$P[E(Xˉ)−Xˉ≥t]≤exp(−∑i=1N​(bi​−ai​)22N2t2​)

• 将Hoeffding不等式中的$X$X替换为$L$L，其中$L_i=L(y_i,f(x_i))$Li​=L(yi​,f(xi​))，$L_i\in [a_i,b_i],a_i=0,b_i=1$Li​∈[ai​,bi​],ai​=0,bi​=1；把$t$t替换为$\varepsilon$ε。对任意函数$f\in F$f∈F，可得$\bar{L}=\hat{R}(f)$Lˉ=R^(f)，$E(\bar{L})=R(f)$E(Lˉ)=R(f)。整理的式子如下：$P(R(f)-\hat{R}(f)\geq\varepsilon)\leq\exp(-2N\varepsilon^2)$P(R(f)−R^(f)≥ε)≤exp(−2Nε2)
• 因为$F$F是有限集合，故
  $\begin{aligned} P(\exist f\in F:R(f)-\hat{R}(f)\geq\varepsilon)&=P(\bigcup_{f\in F}\{R(f)-\hat{R}(f)\geq\varepsilon\})\\&\leq\sum_{f\in F}P(R(f)-\hat{R}(f)\geq\varepsilon)\\&\leq d\exp(-2N\varepsilon^2) \end{aligned}$P(∃f∈F:R(f)−R^(f)≥ε)​=P(f∈F⋃​{R(f)−R^(f)≥ε})≤f∈F∑​P(R(f)−R^(f)≥ε)≤dexp(−2Nε2)​
• 令$d\exp(-2N\varepsilon^2)=\delta$dexp(−2Nε2)=δ，易得$P(R(f)< \hat{R}(f)+\varepsilon)\geq1-\delta$P(R(f)<R^(f)+ε)≥1−δ。$\delta$δ表示：在集合$F$F中，存在$f$f使得期望风险与经验风险的差值大于$\varepsilon$ε的概率。

证毕。

• 点赞
• 收藏
• 分享
• • 文章举报

DamianGao 发布了37 篇原创文章 · 获赞 21 · 访问量 4万+ 私信 关注