17 Validation

Two Cures for Overfitting

Overfitting occurs when a model fits the noise in the data rather than the underlying signal. There are two primary ways to combat this:

1. Regularisation: “Putting on the brakes” by adding a penalty to the error function to discourage overly complex models.
2. Validation: “Checking the bottom line” by using a separate data set to verify how well the model generalises to unseen data.

Note

While Regularisation estimates the “overfit penalty” to adjust the model, Validation directly estimates the total out-of-sample error $(E_{out})$.

The Model Selection Problem

In practice, we often have multiple models ${\mathcal{H}}_1,{\mathcal{H}}_2,\dots ,{\mathcal{H}}_M$ (e.g., linear, quadratic, or models with different regularisation parameters). Our goal is to select the one that will yield the lowest $E_{out}$

Why not use $E_{in}$ ?

Selecting a model bases on lowest in-sample error $(E_{in})$ is dangerous because $E_{in}$ is “contaminated”. Since the algorithm already used that data to pick the best hypothesis, the error rate will be optimistically biased and likely lead to overfitting.

The Ideal (but infeasible) Solution: $E_{test}$

The most accurate way is to select a model is using a fresh test set $(D_{test})$ that has never been seen by the training algorithm

• Hoeffding Guarantee: $E_{\text{out}}(g_{m^{\ast }})\le E_{\text{test}}(g_{m^{\ast }})+O\left(\sqrt{\frac{\log M}{N_{\text{test}}}}\right)$.
• The Catch: True test sets are usually unavailable during the development phase.

The Validation Mechanism

Validation bridges the gap by splitting the available data $D$ (of size $N$) into two sets:

• Training set ($D_{\text{train}}$): Size $N-K$. Used to learn the hypothesis $\bar{g}$.
• Validation set ($D_{\text{val}}$): Size $K$. Used to estimate $E_{\text{out}}$.

Statistical Properties of $E_{val}$

The validation error is the average error over the validation set:

$$E_{\text{val}}(\bar{g})=\frac{1}{K}\sum _{{\mathbf{x}}_n\in {\mathcal{D}}_{\text{val}}}e(\bar{g}({\mathbf{x}}_n),y_n)$$

• Mean: $E_{\text{val}}(\bar{g})$ is an unbiased estimate of $E_{\text{out}}(\bar{g})$, meaning its expected value is exactly the out-of-sample error: $\mathbb{E}[E_{\text{val}}(\bar{g})]=E_{\text{out}}(\bar{g})$.
• Variance: For classification, the variance is bounded by ${\sigma }_{\text{val}}^2\le \frac{1}{4K}$. As $K$ increases, the variance decreases, providing a more stable estimate.

Model Selection Process (Step-by-Step)

To pick the best model using validation, follow these steps:

1. Split the data: Divide your total $N$ samples into $D_{\text{train}}$ (size $N-K$) and $D_{\text{val}}$ (size $K$)
2. Train models: For each model ${\mathcal{H}}_m$, run the learning algorithm on $D_{\text{train}}$ to produce a hypothesis ${\bar{g}}_m$.
3. Evaluate: Calculate the validation error $E_m=E_{\text{val}}({\bar{g}}_m)$ for each model.
4. Select: Choose the model $m^{\ast }$ that has the minimum validation error.
5. Re-train (Crucial): Take the selected model ${\mathcal{H}}_{m^{\ast }}$ and train it on the entire dataset $D$ (all $N$ points) to produce the final hypothesis $g_{m^{\ast }}$.

Intuition

We re-train on all $N$ points because more data generally leads to a better model ($E_{\text{out}}(g_{m^{\ast }})\le E_{\text{out}}({\bar{g}}_{m^{\ast }})$).

Choosing the Validation Set Size $(K)$

Selecting $K$ involves a fundamental trade-off:

• Large $K$: Provides a very accurate estimate of $E_{\text{out}}$, but leaves too few points for training, resulting in a poor model ($\bar{g}$).
• Small $K$: Leaves plenty of data for training (making $\bar{g}$ similar to the final $g$), but the validation estimate becomes noisy and unreliable.
• Rule of Thumb: A common practical choice is $K=N/5$ (20% of data).

Cross-Validation

When data is scarce, we use cross-validation to maximise the utility of every data point.

Leave-One-Out ($K=1$)

• Every single point $(x_n,y_n)$ is used as a validation set once.
• You train the model $N$ times, each time on $N-1$ points.
• The cross-validation error is the average of these $N$ individual errors: $E_{\text{cv}}=\frac{1}{N}{\sum }_{n=1}^N{e}_n$.

$V$-Fold Cross-Validation

• Divide the data into $V$ equal folds (e.g., 10 folds).
• Each fold acts as the validation set once while the other $V-1$ folds are used for training.
• Heuristic: 10-fold cross-validation is generally preferred as it is less computationally expensive than Leave-One-Out but still provides a robust estimate.