4.3 结构风险最小化(SRM)

选择假设集 $\mathcal{H}$ 的策略

• 方法1: 選擇一個非常複雜的家族$\mathcal{H}$
  • 可以使近似误差不存在或非常小。
  • 然而，這可能導致泛化界限无法适用于$\mathcal{H}$。
• 方法2: 逐渐增加假设集的复杂性
  • 将$\mathcal{H}$分解为逐渐复杂化的假设集的并集${\mathcal{H}}_{\gamma }$，即$\mathcal{H}=\bigcup _{\gamma \in \Gamma }{\mathcal{H}}_{\gamma }$。
  • 其中${\mathcal{H}}_{\gamma }$的复杂性随$\gamma$增加，对于某些集合$\Gamma$。

图 4.2 描述一个丰富家族$\mathcal{H}=\bigcup _{\gamma \in \Gamma }{\mathcal{H}}_{\gamma }$的分解的图示。

• 选择参数 ${\gamma }^{\ast }\in \Gamma$
  • 来决定应该选择哪个假设集${\mathcal{H}}_{{\gamma }^{\ast }}$。
  • 目的是在估计误差和近似误差之间找到最有利的权衡。
• 过量误差 (excess error) (也称为过量风险 (excess risk))
  • 可以对其和，即$\bigcup _{\gamma \in \Gamma }{\mathcal{H}}_{\gamma }$，使用统一的上限。

图4.3 选择具有最有利估计误差和近似误差权衡的 ${\gamma }^{\ast }$。

结构风险最小化 (SRM) 方法

• 假设集 $\mathcal{H}$ 的分解
  • 可以将假设集 $\mathcal{H}$ 分解为可数集。
  • 例如，$\mathcal{H}=\bigcup _{k\ge 1}{\mathcal{H}}_k$。
• 嵌套假设集
  • 假设集 ${\mathcal{H}}_k$ 被假设为嵌套的：${\mathcal{H}}_k\subset {\mathcal{H}}_{k+1}$对于所有 $k\ge 1$。
  • 然而，这些结果也适用于非嵌套的假设集。
• SRM 流程
  • 选择索引 $k^{\ast }\ge 1$ 和 ERM 假设 $h$ 在 ${\mathcal{H}}_{k^{\ast }}$ 中，以最小化过量误差的上界。

如我们将看到的，以下学习界对所有 $h\in \mathcal{H}$ 都成立:

• 对于任何$\delta >0$，
• 在从 ${\mathcal{D}}^m$ 中抽取大小为 $m$ 的样本 $S$ 的概率至少为 $1-\delta$ 的情况下，
• 对于所有 $h\in {\mathcal{H}}_k$ 和 $k\ge 1$，

$$R\left(h\right)\le {\hat{R}}_S\left(h\right)+{\Re }_m\left({\mathcal{H}}_{k\left(h\right)}\right)+\sqrt{\frac{\log k}{m}}+\sqrt{\frac{\log \frac{2}{\delta }}{2m}}.$$

因此，为了最小化由此产生的过量误差 $\left(R\left(h\right)-R^{\ast }\right)$ 的上界，指标 $k$ 和假设 $h\in {\mathcal{H}}_k$ 应该被选择来最小化以下目标函数

$$F_k\left(h\right)={\hat{R}}_S\left(h\right)+{\Re }_m\left({\mathcal{H}}_k\right)+\sqrt{\frac{\log k}{m}}.$$

这正是 SRM 解 $h_S^{\mathrm{SRM}}$ 的定义:

$$\begin{array}{rl}{h}_S^{\mathrm{SRM}}& =\underset{k\ge 1,h\in {\mathcal{H}}_k}{\mathrm{argmin}}{F}_k\left(h\right)\\ & =\underset{k\ge 1,h\in {\mathcal{H}}_k}{\mathrm{argmin}}{\hat{R}}_S\left(h\right)+R_m\left({\mathcal{H}}_k\right)+\sqrt{\frac{\log k}{m}}.\end{array}\text{\hspace{1em}(4.4)}$$

