2.6 练习

2.1 PAC模型的二Oracle变体。

假设正例和反例现在分别来自两个独立的分布 ${\mathcal{D}}_{+}$ 和 ${\mathcal{D}}_{-}$ 。对于一个准确度 $\left(1-ϵ\right)$ ，学习算法必须找到一个假设 $h$ ，使得：

$$\underset{x\sim {\mathcal{D}}_{+}}{\mathbb{P}}\left[h\left(x\right)=0\right]\le ϵ\text{ and }\underset{x\sim {\mathcal{D}}_{-}}{\mathbb{P}}\left[h\left(x\right)=1\right]\le ϵ.\text{\hspace{1em}(2.25)}$$

图2.5

(a) Gertrude的区域 $r_1,r_2,r_3$ 。(b) 解题提示。

因此，假设必须在两个分布上都有很小的误差。令 $\mathcal{C}$ 为任意的概念类，$\mathcal{H}$ 为任意的假设空间。令 $h_0$ 和 $h_1$ 分别表示恒等于0和恒等于1的函数。证明 $\mathcal{C}$ 在标准的（单Oracle）PAC模型中使用 $\mathcal{H}$ 有效PAC可学习当且仅当它在二Oracle PAC模型中使用 $\mathcal{H}\cup \left\{h_0,h_1\right\}$ 有效PAC可学习。

2.2 超矩形的PAC学习。

在 ${\mathbb{R}}^n$ 中的一个与坐标轴对齐的超矩形是一个形式为 $\left[a_1,b_1\right]\times \dots \times \left[a_n,b_n\right]$ 的集合。 证明通过扩展 示例 2.4（学习轴对齐矩形）(learning axis-aligned rectangles) 中的证明，与坐标轴对齐的超矩形是PAC可学习的。

2.3 同心圆。

令 $x={\mathbb{R}}^2$ 并考虑形式为 $c=\left\{\left(x,y\right):x^2+y^2\le r^2\right\}$ 的概念集合，其中 $r$ 为某个实数。证明这个类可以从大小为 $m\ge \left(1/ϵ\right)\log \left(1/\delta \right)$ 的训练数据中 $\left(ϵ,\delta \right)$-PAC学习。

2.4 非同心圆。

设 $x={\mathbb{R}}^2$ 并考虑形式为 $c=\left\{x\in {\mathbb{R}}^2:\Vert \begin{array}{c}x-x_0\end{array}\Vert \le r\right\}$ 的概念集合，其中某点 $x_0\in {\mathbb{R}}^2$ 和实数 $r$ 。格特鲁德是一位有抱负的机器学习研究员，她试图证明这类概念可以通过样本复杂性 $m\ge$ $\left(3/ϵ\right)\log \left(3/\delta \right)$ 实现 $\left(ϵ,\delta \right)$ -PAC学习，但在证明中遇到了困难。她的想法是学习算法会选择与训练数据一致的最小圆。她在概念 $c$ 的边缘绘制了三个区域 $r_1,r_2,r_3$ ，每个区域的概率为 $ϵ/3$ （见图2.5(a)）。她想要证明如果泛化误差大于或等于 $ϵ$ ，那么训练数据必定遗漏了这些区域之一，因此这个事件发生的概率至多为 $\delta$ 。你能告诉格特鲁德她的方法是否有效吗？（提示：你可能会希望在解决方案中使用图2.5(b)）。

2.5 三角形。

设 $X={\mathbb{R}}^2$ 具有正交基 $\left({\mathbf{e}}_1,{\mathbf{e}}_2\right)$ ，并考虑由直角三角形 $ABC$ 内的面积定义的概念集合，该三角形的两边平行于坐标轴，$\overrightarrow{AB}/\parallel \overrightarrow{AB}\parallel ={\mathbf{e}}_1$ 和 $\overrightarrow{AC}/\parallel \overrightarrow{AC}\parallel ={\mathbf{e}}_2$ ，以及 $\parallel \overrightarrow{AB}\parallel /\parallel \overrightarrow{AC}\parallel =\alpha$ 对于某个正实数 $\alpha \in {\mathbb{R}}_{+}$ 。使用与本章中用于轴对齐矩形的类似方法，证明这个类别可以从大小为 $m\ge \left(3/ϵ\right)\log \left(3/\delta \right)$ 的训练数据中 $\left(ϵ,\delta \right)$ -PAC学习。（提示：你可能会考虑在解决方案中使用图2.6）。

图2.6

与坐标轴平行的直角三角形。

2.6 在噪声环境下的学习 - 矩形

