> For the complete documentation index, see [llms.txt](https://qmmms.gitbook.io/note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://qmmms.gitbook.io/note/machine_learning/qms_05_vcdimension.md).

# 可学习的充要条件

## 可学习与有限性

> 复习一下，之前我们学过：
>
> * 只要损失函数是有界的，那么具有一般损失函数的不可知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 规则失败，但其他学习规则可以实现可学习性