如何理解VC dimension？

楼上的回答有一点不太正确，并不需要随意给出n个样本都可以正确分类。实际上，只要能找出某一种n样本，hypothesis class H 可以正确分类这个样本，那么我们就说VC 维度至少是n。直到我们确定任意的n+1样本都无法被正确归类，我们就得出结论VC维度是n。

实际上，如果hypothesis class H 是有限的，那么不用VC维度也可以得到一个对于generalization error的上界。但是对于无限的hypothesis class，我们用VC 维度来描述这个class的分类能力。可以想象，如果两个不一样的hypotheses，他们在某个样本空间上是无法被区分开，那么即使这两个hypotheses是不一样的，我们也并不需要去考虑他们的区别。换句话说，VC维度是一种更加精确的描述H能力的维度 （比起简单的数H有多少的hypotheses）。

VC维度是以Vapnik和Chervonenkis的名字缩写命名的。

VC维度描述的是一个模型的复杂程度。

对于一个二元分类器F，F的VC维度等于F能够以0误差训练的训练集样本的数量。换句说说，如果F的VC维数是n，那么随意给出n个样本点以及它们的标签，F总能以100%的正确率去学习这个训练集，也就是训练误差为0。

比如1-近邻算法的VC维度是无穷大，因为对于任何n，1-NN的训练误差总是0。