# A mathematical formula for K-fold cross-validation prediction error?

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. • If you want just how-to-do-it, it has been already answered, for instance here: stats.stackexchange.com/questions/1826/…
– user88
Oct 23, 2011 at 7:35
• @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. Oct 23, 2011 at 10:36
• Well, now I'm confused -- what do you mean by "mathematical formula" in this case?
– user88
Oct 23, 2011 at 12:59
• how I can write K-Fold cross-validation prediction error in mathematical form? Oct 23, 2011 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

• 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? Oct 23, 2011 at 0:40

I think that what the person was asking the question needs is simply a formula that is more explanatory, or a full-blown explanation of the formula. I'm posting this for the sake of others looking for an answer.

Here is how I understand it.

2. Once you divide your data set into K subsets, you calculate the MSE where the test set is one of the subsets k and the function f^(-k)(x_i) is calculated over the training set made of all the points minus subset k. You get

MSE(k)=K/N*sum_{all points in subset k} (y_j - f^(-k)(x_i))^2.

Note that to obtain the average you divide by N/K which is the number of points in subset k. 3. Now you take the average over all K subsets, and you obtain:

MSE = 1/K * sum_k MSE(k)

1. K and K simplify and MSE becomes simply

MSE = 1/N * sum_{all points!} (y_j - f^(-k)(x_i))^2

Note that each point is counted exactly once. That's why instead of f^(-k) you can write like Hastie et al. "f^(-k(i))".

THe extension to a generic loss function should be trivial.

Hope this clarifies.

New contributor
Pietro is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.