VC Dimension

Source: Unit 5 §11

Why VC dimension?

The finite-$H$ bound $m \ge (\ln|H| + \ln(1/\delta))/\varepsilon$ has two drawbacks:

⚠GotchaWhere the finite-H bound breaks

1. The bound can be very loose, and therefore weak, for large $|H|$.
2. It does not work at all when $H$ is infinite.

When is $H$ infinite? Infinitely many lines can separate two real-valued points, so $H$ is infinite. For infinite $H$ the sample-complexity bound fails, and VC dimension comes to the rescue.

Shattering

A dichotomy of a set $S$ is a partition of $S$ into two disjoint subsets - in other words, a labelling. A set of $n$ points has $2^n$ possible dichotomies.

◎Exam cueThe definition to quote

$H$ SHATTERS $S$ if every possible dichotomy of $S$ can be represented by some hypothesis in $H$ - that is, $H$ is consistent with every labelling of $S$.

With 2 points and a line as the model there are $2^2 = 4$ labellings; if $H$ can realize all 4, then $H$ shatters those 2 points.

All 2³ = 8 labellings of three non-collinear points are realisable by a straight line, so a line shatters three points.

Definition of VC dimension

$$VC(H) = \text{the size of the LARGEST finite subset of } X \text{ that can be shattered by } H$$

If $H$ can shatter arbitrarily large finite subsets, then $VC(H) = \infty$.

For finite $H$:

$$VC(H) \le \log_2 |H|$$

→StepsWhy the finite-H ceiling holds

1. Suppose $VC(H) = d$.
2. To shatter $d$ instances, $H$ needs $2^d$ distinct hypotheses, one per labelling.
3. So $2^d \le |H|$.
4. Taking logs, $d \le \log_2 |H|$.

Worked examples

1. Intervals on the real line

$X = \mathbb{R}$ and H = { a < x < b }. The answer is VC(H) = 2.

→StepsShattering two points, failing on three

1. Take S = {1.5, 2.7}. There are $2^2 = 4$ labellings to realise.
2. Cover both: 1 < x < 4. ✓
3. Cover neither: 0 < x < 1. ✓
4. Cover 1.5 only: 1 < x < 2. ✓
5. Cover 2.7 only: 2 < x < 4. ✓ So two points are shatterable.
6. Now take S = {x, y, z} with $x < y < z$. To cover {x, z} but not $y$ is impossible: any interval containing $x$ and $z$ must also contain $y$. ✗
7. The largest shatterable set has size 2, so VC(H) = 2.

2. Linear decision surfaces (the perceptron)

$X = \mathbb{R}^2$ and $H$ is the set of all lines. A line can shatter any 3 non-collinear points, realising all $2^3 = 8$ labellings, but it cannot shatter 4 points - an XOR-like layout defeats it. Therefore VC(H) = 3.

The XOR labelling of four points defeats every straight line, so a line cannot shatter four points. VC(H) = 3 for lines in the plane.

$$VC(\text{linear surfaces in } \mathbb{R}^r) = r + 1$$

That is the perceptron with $r$ inputs.

3. Conjunction of up to 3 boolean literals

Take S = {x₁ = 100, x₂ = 010, x₃ = 001}. To realise a given dichotomy, add the literal $\neg l_i$ for every $x_i$ you want to exclude. For example, to include $x_2$ while excluding $x_1$ and $x_3$, use $\neg l_1 \wedge \neg l_3$. This set of 3 is shatterable, so VC(H) = n - here 3 - for conjunctions of up to $n$ literals.

⚠GotchaThe slide states this rule backwards

The source sentence reads "to realize a dichotomy including $x_i$, add literal $\neg l_i$", which contradicts the example printed immediately after it. Its own example is the correct one, and it is the version used above: $\neg l_i$ excludes $x_i$. Verify it on the numbers - $\neg l_1 \wedge \neg l_3$ demands bit 1 = 0 and bit 3 = 0, so it rejects $x_1 = 100$ and $x_3 = 001$ and accepts $x_2 = 010$, which is exactly the dichotomy that was wanted.

4. The sine wave

For $h(x) = a \cdot \sin(bx)$, VC = ∞ with only 2 parameters. By choosing the phase and period carefully it can shatter almost any set of one-dimensional points.

⚠GotchaVC dimension is not the parameter count

The sine wave has two parameters and infinite VC dimension. VC dimension measures the true power or capacity of a model class, not how many knobs it exposes.

VC dimension, model complexity and generalization

≡FactsWhat VC dimension is a property of

• VC dimension does not depend on the training set. It is a property of the model class.
• A model class that can learn any labelling of $n$ random points is too powerful and will overfit. VC dimension is the maximum $n$ it can shatter for all labellings.

The generalization bound, from the alternate VC deck:

$$\text{testingError} \le \text{trainingError} + f(n, h, p)$$

Symbol	Meaning
n	size of the training set
h	model complexity, i.e. the VC dimension
p	the probability that the bound fails

✓Best practicePick the complexity that minimises the bound

Choose the model complexity that minimises the bound. In practice the bound is often loose, so treat the theory as insight, not as a magic recipe for model selection.

◎Exam cueThe take-away lesson

• If $H$ is very big relative to $n$, a low training error probably means you got lucky - that is overfitting.
• If $H$ is sufficiently constrained, or $n$ is large, then a low training error is good evidence of low generalization error.

≡FactsSample complexity via VC

For infinite $H$ there is an alternative bound on $m$ expressed in terms of VC(H) instead of $\ln|H|$: the VC dimension simply replaces the size of the hypothesis space in the sample-complexity formula.