Vapnik-Chervonenkis Dimension

machine-learning learning-theory statistics

Definition

Vapnik-Chervonenkis Dimension

The Vapnik-Chervonenkis (VC) dimension, denoted $\text{vc}(\mathcal{H})$, is a measure of the capacity or complexity of a hypothesis class. It is defined as the cardinality of the largest set of points $X\subseteq \mathcal{X}$ that can be shattered by $\mathcal{H}$. If $\mathcal{H}$ can shatter sets of arbitrary size, the VC dimension is infinite.

PAC Learnability

The VC dimension provides a necessary and sufficient condition for PAC learnability in the binary classification setting. A class $\mathcal{H}$ is PAC-learnable if and only if $\text{vc}(\mathcal{H})<\infty$. The sample complexity $m$ is then bounded by the VC dimension:

$$m\le \mathcal{O}\left(\frac{\text{vc}(\mathcal{H})\ln (1/ϵ)+\ln (1/\delta )}{ϵ}\right)$$

Examples

Thresholds on the Real Line: For the class $\mathcal{H}=\{h_a(x)=\text{sign}(x-a)\mid a\in \mathbb{R}\}$, the VC dimension is 1.

Axis-aligned Rectangles: In ${\mathbb{R}}^2$, the class of axis-aligned rectangles can shatter at most 4 points, resulting in $\text{vc}(\mathcal{H})=4$.

Linear Separators: In a $d$-dimensional space ${\mathbb{R}}^d$, the VC dimension of linear classifiers is $d+1$.

Convex Polygons: For the class of convex polygons in ${\mathbb{R}}^2$, the VC dimension is infinite. This is because any number of points $n$ can be placed in convex position (e.g., on a circle), and for any binary labelling, a convex polygon can be constructed that contains exactly the points with positive labels.