VC Dimension and Model Complexity

In machine learning, we constantly face a fundamental tradeoff: expressive models can fit training data perfectly but may fail to generalize, while simple models generalize well but may underfit. To navigate this tradeoff rigorously, we need a precise mathematical measure of a hypothesis class's expressive power—its ability to represent arbitrary patterns.

The concept of shattering provides exactly this measure. It answers a seemingly simple but profound question: Given a set of data points, can our hypothesis class realize every possible way of labeling those points?

This question lies at the heart of statistical learning theory and leads directly to the celebrated Vapnik-Chervonenkis (VC) dimension, which quantifies hypothesis class complexity in a way that directly connects to generalization guarantees.

Before defining shattering, we need the concept of a dichotomy. This fundamental notion captures how a hypothesis partitions a finite set of points into two classes.

Formal Definition:

Let $\mathcal{H}$ be a hypothesis class consisting of functions $h: \mathcal{X} \to {-1, +1}$ mapping from some input space $\mathcal{X}$ to binary labels. Given a finite set of points $S = {x_1, x_2, \ldots, x_m} \subset \mathcal{X}$, each hypothesis $h \in \mathcal{H}$ induces a labeling or dichotomy of $S$:

$$h|_S = (h(x_1), h(x_2), \ldots, h(x_m)) \in {-1, +1}^m$$

This is simply the vector of predictions that $h$ makes on the points in $S$. Different hypotheses in $\mathcal{H}$ may induce the same dichotomy, or they may induce different dichotomies.

The Set of Achievable Dichotomies:

The set of all dichotomies that $\mathcal{H}$ can induce on $S$ is denoted:

$$\mathcal{H}(S) = {(h(x_1), \ldots, h(x_m)) : h \in \mathcal{H}}$$

This is the restriction of $\mathcal{H}$ to the set $S$. Note that $\mathcal{H}(S) \subseteq {-1, +1}^m$, meaning the number of achievable dichotomies satisfies:

$$|\mathcal{H}(S)| \leq 2^m$$

The upper bound $2^m$ represents all possible binary labelings of $m$ points. A hypothesis class that achieves this upper bound for a particular set $S$ has complete expressive freedom over $S$—and this is precisely what shattering means.

We now present the central definition that underpins VC theory.

Definition (Shattering):

A hypothesis class $\mathcal{H}$ shatters a finite set $S = {x_1, \ldots, x_m} \subset \mathcal{X}$ if $\mathcal{H}$ can realize every possible dichotomy of $S$. Formally:

$$\mathcal{H} \text{ shatters } S \iff |\mathcal{H}(S)| = 2^m$$

Equivalently, for every labeling $(y_1, \ldots, y_m) \in {-1, +1}^m$, there exists some $h \in \mathcal{H}$ such that:

$$h(x_i) = y_i \quad \text{for all } i = 1, \ldots, m$$

Key Properties of Shattering:

1. Set-dependent: Whether $\mathcal{H}$ shatters a set depends on which points are in the set, not just how many.

2. Subset monotonicity: If $\mathcal{H}$ shatters $S$, it also shatters every subset $S' \subseteq S$. (Proof: Restricting dichotomies to a subset preserves all labelings.)

3. Existence vs. universality: We only require existence of a shattered set of size $m$—there may be many sets of size $m$ that $\mathcal{H}$ cannot shatter.

4. Location matters: Two sets of the same size may have very different shatterability properties based on where the points are positioned.

The most illuminating way to understand shattering is through geometric visualization. Consider the hypothesis class of linear classifiers (halfspaces) in $\mathbb{R}^2$:

$$\mathcal{H}{\text{linear}} = {h{\mathbf{w},b} : \mathbf{w} \in \mathbb{R}^2, b \in \mathbb{R}}$$

where $h_{\mathbf{w},b}(\mathbf{x}) = \text{sign}(\mathbf{w}^\top \mathbf{x} + b)$.

Each hypothesis corresponds to a line in $\mathbb{R}^2$, with points on one side labeled +1 and points on the other labeled -1.

Case 1: A Single Point

For any single point $\mathbf{x}_1$, linear classifiers can trivially shatter it:

• Label +1: Use any line with $\mathbf{x}_1$ on the positive side
• Label -1: Use any line with $\mathbf{x}_1$ on the negative side

✓ All $2^1 = 2$ dichotomies achievable.

Case 2: Two Points

For two distinct points ${\mathbf{x}_1, \mathbf{x}_2}$:

• $(+1, +1)$: Draw a line with both points on the positive side
• $(-1, -1)$: Draw a line with both points on the negative side
• $(+1, -1)$: Draw a line separating them with $\mathbf{x}_1$ on the + side
• $(-1, +1)$: Draw a line separating them with $\mathbf{x}_2$ on the + side

✓ All $2^2 = 4$ dichotomies achievable.

Case 3: Three Points

This is where geometry becomes critical. For three points ${\mathbf{x}_1, \mathbf{x}_2, \mathbf{x}_3}$:

