The Theory of Learning and Model Families

This builds on Learning from Examples, which set up supervised learning as function approximation, the decision tree as a first hypothesis space, and the training/validation/test discipline for measuring generalization. Those tools measure how well a hypothesis predicts; here we ask why prediction is possible at all, and then survey the hypothesis spaces beyond the decision tree.

The theory of learning: PAC learning and sample complexity

Cross-validation and the learning curve measure generalization; they do not explain it. The measurements are specific to one learner on one problem. Behind them sits a general question: how can we be sure a learning algorithm has produced a hypothesis that will predict correctly on inputs it has never seen — that $h$ is close to the unknown $f$ — when we do not know $f$? And how many examples does it take to be sure? These questions belong to computational learning theory.¹

The governing principle: any hypothesis that is seriously wrong will almost certainly be found out after a modest number of examples, because it will make a visibly wrong prediction on one of them. So any hypothesis that stays consistent with a sufficiently large training set is unlikely to be seriously wrong. Such a hypothesis is not guaranteed correct, but it is probably approximately correct — right on most inputs, most of the time. An algorithm that returns probably-approximately-correct hypotheses is a PAC-learning algorithm.

Like every theorem, a PAC theorem needs axioms to license a claim about the future from the past. The axiom here is the stationarity assumption from the previous section: future examples are drawn from the same fixed distribution $P(E)=P(X,Y)$ as past ones. We need not know that distribution, only that it does not drift. To keep the first analysis clean we also assume the true function $f$ is deterministic and lies inside the hypothesis space $\mathcal{H}$ being searched.

The error rate and the $\epsilon$-ball

For Boolean functions the natural measure is $0/1$ loss, and the error rate of a hypothesis is its expected generalization error under the stationary distribution:

In words, $error(h)$ is the probability that $h$ misclassifies a fresh example — exactly the quantity a learning curve estimates. Call $h$ approximately correct if $error(h)\le \epsilon$ for a small constant $\epsilon$. In the hypothesis space, the approximately correct hypotheses lie inside an $\epsilon$-ball around the true $f$, and everything outside it is the set of seriously-wrong hypotheses, ${\mathcal{H}}_{\text{bad}}$. The goal is to see enough examples that, with high probability, every hypothesis still consistent with the data lies inside the ball.

Deriving the sample-complexity bound

The argument in outline: a seriously wrong hypothesis is likely to misclassify any given example, so the probability that it survives many examples is small; sum that probability over every bad hypothesis and require the total to stay small, and a bound on the number of examples follows. Now the details.

Fix any seriously-wrong hypothesis $h_b\in {\mathcal{H}}_{\text{bad}}$, so $error(h_b)>\epsilon$. On a single example, $h_b$ agrees with the true label with probability at most $1-\epsilon$. Because the examples are drawn independently, the probability that $h_b$ agrees with all $N$ of them is at most

We do not want any bad hypothesis to survive. The probability that ${\mathcal{H}}_{\text{bad}}$ contains at least one hypothesis consistent with all $N$ examples is bounded, by the union bound, by the sum of the individual probabilities, and $|{\mathcal{H}}_{\text{bad}}|\le |\mathcal{H}|$:

Demand that this failure probability fall below a small confidence parameter $\delta$, so $|\mathcal{H}|(1-\epsilon {)}^N\le \delta$. Using the standard inequality $1-\epsilon \le e^{-\epsilon }$, it suffices that $|\mathcal{H}|e^{-\epsilon N}\le \delta$; taking logarithms and rearranging gives the bound.

Read the bound term by term. It grows as $1/\epsilon$ — halving the tolerable error doubles the examples. It grows as $\ln (1/\delta )$ — demanding ten times the confidence costs only an additive $\ln 10$, so confidence is cheap. And it grows as $\ln |\mathcal{H}|$ — the size of the hypothesis space enters only through its logarithm, which is why the bound is workable even for enormous spaces: $\ln |\mathcal{H}|$ is the number of bits needed to name a hypothesis, a far tamer quantity than $|\mathcal{H}|$ itself.

What the bound says about generalization

Now apply it to the space of all Boolean functions on $n$ attributes, where $|\mathcal{H}|=2^{2^n}$. Then $\ln |\mathcal{H}|=2^n\ln 2$, so the sample complexity grows as $2^n$ — but there are only $2^n$ possible examples to begin with. The theorem says that PAC-learning the class of all Boolean functions requires seeing nearly every possible input. The reason: the space of all functions is so rich that, for any set of $N$ examples, it contains equal numbers of consistent hypotheses predicting the next input positive and predicting it negative. Consistency with the seen data says nothing about the unseen. Unrestricted learning cannot generalize.

