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)$ 上分類完全正確。