VC Dimension & Computational Learning Theory: Why Some Models Generalize
Every practical rule of thumb this track has given about model complexity has a formal justification. This is it.
Advanced
TopNotchNote
Notes that matter
the question every model in this track has quietly assumed
Every page so far has treated "low error on held-out validation data" as a stand-in for
"will perform well in production." Train/Test Splits &
Cross-Validation justified this empirically — measure it and see. Computational learning
theory asks a more fundamental question: under what conditions is a model that fits its
training data well mathematically guaranteed to generalize to new data, and how much data does
that guarantee actually require? The answer runs through a single idea: how expressive is
the family of models being searched, in the first place.
hypothesis class: the space of models being searched
A hypothesis class is the full set of candidate models a learning
algorithm is allowed to choose from. For logistic
regression on the CI data, the hypothesis class is "every possible straight-line decision
boundary through the feature plane" — training doesn't invent new shapes of boundary, it just
searches within that class for the one line that fits best. For a decision tree capped at
depth 3, the hypothesis class is "every tree with at most 3 levels of splits." Training always
means picking one specific hypothesis out of a fixed class; the size and richness of that
class is what this page is actually about.
shattering: how expressive is a hypothesis class?
A hypothesis class shatters a set of points if it can achieve every
possible way of labeling them. Take 3 CI-run points plotted by two features, positioned so no
one of them sits exactly on the line through the other two. There are
2³ = 8
possible ways to label them pass/fail, and for every single one of those 8 labelings, some
straight line correctly separates the passes from the fails. Straight lines shatter this set
of 3 points.
Now take 4 points arranged as the corners of a quadrilateral, and label the two points on
one diagonal "fail" and the two points on the other diagonal "pass" — an X-shaped labeling. No
straight line can separate that: any line has passes and fails interleaved around both sides.
Straight lines cannot shatter every set of 4 points, no matter how those 4 points are
arranged.
VC dimension: the size of the largest shatterable set
The VC dimension (Vapnik-Chervonenkis dimension) of a hypothesis class is
the size of the largest point set it can shatter. Straight-line classifiers on two features
have VC dimension 3, from the example above; more generally, linear classifiers on
d features have VC dimension d + 1. It's a single number that
captures how expressive — how much it can "memorize" arbitrary labelings — a hypothesis class
really is, independent of any specific dataset.
why VC dimension predicts generalization
This is where the theory connects back to something this track has already worked with
extensively. The PAC (Probably Approximately Correct) learning framework
proves generalization bounds of roughly this shape: with high probability, the gap between
training error and true error shrinks as the number of training examples grows, and grows as
the hypothesis class's VC dimension grows. Put plainly — a hypothesis class capable of
shattering large point sets is also capable of fitting large amounts of pure noise, which is
exactly what an unconstrained decision tree does when grown
without a depth limit: nothing formally stops it, so its effective VC dimension is
essentially unbounded, and the amount of data needed to trust its training error as a good
estimate of its real-world error grows without limit right along with it.
connecting VC dimension to what's already in this track
Nearly every "avoid overfitting" knob covered so far is, in this framing, a way of
explicitly throttling a hypothesis class's effective VC dimension rather than an arbitrary
trick:
| Where this track already covered it | What it's really doing to VC dimension |
|---|---|
| Decision Trees — max depth / min samples per leaf | caps how many distinct labelings the tree family can represent at all |
| Regularization — lambda | shrinks the effective size of the weight space being searched, even though the raw hypothesis class (all linear boundaries) stays the same |
| Support Vector Machines — C and gamma | controls how tightly the boundary can bend, i.e. how close the effective hypothesis class gets to something with unbounded VC dimension |
Every one of those was introduced as a practical fix for overfitting in
Overfitting vs Underfitting. VC dimension is the
formal vocabulary underneath "more model capacity needs more data to trust" — not a new rule,
but the proof that the rule already being followed throughout this track was never just
folklore.
the limits of this theory in practice
Worth being honest about where this framework stops being directly useful. Exact VC
dimension is only cleanly computable for simple hypothesis classes like linear models — for a
deep neural network with millions of parameters, the classical VC dimension is astronomically
large, and the classical bounds it implies would predict the network should badly overfit long
before it actually does in practice. Modern deep learning routinely violates the naive
intuition this theory suggests, which is an active area of research, not a settled question.
VC dimension's real value on this track is conceptual — it's the rigorous justification behind
every practical capacity-control knob covered so far, not a number anyone actually computes
and plugs into a formula before training a real model.
where to go from here
Overfitting vs Underfitting,
Regularization, and Decision
Trees — the practical rules this page supplies the theory behind.
Next in this track, the last page: Instance-Based Learning — k-NN and the curse of dimensionality.
Next in this track, the last page: Instance-Based Learning — k-NN and the curse of dimensionality.