The escape is to restrict $\mathcal{H}$ so that $\ln |\mathcal{H}|$ is small — but not so much that the true $f$ is thrown out with it. AIMA notes three routes.² Bring prior knowledge to bear (the subject of knowledge-in-learning). Insist the algorithm return not merely some consistent hypothesis but a simple one, as decision-tree learning does — where finding simple consistent hypotheses is tractable, the sample-complexity results are better than a bare consistency analysis gives. Or restrict attention to a learnable subset of the full space, a language rich enough to hold a good approximation to $f$ yet small enough that $\ln |\mathcal{H}|$ stays polynomial. Decision lists with tests of at most $k$ literals — the class $k$-DL — are one such language: counting hypotheses gives $|k\text{-DL}(n)|=2^{O(n^k{\log }_2(n^k))}$, so $\ln |\mathcal{H}|$ is polynomial in $n$, and the sample complexity

is polynomial too. Any algorithm returning a consistent $k$-DL hypothesis therefore PAC-learns the class from a reasonable number of examples, for small $k$.

Infinite hypothesis spaces and the VC dimension

The $\ln |\mathcal{H}|$ bound has an obvious hole: it is vacuous when $\mathcal{H}$ is infinite. Linear separators in the plane, for instance, form a continuum — there are uncountably many — yet a single line clearly cannot fit arbitrary labellings, so some finite amount of data ought to suffice. An independent tradition in statistics, beginning with the uniform-convergence theory of Vapnik and Chervonenkis, supplies the missing measure.³ The idea is to count not hypotheses but the number of distinct labellings a hypothesis space can realize on a set of points. A set of points is shattered by $\mathcal{H}$ if, for every possible assignment of positive/negative labels to those points, some hypothesis in $\mathcal{H}$ realizes it. The VC dimension of $\mathcal{H}$ is the size of the largest set it can shatter.

Linear separators in two dimensions have VC dimension $3$: any three points in general position can be split every one of the $2^3$ ways by some line, but no four can (the labelling that puts the diagonal pairs in opposite classes — the XOR pattern — defeats every line). So a class can be uncountably infinite and still have a small VC dimension, and small VC dimension is what makes generalization possible.

The VC dimension completes the theory. Generalization is possible exactly when the hypothesis space is restricted enough — small $\ln |\mathcal{H}|$ in the finite case, small VC dimension in the infinite one — and the two measures formalize the same intuition that has run through the whole lesson: a hypothesis space flexible enough to fit anything predicts nothing, so learning requires choosing a space rich enough to hold the truth yet poor enough that a feasible number of examples determines it. This is Ockham's razor with a proof behind it.

A tour of model families

Decision trees are one hypothesis space; the rest of the lesson surveys the others that a practitioner reaches for, all of them answering the same generalization question with different machinery.

Linear regression and gradient descent

The oldest hypothesis space is the linear functions. A univariate linear function has the form $h_{\mathbf{w}}(x)=w_{1}x+w_0$, with weights $w_0,w_1$ to be learned. Linear regression fits the line that minimizes the squared loss summed over the training examples,

This loss is convex — a smooth bowl with a single global minimum and no local minima to get stuck in — so for the univariate case the minimizing weights have a closed form found by setting the partial derivatives to zero. The multivariate case, $h_{\mathbf{w}}(\mathbf{x})=\mathbf{w}\cdot \mathbf{x}$, likewise has the closed-form solution ${\mathbf{w}}^{\ast }=({\mathbf{X}}^{\top }\mathbf{X}{)}^{-1}{\mathbf{X}}^{\top }\mathbf{y}$.

Closed forms disappear once the loss is not quadratic, so the general tool is gradient descent: start anywhere in weight space and repeatedly step downhill, against the gradient of the loss, until convergence. The step size $\alpha$ is the learning rate. Differentiating the squared loss of a single example gives the update — reduce a weight when the prediction is too high, in proportion to the corresponding input:

Summing the update over all examples before stepping is batch gradient descent, which converges to the global minimum but is slow; stepping after each single example is stochastic gradient descent, often faster and usable online, though with a fixed $\alpha$ it can oscillate around the minimum rather than settle. In high dimensions, an irrelevant attribute may appear useful by chance and cause overfitting; the standard defense is regularization, with $L_1$ (sum of absolute weights) favored because it drives many weights exactly to zero and so produces a sparse model that discards attributes — much as pruning does for trees.

Linear classification and the perceptron

A linear function becomes a classifier by passing it through a threshold: the decision boundary is the hyperplane $\mathbf{w}\cdot \mathbf{x}=0$, and the hypothesis returns $1$ on one side and $0$ on the other. Data that a hyperplane can separate are linearly separable, and the boundary is a linear separator.

When the data are linearly separable, the perceptron learning rule finds a separator. For a single example it is the same update as linear regression, with $h_{\mathbf{w}}(\mathbf{x})$ now the thresholded output:

Applied one example at a time, this rule converges to a perfect separator whenever one exists.⁴ When the data are not separable it may never settle under a fixed $\alpha$, though a learning rate that decays as $O(1/t)$ restores convergence to a minimum-error solution. The perceptron's hard threshold has two flaws: the hypothesis is not differentiable, and it announces a fully confident $0$ or $1$ even for points a hair from the boundary. Softening the threshold to the logistic function $g(z)=1/(1+e^{-z})$ removes both — the output becomes a differentiable probability, gradient descent applies cleanly, and the resulting logistic regression converges far more reliably on noisy, non-separable data, which is why it remains one of the most popular classification methods. The perceptron is also the atom of a neural network: stack layers of these units and train them by gradient descent, and you have the model family that the deep-learning course develops in full.

Support vector machines

The perceptron finds a separator; which one it lands on depends on accidents of the update order, and many separators pass close enough to the data that nearby unseen points would be misclassified. The support vector machine picks a principled one — the maximum margin separator, the boundary as far as possible from the nearest examples on either side.⁵ The margin is the width of the empty corridor around the separator, and the few examples touching its edges are the support vectors; they alone determine the boundary, so an SVM often stores only a small fraction of the data.

The maximum-margin problem has a dual form in which the data enter only as dot products ${\mathbf{x}}_j\cdot {\mathbf{x}}_k$ between pairs of points. That opens the kernel trick. Data not separable in their original space are often separable after mapping into a higher-dimensional feature space $F(\mathbf{x})$ — project a circle of points into three dimensions and a plane can slice through it. The trick is that for many maps, the dot product $F({\mathbf{x}}_j)\cdot F({\mathbf{x}}_k)$ can be computed directly, as a kernel function $K({\mathbf{x}}_j,{\mathbf{x}}_k)$, without ever forming the high-dimensional vectors. Replacing every dot product with a kernel lets an SVM find a linear separator in a space of billions of dimensions while computing only in the original one — an arbitrarily wiggly boundary back in the input space, at linear cost. A soft margin further tolerates a few misclassified points, penalizing them by how far they intrude. These properties — maximum margin for generalization, kernels for nonlinearity, few support vectors for economy — make SVMs a strong default when no special structure is known.

Ensembles: bagging, random forests, and boosting

The last idea does not build a better single hypothesis; it combines many. An ensemble takes a collection of hypotheses and votes their predictions. The motivation is a probability calculation: if five independent hypotheses each err with probability $p$, a majority vote errs only when three or more do, which is far less likely — a $1$-in-$10$ individual error rate can become better than $1$-in-$100$.⁶ Real hypotheses are not independent, but as long as their errors are decorrelated, voting helps. An ensemble also enlarges the hypothesis space: three linear separators, combined, can carve out a triangular region no single line could express.

Bagging decorrelates by resampling: train each hypothesis on a different bootstrap sample drawn with replacement from the data, then average or vote their predictions.⁷ A random forest is bagging applied to decision trees, with an extra twist — each split considers only a random subset of the attributes — which decorrelates the trees further and yields one of the most reliable off-the-shelf classifiers.

Boosting decorrelates in sequence rather than in parallel, using a weighted training set. Start with equal weights and train $h_1$; then increase the weight of the examples $h_1$ got wrong and decrease the weight of those it got right, so the next hypothesis $h_2$ concentrates where its predecessor failed. Repeat for $K$ rounds and take a weighted vote, each hypothesis weighted by how well it performed. The specific algorithm AdaBoost has a striking property: if the base learner is even a weak learner — accuracy just above chance — AdaBoost drives the training error to zero for large enough $K$.