结构风险最小化 (SRM) 方法

• 确定最优索引 $k^{\ast }$
  • SRM 确定了一个最优索引 $k^{\ast }$。
  • 这意味着也确定了假设集 ${\mathcal{H}}_{k^{\ast }}$。
• 返回 ERM 解
  • 基于选定的假设集 ${\mathcal{H}}_{k^{\ast }}$，SRM 返回 ERM 解。

• SRM 通过最小化训练误差和惩罚项 $R_m\left({\mathcal{H}}_k\right)+\sqrt{\log k/m}$ 之和的上界，进一步说明了对索引 $k^{\ast }$ 和假设集 ${\mathcal{H}}_{k^{\ast }}$ 的选择。
• 对于任何 $h\in \mathcal{H}$，我们将用 ${\mathcal{H}}_{k\left(h\right)}$ 表示包含 $h$ 的 ${\mathcal{H}}_k$ 中最简单的假设集。
• 任何 $h\in \mathcal{H}$，SRM 解都比 ERM 解在过量误差方面好。

图4.4 结构风险最小化的图示。 显示了三个误差随索引$k$变化的曲线。 显然，随着$k$的增加，或者说假设集${\mathcal{H}}_k$的复杂度增加，训练误差减小，而惩罚项增加。 SRM 选择使泛化误差上界最小的假设，该上界是经验误差和惩罚项的和。

定理4.2 SRM学习保证

• 对于任意的 $\delta >0$，
  • 从 ${\mathcal{D}}^m$ 中抽取大小为 $m$ 的 i.i.d. 样本 $S$
• 至少为 $1-\delta$ 的概率下，
  • SRM方法返回的假设 $h_S^{\mathrm{SRM}}$ 的泛化误差有如下界限:

$$\begin{array}{rl}& R\left(h_S^{\mathrm{SRM}}\right)\\ \le & \underset{h\in \mathcal{H}}{\inf }\left(R\left(h\right)+2{\Re }_m\left({\mathcal{H}}_{k\left(h\right)}\right)+\sqrt{\frac{\log k\left(h\right)}{m}}\right)\\ & +\sqrt{\frac{2\log \frac{3}{\delta }}{m}}.\end{array}$$

\begin{proof} 首先观察到，由联合界可知，以下不等式成立:

$$\begin{array}{rl}& \mathbb{P}\left[\underset{h\in \mathcal{H}}{\sup }R\left(h\right)-F_{k\left(h\right)}\left(h\right)>ϵ\right]\\ & =\mathbb{P}\left[\underset{k\ge 1}{\sup }\underset{h\in {\mathcal{H}}_k}{\sup }R\left(h\right)-F_k\left(h\right)>ϵ\right]\\ & \le \sum _{k=1}^{\infty }\mathbb{P}\left[\underset{h\in {\mathcal{H}}_k}{\sup }R\left(h\right)-F_k\left(h\right)>ϵ\right]\\ & =\sum _{k=1}^{\infty }\mathbb{P}\left[\underset{h\in {\mathcal{H}}_k}{\sup }R\left(h\right)-{\hat{R}}_S\left(h\right)-{\Re }_m\left({\mathcal{H}}_k\right)>ϵ+\sqrt{\frac{\log k}{m}}\right]\\ & \le \sum _{k=1}^{\infty }\exp \left(-2m{\left[ϵ+\sqrt{\frac{\log k}{m}}\right]}^2\right)\\ & \le \sum _{k=1}^{\infty }{e}^{-2m{ϵ}^2}{e}^{-2\log k}\\ & =e^{-2m{ϵ}^2}\sum _{k=1}^{\infty }\frac{1}{k^2}\\ & =\frac{{\pi }^2}{6}{e}^{-2m{ϵ}^2}\\ & \le 2e^{-2m{ϵ}^2}.\end{array}\text{\hspace{1em}(4.5)}$$

