3.4 Lower bounds

• 上一节中，我们给出了关于泛化误差的几个上界。

• 相比之下，本节将提供任何学习算法的泛化误差的下界，

  • 这些下界是基于所使用假设集合的 VC 维度给出的。

• 这些下界是通过找到一个“糟糕的”分布来展示的，适用于任意算法。

  • 由于学习算法是任意的，具体指定这个分布很困难。
  • 因此，只需非构造性地证明该分布的存在即可。
  • 从高层次上讲，所使用的证明技术是保罗·埃尔德什的概率方法。
    • 在接下来的证明中，首先给出了关于定义分布参数的期望误差的下界。
    • 基于此，展示了该下界对于至少一组参数（即某个分布）成立。

定理 3.20 下界，可实现情况

• 设 $\mathcal{H}$ 为 VC 维度为 $d>1$ 的假设集合。
• 则对于
  • 任意的 $m\ge 1$
  • 任意的学习算法 $\mathcal{A}$，
• 存在
  • 一个定义在 $\mathcal{X}$ 上的分布 $\mathcal{D}$
  • 一个目标函数 $f\in \mathcal{H}$，
• 使得 \underset{S \sim {\mathcal{D}}^{m}}{\mathbb{P}}\left\lbrack {{R}_{\mathcal{D}}\left( {{h}_{S},f}\right) > \frac{d - 1}{32m}}\right\rbrack \geq 1/{100}. \tag{3.31}

\begin{proof}

• 定义：

  • 令 $\overline{\mathcal{X}}=\{x_0,x_1,\dots ,x_{d-1}\}\subseteq \mathcal{X}$
  • 该集合被 $\mathcal{H}$ 打碎

• 对于任意的 $ϵ>0$：

  • 选择分布 $\mathcal{D}$
    • 支持集被限制为 $\overline{\mathcal{X}}$
    • 其中一点 $(x_0)$ 的概率：
  • 非常高的概率 $(1-8ϵ)$
  • 其他点的概率质量均匀分布： - $\forall i\in [d-1],{\mathbb{P}}_{\mathcal{D}}[x_i]=\frac{8ϵ}{d-1}$

• 样本特性：

  • 大多数样本将包含 $x_0$
  • 由于 $\mathcal{X}$ 被打碎，算法 $\mathcal{A}$ 在确定不在训练集中的点 $x_i$ 的标签时，无法比抛硬币更好

• 假设：

  • 不失一般性情况下，算法 $\mathcal{A}$ 在 $x_0$ 上没有错误

• 样本表示：

  • 用 $\bar{S}$ 表示元素落在 $\{x_1,\dots ,x_{d-1}\}$ 中的集合
  • 令 $\mathcal{S}$ 为样本 $S$ 的集合，大小为 $m$，
    • 使得 $|\bar{S}|\le \frac{d-1}{2}$

• 固定一个样本 $S\in \mathcal{S}$

  • 考虑所有标记 $f:\overline{\mathcal{X}}\to \{0,1\}$ 的均匀分布 $\mathcal{U}$
  • 这些标记都在 $\mathcal{H}$ 中

• 以下下界成立：

$$\begin{array}{rl}& \underset{f\sim \mathcal{U}}{\mathbb{E}}\left[R_{\mathcal{D}}\left(h_S,f\right)\right]\\ =& \sum _f\sum _{x\in \overline{\mathcal{X}}}{1}_{h_S\left(x\right)\ne f\left(x\right)}\mathbb{P}\left[x\right]\mathbb{P}\left[f\right]\\ \ge & \sum _f\sum _{x\notin \bar{S}}{1}_{h_S\left(x\right)\ne f\left(x\right)}\mathbb{P}\left[x\right]\mathbb{P}\left[f\right]\\ =& \sum _{x\notin \bar{S}}\left(\sum _f{1}_{h_S\left(x\right)\ne f\left(x\right)}\mathbb{P}\left[f\right]\right)\mathbb{P}\left[x\right]\\ =& \frac{1}{2}\sum _{x\notin \bar{S}}\mathbb{P}\left[x\right]\\ \ge & \frac{1}{2}\frac{d-1}{2}\frac{8ϵ}{d-1}\\ =& 2ϵ\end{array}\text{\hspace{1em}(3.33)}$$

