BACKGROUND
the unique characteristics of microarray data have stimulated the development of a multitude of analysis methods.
microarray data is distinguished by very small numbers of samples compared to the number of features measured.
most previous machine learning methods have been developed on data where the opposite holds true; the number of samples is much larger than the number of features.
as a result, such analysis methods have to be modified for microarray datasets.
an example is the common paradigm of splitting the data-set into training and test data.
the training data is used for selecting features and training a classifier.
once a final classifier has been specified, it can be used to predict the classes of the test samples.
the mean error on a sufficiently large  test dataset gives the true error of the classifier.
when the number of samples n is small, it is important to ensure that the data used to test the classifier is not part of the data used to train it.
testing the classifier on the same samples that were used to train it gives the re-substitution estimate of the true error, which is known to give falsely low  error estimates for small n.
with microarray data, splitting the sample into large training and test sets is usually not feasible since the number of samples is so small.
cross-validation  is one solution to the lack of sufficiently large training and testing sets  <cit> , where, instead of testing a fixed classifier  we have a fixed classifier training algorithm.
a classifier training algorithm takes a set of samples and does feature selection and classifier training and returns a single, well defined classifier.
in cv, part of the data is left out and the rest is used by the classifier training algorithm to develop a classifier.
the classifier thus obtained is used to predict the classes of the left out samples.
this loop is repeated for different left out portions.
the average error thus obtained on the entire dataset  can be interpreted as an estimate of the true error for the classifier we would obtain if we used the classifier training algorithm on the entire dataset.
in the case where the left out data consists of one sample only , it can be shown that the cv error estimate is an almost unbiased estimate of the true error expected on an independent test set for the classifier one would obtain if the classifier training algorithm was used on the entire dataset .
however, cv methods are proven to be unbiased only if all the various aspects of classifier training takes place inside the cv loop.
this means that all aspects of training a classifier e.g.
feature selection, classifier type selection and classifier parameter tuning takes place on the data not left out during each cv loop.
it has been shown that violating this principle in some ways can result in very biased estimates of the true error.
one way is to use all of the training data to choose the genes that discriminate between the two classes and only change the classifier parameters inside the cv loop.
this violates the principle that feature selection must be done for each loop separately, on the data that is not left out.
as pointed out by simon et al.
<cit> , ambroise and mclachlan  <cit>  and reunanen  <cit> , this gives a very biased estimate of the true error; not much better than the resubstitution estimate.
over-optimistic estimates of error close to zero are obtained, even for data where there is no real difference between the two classes.
another violation of the principle is to do any kind of classifier parameter selection outside the cv loop.
examples of these classifier parameters are the numbers of neighbors for a nearest neighbor classifier or kernel parameters for the support vector machine  classifier.
to find the best values of these parameters for a given dataset, we can compute the cv error estimate for the dataset using different values of the parameters.
then the classifier parameter with the minimum cv error estimate is chosen to create the final classifier.
the final classifier is trained on the entire dataset using the chosen optimal classifier parameters.
this comes under the general term of wrapper methods, where a cv algorithm is "wrapped" inside a search algorithm that tries to minimize the cv error.
such wrapper methods have proven very useful for data-driven adaptation of classifier parameters.
however, this involves a kind of additional training of the classifier  that is done outside the cv loop.
this violates the assumption that all training is done within the cv loop on the data not left out.
thus the guarantee of unbiased estimation of true error is not valid and there is a possibility of bias.
in other words, the cv error estimate for the classifier parameters that minimize the cv error estimate could be a biased estimate of the true error of the final classifier trained on all the data using the optimal classifier parameters.
we investigate this possibility using two wrapper algorithms.
the first is the shrunken centroids method of tibshirani et al.
<cit>  where an optimum value of a classifier parameter Δ that controls the degree of shrinkage is obtained as the one that minimizes the 10-fold cv error.
the second is a variant of the support vector machine proposed by peng et al.
<cit>  which selects svm kernel parameters that minimize the leave-one-out-cv  error.
the first article uses both the cv error estimate on the training set and the error on the test set for determining the optimal value of the parameters, thus making the test set part of the training process.
the second article presents only the minimum cv error estimate obtained on the training set.
the true error obtained on an independent test set is not given for either.
since selection of classifier parameters that minimize cv error estimates is a kind of training, it should be included as part of the classifier training algorithm.
thus the classifier training algorithm in this case is the complete wrapper algorithm where, given a dataset, the classifier is trained the following way.
first the cv error estimate is computed for different values of the classifier tuning parameters.
then, the parameters with the smallest cv error estimate are used to create a classifier using all the data.
this satisfies the definition of a classifier training algorithm, i.e.
an algorithm that takes a dataset and returns a single, well defined classifier.
now that we have a wrapper algorithm that is a well defined classifier training algorithm, we can use cv to get an estimate of the true error for the classifier it returns.
we can embed the complete wrapper algorithm  inside another cv loop that computes the error estimate.
note that this is no different from the usual cv method.
here, instead of using cv to find an error estimate for a particular classifier  we use cv to find an error estimate for an optimized classifier .
thus there are two cv loops; the inner loop is part of the wrapper algorithm and the outer loop computes an estimate of the true error.
a similar method was used by izuka et al.
<cit> .
in this article, we investigate the effect on the bias when using this nested cv approach.
shrunken centroids
this classifier, originally proposed by tibshirani et al  <cit> , is an extension of the nearest centroid classifier.
in the nearest centroid classifier the training set is used to calculate the centroids x¯1
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaaieqacuwf4baegaqeamaabaaaleaacqaixaqmaeqaaaaa@2f5f@ and x¯2
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaaieqacuwf4baegaqeamaabaaaleaacqaiyagmaeqaaaaa@2f61@  for the two classes.
a new sample is compared to the two centroids and classified according to the class of the nearest centroid.
in the shrunken centroids method, a parameter Δ is used to shrink the class centroids towards the overall centroid after standardizing by the within class standard deviation.
the centroid belonging to class k is brought closer to the overall centroid x¯
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacuwg4baegaqeaaaa@2e3d@  by
x¯k=x¯+mksign+
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaaieqacuwf4baegaqeamaabaaaleaacqwgrbwaaeqaaogaeyypa0jaf8heagnbaebacqghrawkcqwftbqbdawgaawcbagaem4aasgabeaakmaabmaabagae83camnaey4kasiaem4cam3aasbaasqaaiabicdawaqabaaakiaawicacaglpaaacqqgzbwccqqgpbqacqqgnbwzcqqgubgbcqggoaakcqwfkbazdawgaawcbagaem4aasgabeaakiabcmcapmaabmaabawaaqwaaeaacqwfkbazdawgaawcbagaem4aasgabeaaaogaay5bslaawia7aiabgkhitiabfs5aebgaayjkaiaawmcaamaabaaaleaacqghrawkaeqaaogaaczcaiaaxmaadaqadaqaaiabigdaxagaayjkaiaawmcaaaaa@5571@
where s is the vector of pooled within class standard deviation for all genes, s <dig> is the median of the elements of s, dk is given by
dk=x¯k−x¯mk
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaaieqacqwfkbazdawgaawcbagaem4aasgabeaakiabg2da9maalaaabagaf8heagnbaebadawgaawcbagaem4aasgabeaakiabgkhitiqb=hha4zaaraaabagae8xba02aasbaasqaaiabdugarbqabagcdaqadaqaaiab=nhazjabgucariabdohaznaabaaaleaacqaiwaamaeqaaagccagloagaayzkaaaaaiaaxmaacawljawaaewaaeaacqaiyagmaiaawicacaglpaaaaaa@4366@
and + denotes the positive part of the quantity in the parenthesis, i.e.
equal to the quantity if it is greater than zero, and zero otherwise.
thus genes which are not very differentially expressed will contribute less to the classification than genes that are more discriminating.
the parameter Δ can be varied to vary the number of genes used.
in the original paper, 10-fold cv is used to obtain the cv error estimate for a particular choice of Δ. there is no objective guideline given for selecting Δ based only on the training data.
the authors vary Δ and use the value that minimizes the cv error estimate on the training set and the error on the testing data simultaneously.
thus the test set is used in the selection of the classifier parameters, which is problematic.
support vector machines
peng et al.
present a method for feature selection using genetic algorithms  and recursive feature elimination  in combination with a support vector machine  classifier  <cit> .
svms were introduced by vapnik  <cit>  as linear hyperplanes that separate data belonging to different classes while maximizing the margin, or the distance of the training samples to the linear separating hyperplane.
denote the two classes by  <dig> and - <dig>  for a sample x consisting of p measurements  the linear hyperplane classifier c predicts the class according to
c={1if x^w′≥0−1if x^w′<0
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqwgjbwycqggoaakcqwg4baecqggpaqkcqgh9aqpdagabaqaauaabeqaciaaaeaacqaixaqmaeaacqqgpbqacqqgmbgzcqqggaaiieqacuwf4baegaqcaiqb=dha3zaafagaeyyzimraegimaadabagaeyoei0iaegymaedabagaeeyaakmaeeozaymaeeiiaaiaf8heagnbakaacuwf3bwdgaqbaiabgyda8iabicdawaaaaiaawuhaaiaaxmaacawljawaaewaaeaacqaizawmaiaawicacaglpaaaaaa@4b82@
for a weight vector w = ⌊w <dig> w <dig> ... wp⌋ and the augmented sample vector x^
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaaieqacuwf4baegaqcaaaa@2e3b@ obtained by appending sample x with a constant  <dig>  i.e.
x^
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaaieqacuwf4baegaqcaaaa@2e3b@ = ⌊ <dig>  x <dig>  ..., xp⌋.
the margin of a sample x of class y ∈ {- <dig> } is defined as yx^
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaaieqacuwf4baegaqcaaaa@2e3b@w' and it plays a very important role in svm.
the margin of correctly classified samples is positive and that for misclassified samples is negative.
the margin of the classifier is defined as the smallest margin of all the training samples.
the svm tries to find a w such that the margin is maximized while the norm of the weight vector, ⟨w, w⟩ is minimized.
this is equivalent to minimizing the cost function
Φ=12〈w,w〉+c∑i=1nξi
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqqhmogrcqggoaakieqacqwf3bwdcqggpaqkcqgh9aqpdawcaaqaaiabigdaxaqaaiabikdayaaadaaadaqaaiab=dha3jabcycasiab=dha3bgaayzkjiaawqyiaiabgucariabdoeadnaaqahabaaccigae4nvdg3aasbaasqaaiabdmgapbqabagccqggoaakcqwf3bwdcqggpaqkasqaaiabdmgapjabg2da9iabigdaxaqaaiabd6gaubqdcqghris5aogaaczcaiaaxmaadaqadaqaaiabisda0agaayjkaiaawmcaaaaa@4d18@
where
ξi  = +
and + denotes the positive part of the quantity in the parenthesis, as above, i.e.
equal to the quantity if it is greater than zero, and zero otherwise.
since the capacity of the classifier increases with increasing norm of the weight vector, the parameter c also controls the tradeoff between the size of the margin and the capacity of the classifier.
since the samples need to be represented only in the form of scalar products, this formulation can be extended to non-linear classifiers by the introduction of kernels.
kernels are the functional representation of scalar products in transformed space.
it can be shown that such a transformation leaves the optimization problem unchanged except that the inner product ⟨x <dig>  x2⟩ is replaced by the kernel k. in the case of very high  dimensional transformed space, the kernel is usually easier to compute than doing the transformation followed by scalar product.
for gaussian kernel svm , the kernel is given by
k = exp
the spread of the kernel function is given by γ, which can be varied to adapt the kernel to the data.
the larger the value of γ, the more peaked the corresponding transformations of the feature vectors are, and the higher the capacity of the classifier.
peng et al use the leave-one-out-cv  error to tune the kernel parameters.
loocv is a cv scheme where one sample is left out during each iteration.
the average classification error obtained is an almost unbiased estimate of the true error.
in , the training data is used to select an appropriate kernel  and set of parameters that minimize the loocv error estimate.
however no independent test set is used and only the final loocv error estimate on the training set is reported.
RESULTS
implementation
for each simulation we generated at least  <dig> sets of  <dig> samples, of which  <dig> belonged to class  <dig> and the remaining  <dig> to class  <dig>  each sample was a vector of  <dig> features .
for some of the cases we used "null" data sets where no gene is differentially expressed between the two classes.
for each gene, the population mean expressions in both classes were the same, namely zero.
thus none of the features are truly discriminatory between the two classes.
we also used data generated from a "non-null" distribution for validating the nested cv approach.
in this case, instead of using a "null distribution" , we simulated differential expression by fixing  <dig> genes  to have a population mean differential expression of  <dig> between the two classes.
samples from one class were drawn from a mean zero, unit variance, multivariate normal distribution while samples for the second class had  <dig> genes with mean  <dig>  unit variance normal and the rest  <dig> genes were of mean zero, unit variance normal distribution.
shrunken centroids
this was implemented in matlab™ .
for this case we used the "null" dataset with no difference between the two classes.
for each  <dig> sample dataset, we computed the 10-fold cv error for the shrunken centroid classifier for values of Δ between  <dig>  and  <dig>  the value of Δ with the minimum 10-fold cv error cv was determined.
Δ* = arg min
if two values of Δ had the same error, the larger value was chosen .
to determine if the cv error estimate cv is a unbiased estimate of the true error for a classifier built using all the  <dig> samples with parameter value Δ*, we created a shrunken centroid classifier using all  <dig> samples and parameter value of Δ*.
we call this the optimized shrunken centroids classifier.
this classifier was used to predict the class of  <dig> samples created independently using the "null" data distribution.
since these test samples were not part of the training set, the mean error on them will give us the true error te.
this process was repeated for each simulated 40-sample dataset providing empirical distributions of cvand te.
support vector machine
the same type of analysis was performed for the svm case.
the "null" data distribution was used to create the synthetic data.
for computational efficiency, we do not consider the complete algorithm used in .
instead of recursive feature elimination  for feature selection, we used the two sample t-statistics and selected the three features with the largest absolute t-statistic.
in lieu of genetic algorithms  as the search strategy, we used a simplified algorithm with a fixed gaussian kernel.
the classifier parameters tuned were c  and γ .
it must be noted that reducing the set of parameters over which one optimizes, as we have done here, may potentially reduce the amount of bias obtained.
the leave-one-out-cv  was used to compute the cv error estimate for each point on a grid of c and γ values .
the cv error estimate was computed by leaving out each of the  <dig> samples in turn, selecting the  <dig> best features using the t-statistic on the remaining  <dig> samples and creating an svm classifier using the fixed c and γ values.
this classifier was used to predict the class of the left out sample.
the average error on the  <dig> samples is a cv error estimate cv for the values of c and γ used.
this was repeated for all of the grid values.
we used the libsvm package developed by chang and lin  <cit>  to develop the classifier.
similar to the analysis on shrunken centroids, we find the value of parameters that minimize the cv error estimate
= arg min )
to compute the true error, an svm classifier with parameters c* and γ * was built using all  <dig> samples, and the top  <dig> features based on all  <dig> samples.
we call this the optimized svm classifier.
this classifier was used to predict the classes of a large test set of  <dig> samples with the same distribution as the training set .
the mean error on the test set gives us the true error te.
nested cv with shrunken centroids and svm
we evaluated the nested cv approach for the shrunken centroids classifier with Δ optimized using10-fold cv .
the "null" data distribution was used to generate the datasets.
finding the optimum value Δ* of the classifier parameter was done exactly like described above, as was finding the true error te.
the only thing that changes is how a new estimate of the true error is computed.
instead of using the cv error estimate cv for the optimal Δ, we used the nested cv error estimate.
the nested cv error estimate is computed this way.
one sample  was left out and the Δ for the shrunken centroids classifier was selected on the remaining  <dig> samples by minimizing the 10-fold cv.
this is done exactly as above except that the wrapper algorithm is restricted to  <dig> samples, instead of  <dig>  the wrapper algorithm determines an optimal value of Δ using the  <dig> samples and then creates a classifier with the same  <dig> samples and the optimal value selected based on these samples.
this classifier is used to predict the class of the left out sample.
this was done for each of the  <dig> samples, left out in turn.
the average error over the samples is the nested cv error estimate cvnest for the optimized shrunken centroid classifier.
repeating this for several synthetic datasets gives us the empirical distribution of cvnest and te.
the nested cv approach was also evaluated for the optimized svm classifier.
here we used the "non null" data distribution to create the training samples  and the test samples .
nested cv is used to find the nested cv error estimate cvnest of the svm classifier optimized for parameters c and γ. the procedure is exactly the same as that described for optimized shrunken centroids above, except that the classifier training algorithm being evaluated is the optimized svm classifier algorithm detailed earlier.
fig  <dig> shows the empirical distributions of cv, the cv error estimate for the optimal Δ and te, the true error for the optimal Δ for the optimized shrunken centroid classifier.
fig  <dig> shows the distributions for cv and te for the optimized svm classifier.
in both plots, the cv error estimate is centered over means that are distinctly smaller than the mean true errors.
since both these simulations were done with "null" data, the true errors are centered on 50% while the cv error estimates have a lower mean.
numerical results are shown in table  <dig>  even though the mean true error is 50% , the cv error estimate on the training set averages  <dig> % for the optimized shrunken centroid classifier and  <dig> % for the optimized svm classifier.
on more than one-fifth of the random training datasets, the bias is more than 20% for the classifiers.
fig  <dig> shows the distributions for the nested cv error estimate cvnest and the true error te for the optimized shrunken centroids.
we obtain an almost unbiased estimate of the true error.
the mean nested cv error estimate is a slight overestimate of the true error , since the classifier used in each nested cv iteration is based on  <dig> samples, while the classifier used on the test set is trained on  <dig> samples.
fig  <dig> shows the distribution of the nested cv error estimate cvnest and the true error te for the optimized svm algorithm on the "non null" data sets.
we obtain a mean nested cv error estimate of  <dig> % compared to the true error of  <dig> %.
the higher estimate of training error compared to test error can again be attributed to the lower number of samples being used  to create the classifier in the nested cv iteration.
CONCLUSIONS
our results demonstrate that although it is reasonable to optimize classifier parameters by minimizing cross validated error rates, the resulting minimum cv error estimate is not an unbiased estimate of the true error that can be expected from the final classifier on independent data.
the difference between the cv error estimate and the true error can be greater than 20% more than one-fifth of the time which can be very significant in classification problems where the overall accuracy is not very high .
in our work, we observed this bias for two different resampling methods .
will this bias, possibly with differing magnitudes, be present for other cross validation schemes?
since the bias is caused by the variability in the estimates of prediction error for different values of the tuning parameters it is a general phenomenon.
this can be seen intuitively in the following simple explanation.
assume that classifier parameter α can only take discrete values α <dig>  α <dig>  ..., αk and that the true prediction error e is independent of the value of the parameter.
thus all values of the parameter will give the same true error.
however, due to the variability in the errors estimated by resampling, different parameter values will lead to different prediction error estimates.
let the error estimates be denoted by e <dig>  e <dig>  ..., ek.
if we assume that the resampling method is median unbiased, it is easy to see that the probability that the minimum of the errors is lesser than e
pr =  <dig> - k
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaadaqadaqaamaalaaabagaegymaedabagaegomaidaaagaayjkaiaawmcaamaacaaaleqabagaem4saseaaaaa@3173@
this implies that for large k, there is a high probability that choosing the minimum resampled error will give a biased estimate of the true error.
even if there is no parameter selection being done, any resampling method for estimating error is subject to some bias and variance .
we have mentioned above the bias of the loocv method  that occurs because a subset of training samples is used to create the classifier in the cv loop while the final classifier is created using all the samples.
we call this the inherent bias.
however, as we have shown in our results, when additional parameter selection is being done, the variance of the estimates results in an additional parameter selection bias.
the parameter selection bias adds to the inherent bias to form the total bias of the resampling procedure.
it must be noted that inherent bias can be either negative or positive .
the parameter selection bias, on the other hand, is always negative.
the parameter selection bias is smaller for resampling methods with smaller variances, e.g.
.
<dig> bootstrap  <cit>  and bootstrap cv  <cit> .
however, low variance methods can also have a large inherent bias  <cit>  .
the total bias  is what must be kept in mind when interpreting error estimates.
if the inherent bias is positive, the parameter selection bias will subtract from it and possibly bring the error estimate closer to the true error.
however, if the inherent bias is negative, the parameter selection bias will exacerbate it.
cross-validation can be a useful method for selecting tuning parameters for a classifier, but the generalization error for the resulting classifier should be estimated correctly.
this can be accomplished by a large validation set that is independent of data used for parameter tuning.
however this requires a large number of samples that can be split into training and validation sets.
another way, used in this paper and illustrated by the method of izuka et al.
<cit> , is to leave out some samples that are not used in the cv tuning of the parameters.
a tuned classifier is then developed on the reduced training set and tested on the left out samples; this procedure is repeated for several sets of left out samples.
this is effectively two nested cv loops; the outer loop estimates the generalization error while the inner cv is used for tuning the parameters.
if the number of samples left out at each step of the outer loop is not too large, this gives an almost unbiased estimate of the true error.

 the unique characteristics of microarray data have stimulated the development of a multitude of analysis methods. microarray data is distinguished by very small numbers of samples compared to the number of features measured. most previous machine learning methods have been developed on data where the opposite holds true; the number of samples is much larger than the number of features. as a result, such analysis methods have to be modified for microarray datasets. an example is the common paradigm of splitting the data-set into training and test data. the training data is used for selecting features and training a classifier. once a final classifier has been specified, it can be used to predict the classes of the test samples. the mean error on a sufficiently large test dataset gives the true error of the classifier. when the number of samples n is small, it is important to ensure that the data used to test the classifier is not part of the data used to train it. testing the classifier on the same samples that were used to train it gives the re-substitution estimate of the true error, which is known to give falsely low error estimates for small n. with microarray data, splitting the sample into large training and test sets is usually not feasible since the number of samples is so small. cross-validation is one solution to the lack of sufficiently large training and testing sets, where, instead of testing a fixed classifier we have a fixed classifier training algorithm. a classifier training algorithm takes a set of samples and does feature selection and classifier training and returns a single, well defined classifier. in cv, part of the data is left out and the rest is used by the classifier training algorithm to develop a classifier. the classifier thus obtained is used to predict the classes of the left out samples. this loop is repeated for different left out portions. the average error thus obtained on the entire dataset can be interpreted as an estimate of the true error for the classifier we would obtain if we used the classifier training algorithm on the entire dataset. in the case where the left out data consists of one sample only, it can be shown that the cv error estimate is an almost unbiased estimate of the true error expected on an independent test set for the classifier one would obtain if the classifier training algorithm was used on the entire dataset. however, cv methods are proven to be unbiased only if all the various aspects of classifier training takes place inside the cv loop. this means that all aspects of training a classifier e.g. feature selection, classifier type selection and classifier parameter tuning takes place on the data not left out during each cv loop. it has been shown that violating this principle in some ways can result in very biased estimates of the true error. one way is to use all of the training data to choose the genes that discriminate between the two classes and only change the classifier parameters inside the cv loop. this violates the principle that feature selection must be done for each loop separately, on the data that is not left out. as pointed out by simon et al., ambroise and mclachlan and reunanen, this gives a very biased estimate of the true error; not much better than the resubstitution estimate. over-optimistic estimates of error close to zero are obtained, even for data where there is no real difference between the two classes. another violation of the principle is to do any kind of classifier parameter selection outside the cv loop. examples of these classifier parameters are the numbers of neighbors for a nearest neighbor classifier or kernel parameters for the support vector machine classifier. to find the best values of these parameters for a given dataset, we can compute the cv error estimate for the dataset using different values of the parameters. then the classifier parameter with the minimum cv error estimate is chosen to create the final classifier. the final classifier is trained on the entire dataset using the chosen optimal classifier parameters. this comes under the general term of wrapper methods, where a cv algorithm is "wrapped" inside a search algorithm that tries to minimize the cv error. such wrapper methods have proven very useful for data-driven adaptation of classifier parameters. however, this involves a kind of additional training of the classifier that is done outside the cv loop. this violates the assumption that all training is done within the cv loop on the data not left out. thus the guarantee of unbiased estimation of true error is not valid and there is a possibility of bias. in other words, the cv error estimate for the classifier parameters that minimize the cv error estimate could be a biased estimate of the true error of the final classifier trained on all the data using the optimal classifier parameters. we investigate this possibility using two wrapper algorithms. the first is the shrunken centroids method of tibshirani et al. where an optimum value of a classifier parameter Δ that controls the degree of shrinkage is obtained as the one that minimizes the 10-fold cv error. the second is a variant of the support vector machine proposed by peng et al. which selects svm kernel parameters that minimize the leave-one-out-cv error. the first article uses both the cv error estimate on the training set and the error on the test set for determining the optimal value of the parameters, thus making the test set part of the training process. the second article presents only the minimum cv error estimate obtained on the training set. the true error obtained on an independent test set is not given for either. since selection of classifier parameters that minimize cv error estimates is a kind of training, it should be included as part of the classifier training algorithm. thus the classifier training algorithm in this case is the complete wrapper algorithm where, given a dataset, the classifier is trained the following way. first the cv error estimate is computed for different values of the classifier tuning parameters. then, the parameters with the smallest cv error estimate are used to create a classifier using all the data. this satisfies the definition of a classifier training algorithm, i.e. an algorithm that takes a dataset and returns a single, well defined classifier. now that we have a wrapper algorithm that is a well defined classifier training algorithm, we can use cv to get an estimate of the true error for the classifier it returns. we can embed the complete wrapper algorithm inside another cv loop that computes the error estimate. note that this is no different from the usual cv method. here, instead of using cv to find an error estimate for a particular classifier we use cv to find an error estimate for an optimized classifier. thus there are two cv loops; the inner loop is part of the wrapper algorithm and the outer loop computes an estimate of the true error. a similar method was used by izuka et al.. in this article, we investigate the effect on the bias when using this nested cv approach. shrunken centroids this classifier, originally proposed by tibshirani et al, is an extension of the nearest centroid classifier. in the nearest centroid classifier the training set is used to calculate the centroids x¯1 mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaaieqacuwf4baegaqeamaabaaaleaacqaixaqmaeqaaaaa@2f5f@ and x¯2 mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaaieqacuwf4baegaqeamaabaaaleaacqaiyagmaeqaaaaa@2f61@ for the two classes. a new sample is compared to the two centroids and classified according to the class of the nearest centroid. in the shrunken centroids method, a parameter Δ is used to shrink the class centroids towards the overall centroid after standardizing by the within class standard deviation. the centroid belonging to class k is brought closer to the overall centroid x¯ mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacuwg4baegaqeaaaa@2e3d@ by x¯k=x¯+mksign+      mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaaieqacuwf4baegaqeamaabaaaleaacqwgrbwaaeqaaogaeyypa0jaf8heagnbaebacqghrawkcqwftbqbdawgaawcbagaem4aasgabeaakmaabmaabagae83camnaey4kasiaem4cam3aasbaasqaaiabicdawaqabaaakiaawicacaglpaaacqqgzbwccqqgpbqacqqgnbwzcqqgubgbcqggoaakcqwfkbazdawgaawcbagaem4aasgabeaakiabcmcapmaabmaabawaaqwaaeaacqwfkbazdawgaawcbagaem4aasgabeaaaogaay5bslaawia7aiabgkhitiabfs5aebgaayjkaiaawmcaamaabaaaleaacqghrawkaeqaaogaaczcaiaaxmaadaqadaqaaiabigdaxagaayjkaiaawmcaaaaa@5571@ where s is the vector of pooled within class standard deviation for all genes, s is the median of the elements of s, dk is given by dk=x¯k−x¯mk      mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaaieqacqwfkbazdawgaawcbagaem4aasgabeaakiabg2da9maalaaabagaf8heagnbaebadawgaawcbagaem4aasgabeaakiabgkhitiqb=hha4zaaraaabagae8xba02aasbaasqaaiabdugarbqabagcdaqadaqaaiab=nhazjabgucariabdohaznaabaaaleaacqaiwaamaeqaaagccagloagaayzkaaaaaiaaxmaacawljawaaewaaeaacqaiyagmaiaawicacaglpaaaaaa@4366@ and + denotes the positive part of the quantity in the parenthesis, i.e. equal to the quantity if it is greater than zero, and zero otherwise. thus genes which are not very differentially expressed will contribute less to the classification than genes that are more discriminating. the parameter Δ can be varied to vary the number of genes used. in the original paper, 10-fold cv is used to obtain the cv error estimate for a particular choice of Δ. there is no objective guideline given for selecting Δ based only on the training data. the authors vary Δ and use the value that minimizes the cv error estimate on the training set and the error on the testing data simultaneously. thus the test set is used in the selection of the classifier parameters, which is problematic. support vector machines peng et al. present a method for feature selection using genetic algorithms and recursive feature elimination in combination with a support vector machine classifier. svms were introduced by vapnik as linear hyperplanes that separate data belonging to different classes while maximizing the margin, or the distance of the training samples to the linear separating hyperplane. denote the two classes by and - for a sample x consisting of p measurements the linear hyperplane classifier c predicts the class according to c={1if x^w′≥0−1if x^w′<0      mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqwgjbwycqggoaakcqwg4baecqggpaqkcqgh9aqpdagabaqaauaabeqaciaaaeaacqaixaqmaeaacqqgpbqacqqgmbgzcqqggaaiieqacuwf4baegaqcaiqb=dha3zaafagaeyyzimraegimaadabagaeyoei0iaegymaedabagaeeyaakmaeeozaymaeeiiaaiaf8heagnbakaacuwf3bwdgaqbaiabgyda8iabicdawaaaaiaawuhaaiaaxmaacawljawaaewaaeaacqaizawmaiaawicacaglpaaaaaa@4b82@ for a weight vector w = ⌊w w... wp⌋ and the augmented sample vector x^ mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaaieqacuwf4baegaqcaaaa@2e3b@ obtained by appending sample x with a constant i.e. x^ mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaaieqacuwf4baegaqcaaaa@2e3b@ = ⌊ x..., xp⌋. the margin of a sample x of class y ∈ {- } is defined as yx^ mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaaieqacuwf4baegaqcaaaa@2e3b@w' and it plays a very important role in svm. the margin of correctly classified samples is positive and that for misclassified samples is negative. the margin of the classifier is defined as the smallest margin of all the training samples. the svm tries to find a w such that the margin is maximized while the norm of the weight vector, ⟨w, w⟩ is minimized. this is equivalent to minimizing the cost function Φ=12〈w,w〉+c∑i=1nξi      mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqqhmogrcqggoaakieqacqwf3bwdcqggpaqkcqgh9aqpdawcaaqaaiabigdaxaqaaiabikdayaaadaaadaqaaiab=dha3jabcycasiab=dha3bgaayzkjiaawqyiaiabgucariabdoeadnaaqahabaaccigae4nvdg3aasbaasqaaiabdmgapbqabagccqggoaakcqwf3bwdcqggpaqkasqaaiabdmgapjabg2da9iabigdaxaqaaiabd6gaubqdcqghris5aogaaczcaiaaxmaadaqadaqaaiabisda0agaayjkaiaawmcaaaaa@4d18@ where ξi = +     and + denotes the positive part of the quantity in the parenthesis, as above, i.e. equal to the quantity if it is greater than zero, and zero otherwise. since the capacity of the classifier increases with increasing norm of the weight vector, the parameter c also controls the tradeoff between the size of the margin and the capacity of the classifier. since the samples need to be represented only in the form of scalar products, this formulation can be extended to non-linear classifiers by the introduction of kernels. kernels are the functional representation of scalar products in transformed space. it can be shown that such a transformation leaves the optimization problem unchanged except that the inner product ⟨x x2⟩ is replaced by the kernel k. in the case of very high dimensional transformed space, the kernel is usually easier to compute than doing the transformation followed by scalar product. for gaussian kernel svm, the kernel is given by k = exp     the spread of the kernel function is given by γ, which can be varied to adapt the kernel to the data. the larger the value of γ, the more peaked the corresponding transformations of the feature vectors are, and the higher the capacity of the classifier. peng et al use the leave-one-out-cv error to tune the kernel parameters. loocv is a cv scheme where one sample is left out during each iteration. the average classification error obtained is an almost unbiased estimate of the true error. in, the training data is used to select an appropriate kernel and set of parameters that minimize the loocv error estimate. however no independent test set is used and only the final loocv error estimate on the training set is reported.  implementation for each simulation we generated at least sets of samples, of which belonged to class and the remaining to class each sample was a vector of features. for some of the cases we used "null" data sets where no gene is differentially expressed between the two classes. for each gene, the population mean expressions in both classes were the same, namely zero. thus none of the features are truly discriminatory between the two classes. we also used data generated from a "non-null" distribution for validating the nested cv approach. in this case, instead of using a "null distribution", we simulated differential expression by fixing genes to have a population mean differential expression of between the two classes. samples from one class were drawn from a mean zero, unit variance, multivariate normal distribution while samples for the second class had genes with mean unit variance normal and the rest genes were of mean zero, unit variance normal distribution. shrunken centroids this was implemented in matlab™. for this case we used the "null" dataset with no difference between the two classes. for each sample dataset, we computed the 10-fold cv error for the shrunken centroid classifier for values of Δ between and the value of Δ with the minimum 10-fold cv error cv was determined. Δ* = arg min if two values of Δ had the same error, the larger value was chosen. to determine if the cv error estimate cv is a unbiased estimate of the true error for a classifier built using all the samples with parameter value Δ*, we created a shrunken centroid classifier using all samples and parameter value of Δ*. we call this the optimized shrunken centroids classifier. this classifier was used to predict the class of samples created independently using the "null" data distribution. since these test samples were not part of the training set, the mean error on them will give us the true error te. this process was repeated for each simulated 40-sample dataset providing empirical distributions of cvand te. support vector machine the same type of analysis was performed for the svm case. the "null" data distribution was used to create the synthetic data. for computational efficiency, we do not consider the complete algorithm used in. instead of recursive feature elimination for feature selection, we used the two sample t-statistics and selected the three features with the largest absolute t-statistic. in lieu of genetic algorithms as the search strategy, we used a simplified algorithm with a fixed gaussian kernel. the classifier parameters tuned were c and γ. it must be noted that reducing the set of parameters over which one optimizes, as we have done here, may potentially reduce the amount of bias obtained. the leave-one-out-cv was used to compute the cv error estimate for each point on a grid of c and γ values. the cv error estimate was computed by leaving out each of the samples in turn, selecting the best features using the t-statistic on the remaining samples and creating an svm classifier using the fixed c and γ values. this classifier was used to predict the class of the left out sample. the average error on the samples is a cv error estimate cv for the values of c and γ used. this was repeated for all of the grid values. we used the libsvm package developed by chang and lin to develop the classifier. similar to the analysis on shrunken centroids, we find the value of parameters that minimize the cv error estimate = arg min ) to compute the true error, an svm classifier with parameters c* and γ * was built using all samples, and the top features based on all samples. we call this the optimized svm classifier. this classifier was used to predict the classes of a large test set of samples with the same distribution as the training set. the mean error on the test set gives us the true error te. nested cv with shrunken centroids and svm we evaluated the nested cv approach for the shrunken centroids classifier with Δ optimized using10-fold cv. the "null" data distribution was used to generate the datasets. finding the optimum value Δ* of the classifier parameter was done exactly like described above, as was finding the true error te. the only thing that changes is how a new estimate of the true error is computed. instead of using the cv error estimate cv for the optimal Δ, we used the nested cv error estimate. the nested cv error estimate is computed this way. one sample was left out and the Δ for the shrunken centroids classifier was selected on the remaining samples by minimizing the 10-fold cv. this is done exactly as above except that the wrapper algorithm is restricted to samples, instead of the wrapper algorithm determines an optimal value of Δ using the samples and then creates a classifier with the same samples and the optimal value selected based on these samples. this classifier is used to predict the class of the left out sample. this was done for each of the samples, left out in turn. the average error over the samples is the nested cv error estimate cvnest for the optimized shrunken centroid classifier. repeating this for several synthetic datasets gives us the empirical distribution of cvnest and te. the nested cv approach was also evaluated for the optimized svm classifier. here we used the "non null" data distribution to create the training samples and the test samples. nested cv is used to find the nested cv error estimate cvnest of the svm classifier optimized for parameters c and γ. the procedure is exactly the same as that described for optimized shrunken centroids above, except that the classifier training algorithm being evaluated is the optimized svm classifier algorithm detailed earlier. fig shows the empirical distributions of cv, the cv error estimate for the optimal Δ and te, the true error for the optimal Δ for the optimized shrunken centroid classifier. fig shows the distributions for cv and te for the optimized svm classifier. in both plots, the cv error estimate is centered over means that are distinctly smaller than the mean true errors. since both these simulations were done with "null" data, the true errors are centered on 50% while the cv error estimates have a lower mean. numerical results are shown in table even though the mean true error is 50%, the cv error estimate on the training set averages % for the optimized shrunken centroid classifier and % for the optimized svm classifier. on more than one-fifth of the random training datasets, the bias is more than 20% for the classifiers. fig shows the distributions for the nested cv error estimate cvnest and the true error te for the optimized shrunken centroids. we obtain an almost unbiased estimate of the true error. the mean nested cv error estimate is a slight overestimate of the true error, since the classifier used in each nested cv iteration is based on samples, while the classifier used on the test set is trained on samples. fig shows the distribution of the nested cv error estimate cvnest and the true error te for the optimized svm algorithm on the "non null" data sets. we obtain a mean nested cv error estimate of % compared to the true error of %. the higher estimate of training error compared to test error can again be attributed to the lower number of samples being used to create the classifier in the nested cv iteration.  our results demonstrate that although it is reasonable to optimize classifier parameters by minimizing cross validated error rates, the resulting minimum cv error estimate is not an unbiased estimate of the true error that can be expected from the final classifier on independent data. the difference between the cv error estimate and the true error can be greater than 20% more than one-fifth of the time which can be very significant in classification problems where the overall accuracy is not very high. in our work, we observed this bias for two different resampling methods. will this bias, possibly with differing magnitudes, be present for other cross validation schemes? since the bias is caused by the variability in the estimates of prediction error for different values of the tuning parameters it is a general phenomenon. this can be seen intuitively in the following simple explanation. assume that classifier parameter α can only take discrete values α α..., αk and that the true prediction error e is independent of the value of the parameter. thus all values of the parameter will give the same true error. however, due to the variability in the errors estimated by resampling, different parameter values will lead to different prediction error estimates. let the error estimates be denoted by e e..., ek. if we assume that the resampling method is median unbiased, it is easy to see that the probability that the minimum of the errors is lesser than e pr = - k mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaadaqadaqaamaalaaabagaegymaedabagaegomaidaaagaayjkaiaawmcaamaacaaaleqabagaem4saseaaaaa@3173@     this implies that for large k, there is a high probability that choosing the minimum resampled error will give a biased estimate of the true error. even if there is no parameter selection being done, any resampling method for estimating error is subject to some bias and variance. we have mentioned above the bias of the loocv method that occurs because a subset of training samples is used to create the classifier in the cv loop while the final classifier is created using all the samples. we call this the inherent bias. however, as we have shown in our results, when additional parameter selection is being done, the variance of the estimates results in an additional parameter selection bias. the parameter selection bias adds to the inherent bias to form the total bias of the resampling procedure. it must be noted that inherent bias can be either negative or positive. the parameter selection bias, on the other hand, is always negative. the parameter selection bias is smaller for resampling methods with smaller variances, e.g.. bootstrap and bootstrap cv. however, low variance methods can also have a large inherent bias. the total bias is what must be kept in mind when interpreting error estimates. if the inherent bias is positive, the parameter selection bias will subtract from it and possibly bring the error estimate closer to the true error. however, if the inherent bias is negative, the parameter selection bias will exacerbate it. cross-validation can be a useful method for selecting tuning parameters for a classifier, but the generalization error for the resulting classifier should be estimated correctly. this can be accomplished by a large validation set that is independent of data used for parameter tuning. however this requires a large number of samples that can be split into training and validation sets. another way, used in this paper and illustrated by the method of izuka et al., is to leave out some samples that are not used in the cv tuning of the parameters. a tuned classifier is then developed on the reduced training set and tested on the left out samples; this procedure is repeated for several sets of left out samples. this is effectively two nested cv loops; the outer loop estimates the generalization error while the inner cv is used for tuning the parameters. if the number of samples left out at each step of the outer loop is not too large, this gives an almost unbiased estimate of the true error.
with "null" and "non null" data, we also tested a nested cv procedure, where an inner cv loop is used to perform the tuning of the parameters while an outer cv is used to compute an estimate of the error. random training datasets were created, with no difference in the distribution of the features between the two classes. some recent articles have proposed methods for optimizing classifiers by choosing classifier parameter values that minimize the cv error estimate. we have evaluated the validity of using the cv error estimate of the optimized classifier as an estimate of the true error expected on independent data. using these "null" datasets, we selected classifier parameter values that minimized the cv error estimate. the cv error estimate for the classifier with the optimal parameters was found to be a substantially biased estimate of the true error that the classifier would incur on independent data. even though there is no real difference between the two classes for the "null" datasets, the cv error estimate for the shrunken centroid with the optimal parameters was less than 30% on % of simulated training data-sets. we show that using cv to compute an error estimate for a classifier that has itself been tuned using cv gives a significantly biased estimate of the true error. proper use of cv for estimating true error of a classifier developed using a well defined algorithm requires that all steps of the algorithm, including classifier parameter tuning, be repeated in each cv loop. we used cv to optimize the classification parameters for two kinds of classifiers; shrunken centroids and support vector machines. 10-fold cv was used for shrunken centroids while leave-one-out-cv was used for the svm. the nested cv procedure reduces the bias considerably and gives an estimate of the error that is very close to that obtained on the independent testing set for both shrunken centroids and svm classifiers for "null" and "non-null" data distributions. independent test data was created to estimate the true error. performance of the optimized classifiers on the independent test set was no better than chance.
 cross-validation is an effective method for estimating the prediction error of a classifier. some recent articles have proposed methods for optimizing classifiers by choosing classifier parameter values that minimize the cv error estimate. we have evaluated the validity of using the cv error estimate of the optimized classifier as an estimate of the true error expected on independent data.  we used cv to optimize the classification parameters for two kinds of classifiers; shrunken centroids and support vector machines. random training datasets were created, with no difference in the distribution of the features between the two classes. using these "null" datasets, we selected classifier parameter values that minimized the cv error estimate. 10-fold cv was used for shrunken centroids while leave-one-out-cv was used for the svm. independent test data was created to estimate the true error. with "null" and "non null" data, we also tested a nested cv procedure, where an inner cv loop is used to perform the tuning of the parameters while an outer cv is used to compute an estimate of the error. the cv error estimate for the classifier with the optimal parameters was found to be a substantially biased estimate of the true error that the classifier would incur on independent data. even though there is no real difference between the two classes for the "null" datasets, the cv error estimate for the shrunken centroid with the optimal parameters was less than 30% on % of simulated training data-sets. for svm with optimal parameters the estimated error rate was less than 30% on 38% of "null" data-sets. performance of the optimized classifiers on the independent test set was no better than chance. the nested cv procedure reduces the bias considerably and gives an estimate of the error that is very close to that obtained on the independent testing set for both shrunken centroids and svm classifiers for "null" and "non-null" data distributions.  we show that using cv to compute an error estimate for a classifier that has itself been tuned using cv gives a significantly biased estimate of the true error. proper use of cv for estimating true error of a classifier developed using a well defined algorithm requires that all steps of the algorithm, including classifier parameter tuning, be repeated in each cv loop. a nested cv procedure provides an almost unbiased estimate of the true error. 