VC次元（Vapnik–Chervonenkis次元）は、仮説空間（関数クラス）の表現能力、すなわちデータに対する分類の柔軟性を測る指標である。有限集合に対して取り得るラベル付けの多様性に基づいて定義され、統計的学習理論における汎化性能評価の中核概念である。
旧ソ連出身の2人の統計学者、ウラジミール・ヴァプニク（Vladimir Vapnik）とアレクセイ・チェルボネンキス（Alexey Chervonenkis）はは1960年代後半から共同研究を始め、1968年に発表した論文や1971年の主要な論文（ロシア語版）において、現在のVC次元の基礎となる理論を提唱。当初は確率論における「経験分布の真の分布への一様収束」を証明するための道具として開発されたが、後に機械学習における統計的学習理論（VC理論）の核心的な概念となった。
Vapnik, V. N., & Chervonenkis, A. Ya. (1971). On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16（2）, 264–280.
点集合 $S = \{\boldsymbol{x}_1, \dots, \boldsymbol{x}_n\} \subset \mathcal{X}$ に対し、仮説空間 $\mathcal{H}$ が $S$ をシャタリングするとは、任意のラベルベクトル $(y_1, \dots, y_n) \in \{0,1\}^n$ に対して、それを完全に再現する関数 $f \in \mathcal{H}$ が存在することをいう。
すなわち
\[\forall (y_1,\dots,y_n) \in \{0,1\}^n,\ \exists f \in \mathcal{H} \ \text{s.t.}\ f(\boldsymbol{x}_i) = y_i \ (i=1,\dots,n)\]が成立するとき、$\mathcal{H}$ は $S$ をシャタリングするという[$\mathcal{H}$ shatters $S$ .]。
例えば、平面上に3つの点があるとする。この3つの点に対して、どのような「○」と「×」の組み合わせ（ラベル付け）を割り当てても、1本の直線で「○」と「×」を完全に分けることができる場合、その直線モデルは3つの点を「シャタリングできる」と言う[Three points can be shattered by the linear model.]。
仮説空間 $\mathcal{H}$ のVC次元 $\mathrm{VC}(\mathcal{H})$ は、シャタリング可能な点集合の最大のサイズとして定義される：
\[\mathrm{VC}(\mathcal{H})=\max \left\{n \in \mathbb{N} \;\middle|\;\exists S \subset \mathcal{X},\ |S| = n,\ S \text{ is shattered by } \mathcal{H}\right\}\]そのような最大値が存在しない場合、VC次元は無限大と定義される。
なお、「シャタリング可能な点集合」とは、ある関数族（モデル）によって、その点集合のすべての「ラベルの組み合わせ（全パターン）」を完璧に分類できる状態にある集合のこと。そして、VC次元が「無限大」というのは、どれだけ多くの点（100万個でも1兆個でも）を持ってきても、そのモデルなら「どんなラベルの組み合わせでも完璧に分類できてしまう」という無敵の状態を指す。直感的に言うと、「そのモデルの表現力が全知全能すぎて、学習データに100%過学習（オーバーフィット）できてしまう」という意味。
実数直線上の閾値分類器
\[\mathcal{H}=\{ x \mapsto \mathbf{1}(x \geq t) \mid t \in \mathbb{R} \}\]に対しては、2点までは任意に分類できるが、3点は不可能であるため
\[\mathrm{VC}(\mathcal{H}) = 2\]である。
$\mathbb{R}^p$ における線形分類器
\[\mathcal{H}=\{ \boldsymbol{x} \mapsto \mathrm{sign}(\boldsymbol{w}^\top \boldsymbol{x} + b) \}\]のVC次元は
\[\mathrm{VC}(\mathcal{H}) = p + 1\]であることが知られている。
標本サイズ $n$ に対するラベル付けの最大数を成長関数
\[\Pi_{\mathcal{H}}(n)=\max_{S \subset \mathcal{X}, |S|=n}|\{(f(\boldsymbol{x}_1),\dots,f(\boldsymbol{x}_n)) : f \in \mathcal{H}\}|\]と定義する。VC次元が有限 $d$ のとき、サウアーの補題により
\[\Pi_{\mathcal{H}}(n)\leq\sum_{i=0}^{d} \binom{n}{i}\leq\left(\frac{en}{d}\right)^d\]が成立する。
VC次元は汎化誤差の上界に直接現れる。例えば二値分類において、確率 $1-\delta$ で
\[R(f)\leq R_n(f)+C \sqrt{\frac{\mathrm{VC}(\mathcal{H}) \log n + \log(1/\delta)}{n}}\]が成立する（$C$ は定数）。
VC次元は、仮説空間がどれだけ多様なデータ配置を識別できるかを測る指標であり、シャタリングの概念により定義される。成長関数の多項式的抑制と結びつくことで汎化誤差の上界評価を可能にし、統計的学習理論における複雑さ制御の中心的役割を果たす。
Mathematics is the language with which God has written the universe.