在示例2.4中，我们展示了轴对齐矩形的概念类是PAC可学习的。现在考虑学习者接收的训练点受到以下噪声影响的情况：被标记为负的点不受噪声影响，但是一个正的训练点的标签以概率 $\eta \in \left(0,\frac{1}{2}\right)$ 随机翻转为负。学习者不知道噪声率 $\eta$ 的确切值，但是提供了一个上限 ${\eta }^{\prime }$ 给他，并带有 $\eta \le {\eta }^{\prime }<1/2$ 。证明返回包含正点最紧密矩形的算法在这种噪声下仍然可以PAC学习轴对齐矩形。为此，你可以按照以下步骤进行：

1. 使用示例2.4中的相同符号，假设 $\mathbb{P}\left[\mathrm{R}\right]>ϵ$ 。假设 $R\left({\mathrm{R}}^{\prime }\right)>ϵ$ 。给出 ${\mathrm{R}}^{\prime }$ 错过区域 $r_j,j\in \left[4\right]$ 的概率上限，用 $ϵ$ 和 ${\eta }^{\prime }$ 表示。
2. 使用这个结果给出 $\mathbb{P}\left[R\left({\mathrm{R}}^{\prime }\right)>ϵ\right]$ 的上限，用 $ϵ$ 和 ${\eta }^{\prime }$ 表示，并通过给出样本复杂度界限来得出结论。

2.7 在噪声环境下的学习 - 一般情况。

在这个问题中，我们将寻求比前一个问题更一般的结果。我们考虑一个有限假设集 $\mathcal{H}$ ，假设目标概念在 $\mathcal{H}$ 中，并采用以下噪声模型：学习者接收的训练点的标签以概率 $\eta \in \left(0,\frac{1}{2}\right)$ 随机改变。学习者不知道噪声率 $\eta$ 的确切值，但是提供了一个上限 ${\eta }^{\prime }$ 给他，并带有 $\eta \le {\eta }^{\prime }<1/2$ 。

(a) 对于任意 $h\in \mathcal{H}$ ，令 $d\left(h\right)$ 表示学习者收到的训练点的标签与 $h$ 给定的标签不一致的概率。令 $h^{\ast }$ 为目标假设，证明 $d\left(h^{\ast }\right)=\eta$ 。

(b) 更一般地，证明对于任意 $h\in \mathcal{H},d\left(h\right)=\eta +\left(1-2\eta \right)R\left(h\right)$ ，其中 $R\left(h\right)$ 表示 $h$ 的泛化误差。

(c) 在此及以下所有问题中固定 $ϵ>0$ 。使用前一个问题来证明如果 $R\left(h\right)>ϵ$ ，那么 $d\left(h\right)-d\left(h^{\ast }\right)\ge {ϵ}^{\prime }$ ，其中 ${ϵ}^{\prime }=ϵ\left(1-2{\eta }^{\prime }\right)$ 。

(d) 对于任意假设 $h\in \mathcal{H}$ 和大小为 $m$ 的样本 $S$ ，令 $\hat{d}\left(h\right)$ 表示 $S$ 中标签与 $h$ 给定的标签不一致的点的比例。我们将考虑算法 $L$ ，在接收到 $S$ 后返回具有最小不一致数的假设 $h_S$（因此 $\hat{d}\left(h_S\right)$ 是最小的）。为了证明 $L$ 的 PAC 学习，我们将证明对于任意 $h$ ，如果 $R\left(h\right)>ϵ$ ，那么以高概率 $\hat{d}\left(h\right)\ge \hat{d}\left(h^{\ast }\right)$ 。首先，证明对于任意 $\delta >0$ ，在至少 $1-\delta /2$ 的概率下，对于 $m\ge \frac{2}{{ϵ}^{\prime 2}}\log \frac{2}{\delta }$ ，以下成立：

$$\hat{d}\left(h^{\ast }\right)-d\left(h^{\ast }\right)\le {ϵ}^{\prime }/2$$

(e) 其次，证明对于任意 $\delta >0$ ，在至少 $1-\delta /2$ 的概率下，对于 $m\ge \frac{2}{{ϵ}^{\prime 2}}\left(\log \left|\mathcal{H}\right|+\log \frac{2}{\delta }\right)$ ，以下对于所有 $h\in \mathcal{H}$ 成立：

$$d\left(h\right)-\hat{d}\left(h\right)\le {ϵ}^{\prime }/2$$

