§5.2–5.2.1Capacity, Overfitting and Underfitting · The No Free Lunch Theorem

§5.2 The central challenge: generalization

Machine learning’s defining problem: perform well on new, previously unseen inputs — generalization generalization Performing well on new, unseen inputs — the gap between machine learning and mere optimization; measured as test/generalization error. defined in ch. 5 — open in glossary . Reducing training error is just optimization; machine learning begins when we also demand low generalization (test) error, the expected error on fresh draws from the input distribution, estimated on a held-out test set.

How can the training set tell us anything about the test set? Only under assumptions. The i.i.d. assumptions iid assumptions Examples are independent; train and test are identically distributed from the shared data-generating distribution p_data. defined in ch. 5 — open in glossary : examples are independent, and train and test are identically distributed — both generated by the same data-generating distribution $p_{\mathrm{data}}$. Then for a fixed model the expected training and test errors coincide; but since we choose the parameters using the training set and only then sample the test set, expected test error ≥ expected training error. Everything reduces to two abilities:

1. make the training error small — failing this is underfitting underfitting Training error itself is too high — the model can't fit the training set. defined in ch. 5 — open in glossary ;
2. make the gap between training and test error small — failing this is overfitting overfitting The gap between training and test error is too large — the model memorizes training quirks. defined in ch. 5 — open in glossary .

Capacity — the knob between the two failures

We steer between them with capacity capacity A model's ability to fit a wide variety of functions (hypothesis space size/identity); best matched to task complexity and data amount; generalization error is U-shaped in it. defined in ch. 5 — open in glossary : a model’s ability to fit a wide variety of functions. One way to set it is the hypothesis space hypothesis space The set of functions the learning algorithm may pick as its solution (e.g. all linear functions; all degree-9 polynomials). defined in ch. 5 — open in glossary — which functions the learner may pick. Linear regression’s space is all linear functions; adding features $x^2, x^3, \dots$ admits polynomials ($\hat{y} = b + \sum_{i=1}^9 w_i x^i$ for degree 9) — still linear in the parameters, so the normal equations keep working. Fig 5.2, live:

Degree 1 cannot capture the curvature (underfits); degree 2 matches the true structure and generalizes; degree 9 — with more parameters than training examples — threads every training point yet swings wildly between them: infinitely many wildly different solutions fit the data exactly, and we have little chance of picking one that generalizes. The right pane is fig 5.3’s U-curve: training error falls monotonically with capacity, generalization error falls then rises; between them the generalization gap widens past the optimal capacity.

Two refinements. Representational vs effective capacity: the model family defines what could be expressed, but imperfect optimization means the learner’s effective capacity may be less than the family’s representational capacity. And capacity isn’t only about how many functions — the identity of the functions matters (linear functions are great when the truth is near-linear, useless for $\sin(x)$).

Non-parametric models push capacity arbitrarily high: instead of a fixed-size parameter vector, their complexity grows with the data. Nearest-neighbor regression just stores the training set and answers with $y_i$ for the closest stored $\boldsymbol{X}_{i,:}$ — with tie-averaging, it achieves the minimum possible training error on any dataset. The ideal model — an oracle knowing the true $p(\boldsymbol{x}, y)$ — still errs when the mapping is inherently stochastic or $y$ depends on unobserved variables: that floor is the Bayes error bayes error The error an oracle knowing the true p(x,y) still makes — the irreducible noise floor. defined in ch. 5 — open in glossary .

§5.2.1 The no free lunch theorem

Inductive reasoning — inferring general rules from finitely many examples — is not logically valid; ML escapes by promising only probably correct rules about most members. Even so, the no free lunch theorem no free lunch theorem Averaged over ALL data-generating distributions, every classifier has the same error on unseen points — so seek algorithms for the distributions we actually meet. defined in ch. 5 — open in glossary (Wolpert, 1996) bites: averaged over all possible data-generating distributions, every classification algorithm has the same error rate on unseen points. The most sophisticated algorithm conceivable ties, on average, with predicting one constant class.

The escape is the point: the results hold only for the average over all distributions. Real-world distributions are special, and the goal of ML research is not a universal best algorithm but understanding which distributions the real world serves up — and which algorithms do well on those. That reframing motivates the entire next section: regularization, the art of building the right preferences in.