Cross-Validation

Cross-validation is a method to assess the performance of an algorithm by partitioning the training data into multiple subsamples. It helps avoid overfitting by ensuring the model is validated on unseen data, rather than being both trained and tested on the same points.

K-fold cross-validation

1. Randomly shuffle the dataset and split it into $k$ equally-sized subsets (“folds”).
2. For each fold $i$ (from $1$ to $k$):
       a. Train the model on all folds except fold $i$.
       b. Evaluate the validation error on fold $i$.
3. Average the $k$ validation errors to estimate the model’s generalization error.

This technique balances bias and variance:

• Lower $k$ (e.g., 5) runs faster but has higher bias.
• Higher $k$ (e.g., 10) gives a lower-bias estimate but takes more time.

Leave-One-Out Cross-Validation (LOOCV)

1. Special case of K-fold where $k=n$ (the number of data points).
2. For each data point $i$:
       a. Train the model on all data except point $i$.
       b. Evaluate the model on the single held-out point $i$.
3. Average all $n$ errors to get the overall validation score.

LOOCV provides an almost unbiased estimate of generalization error,
but is computationally expensive for large datasets since it requires $n$ training runs.