Must every set of d points be shattered?

No. Existence of one such set establishes the lower bound.

Can VC dimension exceed the number of features?

Yes. The one-dimensional interval example has dimension 2.

Does dimension 2 mean only two training examples can be fitted?

No. It concerns arbitrary labelings, not the maximum number of correctly labeled examples.

AI Glossary / Graphs and symbolic AI / Advanced

VC dimension

Definition

VC dimension, short for Vapnik - Chervonenkis dimension, measures the expressive capacity of a class of binary classifiers. It is the largest number of input points for which the class can realize every possible assignment of two labels. If arbitrarily large finite sets can be labeled in every possible way, the VC dimension is infinite.

What it means

The measure concerns a whole hypothesis class, not just one fitted classifier or one observed labeling. Realizing every labeling of a point set is called shattering it. A model class with greater expressive capacity can represent more patterns, including patterns caused by noise. VC dimension helps formalize that capacity without requiring a particular data distribution.

How it works

To show that a class has VC dimension at least d, exhibit a set of d points and show that all 2 to the power d binary labelings are achievable. To establish an upper bound of d, show that no set of d+1 points can be shattered. Failure on one particular set alone is insufficient for that upper bound. Statistical learning theory connects finite VC dimension to generalization guarantees under its sampling and learning assumptions; the dimension by itself is not a measured test accuracy.

Three practical examples

A fictional quality-control rule flags measurements inside one adjustable interval. Its two endpoints allow a contiguous accepted region. That restriction is different from the number of measurement columns in its input table.
A fictional screening system flags all scores above one adjustable threshold. On an ordered pair of distinct scores, it can flag neither, the higher score only, or both. It cannot flag only the lower score under that fixed rule direction.
A fictional analyst fits an interval perfectly to a dataset whose positive cases occupy one uninterrupted score band. This success shows that one labeling can be fitted. It does not show that every alternative labeling of the same cases could be fitted by the same rule family.

Think of it this way

Imagine testing a set of stencils on a fixed arrangement of dots. Shattering means that, for every possible choice of dots to mark, some stencil in the set marks exactly those dots. One stencil marking all dots is insufficient. This analogy emphasizes the requirement to realize every labeling, which is stronger than fitting the labels seen in one dataset.

Worked example

Consider classifiers on the real line that output 1 inside a closed interval [a,b], with a<=b, and 0 outside it. Endpoints may be chosen freely.
Take the two points 1 and 3. All four labelings are possible: interval [4,5] gives 00; [0.5,1.5] gives 10; [2.5,3.5] gives 01; and [0.5,3.5] gives 11. Therefore this class shatters a two-point set.
Now consider any three distinct ordered points x1<x2<x3. Labeling them 101 is impossible. An interval containing x1 and x3 must contain the point between them. This argument applies to every three-point set on the line, establishing the upper bound. Consequently the VC dimension is exactly 2.
For the specific points 1,2,3, the achievable labelings are 000,001,010,011,100,110,111: seven of the eight possibilities. For instance, [1.5,2.5] realizes 010, so the missing labeling is specifically 101, not an isolated positive middle point.
Notice that the input has only one numerical coordinate even though the VC dimension is 2. Also, an interval can classify many more than two points correctly when their observed labels happen to follow the required contiguous pattern. The dimension is not a cap on the number of correctly classified observations.

Illustrative case study

In a fictional workshop, a team uses an interval rule to flag unusual scores. Three historical cases have scores 20,50,80 and labels 1,0,1. A reviewer proposes changing the interval endpoints until all three labels are matched.
The worked argument shows why this cannot succeed: including 20 and 80 necessarily includes 50. For these three observations, every single-interval classifier makes at least one mistake, and one mistake is achievable by selecting [15,25]. Its predictions are 1,0,0, matching two labels. The best empirical error is therefore one third.
The team could consider a different rule family, such as two separated intervals, but that would be a change in expressiveness rather than a better endpoint optimizer for the original family. It would also need separate evaluation on new cases. This fictional exercise identifies a representational limitation; it does not establish that more flexible rules will generalize better.

Common misconceptions and mistakes

VC dimension is not generally the number of input features or the number of adjustable parameters. The worked class has one input coordinate and VC dimension 2; the equality with its two endpoints is not a universal counting rule.
Fitting one labeling is not shattering. All possible labelings must be realizable.
To prove a class cannot shatter any d+1 points, failing on one poorly positioned set is not enough. The interval proof works because every ordered triple has a middle point.
A higher value is not automatically better or worse. It describes capacity; predictive usefulness also depends on data, assumptions, fitting, and evaluation.

Business use

Use the concept to distinguish a rule family's limitations from implementation mistakes. In the fictional score example, repeated endpoint tuning cannot eliminate the remaining error. Conversely, perfect training fit should prompt evaluation of how a selected rule performs on new observations. When someone presents a sample-size guarantee involving VC dimension, request the learning assumptions, desired accuracy, confidence level, and exact hypothesis class. A single capacity number is not a complete data-collection plan.

Check your understanding

Which labeling is impossible for three ordered points with a single positive interval?

Answer: 101.

Why does that establish an upper bound here?

Answer: Every three-point set on the real line can be ordered, and its middle point lies between its extremes.

What is the best training error in the 20,50,80 case?

Answer: One mistake out of three, or one third.

Related terms

Learn next

Prove that the class of rules flagging x>=t, with a freely adjustable threshold t, has VC dimension 1. Then compare its possible labelings with the interval class on the same two points. Keep the rule's direction fixed throughout the proof.

Sources

Cosma Shalizi, Carnegie Mellon University, From Rademacher Complexity to VC Dimension, definition and growth-function discussion: https://www.stat.cmu.edu/~cshalizi/sml/21/lectures/09/lecture-09.html Madhavan Mukund, Chennai Mathematical Institute, Lecture 2: VC Dimension, interval examples: https://www.cmi.ac.in/~madhavan/courses/aml2021/lectures/ClassNotes-23sep2021.pdf The selected coordinates, interval enumeration, and score-screening case are illustrative calculations.

Previous: Vauquois triangle Next: Vecchia approximation