If the points are collinear (lie on a line): The labeling $(+1, -1, +1)$ cannot be achieved—a line cannot separate the middle point from both endpoints. ✗ Cannot shatter collinear points.

If the points form a triangle (general position): All 8 dichotomies are achievable by appropriately orienting the separating line. ✓ Linear classifiers shatter any 3 points in general position in $\mathbb{R}^2$.

Case 4: Four Points

Can linear classifiers shatter any set of 4 points in $\mathbb{R}^2$? The answer is no:

Convex hull argument: Consider 4 points in general position forming a quadrilateral. Let's say they are the vertices of a convex quadrilateral. The diagonal labelings like $(+1, -1, +1, -1)$ (alternating around the quadrilateral) cannot be achieved by a single line.

One point inside: If one point lies inside the convex hull of the other three, we cannot label it differently from all surrounding points.

In both cases, there exists at least one dichotomy that no linear classifier can achieve. Therefore:

Linear classifiers in $\mathbb{R}^2$ cannot shatter any set of 4 points.

Let's systematically examine shattering behavior across different hypothesis classes to build intuition for how model structure affects expressive power.

While shattering is a binary concept (a set is either shattered or not), we often want to quantify how many dichotomies a hypothesis class can achieve. This leads to the growth function (also called the shattering coefficient).

Definition (Growth Function):

For a hypothesis class $\mathcal{H}$, the growth function $\Pi_\mathcal{H}: \mathbb{N} \to \mathbb{N}$ is defined as:

$$\Pi_\mathcal{H}(m) = \max_{S \subset \mathcal{X}, |S| = m} |\mathcal{H}(S)|$$

This is the maximum number of dichotomies that $\mathcal{H}$ can induce on any set of $m$ points.

Properties of the Growth Function:

1. Upper bound: $\Pi_\mathcal{H}(m) \leq 2^m$ for all $m$

2. Monotonicity: While $\Pi_\mathcal{H}(m)$ is non-decreasing, the rate of growth can vary

3. Shattering connection: $\mathcal{H}$ shatters some set of size $m$ if and only if $\Pi_\mathcal{H}(m) = 2^m$

4. VC dimension connection: If $\text{VCdim}(\mathcal{H}) = d$, then:

   • $\Pi_\mathcal{H}(m) = 2^m$ for $m \leq d$
   • $\Pi_\mathcal{H}(m) < 2^m$ for $m > d$

Why the Growth Function Matters:

The growth function appears directly in generalization bounds. Roughly speaking, the sample complexity and generalization error depend on $\Pi_\mathcal{H}(m)$ or its logarithm. When $\Pi_\mathcal{H}(m)$ grows polynomially rather than exponentially, we can learn with polynomial sample complexity.

This is the key insight: finite VC dimension implies polynomial growth, which implies learnability.

The concept of shattering might seem abstract, but it has profound implications for machine learning. Understanding shattering answers the fundamental question: Why do some models generalize while others memorize?

The Overfitting Connection:

If $\mathcal{H}$ can shatter a large set, it means $\mathcal{H}$ can perfectly fit any labeling of that set—including completely random labels with no underlying pattern. This ability to fit noise is precisely what we mean by overfitting.

Consider an extreme case: if $\mathcal{H}$ shatters a training set of size $m$, then for any target function $f$ (even if $f$ generates labels randomly), there exists $h \in \mathcal{H}$ with zero training error. But such an $h$ has learned nothing—it has merely memorized.

The Generalization Intuition:

The more points $\mathcal{H}$ can shatter, the more freedom it has to fit arbitrary patterns. This freedom requires more data to distinguish genuine patterns from noise. The VC dimension quantifies this:

• If VCdim($\mathcal{H}$) = d, you need roughly $O(d)$ samples to learn reliably
• If VCdim($\mathcal{H}$) = ∞, no finite sample is sufficient for guaranteed generalization

This gives the first principled answer to 'how much data do I need?'—it depends on the VC dimension of your hypothesis class.

The Fundamental Theorem Preview:

We're building toward one of the deepest results in learning theory:

A hypothesis class $\mathcal{H}$ is PAC-learnable if and only if VCdim($\mathcal{H}$) is finite.

This theorem (which we'll prove in later pages) shows that shattering—and its quantification via VC dimension—is not just one way to measure complexity, but the fundamental measure that determines learnability.

While shattering is a theoretical concept, understanding its computational aspects helps bridge theory and practice.

Verifying Shattering:

Given a specific set $S$ and hypothesis class $\mathcal{H}$, how do we check if $\mathcal{H}$ shatters $S$?

Naive approach: Enumerate all $2^{|S|}$ labelings and verify each is realizable. This is exponential in $|S|$.

For structured $\mathcal{H}$: Often we can use geometric or algebraic arguments. For linear classifiers, this reduces to checking linear separability of various point subsets.

We've developed a deep understanding of shattering—the foundation for VC theory and generalization analysis.

What's Next:

With shattering firmly understood, we're ready to define the VC dimension formally—the largest set size a hypothesis class can shatter. This single number summarizes the expressive power of a hypothesis class and directly determines sample complexity and generalization bounds.