因为研究涉及到过拟合（overfitting），了解到VC维这个概念。VC维已经不是一个新鲜事物了，机器学习教材里面把他列为“进阶知识”。关于VC维介绍普遍比较晦涩难懂，我觉得也没必要用数学语言来定量了解这个概念，抽象的理解VC维的物理意义我觉得就够用了。毕竟据说VC维由于没办法很好的解释深度学习，已经是一个比较边缘化的知识了。

定义

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

简单来说，VC维是用来衡量研究对象（数据集与学习模型）可学习性的指标。

如何理解可学习性？

对于机器学习（数据驱动的学习），首先我们要知道他的要素：训练集，测试集和学习算法。

  1. 对于训练集来说，训练集要足够大，才能使结果收敛。
  2. 对于测试集来说，测试集要有足够的代表性，不能偏差太大。
  3. 对于学习算法来说，要足够复杂，以表达特征（X值）与学习目标（y值）之间的逻辑关系。

可学习的条件

台大教授林轩田把他归纳成两点：

  1. 我们能否使测试集的误差与训练集足够接近？
  2. 我们能否使训练集上的误差足够小？

笔者认为，前者可能更加好懂，但不是那么严谨吧。在上一篇博客中，那个关于水环境的例子。例子中我们认为数据条数太少，结果无法收敛，也就是说不符合训练集上误差足够小这一条。

模型复杂度与拟合的关系
另外模型过于复杂或者过于简单，也会分别导致不符合条件1，2的情况。这也就是所谓的过拟合与欠拟合，网上的介绍很多，具体不在这里展开了。

从这里我们可以尝试得出一个结论：模型的可学习型，只与数据量与模型复杂度有关。与具体的研究对象，输入数据（X）的分布都无关。

回到VC维

从上面的推论，我们知道了可学习性与数据量和模型的复杂度有关。但只是泛泛但知道了，如何定量的计算和表达这种关系就需要引入VC维但概念了。网上关于VC维的介绍非常晦涩难懂，我们直接跳过公式先来看结论。详细请看：VC维的来龙去脉

VC维

在这张图里，纵轴是错误率（1-精度），横轴是VC维，out-of-sample指的是测试集错误率，越小越好。in-sample-error指的是训练集错误率。

我们可以看出：

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

我们来看一下VC维的定义：

一个假设空间H的VC dimension，是这个H最多能够shatter掉的点的数量，记为dvc(H)。

  1. 假设空间可以看作模型的复杂度。
  2. shatter翻译成打散，指的是不管数据的分布如何，H都要把它区分开。
  3. “这个H最多能够shatter掉的点的数指的是无论数据的分布如何”，这句话翻译成人话是，不管数据是怎样分布的，H最多能区分多少个数据。我们可以想像，越是复杂的H能够区分的数据点就越多，VC维也就越大。

这个概念真是看的人头皮发麻，结合公式口感更佳，我们其实不妨就可以把VC维理解成模型复杂度没有关系。

火光摇曳提到：

根据前面的推导，我们知道VC维的大小：与学习算法A无关，与输入变量X的分布也无关，与我们求解的目标函数f 无关。它只与模型和假设空间有关。

我们不管他说了什么，他这句话应该跟我前面尝试总结出的：“模型的可学习性，只与数据量与模型复杂度有关。”是等价的。

VC维理论的边缘化

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

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

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

我在这里抛砖引玉，希望各位同学们能戒骄戒躁，在理论建设的大楼上添砖加瓦。

参考文献