可学习的充要条件

可学习与有限性

复习一下，之前我们学过：

• 只要损失函数是有界的，那么具有一般损失函数的不可知PAC模型中的任何有限类都是可学习的。

• 假设类的样本复杂度上界由其大小的对数给出。

有限是可学习的充分条件，但是它是必要条件吗？换句话说，有界类是可学习的，那么无界类呢？事实上，不是必要条件，我们首先给出一个无限大小假设类的简单例子，该类是可学习的。

设 $\mathcal{H}$ 为实数上的阈值函数类，即 $\mathcal{H} = \{ h_a:a \in \mathbb{R}\}$ ，其中 $h_a : \mathbb{R} \to \{0, 1\}$ 是一个函数，使得 $h_a(x) = \mathbb{1}_{[x < a]}$ 。显然，$\mathcal{H}$ 是无限的。但是经过证明（证明略），可以得到结论：使用 ERM 规则，这个 $\mathcal{H}$ 是 PAC 可学习的，其样本复杂度 $m_{\mathcal{H}}(\epsilon, \delta) \leq \left\lceil \log(2/\delta)/\epsilon\right\rceil$

分割

事实上，一种称为假设类的 VC 维度的性质，是充要条件。为了引出 VC 维度，我们先看两个概念。

定义 6.2（$\mathcal{H}$ 在 $C$ 上的限制） 设 $\mathcal{H}$ 为从 $\mathcal{X}$ 到 {0,1} 的函数类，设 $C=\{c_1, ... c_m\} \subset \mathcal{X}$。$\mathcal{H}$ 在 $C$ 上的限制 $\mathcal{H}_C$ 是可以从 $\mathcal{H}$ 派生的从 $C$ 到 {0,1} 的函数集。即：

$$\mathcal{H}_C = \{(h(c_1), \ldots, h(c_m)) : h \in \mathcal{H}\}$$

其中我们将每个从 $C$ 到 {0,1} 的函数表示为 $\{0,1\}^{|C|}$ 中的一个向量

定义 6.3（分割）： 如果$\mathcal{H}$ 在 $C$ 上的限制是从 $C$ 到 {0,1} 的所有函数集，那么我们说 $\mathcal{H}$ 分割集合 $C$。即 $\mathcal{H}_C = 2^{|C|}$

例子：令 $\mathcal{H}$ 为实数上的阈值函数（类似阶梯函数，但只有一个阶梯）类。取集合 $C=\{c_1\}$。如果 $a=c_1+1$ 有 $h_a(c_1)=1$， $a=c_1-1$ 有 $h_a(c_1)=0$，那么，$\mathcal{H}_C$ 是从 $C$ 到 {0,1} 的所有函数集 {(0), (1)}， $\mathcal{H}$ 分割集合 $C$

那么取集合 $C=\{c_1, c_2\}$ （其中$c_1< c_2$）呢？所有可能标记组合为 (0,0),(0,1),(1,0),(1,1)，但是如果 $h(c_1)=0$，那么由于阈值函数性质，$h(c_2)=0$ 也必须是 0，因此，$\mathcal{H}$ 不能实现所有组合。因此，集合 $C$ 不被 $\mathcal{H}$ 分割

回顾无免费午餐定理，当某些集合 $C$ 被 $\mathcal{H}$ 分割时，对手（指找到一个 $\mathcal{H}$ 失败但有其他算法成功的方法）不受 $\mathcal{H}$ 的限制，因为可以基于从 $C$ 到 {0,1} 的任何目标函数构造一个分布，同时保持可实现性假设：

推论 6.4 ： 设 $\mathcal{H}$ 为从 $\mathcal{X}$ 到 {0,1} 的函数类，令 $m$ 为训练集大小。假设存在大小为 $2m$ 的集合 $C \subset \mathcal{X}$，被 $\mathcal{H}$ 分割。那么，对于任何学习算法 $A$ ，存在一个$\mathcal{X}$ 到 {0,1} 的分布 $\mathcal{D}$ ，和一个预测函数 $h\in\mathcal{H}$，使得 $L_{\mathcal{D}}(h)=0$，但至少有1/7的概率$S\sim\mathcal{D}^m$，使得 $L_\mathcal{D}(A(S)) \geq 1/8$

推论 6.4 告诉我们，如果 $\mathcal{H}$ 分割了大小为 $2m$ 的集合 $C$，那么我们无法通过 $m$ 个样本学习 $\mathcal{H}$ （这和无免费午餐定理很像），因为这些实例的标签不会提供有关 $C$ 其余实例标签的信息，而由于 $\mathcal{H}$ 包含的可能太大（以致于能分割 $C$），无论剩下一半的标签是咋样的，都可以由 $\mathcal{H}$ 中的某个假设解释

