4.4 交叉验证

模型选择的另一种方法，交叉验证，包括使用训练样本的一部分作为验证集来选择一个假设集 ${\mathcal{H}}_k$。

• 这与依赖理论学习界限为每个假设集分配惩罚的SRM模型形成对比。
• 在本节中，我们分析交叉验证方法并将其性能与SRM进行比较。

与前一节类似， 设${\left({\mathcal{H}}_k\right)}_{k\ge 1}$为一个具有递增复杂度的可数假设集序列。 交叉验证(CV)的解是通过以下方式获得的。

• 设 $S$ 为大小为$m$. $S$ 的独立同分布带标签样本
• 将其分为大小为 $\left(1-\alpha \right)m$ 的样本 $S_1$ 和大小为 $\alpha m$ 的样本 $S_2$， 其中
  • $\alpha \in \left(0,1\right)$通常选择相对较小。
  • $S_1$ 保留用于训练，
  • $S_2$ 用于验证。
• 对于任意的 $k\in \mathbb{N}$，设 $h_{S_1,k}^{\mathrm{ERM}}$ 表示使用假设集 ${\mathcal{H}}_k$ 在 $S_1$ 上运行ERM得到的解。
• 通过交叉验证返回的假设$h_S^{\mathrm{CV}}$是ERM解 $h_{S_1,k}^{\mathrm{ERM}}$ 在$S_2$上表现最好的:

$$h_S^{\mathrm{CV}}=\underset{h\in \left\{h_{S_1,k}^{\mathrm{ERM}}:k\ge 1\right\}}{\mathrm{argmin}}{\hat{R}}_{S_2}\left(h\right)\text{\hspace{1em}(4.7)}$$

以下的一般结果将帮助我们推导出交叉验证的学习保证。

命题4.3

对于

• 任意的 $\alpha >0$
• 任意的样本大小 $m\ge 1$，

以下的一般不等式成立:

$$\begin{array}{rl}& \mathbb{P}\left[\underset{k\ge 1}{\sup }\left|R\left(h_{S_1,k}^{\mathrm{ERM}}\right)-{\hat{R}}_{S_2}\left(h_{S_1,k}^{\mathrm{ERM}}\right)\right|>ϵ+\sqrt{\frac{\log k}{\alpha m}}\right]\\ \le & 4e^{-2\alpha m{ϵ}^2}.\end{array}$$

\begin{proof} 通过联合界，我们可以写出

$$\begin{array}{rl}& \mathbb{P}\left[\underset{k\ge 1}{\sup }\left|R\left(h_{S_1,k}^{\mathrm{ERM}}\right)-{\hat{R}}_{S_2}\left(h_{S_1,k}^{\mathrm{ERM}}\right)\right|>ϵ+\sqrt{\frac{\log k}{\alpha m}}\right]\\ & \le \sum _{k=1}^{\infty }\mathbb{P}\left[\left|R\left(h_{S_1,k}^{\mathrm{ERM}}\right)-{\hat{R}}_{S_2}\left(h_{S_1,k}^{\mathrm{ERM}}\right)\right|>ϵ+\sqrt{\frac{\log k}{\alpha m}}\right]\\ & =\sum _{k=1}^{\infty }\mathbb{E}\left[\mathbb{P}\left[\left|R\left(h_{S_1,k}^{\mathrm{ERM}}\right)-{\hat{R}}_{S_2}\left(h_{S_1,k}^{\mathrm{ERM}}\right)\right|>ϵ+\sqrt{\frac{\log k}{\alpha m}}|S_1\right]\right].\end{array}$$

假设$h_{S_1,k}^{\mathrm{ERM}}$在$S_1$的条件下是固定的。 此外，样本$S_2$与$S_1$独立。 因此，通过 Hoeffding 不等式， 我们可以界定条件概率如下:

$$\begin{array}{rl}& \mathbb{P}\left[\left|R(h_{S_1,k}^{\mathrm{ERM}})-{\hat{R}}_{S_2}(h_{S_1,k}^{\mathrm{ERM}})\right|>ϵ+\sqrt{\frac{\log k}{\alpha m}}|S_1\right]\\ & \le 2e^{-2\alpha m{\left(ϵ+\sqrt{\frac{\log k}{\alpha m}}\right)}^2}\\ & \le 2e^{-2\alpha m{ϵ}^2-2\log k}\\ & =\frac{2}{k^2}{e}^{-2\alpha m{ϵ}^2}.\end{array}$$

将这个界右侧代入(4.8)并对$k$求和得到

$$\begin{array}{rl}& \mathbb{P}\left[\underset{k\ge 1}{\sup }\left|R\left(h_{S_1,k}^{\mathrm{ERM}}\right)-{\hat{R}}_{S_2}\left(h_{S_1,k}^{\mathrm{ERM}}\right)\right|>ϵ+\sqrt{\frac{\log k}{\alpha m}}\right]\\ & \le \frac{{\pi }^2}{3}{e}^{-2\alpha m{ϵ}^2}\\ & <4e^{-2\alpha m{ϵ}^2}\end{array}$$

这就完成了证明。 \end{proof}

设

• $R\left(h_{S_1}^{\mathrm{SRM}}\right)$ 为使用大小为 $\left(1-\alpha m\right)$ 的样本 $S_1$ 的SRM解的泛化误差，
• $R\left(h_S^{\mathrm{CV}},S\right)$ 为使用大小为 $m$ 的样本 $S$ 的交叉验证解的泛化误差。 那么，利用 命题4.3，可以推导出以下的学习保证， 它比较了CV方法的误差与SRM的误差。

定理4.4 交叉验证与SRM的比较)

