# Leave One Out Cross Validation

I tried to implement the Leave One Out Cross Validation (LOOCV) method to get me a best combination of 4 data points to train my model which is of the form:

Y= a + b X1 + c X2.

Where a, b and c are the coefficients based on regression. I have a set of 20 data points on the whole to train my model but I want to restrict my model to be trained from a set of 4 data points and be able to predict the other data points fairly well.

So I used the LOOCV method to achieve that by starting with 19 data points as my training set and the remaining 1 data point as my test set and calculating the error. Then I eliminated the data point (from both training and test data set) that resulted in the minimum error as this data point has been best predicted by the model. Then I kept on iterating until I came to 4 data points.

But the problem is, when I tried to add the data point that has been left out from each iteration and compute the Root Mean Square Error Value by applying the model to the whole set of data points at each iteration, I presume that it should have kind of an asymptotic shape when I plot the Root Mean Square Value Vs the No. of data points i.e. higher RMSE at lower no. of data points and converging to the lowest RMSE values at higher no. of data points. But this is the plot I'm getting for the data set. I don't know why is the plot showing this type of a behavior. Also, Is it valid to use the Leave One Out Cross Validation method as I have used it?. Please, clarify.

• Why do you eliminate the data points after you do LOOCV? – bdeonovic Apr 29 '14 at 17:06
• @Benjamin I need to eliminate because I need to find the minimum best 4 data points to train my model to predict the other data sets. Is there any other statistical method that can help me do this?. – Jeba Apr 29 '14 at 19:24
• It sounds like you might be interested in SVM – bdeonovic Apr 29 '14 at 20:22

After thinking a bit about your problem it is essentially coreset selection, i.e., finding a small subset (the coreset) of the training data such that the model trained on the subset is as close as possible to the model trained on the full dataset.

I'm not familiar with the area and it isn't a very easy term to google, but the paper Near-optimal Coresets For Least-Squares Regression (and the papers it references) is probably very relevant. It doesn't look like they directly solve the problem of finding the best $k$ points though. Instead their algorithm produces a coreset of size polynomially bounded in terms of a desired accuracy parameter and the rank of the data matrix. You might be able to massage their technique into want you want though by playing around with the bounds.

One thing I do want to mention is the idea of using some sort of CV procedure, like fitting a model for each $\binom{20}{4}$ split of your data and selecting the 4 points that results in a model with the minimum error on the remaining 16 points, as your search technique seems flawed. Notice that there is a sort of symmetry, as you could also view this procedure as picking the 16 points that are most easily predicted from 4, which almost certainly isn't what you really want. Essentially all such a procedure would be doing is searching for the split of your data that makes the problem easiest.

The way I understand LOOCV is like this: You want to fit your model to the data, but you also want it to not 'overfit' that is you want to also be able to generalize your model to data not in your data set. It is hard to get an estimate of how well your model is doing by testing it on the data that generated the model. Therefore you fit your data on a subset of your data ($n-1$ data points for LOOCV). This will give you an estimate of your parameters ($\hat{a}, \hat{b}$, and $\hat{c}$ in your model). Then you test your model on the remaining variables (the one you left out). From this fit you can get some kind of measure of how poorly you fit to this one data point.

You repeat this for every data point in your data (without removing anything). Then you plot the measure of error against all of these iterations. The parameter estimates that produed the lowest error would be your LOOCV estimated parameters. These measures of error should then be averaged to get an appropriate estimate of how well your model fits data.

• Fine description of LOOCV, but I can't agree with your last few statements (unless I'm misinterpreting). Normally what one would do is average all the errors to get an estimate of generalization error. CV is not for estimating parameters. It's to asses predictive performance, compare models, select hyper-parameters, and whatnot. Using CV as you describe in your last sentence can get you into real trouble (especially with LOOCV). Imagine you have a duplicate datapoint. If you have a flexible enough model, the lowest generalization error is likely to be the fold with this point left out. – alto Apr 29 '14 at 18:02
• Hi @alto , Ya I agree with your description of the LOOCV, but is there any other possible statistical methods that can help me to find the minimum best possible data points to train my model from a set of given data points. So that when I use the parameters estimated from these minimum data points on other data sets I should get a good fit. – Jeba Apr 29 '14 at 19:22

It doesn't sound like the method you are using is guaranteed to give you the global 4 point solution. If you really want the 4 best data points from which to build your model, then you need to fit your model to all possible sets of 4 points, leaving you with ${20 \choose 4}$ models to build and evaluate the out of sample prediction error of each model on the remaining 16 points.