Regression
One summer in college, I scooped ice cream at a stand that threw away melted inventory every night. The owner’s ordering strategy was to look at the sky, mutter, and guess. Some days we ran out by noon; other days we poured gallons of mint chip into the dumpster. He was solving, badly, the problem this unit solves well: predict tomorrow’s sales from what you can observe today.
Welcome to the Linear Models unit, where the machine learning begins. The last unit introduced probability and linear algebra; this unit uses both, starting with regression. The unit begins with its main question:
Under squared error, the best possible prediction is the conditional mean, and even that prediction has irreducible error.
Supervised Learning
In supervised learning, we observe examples that have already been labeled with the right answer, and our job is to predict the labels of examples we have not seen. Concretely, we are given a dataset of \(n\) data points: \[ (\mathbf{x}^{(1)}, y^{(1)}), \; (\mathbf{x}^{(2)}, y^{(2)}), \; \ldots, \; (\mathbf{x}^{(n)}, y^{(n)}), \] where each \(\mathbf{x}^{(i)} \in \mathbb{R}^d\) is a vector of \(d\) features (the measurements we get to observe) and each \(y^{(i)} \in \mathbb{R}\) is the label (the answer we want to predict). The goal is to learn a function \(f: \mathbb{R}^d \to \mathbb{R}\) with \(f(\mathbf{x}) \approx y\) on new examples, not just on the data we were handed.
At the ice-cream stand, a feature vector might collect today’s temperature, the day of the week, and whether school is out; the label is the number of cones we will sell. For most of this unit we keep the example univariate (one feature, temperature) because we can draw it, and in that case we drop the boldface and write \(x\) for the single feature.
The type of the label splits supervised learning in two:
Regression: the label is a real number, such as cones sold, tomorrow’s temperature, or a house price.
Classification: the label is a category, such as spam or not spam, which digit is in the image, or which word comes next.
This lecture and the next four are about regression; classification arrives at the end of the unit and shares almost all of the machinery. Either way, we cannot yet say which function \(f\) is a good one, because we have not said where the labels come from.
The Best Possible Prediction
Suppose the entire joint distribution of \((X, Y)\) is known rather than estimated from a finite dataset. Its optimal predictor is the target every algorithm in this unit estimates.
The in-class exercise works it out on an example small enough to do by hand. At the stand, suppose the weather \(X\) is cloudy or sunny and the day’s sales \(Y\) are either \(10\) or \(30\) cones, with joint probabilities:
| \(Y = 10\) | \(Y = 30\) | |
| $X = $ cloudy | \(0.30\) | \(0.10\) |
| $X = $ sunny | \(0.15\) | \(0.45\) |
Compare a constant forecaster that ignores the sky with one that conditions on it. The best such constant under squared error is the overall mean (Problem 5 recovers this as a special case), and summing the table down each column gives the marginal distribution of \(Y\) and hence that mean: \[ \mathbb{E}[Y] = 10 \cdot (0.30 + 0.15) + 30 \cdot (0.10 + 0.45) = 10 \cdot 0.45 + 30 \cdot 0.55 = 21 . \] Its expected squared error is then the variance of \(Y\), since the variance is by definition the expected squared distance from the mean: \[ \mathbb{E}\big[(Y - 21)^2\big] = \mathrm{Var}(Y) = 0.45 \cdot (10 - 21)^2 + 0.55 \cdot (30 - 21)^2 = 54.45 + 44.55 = 99 . \]
But we can see the sky, and conditioning is exactly the tool for using it. Summing the table across each row gives \(\Pr(X = \text{cloudy}) = 0.4\) and \(\Pr(X = \text{sunny}) = 0.6\), and dividing each entry by its row sum gives the conditional distribution of \(Y\) within that kind of day. On cloudy days \(Y\) is \(10\) with probability \(0.30/0.4 = 0.75\) and \(30\) with probability \(0.10/0.4 = 0.25\); on sunny days the two probabilities swap. Averaging \(Y\) inside each row gives the two conditional means: \[ \mathbb{E}[Y \mid X = \text{cloudy}] = 10 \cdot 0.75 + 30 \cdot 0.25 = 15, \qquad \mathbb{E}[Y \mid X = \text{sunny}] = 10 \cdot 0.25 + 30 \cdot 0.75 = 25 . \] Now consider the predictor that answers \(15\) on cloudy days and \(25\) on sunny days. On a cloudy day its expected squared miss is the spread of \(Y\) around \(15\), and on a sunny day the spread around \(25\), so its overall error is the average of the two conditional variances, weighted by how often each kind of day occurs: \[ \begin{align*} \mathrm{Var}(Y \mid X = \text{cloudy}) &= 0.75 \cdot (10 - 15)^2 + 0.25 \cdot (30 - 15)^2 = 18.75 + 56.25 = 75, \\ \mathrm{Var}(Y \mid X = \text{sunny}) &= 0.25 \cdot (10 - 25)^2 + 0.75 \cdot (30 - 25)^2 = 56.25 + 18.75 = 75, \\ \mathbb{E}\big[\mathrm{Var}(Y \mid X)\big] &= 0.4 \cdot 75 + 0.6 \cdot 75 = 75 . \end{align*} \] Conditioning cut the error from \(99\) to \(75\), and the \(24\) it saved is exactly the variance of the conditional mean itself: \[ \mathrm{Var}\big(\mathbb{E}[Y \mid X]\big) = 0.4 \cdot (15 - 21)^2 + 0.6 \cdot (25 - 21)^2 = 14.4 + 9.6 = 24, \qquad 99 = 75 + 24 . \] A feature helps exactly as much as it swings the conditional mean around; the spread left inside a single kind of day is invisible to any predictor that sees only \(X\). What would the same split look like for a feature that pinned \(Y\) down exactly?
In the plot, each panel shows the conditional distribution of sales for one weather condition, with the conditional mean marked in black and the best constant guess \(21\) in gray. The constant sits between the two panels and is wrong in both, while the conditional mean moves with the evidence.
The regression function is the conditional mean of the label given the features: \[ f^*(x) = \mathbb{E}[Y \mid X = x] . \] It is the best possible predictor under squared error, and its expected squared error also has a name: \[ \mathbb{E}\big[(Y - f^*(X))^2\big] = \mathbb{E}\big[\mathrm{Var}(Y \mid X)\big] , \] the irreducible error, a floor that no model, however clever, and no dataset, however large, can get below. Problem 5 proves both facts in full generality with one add-and-subtract, and the floor it establishes reappears term for term when we decompose test error in the Methodology lecture.
The floor is an average of conditional variances, the spread of \(Y\) that survives after \(X\) is known, so it counts exactly the part of the label our features cannot see. It is a property of the joint distribution, not of the model or the dataset: it does not grow when the relationship is complicated, does not shrink when we collect more days, and drops only when we measure something new. Even the optimal forecaster has root mean squared error \(\sqrt{\mathbb{E}[\mathrm{Var}(Y \mid X)]}\). All of this rested on knowing the joint distribution, which is the one thing we never have.
Model Classes
Back in the real world we hold \(n\) samples from that distribution rather than the distribution itself, so we cannot compute \(\mathbb{E}[Y \mid X = x]\) from a formula we do not have. Worse, with finitely many points we cannot hope to recover an arbitrary function: infinitely many functions pass through any finite scatter.
With finite data, we restrict the search to a model class (also called a hypothesis class), a set \(\mathcal{F}\) of candidate functions. Each candidate \(f \in \mathcal{F}\) is a hypothesis about how features relate to labels. The course uses several model classes:
Constant functions: \(f(\mathbf{x}) = c\) for a single number \(c \in \mathbb{R}\), which is the mutter-and-guess strategy.
Linear functions: \(f(\mathbf{x}) = \langle \mathbf{w}, \mathbf{x} \rangle\) for a weight vector \(\mathbf{w} \in \mathbb{R}^d\), the star of this unit, with one parameter per feature.
Neural networks: compositions of linear maps and simple nonlinearities, the star of the next unit, with millions of parameters.
Choosing the class is a modeling decision: it encodes what we believe about the hidden function before seeing much data. A class that is too small cannot express the truth, since no straight line can climb and then sag the way the ice-cream curve does; we will see later in the unit what goes wrong when the class is too large. Committing to a class narrows the search to something finite-dimensional, but it does not select a hypothesis.
The Most Likely Function
Picture two curves fit to the same scatter of days: one a plausible guess at the truth, the other an elaborate curve that threads every point exactly. Under the plausible curve, the observed points are the kind of thing that would actually happen; under the curve that threads every point, the noise \(\eta\) would have had to land in a suspiciously cooperative pattern rather than at random.
The maximum likelihood principle says to select the hypothesis under which the observed data was most probable: \[ \hat{f} = \arg\max_{f \in \mathcal{F}} \; \Pr\big(y^{(1)}, \ldots, y^{(n)} \mid f\big) , \] where the probability is over the noise in each label with the features held fixed, and the hat marks \(\hat{f}\) as our estimate of the target function \(f\). Maximum likelihood will select functions for regression this week, classification in two weeks, and an agent playing games in the final unit. The demo puts three such curves against the same scatter and scores each by plausibility: the curve that threads every point wins on the data it was fit to and can still lose on the next batch, the trap the Methodology lecture is devoted to. The next step is to express that probability as a loss we can minimize.
Gaussian Noise and Squared Error
Next lecture writes down the probability of the dataset under Gaussian noise and takes its logarithm. The resulting objective is the average squared gap between predictions and labels. A loss function therefore encodes an assumption about the noise. Under squared error, the conditional mean is optimal and its remaining error is the part of the label the features cannot explain.