• 第一个下界成立：

  • 仅考虑 $x\notin \bar{S}$ 而非所有 $x\in \overline{\mathcal{X}}$
  • 从求和中去除了非负项

• 重新排列项后，后续等式成立：

  • 因为对每个 $f$ 取均匀权重的期望
  • 由于 $\mathcal{H}$ 打碎了 $\overline{\mathcal{X}}$

• 最后一个下界成立：

  • 基于 $\mathcal{D}$ 和 $\bar{S}$ 的定义
  • 后者意味着 $|\overline{\mathcal{X}}-\bar{S}|\ge \frac{d-1}{2}$

• 由于 (3.33) 对于所有 $S\in \mathcal{S}$ 成立：

  • 它在所有 $S\in \mathcal{S}$ 的期望中也成立

• 表达式：

  • ${\mathbb{E}}_{S\in \mathcal{S}}\left[{\mathbb{E}}_{f\sim \mathcal{U}}\left[R_{\mathcal{D}}(h_S,f)\right]\right]\ge 2ϵ$

• 根据费比尼定理：

  • 期望可以交换 \underset{f \sim \mathcal{U}}{\mathbb{E}}\left\lbrack {\underset{S \in \mathcal{S}}{\mathbb{E}}\left\lbrack {{R}_{\mathcal{D}}\left( {{h}_{S},f}\right) }\right\rbrack }\right\rbrack \geq {2\epsilon } \tag{3.34}

• 可见 ${\mathbb{E}}_{S\in \mathcal{S}}\left[R_{\mathcal{D}}(h_S,f_0)\right]\ge 2ϵ$

  • 对于至少一个标记 $f_0\in \mathcal{H}$ 成立

• 期望分解：

  • 将期望分解为两部分
  • 使用不等式：
    • $R_{\mathcal{D}}(h_S,f_0)\le {\mathbb{P}}_{\mathcal{D}}\left[\overline{\mathcal{X}}-\{x_0\}\right]$

• 得到：

$$\begin{array}{rl}& \underset{S\in \mathcal{S}}{\mathbb{E}}\left[R_{\mathcal{D}}(h_S,f_0)\right]\\ & =\sum _{S:R_{\mathcal{D}}(h_S,f_0)\ge ϵ}{R}_{\mathcal{D}}(h_S,f_0)\mathbb{P}\left[R_{\mathcal{D}}(h_S,f_0)\right]\\ & +\sum _{S:R_{\mathcal{D}}(h_S,f_0)<ϵ}{R}_{\mathcal{D}}(h_S,f_0)\mathbb{P}\left[R_{\mathcal{D}}(h_S,f_0)\right]\\ & \le \underset{\mathcal{D}}{\mathbb{P}}\left[\overline{\mathcal{X}}-\{x_0\}\right]\underset{S\in \mathcal{S}}{\mathbb{P}}\left[R_{\mathcal{D}}(h_S,f_0)\ge ϵ\right]\\ & +ϵ\underset{S\in \mathcal{S}}{\mathbb{P}}\left[R_{\mathcal{D}}(h_S,f_0)<ϵ\right]\\ & \le 8ϵ\underset{S\in \mathcal{S}}{\mathbb{P}}\left[R_{\mathcal{D}}(h_S,f_0)\ge ϵ\right]\\ & +ϵ\left(1-\underset{S\in \mathcal{S}}{\mathbb{P}}\left[R_{\mathcal{D}}(h_S,f_0)\ge ϵ\right]\right).\end{array}$$

