Lecture 8: Cross Validation and Data Splitting

DATA 311: Machine Learning

Dr. Irene Vrbik

University of British Columbia Okanagan

Introduction

# README
# 
# Irene, you should redo the pictures so that it is clear that the test set is still reserved when we do cross-validation

# GO back to the old pictures /lecture
# 1. train/test (bad cuz we peak)
# 2. train/test/validation (bad cuz only one example)
# 3. train(with cv)/test more stable
#
# k-fold more stable than loocv
#
# use something other than the cars data, it's too weird with it's discrete X
# and its not big enough to split into train and test first.
#
# we have a hacky way to estimate standard error of this estimate, but we'll get a better way to do this next class (bootsrap!)

• In this lecture we’ll be looking at a resampling method called cross validation (or CV for short)

• This technique will be used for validating/accessing our model by providing an estimate of model performance on unseen data (i.e. not used in training).

• By the end of this lecture, you should understand the difference between training, validation, and test datasets, the need for these splits, and how to implement CV.

• we have done this estimate before with a training/testing set, but as we will see, CV will have some benefits over this approach.
• Consequently, CV will be an indispensable tool for helping us choose between various modelling options.

Metrics for Model Assessment

For regression we aim to reduce the test MSE \[MSE = \frac{1}{m} \sum_{i=1}^m (y_i-\hat y_i)^2\]

For classification we may consider the test error rate \[\frac{1}{m} \sum_{i=1}^m I(y_i \neq \hat y_i)\]

Where \(1, \dots, m\) denotes unseen test observations that not used in the model-fitting process.

test error = misclassification rate of the error.

I use \(N\) to suggest that we want to minimize these for the population rather than just the sample we have on hand.

Recall

• Ideally, we could fit our model on a sample of data, and then compare the predictions from the estimated model on a very large data set (not used in fitting) to estimate the MSE¹.

• If we only have one sample, we often split it into a training set (used to fit the model) and testing set (used to estimate the test MSE).

• This train/test split approach is sometimes referred to validation approach.

we’ve used this approach before but i’ve never called it by this name: validation approach

1. We’ll start with MSE in the regression setting and see how these concepts can be extended to classification.

Training vs Test-set Performance

Recall: training error rate often is quite different from the test error rate [Image source]

• recall the diff between training and test error

• training error can dramatically underestimate test error.”

  • low = regression with a low number of predictors

  • high = large number of predictors

• for most models the training error will go down as complexity increases

• RIGHT: overfitting LEFT: underfitting

• Bias = how far off on average the model is from the truth
  Variance: how much the variance varies around its average

Validation Approach

Train/Test Split

set.seed(1234) # for reproducibility (eg. student number)
N = 200        # total number of obs. in our data set

# Randomly sample 80%/20% for training/testing
tr.ind <- sample(N, 0.8*N, replace=FALSE)
te.ind <- setdiff(1:N, tr.ind)

tr.ind

2, 3, 4, 6, 7, 8, 9, 10, 11, 14, …

te.ind

1, 5, 12, 13, 15, 18, 24, 31, …

In this case, we fit the model with samples with index tr.ind and estimate the MSE using samples with index te.ind

By now, we have experience splitting our data set randomly into non-overlapping training and testing sets:

Validation Approach

Train/Test Split

set.seed(67)   # for reproducibility (eg. student number)
N = 200        # total number of obs. in our data set

# Randomly sample 80%/20% for training/testing
tr.ind <- sample(N, 0.8*N, replace=FALSE)
te.ind <- setdiff(1:N, tr.ind)

tr.ind

1, 2, 3, 4, 6, 7, 8, 9, 11, 12, …

te.ind

5, 10, 21, 27, 28, 30, 34, 40, …

If we use a different seed, we get a different split.

By now, we have experience splitting our data set randomly into non-overlapping training and testing sets:

Validation Approach Schematic

A schematic display of the validation set approach. A set of N observations are randomly split into training set (shown in red, containing \(n\) observations 2,3,4,6,7,8,9,10,11,14,…, among others) and a validation set (shown in blue, containing \(m\) observation 1, 5, 12, 13, 15, 18, 24, 31, 33, among others). The ML method is fit on the training set, and its performance is evaluated on the validation set.

this is a one-stage process

Can you think of any limitations/issues with this this method?

ISLR Train Test Figure

jump forward to cross-validation approach

ILSR Fig 5.2 Compares linear vs. higher-order polynomial terms in Linear Regression Left: Validation error estimates for a single split into training (196 obs.) and validation (196 obs.) sets. Right: The validation method was repeated ten times, each time using a different random split of the observations into a training set and a validation set. This illustrates the variability in the estimated test MSE from this approach applied to the Auto data set.

• Compares linear vs. higher-order polynomial terms in Linear Regression
• comparing with validation approach (no resampling) the MSE test is highly variable
• the “best” model changes from split to split SEE NEON YELLOW (lowest curve)
• this approach tends to overestimate the test error rate since much of the data is hidden in the fitting process (maybe half)