Boosting on decision stumps — trees with a single test — reaches high accuracy on the restaurant data, and as $K$ grows the test accuracy keeps improving after the training error has already hit zero. Ockham's razor warns against needless complexity, yet here added hypotheses help. One reading is that more hypotheses make the ensemble's margin between the classes more definite, which aids classification of new examples — a hint that the true measure of complexity is subtler than a raw count of parameters.

Learning after deep networks

AIMA's third edition treats deep learning as a footnote to the perceptron. The decade that followed inverted the picture: the models that now dominate perception and language are learned end to end, and two of the lesson's load-bearing ideas — handcrafted features, and the U-shaped bias-variance curve — need qualification in that regime. This section states, conservatively, what the canonical public work actually established, and points to the sibling deep-learning course for the machinery.

From feature engineering to representation learning

Every model family above takes the input features as given: the SVM computes dot products of whatever attributes you hand it, decision trees test them one at a time. For images, audio, and text, choosing those attributes was, for decades, the hard part of the job — edge detectors, colour histograms, hand-tuned acoustic features. Representation learning removes that step. A deep network stacks the perceptron of the previous section into many layers and learns, by gradient descent on the same squared or logistic loss, the features and the classifier at once; early layers discover low-level structure (edges, phonemes) and later layers compose it into the abstractions the task needs.⁸ The empirical break came in 2012, when Krizhevsky, Sutskever, and Hinton's convolutional network AlexNet cut the ImageNet top-5 error from roughly 26% to 16%, a margin that ended feature engineering as the default for vision.⁹ The learning problem is unchanged from the one stated at the top of this lesson — fit examples, generalize to new ones — but the hypothesis space is now a composition of millions of weights rather than a fixed kernel.

When the U-shaped curve breaks: double descent

The model-selection figure earlier in this lesson drew the validation error as a U: error falls, then rises as complexity grows past the sweet spot, and Ockham's razor tells you to stop at the bottom. Modern over-parameterized networks violate that picture, and the violation is now well documented. Belkin, Hsu, Ma, and Mandal characterized double descent: as model capacity increases past the point where the model can exactly interpolate the training data (the interpolation threshold), test error stops rising and begins a second descent, often reaching a new minimum below the classical sweet spot.¹⁰ Nakkiran and colleagues showed the same non-monotone curve as a function of model size, training time, and dataset size in deep networks.¹¹

Double descent does not repeal the generalization theory of this lesson — it says the raw parameter count is the wrong complexity measure, exactly the caution the boosting result hinted at. The effective complexity that the PAC and VC bounds care about is controlled by the implicit bias of gradient descent toward low-norm solutions, not by the number of weights. This is an area of active research, not a settled replacement for the U-curve, and the honest summary is that model selection by a validation set still works in practice; over-parameterized models simply have a second regime the classical curve never predicted.

Scaling laws

The final departure is quantitative. The learning curve of this lesson said accuracy rises with data and then plateaus. For large neural language models, Kaplan and colleagues found instead that test loss falls as a smooth power law in model size, dataset size, and compute, across several orders of magnitude with no plateau in the measured range.¹² Hoffmann and colleagues (the Chinchilla study) refined the tradeoff, showing that for a fixed compute budget model size and training tokens should grow in roughly equal proportion — many large models had been undertrained.¹³ These are empirical regularities, not theorems, and they hold in a regime AIMA's examples never reach, but they are why the practical answer to would more data help? shifted from check the learning curve to yes, predictably, for a long way. The mechanisms live in the deep-learning course; the point here is only that the generalization question this lesson posed remains the right question, while several of its classical answers acquired exceptions once models grew large.

The through-line

Every method across these two lessons answers the same question — how to fit the examples you have without overfitting them, so as to predict the ones you have not. Decision trees answer it with information gain and pruning; linear models with a convex loss and regularization; SVMs with a maximum margin and kernels; ensembles by voting decorrelated hypotheses. There is no universally best method — decision trees suit many discrete, possibly-irrelevant features; SVMs are a strong default on modest data; ensembles usually beat their components. The choices multiply from here: probabilistic learning recasts fitting as inferring a distribution, and reinforcement learning drops the labels entirely, learning from reward. The perceptron, softened and stacked, becomes the neural network that carries the same gradient-descent idea into the modern era. But underneath every one of them is the generalization problem stated at the top, and no amount of machinery makes it go away.