在 ${\mathbb{P}}_{S\in \mathcal{S}}\left[R_{\mathcal{D}}\left(h_S,f_0\right)\ge ϵ\right]$ 中，得到： \underset{S \in \mathcal{S}}{\mathbb{P}}\left\lbrack {{R}_{\mathcal{D}}\left( {{h}_{S},{f}_{0}}\right) \geq \epsilon }\right\rbrack \geq \frac{1}{7\epsilon }\left( {{2\epsilon } - \epsilon }\right) = \frac{1}{7}. \tag{3.35}

因此，所有样本 $S$（不一定在 $\mathcal{S}$ 中）的概率可以下界为： \underset{S}{\mathbb{P}}\left\lbrack {{R}_{\mathcal{D}}\left( {{h}_{S},{f}_{0}}\right) \geq \epsilon }\right\rbrack \geq \underset{S \in \mathcal{S}}{\mathbb{P}}\left\lbrack {{R}_{\mathcal{D}}\left( {{h}_{S},{f}_{0}}\right) \geq \epsilon }\right\rbrack \mathbb{P}\left\lbrack \mathcal{S}\right\rbrack \geq \frac{1}{7}\mathbb{P}\left\lbrack \mathcal{S}\right\rbrack . \tag{3.36}

• 这使我们能够找到 $\mathbb{P}[\mathcal{S}]$ 的下界
• 根据乘法切尔诺夫界限（定理 D.4）：
  • 对于任何 $\gamma >0$
  • 样本大小为 $m$ 时：
  • 抽取超过 $\frac{d-1}{2}$ 个点的概率满足 1 - \mathbb{P}\left\lbrack \mathcal{S}\right\rbrack = \mathbb{P}\left\lbrack {{S}_{m} \geq {8\epsilon m}\left( {1 + \gamma }\right) }\right\rbrack \leq {e}^{-{8\epsilon m}\frac{{\gamma }^{2}}{3}}. \tag{3.37}

因此，对于 $ϵ=\left(d-1\right)/\left(32m\right)$ 和 $\gamma =1$， \mathbb{P}\left\lbrack {{S}_{m} \geq \frac{d - 1}{2}}\right\rbrack \leq {e}^{-\left( {d - 1}\right) /{12}} \leq {e}^{-1/{12}} \leq 1 - {7\delta }, \tag{3.38} 对于 $\delta \le 0.01$，因此

• $\mathbb{P}\left[\mathcal{S}\right]\ge 7\delta$，

• ${\mathbb{P}}_S\left[R_{\mathcal{D}}\left(h_S,f_0\right)\ge ϵ\right]\ge \delta$。 \end{proof}

• 定理结果：

  • 对于任何算法 $\mathcal{A}$：
    • 存在一个关于 $\mathcal{X}$ 的 “糟糕” 分布和一个目标函数 $f$
    • 使得 $\mathcal{A}$ 返回的假设的错误率是某个常数倍的 $\frac{d}{m}$
    • 并且具有一定的概率

• 结论：

  • 进一步证明了 VC 维度在学习中的关键作用
  • 特别地：
    • 该结果暗示在可实现的情况下：
    • 当 VC 维度无限时，PAC 学习是不可能的

• 注意：

• 证明显示的结果比定理的陈述更强：

  • 分布 $\mathcal{D}$ 是独立于算法 $\mathcal{A}$ 选择的

• 下一个步骤：

  • 提出一个在非可实现情况下给出下界的定理
  • 证明将需要以下两个引理

引理 3.21

• 设 $\alpha$ 为均匀分布的随机变量，
  • 取值于 $\left\{{\alpha }_{-},{\alpha }_{+}\right\}$，
    • 其中 ${\alpha }_{-}=\frac{1}{2}-\frac{ϵ}{2}$ 和 ${\alpha }_{+}=\frac{1}{2}+\frac{ϵ}{2}$。
