模型泛化能力(泛化误差+泛化误差上界)| 15mins 入门 | 《统计学习方法》学习笔记（六）

泛化能力

一、 泛化误差

学习方法的泛化能力（generalization ability）：方法学习到的模型对未知数据的预测能力。

评价标准：测试误差。

但因为测试数据集是有限的，很有可能由此得到的评价结果是不可靠的。统计学习理论试图从理论上对学习方法的泛化能力进行分析。

• 泛化误差定义：如果学习到的模型是$\hat{f}$，那么用这个模型对未知数据预测的误差即为泛化误差（generalization error）
  $$R_{exp}(\hat{f})=E_p[L(Y,\hat{f}(X))]={\int }_{\chi \times \gamma }L(y,\hat{f}(x))p(x,y)dxdy$$
  实际上，泛化误差就是学习到的模型的期望风险

• 意义：反映了学习方法的泛化能力，越小，则泛化能力越好

二、 泛化误差上界

泛化误差上界（generalization error bound）：泛化误差的概率上界。

• 通过比较两种学习方法的泛化误差上界的大小来比较它们的优势。

• 性质：

  1. 是样本容量的函数，当样本容量增加时，泛化上界趋于0
  2. 是假设空间容量的函数，假设空间容量越大，模型就越难学，泛化误差上界就越大。

• 二分类问题的泛化误差上界：

  已知训练数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\} T={ (x1?,y1?),(x2?,y2?),...,(xN?,yN?)}，它是联合概率分布$P(X,Y)$独立同分布产生的， X ∈ R n , Y ∈ { ? 1 , + 1 } X\in R^n, Y\in \{-1,+1\} X∈Rn,Y∈{ ?1,+1}. 假设空间是函数的有限集合 F = { f 1 , f 2 , . . . , f d } F=\{f_1,f_2,...,f_d\} F={ f1?,f2?,...,fd?}，d是函数个数。设f是从F中选取的函数。损失函数是0-1损失，关于f的期望风险和经验风险分别是：
  $$\begin{gathered} R(f)=E[L(Y,f(X))] \\ \hat{R}(f)=\frac{1}{N}\sum _{i=1}^{N}L(y_i,f(x_i)) \end{gathered}$$
  经验风险最小化函数是：
  $$f_N=argmi{n}_{f\in F}\hat{R}(f)$$
  $f_N$的泛化能力：
  $$R(f_N)=E[L,f_N(X)]$$
  **定理(泛化误差上界)：**对二类分类问题，当假设空间是有限个函数的集合 F = { f 1 , f 2 , . . . f d } F=\{f_1,f_2,...f_d\} F={ f1?,f2?,...fd?}时，对任意一个函数$f\in F$，至少以概率$1?\delta$，以下不等式成立：
  $$R(f)\le \hat{R}(f)+?(d,N,\delta )\text{\hspace{1em}(1)}$$
  其中
  $$?(d,N,\delta )=\sqrt{\frac{1}{2N}(logd+log\frac{1}{\delta })}$$
  不等式（1）左端$R(f)$是泛化误差，右端即为泛化误差上界。在泛化误差上界中，第1项是训练误差，训练误差越小，泛化误差越小。第2项$?(d,N,\delta )$是N的单调递减函数，当$N$趋于无穷时，它趋于0；同时它也是$\sqrt{logd}$阶的函数，假设空间$F$包含的函数越多，其值越大。

  **证明：**在证明中要用到$Hoeffding$不等式，先叙述如下

  设$S_n={\sum }_{i=1}^n{X}_i$是独立随机变量$X_1,X_2,...,X_n$之和，$X_i\in [a_i,b_i]$，则对任意$t>0$，以下不等式成立：
  $$P(S_n?E{S}_n\ge t)\le exp(\frac{?2t^2}{{\sum }_{i=1}^n(b_i?a_i{)}^2})\text{\hspace{1em}(2)}$$

  $$P(E{S}_n?S_n\ge t)\le exp(\frac{?2t^2}{{\sum }_{i=1}^n(b_i?a_i{)}^2})\text{\hspace{1em}(3)}$$

  对任意函数$f\in F$，$\hat{R}(f)$是N个独立的随机变量$L(Y,f(X))$的样本均值，$R(f)$是随机变量$L(Y,f(X))$的期望值。如果损失函数取值于区间$[0,1]$，即对所有i，$[a_i,b_i]=[0,1]$，那么由$Hoeffding$不等式(3)不难得知，对$?>0$，以下不等式成立：
  $$P(R(f)?\hat{R}(f)\ge ?)\le exp(?2N{?}^2)$$
  由于 F = { f 1 , f 2 , . . . , f d } F=\{f_1,f_2,...,f_d\} F={ f1?,f2?,...,fd?}是一个有限集合，故
  P ( ? f ∈ F : R ( f ) ? R ^ ( f ) ≥ ? ) = P ( ? f ∈ F { R ( f ) ? R ^ ( f ) ≥ ? } ) ≤ ∑ f ∈ F P ( R ( f ) ? R ^ ( f ) ≥ ? ) ≤ d e x p ( ? 2 N ? 2 ) P(\exists f\in F:R(f)-\hat R(f)\geq \epsilon)=P(\bigcup_{f\in F}\{R(f)-\hat R(f) \geq \epsilon\}) \\ \leq \sum_{f\in F}P(R(f)-\hat R(f)\geq \epsilon) \\ \leq d \space exp(-2N\epsilon^2) P(?f∈F:R(f)?R^(f)≥?)=P(f∈F??{ R(f)?R^(f)≥?})≤f∈F∑?P(R(f)?R^(f)≥?)≤d exp(?2N?2)
  或者等价的，对任意的$f\in F$，有
  $$P(R(f)?\hat{R}(f)<?)\ge 1?dexp(?2N{?}^2)$$
  令
  $$\delta =dexp(?2N{?}^2)\text{\hspace{1em}(4)}$$
  则
  $$P(R(f)<\hat{R}(f)+?)\ge 1?\delta$$
  则至少以概率$1?\delta$有$R(f)<\hat{R}(f)+?$<其中$?$由(4)得到，即为$?(d,N,\delta )$

  从泛化误差上界可知，
  $$R(f_N)\le \hat{R}(f_N)+?(d,N,\delta )$$
  其中$?(d,N,\delta )$和$f_N$在上面表示。因此，训练误差小的模型，其泛化误差也会小。

  以上的讨论的只是假设空间包含有限个函数情况下的泛化误差上界，对一般的假设空间要找到的泛化误差界就没这么简单。