Why Shattering Is a Useful Notion
A hypothesis class can be large in several different senses. It may contain many functions, or it may be able to produce many different label patterns when evaluated on a finite collection of points. The second idea is central to shattering: a class shatters a set if it can realize every possible binary labeling of that set. This is a precise way to ask how flexibly the class can fit labels on chosen data points.
The VC dimension summarizes this flexibility by recording the largest number of points that the class can shatter. It is defined through the existence of configurations, not by counting the hypotheses themselves. To establish shattering, list a realizing hypothesis for every labeling; to establish failure, it is enough to identify one labeling that cannot be realized.
Definitions
Let \(\mathcal X\) be a domain and let \(\mathcal H\) be a nonempty class of binary-valued functions \(h:\mathcal X\to\{0,1\}\). For a finite set \(A\subseteq\mathcal X\), a labeling is a function \(y:A\to\{0,1\}\). The restriction of \(h\) to \(A\), written \(h|_A\), is the labeling \(x\mapsto h(x)\) on that set.
For a class \(\mathcal C\) of subsets of \(\mathcal X\), the same definition can be written without function notation. The class \(\mathcal C\) shatters \(A\) if every subset \(B\subseteq A\) can be expressed as \(C\cap A\) for some \(C\in\mathcal C\). This is the set-class version: points in \(B\) receive label 1, and points in \(A\setminus B\) receive label 0.
If the supremum is a finite integer \(d\), then some set of size \(d\) is shattered, and no set of size \(d+1\) is shattered. The dimension concerns whether such sets exist in the domain. A particular sample can have fewer realized labelings than the class can realize on some other configuration of the same size.
How to Test a Configuration
For \(m\) distinct points, there are \(2^m\) binary labelings. The direct test is therefore finite: record which labelings are induced by members of the class, then compare this list with all \(2^m\) possibilities. A complete list proves shattering; one missing labeling proves that the configuration is not shattered. In set notation, the same test asks whether every subset of the configuration occurs as a trace.
Worked Example: A Class That Shatters Three Points
Let \(A=\{x_1,x_2,x_3\}\), let the domain be \(A\), and let \(\mathcal H\) contain every binary-valued function on \(A\). Equivalently, as a set class, it contains every subset of \(A\). We check the eight labelings, writing each labeling in the order \(x_1,x_2,x_3\).
The labeling 000 is realized by the empty set; 001 by \(\{x_3\}\); 010 by \(\{x_2\}\); and 011 by \(\{x_2,x_3\}\). The labeling 100 is realized by \(\{x_1\}\); 101 by \(\{x_1,x_3\}\); 110 by \(\{x_1,x_2\}\); and 111 by \(A\).
Each of the \(2^3=8\) labelings has a realizing member of \(\mathcal H\), so \(A\) is shattered. No subset of the domain has more than three points. Therefore \(\operatorname{VCdim}(\mathcal H)=3\).
Worked Example: A Class That Shatters a Pair but Not a Triple
Take the domain \(A=\{a,b,c\}\) and the set class \(\mathcal C=\{\varnothing,\{a,b\},\{b,c\},\{a,c\}\}\). First consider the pair \(\{a,b\}\). The traces \(C\cap\{a,b\}\), as \(C\) runs through \(\mathcal C\), are \(\varnothing,\{a,b\},\{b\},\{a\}\), respectively. These are all four subsets of the pair, so the pair is shattered.
For the triple \(A\), the available traces are exactly \(\varnothing,\{a,b\},\{b,c\},\{a,c\}\). For instance, the labeling that selects \(a\) alone, corresponding to the trace \(\{a\}\), is missing. Thus \(A\) is not shattered. Since the domain has only three points and its only three-point subset is \(A\), no three-point set is shattered. A pair is shattered, so \(\operatorname{VCdim}(\mathcal C)=2\).
This example also illustrates why counting hypotheses alone does not settle a shattering question: four members are enough to realize all four labelings on a pair, but these particular four members do not realize every labeling on the triple.
Worked Example: A Class That Cannot Shatter Any Pair
Let \(\mathcal X=\{u,v,w\}\), and let \(\mathcal H\) consist of the functions whose sets of positive points are \(\varnothing,\{u\},\{v\},\{w\}\). On the one-point set \(\{u\}\), the empty set gives label 0 and \(\{u\}\) gives label 1. Thus at least one point is shattered.
Now take any pair of distinct points, for example \(\{u,v\}\). The empty set gives 00, \(\{u\}\) gives 10, and \(\{v\}\) gives 01. The labeling 11 is unavailable because every member of \(\mathcal H\) has at most one positive point. This same argument applies to every pair in the domain, so no pair is shattered. Therefore \(\operatorname{VCdim}(\mathcal H)=1\).
Structural Properties
Shattering has a useful hereditary property: once a set is shattered, every subset of it is shattered. This explains why VC dimension can be checked by locating the largest shattered sets: if a set of size \(m\) is shattered, then shattered sets of every smaller size are available by taking subsets.
Proof. Let \(B\subseteq A\), and choose any labeling \(y:B\to\{0,1\}\). Extend \(y\) to a labeling \(\widetilde y:A\to\{0,1\}\) by setting \(\widetilde y(x)=0\) for \(x\in A\setminus B\), and \(\widetilde y(x)=y(x)\) for \(x\in B\). Because \(\mathcal H\) shatters \(A\), some \(h\in\mathcal H\) agrees with \(\widetilde y\) at every point in \(A\). Its restriction to \(B\) therefore agrees with \(y\) everywhere on \(B\). Since \(y\) was arbitrary, every labeling of \(B\) is realized. Hence \(\mathcal H\) shatters \(B\). \(\square\)
The function and set-class descriptions also make complementation transparent. For a binary function, complementing means replacing each output by the other binary label. For a set, it means replacing membership by nonmembership.
Proof. Fix a finite set \(A\). If \(\mathcal H\) shatters \(A\), take any labeling \(y:A\to\{0,1\}\). The labeling \(1-y\), defined by \((1-y)(x)=1-y(x)\), is realized on \(A\) by some \(h\in\mathcal H\). Then \(1-h\in\mathcal H^c\) realizes \(y\), since \((1-h)(x)=1-y(x)=y(x)\) would be incorrect; rather, choose \(h\) realizing \(1-y\), so \(h(x)=1-y(x)\), and therefore \((1-h)(x)=y(x)\). Thus \(\mathcal H^c\) shatters \(A\). Applying the same reasoning to \(\mathcal H^c\), whose complement class is \(\mathcal H\), proves the converse. The two classes shatter exactly the same finite sets and hence have equal VC dimension. \(\square\)
A further basic constraint follows directly from the definition: shattering \(m\) points requires at least \(2^m\) distinct hypotheses. Indeed, two different labelings on those points cannot be induced by the same hypothesis, because a function has a unique value at each point. This is a necessary condition, not a sufficient one; the second worked example has four hypotheses but does not shatter its three-point domain.
Common Pitfall and Why Dimension Matters
A common mistake is to reason, “There are \(2^m\) hypotheses, so the class shatters every \(m\)-point set.” The count does not show that the hypotheses produce different labelings on the chosen set. Some may agree there, and a labeling may be missing. The correction is to inspect the restrictions to the specific configuration: show all \(2^m\) distinct labelings to prove shattering, or exhibit one absent labeling to disprove it.
Another mistake is to infer that a class with many hypotheses must have large VC dimension. A class can be large while its members behave in a highly restricted way on every configuration. Conversely, a small finite class can shatter a small set if its members realize all labelings there. VC dimension records the capacity to produce labelings on finite configurations, not the raw number of models or the fit on one observed sample.
This distinction matters because shattering and VC dimension are combinatorial measures of a class’s flexibility. In later analysis, bounds on the number of label patterns and generalization will connect this flexibility to statistical performance. For now, the central discipline is exact: name the configuration, list its possible labelings, and check which are actually realized.
Check Your Understanding
Answer each question by using the definition and, where appropriate, listing the labelings.
- A class shatters a four-point set. What is the minimum number of distinct hypotheses it must contain? Explain why.
- If a class shatters a set of five points, what can be concluded about each of its two-point subsets?
- A class induces the labelings 00, 01, and 10 on a particular pair. Is that pair shattered? Which labeling determines your answer?
- Can a class with eight hypotheses shatter a four-point set? Explain using the number of required labelings.
- Why does complementing every function in a class leave its VC dimension unchanged?