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$。

參見

• 紹爾-謝拉赫引理