(f) 最后，证明对于任意 $\delta >0$ ，在至少 $1-\delta$ 的概率下，对于 $m\ge$ $\frac{2}{{ϵ}^2{\left(1-2{\eta }^{\prime }\right)}^2}\left(\log \left|\mathcal{H}\right|+\log \frac{2}{\delta }\right)$ ，以下对于所有 $h\in \mathcal{H}$ 且 $R\left(h\right)>ϵ$ 成立：

$$\hat{d}\left(h\right)-\hat{d}\left(h^{\ast }\right)\ge 0$$

（提示：使用 $\hat{d}\left(h\right)-\hat{d}\left(h^{\ast }\right)=\left[\hat{d}\left(h\right)-d\left(h\right)\right]+\left[d\left(h\right)-d\left(h^{\ast }\right)\right]+\left[d\left(h^{\ast }\right)-\hat{d}\left(h^{\ast }\right)\right]$ 并利用前一个问题来为这三个项设定下界）。

2.8 学习区间。

为概念类 $\mathcal{C}$ ，即由闭区间 $\left[a,b\right]$ 组成的概念类，给出一个 PAC 学习算法，其中 $a,b\in \mathbb{R}$ 。

2.9 学习区间的并集。

为概念类 ${\mathcal{C}}_2$ ，即由两个闭区间的并集组成的概念类，给出一个 PAC 学习算法，即 $\left[a,b\right]\cup \left[c,d\right]$ ，其中 $a,b,c,d\in \mathbb{R}$ 。将你的结果扩展为推导出一个 PAC 学习算法，用于由 $p\ge 1$ 个闭区间组成的并集形成概念类 ${\mathcal{C}}_p$ ，因此 $\left[a_1,b_1\right]\cup \cdots \cup \left[a_p,b_p\right]$ ，其中 $a_k,b_k\in \mathbb{R}$ 对于 $k\in \left[p\right]$ 。你的算法的时间和样本复杂度作为 $p$ 的函数是什么？

2.10 一致性假设。

在本章中，我们证明了对于一个有限假设集 $\mathcal{H}$ ，一个一致性学习算法 $\mathcal{A}$ 是一个 PAC 学习算法。在这里，我们考虑一个相反的问题。设 $z$ 为一个有限的 $m$ 标记点集。假设你被给定了一个 PAC 学习算法 $\mathcal{A}$ 。证明你可以使用 $\mathcal{A}$ 和一个有限的训练样本 $S$ ，以高概率在多项式时间内找到一个与 $z$ 一致的假设 $h\in \mathcal{H}$。（提示：你可以选择一个适当分布 $\mathcal{D}$ 在 $z$ 上，并对 $R\left(h\right)$ 给出一个条件以使 $h$ 一致。）

2.11 参议院法律。

对于重要问题，总统 Mouth 依赖于专家的建议。他从 $\mathcal{H}=2,800$ 专家的集合中选出一个合适的顾问。

(a) 假设法律以随机方式独立且相同地根据某个分布 $\mathcal{D}$ 提出并由一群未知的参议员决定。假设总统Mouth能够从 $\mathcal{H}$ 中找到并选择一位在过去 $m=200$ 次法律投票中始终与多数人意见一致的专家参议员。请给出此类参议员错误预测未来法律全局投票的概率上界。在 $95\%$ 置信水平下，这个上界的值是多少？

(b) 现在假设总统Mouth能够从 $\mathcal{H}$ 中找到并选择一位在过去 $m=200$ 次法律投票中除 $m^{\prime }=20$ 次以外始终与多数人意见一致的专家参议员。新的上界值是多少？

2.12 贝叶斯界。

设 $\mathcal{H}$ 为一个可数的假设集，其中的函数将 $x$ 映射到 $\{0,1\}$，并设 $p$ 为定义在 $\mathcal{H}$ 上的一个概率测度。这个概率测度表示了假设类的先验概率，即特定假设被学习算法选中的概率。使用霍夫丁不等式证明，对于任何 $\delta >0$，以至少 $1-\delta$ 的概率，以下不等式成立：

$$\forall h\in \mathcal{H},R\left(h\right)\le {\hat{R}}_S\left(h\right)+\sqrt{\frac{\log \frac{1}{p\left(h\right)}+\log \frac{1}{\delta }}{2m}}.\text{\hspace{1em}(2.26)}$$

将这个结果与不一致情况下有限假设集给出的界进行比较（提示：你可以在霍夫丁不等式中使用 ${\delta }^{\prime }=p\left(h\right)\delta$ 作为置信参数）。

2.13 未知参数的学习。

