1 Definition and Formalization
The Vapnik–Chervonenkis (VC) dimension formalizes the capacity of a hypothesis class to fit arbitrary binary labelings. It is defined through the concept of shattering and bounded by the growth function.
1.1 Shattering
A hypothesis class \(\mathcal{H}\) of binary classifiers (functions mapping from an input space \(\mathcal{X}\) to \(\{0,1\}\)) is said to shatter a set of points \(S = \{x_1, x_2, \dots, x_m\} \subseteq \mathcal{X}\) if, for every possible binary labeling \(y_1, y_2, \dots, y_m \in \{0,1\}\), there exists some hypothesis \(h \in \mathcal{H}\) such that \(h(x_i) = y_i\) for all \(i\). In other words, the class can realize all \(2^m\) distinct patterns of classification on those points.
Shattering does not require the hypothesis to be consistent on other points; only the given set matters. A set that can be shattered is sometimes called a shattered set.
1.2 Formal Definition of VC Dimension
The VC dimension of a hypothesis class \(\mathcal{H}\), denoted \(\mathrm{VCdim}(\mathcal{H})\), is defined as the largest integer \(d\) such that there exists a set of \(d\) points in \(\mathcal{X}\) that is shattered by \(\mathcal{H}\). Formally:
\[
| \mathrm{VCdim}(\mathcal{H}) = \max \left\{ m \in \mathbb{N} \; | \; \exists S \subseteq \mathcal{X}, | S | = m, \text{ and } \mathcal{H} \text{ shatters } S \right\}. |
|---|
\]
If \(\mathcal{H}\) can shatter arbitrarily large finite sets (i.e., for every \(m\) there exists a shattered set of size \(m\)), then the VC dimension is infinite.
1.3 Connection to Growth Function
The growth function (or shattering coefficient) of \(\mathcal{H}\) for a sample size \(m\) is defined as:
\[
| \Pi_{\mathcal{H}}(m) = \max_{S \subseteq \mathcal{X}, | S | = m} \left | \{ (h(x_1), \dots, h(x_m)) : h \in \mathcal{H} \} \right | . |
|---|
\]
It counts the maximum number of distinct labelings that \(\mathcal{H}\) can induce on any set of \(m\) points. The growth function is bounded above by \(2^m\), but if \(\mathrm{VCdim}(\mathcal{H}) = d < \infty\), then for all \(m \leq d\), \(\Pi_{\mathcal{H}}(m) = 2^m\), and for \(m > d\), the Sauer–Shelah lemma gives \(\Pi_{\mathcal{H}}(m) \leq \sum_{i=0}^d \binom{m}{i}\). This polynomial bound is crucial for deriving generalization guarantees.
2 Properties of VC Dimension
2.1 Monotonicity
If \(\mathcal{H}_1 \subseteq \mathcal{H}_2\) (i.e., every hypothesis in \(\mathcal{H}_1\) is also in \(\mathcal{H}_2\)), then \(\mathrm{VCdim}(\mathcal{H}_1) \leq \mathrm{VCdim}(\mathcal{H}_2)\). Adding more functions to a class cannot reduce its shattering capacity. Similarly, if \(\mathcal{H}\) has VC dimension \(d\), then any subclass that lacks the ability to shatter a particular set of size \(d\) may have strictly smaller VC dimension.
2.2 Relationship with Hypothesis Class Size
| For a finite hypothesis class \(\mathcal{H}\) with \( | \mathcal{H} | = N\), the VC dimension is at most \(\log_2 N\). This follows because to shatter \(d\) points, the class must contain at least \(2^d\) distinct functions (one for each labeling). Thus, finite classes have bounded VC dimension. Conversely, infinite classes may have finite or infinite VC dimension. |
|---|
2.3 Subset and Union Bounds
- Subset: If \(\mathcal{H}\) shatters a set \(S\) of size \(d\), then it also shatters every subset of \(S\). Consequently, \(\mathrm{VCdim}(\mathcal{H}) \geq d\) implies that for every \(k \leq d\) there exists a shattered set of size \(k\) (not necessarily a subset of the original one, but by taking subsets of a shattered set, one obtains shattered sets of all smaller sizes).
- Union: For two hypothesis classes \(\mathcal{H}_1\) and \(\mathcal{H}_2\) over the same input space, the VC dimension of their union satisfies \(\mathrm{VCdim}(\mathcal{H}_1 \cup \mathcal{H}_2) \leq \mathrm{VCdim}(\mathcal{H}_1) + \mathrm{VCdim}(\mathcal{H}_2) + 1\). This bound can be tight in worst-case scenarios, such as when one class shatters a set of points and the other shatters a different set.
3 Examples of VC Dimension
3.1 Class of Intervals on the Real Line
Consider \(\mathcal{H} = \{ h_{a,b} : a < b \}\) where \(h_{a,b}(x) = 1\) if \(a \leq x \leq b\) and 0 otherwise (closed intervals). The VC dimension is 2:
- Shattering 2 points: For any two distinct points \(x_1 < x_2\), all four labelings can be realized: (0,0) by an interval that avoids both; (1,1) by an interval covering both; (1,0) by an interval covering only \(x_1\); (0,1) by an interval covering only \(x_2\).
- No shattering of 3 points: For three points \(x_1 < x_2 < x_3\), the labeling (1,0,1) cannot be realized because any interval that contains \(x_1\) and \(x_3\) also contains the middle point \(x_2\).
3.2 Axis-Aligned Rectangles in the Plane
The class of axis-aligned rectangles (closed) in \(\mathbb{R}^2\) has VC dimension 4. A set of four points can be shattered (e.g., points at the four corners of a diamond), but any five points cannot: by the pigeonhole principle, at least one point is inside the convex hull of the others, making the labeling that assigns that point 0 and others 1 impossible. (An axis-aligned rectangle covering the convex hull of the others would necessarily cover the interior point.)
3.3 Linear Classifiers (Perceptrons)
3.3.1 Affine Hyperplanes in \(\mathbb{R}^d\)
The class of linear classifiers (halfspaces) in \(\mathbb{R}^d\) is \(\mathcal{H} = \{ x \mapsto \mathrm{sign}(w \cdot x + b) : w \in \mathbb{R}^d, b \in \mathbb{R} \}\). Its VC dimension is \(d+1\).
- Lower bound: The set of points \(\{0, e_1, e_2, \dots, e_d\}\) (zero vector and standard basis vectors) can be shattered. For any labeling, one can choose appropriate \(w\) and \(b\) to achieve it by setting \(b\) to separate 0 from the others and adjusting \(w\) components.
- Upper bound: Radon’s theorem implies that any set of \(d+2\) points in \(\mathbb{R}^d\) can be partitioned into two subsets whose convex hulls intersect, preventing shattering. This yields \(\mathrm{VCdim} \leq d+1\).
3.4 Decision Trees and Neural Networks
- Decision trees: The VC dimension of decision trees with \(N\) leaves (or with a fixed depth) depends on the number of leaves and the input dimension. For binary decision trees that axis-align splits (each internal node tests one coordinate), the VC dimension is \(O(N \log N)\) up to constants.
- Neural networks: For feedforward neural networks with a fixed architecture (number of layers, nodes per layer), the VC dimension is bounded by \(O(W^2)\) where \(W\) is the total number of weights, but precise values depend on the activation function. For example, a single hidden layer with \(k\) nodes and sigmoid activation has VC dimension \(O(k^2 d^2)\) for input dimension \(d\). For piecewise-linear activations like ReLU, the VC dimension scales as \(O(W \log W)\). In practice, many deep networks have VC dimensions far larger than the training set size yet still generalize, a phenomenon partly explained by implicit regularization.
4 Applications in Learning Theory
4.1 PAC Learning and Sample Complexity
In the Probably Approximately Correct (PAC) learning framework, a hypothesis class is PAC learnable if and only if its VC dimension is finite. The sample complexity (number of training examples needed to achieve, with probability at least \(1-\delta\), an error at most \(\epsilon\)) is:
\[ m \geq \frac{1}{\epsilon} \left( 4 \log \frac{2}{\delta} + 8 \mathrm{VCdim}(\mathcal{H}) \log \frac{13}{\epsilon} \right) \]
(up to constants). This upper bound guarantees that any empirical risk minimizer (ERM) over \(\mathcal{H}\) will be a PAC learning algorithm. Conversely, a lower bound states that no algorithm can achieve PAC learning with fewer than \(\Omega((\mathrm{VCdim}(\mathcal{H}) + \log(1/\delta))/\epsilon)\) examples.
4.2 Uniform Convergence and Generalization Bounds
The VC dimension underpins uniform convergence of empirical risks to true risks. For any distribution over \(\mathcal{X} \times \{0,1\}\), with probability at least \(1-\delta\) over an i.i.d. sample of size \(m\), for every hypothesis \(h \in \mathcal{H}\):
\[
| R(h) - \hat{R}(h) | \leq O\left( \sqrt{ \frac{ \mathrm{VCdim}(\mathcal{H}) + \log(1/\delta) }{m} } \right), |
|---|
\]
where \(R(h)\) is the true error and \(\hat{R}(h)\) is the empirical error. This bound is distribution-free and holds uniformly over the hypothesis class, hence the name uniform convergence. It directly implies that if the VC dimension is finite, the ERM hypothesis’s true error converges to its empirical error as \(m\) grows.
4.3 Implications for Overfitting and Model Selection
A hypothesis class with very large VC dimension (relative to sample size) can overfit: it can shatter the training set perfectly even if the true labeling is random, leading to poor generalization. VC dimension thus serves as a model complexity measure for model selection (e.g., via structural risk minimization). When comparing hypothesis classes (e.g., polynomials of degree \(k\) vs. degree \(k+1\)), one can choose the class that minimizes a penalty-augmented empirical risk:
\[ \hat{R}(h) + C \cdot \frac{ \mathrm{VCdim}(\mathcal{H}) }{m}, \]
where \(C\) is a constant. This trades off training error against capacity, discouraging overly complex models.
5 Limitations and Extensions
5.1 Infinite VC Dimension and Non-Learnability
If a hypothesis class has infinite VC dimension, it is not PAC learnable in the standard distribution-free sense. For example, the class of all functions from \(\mathbb{N}\) to \(\{0,1\}\) has infinite VC dimension and is not learnable. However, under specific data distributions or with additional assumptions (e.g., realizability), learnability may still be possible even with infinite VC dimension. Also, classes with infinite VC dimension can sometimes be learned using non-ERM algorithms or in the agnostic setting if the label noise is bounded.
5.2 VC Dimension vs. Rademacher Complexity
Rademacher complexity is an alternative capacity measure that often yields tighter, data-dependent generalization bounds. While VC dimension is a combinatorial property of the hypothesis class alone (ignoring the data distribution), Rademacher complexity captures the ability of the class to fit random noise on a given sample. For many classes, the Rademacher complexity can be bounded using the VC dimension via Sauer’s lemma: \(\mathcal{R}_m(\mathcal{H}) \leq O(\sqrt{\mathrm{VCdim}(\mathcal{H})/m})\). However, Rademacher complexity can be smaller than this bound in practice, especially when the data distribution is concentrated.
5.3 Alternative Capacity Measures (e.g., Fat-Shattering Dimension)
For real-valued functions (regression), the VC dimension is not directly applicable. The fat-shattering dimension (or pseudo-dimension) generalizes the VC dimension to continuous outputs. A real-valued function class \(\mathcal{F}\) has a fat-shattering dimension \(d_\gamma\) at scale \(\gamma\) if there exists a set of points that can be shattered with margin \(\gamma\). This dimension governs the sample complexity of learning under the squared loss or absolute loss, and it also appears in bounds for classification with a margin (e.g., support vector machines). For binary classification, the fat-shattering dimension reduces to the standard VC dimension when \(\gamma\) is sufficiently small.