Validation approach

• The dataset is split into two subsets: a training set and a validation set.

• The model is trained on the training set and evaluated on the validation set to tune the model’s hyperparameters.

• We are using the validation set both for tuning and evaluation, which can lead to biased performance estimates.

Validation Approach: some problems

• High Variance: Results depend heavily on how the data is split.

• Inefficient Use of Data: Less data is available for training, especially with small datasets.

• Single Evaluation: One run may not reflect true generalization.

• Data leakage: the model “learns” from data it shouldn’t have access to during training which may lead to overly optimistic performance estimates

• Overfitting Risk: The model may overfit to the validation set.

1. Since the model is evaluated on a single validation set, the performance estimate can vary significantly depending on how the data is split. Different random splits may yield different results, leading to unreliable estimates of model performance.

   • If the dataset is small or not well-balanced, a single unlucky split can make the model look much better or worse than it really is.

2. By splitting the data into just a training and validation set, you’re not using all available data for training. This is especially problematic with small datasets, where reducing the size of the training set can hurt model performance.

   • even wehn you are just performing cv just on your training set, you make fuller use of your training data:
   • you train and validate on multiple partitions instead of holding back a single validation set. — points are used both in training and validating. e.g. Each observation serves as validation once and as training four times.

3. The lack of a separate test set means the validation set is being used for both tuning and evaluation. This can lead to biased performance estimates, as the model may perform well on the validation set but poorly on new, unseen data.

4. You get only one point of evaluation for the model. This single validation score might not reflect the true performance, as it could be too high or too low purely by chance.

5. As the model is tuned using the validation set, there is a risk that the model may overfit to this specific data subset, making it less effective on truly unseen data.

   • You’re tailoring your model choice to the idiosyncrasies (noise) of one specific subset of data.

(Goodhart’s law) is an adage often stated as, “When a measure becomes a target, it ceases to be a good measure”.

Overall, these issues make the validation set approach less reliable compared to more robust methods like cross-validation or the train-validation-test split.

Multiple are needed to ensure that differences between models are not due to random variation in the test data.

Cross-Validation: The Solution

k-fold cross-validation

1. Split data into k folds.
2. Train on k−1 folds, validate on the remaining one.
3. Repeat k times and average errors.

K-fold Cross-Validation

Training\(_1\)

valid.\(_1\)

Training\(_2\)

valid.\(_2\)

Train\(_2\)

Training\(_3\)

valid.\(_3\)

Training\(_3\)

Training\(_4\)

valid.\(_4\)

Training\(_4\)

Training\(_5\)

valid.\(_5\)

Training\(_5\)

Training\(_6\)

valid.\(_6\)

Training\(_6\)

Train\(_7\)

valid.\(_7\)

Training\(_7\)

valid.\(_8\)

Training\(_8\)

we do not want to evaluate the candidate models once. Instead, we prefer to evaluate each model multiple times with different dataset and take the average score for our decision.

So in this case, we’d have 8 different runs, and each data point will have a turn at belonging to the validation set.

The trick of \(k\)-fold (k = 8 here) to resample the same dataset multiple times and pretend they are different.

K Iterations (K-Folds): The dataset is divided into k equal-sized “folds” (in this example, k = 8). Each fold is used as a validation set once, while the remaining folds are combined to form the training set.

• 1st iteration: The first fold (in blue) is used as the validation set, while the remaining folds are used for training the model. The performance of the model on this validation fold is recorded as Performance₁.
• 2nd iteration: The second fold is used as the validation set, and the others for training. This gives Performance₂.
• The process repeats for all folds (3rd, 4th, … 8th), each time using a different fold as the validation set, while the rest are used for training.

Key Takeaways:

• Each fold gets a chance to be used as both training and validation data, which provides a better estimate of the model’s ability to generalize to unseen data.
• This method helps reduce bias from a single split and variance by considering multiple data splits.

Steps of K-fold CV

Step 0: Divide dataset into \(k\) equal-sized “folds”; each fold is used as a validation set once, while the remaining folds form the training set

1. 1st iteration: The first fold (in blue) is used as validation set\(_1\), while the remaining folds are used for training the model. The performance of the model on this validation fold is recorded as Performance₁.

2. 2nd iteration: The second fold is used as validation set\(_2\), and the others for training. This gives Performance₂.

The process repeats for all \(k\) folds, each time using a different fold as the validation set, while the rest are used for training.

The image on the previous slide shows the process of \(k\)-fold cross-validation.

CV Performance

After completing all \(k\) iterations, the performances from each fold are averaged to get a more reliable estimate of the model’s performance across different subsets of the data. Source of image: [Zitao’s Web]

this cv estimate of error will be more reliable than the test set one we were doing earlier which just relied on one random split - plus it means we don’t have to peak at the test set yet!