接下来，对于任意两个随机变量 $X_1$ 和 $X_2$， 如果$X_1+X_2>ϵ$， 那么 $X_1$ 或 $X_2$ 必须大于$ϵ/2$。 基于这一点，由联合界可知， $\mathbb{P}\left[X_1+X_2>ϵ\right]\le \mathbb{P}\left[X_1>\frac{ϵ}{2}\right]+\mathbb{P}\left[X_2>\frac{ϵ}{2}\right].$ 使用这个不等式、不等式(4.5)以及对于所有$h\in \mathcal{H}$都成立的不等式 $F_{k\left(h_S^{\mathrm{SRM}}\right)}\left(h_S^{\mathrm{SRM}}\right)\le F_{k\left(h\right)}\left(h\right),$ 根据 $h_S^{\mathrm{SRM}}$ 的定义，我们可以写出，对于任意 $h\in \mathcal{H}$，

$$\begin{array}{rl}& \mathbb{P}\left[R\left(h_S^{\mathrm{SRM}}\right)-R\left(h\right)-2{\Re }_m\left({\mathcal{H}}_{k\left(h\right)}\right)-\sqrt{\frac{\log k\left(h\right)}{m}}>ϵ\right]\\ & \le \mathbb{P}\left[R\left(h_S^{\mathrm{SRM}}\right)-F_{k\left(h_S^{\mathrm{SRM}}\right)}\left(h_S^{\mathrm{SRM}}\right)>\frac{ϵ}{2}\right]\\ & +\mathbb{P}\left[F_{k\left(h_S^{\mathrm{SRM}}\right)}\left(h_S^{\mathrm{SRM}}\right)-R\left(h\right)-2{\Re }_m\left({\mathcal{H}}_{k\left(h\right)}\right)-\sqrt{\frac{\log k\left(h\right)}{m}}>\frac{ϵ}{2}\right]\\ & \le 2e^{-\frac{m{ϵ}^2}{2}}+\mathbb{P}\left[F_{k\left(h\right)}\left(h\right)-R\left(h\right)-2{\Re }_m\left({\mathcal{H}}_{k\left(h\right)}\right)-\sqrt{\frac{\log k\left(h\right)}{m}}>\frac{ϵ}{2}\right]\\ & =2e^{-\frac{m{ϵ}^2}{2}}+\mathbb{P}\left[{\hat{R}}_S\left(h\right)-R\left(h\right)-{\Re }_m\left({\mathcal{H}}_{k\left(h\right)}\right)>\frac{ϵ}{2}\right]\\ & =2e^{-\frac{m{ϵ}^2}{2}}+e^{-\frac{m{ϵ}^2}{2}}=3e^{-\frac{m{ϵ}^2}{2}}.\end{array}$$

将右侧设置为等于$\delta$，完成证明。 \end{proof}

刚才证明的SRM学习保证是引人注目的。

• 为了简化讨论，假设存在 $h^{\ast }$ 使得 $R\left(h^{\ast }\right)=\underset{h\in \mathcal{H}}{\inf }R\left(h\right)$
  • 即存在一个最佳分类器 $h^{\ast }\in \mathcal{H}$。
• 那么，定理特别暗示，
  • 在至少为 $1-\delta$ 的概率下，
  • 以下不等式对于所有 $h\in \mathcal{H}$ 都成立:

$$\begin{array}{rl}R\left(h_S^{\mathrm{SRM}}\right)\le & R\left(h^{\ast }\right)+2{\Re }_m\left({\mathcal{H}}_{k\left(h^{\ast }\right)}\right)\\ & +\sqrt{\frac{\log k\left(h^{\ast }\right)}{m}}+\sqrt{\frac{2\log \frac{3}{\delta }}{m}}.\end{array}\text{\hspace{1em}(4.6)}$$

