Chapter 4: 泛化界
1. 有限假设空间对应的泛化误差上界
1.1 问题可分
对于可分的有限假设空间 \(\mathcal{H}\)，目标概念 \(c \in \mathcal{H}\)，任何在训练集 \(D\) 上犯错的假设都不是要找的目标概念。因此可以剔除这些在训练集 \(D\) 上犯错的假设，最终剩下与 \(D\) 一致的假设，目标概念一定存在于这些一致的假设中。如果 \(D\) 足够大，则最终剩下的一致假设会很少，从而能够以较大的概率找到目标概念的近似。然而由于实际中数据集 \(D\) 通常只包含有限数量的样本，所以假设空间 \(\mathcal{H}\) 中会剩下不止一个与 \(D\) 一致的等效假设，这些等效假设无法通过数据集 \(D\) 再进行区分。一般来说，无法强求通过训练集 \(D\) 能够确保找到目标概念 \(c\)。在 PAC 学习理论中，只要训练集 \(D\) 的规模能使学习算法 \(\mathfrak{L}\) 以至少 \(1 - \delta\) 的概率找到目标概念的 \(\epsilon\) 近似即可。当 \(\mathcal{H}\) 为可分的有限假设空间时，有下面的定理成立：
定理 1.1：令 \(\mathcal{H}\) 为可分的有限假设空间，\(D\) 为从 \(\mathcal{D}\) 独立同分布采样得到的大小为 \(m\) 的训练集，学习算法 \(\mathfrak{L}\) 基于训练集 \(D\) 输出与训练集一致的假设 \(h \in \mathcal{H}\)，对于 \(0 < \epsilon,\delta < 1\)，若 \(m \geq \frac{1}{\epsilon}(\ln |\mathcal{H}| + \ln \frac{1}{\delta})\)，则有
\[P(E(h) \leq \epsilon) \geq 1 - \delta,\]
即 \(E(h) \leq \epsilon\) 以至少 \(1 - \delta\) 的概率成立。
证明
学习算法 \(\mathfrak{L}\) 输出与训练集一致的假设 \(h \in \mathcal{H}\)，该假设的泛化误差依赖于训练集 \(D\)，我们希望能够以较大的概率找到与目标概念 \(c\) 近似的假设。若 \(h\) 的泛化误差太大且与训练集一致，则这样的假设出现的概率可以表示为
\[P(\exists h \in \mathcal{H} : E(h) > \epsilon \land \widehat{E}(h) = 0).\]
下面只需证明这一概率至多为 \(\delta\) 即可。通过计算可知
\[P(\exists h \in \mathcal{H} : E(h) > \epsilon \land \widehat{E}(h) = 0) \leq \sum_{h\in\mathcal{H}} P(E(h) > \epsilon \land \widehat{E}(h) = 0)
\leq |\mathcal{H}|(1-\epsilon)^m.\]
第一个不等号是因为 \(E(h) > \epsilon\) 表明 \(h\) 犯错的概率大于 \(\epsilon\)，也就是预测正确率小于 \(1-\epsilon\)，而 \(\widehat{E}(h) = 0\) 表明 \(h\) 对 \(m\) 个独立同分布采样得到的样本被 \(h\) 均预测正确，这个事件的发生概率不大于 \((1 - \epsilon)^m\)。
因此只需要保证 \(|\mathcal{H}|(1-\epsilon)^m\) 最右端不大于 \(\delta\) 即可。由于 \((1-\epsilon)^m \leq e^{-\epsilon m}\)，若 \(m \geq \frac{1}{\epsilon}(\ln |\mathcal{H}| + \ln \frac{1}{\delta})\)，则有
\[|\mathcal{H}|(1-\epsilon)^m \leq |\mathcal{H}|e^{-\epsilon m} \leq \delta.\]
从而可知 \(P(E(h) \leq \epsilon) \geq 1 - \delta\)，即 \(P(E(h) \leq \epsilon) \geq 1 - \delta\)，定理得证。
这个定理表明，当假设空间 \(\mathcal{H}\) 是有限可分时，学习算法 \(\mathfrak{L}\) 输出假设的泛化误差依赖于假设空间的大小 \(|\mathcal{H}|\) 和训练集的大小 \(m\)，随着训练集中样本数目的逐渐增加，泛化误差的上界逐渐趋近于 0，收敛率是 \(O(1/m)\)。
1.2 问题不可分
在不可分情形时，目标概念不在假设空间中，假设空间中的每个假设都会或多或少地出现分类错误，我们不再着眼于找到目标概念的 \(\epsilon\) 近似，而是希望找到假设空间中泛化误差最小假设的 \(\epsilon\) 近似。对于学习算法输出的假设 \(h\) 来说，泛化误差是其在未见数据上的预测能力，无法直接核测得到，但其在训练集上的经验误差是可以直接观测得到的。定理 2.1 探讨了泛化误差与经验误差之间的关系，表明当训练集中样本数目 \(m\) 较大时，\(h\) 的经验误差是泛化误差的较好近似。基于这一关系，可以给出下面的定理。
定理 1.2：令 \(\mathcal{H}\) 为有限假设空间，\(D\) 为从 \(\mathcal{D}\) 独立同分布采样得到的大小为 \(m\) 的训练集，\(h \in \mathcal{H}\)，对于 \(0 < \epsilon,\delta < 1\) 有
\[P(E(h) \leq \widehat{E}(h) + \sqrt{\frac{\ln |\mathcal{H}| + \ln(2/\delta)}{2m}}) \geq 1 - \delta.\]
证明
将 \(\mathcal{H}\) 中的有限假设记为 \(h_1,h_2,\ldots,h_{|\mathcal{H}|}\)，通过计算和并集界定理可得
\[\begin{aligned}
P(\exists h \in \mathcal{H} : E(h) > \widehat{E}(h) + \epsilon)
&= P\left(\left(E(h_1) > \widehat{E}(h_1) + \epsilon\right) \vee \cdots \vee \left(E(h_{|\mathcal{H}|}) > \widehat{E}(h_{|\mathcal{H}|}) + \epsilon\right)\right) \\
&\leq \sum_{h\in\mathcal{H}} P\left(E(h) > \widehat{E}(h) + \epsilon\right).
\end{aligned}\]
基于引理 2.1，令 \(2\exp(-2m\epsilon^2) = \delta/|\mathcal{H}|\) 可得
\[\sum_{h\in\mathcal{H}} P\left(E(h) > \widehat{E}(h) + \epsilon\right) \leq \sum_{h\in\mathcal{H}} \delta/|\mathcal{H}| \leq |\mathcal{H}| \cdot \delta/|\mathcal{H}| = \delta.\]
由 \(2\exp(-2m\epsilon^2) = \delta/|\mathcal{H}|\) 可求解 \(\epsilon = \sqrt{\frac{\ln |\mathcal{H}| + \ln(2/\delta)}{2m}}\)，从而定理得证。
由于 \(\sqrt{\frac{\ln |\mathcal{H}| + \ln(2/\delta)}{2m}} = O(1/\sqrt{m})\)，所以在有限假设空间不可分情形下，泛化误差的收敛率为 \(O(1/\sqrt{m})\)。
2. 无限假设空间对应的泛化误差上界
2.1 有限 VC 维假设空间的泛化误差界
引理 4.1：对于假设空间 \(\mathcal{H}\)，\(h \in \mathcal{H}\)，\(m \in \mathbb{N}\) 和 \(0 < \epsilon < 1\)，当 \(m \geq 2/\epsilon^2\) 时有
\[P\left(|E(h) - \widehat{E}(h)| > \epsilon\right) < 4\Pi_{\mathcal{H}}(2m)\exp\left(-\frac{m\epsilon^2}{8}\right).\]
证明
考虑两个大小均为 \(m\) 且分别从 \(\mathcal{D}\) 独立同分布采样得到的训练集 \(D\) 和 \(D^{\prime}\)。首先证明
\[P\left(\sup_{h\in\mathcal{H}}|\widehat{E}_D(h) - \widehat{E}_{D^{\prime}}(h)| \geq \frac{1}{2}\epsilon\right) \geq \frac{1}{2}P\left(\sup_{h\in\mathcal{H}}|E(h) - \widehat{E}_D(h)| > \epsilon\right).\]
令 \(Q\) 表示集合
\[\left\{D \sim \mathcal{D}^m\left|\sup_{h\in\mathcal{H}}|E(h) - \widehat{E}_D(h)| > \epsilon\right.\right\},\]
其中 \(D \sim \mathcal{D}^m\) 表示从 \(\mathcal{D}\) 独立同分布采样得到的大小为 \(m\) 的训练集。计算可得
\[\begin{aligned}
P\left(\sup_{h\in\mathcal{H}}|\widehat{E}_D(h) - \widehat{E}_{D^{\prime}}(h)| \geq \frac{1}{2}\epsilon\right) &= \mathbb{E}_{D,D^{\prime}\sim\mathcal{D}^m}\left[\mathbb{I}\left(\sup_{h\in\mathcal{H}}|\widehat{E}_D(h) - \widehat{E}_{D^{\prime}}(h)| \geq \frac{1}{2}\epsilon\right)\right] \\
&= \mathbb{E}_{D\sim\mathcal{D}^m}\left[\mathbb{E}_{D^{\prime}\sim\mathcal{D}^m}\left[\mathbb{I}\left(\sup_{h\in\mathcal{H}}|\widehat{E}_D(h) - \widehat{E}_{D^{\prime}}(h)| \geq \frac{1}{2}\epsilon\right)\right]\right] \\
&\geq \mathbb{E}_{D\in Q}\left[\mathbb{E}_{D^{\prime}\sim\mathcal{D}^m}\left[\mathbb{I}\left(\sup_{h\in\mathcal{H}}|\widehat{E}_D(h) - \widehat{E}_{D^{\prime}}(h)| \geq \frac{1}{2}\epsilon\right)\right]\right].
\end{aligned}\]
第三行的不等式是因为 \(\mathbb{E}_{D\notin Q}[\cdot] \geq 0\)。对于任意 \(D \in Q\)，存在一个假设 \(h_0 \in \mathcal{H}\) 使得 \(|E(h_0) - \widehat{E}_D(h_0)| > \epsilon\)。对于 \(h_0\)，计算可得
\[\begin{aligned}
\mathbb{E}_{D^{\prime}\sim\mathcal{D}^m}\left[\mathbb{I}\left(\sup_{h\in\mathcal{H}}|\widehat{E}_D(h) - \widehat{E}_{D^{\prime}}(h)| \geq \frac{1}{2}\epsilon\right)\right] &\geq \mathbb{E}_{D^{\prime}\sim\mathcal{D}^m}\left[\mathbb{I}\left(|\widehat{E}_D(h_0) - \widehat{E}_{D^{\prime}}(h_0)| \geq \frac{1}{2}\epsilon\right)\right] \\
&= \mathbb{E}_{D^{\prime}\sim\mathcal{D}^m}\left[\mathbb{I}\left(|(\widehat{E}_D(h_0) - E(h_0)) - (\widehat{E}_{D^{\prime}}(h_0) - E(h_0))| \geq \frac{1}{2}\epsilon\right)\right] \\
&\geq \mathbb{E}_{D^{\prime}\sim\mathcal{D}^m}\left[\mathbb{I}\left(|\widehat{E}_D(h_0) - E(h_0)| - |\widehat{E}_{D^{\prime}}(h_0) - E(h_0)| \geq \frac{1}{2}\epsilon\right)\right].
\end{aligned}\]
这两个不等号分别利用了 \(\sup\) 的性质和绝对值的性质。注意到 \(|E(h_0) - \widehat{E}_D(h_0)| > \epsilon\)，若 \(|\widehat{E}_{D^{\prime}}(h_0) - E(h_0)| \leq \frac{1}{2}\epsilon\)，则 \(|\widehat{E}_D(h_0) - E(h_0)| - |\widehat{E}_{D^{\prime}}(h_0) - E(h_0)| \geq \frac{1}{2}\epsilon\) 成立。从而基于上面的不等式可得
\[\begin{aligned}
\mathbb{E}_{D^{\prime}\sim\mathcal{D}^m}\left[\mathbb{I}\left(\sup_{h\in\mathcal{H}}|\widehat{E}_D(h) - \widehat{E}_{D^{\prime}}(h)| \geq \frac{1}{2}\epsilon\right)\right] &\geq \mathbb{E}_{D^{\prime}\sim\mathcal{D}^m}\left[\mathbb{I}\left(|\widehat{E}_D(h_0) - E(h_0)| - |\widehat{E}_{D^{\prime}}(h_0) - E(h_0)| \geq \frac{1}{2}\epsilon\right)\right] \\
&\geq \mathbb{E}_{D^{\prime}\sim\mathcal{D}^m}\left[\mathbb{I}\left(|\widehat{E}_{D^{\prime}}(h_0) - E(h_0)| \leq \frac{1}{2}\epsilon\right)\right] \\
&= P\left(|\widehat{E}_{D^{\prime}}(h_0) - E(h_0)| \leq \frac{1}{2}\epsilon\right) \\
&= 1 - P\left(|\widehat{E}_{D^{\prime}}(h_0) - E(h_0)| > \frac{1}{2}\epsilon\right).
\end{aligned}\]
再有 Chebyshev 不等式：
\[P\left(|\widehat{E}_{D'}(h_0) - E(h_0)| > \frac{1}{2}\epsilon\right) \leq \frac{4(1-E(h_0))E(h_0)}{\epsilon^2m} \leq \frac{1}{\epsilon^2m}.\]
这里其实需要证明 \(\mathbb{V}_{D^{\prime}}(\widehat{E}_{D^{\prime}}(h_0)) = E(h_0)(1-E(h_0))/m\)，这里没证明，我也不知道怎么证明的。
当 \(m \geq 2/\epsilon^2\) 时，\(P\left(|\widehat{E}_{D'}(h_0) - E(h_0)| > \frac{1}{2}\epsilon\right) \leq 1/2\)。于是可得
\[P\left(\sup_{h\in\mathcal{H}}|\widehat{E}_D(h) - \widehat{E}_{D'}(h)| \geq \frac{1}{2}\epsilon\right) \geq \mathbb{E}_{D\in Q}\left[\frac{1}{2}\right] = \frac{1}{2}P\left(\sup_{h\in\mathcal{H}}|E(h) - \widehat{E}_D(h)| > \epsilon\right).\]
这样，我们要证明的东西就成立了，我们下面对 \(P\left(\sup_{h\in\mathcal{H}}|\widehat{E}_D(h) - \widehat{E}_{D^{\prime}}(h)| \geq \frac{1}{2}\epsilon\right)\) 进行进一步的分析。
由于 \(D\) 和 \(D^{\prime}\) 均为从 \(\mathcal{D}\) 独立同分布采样得到的大小为 \(m\) 的训练集，则 \(D\) 和 \(D^{\prime}\) 一共包含 \(2m\) 个样本（这 \(2m\) 个样本有可能重复）。若令 \(T_i\) 表示这 \(2m\) 个样本上的置换，则有 \((2m)!\) 个 \(T_i\)。令 \(T_iD\) 表示 \(2m\) 个样本经过置换 \(T_i\) 的前 \(m\) 个样本，\(T_iD^{\prime}\) 表示这 \(2m\) 个样本经过置换 \(T_i\) 的后 \(m\) 个样本，则对于 \(D\)，\(D^{\prime}\)，\(T_iD\) 和 \(T_iD^{\prime}\) 有
\[P\left(\sup_{h\in\mathcal{H}}|\widehat{E}_D(h) - \widehat{E}_{D^{\prime}}(h)| \geq \frac{1}{2}\epsilon\right) = P\left(\sup_{h\in\mathcal{H}}|\widehat{E}_{T_iD}(h) - \widehat{E}_{T_iD^{\prime}}(h)| \geq \frac{1}{2}\epsilon\right).\]
因此有
\[\begin{aligned}
P\left(\sup_{h\in\mathcal{H}}|\widehat{E}_D(h) - \widehat{E}_{D^{\prime}}(h)| \geq \frac{1}{2}\epsilon\right) &= \mathbb{E}_{D,D^{\prime}}\left[\frac{1}{(2m)!}\sum_{i=1}^{(2m)!}\mathbb{I}\left(\sup_{h\in\mathcal{H}}|\widehat{E}_{T_iD}(h) - \widehat{E}_{T_iD^{\prime}}(h)| \geq \frac{1}{2}\epsilon\right)\right] \\
&= \mathbb{E}_{D,D^{\prime}}\left[\frac{1}{(2m)!}\sum_{i=1}^{(2m)!}\sup_{h\in\mathcal{H}}\mathbb{I}\left(|\widehat{E}_{T_iD}(h) - \widehat{E}_{T_iD^{\prime}}(h)| \geq \frac{1}{2}\epsilon\right)\right] \\
&\leq \mathbb{E}_{D,D^{\prime}}\left[\sum_{h\in\mathcal{H}_{\mid D+D^{\prime}}} \frac{1}{(2m)!}\sum_{i=1}^{(2m)!}\mathbb{I}\left(|\widehat{E}_{T_iD}(h) - \widehat{E}_{T_iD^{\prime}}(h)| \geq \frac{1}{2}\epsilon\right)\right].
\end{aligned}\]
其中 \(\mathcal{H}_{\mid D + D^{\prime}}\) 为 \(\mathcal{H}\) 在训练集 \(D + D^{\prime}\) 上的限制。接下来考虑
\[\sum_{i=1}^{(2m)!}\mathbb{I}\left(|\widehat{E}_{T_iD}(h) - \widehat{E}_{T_iD^{\prime}}(h)| \geq \frac{1}{2}\epsilon\right).\]
这表示对于给定假设 \(h\) 满足 \(|\widehat{E}_{T_iD}(h) - \widehat{E}_{T_iD^{\prime}}(h)| \geq \frac{1}{2}\epsilon\) 的置换数目。令 \(l\) 表示 \(h\) 在 \(D + D^{\prime}\) 上预测正确的样本数目，有
\[\begin{aligned}
\frac{1}{(2m)!}\sum_{i=1}^{(2m)!}\mathbb{I}\left(|\widehat{E}_{T_iD}(h) - \widehat{E}_{T_iD^{\prime}}(h)| \geq \frac{1}{2}\epsilon\right) = \sum_{\substack{k \in [l] \\ \text{s.t. } |2k/m - l/m| > \epsilon/2}} \frac{\binom{l}{k}\binom{2m - l}{m - k}}{\binom{2m}{m}} \leq 2\exp\left(-\frac{\epsilon^2m}{8}\right).
\end{aligned}\]
这个式子的两段我们一段一段仔细分解：
- 第一个等号：显然最左侧的式子可以看作一个概率，正例的示性函数值为 1，负例的示性函数值为 0，所以求和的结果就是正例的个数所占的比例，在古典概型中，这个比例就是正例的概率。\(k\) 表示 \(T_iD\) 中被 \(h\) 预测正确的样本数目，\(m-k\) 表示 \(T_iD\) 中被 \(h\) 预测错误的样本数目，\(\binom{l}{k}\) 表示从 \(l\) 个预测正确的样本中选择 \(k\) 个样本的种数，\(\binom{2m-l}{m-k}\) 表示从 \(2m-l\) 个预测错误的样本中选择 \(m-k\) 个样本的种数，\(\binom{2m}{m}\) 表示从 \(2m\) 个样本中选择 \(m\) 个样本构成 \(T_iD\) 的种数。若 \(|(m-k)/m - (m-l+k)/m| \geq \epsilon/2\)，即 \(|2k/m - l/m| \geq \epsilon/2\)，这也就是 \(|\widehat{E}_{T_iD}(h) - \widehat{E}_{T_iD'}(h)| \geq \frac{1}{2}\epsilon\)。
- 第二个小于等于号：被求和项看可以看作超几何分布的概率，内容是从 \(2m\) 个样本中抽取 \(m\) 个样本，其中有 \(k\) 个是正确的，\(m-k\) 个是错误的，将约束条件变形为 \(\lvert k - l/2 \rvert > m\epsilon/4\)，注意到抽取 \(m\) 个样本中正确样本的期望值为 \(l/2\)，所以约束条件可以看作是正确样本数目偏离期望值的程度大于 \(m\epsilon/4\)，对其使用 Hoeffding 不等式可得不等式的结果。
因此，我们需要求的概率转化为
\[P\left(\sup_{h\in\mathcal{H}}|\widehat{E}_D(h) - \widehat{E}_{D'}(h)| \geq \frac{1}{2}\epsilon\right) \leq 2|\mathcal{H}_{\mid D+D^{\prime}}|\exp\left(-\frac{\epsilon^2m}{8}\right).\]
根据增长函数的定义可知 \(|\mathcal{H}_{\mid D+D^{\prime}}| \leq \Pi_{\mathcal{H}}(2m)\)。再结合最初证明的不等式，对于任意假设 \(h \in \mathcal{H}\) 可得
\[P\left(|E(h) - \widehat{E}_D(h)| > \epsilon\right) \leq P\left(\sup_{h\in\mathcal{H}}|E(h) - \widehat{E}(h)| > \epsilon\right) \leq 4\Pi_{\mathcal{H}}(2m)\exp\left(-\frac{m\epsilon^2}{8}\right).\]
这就完成了证明。
基于上述引理，再结合关于 VC 维与增长函数之间关系，有下面的定理。
定理 4.3：若假设空间 \(\mathcal{H}\) 的有限 VC 维为 \(d\)，\(h \in \mathcal{H}\)，则对 \(m > d\) 和 \(0 < \delta < 1\) 有
\[P\left(|E(h) - \widehat{E}(h)| \leq \sqrt{\frac{8d\ln \frac{2em}{d} + 8\ln \frac{4}{\delta}}{m}}\right) \geq 1 - \delta.\]
证明
由定理 3.1 可知
\[4\Pi_{\mathcal{H}}(2m)\exp\left(-\frac{m\epsilon^2}{8}\right) \leq 4\left(\frac{2em}{d}\right)^d \exp\left(-\frac{m\epsilon^2}{8}\right).\]
令 \(4\left(\frac{2em}{d}\right)^d \exp\left(-\frac{m\epsilon^2}{8}\right) = \delta\) 可得
\[\epsilon = \sqrt{\frac{8d\ln \frac{2em}{d} + 8\ln \frac{4}{\delta}}{m}}.\]
将上式带入引理 4.1，定理得证。
通过此定理，我们可以知道 \(E(h) \leq \widehat{E}(h) + O\left(\sqrt{\frac{\ln(m/d)}{m/d}}\right)\) 以至少 \(1 - \delta\) 的概率成立，泛化误差的收敛率为 \(O\left(\sqrt{\frac{\ln(m/d)}{m/d}}\right)\)。对于有限 VC 维的假设空间，泛化误差的收敛率与 VC 维的大小有关，VC 维越大，假设空间越复杂，泛化误差的收敛率也越慢。其次，有限 VC 维的不可分假设空间比有限不可分假设空间更难收敛，这也是无限假设空间与有限假设空间的区别。
2.2 基于 Rademacher 复杂度的泛化误差界
对于从 \(\mathcal{D}\) 独立同分布采样得到的大小为 \(m\) 的训练集 \(Z\)，函数空间 \(\mathcal{F}\) 关于 \(Z\) 的经验 Rademacher 复杂度和关于 \(\mathcal{D}\) 的 Rademacher 复杂度分别是 \(\widehat{\mathfrak{R}}_Z(\mathcal{F})\) 和 \(\mathfrak{R}_m(\mathcal{F})\)，基于 \(\widehat{\mathfrak{R}}_Z(\mathcal{F})\) 和 \(\mathfrak{R}_m(\mathcal{F})\) 可以分析关于函数空间 \(\mathcal{F}\) 的泛化误差界。
定理 4.4：对于实值函数空间 \(\mathcal{F} : \mathcal{Z} \mapsto [0,1]\)，从分布 \(\mathcal{D}\) 独立同分布采样得到的大小为 \(m\) 的训练集 \(Z = \{z_1,z_2,\ldots,z_m\}\)，\(z_i \in \mathcal{Z}\)，\(f \in \mathcal{F}\) 和 \(0 < \delta < 1\)，以至少 \(1 - \delta\) 的概率有
\[\begin{aligned}
E(f) &\leq \widehat{E}(f) + 2\mathfrak{R}_m(\mathcal{F}) + \sqrt{\frac{\ln(1/\delta)}{2m}},\\
E(f) &\leq \widehat{E}(f) + 2\widehat{\mathfrak{R}}_Z(\mathcal{F}) + 3\sqrt{\frac{\ln(2/\delta)}{2m}}.
\end{aligned}\]
证明
首先定义下面两个量：
\[\begin{aligned}
\widehat{E}_Z(f) &= \frac{1}{m}\sum_{i=1}^m f(z_i),\\
\Phi(Z) &= \sup_{f\in\mathcal{F}}\left(\mathbb{E}[f] - \widehat{E}_Z(f)\right).
\end{aligned}\]
\(Z^{\prime}\) 为与 \(Z\) 仅有一个样本不同的训练集，不妨设 \(z_m \in Z\) 和 \(z'_m \in Z'\) 为不同样本，可得
\[\begin{aligned}
\Phi(Z') - \Phi(Z) &= \sup_{f\in\mathcal{F}}\left(\mathbb{E}[f] - \widehat{E}_{Z'}(f)\right) - \sup_{f\in\mathcal{F}}\left(\mathbb{E}[f] - \widehat{E}_Z(f)\right)\\
&\leq \sup_{f\in\mathcal{F}}\left(\widehat{E}_Z(f) - \widehat{E}_{Z'}(f)\right)\\
&= \sup_{f\in\mathcal{F}}\frac{f(z_m) - f(z'_m)}{m} \leq \frac{1}{m}.
\end{aligned}\]
同样可以得到
\[\Phi(Z) - \Phi(Z') \leq \frac{1}{m}.\]
从而可知
\[|\Phi(Z) - \Phi(Z')| \leq \frac{1}{m}.\]
这就表明了 \(\Phi(Z)\) 是关于 \(Z\) 差有界的。根据 McDiarmid 不等式可知，对于 \(0 < \delta < 1\)，
\[\Phi(Z) \leq \mathbb{E}_Z[\Phi(Z)] + \sqrt{\frac{\ln(1/\delta)}{2m}}\]
以至少 \(1 - \delta\) 的概率成立。下面估计 \(\mathbb{E}_Z[\Phi(Z)]\) 的上界，在使用完 McDiarmid 不等式之后，我们可以不要求 \(Z^{\prime}\) 与 \(Z\) 仅有一个样本不同，这两个集合就变成了分别从 \(\mathcal{F}\) 中独立同分布采样得到的两个训练集。
\[\begin{aligned}
\mathbb{E}_Z[\Phi(Z)] &= \mathbb{E}_Z\left[\sup_{f\in\mathcal{F}}\left(\mathbb{E}[f] - \widehat{E}_Z(f)\right)\right]\\
&= \mathbb{E}_Z\left[\sup_{f\in\mathcal{F}}\mathbb{E}_{Z'}\left[\widehat{E}_{Z'}[f] - \widehat{E}_Z[f]\right]\right] \leq \mathbb{E}_{Z,Z'}\left[\sup_{f\in\mathcal{F}}\left(\widehat{E}_{Z'}[f] - \widehat{E}_Z[f]\right)\right]\\
&= \mathbb{E}_{Z,Z'}\left[\sup_{f\in\mathcal{F}}\frac{1}{m}\sum_{i=1}^m\left(f(z'_i) - f(z_i)\right)\right] = \mathbb{E}_{\sigma,Z,Z'}\left[\sup_{f\in\mathcal{F}}\frac{1}{m}\sum_{i=1}^m \sigma_i\left(f(z'_i) - f(z_i)\right)\right]\\
&\leq \mathbb{E}_{\sigma,Z'}\left[\sup_{f\in\mathcal{F}}\frac{1}{m}\sum_{i=1}^m \sigma_if(z'_i)\right] + \mathbb{E}_{\sigma,Z}\left[\sup_{f\in\mathcal{F}}\frac{1}{m}\sum_{i=1}^m -\sigma_if(z_i)\right]\\
&= 2\mathbb{E}_{\sigma,Z}\left[\sup_{f\in\mathcal{F}}\frac{1}{m}\sum_{i=1}^m \sigma_if(z_i)\right]\\
&= 2\mathfrak{R}_m(\mathcal{F}).
\end{aligned}\]
有下面几点需要注意：
- 第二个等号是对 \(Z^{\prime}\) 的期望，这里其实也可以看出来 \(Z^{\prime}\) 不可能是与 \(Z\) 仅有一个样本不同的集合。
- 第二行的不等号来自于 Jensen 不等式，利用了 \(\sup\) 的凸性。
- 第三行第二个等号利用了对称化的想法，在「机器学习算法的数学分析」的笔记中有介绍，其中由于 \(z_i\) 和 \(z^\prime_i\) 是独立同分布的，所以 \(f(z_i) - f(z^\prime_i)\) 的分布关于原点对称，再乘以一个 Rademacher 随机变量 \(\sigma_i\)，当然不应强分布和均值。
- 后面的推导就是很自然的事情了。
这样，对于任意的 \(f\in \mathcal{F}\)，有
\[\mathbb{E}[f] - \widehat{E}_Z(f) \leq \sup_{f\in\mathcal{F}}\left(\mathbb{E}[f] - \widehat{E}_Z(f)\right) = \Phi(Z) \leq \mathbb{E}_Z[\Phi(Z)] + \sqrt{\frac{\ln(1/\delta)}{2m}} = 2\mathfrak{R}_m(\mathcal{F}) + \sqrt{\frac{\ln(1/\delta)}{2m}}.\]
因此，我们要的第一个式子得证。再然后，我们知道改变训练集中的一个样本后经验 Rademacher 复杂度最多改变 \(1/m\)，即 \(|\widehat{\mathfrak{R}}_Z(\mathcal{F}) - \widehat{\mathfrak{R}}_{Z'}(\mathcal{F})| \leq 1/m\)。再根据 McDiarmid 不等式可知：
\[\widehat{\mathfrak{R}}_Z(\mathcal{F}) \leq \widehat{\mathfrak{R}}_{Z'}(\mathcal{F}) + \sqrt{\frac{\ln(2/\delta)}{2m}}\]
以至少 \(1 - \delta/2\) 的概率成立。还有
\[\Phi(Z) \leq \mathbb{E}_Z[\Phi(Z)] + \sqrt{\frac{\ln(2/\delta)}{2m}}\]
以至少 \(1 - \delta/2\) 的概率成立。将上面两个不等式带入到下面的式子中，利用联合界不等式可得：
\[\Phi(Z) \leq 2\widehat{\mathfrak{R}}_Z(\mathcal{F}) + 3\sqrt{\frac{\ln(2/\delta)}{2m}}\]
以至少 \(1 - \delta\) 的概率成立，从而第二个式子得证。
定理 4.4 的适用范围是实值函数空间 \(\mathcal{F} : \mathcal{Z} \mapsto [0,1]\)，一般用于回归问题。对于分类问题有下面的定理。
定理 4.5：对于假设空间 \(\mathcal{H} : \mathcal{X} \mapsto \{-1,+1\}\)，从分布 \(\mathcal{D}\) 独立同分布采样得到的大小为 \(m\) 的训练集 \(D = \{\boldsymbol{x}_1,\ldots,\boldsymbol{x}_m\}\)，\(\boldsymbol{x}_i \in \mathcal{X}\)，\(h \in \mathcal{H}\) 和 \(0 < \delta < 1\)，以至少 \(1 - \delta\) 的概率有
\[\begin{aligned}
E(h) &\leq \widehat{E}(h) + \mathfrak{R}_m(\mathcal{H}) + \sqrt{\frac{\ln(1/\delta)}{2m}},\\
E(h) &\leq \widehat{E}(h) + \widehat{\mathfrak{R}}_D(\mathcal{H}) + 3\sqrt{\frac{\ln(2/\delta)}{2m}}.
\end{aligned}\]
证明
对于二分类问题的假设空间 \(\mathcal{H}\)，令 \(\mathcal{Z} = \mathcal{X} \times \{-1,+1\}\)，\(\mathcal{H}\) 中的假设 \(h\) 可以变形为 \(f_h(z) = f_h(\boldsymbol{x},y) = \mathbb{I}(h(\boldsymbol{x}) \neq y)\)。于是值域为 \(\{-1,+1\}\) 的假设空间 \(\mathcal{H}\) 转化为值域为 \([0,1]\) 的函数空间 \(\mathcal{F}_{\mathcal{H}} = \{f_h : h \in \mathcal{H}\}\)。从 Rademacher 复杂度的定义可知
\[\begin{aligned}
\widehat{\mathfrak{R}}_Z(\mathcal{F}_{\mathcal{H}}) &= \mathbb{E}_{\boldsymbol{\sigma}}\left[\sup_{f_h\in\mathcal{F}_{\mathcal{H}}} \frac{1}{m}\sum_{i=1}^m \sigma_if_h(\boldsymbol{x}_i,y_i)\right] = \mathbb{E}_{\boldsymbol{\sigma}}\left[\sup_{h\in\mathcal{H}} \frac{1}{m}\sum_{i=1}^m \sigma_i\mathbb{I}(h(\boldsymbol{x}_i) \neq y_i)\right]\\
&= \mathbb{E}_{\boldsymbol{\sigma}}\left[\sup_{h\in\mathcal{H}} \frac{1}{m}\sum_{i=1}^m \sigma_i\frac{1-y_ih(\boldsymbol{x}_i)}{2}\right] = \frac{1}{2}\mathbb{E}_{\boldsymbol{\sigma}}\left[\frac{1}{m}\sum_{i=1}^m \sigma_i + \sup_{h\in\mathcal{H}} \frac{1}{m}\sum_{i=1}^m (-y_i\sigma_ih(\boldsymbol{x}_i))\right]\\
&= \frac{1}{2}\mathbb{E}_{\boldsymbol{\sigma}}\left[\sup_{h\in\mathcal{H}} \frac{1}{m}\sum_{i=1}^m (-y_i\sigma_ih(\boldsymbol{x}_i))\right] = \frac{1}{2}\mathbb{E}_{\boldsymbol{\sigma}}\left[\sup_{h\in\mathcal{H}} \frac{1}{m}\sum_{i=1}^m (\sigma_ih(\boldsymbol{x}_i))\right]\\
&= \frac{1}{2}\widehat{\mathfrak{R}}_D(\mathcal{H}).
\end{aligned}\]
- 第一行和第二行的等号都是纯粹的代入；
- 第三行的第一个等号利用了 \(\sigma\) 的均匀分布的性质，第二个等号利用了 \(-y_i\sigma_i\) 和 \(\sigma_i\) 等价的性质；
- 后面就自然了。
同时对上式两边取期望可得
\[\mathfrak{R}_Z(\mathcal{F}_{\mathcal{H}}) = \frac{1}{2}\mathfrak{R}_D(\mathcal{H}).\]
将上式代入定理 4.4，定理得证。
3. 泛化误差下界
3.1 可分情景
3.2 不可分情景
4. 分析实例