Typical Workflow

1. Split data into training and test sets.
   
2. Use cross-validation on training data to:
   • Compare models (e.g., logistic vs KNN vs tree)
   • Tune hyperparameters (e.g., \(k\), \(\lambda\), depth)
3. Choose the model with lowest CV error.
   
4. Retrain on all training data.

Final model testing

• Once we have refitted the selected model on the non-test examples, we use the test dataset for unbiased final evaluation (e.g. \(MSE_{test}\) or test error)

• The test dataset, untouched until now, estimates model performance on unseen data and checks for overfitting¹.

The test dataset used for evaluation is independent from the validation sets we used in cross validation.

they are different because we do not want data leakage

Overfitting happens when a model performs exceptionally well on the training data but fails to generalize to new, unseen data. When we evaluate the model on the test dataset, it reveals whether the model has learned the underlying patterns or if it has simply memorized the training data.

1. If the performance on the test set is much worse than on the training/validation sets, it indicates that the model may be overfitting.

Summary of steps

1. Training Phase: Use Resampling Methods to obtain multiple training sets to train candidate models.
2. Model Evaluation: Instead of evaluating candidates once, evaluate each model multiple times with different validation sets.
3. Model Selection: Choose the best performing model based on the average validation scores.
4. Retrain: Combine training and validation sets (non-test set) for final training.
5. Final Model Testing: Evaluate the model’s performance on the test dataset

Average the scores to make a better decision.

Resampling Methods

• \(k\)-fold cross-validation (CV) is one of the most commonly used resampling methods

• Resampling methods involve repeatedly drawing samples from a dataset and training the model on different subsets of data to evaluate its performance.

• Another popular choose is Leave-one-out CV

• Next lecture we’ll discuss another resampling method called the bootstrap

The model is trained and validated on different “resampled” subsets of the data in each iteration, without the need to collect new data.

Today we focus on CV which can be used:

• to assess model performance (eg. estimate test MSE),
• perform model selection (eg. choose \(k\) for knn)
• model comparison (choosing between method 1 and 2)
• provide standard deviation and bias of our parameter estimates

• expensive because they involve fitting the same statistical method multiple times using different subsets of the training data.
• cv can be used to estimate the test error to eval performance
• The bootstrap is used in several contexts, most commonly to provide a measure of accuracy of a parameter estimate/learning method (estimate variance of estimators)

Leave One Out Cross-Validation

Leave One Out Cross-Validation (LOOCV) is a special case of \(k\)-fold CV; namely, where \(k\) equals the number of data points in the dataset.

1. The dataset is split into \(n\) folds, where \(n\) is the number of data points.

2. In each iteration, 1 data point is used as the validation set, and the remaining \(n-1\) data points are used as the training set.

• Unlike the validation approach, LOOCV systematically creates multiple training sets¹ of size \(n - 1\) each having a validation (i.e. testing) set with a single observation \((x_i, y_i)\)

• Unlike the validation approach the subsets will not be a comparable size but rather a single observation \((x_i, y_i)\) for the validation set, and the remaining observations making up the training set.

• hence we we are “holding out” one observation.

1. this method will split our data into training and validation set \(n\) times (where \(n\) is our sample size).

LOOCV approach

Full sample index (1, 2, … , 200) is systematically divided into:

	Index
CV Set	Training	Validation*
1	2, 3, 4, ..., 200	1
2	1, 3, 4, ..., 200	2
3	1, 2, 4, ..., 200	3
...	...	...
200	1, 2, 3, ..., 199	200

Rather than test set we may use “validation” or “hold-out” set

LOOCV Schematic

A schematic display of LOOCV. A set of n data points is repeatedly split into a training set (shown in red) containing all but one observation, and a validation set that contains only that observation (shown in blue). The test error is then estimated by averaging the n resulting MSE’s. The first training set contains all but observation 1, the second training set contains all but observation 2, and so forth.

• Notice how each CV set (i.e. each row) defines a non-overlapping partition of the data.

• IOW each observation is represented either in the training or validation set.

LOOCV Steps

Steps:

Create \(n\) training/validation sets, then for each set:

• Fit the model to the training set

• Use the fitted model to predict the responses for the (single) observation in the validation set.

• Record the validation set error.

The final performance is the average of the performance scores from each iteration.

CV Estimation

• If our response is quantitative, our validation set error can be assessed using the MSE.

• For LOOCV the MSE corresponds to a single left out observation \(x_i\) will be defined as \(MSE_i = (y_i-\hat y_i)^2\) where \(\hat y_i\) is the prediction found from the \(i^{th}\) fitted model.

• We can then estimate the MSE of the model using \[CV_{(n)} = \frac{1}{n} \sum_{i=1}^n MSE_i\]

\((n)\) in the subscript denotes how many CV/validation sets we have

LOOCV Steps Visualized

