VC维

瓦普尼克-契尔沃年基斯维（Vapnik-Chervonenkis Dimension），简称VC维，由弗拉基米尔·瓦普尼克与阿列克谢·契尔沃年基斯提出。在VC理论中，VC维是对一个可学习分类函数空间的能力（复杂度，表示能力等）的衡量。它定义为算法能“打散”的点集的势的最大值。 直观地，一个分类模型的能力与其复杂程度相关。例如，考虑一个高次多项式的分类模型：若函数值大于0则分类为正，反之则分类为负。高次多项式能够“摆动”的范围很大，所以能够很好地拟合给定的点集。当然因此，这样的模型也很可能会在其他符合原点集趋势的点集上分类错误。我们说这一多项式是高能力的。如果考虑一个简单的线性分类模型，就不一定能够很好地拟合给定的点集。

定义

集合族的VC维

给定一集合族$H$与一集合$C$，定义其交为如下的集合族：

$H\cap C:=\{h\cap C\vert h\in H\}$

称$H$能打散$C$，当且仅当$H\cap C$包含$C$的所有子集，即

$\vert H\cap C\vert =2^{\vert C\vert }$

$H$的VC维定义为能被$H$打散的势最大的集合的势。

分类模型的VC维

对一个参数记为$\theta$的分类模型$f$，称模型$f$能够打散一点集$X=\{x_{1},x_{2},\cdots ,x_{n}\}$，当且仅当对任意标签集$Y\in \{-1,+1\}^{n}$都存在参数$\theta ^{*}$使得$f_{\theta ^{*}}$在$(X,Y)$上分类完全正确。

模型$f$的VC维定义为能被$f$打散的势最大的点集的势，或等价地，满足存在$X$，$\vert X\vert =D$使得$f$能打散$X$的最大的$D$。

参见

• 绍尔-谢拉赫引理