• 令 $S$ 为一个包含 $m\ge 1$ 个随机变量 $X_1,\dots ,X_m$ 的样本，
  • 这些随机变量取值于 $\{0,1\}$，
  • 并根据分布 ${\mathcal{D}}_{\alpha }$ 独立同分布地抽取，
• 定义为 ${\mathbb{P}}_{{\mathcal{D}}_{\alpha }}\left[X=1\right]=\alpha$
• 令 $h$ 为从 $X^m$ 到 $\left\{{\alpha }_{-},{\alpha }_{+}\right\}$ 的函数，则以下成立： \underset{\alpha }{\mathbb{E}}\left\lbrack {\underset{S \sim {\mathcal{D}}_{\alpha }^{m}}{\mathbb{P}}\left\lbrack {h\left( S\right) \neq \alpha }\right\rbrack }\right\rbrack \geq \Phi \left( {2\lceil m/2\rceil ,\epsilon }\right) , \tag{3.39} 这里 $\Phi \left(m,ϵ\right)=\frac{1}{4}\left(1-\sqrt{1-\exp \left(-\frac{m{ϵ}^2}{1-{ϵ}^2}\right)}\right)$ 对所有 $m$ 和 $ϵ$ 成立。

\begin{proof}

• 引理解释：
  • 通过一个实验进行解释
    • 涉及两枚硬币，偏差分别为 ${\alpha }_{-}$ 和 ${\alpha }_{+}$
  • 意义：
    • 对于基于从 ${\mathcal{D}}_{{\alpha }_{-}}$ 或 ${\mathcal{D}}_{{\alpha }_{+}}$ 抽取的样本 $S$ 的判别规则 $h(S)$
    • 要确定哪枚硬币被抛掷：
      • 样本大小 $m$ 必须至少为 $\Omega \left(\frac{1}{{ϵ}^2}\right)$
• 证明：
  • 留作练习（练习 D.3）

\end{proof}

我们将利用这样一个事实：

• 对于任意固定的 $ϵ$，函数 $m\mapsto \Phi \left(m,x\right)$ 是凸函数，这一点不难证明。

引理 3.22

• 设 $Z$ 是一个取值于 $\left[0,1\right]$ 的随机变量。
• 则对于任意 $\gamma \in [0,1)$，

\mathbb{P}\left\lbrack {z > \gamma }\right\rbrack \geq \frac{\mathbb{E}\left\lbrack Z\right\rbrack - \gamma }{1 - \gamma } > \mathbb{E}\left\lbrack Z\right\rbrack - \gamma \tag{3.40}

\begin{proof} 由于 $Z$ 取值于 $\left[0,1\right]$，

$$\begin{array}{rl}\mathbb{E}[Z]& =\sum _{z\le \gamma }\mathbb{P}[Z=z]z+\sum _{z>\gamma }\mathbb{P}[Z=z]z\\ & \le \sum _{z\le \gamma }\mathbb{P}[Z=z]\gamma +\sum _{z>\gamma }\mathbb{P}[Z=z]\\ & =\gamma \mathbb{P}[Z\le \gamma ]+\mathbb{P}[Z>\gamma ]\\ & =\gamma \left(1-\mathbb{P}[Z>\gamma ]\right)+\mathbb{P}[Z>\gamma ]\\ & =\gamma +(1-\gamma )\mathbb{P}[Z>\gamma ].\end{array}$$

得证 \end{proof}

定理 3.23（下界，非可实现情况）

• 假设集：
  • 设 $\mathcal{H}$ 为一个假设集
  • VC 维度为 $d>1$
• 结果：
• 对于任意 $m\ge 1$ 和任意学习算法 $\mathcal{A}$
• 存在一个分布 $\mathcal{D}$ 在 $\mathcal{X}\times \{0,1\}$ 上，使得：