类似我想搜选择题的答案，搜题软件告诉我说：A、B、C、D 四个选项的可能性都是 25%

VC 维度

定义 6.5（VC 维度）： 假设类 $\mathcal{H}$ 的 VC 维度，记作 $\text{VCdim}(\mathcal{H})$，是可以被 $\mathcal{H}$ 分割的集合 $C \subset \mathcal{X}$ 的最大大小。如果 $\mathcal{H}$ 可以分割任意大的集合，我们称 $\mathcal{H}$ 具有无限 VC 维度。

因此，推论 6.4 的直接结果是：

定理 6.6 ：设 $\mathcal{H}$ 是一个具有无限 VC 维度的类。那么，$\mathcal{H}$ 不是 PAC 可学习的。

6.6 的证明 由于 $\mathcal{H}$ 具有无限 VC 维度，对于任何训练集大小 $m$，存在一个大小为$2m$ 的被分割集合，因此根据推论 6.4，得出该结论。

事实上，在本章后面将看到，定理6.6的反面也成立，即有限 VC 维度保证可学习性，

要证明 $\text{VCdim}(\mathcal{H})=d$，我们需要证明：

1. 存在一个大小为 d 的集合 C，被 $\mathcal{H}$ 分割
2. 每个大小为 d+1 的集合 C 都不被 $\mathcal{H}$ 分割

例如上面提到的，阈值函数类，存在大小为1的集合 C，被 $\mathcal{H}$ 分割，每个大小为 2 的集合 C 都不被 $\mathcal{H}$ 分割，那么它的 $\text{VCdim}(\mathcal{H})=1$

再来一个例子，设 $\mathcal{H}$ 为实数上的区间类，即 $\mathcal{H}=\{h_{a,b}:a,b\in \mathbb{R},a<b\}$，其中 $h_{a,b}(x) = \mathbb{1}_{x \in (a,b)}$

• 取集合 $C=\{c_1, c_2\},c_1=1,c_2=2$。那么，$\mathcal{H}$ 分割集合 $C$，因为能取到 (0,0),(0,1),(1,0),(1,1)，因此 $\text{VCdim}(\mathcal{H})\geq 2$
• 现在取任意集合 $C=\{c_1, c_2, c_3\}$ 并假设 $c_1< c_2<c_3$。那么，(1,0,1) 不能通过区间获得，因此 $\mathcal{H}$ 不分割集合 $C$ ，$\text{VCdim}(\mathcal{H}) < 3$

因此我们得出结论 $\text{VCdim}(\mathcal{H})=2$

再来一个例子，$\mathcal{H} = \{h_\theta : \theta \in \mathbb{R}\}$, $h_\theta(x) = \lceil 0.5 \sin(\theta x)\rceil$，可以证明 $\text{VCdim}(\mathcal{H})= \infty$

设 $\mathcal{H}$ 为有限类。那么显然，对于任意集合 C，我们有 $|\mathcal{H}_C| \leq |\mathcal{H}|$，因此，如果 $|\mathcal{H}| < 2^{|C|}$，C 不能被分割，这意味着$\text{VCdim}(\mathcal{H}) \leq \log_2(|\mathcal{H}|)$

对于阈值函数类，如果 $\mathcal{X}=\{1,2,...k\}$ ，那么 $\log_2(|\mathcal{H}|) = \log_2(k)$，而 $\text{VCdim}(\mathcal{H})=1$

PAC 学习的基本定理

定理 6.7（统计学习的基本定理）（证明略）：设 $\mathcal{H}$ 为从 $\mathcal{X}$ 到 {0,1} 的函数的假设类，并让损失函数为 0-1 损失。那么，以下条件是等价的：

1. $\mathcal{H}$ 具有一致收敛性
2. 任何 ERM 规则都是 $\mathcal{H}$ 的成功不可知 PAC 学习器
3. $\mathcal{H}$ 是不可知 PAC 可学习的
4. $\mathcal{H}$ 是 PAC 可学习的
5. 任何 ERM 规则都是 $\mathcal{H}$ 的成功 PAC 学习器
6. $\mathcal{H}$ 具有有限 VC 维度

我们为二元分类任务陈述了基本定理。类似的结果适用于其他学习问题，例如绝对损失或平方损失的回归。然而，该定理并不适用于所有学习任务：

• 即使一致收敛性属性不成立，学习有时也是可能的

• 即使ERM 规则失败，但其他学习规则可以实现可学习性