Training Set	Prediction	Metric \(MSE_i\)
2,3,4, …, 199, 200	\(\hat y_1 = \hat f_{1}(x_1)\)	\((y_1 - \hat y_1)^2\)
1,3,4, …, 199, 200	\(\hat y_2 = \hat f_{2}(x_2)\)	\((y_2 - \hat y_2)^2\)
1,2,4, …, 199, 200	\(\hat y_3 = \hat f_{3}(x_3)\)	\((y_3 - \hat y_3)^2\)
\(\vdots\)	\(\vdots\)	\(\vdots\)
1,2,3, …, 198, 199	\(\hat y_{200} = \hat f_{200}(x_{200})\)	\((y_{200} -\hat y_{200})^2\)

Pros to LOOCV

1. Less bias: LOOCV uses almost all of the data to fit the model whereas the validation approach may only use 50% (which tends to lead to an overestimate of the test error).

2. Deterministic estimates: LOOCV always gives the same estimate because the partitions are not chosen randomly.

3. Very general: LOOCV¹ can be used with any kind of predictive modeling; logistic regression, LDA, you name it!

1. LOOCV tends not to overestimate the test error rate as much as the validation approach
2. validation approach will give you a different answer every time due to the randomness in the train/testing split
3. some methods will even have LOOCV built in

1. While the validation approach can be general as well, LOOCV has the added benefit of having more data which may be important for methods like QDA

Cons to LOOCV

1. Computationally demanding¹: LOOCV requires the model to be fitted \(n\) times which can be very costly if \(n\) is large and/or the model is slow to fit.

2. More variance since LOOCV estimates are highly correlated² \[\begin{align} \text{Var}(X + Y) = \text{Var}(X) + \text{Var}(Y) + 2\cdot\text{Cov}(X,Y) \end{align}\]

• Con 1: This can be very time consuming if n is large, and if each individual model is slow to fit (a shortcut exists for regression)
  • (consider \(n\)=1000 images!) or a model that takes 5 days to run a single model
  • wine data example took 30 seconds (which might not seem like a lot but its not that big of a data set)
  • there are some shortcuts for regression (see textbook)
• Con 2: But even though MSE1 is unbiased for the test error, it is a poor estimate because it is highly variable, since it is based upon a single observation
• usually k-fold with 5 or 10 is best

1. With least-squares linear or polynomial regression there is a mathematical shortcut that does not require us to refit the model

2. since they trained on an almost identical set of observations

Comments on k-Fold CV

• As mentioned earlier, \(k\)-fold CV is more general than LOOCV (with the added benefit of less variance)

• While \(k\) can be anything from 1 to \(n\), typically we use 5- or 10-fold CV.

• While we try to subdivide the data into equally-sized non-overlapping sets, sometimes that is impossible so we approximate¹

• Each set (or “fold”) takes a turn as the validation set, with the remainder of the data used to train the model.

• We usually shuffle the data before making the folds

• divide data into k groups, or “folds”
• typically k = 5 or 10

1. your sample size may not divide perfectly. For example if \(n=20\) and \(k=3\) (20/3 = 6.67) you might use two validation sets with 7 observations and one with 6

5-fold Visualization

A schematic display of 5-fold CV. A set of n = 20 observations is randomly split into five non-overlapping groups (or folds). Each of these folds takes a turn a validation set (shown in blue), and the remainder as a training set (shown in red). The test error is estimated by averaging the five resulting MSE estimates.

• Observations appear in exactly 1 validation set -LOOCV is a special case of k-fold CV in which k is set to equal n
• typically use k = 5 or k = 10.
• PRO there is much less overlap in these training sets than in LOOCV
• LOOCV is a special case of k-fold (when k = n)

knitr::include_graphics("img/11/k-fold-rearranged.png")

Dataset Splitting: The original dataset is divided into k roughly equal-sized subsets or “folds.” Each fold contains a portion of the data, and typically, these subsets do not overlap.

Iterative Process: The cross-validation process is then performed iteratively for k rounds. In each round, one of the k folds is used as the validation set, and the remaining k-1 folds are used as the training set.

Model Training and Testing: The model is trained on the training set, and its performance is evaluated on the validation set. This performance metric (e.g., accuracy, mean squared error) is recorded for each round.

Average Performance: After all k rounds are completed, the performance metrics from each round are usually averaged to provide a single estimate of the model’s performance.

\(k\)-Fold split

Full Sample Index: 1, 2, … , 20, with \(k = 5\)

Training Set	Validation*
1, 2, 4, 5, 6, 8, 9, 11, 13, 14, 15, 16, 17, 18, 19, 20	3, 7, 10, 12
1, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18, 20	2, 4, 14, 19
1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 14, 15, 17, 19, 20	5, 13, 16, 18
1, 2, 3, 4, 5, 7, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20	6, 8, 9, 15
2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 18, 19	1, 11, 17, 20

