Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
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.
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
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.
Start with a less abstract loss function, say the MSE.
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)
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.
