Why does cross validation have a pessimistic bias?

Question

My course notes list two reasons why cross-validation has a pessimistic bias. The first one is that the accuracy is measured for models that are trained on less data, which I understand. However, the second reason I don't understand. Supposedly, when we do cross validation and divide our data D into training sets D_i and test sets T_i, then the D_i and T_i are not independent (and even complementary) given D.

However, I don't see why this is different from the situation where we use a fixed testset: if we have a training set D and test set T, than T and D are also not independent given the union of D and T. In this case there is no bias, so I would expect there to be no bias for cross-validation either (apart from the fact that the model is trained on less data). Of course, since the different models that we train for cross validation use overlapping data, I would expect their accuracy to be correlated, which could lead to a higher variance, but I don't see how this could give a bias.

Answer 1

The issue arises because these k subsets are not randomly sampled and are often consecutive. For example, in k-fold cross-validation, the dataset is partitioned into k consecutive folds. This non-randomness in the selection of training and test sets means that the model can learn patterns that are specific to the particular division of the data.

In the extreme case of leave-one-out cross-validation (LOOCV), where k equals the number of data points, each model is trained on almost all data points except one, which makes the training and test sets almost identical. In such cases, the model may end up overfitting to the specific data points in the training set, leading to optimistic bias in the estimated accuracy.

In contrast, when you use a fixed test set that is independent of the training data, the potential bias due to non-independence between training and test sets is not an issue. The test set is completely separate from the training set, and the model is evaluated on a truly unseen and independent dataset, which leads to a more reliable estimate of the model's performance on new data.

To mitigate the bias due to non-independence in cross-validation, researchers sometimes use techniques like stratified k-fold cross-validation, which attempts to ensure that each fold represents the overall class distribution of the data more accurately. However, it's important to be aware of this bias and use cross-validation appropriately, especially when the dataset is small or highly imbalanced.