2

There is an interesting exercise which shows k-fold cross validation fails in some cases. The exercise is as follows:

Consider a case in that the label is chosen at random according to $P[y =1]= P[y =0]=1/2$. Consider a learning algorithm that outputs the constant predictor $h(x)=1$ if the parity of the labels on the training set is 1 and otherwise the algorithm outputs the constant predictor $h(x)=0$. Prove that the difference between the leave-one-out estimate and the true error in such a case is always 1/2.

My question is in what cases (or under what conditions) k-fold cross validation fails? Is it only k-fold validation that fails or other types of cross validation may fail too?

SMA.D
  • 295
  • Cross validation fails whenever there's a dependency between samples. This kind of dependency exists in the scenario you provided as well as other scenarios, such as time dependent samples (time series), samples that originally belong to a group out of a set and more. – Omri374 Dec 24 '17 at 13:40
  • @Omri374 I think in the example there is no dependency between samples. Samples are i.i.d – SMA.D Dec 24 '17 at 13:46
  • The dependency here is not between samples, but between runs of the CV algorithm, if I understand correctly. – Omri374 Dec 24 '17 at 13:50
  • 1
    @Omri374 there is always dependency in CV, as long as there are overlapping samples between different folds. That is not a problem of CV. – Lii Dec 24 '17 at 15:38
  • @Lii I agree. I was referring to the example provided in the question, in which the model is heavily dependent on the subset of training samples. A change in one sample would change the output of the model even if the number of samples is high. – Omri374 Dec 25 '17 at 05:49
  • @SMA.D: does the text give an explanation what they consider a failure of the validation plan? – cbeleites unhappy with SX Dec 25 '17 at 10:32
  • @cbeleites I think they consider PAC learning framework. Which is in brief: for any distribution of the data (unknown to the learning algorithm), the gap between generalization error of hypothesis h and error on validation samples should be bounded by a value that decreases as number of samples increase. – SMA.D Dec 25 '17 at 12:16

1 Answers1

1

I found this answer in the same book:

The cross validation method often works very well in practice. However,it might sometime fail, as the artificial example shows. Rigorously understanding the exact behavior of cross validation is still an open problem. Rogers and Wagner (Rogers & Wagner 1978) have shown that for k local rules (e.g., k Nearest Neighbor) the cross validation procedure gives a very good estimate of the true error. Other papers show that cross validation works for stable algorithms.

SMA.D
  • 295