VC dimension and growth functions

A set of d distinct inputs is shattered if the class realizes all $2^d$ binary labelings on that same set. VC dimension is the largest such d, or infinity when arbitrarily large finite sets can be shattered. Showing that a class realizes many patterns on different input sets is insufficient: all patterns must be available on one chosen set. The growth function takes the maximum number of restrictions the class can realize on any n distinct inputs, and is at most $2^n$. This displayed distinct-point form assumes the domain has at least n points; for a smaller finite domain use n-tuples allowing repeated inputs.

Consider classifiers that label a real input positive exactly when it belongs to one interval, allowing an empty positive set. Two ordered points are shattered: an interval can select neither, either singleton, or both. Three ordered points are not shattered, because selecting the two extremes without the middle is impossible for an interval. Hence the class has VC dimension two. The argument uses the order structure of the inputs, not an assertion that two endpoints always imply two units of capacity in arbitrary parameterizations.

On n ordered distinct real points, a nonempty interval-positive labeling is exactly one contiguous positive block. Choose the first and last positive points to obtain n(n+1)/2 possibilities, and add the all-negative labeling. Many different endpoint pairs represent the same pattern because endpoints can move between sample points. That redundancy is precisely why the infinite parameter space need not prevent finite-sample control. The all-positive labeling is already one of the contiguous blocks and must not be counted twice.

The Sauer–Shelah lemma says that a binary class with finite VC dimension d has growth at most the sum of binomial coefficients through d. When n≥d≥1, this sum is at most $(en/d)^d$. If d=0 the appropriate bound is one, and if n<d the trivial $2^n$ bound is the useful form. The lemma is a combinatorial theorem and makes no sampling claim by itself. For interval classifiers the d=2 binomial sum equals the exact contiguous-block count; the simpler exponential bound is generally looser.

A tempting but incomplete argument unions over the label patterns observed on the training sample as though that random set of patterns were fixed in advance. VC generalization proofs introduce an independent ghost sample or symmetrization so that the relevant finite restrictions can be counted legitimately. Under standard measurability assumptions, finite VC dimension gives distribution-free binary PAC learnability. The usual elementary agnostic bounds scale like the square root of a dimension-and-confidence term divided by sample size, possibly with a logarithmic sample-size factor depending on the proof.

For rigorous probability statements here, one may restrict to finite or countable classes, or assume the appropriate suprema and selection rules are measurable. A raw VC count alone does not settle pathological measurability cases or computational efficiency. Nor does a small parameter count prove low VC dimension without examining the function family. Practical use begins by identifying the actual decision class, proving its shattering dimension, and checking that the learning algorithm and data model match the theorem whose rate is being invoked.