VC維
瓦普尼克-澤范蘭傑斯維（Vapnik-Chervonenkis Dimension），簡稱VC維，由弗拉基米爾·瓦普尼克與亞歷克塞·澤范蘭傑斯提出。在VC理論中，VC維是對一個可學習分類函數空間的能力（複雜度，表示能力等）的衡量。它定義為算法能「打散」的點集的勢的最大值。 直觀地，一個分類模型的能力與其複雜程度相關。例如，考慮一個高次多項式的分類模型：若函數值大於0則分類為正，反之則分類為負。高次多項式能夠「擺動」的範圍很大，所以能夠很好地擬合給定的點集。當然因此，這樣的模型也很可能會在其他符合原點集趨勢的點集上分類錯誤。我們說這一多項式是高能力的。如果考慮一個簡單的線性分類模型，就不一定能夠很好地擬合給定的點集。
定義[編輯]
集合族的VC維[編輯]
給定一集合族<math>H</math>與一集合<math>C</math>，定義其交為如下的集合族：
<math>H\cap C:=\{h\cap C\vert h\in H\}</math>
稱<math>H</math>能打散<math>C</math>，若且唯若<math>H\cap C</math>包含<math>C</math>的所有子集，即
<math>\vert H\cap C\vert=2^{\vert C\vert}</math>
<math>H</math>的VC維定義為能被<math>H</math>打散的勢最大的集合的勢。
分類模型的VC維[編輯]
對一個參數記為<math>\theta</math>的分類模型<math>f</math>，稱模型<math>f</math>能夠打散一點集<math>X=\{x_1,x_2,\cdots,x_n\}</math>，若且唯若對任意標籤集<math>Y\in\{-1,+1\}^n</math>都存在參數<math>\theta^*</math>使得<math>f_{\theta^*}</math>在<math>(X,Y)</math>上分類完全正確。
模型<math>f</math>的VC維定義為能被<math>f</math>打散的勢最大的點集的勢，或等價地，滿足存在<math>X</math>，<math>\vert X\vert=D</math>使得<math>f</math>能打散<math>X</math>的最大的<math>D</math>。