• Here the data set split evenly but remember there may be validation sets of slightly different size
• Note there different sizes will be taken into account in the weights of the CV estimates

5-fold CV Calculations

Where \(\hat f_j\) is the model fitted using all observations not in validation set (i.e. \(i \notin V_j\)).

Validation Set \(V\)	Prediction	Metric \(MSE_j\)
\(V_1\) = 3, 7, 10, 12	\(\hat f_1 (x_3, x_7, x_{10}, x_{12})\)	\(\frac{1}{4}\sum_{i\in V_1} (y_i - \hat y_i)^2\)
\(V_2\) = 2, 4, 14, 19	\(\hat f_2 (x_2, x_4, x_{14}, x_{19})\)	\(\frac{1}{4}\sum_{i\in V_2} (y_i - \hat y_i)^2\)
\(V_3\) =5, 13, 16, 18	\(\hat f_3 (x_5, x_{13}, x_{16}, x_{18})\)	\(\frac{1}{4}\sum_{i\in V_3} (y_i - \hat y_i)^2\)
\(V_4\) =6, 8, 9, 15	\(\hat f_4 (x_6, x_8, x_{9}, x_{15})\)	\(\frac{1}{4}\sum_{i\in V_4} (y_i - \hat y_i)^2\)
\(V_5\) =1, 11, 17, 20	\(\hat f_5 (x_1, x_{11}, x_{17}, x_{20})\)	\(\frac{1}{4}\sum_{i\in V_5} (y_i - \hat y_i)^2\)

\[\begin{align} \text{CV}_{(5)} = \frac{1}{5} \sum_{j=1}^5 MSE_j \end{align}\]

CV is the weighted average of the \(MSE_k\)

\(k\)-Fold Estimation

More generally, we can calculate the MSE for each validation set \(j\), for \(j = 1, \dots, k\) \[MSE_j = \frac{1}{n_j} \sum_{i \in j}(y_i-\hat y_i)^2\] where \(n_j\) is the number of observations in the \(j\)th validation set. A cross-validated estimate the MSE given by \[ CV_{(k)} = \frac{1}{k}\sum_{j=1}^k MSE_j \]

• This process results in k estimates of the test error, MSE1, MSE2, . . . , MSEk
• if k = 5, we run the model 5 times and obtain 5 mse est then average them
• denom is just saying number of obs in that validation set j (which may or may not be the same for each validation set if we have a data set that doesn’t divide perfectly)

ISLR Cross Validation Figure

jump back to validation approach

ILSR Fig 5.4 Cross-validation was used on the Auto data set in order to estimate the test error that results from predicting mpg using polynomial functions of horsepower. Left: The LOOCV error curve. Right: 10-fold CV was run nine separate times, each with a different random split of the data into ten parts. The figure shows the nine slightly different CV error curves. These are much less variable than the Validation Approach

• one curve of LOOCV since its deterministic
• 10-fold is stochastic so let’s run in a few times (nine times)
• While there is some variability in the resulting estimates for error they are much more stable than the validation approach
• The curve is telling us that a quadradic, cubic, quatric, quintic, sextic, septic, octic, nonic, decic (tenth-order) polynomial all preform similarly well on data it hasn’t seen.
• In the spirit of K.I.S.S and parsimony, this would give us some reason to choose a quadradtic (second-degree polynomial). Notably a 1st degree polynomal (linear regression) would not suffice

\(k\)-fold vs. LOOCV

Pros of \(k\)-fold

1. Less variance than LOOCV
2. More computationally feasible than LOOCV (\(k\) vs. \(n\) model fits)
3. Often gives more accurate estimates of test error than LOOCV.

Cons of \(k\)-fold

1. more bias than LOOCV when estimating MSE
2. Non deterministic estimate of the MSE (randomly spliting the data into \(k\) folds)

Pros 1. Since the mean of many highly correlated quantities has higher variance than does the mean of many quantities that are not as highly correlated, the test error estimate resulting from LOOCV tends to have higher variance than does the test error estimate resulting from k-fold CV. 3. this has to do with bias-var tradeoff

3. why (next slide?) Bias-Variance Tradeoff: LOOCV has lower bias but higher variance, whereas k-fold CV strikes a better balance between bias and variance.

Cons 1. k-fold is trained using less data so more bias (since it uses less data) (LOOCV is almost unbiased becuase it uses almost all available data in our training set)

In practice, k-fold CV (usually k = 5 or 10) is preferred, because:

• It achieves a better bias–variance balance.
• It is computationally cheaper (fit only k models, not n).
• It gives a more stable estimate of test error.

Bias-Variance trade-off

LOOCV will have lower bias than does \(k\)-fold CV with \(k < n\), but LOOCV has higher variance.

Again we are seeing the bias-variance trade-off that we have discussed previously throughout the course!