对任意 $\delta >0$, 有至少 $1-\delta$ 的概率，以下成立:

$$\begin{array}{rl}& R\left(h_S^{\mathrm{CV}}\right)-R\left(h_{S_1}^{\mathrm{SRM}}\right)\\ & \le 2\sqrt{\frac{\log \max \left(k\left(h_S^{\mathrm{CV}}\right),k\left(h_{S_1}^{\mathrm{SRM}}\right)\right)}{\alpha m}}+2\sqrt{\frac{\log \frac{4}{\delta }}{2\alpha m}},\end{array}$$

其中，对于任何 $h$, $k\left(h\right)$ 表示包含 $h$ 的假设集的最小索引。

\begin{proof} 根据 命题4.3 和 定理4.2, 利用 $h_S^{\mathrm{CV}}$ 作为最小化者的性质，对于任何 $\delta >0$，在至少 $1-\delta$ 的概率下，以下不等式成立:

$$\begin{array}{rl}& R\left(h_S^{\mathrm{CV}}\right)\\ & \le {\hat{R}}_{S_2}\left(h_S^{\mathrm{CV}}\right)+\sqrt{\frac{\log \left(k\left(h_S^{\mathrm{CV}}\right)\right)}{\alpha m}}+\sqrt{\frac{\log \frac{4}{\delta }}{2\alpha m}}\\ & \le {\hat{R}}_{S_2}\left(h_{S_1}^{\mathrm{SRM}}\right)+\sqrt{\frac{\log \left(k\left(h_S^{\mathrm{CV}}\right)\right)}{\alpha m}}+\sqrt{\frac{\log \frac{4}{\delta }}{2\alpha m}}\\ & \le R\left(h_{S_1}^{\mathrm{SRM}}\right)+\sqrt{\frac{\log \left(k\left(h_S^{\mathrm{CV}}\right)\right)}{\alpha m}}+\sqrt{\frac{\log \left(k\left(h_{S_1}^{\mathrm{SRM}}\right)\right)}{\alpha m}}+2\sqrt{\frac{\log \frac{4}{\delta }}{2\alpha m}}\\ & \le R\left(h_{S_1}^{\mathrm{SRM}}\right)+2\sqrt{\frac{\log (\max \left(k\left(h_S^{\mathrm{CV}}\right),k\left(h_{S_1}^{\mathrm{SRM}}\right)\right)}{\alpha m}}+2\sqrt{\frac{\log \frac{4}{\delta }}{2\alpha m}}.\end{array}$$

这完成了证明。 \end{proof}

刚才证明的学习保证显示，

• 对于样本大小为 $m$ 的CV解，其泛化误差与样本大小为 $\left(1-\alpha \right)m$ 的SRM解的泛化误差相近。
• 对于相对较小的$\alpha$，这表明了一个类似于SRM的保证，正如之前讨论的，这是非常有利的。
• 然而，在某些不利的条件下，一个算法(在这里是SRM)在 $\left(1-\alpha \right)m$ 个点上训练的性能可能比在 $m$ 个点上训练的性能差得多
  • 避免这种相变问题是实际中使用 $n$ 倍交叉验证方法的主要动机之一，参见 4.5 n-折交叉验证。
• 因此，这个界限实际上暗示了一个权衡:
  • $\alpha$ 应该足够小以避免刚刚提到的有利条件，
  • 同时应该足够大，以便界限右侧保持较小且具有信息性。

在实践中，CV的学习界限在某些情况下可以更加明确。

• 例如，假设假设集 ${\mathcal{H}}_k$ 是嵌套的，并且ERM解的实证误差$h_{S_1,k}^{\mathrm{ERM}}$在达到零之前是递减的:
• 对于任何 $k$，对于所有满足 ${\hat{R}}_{S_1}\left(h_{S_1,k}^{\mathrm{ERM}}\right)>0$ 的 $k$ 以及 ${\hat{R}}_{S_1}\left(h_{S_1,k+1}^{\mathrm{ERM}}\right)\le {\hat{R}}_{S_1}\left(h_{S_1,k}^{\mathrm{ERM}}\right)$ 其他情况, ${\hat{R}}_{S_1}\left(h_{S_1,k+1}^{\mathrm{ERM}}\right)<{\hat{R}}_{S_1}\left(h_{S_1,k}^{\mathrm{ERM}}\right)$
• 注意到 ${\hat{R}}_{S_1}\left(h_{S_1,k}^{\mathrm{ERM}}\right)>0$ 至少意味着 $h_{S_1,k}^{\mathrm{ERM}}$ 的一个误差，因此 ${\hat{R}}_{S_1}\left(h_{S_1,k}^{\mathrm{ERM}}\right)>\frac{1}{m}$
• 鉴于这一点，我们必须有，对于所有$n\ge m+1$， ${\hat{R}}_{S_1}\left(h_{S_1,n}^{\mathrm{ERM}}\right)=0$
• 因此，我们得到，对于所有$n\ge m+1$，$h_{S_1,n}^{\mathrm{ERM}}=h_{S_1,m+1}^{\mathrm{ERM}}$
• 并且我们可以假设 $k\left(f_{CV}\right)\le m+1$
• 由于 ${\mathcal{H}}_k$ 的复杂性随 $k$ 增加而增加，我们还得到 $k\left(f_{SRM}\right)\le m+1$
• 鉴于这一点，我们得到以下更明确的学习界限，用于交叉验证:

$$R\left(f_{CV},S\right)-R\left(f_{SRM},S_1\right)\le 2\sqrt{\frac{\log \left(\frac{4}{\delta }\right)}{2\alpha m}}+2\sqrt{\frac{\log \left(m+1\right)}{\alpha m}}.$$