Linear regression in an ML setting
Goals
- Express ordinary least squares as loss minimization for IID data
- Discuss the advantages (but arbitrariness) of squared error
- Compare empirical and population losses
- Show consistency of OLS when we can use the LLN
Ordinary least squares under misspecification
Suppose we observe IID data,
\[ \mathcal{D}:= \left\{ (\boldsymbol{x}_n, y_n) \textrm{ for }n=1,\ldots,N \right\}. \]
Later, we expect to observe one (or more) values \(\boldsymbol{x}_\mathrm{new}\), but not the corresponding \(y_\mathrm{new}\). We’ll assume (tentatively) that the pair \((\boldsymbol{x}_\mathrm{new}, y_\mathrm{new})\) come from the same distribution as the data, and are independent of the data. But for now, let’s think about the OLS estimator,
\[ \hat{\boldsymbol{\beta}}= (\boldsymbol{X}^\intercal\boldsymbol{X})^{-1} \boldsymbol{X}^\intercal\boldsymbol{Y} \]
under the assumption only of IID pairs of \((x_n, y_n)\) and that certain moments exist (specifically that all covariances are finite, and \(x_n\) has an invertible covariance matrix, but we won’t worry too much about technical conditions for now).
You might be used to making an assumption about \(y_n\) that looks something like
\[ y_n = {\boldsymbol{\beta}_{\mathrm{true}}}^\intercal\boldsymbol{x}_n + \varepsilon_n \textrm{ for }\varepsilon_n \overset{\mathrm{IID}}{\sim}\mathcal{N}\left(0,\sigma^2\right) \quad \leftarrow \textrm{ We do not assume this!} \]
Now we have no such assumption! In particular, there is no “true” \(\boldsymbol{\beta}_{\mathrm{true}}\) to estimate. We can still define mean zero “residuals” as
\[ \varepsilon_n := y_n - \mathbb{E}_{\vphantom{}}\left[y| \boldsymbol{x}_n\right] \quad\Leftrightarrow\quad y_n = \mathbb{E}_{\vphantom{}}\left[y| \boldsymbol{x}_n\right] + \varepsilon_n, \]
but there is no reason to believe the function \(\mathbb{E}_{\vphantom{}}\left[y| \boldsymbol{x}_n\right]\) is linear in \(\boldsymbol{x}_n\). We might say that our regression model is misspecified in the sense the we are fitting a model of the form that does not match the actual process that generated the data.
Some things that you may have learned about OLS in introductory classes are no longer true under misspecification. The big one is the (now fals) assertion that \(\hat{\boldsymbol{\beta}}\sim \mathcal{N}\left(\boldsymbol{\beta}_{\mathrm{true}}, \sigma^2 (\boldsymbol{X}^\intercal\boldsymbol{X})^{-1}\right)\). There are a lot of things wrong with this one:
- There is no such thing as \(\boldsymbol{\beta}_{\mathrm{true}}\)
- There is no reason to think that \(\mathrm{Var}_{\,}\left(\varepsilon_n\right)\) is a constant \(\sigma^2\) that does not depend on \(\boldsymbol{x}_n\) (heteroskedasticity)
- This derivation relies on \(\varepsilon_n\) being normal, but \(\varepsilon_n\) can have essentially any distribution (we assume it has finite variance though)
- \(\boldsymbol{X}\) is actually random here (they too are IID), and so it cannot be a parameter in a distribution. (Typically this formula is derived conditional on \(\boldsymbol{X}\).)
Similarly, you might have learned that “OLS is unbiased,” meaning \(\mathbb{E}_{\vphantom{}}\left[\hat{\boldsymbol{\beta}}\right] = \boldsymbol{\beta}_{\mathrm{true}}\). This no longer makes sense, again because there is no \(\boldsymbol{\beta}_{\mathrm{true}}\). But even the predictions are biased. Taking \(\hat{\boldsymbol{Y}}:= \boldsymbol{X}\hat{\boldsymbol{\beta}}\), we see that
\[ \mathbb{E}_{\vphantom{}}\left[\hat{\boldsymbol{Y}}\right] = \mathbb{E}_{\vphantom{}}\left[\boldsymbol{X}(\boldsymbol{X}^\intercal\boldsymbol{X})^{-1} \boldsymbol{X}^\intercal\boldsymbol{Y}\right] = \mathbb{E}_{\vphantom{}}\left[\boldsymbol{X}(\boldsymbol{X}^\intercal\boldsymbol{X})^{-1} \boldsymbol{X}^\intercal\mathbb{E}_{\vphantom{}}\left[\boldsymbol{Y}| \boldsymbol{X}\right]\right], \]
which does not equal \(\mathbb{E}_{\vphantom{}}\left[\boldsymbol{Y}\right]\) in general. It’s even worse: the expectation of \(\hat{y}_{\mathrm{new}}\) at an IID draw \(\boldsymbol{x}_{\mathrm{new}}\) is not unbiased either:
\[ \mathbb{E}_{\vphantom{}}\left[\hat{y}_{\mathrm{new}}\right] = \mathbb{E}_{\vphantom{}}\left[\boldsymbol{x}_{\mathrm{new}}^\intercal\hat{\boldsymbol{\beta}}\right] = \mathbb{E}_{\vphantom{}}\left[\boldsymbol{x}_{\mathrm{new}}\right]^\intercal\mathbb{E}_{\vphantom{}}\left[(\boldsymbol{X}^\intercal\boldsymbol{X})^{-1} \boldsymbol{X}^\intercal\boldsymbol{Y}\right], \]
and since the rightmost expression is no longer a true \(\boldsymbol{\beta}_{\mathrm{true}}\), this has no guaranteed relation to \(\mathbb{E}_{\vphantom{}}\left[y_{\mathrm{new}}\right]\).
So what can we say? Assuming covariances are finite, we can apply a LLN, so that
\[ \frac{1}{N} \boldsymbol{X}^\intercal\boldsymbol{X}\rightarrow \mathbb{E}_{\vphantom{}}\left[\boldsymbol{x}\boldsymbol{x}^\intercal\right] \quad\textrm{and}\quad \frac{1}{N} \boldsymbol{X}^\intercal\boldsymbol{Y}\rightarrow \mathbb{E}_{\vphantom{}}\left[\boldsymbol{x}y\right], \]
and so (by the continuous mapping theorem if \(\mathbb{E}_{\vphantom{}}\left[\boldsymbol{x}\boldsymbol{x}^\intercal\right]\) is invertible),
\[ \hat{\boldsymbol{\beta}}\rightarrow \mathbb{E}_{\vphantom{}}\left[\boldsymbol{x}\boldsymbol{x}^\intercal\right]^{-1} \mathbb{E}_{\vphantom{}}\left[\boldsymbol{x}y\right]. \]
This is a mysterious expression. In order to give it meaning, let us consider the more general problem of empirical risk minimization. We will see at the end that this is actually quite a good quantity for \(\hat{\boldsymbol{\beta}}\) to converge to.
Regression as risk minimization
Let us step back. Ultimately, we want to guess \(y_\mathrm{new}\), for which we want a function \(f(\boldsymbol{x}_\mathrm{new})\). We hope \(\hat{y}_\mathrm{new}:= f(\boldsymbol{x}_\mathrm{new})\) is “close” to \(y_\mathrm{new}\).
What does “close” mean? There are many choices for measuring a “distance” between \(\hat{y}_\mathrm{new}\) and \(y_\mathrm{new}\). Here are a few:
- \(|\hat{y}_\mathrm{new}- y_\mathrm{new}|\)
- \(|\hat{y}_\mathrm{new}- y_\mathrm{new}|^2\)
- \(|\hat{y}_\mathrm{new}- y_\mathrm{new}|^4\)
- \(\exp\left(|\hat{y}_\mathrm{new}- y_\mathrm{new}|\right)\)
- \(\mathrm{I}\left(|\hat{y}_\mathrm{new}- y_\mathrm{new}| > 1\right)\)
- \(\mathrm{I}\left(|\hat{y}_\mathrm{new}- y_\mathrm{new}| \ne 0\right)\)
In this course, \(\mathrm{I}\left(z\right)\) will always be the “indicator function” taking value \(0\) when \(z\) is false and \(1\) when \(z\) is true.
Describe in ordinary language the implications of using each of the following loss functions.
Whichever one we choose, we’ll define the “loss” of guessing \(\hat{y}\) when the true value was is \(y\) as \[ \mathscr{L}(\hat{y}, y) = \mathscr{L}(f(\boldsymbol{x}), y) \]
We want to find \(f(\cdot)\) so that \(\mathscr{L}(f(\boldsymbol{x}), y)\) is as small as possible. But the loss for a particular \(f\) may depend on \(\boldsymbol{x}_\mathrm{new}\), since different \(\boldsymbol{x}_\mathrm{new}\) are associated with different distributions of \(y_\mathrm{new}\). It follows that it doesn’t make sense to minimize the loss — instead we want to minimize the risk,
\[ \begin{aligned} \mathscr{R}(f) :=& \mathbb{E}_{\vphantom{}}\left[\mathscr{L}(f(\boldsymbol{x}), y)\right] & \textrm{(Risk)}. \end{aligned} \]
In optimization, the quantity you minimize is commonly called a “loss function”. Here, we use the term “loss function” in the ML sense to measure the discrepancy between a prediction and the truth. Then we take an empirical or population average to form a risk, which in turn becomes a “loss function” in the optimization sense when we try to minimize it. This double use of “loss” is as ubiquitous as it is unfortunate. All we can do is be aware of it and keep an eye on the context to avoid abiguity.
So we would like to find
\[ f^{\star}(\cdot) := \underset{f}{\mathrm{argmin}}\, \mathscr{R}(f) = \underset{f}{\mathrm{argmin}}\, \mathbb{E}_{\vphantom{}}\left[\mathscr{L}(f(\boldsymbol{x}), y)\right]. \]
The \(\underset{\,}{\mathrm{argmin}}\,\) operator finds the argument that minimizes a function, as opposed to the actual minimum, which is returned by \(\min{\,}\). For example
\[ \min{x}{(x - 3)^2 + 4} = 4 \quad\textrm{and}\quad \underset{x}{\mathrm{argmin}}\,{(x - 3)^2 + 4} = 3, \]
since the function \((x - 3)^2 + 4\) is minimized at the \(\underset{\,}{\mathrm{argmin}}\,\) value \(x= 3\), at which point it takes the \(\min{\,}\) value \(4\).
The notation \((\cdot)\) in \(f^{\star}(\cdot)\) emphasizes that the object \(f^{\star}\) is a function. At times I may omit it and simply write \(f^{\star}\) (for example). In contrast, I will (try) to write \(f^{\star}(x)\) only for the function \(f^{\star}\) evaluated at a particular value \(x\).
The problem with this definition of \(f^{\star}\) is that we don’t actually know how to compute \(\mathscr{R}(f)\), since we don’t know the joint distribution of \(\boldsymbol{x},y\). In this class, we will extensively use and study the empirical risk,
\[ \hat{\mathscr{R}}(f) := \frac{1}{N} \sum_{n=1}^N\mathscr{L}(f(\boldsymbol{x}_n), y_n). \]
By the law of large numbers, for any particular \(f\), we might expect that \(\hat{\mathscr{R}}(f) \approx \mathscr{R}(f)\):
\[ \hat{\mathscr{R}}(f) \rightarrow \mathscr{R}(f) \quad\textrm{for a particular $f$, by the LLN}. \]
But that is not enough, since what we want is for
\[ \underset{f}{\mathrm{argmin}}\, \hat{\mathscr{R}}(f) \approx \underset{f}{\mathrm{argmin}}\, \mathscr{R}(f). \]
For example, what if \(\mathscr{R}(f') = \mathscr{R}(f)\), but, at a particular \(N\), \(\hat{\mathscr{R}}(f')\) is systematically lower than \(\hat{\mathscr{R}}(f)\)? This can happen when the function \(f'\) overfits the randomness in the dataset at hand.
One of the key themes of statistical machine learning, and of this class, is when and why \(\hat{\mathscr{R}}\) is an appropriate proxy for \(\mathscr{R}\).