\mathbb{P}_{S \sim \mathcal{D}^{m}}\left[ R_{\mathcal{D}}(h_{S}) - \inf_{h \in \mathcal{H}} R_{\mathcal{D}}(h) > \sqrt{\frac{d}{320m}} \right] \geq \frac{1}{64} \tag{3.41}$$ - 样本复杂度： - 对于任何学习算法： - 满足： $$m \geq \frac{d}{320 \epsilon^{2}} \tag{3.42}$$

\begin{proof}

• 定义：

  • 设 $\bar{x}=\{x_1,\dots ,x_d\}\subseteq x$
  • 为一个被 $\mathcal{H}$ 分割的集合

• 参数：

  • 对于任意 $\alpha \in [0,1]$
  • 以及任意向量 $\sigma =({\sigma }_1,\dots ,{\sigma }_d{)}^{\top }\in \{-1,+1{\}}^d$

• 分布定义：

  • 定义一个支撑集为 $\bar{x}\times \{0,1\}$ 的分布 ${\mathcal{D}}_{\sigma }$，定义如下：

\forall i \in \left\lbrack d\right\rbrack ,\;\underset{{\mathcal{D}}_{\mathbf{\sigma }}}{\mathbb{P}}\left\lbrack \left( {{x}_{i},1}\right) \right\rbrack = \frac{1}{d}\left( {\frac{1}{2} + \frac{{\sigma }_{i}\alpha }{2}}\right) . \tag{3.43}

• 标签分布：

  • 每个点 $x_i,i\in [d]$ 的标签遵循分布：
    \mathbb{P}{\mathcal{D}{\mathbf{\sigma}}}[\cdot \mid x_{i}]
  • 即一个偏置硬币的分布：
    • 偏置由 ${\sigma }_i$ 的符号和 $\alpha$ 的大小决定

• 学习算法要求：

  • 为了确定每个点 $x_i$ 的最可能标签
  • 需要估计：
    \mathbb{P}{\mathcal{D}{\mathbf{\sigma}}}[1 \mid x_{i}]
  • 其精度必须优于 $\alpha$

• 问题复杂度：

  • 为了使问题更加困难：
    • $\alpha$ 和 $\sigma$ 将根据算法来选择
    • 根据引理 3.21：
      • 每个点 $x_i$ 在训练样本中需要至少 $\Omega \left(\frac{1}{{\alpha }^2}\right)$ 个实例

• 贝叶斯分类器定义：

  • 贝叶斯分类器 $h_{{\mathcal{D}}_{\sigma }}^{\ast }$ 定义为：
    h_{\mathcal{D}{\sigma}}^{*}(x{i}) = \operatorname{argmax}{y \in { 0, 1 }} \mathbb{P}[y \mid x{i}] = 1_{\sigma_{i} > 0}
  • 适用范围：
    • 对于所有 $i\in [d]$
    • $h_{{\mathcal{D}}_{\sigma }}^{\ast }$ 在 $\mathcal{H}$ 中，因为 $\overline{\mathcal{X}}$ 被分割

• 对于所有 $h\in \mathcal{H}$：

$$\begin{array}{rl}& R_{{\mathcal{D}}_{\sigma }}\left(h\right)-R_{{\mathcal{D}}_{\sigma }}\left(h_{{\mathcal{D}}_{\sigma }}^{\ast }\right)\\ =& \frac{1}{d}\sum _{x\in \overline{\mathcal{X}}}\left(\frac{\alpha }{2}+\frac{\alpha }{2}\right)1_{h\left(x\right)\ne h_{{\mathcal{D}}_{\sigma }}^{\ast }\left(x\right)}\\ =& \frac{\alpha }{d}\sum _{x\in \overline{\mathcal{X}}}{1}_{h\left(x\right)\ne h_{{\mathcal{D}}_{\sigma }}^{\ast }\left(x\right)}.\end{array}\text{\hspace{1em}(3.44)}$$

