50 Meetings 22-23: Model Selection and Aggregation

In the previous meeting, we saw that trees give us a rich family of piecewise-constant models. But a tree with more splits fits the data better and risks overfitting, while a tree with fewer splits is more stable but might miss real structure. How do we choose? That’s the model selection problem. The same question comes up whenever we have a family of models indexed by a complexity parameter—polynomial degree, number of basis functions, tree depth. Here we develop tools for making that choice.

Model Selection

Finite Models

Basically, we don’t use them. \[ \begin{align*} \model &= \{m(x)=x^T b : b \in \R^k\} && \text{ Linear model } \\ \model &= \{ \text{ increasing } \ m(x) \} && \text{ Monotone model } \\ \model &= \{ m(x) : \int_0^1 |m'(x)|dx \le B_{TV} \} && \text{ Bounded variation model } \\ \model &= \{ m(x) : \max_{x \in [0,1]}|m'(x)| \le B_{Lip} \} && \text{ Lipschitz model } \end{align*} \] All of them contain infinitely many curves.

But sometimes we fit finitely many models. After all, we don’t know which is best.

Polynomial models of different orders.
Increasing vs. decreasing vs. convex vs. concave models.
Bounded variation models for different bounds \(B_{TV}\) on total variation.
Lipschitz models for different bounds \(B_{Lip}\) on the Lipschitz constant.

And if we fit \(K\) models \(\model^1 \ldots \model^K\), we get \(K\) least squares estimators \(\hat \mu^1 \ldots \hat \mu^K\).

We can define a new, finite, model that contains these least squares estimators. \[ \model = \{ \hat \mu^1 \ldots \hat \mu^K \}. \] Choosing the best of these curves is the model selection problem.

Sample splitting

\[ \text{Is} \quad \model = \{ \hat \mu^1 \ldots \hat \mu^K \} \quad \text{ a model? } \]

Not in the sense that we’ve been discussing.
Yes, it’s a set of curves, but those curves are random.
They’re estimators. They depend on the outcomes \(Y_i\).
This breaks our analysis. But there is an easy fix!

Sample splitting

Split the data in half. \[ \underset{\text{first half}}{(X_1, Y_1) \ldots (X_n, Y_n)} \qquad \underset{\text{second half}}{(X_{n+1}, Y_{n+1}) \ldots (X_{2n}, Y_{2n})}. \]

Use the second half to fit our \(K\) models and get our \(K\) least squares estimators. \[ \hat\mu^k = \argmin_{m \in \model^k} \frac{1}{n}\sum_{i=n+1}^{2n} \{ Y_i - m(X_i)\}^2 \quad \text{ for } \quad k = 1 \ldots K. \]

These \(K\) curves go in our finite model \(\model\).
As far as the first half cares, the curves aren’t random.
There’s no dependence on the outcomes \(Y_i\) in the first half.

Using the first half, get least squares estimator \(\hat \mu\) based on this finite model. \[ \hat \mu = \argmin_{m \in \model} \frac{1}{n}\sum_{i=1}^n \{ Y_i - m(X_i)\}^2 \quad \text{ for } \quad \model = \{ \hat\mu^1 \ldots \hat\mu^K \}. \] This is close to the target \(\mu\) like we’ve proven, satisfying \[ \norm{\hat \mu - \mu}_{L_2(\Pn)} \le 4\sigma\sqrt{\log(K)/n} \quad \text{ with probability } \quad 1-1/K, \] … if the target \(\mu\) is in this finite model \(\model\). But it isn’t.

We almost know that this kind of model selection works. The problem is that \(\mu\) isn’t in this model, and our argument has assumed that it is.

But does it work?

Yes and no.
It won’t necessarily select a curve \(\hat \mu\) from \(\hat\mu^1 \ldots \hat\mu^K\) that’s close to \(\mu\).
There may not be any curve in this set that is close to \(\mu\).
But it will select one that’s almost as close as the closest one.
We’ll talk about this in Lab on Wednesday.

More precisely: if the best of our \(K\) candidates has squared error \(\varepsilon^2\) from \(\mu\), our selection procedure picks one with squared error at most \(\varepsilon^2 + C \log(K)/n\) for some constant \(C\). The \(\log(K)/n\) term is the cost of choosing. It grows with \(K\)—more candidates means more chance of overfitting—but slowly, and it shrinks with \(n\).

Least Squares Model Selection in Action

Choosing the best polynomial

Choosing the best polynomial.

Choosing the best BV regression

Choosing the best BV regression.

Choosing the best of both

Choosing the best of both.

Sample splitting works, but it’s wasteful: we throw away half the data for fitting and half for evaluation. Cross-validation improves on this by rotating which observations are held out. Instead of one split, we make several—each time fitting on most of the data and evaluating on the rest.

Cross-Validation

Cross Validation Worksheet

Consider the following data with three observations.

Our goal is to use leave one out cross-validation to choose between a linear regression model and a constant model for this data. Below we have plotted these data three times. The hollow point is the data that is “left out” for the cross-validation, which we will use as our test data.

Draw a constant model (i.e., flat line) for each of the three plots based on the non-left-out data.
Draw and calculate the residuals from the constant models to the left-out observation for each of the three plots.
Draw a linear regression line (i.e., line that doesn’t have to be flat) for each of the three plots based on the non-left-out data.
Draw and calculate the residuals from the linear models to the left-out observation for each of the three plots.

\[ \begin{array}{|c|p{3cm}|p{3cm}|p{3cm}|} \hline & A & B & C \\ \hline & & & \\ \text{Constant model } \hat{y}_{test} & & & \\ & & & \\ \hline & & & \\ \text{Constant model } y_{test} - \hat{y}_{test} \text{ (residual)} & & & \\ & & & \\ \hline & & & \\ \text{Linear model } \hat{y}_{test} & & & \\ & & & \\ \hline & & & \\ \text{Linear model } y_{test} - \hat{y}_{test} \text{ (residual)} & & & \\ & & & \\ \hline \end{array} \]

Based on the residuals you calculated, which model is preferred? The constant model or the linear regression model?

Aggregation: Combining Models

Instead of choosing between models, we can combine them. After cross-fitting \(K\) models, we have out-of-sample predictions \(\hat\mu^1(X_i) \ldots \hat\mu^K(X_i)\) for each observation \(i\). We can find the best linear combination of these predictions by running least squares one more time: \[ \hat\alpha = \argmin_{\alpha \in \mathbb{R}^K} \frac{1}{n}\sum_{i=1}^n \left\{ Y_i - \sum_{k=1}^K \alpha_k \hat\mu^k(X_i) \right\}^2. \] The aggregated predictor \(\hat\mu(x) = \sum_k \hat\alpha_k \hat\mu^k(x)\) can be better than any individual model. It’s important that we use out-of-sample predictions \(\hat\mu^k(X_i)\): if we used in-sample predictions, the aggregation would overfit to the training data just like model selection can.