1.3　假设空间和VC维

1.1节提到的Hoeffding不等式针对的是一个固定好的特征X到目标值y的函数，这个函数并不会对经验误差的大小作出保证。在固定好函数的情况下，单纯地增大数据量，虽然会缓和过拟合，但会带来欠拟合。

从特征X空间到目标y空间的一个映射h，如果对任何样本都有f（X）=y，那么该映射就为目标映射。学习算法可以学习到的映射的集合叫作算法的假设空间（Hypothesis Space），目标映射不一定在假设空间中，即使在，也不意味着一定可以学习到该映射。我们通过数据来学习的过程，就是从假设空间的所有可能映射中挑选接近目标映射的过程。我们常使用最小化损失函数的方法来找到好的映射。

所以考虑到假设空间的影响，假设包含了H个可能映射，并且它们为目标映射的可能性相同，那么Hoeffding不等式可以被简单的修改为：

如果假设空间比较大，那么随着数据量的增多，经验误差和泛化误差小间隔的概率也不会大。更糟糕的是，很多算法的假设空间是无穷大，比如，线性回归或者分类算法给出的假设空间是无穷多个线性超平面，复杂度更高的多项式算法的假设空间也是无穷大，这使得Hoeffding不等式失去了意义。所以我们不再使用映射的绝对数量来描述假设空间的复杂度，而是使用VC维（Vapnik-Chervonenkis Dimension）。

VC维的本质是假设空间作用在数据集上，利用能打散（见定义1.2）的最大数据集的规模来定义假设空间的复杂度。VC维越大，则假设空间的复杂度也就越高，模型的容量也就越大。

定义1.2（打散shatter）　考虑有N个数据的二分类问题，如果假设空间中不同的映射可以将全部的数据赋予的可能标记数为2N，也就是说穷尽了所有的可能结果，此时，假设空间可以把数据集打散。

如图1.4所示，3个数据点分布在一个2维空间中，其任意的可能性都可以被一条直线准确地划分，如果再增加样本数，则可能存在有标记不能被一条直线划分，线性超平面的VC维就为3。事实上，在d维特征空间上，超平面的VC维是d+1，k近邻的VC维是无穷大（见第5章）。

图1.4　对于每个数据点都只有2种可能的标记，3个数据点的可能结果数就为23=8种