示例 2.4（学习轴对齐矩形）(learning axis-aligned rectangles)

考虑

• 实例集合是平面上的点， $\mathcal{X}={\mathbb{R}}^2$
• 概念类 $\mathcal{C}$ 是所有位于 ${\mathbb{R}}^2$ 中的轴对齐矩形的集合。
  • 每个概念 $c$ 是特定轴对齐矩形内部的点的集合。

---

• 学习问题包括使用标记的训练样本以小的误差确定目标轴对齐矩形。
• 我们将证明轴对齐矩形的概念类是 PAC 可学习的。

---

图 2.1. 目标概念 $\mathrm{R}$ 和可能的假设 ${\mathrm{R}}^{\prime }$。圆圈代表训练实例。一个蓝色圆圈是一个标记为 1 的点，因为它落在矩形 R 内。其他的为红色并标记为 0。

---

• $R$ 表示目标轴对齐矩形
• $R^{\prime }$ 表示一个假设。
• $R^{\prime }$ 的误差区域由以下两类区域组成 ^fig-2-1
  • $R$ 内但不在 $R^{\prime }$ 内的区域
    • 对应假阴性，即被 1 标记为 0 或负值的点，实际上是正的或标记为 1。
  • $R^{\prime }$ 内但不在 $R$ 内的区域
    • 对应假阳性，即被 正面标记的点实际上是负面标记的。

---

• 回忆 PAC学习的定义， 为了证明概念类是 PAC 可学习的，我们描述了一个简单的 PAC 学习算法 $\mathcal{A}$。
• 给定一个标记样本 $S$，算法包括返回包含标记为 1 的点的 最紧的 轴对齐矩形 ${\mathrm{R}}^{\prime }={\mathrm{R}}_{\mathrm{S}}$。
• ^fig-2-2 描述了算法返回的假设。
• 根据定义，${\mathrm{R}}_{\mathrm{S}}$ 不会产生任何假阳性，因为它的点必须包含在目标概念 $\mathrm{R}$ 中。
• 因此，${\mathrm{R}}_{\mathrm{S}}$ 的误差区域包含在 $\mathrm{R}$ 中。

---

图 2.2 算法返回的假设 ${\mathrm{R}}^{\prime }={\mathrm{R}}_{\mathrm{S}}$ 的说明。

---

• 令 $\mathrm{R}\in \mathcal{C}$ 为一个目标概念。
• 固定 $ϵ>0$ 。
• 令 $\mathbb{P}\left[\mathrm{R}\right]$ 表示由 $R$ 定义的区域的概率质量，
  • 即根据 $\mathcal{D}$ 随机抽取的点落在 $\mathrm{R}$ 内的概率。
• 由于我们的算法产生的错误只能是由于点落在 $\mathrm{R}$ 内，
  • 我们可以假设 $\mathbb{P}\left[\mathrm{R}\right]>ϵ$ ；
  • 否则，无论接收到什么样的训练样本 $S$ ，${\mathrm{R}}_{\mathrm{S}}$ 的错误小于或等于 $ϵ$ 。

---

• 由于 $\mathbb{P}\left[\mathrm{R}\right]>ϵ$ ，我们可以定义
  • 四个矩形区域 $r_1$，$r_2$，$r_3$， $r_4$
  • 每个区域的概率至少为 $ϵ/4$ 。
  • 这些区域可以通过
    • 从完整的矩形 $\mathrm{R}$ 开始，
    • 然后通过尽可能移动一边来减小大小，
    • 同时保持至少 $ϵ/4$ 的分布质量来构建。
  • ^fig-2-3 说明了这些区域的定义。

---

图 2.3 区域 $r_1,\dots ,r_4$ 的示例。

---