• 假设定义：

  • 设 $h_S$ 为学习算法 $\mathcal{A}$ 在接收到根据 ${\mathcal{D}}_{\sigma }$ 抽取的标记样本 $S$ 后返回的假设

• 记号：

  • 用 $|S{|}_x$ 表示点 $x$ 在 $S$ 中的出现次数
  • 令 $\mathcal{U}$ 表示在 $\{-1,+1{\}}^d$ 上的均匀分布

• 结论：

  • 根据 (3.44)，以下成立：

$$\begin{array}{rl}& \underset{\begin{array}{c}\sigma \sim {\mathcal{U}}_m\\ S\sim {\mathcal{D}}_{\sigma }\end{array}}{\mathbb{E}}\left[\frac{1}{\alpha }\left(R_{{\mathcal{D}}_{\sigma }}(h_S)-R_{{\mathcal{D}}_{\sigma }}(h_{{\mathcal{D}}_{\sigma }}^{\ast })\right)\right]\\ & =\frac{1}{d}\sum _{x\in \overline{\mathcal{X}}}\underset{\begin{array}{c}\sigma \sim {\mathcal{U}}_m\\ S\sim {\mathcal{D}}_{\sigma }^m\end{array}}{\mathbb{E}}\left[1_{h_S(x)\ne h_{{\mathcal{D}}_{\sigma }}^{\ast }(x)}\right]\\ & =\frac{1}{d}\sum _{x\in \overline{\mathcal{X}}}\underset{\sigma \sim \mathcal{U}}{\mathbb{E}}\left[\underset{S\sim {\mathcal{D}}_{\sigma }^m}{\mathbb{P}}\left[h_S(x)\ne h_{{\mathcal{D}}_{\sigma }}^{\ast }(x)\right]\right]\\ & =\frac{1}{d}\sum _{x\in \overline{\mathcal{X}}}\sum _{n=0}^m\underset{\sigma \sim \mathcal{U}}{\mathbb{E}}\left[\underset{S\sim {\mathcal{D}}_{\sigma }^m}{\mathbb{P}}\left[h_S(x)\ne h_{{\mathcal{D}}_{\sigma }}^{\ast }(x)\mid {|S|}_x=n\right]\mathbb{P}\left[{|S|}_x=n\right]\right]\\ & \ge \frac{1}{d}\sum _{x\in \overline{\mathcal{X}}}\sum _{n=0}^m\Phi (n+1,\alpha )\mathbb{P}\left[{|S|}_x=n\right]\\ & \ge \frac{1}{d}\sum _{x\in \overline{\mathcal{X}}}\Phi \left(\frac{m}{d}+1,\alpha \right)\text{(convexity of }\Phi (\cdot ,\alpha )\text{ and Jensen’s inequality)}\\ & =\Phi \left(\frac{m}{d}+1,\alpha \right).\end{array}\text{\hspace{1em}(lemma 3.21)}$$

由于 $\sigma$ 的期望被 $\Phi \left(m/d+1,\alpha \right)$ 下界， 因此必定存在某个 $\sigma \in \{-1,+1{\}}^d$，使得

$$\underset{S\sim {\mathcal{D}}_{\sigma }^m}{\mathbb{E}}\left[\frac{1}{\alpha }\left[R_{{\mathcal{D}}_{\sigma }}\left(h_S\right)-R_{{\mathcal{D}}_{\sigma }}\left(h_{{\mathcal{D}}_{\sigma }}^{\ast }\right)\right]\right]>\Phi (m/d+1,\alpha )\text{\hspace{1em}(3.45)}$$

然后，根据引理 3.22，对于该 $\sigma$，对于任意 $\gamma \in \left[0,1\right]$， \underset{S \sim {\mathcal{D}}_{\sigma }^{m}}{\mathbb{P}}\left\lbrack {\frac{1}{\alpha }\left\lbrack {{R}_{{\mathcal{D}}_{\sigma }}\left( {h}_{S}\right) - {R}_{{\mathcal{D}}_{\sigma }}\left( {h}_{{\mathcal{D}}_{\sigma }}^{ * }\right) }\right\rbrack > {\gamma u}}\right\rbrack > \left( {1 - \gamma }\right) u, \tag{3.46} 其中 $u=\Phi \left(m/d+1,\alpha \right)$。

