机器学习：VC维的概念和用途

统计学习理论之VC维究竟是什么 | TangShusen

机器学习|VC维的理解_我去喝咖啡了的博客-CSDN博客_vc维

一、提要

        VC维是机器学习的重要概念，它给机器学习的“可学习性”提供了理论基础。然而，在网上的博客中，多数将VC维解释的复杂抽象，看后似是而非。本文意在用浅显易懂的手段，将VC维的基本概念交待清楚，然后，再在高层次上介绍其用途。

二、VC维的概念

2.1 VC维的出处

        VC维（外文名Vapnik-Chervonenkis Dimension）的概念是为了研究学习过程一致收敛的速度和推广性（Generalization performance），由统计学理论定义的有关函数集学习性能的一个重要指标。

2.2 VC维的定义

        传统的定义是：对于一个有H个样本的数据集合，另有一个函数集，如果存在H个样本能够被函数集中的函数按所有可能的2的H次方种形式分开，则称函数集能够把H个样本打散；函数集的VC维就是它能打散的最大样本数目H。

以上是我抄来的较正确的定义，但是有几个方面没有交待清楚，我给补上：

1.  数据集合中，每个数据样本的属性维度d，必须是已知的。
2.  所谓【 H个样本能够被函数集中的函数按所有可能的2的H次方种形式分开】，是指用二分类方法，将每一个元素都可分出，或取出。
3.  H个样本可以任意给出，没有条件限制。
4. 所谓“打散”就是颗粒度小到不能再分。

2.3 举个平面上的VC维例子

对于平面（d=2）上的集合，内有元素H=3；分类类别为二：【-1，1】，试确定其VC维？

 将数据集，冠上二分类信息，按照可能性，可穷举出8种数据集的可能分布：

 看能否找出一组函数，将上边数据集“打散”？下面，我们用直线做为分类函数，将上述蓝点和绿点分离出来。

 通过上图，我们已经证明，通过8个直线函数，可以将的元素区分出来。说明平面上的VC维度大于等于3；

新出现的问题？平面上的VC维可不可以是4？

我们再次用图形证明。只要举出一个反例，证明直线不可以打散的情况就可以了（下图*）。

 因此，用直线函数做分类器，平面上的VC维只能是3，不能是4；

 注意：数据集退化，如果三个点共线，也不可以“打散”。我们这里不讨论这种情况。

2.4 VC维的和d的关系

        上面说，d=2的VC维是3；那么d=3对应的VC维是不是4呢？答案：是的，不过有个约束：线性空间内部。

三、VC维的进一步探讨

3.1 shatter概念

3.2 break point概念

3.3  与VC维相关的指标

1. VC维跟模型复杂度是正相关的，以至于很多人误解VC维就是模型复杂度，当然这么理解好像也不会有什么不好的后果。
2. 测试集的错误率一开始很高，随着VC维增大而减小，在dvc∗dvc∗ 达到最小值，然后开始增大。我们就称这个dvcdvc处为这个模型的VC维。
3. 训练集的错误率一直在减小。

3.4 是不是VC维越大越好？

        度量模型的学习能力的指标，一般来说，VC维越大，其学习能力越强。比如，常见的神经网络模型，一个更深参数量越多的模型的VC维一定大于更轻量的模型。当数据量不足的情况下，对于一个很大的模型，往往效果会很差，容易形成过拟合。目前很多基于深度学习的算法都面临一个VC维冗余的问题。

更重要的是，VC维的实践意义是给机器学习可学性提供了理论支撑。

1. 测试集合的loss是否和训练集合的loss接近？VC维越小，理论越接近。

2. 训练集合的loss是否足够小？VC维越大，loss理论越小。

一般工业实践中通过引入正则对模型复杂度(VC维)进行控制，平衡这两个问题的矛盾。

3.5 VC维理论的边缘化

说了这么多，其实我还想告诉你，虽然这个理论读起来很晦涩，但是实际情况是它目前是一个被边缘化的知识。理由根据VC维理论，神经网络的VC维巨大，学习是不可行的。但是实际情况，神经网络却在一些领域表现良好。这又是什么原因呢？可能有以下的解释。

• 数据量增多了
• 神经网络共享权值导致参数变少，导致VC维下降了
• 训练结束的时候，模型实际上对训练集还是欠拟合的

Whatever，VC维在神经网络中看似是失效了。各位同学们也不要高兴得太早，我们总是需要有一个理论来定量的计算学习的可行性。而不是像现如今的大部分研究一样，只有一个实验结果，而对方法的改进拿不出靠谱的评价标准。