Learning From Data (Abu-Mostafa) — Book Notes

Authors: Yaser Abu-Mostafa (Caltech), Malik Magdon-Ismail, Hsuan-Tien Lin (2012)

The companion book to Abu-Mostafa’s Caltech course CS 156. Short (~200 pages), mathematically serious, and focused on one question most ML books skip: why is learning from data possible at all?

The Learning Problem

Setup: an unknown target function f maps inputs to outputs. You have a finite sample of data generated by f. Learning = choosing a hypothesis g from a hypothesis set H that approximates f well on data you haven’t seen.

The tension: you only ever measure performance on the sample (in-sample error, E_in), but you care about performance on new data (out-of-sample error, E_out).

Feasibility of Learning

A finite sample can’t tell you anything about f outside the sample — deterministically. The escape is probabilistic: Hoeffding’s inequality bounds the probability that in-sample frequency deviates far from out-of-sample probability.

The catch: Hoeffding applies to one fixed hypothesis. When you choose the best hypothesis from many, the bound degrades with the size of the hypothesis set. Learning is a trade-off:

• Small H → E_in tracks E_out well, but might not contain a good hypothesis
• Large H → probably contains a good hypothesis, but E_in becomes an unreliable estimate of E_out

VC Dimension

The book’s centerpiece. For infinite hypothesis sets, counting hypotheses fails — what matters is the growth function: how many distinct ways the hypothesis set can classify N points.

The VC dimension d_vc is the largest N the hypothesis set can shatter (classify in all 2^N ways). If d_vc is finite, the growth function is polynomial, and generalization is guaranteed with enough data.

Rule of thumb from the book: you need roughly N ≥ 10 × d_vc data points for decent generalization.

For a linear perceptron in d dimensions: d_vc = d + 1 — the number of parameters. More parameters, more data needed. This is the theoretical backbone of “model complexity.”

Bias-Variance

The other decomposition of generalization error:

• Bias: how far the average learned hypothesis is from the target. Driven by the hypothesis set being too simple.
• Variance: how much the learned hypothesis varies across different training samples. Driven by the hypothesis set being too flexible for the amount of data.

Matching model complexity to data resources, not target complexity, is the practical lesson.

Overfitting, Regularization, Validation

• Overfitting: fitting the noise. E_in keeps dropping while E_out rises. Driven by noise (stochastic and deterministic — the part of f your model class can’t express acts like noise).
• Regularization: constrain the fit (weight decay etc.) — accept a little bias to cut a lot of variance.
• Validation: hold out data to estimate E_out honestly. The moment you use validation data to make choices, it starts becoming training data — the book is precise about this budget.

Key Takeaways

• Learning is feasible only in probability, and only if you commit to your hypothesis set before seeing the data.
• Generalization depends on effective complexity (VC dimension), not parameter count per se.
• Data snooping is the cardinal sin — every decision made after looking at the data contaminates the guarantee.
• “If you torture the data long enough, it will confess.”

Why It Stuck With Me

Most practical ML education is recipes. This is the physics underneath — after it, you know why a validation set works, why more parameters demand more data, and why leakage silently destroys everything.