• 令 $l$， $r$， $b$ ，$t$ 为定义 $\mathrm{R}:\mathrm{R}=\left[l,r\right]\times \left[b,t\right]$ 的四个实数值。
  • 左边的矩形 $r_4$ 由 $r_4=\left[l,s_4\right]\times \left[b,t\right]$ 定义
    • $s_4=$ $\inf \{s:\mathbb{P}\left[\left[l,s\right]\times \left[b,t\right]\right]\ge ϵ/4\}$ 。
  • 从 $r_4$ 排除最右的边得到的区域 ${\bar{r}}_4=[l,s_4[\times \left[b,t\right]$
    • 概率 至多 为 $ϵ/4$
  • $r_1,r_2,r_3,{\bar{r}}_1,{\bar{r}}_2,{\bar{r}}_3$ 以类似的方式定义。

---

• 如果 ${\mathrm{R}}_{\mathrm{S}}$ 碰到这四个区域 $r_i,i\in \left[4\right]$，
• 那么，因为它是一个矩形，它将在这些区域中的每一个都有一边（几何论证 ^fig-2-3）。
• 它的误差区域，即 $\mathrm{R}$ 中未被它覆盖的部分，
  • 包含在这些区域的并集中 ${\bar{r}}_i,i\in \left[4\right]$
  • 其概率质量不可能超过 $ϵ$ 。
• 通过逆否命题可得， 如果 $R\left({\mathrm{R}}_{\mathrm{S}}\right)>ϵ$ ， 那么 ${\mathrm{R}}_{\mathrm{S}}$ 必须至少错过 $r_i$ ，$i\in \left[4\right]$ 中的一个区域。

---

• ^fig-2-3 可见

$$\begin{array}{rlr}& \underset{S\sim {\mathcal{D}}^m}{\mathbb{P}}\left[R\left({\mathrm{R}}_{\mathrm{S}}\right)>ϵ\right]& \\ \le & \underset{S\sim {\mathcal{D}}^m}{\mathbb{P}}\left[{\cup }_{i=1}^4\left\{{\mathrm{R}}_{\mathrm{S}}\cap r_i=\varnothing \right\}\right]& \\ \le & \sum _{i=1}^4\underset{S\sim {\mathcal{D}}^m}{\mathbb{P}}\left[\left\{{\mathrm{R}}_{\mathrm{S}}\cap r_i=\varnothing \right\}\right]& \\ \le & 4{\left(1-ϵ/4\right)}^m& \left(\mathbb{P}\left[r_i\right]\ge ϵ/4\right)\\ \le & 4\exp \left(-mϵ/4\right)& \text{(2.5)}\end{array}$$

• 最后一步，我们使用了对于所有 $1-x\le e^{-x}$ 都成立的广义不等式 $x\in \mathbb{R}$ 。

---

• 对于任何 $\delta >0$ ，为了确保 ${\mathbb{P}}_{S\sim {\mathcal{D}}^m}\left[R\left({\mathrm{R}}_{\mathrm{S}}\right)>ϵ\right]\le \delta$ ，我们可以施加

$$\begin{array}{rlr}& 4\exp \left(-ϵm/4\right)\le \delta & \\ \iff & m\ge \frac{4}{ϵ}\log \frac{4}{\delta }.& \text{(2.6)}\end{array}$$

---

• 对于任何 $ϵ>0$ 和 $\delta >0$ ，
  • 如果样本大小 $m$ 大于 $\frac{4}{ϵ}\log \frac{4}{\delta }$ ，
  • 那么 ${\mathbb{P}}_{S\sim {\mathcal{D}}^m}\left[R\left({\mathrm{R}}_{\mathrm{S}}\right)>ϵ\right]\le \delta$ 。
• 表示 ${\mathbb{R}}^2$ 中的点以及与坐标轴平行的矩形的计算成本是常数，
  • 后者可以通过它们的四个角来定义。
• 这证明了
  • 与坐标轴平行的矩形的概念类是PAC可学习的，
  • PAC学习与坐标轴平行的矩形的样本复杂度在 $O\left(\frac{1}{ϵ}\log \frac{1}{\delta }\right)$ 内。

---

Remark

• 我们将在本书中经常看到，表示样本复杂度结果（如 (2.6) ）的一种等价方式，是给出一个泛化边界。
• 泛化边界表明，在至少 $1-\delta$ 的概率下，算法错误 $ϵ$ 被某个依赖于样本大小 $m$ 和 $\delta$ 的量所上界。
• 为了得到这个结果，只需将 $\delta$ 设置为（2.5）中导出的上界，即 $\delta =4\exp \left(-mϵ/4\right)$ 并求解 $ϵ$ 。
• 这表明在至少 $1-\delta$ 的概率下，算法的错误被如下界定：R\left( {\mathrm{R}}_{\mathrm{S}}\right) \leq \frac{4}{m}\log \frac{4}{\delta} \tag{2.7}

---

Question

对于这个例子，可以考虑其他PAC学习算法。

• 一个替代方案是返回不包含负点的最大轴对齐矩形。
• 刚刚为最紧密轴对齐矩形提出的PAC学习证明可以很容易地适应于其他此类算法的分析。

---

• 在此例中考虑的假设集 $\mathcal{H}$ 与概念类 $\mathcal{C}$ 相重合，且其数量是无限的。
  • 尽管如此，问题还是允许有一个简单的PAC学习证明。
• 那么我们可能会问，是否可以将类似的证明轻易应用于其他类似的概念类。
  • 这并不简单，因为证明中使用的特定几何论证是关键。
  • 将证明扩展到其他概念类，如非同心圆的概念类（见 2.4 非同心圆。），并不平凡。
  • 因此，我们需要一种更一般的证明技术和更一般的结果。
• 接下来的两个部分在有限假设集的情况下为我们提供了这样的工具。

---

Homework

2.2 超矩形的PAC学习。