在示例2.9中，我们展示了 $k$ -CNF 的概念类是PAC可学习的。然而，需要注意的是，学习算法将 $k$ 作为输入。当 $k$ 没有提供时，PAC学习是否仍然可能？更一般地，考虑一个概念类家族 ${\left\{{\mathcal{C}}_s\right\}}_s$ ，其中 ${\mathcal{C}}_s$ 是 $\mathcal{C}$ 中大小至多 $s$ 的概念集合。假设我们有一个PAC学习算法 $\mathcal{A}$ ，当给定 $s$ 时，可以用于学习任何 ${\mathcal{C}}_s$ 的概念类。

我们能否将 $\mathcal{A}$ 转换为不需要了解 $s$ 的PAC学习算法 $\mathcal{B}$？这是本问题的主要目标。

为此，我们首先引入一种以高概率测试假设 $h$ 的方法。固定 $ϵ>0,\delta >0$ ，$i\ge 1$ ，并定义样本大小 $n$ 为 $n=\frac{32}{ϵ}\left[i\log 2+\log \frac{2}{\delta }\right]$ 。假设我们根据某个未知的分布 $\mathcal{D}$ 抽取了一个大小为 $n$ 的独立同分布样本 $S$ 。如果假设 $h$ 在 $S$ 上最多犯 $3/4ϵ$ 个错误，则我们说该假设被接受；否则，被拒绝。因此，$h$ 被接受当且仅当 $\hat{R}\left(h\right)\le 3/4ϵ$ 。

(a) 假设 $R\left(h\right)\ge ϵ$ 。使用（乘法）切尔诺夫界来证明在这种情况下 ${\mathbb{P}}_{S\sim {\mathcal{D}}^n}\left[h\text{is accepted}\right]\le \frac{\delta }{2^{i+1}}$ 。

(b) 假设 $R\left(h\right)\le ϵ/2$ 。使用（乘法）切尔诺夫界来证明在这种情况下 ${\mathbb{P}}_{S\sim {\mathcal{D}}^n}\left[h\text{is rejected}\right]\le \frac{\delta }{2^{i+1}}$ 。

(c) 算法 $\mathcal{B}$ 定义如下：我们从 $i=1$ 开始，在每一轮 $i\ge 1$ 中，我们猜测参数大小 $s$ 为 $\tilde{s}=\lfloor 2^{\left(i-1\right)/\log \frac{2}{\delta }}\rfloor$ 。我们抽取一个大小为 $n$（这取决于 $i$）的样本 $S$ 来测试当用大小为 $S_{\mathcal{A}}\left(ϵ/2,1/2,\tilde{s}\right)$ 的样本训练时，由 $\mathcal{A}$ 返回的假设 $h_i$ ，即 $\mathcal{A}$ 对于所需精度 $ϵ/2$ 、置信度 $1/2$ 和大小 $\tilde{s}$ 的样本复杂性（在此处我们忽略每个示例表示的大小）。如果接受 $h_i$ ，算法停止并返回 $h_i$ ，否则它进入下一轮迭代。证明如果在迭代 $i$ 中，估计值 $\tilde{s}$ 大于或等于 $s$ ，那么 $\mathbb{P}[h_i$ 被接受 $]\ge 3/8$ 。

(d) 证明 $\mathcal{B}$ 在经过 $j=\lceil \log \frac{2}{\delta }/\log \frac{8}{5}\rceil$ 次迭代后不停止的概率最多为 $\delta /2$ 。

(e) 证明对于 $i\ge \lceil 1+\left({\log }_{2}s\right)\log \frac{2}{\delta }\rceil$ ，不等式 $\tilde{s}\ge s$ 成立。

(f) 证明在至少 $1-\delta$ 的概率下，算法 $\mathcal{B}$ 在最多 $j^{\prime }=\lceil 1+\left({\log }_{2}s\right)\log \frac{2}{\delta }\rceil +j$ 次迭代后停止，并返回一个误差不超过 $ϵ$ 的假设。

2.14

在这个练习中，我们将噪声的概念推广到任意损失函数 $L:\mathcal{Y}\times \mathcal{Y}\to {\mathbb{R}}_{+}$ 的情况。

1. 验证以下在点 $x\in \mathcal{X}$ 处噪声的定义：

$$\mathrm{noise}\left(x\right)=\underset{y^{\prime }\in \mathcal{Y}}{\min }\underset{y}{\mathbb{E}}\left[L\left(y,y^{\prime }\right)\mid x\right]$$

在确定性场景中，噪声 $\left(x\right)$ 的值是多少？这个定义是否与本章中对于二分类给出的定义相匹配？ 2. 证明平均噪声与贝叶斯误差（由可测函数实现的最小损失）相一致。