- LOOCV less bias: uses almost all the data we have on hand
- LOOCV high variance: since the estimates are highly correlated (because the differ by a single observation)

Bias-Variance Tradeoff: LOOCV has lower bias but higher variance, whereas k-fold CV strikes a better balance between bias and variance.

(general recommendation on next slide)

k-fold or LOOCV?

• k-fold or LOOCV

k-fold or LOOCV?

• k-fold or LOOCV? ¹ What value of \(k\) is best?

• The ISLR authors argue that for intermediate values of \(k\), say 5 or 10, \(k\)-fold CV provides a better estimate of test error rate than LOOCV²

• In other words, the decrease in variance tends to outweigh the increase in bias when we chose 5/10-fold validation over LOOCV.

• generally speaking k-fold with 5 or 10 will tend to produced more accurate estimates of MSE than LOOCV.
  
• (Error = Var(g) + Bias(g)²) if we choose k-fold over LOOCV we increase Bias but decrease Var but the net loss will be bigger (generally speaking) when we choose k = 5, 10
• choice often between deterministic vs. non-deterministic method
• ILSR: shown empirically that 5/10fold CV suffer neither from excessively high bias nor from very high variance

In practice, k-fold CV (usually k = 5 or 10) is preferred, because:

• It achieves a better bias–variance balance.
• It is computationally cheaper (fit only k models, not n).
• It gives a more stable estimate of test error.

1. LOOCV is a special case of k-fold CV

2. this point is debatable; see a discussion here

CV and Classification (LOO)

• CV (either \(k\)-fold or LOO) can be applied easily in a classification context as well.

• For instance, in LOOCV we can calculate cross-validated misclassification rates by replacing \(MSE_i\) with the validation misclassification rate (aka error rate \(\text{Err}_i\)) : \[ CV_{(n)} = \frac{1}{n} \sum_i^n \text{Err}_i = \frac{1}{n} \sum_i^n I(y_i \neq \hat y_i) \] where \(I(y_i \neq \hat y_i)\) is 1 if the left-out observation was misclassified using the \(i\)th model, and 0 otherwise.

CV and Classification (k-fold)

We divide the data into \(k\) roughly equal-sized parts \(C_1, C_2, \ldots, C_k\) where \(n_j\) is the number of observations in part \(j\): if \(n\) is a multiple of \(k\), then \(n_j = n/k\).

\[\begin{align} MC_j &= \frac{1}{n_j} \sum_{i \in j} I(y_i \neq \hat y_i) \\ CV_{(k)} &= \sum_{j=1}^k \frac{n_j}{n} MC_j \end{align}\]

• denom \(\sum_{i=1}^n I(i \in j)}\) is simply counting the number of observations in our validation set.
• numerator \(\sum_{i \in j} I(y_i \neq \hat y_i)\) is counting how many observations in our validation set were misclassified

We could also extend these CV estimates to other values such as log-loss

Model Selection

• We have just seen how we could use these methods to to assess model performance.

• Now let’s switch gears and see how these methods can be used for model selection.

• Now we can use cross-validation (CV) to compare and select the best-performing model among several candidates.

• In this case, we use CV to choose which value of k¹ for KNN performs the best in terms of generalization.

• model assessment we care what the MSE estimate was
• model selection we care where the minimum MSE estimate is
• These are the first systematic approaches we have for selecting among possible models!
• don’t be confused with the multiple use of \(k\)!

1. This k refers to the number of neighbours and has nothing to do with \(k\)-fold. I will try to distinguish these by using typewriter text when using k in reference to KNN.

iClicker

iClicker:

What is the primary purpose of the training dataset in machine learning?

1. To tune the model’s hyperparameters
2. To evaluate the final performance of the model
3. To train the model on a given dataset
4. To prevent overfitting during training

iClicker

iClicker:

What is the key difference between a validation set and a test set?

1. The validation set is used for final model evaluation

2. The test set is used for hyperparameter tuning

3. The validation set is used for hyperparameter tuning, while the test set is for evaluating generalization

4. The validation set is larger than the test set

iClicker

iClicker:

Which of the following best describes the concept of data leakage

1. Including irrelevant features in the training set
2. Sharing test data with the training data
3. Training on a small portion of data
4. Using a non-random dataset split

Cars Example

The cars data give the speed of 1920s cars (speed) and the distances taken to stop (dist).

KNN (from FNN package)

library(FNN)
knn.reg(train, test = NULL, y, k)

• train matrix or data frame of training set cases.
• test matrix or data frame of test set cases. A vector will be interpreted as a row vector for a single case. If not supplied, LOOCV will be done.
• y reponse of each observation in the training set.
• k number of neighbours considered.

Value returned: - PRESS the sums of squares of the predicted residuals = \(\sum_i^n (y_i - \hat y_i)^2\) (i.e the numerator of \(CV_{(n)}\))

Cross-validated estimates

