A combinatorial capacity measure for a class of indicator (binary) functions defined as the largest cardinality of a finite set that the class can shatter, i.e., realize every possible binary labeling on that set.

Principle

Capacity is measured by the ability to realize all labelings on finite point sets; the VC dimension equals the maximum number of points for which this full labeling freedom holds.

Demonstration

For intervals on the real line, choose two distinct points; the class of intervals can realize all four binary labelings on those two points, but no three-point configuration is guaranteed to be shattered by intervals, so the VC dimension of intervals is 2.

Misapplication

Treating VC dimension as a direct predictor of test-set error without accounting for data distribution, margin effects, or regularization; or using VC dimension computed for a wildly different hypothesis class than the one actually trained.

Consequence

When properly applied, VC dimension provides uniform convergence and sample-complexity bounds: higher VC dimension requires more samples to guarantee that empirical risk approximates true risk uniformly over the class.

Reversal

Interpreting the concept in reverse: a small VC dimension implies limited expressivity and easier generalization, while infinite VC indicates potential for overfitting unless other constraints apply.

Boundary

Defined for classes of indicator (binary-valued) functions; extensions exist (pseudo-dimension, fat-shattering) for real-valued hypotheses. It is a combinatorial worst-case quantity and may be loose for specific distributions or algorithms.

Semantic Tension

Competes with other complexity measures (Rademacher complexity, algorithmic stability, margin-based bounds); VC dimension is distribution-free and combinatorial, which can conflict with data-dependent measures that better predict practical generalization.

Synthesis

VC dimension concisely captures the worst-case combinatorial expressivity of a binary hypothesis class by counting the largest finite set it can label in every possible way; it is a useful but sometimes conservative ingredient in learning-theoretic sample complexity reasoning.