可学习的充要条件

可学习与有限性

复习一下,之前我们学过:

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

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

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

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

分割

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

定义 6.2H \mathcal{H}CC 上的限制) 设 H\mathcal{H} 为从 X\mathcal{X} 到 {0,1} 的函数类,设 C={c1,...cm}XC=\{c_1, ... c_m\} \subset \mathcal{X}H \mathcal{H}CC 上的限制 HC\mathcal{H}_C 是可以从 H\mathcal{H} 派生的从 CC 到 {0,1} 的函数集。即:

HC={(h(c1),,h(cm)):hH}\mathcal{H}_C = \{(h(c_1), \ldots, h(c_m)) : h \in \mathcal{H}\}

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

定义 6.3(分割): 如果H \mathcal{H}CC 上的限制是从 CC 到 {0,1} 的所有函数集,那么我们说 H\mathcal{H} 分割集合 CC。即 HC=2C\mathcal{H}_C = 2^{|C|}

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

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

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

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

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

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

VC 维度

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

因此,推论 6.4 的直接结果是:

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

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

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

要证明 VCdim(H)=d\text{VCdim}(\mathcal{H})=d,我们需要证明:

  1. 存在一个大小为 d 的集合 C,被 H\mathcal{H} 分割

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

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

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

  • 取集合 C={c1,c2},c1=1,c2=2C=\{c_1, c_2\},c_1=1,c_2=2。那么,H \mathcal{H} 分割集合 CC,因为能取到 (0,0),(0,1),(1,0),(1,1),因此 VCdim(H)2\text{VCdim}(\mathcal{H})\geq 2

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

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

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

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

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

PAC 学习的基本定理

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

  1. H\mathcal{H} 具有一致收敛性

  2. 任何 ERM 规则都是 H\mathcal{H} 的成功不可知 PAC 学习器

  3. H\mathcal{H} 是不可知 PAC 可学习的

  4. H\mathcal{H} 是 PAC 可学习的

  5. 任何 ERM 规则都是 H\mathcal{H} 的成功 PAC 学习器

  6. H\mathcal{H} 具有有限 VC 维度

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

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

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

最后更新于