Cross-Validation & Model Selection

Estimate generalization error and tune models with k-fold CV.

The idea

$k$-fold cross-validation is the standard method for estimating the error a model will make on new data. Training error cannot serve: fitting has already pulled the model toward those particular points, so training error runs low, and the more flexible the model, the lower it runs.

An honest estimate needs points the fit never saw. Holding some aside provides them, but at a cost: the held-out points no longer train the model, and the estimate depends on which points we chose. Cross-validation rotates the held-out set instead.

Algorithm.

Algorithm: k-Fold Cross-Validation Input: a training set, a model to assess, a fold count k Output: an estimate CV of the model's error on new data 1. split the data into k equal parts, the folds; i = 1 2. fit the model on every fold except fold i 3. E_i = the error this fit makes on fold i // fold i was never seen by this fit 4. if i < k, i = i + 1, go to step 2 5. return CV = (E_1 + ... + E_k)/k // the average of the k recorded errors

The procedure validates every point exactly once and trains on it $k-1$ times, and averaging over $k$ splits reduces the effect of any single unlucky division. Because $\mathrm{CV}$ estimates error on unseen data, we can compare it across models, or across settings of a tuning parameter, and select the one with the smallest $\mathrm{CV}$.

Ways to work on it

• Walkthrough. Folds, the averaged cross-validation estimate, and selecting the model that minimizes it.
• Practice. Compute the cross-validation estimate or fold size for a run.
• Hardest. The cost of leave-one-out validation, and choosing among models with nearly tied scores.

Not sure where to start? Take the ten-question placement test.