选择 $\delta$ 和 $ϵ$ 使得 $\delta \le \left(1-\gamma \right)u$ 且 $ϵ\le \gamma \alpha u$，可以得到 \underset{S \sim {\mathcal{D}}_{\sigma }^{m}}{\mathbb{P}}\left\lbrack {{R}_{{\mathcal{D}}_{\sigma }}\left( {h}_{S}\right) - {R}_{{\mathcal{D}}_{\sigma }}\left( {h}_{{\mathcal{D}}_{\sigma }}^{ * }\right) > \epsilon }\right\rbrack > \delta . \tag{3.47}

为了满足定义 $ϵ$ 和 $\delta$ 的不等式，令 $\gamma =1-8\delta$。 那么,

$$\begin{array}{rl}& \delta \le (1-\gamma )u\\ & \iff u\ge \frac{1}{8}\\ & \iff \frac{1}{4}\left(1-\sqrt{1-\exp \left(-\frac{(m/d+1){\alpha }^2}{1-{\alpha }^2}\right)}\right)\ge \frac{1}{8}\\ & \iff \frac{(m/d+1){\alpha }^2}{1-{\alpha }^2}\le \log \frac{4}{3}\\ & \iff \frac{m}{d}\le \left(\frac{1}{{\alpha }^2}-1\right)\log \frac{4}{3}-1.\end{array}\text{\hspace{1em}(3.48)(3.49)(3.50)(3.51)}$$

选择 $\alpha =\frac{8ϵ}{1-8\delta }$，可以得到 $ϵ=\frac{\gamma \alpha }{8}$，并且满足 \frac{m}{d} \leq \left( {\frac{{\left( 1 - 8\delta \right) }^{2}}{{64}{\epsilon }^{2}} - 1}\right) \log \frac{4}{3} - 1 \tag{3.52}

我们令 $f\left(1/{ϵ}^2\right)$ 表示右侧表达式，并且我们正在寻找一个足够条件的形式 $m/d\le \omega /{ϵ}^2$ 。由于 $ϵ\le 1/64$ ，为了确保 $\omega /{ϵ}^2\le f\left(1/{ϵ}^2\right)$，我们只需要施加条件：

$$\frac{\omega }{{\left(1/64\right)}^2}=f\left(\frac{1}{{\left(1/64\right)}^2}\right)$$

这个条件可以简化并确定 $\omega$ 的具体取值。

$$\begin{array}{rl}\omega & ={\left(7/64\right)}^2\log \left(4/3\right)-{\left(1/64\right)}^2\left(\log \left(4/3\right)+1\right)\\ & \approx .003127\\ & \ge 1/320=.003125.\end{array}$$

因此，${ϵ}^2\le \frac{1}{320\left(m/d\right)}$ 是确保这些不等式成立的充分条件。 \end{proof}

• 定理说明：

  • 在非可实现的情况下
  • 对于任何算法 $\mathcal{A}$
  • 存在一个“糟糕的”分布在 $X\times \{0,1\}$ 上
    • 使得算法 $\mathcal{A}$ 返回的假设的错误率是某个常数乘以 $\sqrt{\frac{d}{m}}$
    • 并且具有某个常数概率

• VC-维度的重要性：

  • VC-维度在这一广义的学习设置中作为一个关键量出现
  • 特别地，当 VC-维度为无限时
    • 不可知的 PAC 学习是不可能的

• 这进一步表明 VC-维度的限制在无论可实现还是不可实现的学习场景中，

  • 都是影响学习算法有效性的重要因素。