【注】学习笔记参考自《统计学习方法第二版》——李航。

1. 简介

学习方法的泛化能力是指由该方法学习到的模型对未知数据的预测能力，是学习方法本质上重要的性质。现实中采用最多的办法是通过测试误差来评价学习方法的泛化能力，但这种评价是依赖于测试数据集的。因为测试数据集是有限的，很有可能由此得到的评价结果是不可靠的。

2. 泛化误差

假设学习到的模型为 $\hat{f}$，那么用这个模型对未知数据预测的误差即为泛化误差：

$$\begin{array}{c} R_{exp}(\hat{f}) = E_P [L(Y,\hat{f}(X))] = \int_{\mathcal{X} \times \mathcal{Y}} L(y,\hat{f}(x)) P(x,y) \mathrm{d}x \mathrm{d}y \end{array}$$

泛化误差反映了学习方法的泛化能力。事实上，泛化误差就是所学习到的模型的期望风险。

3. 泛化误差上界

学习方法的泛化能力分析往往是通过研究泛化误差的概率上界进行的，简称为泛化误差上界，即通过比较两种学习方法的泛化误差上界的大小来比较它们的优势。

3.1 性质

泛化误差上界通常具有以下性质：

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

3.2 举例

考虑二分类问题。已知训练数据集 $T = \{ (x_1,y_1), (x_2,y_2), \cdots, (x_N,y_N) \}$，$N$ 是样本容量，$T$ 是从联合概率分布 $P(X,Y)$ 独立同分布产生的，$X \in \boldsymbol{R}^n$，$Y \in \{-1,+1\}$。假设空间是函数的有限集合 $\mathcal{F} = \{f_1, f_2, \cdots, f_d \}$，$d$ 是函数个数。设 $f$ 是从 $\mathcal{F}$ 中选取的函数。损失函数是 $0$—$1$ 损失。关于 $f$ 的期望风险和经验风险分别是

$$\begin{array}{c} R(f) = E(L(\boldsymbol{Y},f(\boldsymbol{X}))) \\ \hat{R}(f) = \frac{1}{N} \sum_{i=1}^N L(y_i,f(x_i)) \end{array}$$

泛化误差上界定理

对于二分类问题，当假设空间是有限个函数的集合 $\mathcal{F} = \{ f_1, f_2, \cdots, f_d \}$ 时，对任意一个函数 $f \in \mathcal{F}$，至少以概率 $1-\delta$（$0 \lt \delta \lt 1$），以下不等式成立

$$\begin{array}{c} R(f) \leq \hat{R}(f) + \varepsilon(d,N,\delta) \end{array}$$

其中

$$\begin{array}{c} \varepsilon(d,N,\delta) = \sqrt{\frac{1}{2N} (\log{d} + \log{\frac{1}{\delta}})} \end{array}$$

$R(f)$ 为泛化误差，$\hat{R}(f) + \varepsilon(d,N,\delta)$ 为泛化误差上界。$\hat{R}(f)$ 为训练误差，$\varepsilon(d,N,\delta)$ 是 $N$ 的单调递减函数，当 $N$ 趋于无穷时趋于 $0$，同时它也是 $\sqrt{\log{d}}$ 阶的函数，假设空间 $\mathcal{F}$ 包含的函数越多，其值越大。

证明

由于损失函数是 $0$—$1$ 损失，因此损失函数值在区间 $[0,1]$ 范围内。由霍夫丁不等式可知，对 $\varepsilon \gt 0$，以下不等式成立

$$\begin{array}{c} P(R(f) - \hat{R}(f) \geq \varepsilon) \leq \exp{(-2N\varepsilon^2)} \end{array}$$

由于 $\mathcal{F} = \{ f_1,f_2,\cdots,f_d \}$ 是一个有限集合，故

$$\begin{array}{rl} P(\exists f \in \mathcal{F}: R(f) - \hat{R}(f) \geq \varepsilon) & = P(\cup_{f \in \mathcal{F}} \{ R(f) - \hat{R}(f) \geq \varepsilon \}) \\ & \leq \sum_{f \in \mathcal{F}} P(R(f) - \hat{R}(f) \geq \varepsilon) \\ & \leq d \exp{(-2N \varepsilon^2)} \end{array}$$

因此，对于任意 $f \in \mathcal{F}$，有

$$\begin{array}{c} P(R(f) - \hat{R}(f) \lt \varepsilon) \geq 1 - d \exp{(-2N \varepsilon^2)} \end{array}$$

令 $\varepsilon = d\exp{(-2N \varepsilon^2)}$，则有

$$\begin{array}{c} \varepsilon = \sqrt{\frac{1}{2N}(\log{d} + \log{\frac{1}{\delta}})} \\ P(R(f) \lt \hat{R}(f) + \varepsilon) \geq 1 - \delta \end{array}$$

即至少以概率 $1 - \delta$ 有不等式 $R(f) \lt \hat{R}(f) + \varepsilon(d,N,\delta)$ 成立。

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