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

传统的定义是：对一个指示函数集，如果存在H个样本能够被函数集中的函数按所有可能的2的H次方种形式分开，则称函数集能够把H个样本打散；函数集的VC维就是它能打散的最大样本数目H。若对任意数目的样本都有函数能将它们打散，则函数集的VC维是无穷大，有界实函数的VC维可以通过用一定的阈值将它转化成指示函数来定义。

VC维反映了函数集的学习能力，VC维越大则学习机器越复杂（容量越大），遗憾的是，尚没有通用的关于任意函数集VC维计算的理论，只对一些特殊的函数集知道其VC维。例如在N维空间中线性分类器和线性实函数的VC维是N+1。

如果一个假设空间存在突破点，则一定存在成长函数 被某个上限函数B(N,k)所约束，而上限函数等于一个组合的求和形式 ，易知该形式的最高次项是 。图左和右分别是以上限函数为上限的情况和以为 上限的情况。

可以得出：

若输入数据量N小于VC维，则有可能输入数据D会被完全的二分类。

如果输入数据量N（或者用k表示）大于VC维，则有k一定是假设空间H的突破点。

在N≥2， 时，可得：

一个有限的VC维总是能够保证寻找到的近似假设g是泛化的，即近似假设g满足 。没有必要知道具体的VC维的值，只需要知道它是有限的就可以得出这一结论。

同时这一结论与下述部分没有关系：1.使用的算法，即使使用某种算法使得 很大，也依然能满足上述的性质；2.输入数据的分布P；3.未知的目标函数f。

即VC维可应对任意的假设空间，任意的数据分布情况，任意的目标函数。满足这一性质可以得到如图2所示的流程图，其中灰色的部分表示上述几个不会影响 这一结果的部分：

以下两个条件保证了2维线性可分的数据是可以学习的：

1.线性可分的数据通过PLA算法运行足够长的时间（T步骤足够大），则会找出一条可以正确分类的直线，使得样本中没有产生分错类的情况，即 ；

2.在训练样本和整个数据集都服从同一分布P的前提下，有VC限制保证了，在 且训练样本N足够大时， 。

由VC维的定义知：只要求出 是一个有限数，则可以使用VC限制来保证 。那么在维数大于二维时，感知器的dvc能否表示成一个有限数。已知，1维感知器的VC维： =2；2维感知器的VC维： =3。猜想，d维感知器的VC维： =d+1。

证明：1. ≥d+1

取出N=d+1个在 的样本点，得到了如下的可逆矩阵（满秩矩阵）：

对于任意的 ，我们需要找到一个向量 ，且 满足sign(X )=y。

因为y向量可以是任意一种形式的二分类，如果我们能够对任意一个y向量都能找到对应的 ，那么我们就可以得到所有的二分类，即实现完全二分类。令让X =y。同时因为X是可逆的，我们得到 =X−1y，因此我们可以解得 的值。

因此我们证明了 ≥d+1。

2. ≤d+1

对于任意d+2个样本点，X1,X2,…,Xd+1,Xd+2的维度均为d+1。那么当维度大于点的个数的时候，可以知道他们一定线性相关，即，其中不是所有的都为0（因为任意xj的第一维都是1，所以权重不可能全是0）。

构造一组，且对于Xj，让yj=−1，其余权重为零的Xi对应的yi可以任意取值。

令，那么对于每一个非零的ai，可以得到和(ai)的符号是相同的，即，。

因此（因为ai=0时，累加无效），同时可得>0。则可以得到

假设不成立，因此在任何d+2个输入数据集中必然都存在不能满足的二分类，即。

证明了。

如果从假设空间的数量|H|角度上描述，则自由度是无限大的；但是从感知器在二元分类上这一限制条件入手，则可以使用VC维作为自由度的衡量。

VC维和假设空间参数之间的关系：

当dvc=1时，假设空间有1个参数，即阈值。

当dvc=2时，假设空间有2个参数，即左右边界点。因此在大部分情况下，dvc大致等于假设空间参数的个数。

将一个1D的感知器输出连接到下一个1D感知器的输入，如下图3所示，这样就得到了8个参数，然而它的自由度并没有增加。根据dvc，我们可以得出只需要一个感知器就足够的结论。