• We fit all possible k values (1 to 49 - the number of samples)

• If we don’t supply a test test, knn.reg performs LOOCV

• We plot the cross-validated estimates of MSE across all values of k each calculated using: \[CV_{(n)} = \frac{1}{n} \sum_{i=1}^n MSE_i\]

• where k is being used in the context of KNN.
• so there will be 49 different CV estimates (one for each value of k NN) Value returned: - PRESS the sums of squares of the predicted residuals = \(\sum_i^n (y_i - \hat y_i)^2\) (i.e the numerator of \(CV_{(n)}\))

k vs MSE plot

library(FNN)
data(cars, package="datasets")
attach(cars)
kr <- list()
predmse <- NA
for(i in 1:49){
  # LOOCV (default if no test set is supplied)
  kr[[i]] <- knn.reg(speed, test=NULL, dist, k=i)
  predmse[i] <- kr[[i]]$PRESS/nrow(cars) # LOOCV estimate for k = i
}
par(mar = c(4, 4.2, 1.1, 0.1))
plot(predmse, type="b", lwd=3, col="red", 
     ylab = expression(CV[(n)]), 
     xlab = "k (nearest neighbours)",
     main ="LOOCV MSE Estimates")

• this is estimating that true MSE curve (see fig 5.6 in ISLR)
• We want the model that minimizes the predicted MSE
• min is at \(k\)= 2

This dataset is very small (n = 50), so i’ve skipped separating into a final test set.

• use LOOCV or k-fold CV on the entire dataset,
• choose the best hyperparameters, and
• report the cross-validation error as an approximate test error.

This is okay for demonstration or small-sample inference — but in real predictive modeling, that test set should exist.

PRESS: the sums of squares of the predicted residuals. NULL if test is supplied.

k vs MSE plot

Zoomed in

The minimum of that plot suggests that the best value of k is at 2.

Jump to compare with Regression MSE estimate.

k = 1

Too flexible

k = 10

k = 20

not flexible enough

k = 2 (winner)

• To flexible?
• speed is quite discretized
• best model is to just average the y’s at each vertical collection of points
• for jittered x i suspect a higher k would be selected

Cars: using 10-fold

set.seed(123)  # for reproducibility

# We'll predict dist from speed
X <- cars$speed
y <- cars$dist
n <- length(y)

# number of folds
Kfold <- 10

# create fold assignments (roughly equal sizes)
fold_id <- sample(rep(1:Kfold, length.out = n))

# function to get 10-fold CV MSE for a single k
cv_mse_for_k <- function(k_val) {
  sq_errs <- numeric(n)  # store squared errors for each point
  
  for (fold in 1:Kfold) {
    test_idx  <- which(fold_id == fold)      # indices in this fold
    train_idx <- setdiff(1:n, test_idx)      # everything else

    # training data for this fold
    train_X <- matrix(X[train_idx], ncol = 1)
    train_y <- y[train_idx]

    # test data for this fold
    test_X <- matrix(X[test_idx], ncol = 1)

    # fit KNN regression using training fold, predict on test fold
    pred <- knn.reg(train = train_X,
                    test  = test_X,
                    y     = train_y,
                    k     = k_val)$pred

    # store squared errors for this fold's test points
    sq_errs[test_idx] <- (y[test_idx] - pred)^2
  }

  # average MSE across all points
  mean(sq_errs)
}

# try a grid of k values
k_grid <- 1:15  # (you can extend if you like)
cv_mse <- sapply(k_grid, cv_mse_for_k)

plot(data.frame(k = k_grid, mse = cv_mse), type="b")

Minimum at \(k\) = 5

k = 5 (winner)

• odd artifact of the data
• x’s (speed are discrete-ish)
• best model is to just take the average at each of these discrete values

Comments

LOOCV chose k = 2, but the fitted curve looked too wiggly;
a clear sign of overfitting.

• LOOCV refits the model n times (once per obs).

• Each training set differs by only one point →
  estimates are highly correlated, leading to high variance.

10-fold CV chose k = 5, producing a smoother, more generalizable fit.

• 10-Fold CV uses larger, distinct test folds →
  less correlation, lower variance, and more stable error estimates.

Compared to LOOCV:

• 10-fold CV trains on only 90% of the data each time, so the models differ more → less correlated error estimates.
• That gives a lower-variance estimate of the test MSE.
• It tends to choose slightly smoother (less wiggly) models — which almost always generalize better.

Comparing Models

• Not only can we select k using CV, but we can furthermore compare that best KNNreg model’s predictive performance with any other potential model.

• Since CV estimates the MSE, there’s no reason we cannot provide that estimate in the context of, say, simple linear regression…

Cars example (regression)

Car data, simple linear regression on full sample

cars.line <- lm(dist~speed)
summary(cars.line)

...
Call:
lm(formula = dist ~ speed)

Coefficients:
            Estimate Std. Error t value Pr(>|t|)    
