VC维

集合族的VC维

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

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

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

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

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

分类模型的VC维

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

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

• 绍尔-谢拉赫引理