Cross-validation versus leave-one-out validation
Phil Sherrod
superior to 10-fold cross validation (CV). This is particularly inconvenient because they want to
train an SVM model with 100 variables and about 2500 data rows. Hence, for LOO validation, 2500
large models must be trained and tested. This is requiring several days of computer time.
I recall a discussion a year or two ago about the merits of LOO versus CV. As I recall, there were
some convincing arguments that CV is actually superior to LOO, but I can't remember what those
arguments were. Can someone please enlighten me?
--
Phil Sherrod
(PhilSherrod 'at' comcast.net)
http://www.dtreg.com (Decision trees, Neural networks, SVM)
http://www.nlreg.com (Nonlinear Regression)
Erdal
wrote:
> I have a customer who is under the impression that leave-one-out (LOO) validation is greatly
> superior to 10-fold cross validation (CV). This is particularly inconvenient because they want to
> train an SVM model with 100 variables and about 2500 data rows. Hence, for LOO validation, 2500
> large models must be trained and tested. This is requiring several days of computer time.
>
> I recall a discussion a year or two ago about the merits of LOO versus CV. As I recall, there were
> some convincing arguments that CV is actually superior to LOO, but I can't remember what those
> arguments were. Can someone please enlighten me?
>
> --
> Phil Sherrod
You may want to look at Kohavi, A Study of Cross-Validation and
Bootstrap for Accuracy Estimation and Model Selection, 1995.
Hope this helps.
MEO
Wit Jakuczun
wrote:
> I have a customer who is under the impression that leave-one-out (LOO) validation is greatl
> train an SVM model with 100 variables and about 2500 data rows. Hence, for LOO validation, 2500
> large models must be trained and tested. This is requiring several days of computer time.
>
How many classes? What is a class distribution?
> I recall a discussion a year or two ago about the merits of LOO versus CV. As I recall, there were
> some convincing arguments that CV is actually superior to LOO, but I can't remember what those
> arguments were. Can someone please enlighten me?
>
In what way would you like to measure superiority?
For example LOO gives almost unbiased estimator but it can
be easily cheated. CV is less computationaly intensive but
on the other hand there are some approximations to
LOO error that are not computationaly intensive.
According to my experience CV is good estimator but it MUST be
repeated
a few times with different foldings and average error rate should be
taken
Also according to my experience, customer is always right ;)
Best regards,
Wit Jakuczun [ http://www.linkedin.com/in/jakuczunwit ]
Greg
wrote:
> I have a customer who is under the impression that leave-one-out (LOO) validation is greatly
> superior to 10-fold cross validation (CV). This is particularly inconvenient because they want to
> train an SVM model with 100 variables and about 2500 data rows. Hence, for LOO validation, 2500
> large models must be trained and tested. This is requiring several days of computer time.
>
> I recall a discussion a year or two ago about the merits of LOO versus CV. As I recall, there were
> some convincing arguments that CV is actually superior to LOO, but I can't remember what those
> arguments were. Can someone please enlighten me?
It is well known that LOO is inferior; especially in
classification with small data sets. The large variance
overwhelms the low bias. For larger data sets it doesn't
outperform bootstrapping and 10-fold XVAL but is obviouly
ridiculously more expensive.
Check the standard pattern recognition books (Duda et al,
Fukunaga, Devijver & Kittler, MacLachlan,..). Warren must
have mentioned it in the FAQ. So must have the originators
of bootstrapping. The question comes up once in a while in
sci.stat.* (math,consult,edu).
Try searching in Google Groups in addition to citeseer and
neuroprose.
Hope this helps.
Greg
Greg
wrote:
> (LOO) validation is greatly superior to 10-fold cross validation
> (CV).
Misconceptions like this can be cured with a rolled-up newspaper.
> This is particularly inconvenient because they want to
> train an SVM model with 100 variables and about 2500 data rows.
> Hence, for LOO validation, 2500 large models must be trained and
> tested. This is requiring several days of computer time.
Are you getting paid by the job or by the hour?
Linear, quadratic, and closest cluster classifiers are readily
modified when 1 measurement is added or deleted. Is this a
possibility for SVM?
Is this all of the data or do you have a nondesign test
set lying in the wings?
> I recall a discussion a year or two ago about the merits of LOO
> versus CV. As I recall, there were some convincing arguments
> that CV is actually superior to LOO, but I can't remember
> what those arguments were. Can someone please enlighten me?
All the references that I can remember just state that LOO
is relatively unbiased but the variance is much larger than
10-fold XVAL or bootstrapping. I don't remember any proofs
or definitive experiments.
Is this regression or classification? If the latter, the
classification rate objective is discontinuous and more prone
to sampling fluctuaions than a continuous regression objective
function.
Here are a few useful Google Group references:
----------------------------------------------------------------------
http://groups.google.com/group/sci.stat.consult/
msg/281a986e51e15eda?hl=en&dmode=source
Newsgroups: sci.stat.consult
From: Frank E Harrell Jr <fe...@spamcop.net>
Date: Wed, 7 Apr 2004 11:31:02 -0500
Local: Wed, Apr 7 2004 12:31 pm
Subject: Re: Leave one out Crossvalidation
> I need to use the Forward Selection algorithm to find the best
> features. I think I know how Forward Selection works, namely starting
> with an empty set of features, selecting the best feature and adding
> it to the set, computing the error, then selecting the next-best
> feature etc.
>
> But now I need to use LOOCV to determine what the 'best' feature is.
> How does this work, using the Naive Bayes classifier method?
You can't do leave-out-one validation when stepwise variable selection
is
being used. It does not penalize sufficiently for the variable
selection.
The bootstrap or x-fold cross-validation is required.
Frank E Harrell Jr Professor and Chair School of Medicine
Department of Biostatistics Vanderbilt
University
-----------------------------------------------------------------------
http://groups.google.com/group/sci.stat.math/
msg/0c629416a911be32?hl=en&dmode=source
Newsgroups: sci.stat.math
From: "Graham Jones" <x...@x.x>
Date: Sun, 28 Oct 2007 10:09:10 -0000
Local: Sun, Oct 28 2007 6:09 am
Subject: Re: why does leave one out cross validation have high
variance
"Shrihari" <shrihari.vasude...@gmail.com> wrote in message
news:1193516580.0...@22g2000hsm.googlegroups.com...
> I have a query regarding cross validation methods for estimating the
> generalization error of a classifier.
>
> Most prior literature says that leave-one-out CV (LOOCV) has low bias
> and high variance. Low bias I completely understand. The thing I do
> not understand is why it should have high variance - the only
> explanation I have been able to gather thus far is that since the
> models computed in each stage of the CV are very similar to each other
> (obviously, because they only differ by 2 training data instances),
> the variance is high (this is not obvious and in fact counter
> intuitive as I would expect similar models to produce similar
> results).
The high variance of the LOOCV refers to the variability of the
estimate
when the entire training set is varied, not to omitting single
training data
instances. Your particular training set might be accidentally `easy'
or
`hard', and the LOOCV estimate will be low or high accordingly. If you
omit
a larger fraction when training (n-fold cross validation), you stand
a
better chance of seeing a hard subsample from an easy training set,
and
vice-versa.
--------------------------------------------------------------------------------------
Why not try a limited demonstration:
1. Reduce the number of variables. It is very hard to believe
that 100 are necessary for the original problem, Regardless,
100 won't be necessary for this demo.
2. Randomly partition the data, take a convincingly sized
subsample and demonstrate the difference between LOO
and 10-fold XVAL.
Hope this helps.
Greg
Greg
> On Jun 16, 8:07 pm, "Phil Sherrod" <PhilSher...@REMOVEcomcast.net>
> wrote:
>
> > I have a customer who is under the impression that leave-one-out
> > (LOO) validation is greatly superior to 10-fold cross validation
> > (CV).
>
> Misconceptions like this can be cured with a rolled-up newspaper.
>
> > This is particularly inconvenient because they want to
> > train an SVM model with 100 variables and about 2500 data rows.
> > Hence, for LOO validation, 2500 large models must be trained and
> > tested. This is requiring several days of computer time.
>
> Are you getting paid by the job or by the hour?
>
> Linear, quadratic, and closest cluster classifiers are readily
> modified when 1 measurement is added or deleted. Is this a
> possibility for SVM?
Please ignore if you are getting paid by the hour.
An efficient method for computing leave-one-out error in support
vector machines with Gaussian kernels.
Authors:Lee, M.M.S.; Keerthi, S.S.; Ong, C.; DeCoste, D.
Source: IEEE Transactions on Neural Networks, Volume 15,
Number 3, p.750-757 (2004)
Greg
Greg
There are many more including
Making Large Scale Support Vector Machine Learning
Possible (1999) by by T Joachims
In Advances in Kernel Methods,, Scholkopf
Two Efficient Methods for Computing Leave-One-Out Error in
SVM Algorithms (2000) by S. Sathiya Keerthi, Chong Jin Ong,
Martin M. S. Lee
Download: http://guppy.mpe.nus.edu.sg/~mpessk/svm/loo.ps.gz
A data parallel approach for large-scale gaussian process
modeling (2002 )by Andy J. Keane, Arindam Choudhury, Arindam
Choudhury, Prasanth B. Nair, Prasanth B. Nair, Andy J. Keane
{a. Choudhury, P. B. Nair in Proc. the Second SIAM
International Conference on Data Mining)
Download: http://www.siam.org/meetings/sdm02/proceedings/sdm
Greg
Gavin...@googlemail.com
wrote:
> I have a customer who is under the impression that leave-one-out (LOO) validation is greatly
> superior to 10-fold cross validation (CV).
The no free lunch theorems suggest that in machine learning there is
very little that is generally superior to anything else without taking
into account the specific nature of the problem.
> This is particularly inconvenient because they want to
> train an SVM model with 100 variables and about 2500 data rows. Hence, for LOO validation, 2500
> large models must be trained and tested. This is requiring several days of computer time.
No, there are some short cuts you can take for SVMs and some useful
approximations. Firstly if a pattern isn't a support vector then it
will never be classified incorrectly during leave-one-out cross-
validation (that is easy to prove). Also I am pretty sure that any
pattern that is misclassified in training will always be misclassified
in leave-one-out cross-validation. So if you have trained the model
on the full data, you only need to investigate the folds in which a
correctly classified support vector will be left out.
Secondly you can make a good approximation of the leave-one-out error
by borrowing a technique from least-squares regression. See the work
of Olivier Chapelle (there was a paper on tuning multiple parameters
for SVMs in the journal Machine Learning, which would be a good place
to start).
> I recall a discussion a year or two ago about the merits of LOO versus CV. As I recall, there were
> some convincing arguments that CV is actually superior to LOO, but I can't remember what those
> arguments were. Can someone please enlighten me?
Basically LOO is approximately unbiased (i.e. the difference between
the expected LOO error and the true error is approximately zero, where
the expectation is over random training sets sampled from the same
underlying distribution), which is a nice feature for performance
evaluation, but not for model selection (where low variance is at
least as important).
However, LOO has a high variance (you get a wide spread of values for
the LOO error for different sets of training data sampled from the
underlying distribution), which is undesirable both for performance
prediction and model selection. This means that you can easily get a
misleadingly low or high value due to the peculiarities of the
particular sample you are looking at.
On the other hand, if you have a very small dataset, then cross-
validation can have a very high bias because each model is trained on
a smaller amount of data, so if the data were only just large enough
to train the model in the first place, cross-validation will have a
significant pessimistic bias. In that case, it may be worth trading
off the variance of leave-one-out against the bias of k-fold cross-
validation, so it is a case of "horses for courses".
Personally I am becoming more in favour of bootstrapping instead.
The reason that leave-one-out is used so often for kernel machine is
that it can be evaluated or approximated very cheaply, so even though
it has a high variance it makes a good model selection criterion (see
http://theoval.cmp.uea.ac.uk/~gcc for some examples, including papers
and MATLAB code). The problem of over-fitting due to the variance of
the LOO estimator can be alleviated by using a higher level
regularisation term, which I have found to be useful.
HTH
Gavin
Gavin...@googlemail.com
> On Jun 16, 8:07 pm, "Phil Sherrod" <PhilSher...@REMOVEcomcast.net>
> wrote:
>
> > I have a customer who is under the impression that leave-one-out (LOO) validation is greatly
> > superior to 10-fold cross validation (CV). This is particularly inconvenient because they want to
> > train an SVM model with 100 variables and about 2500 data rows. Hence, for LOO validation, 2500
> > large models must be trained and tested. This is requiring several days of computer time.
>
> > I recall a discussion a year or two ago about the merits of LOO versus CV. As I recall, there were
> > some convincing arguments that CV is actually superior to LOO, but I can't remember what those
> > arguments were. Can someone please enlighten me?
>
> It is well known that LOO is inferior; especially in
> classification with small data sets. The large variance
> overwhelms the low bias.
unless it is a small dataset where k-fold cross-validation has a high
bias. I would avoid LOO for performance estimation, but it is not a
firm rule with no exceptions.
> For larger data sets it doesn't
> outperform bootstrapping and 10-fold XVAL but is obviouly
> ridiculously more expensive.
unless you are using an algorithm where it can be computed for free,
such as k-NN or least-squares regression or many kernel learning
methods.
> Check the standard pattern recognition books (Duda et al,
> Fukunaga, Devijver & Kittler, MacLachlan,..). Warren must
> have mentioned it in the FAQ. So must have the originators
> of bootstrapping. The question comes up once in a while in
> sci.stat.* (math,consult,edu).
Just adding caveats to Gregs good basic advice, there are indeed many
papers on different forms of cross-validation.
Gavin...@googlemail.com
ISTR that one is a very rough approximation to LOO CV, it is useful
for model selection, but not for performance evaluation. The paper by
Olivier Chapelle I mentioned earlier compares several such bounds/
approximations and also explains the most accurate approximation (the
span bound).
> Two Efficient Methods for Computing Leave-One-Out Error in
> SVM Algorithms (2000) by S. Sathiya Keerthi, Chong Jin Ong,
> Martin M. S. Lee
> Download:http://guppy.mpe.nus.edu.sg/~mpessk/svm/loo.ps.gz
>
> A data parallel approach for large-scale gaussian process
> modeling (2002 )by Andy J. Keane, Arindam Choudhury, Arindam
> Choudhury, Prasanth B. Nair, Prasanth B. Nair, Andy J. Keane
> {a. Choudhury, P. B. Nair in Proc. the Second SIAM
> International Conference on Data Mining)
> Download:http://www.siam.org/meetings/sdm02/proceedings/sdm
For Gaussian processes, you can get the leave-one-out error almost for
free, see the book by Rasmussen and Williams. For pattern
recognition, an approximation that is useful for model selection is
also available (I have a publication in Machine Learning for kernel
logistic regression, the Gaussian Process equivalent using the Laplace
approximation is along similar lines, but using the Expectation
Propagation approximation the LOO error is available for free anyway
and I wouldn't recommend anyone to use the Laplace approximation for
GPC now that EP is available).
Greg
<GavinCaw...@googlemail.com> wrote:
> On Jun 17, 1:07 am, "Phil Sherrod" <PhilSher...@REMOVEcomcast.net>
> wrote:
>
>
> ... there are some short cuts you can take for SVMs and some useful
> approximations. Firstly if a pattern isn't a support vector then it
> will never be classified incorrectly during leave-one-out cross-
> validation (that is easy to prove). Also I am pretty sure that any
> pattern that is misclassified in training will always be misclassified
> in leave-one-out cross-validation. So if you have trained the model
> on the full data, you only need to investigate the folds in which a
> correctly classified support vector will be left out.
>
> Secondly you can make a good approximation of the leave-one-out error
> by borrowing a technique from least-squares regression. See the work
> of Olivier Chapelle (there was a paper on tuning multiple parameters
> for SVMs in the journal Machine Learning, which would be a good place
> to start).
In linear, quadratic and closest cluster classifiers, it is possible
to add or remove the effect of a single observation from the model.
Since you use the term "approximation" can you explain what is
different
here?
-----SNIP
> Basically LOO is approximately unbiased (i.e. the difference between
> the expected LOO error and the true error is approximately zero, where
> the expectation is over random training sets sampled from the same
> underlying distribution), which is a nice feature for performance
> evaluation, but not for model selection (where low variance is at
> least as important).
It's still a nice feature. However, the no-free-lunch bias/variance
tradeoff penalizes too highly for it to be important.
> However, LOO has a high variance (you get a wide spread of values for
> the LOO error for different sets of training data sampled from the
> underlying distribution), which is undesirable both for performance
> prediction and model selection. This means that you can easily get a
> misleadingly low or high value due to the peculiarities of the
> particular sample you are looking at.
>
> On the other hand, if you have a very small dataset, then cross-
> validation can have a very high bias because each model is trained on
> a smaller amount of data, so if the data were only just large enough
> to train the model in the first place, cross-validation will have a
> significant pessimistic bias. In that case, it may be worth trading
> off the variance of leave-one-out against the bias of k-fold cross-
> validation, so it is a case of "horses for courses".
In this case a viable alternative is to use leave-v-out XVAL where
there can be as many as N-choose-v estimates for each v with v = 1,
2,...,V.
> Personally I am becoming more in favour of bootstrapping instead.
I have used a bastardized form of bootstrapping by averaging over
M trials of modified k-fold XVAL. The modification involved adding
N/k random duplicates to the training sets to obtain a training set
size of N.
> The reason that leave-one-out is used so often for kernel machine is
> that it can be evaluated or approximated very cheaply, so even though
> it has a high variance it makes a good model selection criterion > (seehttp://theoval.cmp.uea.ac.uk/~gccfor some examples, including papers
> and MATLAB code). The problem of over-fitting due to the variance of
> the LOO estimator can be alleviated by using a higher level
> regularisation term, which I have found to be useful.
So, to mitigate the concerns of Frank Harrell that I posted
in a previous reply, use regularization.
Informative post.
Thanks.
Greg
Gavin...@googlemail.com
> On Jun 19, 4:34 am, "GavinCaw...@googlemail.com"
>
>
>
> <GavinCaw...@googlemail.com> wrote:
> > On Jun 17, 1:07 am, "Phil Sherrod" <PhilSher...@REMOVEcomcast.net>
> > wrote:
>
> -----SNIP
>
> > ... there are some short cuts you can take for SVMs and some useful
> > approximations. Firstly if a pattern isn't a support vector then it
> > will never be classified incorrectly during leave-one-out cross-
> > validation (that is easy to prove). Also I am pretty sure that any
> > pattern that is misclassified in training will always be misclassified
> > in leave-one-out cross-validation. So if you have trained the model
> > on the full data, you only need to investigate the folds in which a
> > correctly classified support vector will be left out.
>
> > Secondly you can make a good approximation of the leave-one-out error
> > by borrowing a technique from least-squares regression. See the work
> > of Olivier Chapelle (there was a paper on tuning multiple parameters
> > for SVMs in the journal Machine Learning, which would be a good place
> > to start).
>
> In linear, quadratic and closest cluster classifiers, it is possible
> to add or remove the effect of a single observation from the model.
> Since you use the term "approximation" can you explain what is
> different
> here?
For L2 SVMs, the KKT conditions that hold at the optimum of the
training criterion are the same as linear least squares regression
using only the support vectors, so you can use a similar leave-one-out
approach to that used in linear regression. However, this assumes
that the set of support vectors doesn't change during the leave-one-
out procedure, but that isn't neccessarily the case, so in practice it
is only an approximation. The corresponding method for L1 SVMs have
similar issues.
> > Basically LOO is approximately unbiased (i.e. the difference between
> > the expected LOO error and the true error is approximately zero, where
> > the expectation is over random training sets sampled from the same
> > underlying distribution), which is a nice feature for performance
> > evaluation, but not for model selection (where low variance is at
> > least as important).
>
> It's still a nice feature.
for model selection, only a good correllation is required for model
selection, so scalings and offsets (which would be sources of bias)
don't matter. Lower bias doesn't neccessarily give a better
correlation, so it is better to focus on the correllation rather than
bias.
> However, the no-free-lunch bias/variance
> tradeoff penalizes too highly for it to be important.
>
> > However, LOO has a high variance (you get a wide spread of values for
> > the LOO error for different sets of training data sampled from the
> > underlying distribution), which is undesirable both for performance
> > prediction and model selection. This means that you can easily get a
> > misleadingly low or high value due to the peculiarities of the
> > particular sample you are looking at.
>
> > On the other hand, if you have a very small dataset, then cross-
> > validation can have a very high bias because each model is trained on
> > a smaller amount of data, so if the data were only just large enough
> > to train the model in the first place, cross-validation will have a
> > significant pessimistic bias. In that case, it may be worth trading
> > off the variance of leave-one-out against the bias of k-fold cross-
> > validation, so it is a case of "horses for courses".
>
> In this case a viable alternative is to use leave-v-out XVAL where
> there can be as many as N-choose-v estimates for each v with v = 1,
> 2,...,V.
yep, ISTR there is a useful discussion of the benefits of that
approach in the FAQ
> > Personally I am becoming more in favour of bootstrapping instead.
>
> I have used a bastardized form of bootstrapping by averaging over
> M trials of modified k-fold XVAL. The modification involved adding
> N/k random duplicates to the training sets to obtain a training set
> size of N.
I have used repeated randomised k-fold x-val as well. To a first
approximation (for any sensible approach), the more processor time you
are willing to spend on resampling, the better (although it is a case
of diminishing returns).
> > The reason that leave-one-out is used so often for kernel machine is
> > that it can be evaluated or approximated very cheaply, so even though
> > it has a high variance it makes a good model selection criterion > (seehttp://theoval.cmp.uea.ac.uk/~gccforsome examples, including papers
> > and MATLAB code). The problem of over-fitting due to the variance of
> > the LOO estimator can be alleviated by using a higher level
> > regularisation term, which I have found to be useful.
>
> So, to mitigate the concerns of Frank Harrell that I posted
> in a previous reply, use regularization.
overfitting the model selection criterion is basically the same type
of problem as over-fitting the training criterion in that both involve
trying too hard to optimise a performance statistic based on a finite
sample of data, so the solutions that work with the training criterion
are likely to work with the model selection criterion as well
(regularisation, early stopping, not having too many hyper-parameters,
ensembling). My initial thought was to add an extra regularisation
term as it could be done effectively for free. It seems to work well,
but there is much research left to be done!
Of course if you use a fully Bayesian approach you would use sampling
to marginalise over both the model parameters and the hyper-
parameters, and since no optimisation is done, the over-fitting
problem is more or less eliminated.
Paul Birke
wrote:
> superior to 10-fold cross validation (CV).
not even, I do not even trust it.
lots of papers I got off internet just around Christmas time when I
went through this recently with my German colleague and we agree 10fcv
is way to go. I would prefer to use "optimal jittering" but not on
quite a good basis I think as ten fold.
Nicely tell your customer he/she is quite wrong.
best wishes
Paul in Guelph
This is particularly inconvenient because they want to
> train an SVM model with 100 variables and about 2500 data rows. Hence, for LOO validation, 2500
> large models must be trained and tested. This is requiring several days of computer time.
>
> I recall a discussion a year or two ago about the merits of LOO versus CV. As I recall, there were
> some convincing arguments that CV is actually superior to LOO, but I can't remember what those
> arguments were. Can someone please enlighten me?
>
> --
> Phil Sherrod
> (PhilSherrod 'at' comcast.net)http://www.dtreg.com (Decision trees, Neural networks, SVM)http://www.nlreg.com (Nonlinear Regression)