(Intercept) -17.5791     6.7584  -2.601   0.0123 *  
speed         3.9324     0.4155   9.464 1.49e-12 ***
---
Signif. codes:  0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1

Residual standard error: 15.38 on 48 degrees of freedom
Multiple R-squared:  0.6511,    Adjusted R-squared:  0.6438 
F-statistic: 89.57 on 1 and 48 DF,  p-value: 1.49e-12
...

Regression MSE estimate

• Under the inferential assumptions for SLR, we have a theoretical (unbiased) estimate of the test MSE via \[ \hat{\text{MSE}} = \frac{\text{RSS}}{n-2} = \frac{\sum (y_i - f(x_i))^2}{n-2}\]

• For the cars data, that gives us: \(\frac{11353.52}{48}= 236.53\)

• In this case k = 2 KNN model gets a CV MSE estimate of 178.54 hence is suggested as the better model.

Assuming all our diagnostics hold and we’re willing to make those inferential assumptions,

LOOCV Regression Shortcut

• While we could compare these estimates of MSE directly, we could go one step further and get the CV estimate for MSE by applying LOOCV to the linear model!

• Notably, there is a mathematical shortcut for LOOCV with the least squares linear or polynomial regression that calculate \(CV_{(n)}\) using a single fit!

• The details of this shortcut are discussed in Section 5.1.2 of the ILSR textbook (we won’t go over them here).

LOO Regression Animation

LOO regression fits

Plots the \(n\) (highly correlated) LOOCV regression fits produce a cross-validated estimates MSE = \(CV_{(n)} = 246.405416\)

only one blue line out of place for that higher leverage point

5-fold CV Animation

• this estimate would be different if we ran it again (unlike LOO)
• more variation in the lines and only have 5 of them
• less correlation in the lines give less variance for MSE
• if we did this again and agin on new data, the estimate of MSE would have higher variance for LOOCV than k-fold

5-fold estimates MSE as \(CV_{(5)} = 254.0391118\)

• compared to LOOCV estimate of 246 (low bias high variance)
• similar value (higher bias lower variance)

10-fold CV Animation

now we have 10 validation sets (with 5 obs in each) n=50

10-fold estimates MSE as \(CV_{(10)} = 243.7798735\)

Summary

\(k\)	\(CV_{(k)}\)
5	254.04
10	243.78
\(n\) (LOOCV)	246.41

• LOOCV fits are highly correlated (almost identical)
• The smaller correlatiaon between the fits in k-fold results in less variability in the MSE estimate.
• As stated before, 5- or 10- fold CV tend to produce more accurate estimates of test error than LOOCV (which tends to overestimate).

Wine example

• We now consider the wine data set from the pgmm package

• 27 measurements on 178 samples of red wine.

• Samples originate from the same region of Italy (Piedmont), but are of different varietals (Barolo, Barbera, Grignolino).

• We can do KNN classification, using LOOCV¹ to choose k, the number of neighbours…

1. We will use knn from the class package and hard-code LOOCV in lab.

Best k

In this case the minimum is at k = 8

source code at lectures/code/13/wine.R

Wine Example

We can provide a cross-validated classification table,

	Predicted
	1	2	3
Barolo	52	3	2
Grignolino	2	59	11
Barbera	5	9	35

or LOOCV Error …

\[ \begin{align} CV_{(n)} &= \frac{1}{n} \sum_i^n \text{Err}_i\\ & = \frac{1}{n} \sum_i^n I(y_i \neq \hat y_i)\\ & = \frac{32}{178} = 0.18 \end{align} \]

… or cross-validated versions of any of our other classification performance indices exist!

prime you for next lecture - not that the model we used here was the \(k\)=8 group model fitted to the entire data set.

Standard Errors

• More generally: \(CV_K = \sum_{k=1}^K \frac{n_k}{n} \text{Err}_k\)

• In addition to computing \(CV_K\) estimate of the error rate, we can also estimate standard deviation of \(CV_K\).

• The estimated standard deviation of \(CV_K\) is given by:

\[\begin{equation} \hat{\text{SE}}(CV_K) = \sqrt{ \sum_{k=1}^{K} \left(\text{Err}_k - \overline{\text{Err}_k}\right)^2/ (K-1)} \end{equation}\]

• \(SE(CV_{(K)}\) estimate is a measure that quantifies the variability of the CV estimate itself.
• tells how reliable and stable the performance evaluation of a predictive model is when using cross-validation.
• Err\(k\) overlaps with Err\(j\) cuz they share some training samples
• nevertheless people use it anywya

While this is a useful estimate, but strictly speaking, not quite valid since observations are not independent

Final Remark

• Now we have \(n\) different fits of the model, which model should we report?

None of them

• While CV is used to help select a model, the actual reported model would be the one run with all the data.

• That is, we would need to run knn() with k = 8 on the full data set with no observations removed.