VC维

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

给定一集合族${\displaystyle H}$为如下的集合族：

${\displaystyle H\cap <!--\; \cap \; -->C:=\{h\cap <!--\; \cap \; -->C|h\in <!--\; \in \; -->H\}}$

称${\displaystyle H}$能打散${\displaystyle C}$，当且仅当${\displaystyle H\cap <!--\; \cap \; -->C}$包含${\displaystyle C}$的所有子集，即

${\displaystyle |H\cap <!--\; \cap \; -->C|=2^{|C|}}$

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

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

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