Could anyone elaborate on a theoretical perspective of K-fold cross-validation and especially a mathematical formula for k-fold CV prediction error?

Updated:Could any one of you help me to understand the formula written on latest edition (Feb, 2011) of the book at page 242. enter image description here

  • $\begingroup$ If you want just how-to-do-it, it has been already answered, for instance here: stats.stackexchange.com/questions/1826/… $\endgroup$ – user88 Oct 23 '11 at 7:35
  • $\begingroup$ @mbq: I know that how it works, but I need mathematical formula for this prediction error. I have applied Least Angle regression (R package 'lars'). So I am looking for mathematical formula for this cross validation procedure for R function (cv.lars) in 'lars' package. $\endgroup$ – Biostat Oct 23 '11 at 10:36
  • $\begingroup$ Well, now I'm confused -- what do you mean by "mathematical formula" in this case? $\endgroup$ – user88 Oct 23 '11 at 12:59
  • $\begingroup$ how I can write K-Fold cross-validation prediction error in mathematical form? $\endgroup$ – Biostat Oct 23 '11 at 14:48

There are formulae for computing the leave-one-out cross-validation error in closed form for many models, including least-squares regression, but as far as I am aware there isn't a general formula for k-fold cross-validation (or at least it may be possible but the computational advantage is too small to be worthwhile).

The formula in the book isn't saying very much it is just saying that the cross-validation error is the average of the loss function (L) evaluated using models trained on different subsets of the data. The superscript $-\kappa(i)$ just means "model $f$ is trained without the training patterns in the same partition of the dataset as pattern $i$". Sometimes writing things in formal mathematical notation makes things less ambiguous, but it doesn't necessarily make it any easier to understand than the text - I think this is one of those occasions.


The reason people do cross-validation is that there is no mathematical formula to accurately get at the same thing except under very restrictive conditions. And note that k-fold cross-validation does not have adequate precision in most cases, so you have to repeat k-fold cross-validation often 50-100 times (and average the performance metric) to get accurate, precise estimates of model performance. There is certainly no mathematical formula for that.


The truth is that cross-validation is simply a heuristic for model selection. If what you are really looking for is obtaining a theoretically-backed estimate of your generalization prediction, cross-validation can only give a good estimate of it but there are no guarantees. A better fit for that would be learning theoretical frameworks such as the PAC-Bayes setting. However those frameworks have their own short-comings, mostly related to the fact that bounds tend to be to loose/general (for example a bound telling you that you're not going to predict wrong more than 100% of the time).

However some people have tried to formalize the cross-validation heuristic. You may want to take a look at the references in this post from John Langford. http://hunch.net/?p=29

  • $\begingroup$ Actually, I am looking for mathematical formula of this prediction error. Do you have experience CV with Least Angle Regression? That is implemented in R package 'lars'. How CV works with model selection, I mean to say should we always select as many predictors with minimum prediction error? $\endgroup$ – Biostat Oct 23 '11 at 0:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.