Leave One Out Cross Validation

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.