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

定义

编辑

集合族的VC维

编辑

给定一集合族 与一集合 ,定义其为如下的集合族:

 

 能打散 ,当且仅当 包含 的所有子集,即

 

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

分类模型的VC维

编辑

对一个参数记为 的分类模型 ,称模型 能够打散一点集 ,当且仅当对任意标签集 都存在参数 使得  上分类完全正确。

模型 的VC维定义为能被 打散的势最大的点集的势,或等价地,满足存在  使得 能打散 的最大的 

參見

编辑