VC dimension — the capacity that decides learnability

Parent: learning-theory Prereq: learning-theory — defines H (hypothesis class), h ∈ H (one rule X→{+,−}), ε, m.

A single number measuring a hypothesis class H's raw "power" — and it turns out to be exactly the line between learnable and not.

Shattering

Fix a class H. A finite set S = {x₁, …, xₙ} is shattered by H if every one of its 2ⁿ labelings can be realized: for each (y₁,…,yₙ) ∈ {+,−}ⁿ there is some h ∈ H with h(xᵢ) = yᵢ for all i.

VC dimension

VCdim(H) = the largest n such that there exists a set of n points shattered by H (and ∞ if there is no largest).

The quantifier structure — the part that trips everyone — is:

VCdim(H) ≥ n ⟺ ∃ points x₁,…,xₙ such that ∀ labelings ∃ h ∈ H realizing it.

Read the three quantifiers in order: you get to choose the n points (∃, pick the most favorable placement); then the class must handle every labeling of them (∀); by finding some hypothesis each time (∃). And VCdim(H) = n means additionally that no n+1 points work — every placement of n+1 fails on some labeling.

How you actually count it

• to show VC ≥ n: exhibit some n points and realize all 2ⁿ labelings (shatter them);
• to show VC = n: also show no n+1 points can be shattered — some labeling always fails.

You are counting points you can shatter, not lines or parameters. So "2 lines" does not mean "VC 2" — you have to run the test.

Children

• examples — a capacity ladder, counted by hand: threshold (1) → interval (2) → union-of-k (2k) → linear (3) → rectangle (4) → sin ωx (∞).
• price-of-capacity — raising VC is never free: the bias–variance tradeoff and structural risk minimization.
• sauer-shelah — the lemma that tames an infinite class: on n points it realizes only O(nᵈ) labelings, not 2ⁿ.
• fundamental-theorem — PAC-learnable ⟺ finite VC, with the proof (both directions).

Why it's called "VC dimension"

• VC = Vapnik–Chervonenkis — Vladimir Vapnik & Alexey Chervonenkis (1971), the two who defined it. It's just their names (like "Euler's number"), not an acronym for a concept.
• "dimension" because it counts the class's degrees of freedom, generalizing vector-space dimension: shattering n points = independently choosing all n labels = n independent "coordinates" you control — exactly as dimension = the largest set of independent vectors. Shattering is the learning-theory version of linear independence.
• For a parametric class it even matches the parameter count: linear separators in ℝᵈ have VC = d+1.
• But VC is more honest than counting parameters: sin(ωx) has one parameter ω, yet VC = ∞. Parameter-count lies about capacity; VC measures the true flexibility — which is exactly why a new notion of "dimension" was needed.

VC dimension ≠ the dimension of the data space

Three different "dimensions" get confused here — keep them apart:

class	input space (geometry)	parameters	VC
threshold on a line	1-D	1 (t)	1
interval on a line	1-D	2 (a,b)	2
line in the plane	2-D	2	3
rectangle in the plane	2-D	4	4

Threshold and interval live on the same 1-D line, yet have VC 1 vs 2 — so VC is a property of the rule class, not of where the points live. A line cutting the 2-D plane is a 1-D cut but has VC 3 — none of {input=2, cut=1, VC=3} agree. VC coincides with the input dimension only for special classes (linear separators: d+1 in ℝᵈ), which is why they're so easily conflated.