4.4 Cross-Validation

4.4.1 Cross-Validation

We spend some time developing theory to control the generalization error, \(\hat {\mathcal {L}}(\hat {f}) - \mathcal {L}(\hat {f})\). In practice, however, this theory is not useful because we cannot actually compute the complexity. More importantly, the worst-case bounds we computed appear in practice to be too loose and may suggest bad advice (see, e.g., Belkin et al. (2019)). In practice, we most often estimate the risk \(\mathcal {L}(\hat {f})\) using held-out data.

Recall that the estimator \(\hat {\mathcal {L}}(\hat {f}) = \frac {1}{N}\sum _{n=1}^{N} \mathcal {L}(\hat {f}(\boldsymbol {x}_n), y_n)\) is not considered a reliable estimator of \(\mathcal {L}(\hat {f})\) because \(\hat {f}\) is not independent of \((\boldsymbol {x}_n, y_n)\). But suppose we have an actual new dataset, \(\mathcal {D}_{\text {new}} = ((\boldsymbol {x}_1, y_1), \ldots , (\boldsymbol {x}_M, y_M))\). Then we could just estimate: \[ \hat {\mathcal {L}}_{\text {new}}(\hat {f}) \;\approx \; \frac {1}{M}\sum _{m=1}^{M} \mathcal {L}(\hat {f}(\boldsymbol {x}_m), y_m). \] This is a consistent estimate of \(\mathcal {L}(\hat {f})\) since we did not use \(\mathcal {D}_{\text {new}}\) to train \(\hat {f}\), and so \(\hat {f}\) is independent of \(\boldsymbol {x}_m, y_m\).

One might ask, if you had \(\mathcal {D}_{\text {new}}\), why didn’t you just use it to train \(\hat {f}\)? Conversely, you might imagine taking the data you do have, and splitting it (randomly) into a “training set” \(\mathcal {D}_{\text {train}}\) and a “test set” \(\mathcal {D}_{\text {test}}\), using only \(\mathcal {D}_{\text {train}}\) to compute \(\hat {f}\), and \(\mathcal {D}_{\text {test}}\) to estimate \(\hat {\mathcal {L}}_{\text {test}}(\hat {f})\) using the above formula. There are costs and benefits to doing this:

• You have less data to train \(\hat {f}\).
• You have a good estimate of \(\mathcal {L}(\hat {f})\).

Putting more data in \(\mathcal {D}_{\text {train}}\) ameliorates the first cost, at the risk of making your estimate of \(\mathcal {L}(\hat {f})\) worse.

A clever way to use nearly all the data to compute \(\hat {f}\) and still get a reasonable test set error is to repeat the above procedure many times, each time with a different test set.

As an extreme, let \(\hat {f}_{-n}\) denote an estimate of \(\hat {f}\) with the \(n\)-th datapoint removed. Since you have removed only one datapoint, we might hope that \(\hat {f}_{-n} \approx \hat {f}\), so we have paid little estimation cost. Of course, the estimate \[ \hat {\mathcal {L}}_{\text {test}}(\hat {f}_{-n}) \;=\; \mathcal {L}(\hat {f}_{-n}(\boldsymbol {x}_n), y_n) \] uses a single datapoint, and so is very variable, if nearly unbiased. However, we can do this for each datapoint and average the results to reduce the variance of the test error estimate. This is called the “leave-one-out CV estimator,” or LOO-CV: \[ \hat {\mathcal {L}}_{\text {LOO}} \;:=\; \frac {1}{N}\sum _{n=1}^{N} \mathcal {L}(\hat {f}_{-n}(\boldsymbol {x}_n), y_n). \] Of course, you can do the same thing leaving two points out, or three, or so on, giving “leave-\(k\)-out CV” estimators. In the extreme where you leave a fraction \(N/K\) points out, you get “\(K\)-fold” CV estimators.

How many should you leave out? There seems to be a striking lack of useful theory. The rules of thumb are:

• By leaving out more datapoints you “bias” your estimate if your estimate of \(\hat {f}\) depends strongly on how many datapoints you have.
• By leaving out more datapoints you reduce the “variance” of your estimate of \(\mathcal {L}(\hat {f})\) by making the test set larger.

So there appears to be a sort of meta-bias-variance tradeoff in the estimation of \(\mathcal {L}(\hat {f})\). Common practice is five- or ten-fold cross-validation.

4.4.2 Influence Function

The influence function estimates how the model parameters (or predictions) change when a training sample is slightly perturbed, without retraining.

Let the parameters \(\hat \theta \) minimize the empirical risk \(\hat \theta = \arg \min _{\theta } \frac {1}{n}\sum _{i=1}^{n} \mathcal {L}(z_i,\theta )\). Now upweight the \(i\)-th sample by a small \(\epsilon \), giving the perturbed optimizer \[ \hat \theta _{\epsilon ,z_i} = \arg \min _{\theta }\ \frac {1}{n}\sum _{j=1}^{n} \mathcal {L}(z_j,\theta )+\epsilon \,\mathcal {L}(z_i,\theta ). \]

Differentiating with respect to \(\epsilon \) at \(\epsilon =0\) yields the influence of this sample on the parameters, \[ \mathcal {I}_{\text {params}}(z_i) = \left .\frac {d\hat \theta _{\epsilon ,z_i}}{d\epsilon }\right |_{\epsilon =0} = -\,H_{\hat \theta }^{-1}\,\nabla _\theta \mathcal {L}(z_i,\hat \theta ), \] where \(H_{\hat \theta }=\frac {1}{n}\sum _{i=1}^{n}\nabla _\theta ^2 \mathcal {L}(z_i,\hat \theta )\) is the Hessian. Since deleting a sample corresponds to \(\epsilon =-\tfrac {1}{n}\), the parameter change from removal is approximately \(-\tfrac {1}{n}\,\mathcal {I}_{\text {params}}(z_i)\).

By the chain rule, the influence of a training sample \(z\) on the loss at a test point \(z_{\text {test}}\) is \[ \mathcal {I}(z,z_{\text {test}}) = -\,\nabla _\theta \mathcal {L}(z_{\text {test}},\hat \theta )^{\top }\, H_{\hat \theta }^{-1}\, \nabla _\theta \mathcal {L}(z,\hat \theta ). \] Intuitively, the more aligned the two gradients are after weighting by \(H_{\hat \theta }^{-1}\), the more the training sample \(z\) helps that prediction.