2.4.1 确定性场景与随机场景

在监督学习的最一般场景中，

• 分布 $\mathcal{D}$ 定义在 $\mathcal{X}\times \mathcal{Y}$ 上，
• 训练数据是从 $\mathcal{D}$ 中独立同分布抽取的带标签样本 $S$：

$$S=\left(\left(x_1,y_1\right),\dots ,\left(x_m,y_m\right)\right).$$

• 学习问题是要找到一个假设 $h\in \mathcal{H}$ 具有小的泛化误差

$$R\left(h\right)=\underset{\left(x,y\right)\sim \mathcal{D}}{\mathbb{P}}\left[h\left(x\right)\ne y\right]=\underset{\left(x,y\right)\sim \mathcal{D}}{\mathbb{E}}\left[1_{h\left(x\right)\ne y}\right].$$

• 这种更一般的场景被称为随机场景。
• 在这个设置中，输出标签是输入的随机函数。

---

• 随机场景捕捉了许多现实世界中的问题，
  • 其中输入点的标签不是唯一的。
• 例如，如果我们试图根据由一个人的身高和体重组成的输入对预测性别，那么标签通常不会是唯一的。
  • 对于大多数对，男性和女性都是可能的性别。
  • 对于每个固定的对，都有一个标签为男性的概率分布。

PAC学习框架在这个设置中的自然扩展被称为 不可知PAC学习。

定义2.14（不可知PAC学习）

• 设 $\mathcal{H}$ 为一个假设集。
• $\mathcal{A}$ 是一个 不可知 PAC学习算法，如果存在一个多项式函数 $\mathrm{poly}\left(\cdot ,\cdot ,\cdot ,\cdot \right)$，
  • 使得对于
    • 任何 $ϵ>0$ 和 $\delta >0$，
    • 所有在 $\mathcal{X}\times \mathcal{Y}$ 上的分布 $\mathcal{D}$，
  • 以下对于任何样本大小 $m\ge \mathrm{poly}\left(1/ϵ,1/\delta ,n,\mathrm{size}\left(c\right)\right)$ 都成立： \underset{S \sim {\mathcal{D}}^{m}}{\mathbb{P}}\left\lbrack {R\left( {h}_{S}\right) - \mathop{\min }\limits_{{h \in \mathcal{H}}}R\left( h\right) \leq \epsilon }\right\rbrack \geq 1 - \delta . \tag{2.21}
• 如果 $\mathcal{A}$ 进一步在多项式时间 $\left(1/ϵ,1/\delta ,n\right)$ 内运行，那么它被称为一个 有效的 不可知PAC学习算法。

---

• 当一个点的标签可以由某个可测函数 $f:\mathcal{X}\to \mathcal{Y}$（以概率一确定）唯一确定时，这种情况被称为 确定性的 。
• 在这种情况下，只需要考虑输入空间上的一个分布 $\mathcal{D}$。
• 训练样本是
  • 通过根据 $\mathcal{D}$ 进行抽样 $\left(x_1,\dots ,x_m\right)$ 得到的，
  • 标签是通过 $f:y_i=f\left(x_i\right)$ 对于所有 $i\in \left[m\right]$ 获得的。
• 许多学习问题都可以在这个确定性场景中表述。

在前面的章节中，以及本书中介绍的大部分材料中，

• 为了简单起见，我们限制了讨论范围，只考虑了确定性场景。
• 然而，对于所有这些材料，读者应该能够轻松地将内容扩展到随机场景。