• 注意到，值得注意的是，这个界限与 ${\mathcal{H}}_{k\left(h^{\ast }\right)}$ 的估计误差界限相似:
  • 它仅与项 $\sqrt{\log k\left(h^{\ast }\right)/m}$ 不同。
• 因此，除了该项之外，SRM 的保证与如果我们有一个告知我们最佳分类器的假设集索引 $k\left(h^{\ast }\right)$ 的预言者所获得的保证一样有利。

此外，观察到

• 当$\mathcal{H}$足够丰富
  • 以至于$R\left(h^{\ast }\right)$接近贝叶斯误差时，
• 学习界限(4.6)大致上是SRM解的过量误差的界限。
• 注意，如果对于某些 $k_0$，ERM解的实证误差为零，
  • 特别是当${\mathcal{H}}_{k_0}$包含贝叶斯误差时，
  • 那么，对于所有$k>k_0$我们有$\underset{h\in {\mathcal{H}}_k}{\min }{F}_{k_0}\left(h\right)\le \underset{h\in {\mathcal{H}}_k}{\min }{F}_k\left(h\right),$
  • 并且只需要在SRM中考虑有限多个指标。

更一般地假设，

• 如果 $\underset{h\in {\mathcal{H}}_k}{\min }{F}_k\left(h\right)\le \underset{h\in {\mathcal{H}}_{k+1}}{\min }{F}_k\left(h\right)$ 对于某些 $k$ 成立，那么无需检查 $k+1$ 以外的指标。
  • 例如，如果在某个指标 $k$ 之后实证误差不能再进一步改善，那么这个性质可能成立。
• 在这种情况下，可以通过在区间$\left[1,k_{\max }\right]$中进行二分搜索来确定最小化指标$k^{\ast }$，给定某个最大值$k_{\max }$。
• $k_{\max }$，该最大值本身可以通过检查 $\underset{h\in {\mathcal{H}}_{2^n}}{\min }{F}_k\left(h\right)$ 对于指数增长的指标 $2^n$, $n\ge 1$，并设置 $k_{\max }=2^n$ 对于 $n$ 使得 $\underset{h\in {\mathcal{H}}_{2^n}}{\min }{F}_k\left(h\right)\le \underset{h\in {\mathcal{H}}_{2^{n+1}}}{\min }{F}_k\left(h\right)$ 来找到。
• 找到 $k_{\max }$ 需要的ERM计算次数在$O\left(n\right)=O\left(\log k_{\max }\right)$ 之内，同样，由于二分搜索导致的ERM计算次数在 $O\left(\log k_{\max }\right)$ 之内。因此，如果 $n$ 是使得 $k^{\ast }<2^n$ 成立的最小整数，那么总的ERM计算次数在 $O\left(\log k^{\ast }\right)$之内。

结构风险最小化 (SRM) 方法的缺点

• 缺乏灵活性
  • SRM 依赖于 $\mathcal{H}$ 可分解为可数多个假设集，每个假设集的 Rademacher 复杂度都收敛。
  • 这仍然是一个很强的假设。
  • 例如，所有可测函数的族不能写成有限 VC维的可数多个假设集的并集。
• 需要选择 $\mathcal{H}$ 或 ${\mathcal{H}}_k$
  • 选择 $\mathcal{H}$ 或假设集 ${\mathcal{H}}_k$ 是 SRM 的关键组成部分。
  • 这需要对问题和数据进行详细了解。
• 计算成本高昂
  • SRM 的主要缺点是计算成本高昂：
    • 对于大多数假设集，找到 ERM 的解是 NP 困难的。
    • 通常，SRM 需要确定大量指标 $k$ 的解。
    • 这使得 SRM 不适合大规模数据或复杂问题。
• 处理挑战
  • SRM 仍然存在处理挑战的问题：
    • 可能需要人工调整参数和超参数。
    • 需要仔细选择假设集 ${\mathcal{H}}_k$ 以确保收敛和性能。