Recall the pipeline: labeled training data goes into a learning algorithm, which selects a trained model \(\hat f\) from a pool of models \(\mathcal{F}\). In Chapter 1.1 we built ordinary least squares (OLS):
The \(^{+}\) is new. We explain it next, and then we look at OLS from a completely different angle.
The equation we solved in Chapter 1.1, \[ X^\top X\, w_{\text{OLS}} = X^\top y, \] looks like a single equation, but \(X^\top X\) is a \((d+1) \times (d+1)\) matrix, so it is really \(d+1\) equations in \(d+1\) unknowns. To check the shape: \(X\) is \(n \times (d+1)\), so \(X^\top\) is \((d+1) \times n\), and \(X^\top X\) is \((d+1) \times (d+1)\).
This system always has a solution, but it may not have a unique one. Some of the equations can be redundant, in which case there are effectively fewer than \(d+1\) equations and infinitely many solutions. When \(X^\top X\) is invertible (equivalently, its columns are linearly independent), the solution is unique and equals \((X^\top X)^{-1} X^\top y\).
When \(X^\top X\) is not invertible, we have to make a design choice: which of the many solutions do we prefer? The standard answer is the pseudo-inverse \((X^\top X)^{+}\). It is always uniquely defined, and \((X^\top X)^{+} X^\top y\) picks out the solution with the smallest norm. If the inverse exists, the pseudo-inverse is just the inverse. So the formula above covers both cases, and it is what software returns when you ask for an OLS solution. We will see the idea of preferring small-norm solutions again in Chapter 1.3.
Setting the gradient to zero only finds a stationary point. We know it is a minimum because \(L\) is convex: a convex function looks like a bowl, with a minimum and no maximum. For a concave function the picture is flipped, and stationary points are maximizers.
There are two broad ways to select \(\hat f\) from \(\mathcal{F}\):
This chapter takes the second route. Our goal is to design a learning objective by defining a generative model on the labels.
A generative model describes how the data themselves are produced. In that sense it is more interpretable than a loss: instead of only asking for good predictions, it tells a story about where the labels came from.
Before going further, we need to decide what is random. We could treat the inputs, the labels and the parameter all as random. As a starting point, we treat only the labels as random:
For each \(x_i \in \mathbb{R}^{d+1}\), define a random variable \(Y_i\), the label of \(x_i\), by \[ Y_i := w^\top x_i + \varepsilon_i, \qquad \varepsilon_i \sim \mathcal{N}(0, 1). \]
In words: in an ideal world, the label of \(x_i\) would be exactly the linear model’s output \(w^\top x_i\). But measurements are noisy, so we add a random noise term \(\varepsilon_i\). With no reason to expect the noise to be biased in either direction, mean \(0\) is the natural choice. We set the variance to \(1\) to keep the algebra clean; a general variance \(\sigma^2\) gives the same result.
What is the distribution of \(Y_i\)? Here \(w^\top x_i\) is just a number, not a random variable, and adding a constant to a normal random variable shifts its mean and leaves its variance unchanged. So \[ Y_i \sim \mathcal{N}(w^\top x_i,\, 1). \] This is a special property of the normal distribution. In general, adding two random variables does not give a distribution with a clean closed form. The Gaussian assumption is not only reasonable, it also keeps the math tractable. That is worth remembering as a general design principle: a good modeling choice should reflect reality, and lead to something we can actually optimize.
We choose \(w\) to maximize the “probability” of observing the labels \(y_1, \dots, y_n \in \mathbb{R}\) that we actually collected. Assuming the data points are collected independently, \[ \text{Likelihood}(w) := p(y_1, \dots, y_n) = \prod_{i=1}^n p(y_i). \] The probability of observing all the labels at once is the product of the probabilities of observing each one.
The data are fixed, so this is a function of \(w\) alone: a different \(w\) gives a different value. That is why it is called the likelihood of \(w\). The learned parameters are \[ \operatorname*{argmax}_w \; \text{Likelihood}(w). \]
The \(Y_i\) are continuous, so \(p(y_i)\) is a probability density, not a probability. It can be greater than 1. Think of it as a scaled measure of how likely a value is.
As written, this does not look easy to maximize: it is a product of Gaussian densities. Yet the answer is something we have already seen.
\[ \operatorname*{argmax}_w \; \text{Likelihood}(w) = w_{\text{OLS}}. \]
So OLS has two interpretations:
Both lead to exactly the same solution.
To prove the theorem, we will rewrite the objective, without moving its maximizer, until it looks familiar. Consider any \(f : \mathbb{R}^d \to (0, \infty)\).
The first two say constants don’t matter. Think of each \(w\) as the label on a box, and \(f(w)\) as the value inside it. Adding the same constant to every box, or scaling every box by the same positive number, does not change which box holds the largest value, and argmax only asks which box.
The third holds because \(\log\) is strictly increasing: \[ f(w_1) > f(w_2) \iff \log f(w_1) > \log f(w_2). \] Applying \(\log\) reshapes the values but keeps their order, and order is all argmax cares about.
We will show that \[ \operatorname*{argmax}_w \log \text{Likelihood}(w) = \operatorname*{argmin}_w L(w), \quad\text{i.e.}\quad \operatorname*{argmax}_w \sum_{i=1}^n \log p(y_i) = \operatorname*{argmin}_w \|Xw - y\|^2. \] By the third fact, maximizing the log-likelihood is the same as maximizing the likelihood. Taking logs also turns the product into a sum, which is much easier to work with.
Since \(Y_i \sim \mathcal{N}(w^\top x_i, 1)\), its density is \[ p(y_i) = \frac{1}{\sqrt{2\pi}} \exp\!\Big(-\tfrac12 (y_i - w^\top x_i)^2\Big), \] so \[ \log p(y_i) = \text{constant} - \tfrac12 (y_i - w^\top x_i)^2. \] Summing over all data points, \[ \sum_{i=1}^n \log p(y_i) = \sum_{i=1}^n \Big(-\tfrac12 (y_i - w^\top x_i)^2\Big) + \text{constant} = -\tfrac12 \|Xw - y\|^2 + \text{constant}. \] Notice the familiar squared deviations \(y_i - w^\top x_i\) appearing. Therefore \[ \operatorname*{argmin}_w \|Xw - y\|^2 = \operatorname*{argmax}_w \Big(-\|Xw - y\|^2\Big) = \operatorname*{argmax}_w \sum_{i=1}^n \log p(y_i). \] The first step holds because minimizing a function is the same as maximizing its negative. The second drops the additive constant and the positive factor \(\tfrac12\), using the first two facts. \(\blacksquare\)
Here we treated \(w\) as fixed but unknown. What if \(w\) is also a random variable, with its own distribution? That leads to a different regression model, which we will connect to ridge regression in Chapter 1.3.