Not able to understand CV error In slide 8 Hastie & Tibshirani mention:

It is easy to simulate realistic data with the class labels independent of the outcome, so that

*

*true test error =50%, but

*“Wrong” CV error estimate is zero!


I am not able to understand the overall setup. Specifically, I cannot understand why CV Error = 0?
If someone could provide a small example that will be great.
 A: To put their point into different words: any pre-processing that "combines" multiple cases into the pre-processing calculations*, this pre-processing needs to be done inside the cross validation.

Here are key "features" of a scenario that contribute to this particular problem:

*

*few cases make the cross validation estimate subject to high variance

*comparing many models to pick the one that looks best (in their case via correlation),

*even worse if this comparison or otherwise data-driven selection that is based on test data that are not independent of the training data.

*Doing a kind of pre-processing where many (all) training cases enter the calculation without including this pre-processing into the tested part of the data analysis is one way of obtaining such a dependence in the data.

Picking the obsreved optimum from many estimates that are subject to high variance uncertainty means that you run a high risk of "skimming" the variance rather than finding the underlying true structure in error as function of the hyperparameters (here: which features to use).

*

*The "step-2-only" error bein estimated by CV as opposed to, say, a test set is unimportant here. The important distinction is "step-2-only" vs. "step-1+2".


I can give you a real data example I discuss in my PhD thesis (in German) C. Beleites: Raman-spektroskopische Diagnostik von
primären Hirntumoren mit Hilfe weicher
chemometrischer Klassifikationsmethoden, FSU Jena, 2014, section 5.2.1 Modellvergleiche und Optimierung, Festlegen von Hyperparameter (Model comparison and optimization, fixing of hyperparameters):

*

*Data set: FTIR images from tissues, to be classified into tumor grades.


*Each image consists of many (32 x 32 = 1024) spectra


*Each spectrum consists of many features that are absorbances at different wavelengths (think of this as an image with 100s of colours instead of the usual 3).


*Classifier: LDA after feature selection by a genetic algorithm (GA): the GA selects up to 8 different spectral regions, of which the average absorbance is the new feature. The LDA is trained on these up to 8 features.


*The GA is a very "aggressive" optimizer that picks the apparently best model out of some 4500 - 5000 of models in the optimization run.


*Cross validation: the performance of the LDA model is estimated by leave-one-out cross validation (LOO-CV). The LOO-CV looks at the LDA only, and does not include leaving out that row of data from the GA (i.e. Hastie & Tibshirani's step 2 only).


*Since I had already exposed heavy overoptimism in the performance estimates of the very same training method on a similar data set in my Diplom thesis, I wrapped an outer CV (as estimate of the "true test error") around the whole training procedure. This outer CV thus tests both step 2 in Hastie & Tibshirani's terminology.


*I also knew already that the spectra of one image are not independent: neighbour spectra tend to be more similar to each other than to spectra from an image of another tissue sample.
Since the training program did not allow to do leave-image-out estimates, the training data was 1 average spectrum per image. The outer CV ("test") was done with the 32 x 32 pixel images.


*While the data set had several 1000 spectra, there were only few images. The smallest class was tumor grade II (blue below) with only 5 images.


*The outer CV was done as 40 repetitions (itertations) of 5-fold cross validation. I thus have for each images 160 (40 x 4) estimates of inner LOO-CV and
40 estimates for the outer 40x5-fold CV test.
As example, here's one of the grade II images:

*

*inner LOO-CV estimate



*outer 40x5-fold CV (test):

So for the very same image, the inner/step-2-only CV estimate shows >99 % correct, while the outer/step-1+2 CV estimate overall gets only 51 % correct (which is still better than guessing for 4 classes)
In Beleites, C. & Salzer, R.: Assessing and improving the stability of chemometric models in small sample size situations, Anal Bioanal Chem, 390, 1261-1271 (2008). DOI: 10.1007/s00216-007-1818-6, we discussed the classification problem and how to detect and what to do if a training algorithm outputs unsgtable models (to a user of the training algorithm). We did not want to distract from that widespread problem by an in-depth discussion of one particular training algorithm:  the GA/LDA combination we used is just one out of many training algorithms that yield unstable models for data like ours.
