VC維

瓦普尼克-澤范蘭傑斯維（Vapnik-Chervonenkis Dimension），簡稱VC維，由弗拉基米爾·瓦普尼克與亞歷克塞·澤范蘭傑斯提出。在VC理論中，VC維是對一個可學習分類函數空間的能力（複雜度，表示能力等）的衡量。它定義為算法能「打散」的點集的勢的最大值。 直觀地，一個分類模型的能力與其複雜程度相關。例如，考慮一個高次多項式的分類模型：若函數值大於0則分類為正，反之則分類為負。高次多項式能夠「擺動」的範圍很大，所以能夠很好地擬合給定的點集。當然因此，這樣的模型也很可能會在其他符合原點集趨勢的點集上分類錯誤。我們說這一多項式是高能力的。如果考慮一個簡單的線性分類模型，就不一定能夠很好地擬合給定的點集。

定義

集合族的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}$。

參見

• 紹爾-謝拉赫引理