Appears in the International Joint Conference on Arti�cial Intelligence (IJCAI), 1995A Study of Cross-Validation and Bootstrapfor Accuracy Estimation and Model SelectionRon KohaviComputer Science DepartmentStanford UniversityStanford, CA. [email protected]://robotics.stanford.edu/~ronnykAbstractWe review accuracy estimation methods andcompare the two most commonmethods: cross-validation and bootstrap. Recent experimen-tal results on arti�cial data and theoretical re-sults in restricted settings have shown that forselecting a good classi�er from a set of classi-�ers (model selection), ten-fold cross-validationmay be better than the more expensive leave-one-out cross-validation. We report on a large-scale experiment|over half a million runs ofC4.5 and a Naive-Bayes algorithm|toestimatethe e�ects of di�erent parameters on these al-gorithms on real-world datasets. For cross-validation, we vary the number of folds andwhether the folds are strati�ed or not; for boot-strap, we vary the number of bootstrap sam-ples. Our results indicate that for real-worddatasets similar to ours, the best method to usefor model selection is ten-fold strati�ed crossvalidation, even if computation power allowsusing more folds.1 IntroductionIt can not be emphasized enough that no claimwhatsoever is being made in this paper that allalgorithms are equivalent in practice, in the realworld. In particular, no claim is being made that oneshould not use cross-validation in the real world.|Wolpert (1994a)Estimating the accuracy of a classi�er induced by su-pervised learning algorithms is important not only topredict its future prediction accuracy, but also for choos-ing a classi�er from a given set (model selection), orcombining classi�ers (Wolpert 1992). For estimating the�nal accuracy of a classi�er, we would like an estimationmethod with low bias and low variance. To choose aclassi�er or to combine classi�ers, the absolute accura-cies are less important and we are willingto trade o� biasA longer version of the paper can be retrieved by anony-mous ftp to starry.stanford.edu:pub/ronnyk/accEst-long.ps

for low variance, assuming the bias a�ects all classi�erssimilarly (e.g., estimates are 5% pessimistic).In this paper we explain some of the assumptions madeby the di�erent estimation methods, and present con-crete examples where each method fails. While it isknown that no accuracy estimation can be correct allthe time (Wolpert 1994b, Scha�er 1994), we are inter-ested in identifying a method that is well suited for thebiases and trends in typical real world datasets.Recent results, both theoretical and experimental,have shown that it is not always the case that increas-ing the computational cost is bene�cial, especially if therelative accuracies are more important than the exactvalues. For example, leave-one-out is almost unbiased,but it has high variance, leading to unreliable estimates(Efron 1983). For linear models, using leave-one-outcross-validation for model selection is asymptotically in-consistent in the sense that the probability of selectingthe model with the best predictive power does not con-verge to one as the total number of observations ap-proaches in�nity (Zhang 1992, Shao 1993).This paper is organized as follows. Section 2 describesthe common accuracy estimation methods and ways ofcomputing con�dence bounds that hold under some as-sumptions. Section 3 discusses related work comparingcross-validation variants and bootstrap variants. Sec-tion 4 discusses methodology underlying our experiment.The results of the experiments are given Section 5 with adiscussion of important observations. We conclude witha summary in Section 6.2 Methods for Accuracy EstimationA classi�er is a function that maps an unlabelled in-stance to a label using internal data structures. An in-ducer, or an induction algorithm, builds a classi�er froma given dataset. CART and C4.5 (Breiman, Friedman,Olshen & Stone 1984, Quinlan 1993) are decision tree in-ducers that build decision tree classi�ers. In this paper,we are not interested in the speci�c method for inducingclassi�ers, but assume access to a dataset and an inducerof interest.Let V be the space of unlabelled instances and Y the

set of possible labels. Let X = V � Y be the space oflabelled instances and D = fx1; x2; : : :; xng be a dataset(possibly a multiset) consisting of n labelled instances,where xi = hvi 2 V; yi 2 Yi. A classi�er C maps an unla-belled instance v 2 V to a label y 2 Y and an inducer Imaps a given dataset D into a classi�er C. The notationI(D; v) will denote the label assigned to an unlabelled in-stance v by the classi�er built by inducer I on dataset D,i.e., I(D; v) = (I(D))(v). We assume that there exists adistribution on the set of labelled instances and that ourdataset consists of i.i.d. (independently and identicallydistributed) instances. We consider equal misclassi�ca-tion costs using a 0/1 loss function, but the accuracyestimation methods can easily be extended to other lossfunctions.The accuracy of a classi�er C is the probability ofcorrectly classifying a randomly selected instance, i.e.,acc = Pr(C(v) = y) for a randomly selected instancehv; yi 2 X, where the probability distribution over theinstance space is the same as the distribution that wasused to select instances for the inducer's training set.Given a �nite dataset, we would like to estimate the fu-ture performance of a classi�er induced by the given in-ducer and dataset. A single accuracy estimate is usuallymeaningless without a con�dence interval; thus we willconsider how to approximate such an interval when pos-sible. In order to identify weaknesses, we also attemptto identify cases where the estimates fail.2.1 HoldoutThe holdout method, sometimes called test sample esti-mation, partitions the data into two mutually exclusivesubsets called a training set and a test set, or holdout set.It is common to designate 2/3 of the data as the trainingset and the remaining 1/3 as the test set. The trainingset is given to the inducer, and the induced classi�er istested on the test set. Formally, let Dh, the holdout set,be a subset of D of size h, and let Dt be D n Dh. Theholdout estimated accuracy is de�ned asacch = 1h Xhvi;yii2Dh �(I(Dt; vi); yi) ; (1)where �(i; j) = 1 if i = j and 0 otherwise. Assumingthat the inducer's accuracy increases as more instancesare seen, the holdout method is a pessimistic estimatorbecause only a portion of the data is given to the inducerfor training. The more instances we leave for the test set,the higher the bias of our estimate; however, fewer testset instances means that the con�dence interval for theaccuracy will be wider as shown below.Each test instance can be viewed as a Bernoulli trial:correct or incorrect prediction. Let S be the numberof correct classi�cations on the test set, then S is dis-tributed binomially (sum of Bernoulli trials). For rea-sonably large holdout sets, the distribution of S=h is ap-proximately normal with mean acc (the true accuracy of

the classi�er) and a variance of acc�(1�acc)=h. Thus,by De Moivre-Laplace limit theorem, we havePr(�z < acch � accpacc(1 � acc)=h < z) � (2)where z is the (1+ )=2-th quantile point of the standardnormal distribution. To get a 100 percent con�denceinterval, one determines z and inverts the inequalities.Inversion of the inequalities leads to a quadratic equationin acc, the roots of which are the low and high con�dencepoints:2h � acch + z2 � z �p4h � acch + z2 � 4h � acc2h2(h + z2) : (3)The above equation is not conditioned on the dataset D;if more information is available about the probability ofthe given dataset, it must be taken into account.The holdout estimate is a random number that de-pends on the division into a training set and a test set.In random subsampling, the holdout method is re-peated k times, and the estimated accuracy is derivedby averaging the runs. The standard deviation can beestimated as the standard deviation of the accuracy es-timations from each holdout run.The main assumption that is violated in random sub-sampling is the independence of instances in the test setfrom those in the training set. If the training and testset are formed by a split of an original dataset, thenan over-represented class in one subset will be a under-represented in the other. To demonstrate the issue, wesimulated a 2/3, 1/3 split of Fisher's famous iris datasetand used a majority inducer that builds a classi�er pre-dicting the prevalent class in the training set. The irisdataset describes iris plants using four continuous fea-tures, and the task is to classify each instance (an iris)as Iris Setosa, Iris Versicolour, or Iris Virginica. For eachclass label, there are exactly one third of the instanceswith that label (50 instances of each class from a to-tal of 150 instances); thus we expect 33.3% predictionaccuracy. However, because the test set will always con-tain less than 1/3 of the instances of the class that wasprevalent in the training set, the accuracy predicted bythe holdout method is 27.68% with a standard deviationof 0.13% (estimated by averaging 500 holdouts).In practice, the dataset size is always �nite, and usu-ally smaller than we would like it to be. The holdoutmethod makes ine�cient use of the data: a third ofdataset is not used for training the inducer.2.2 Cross-Validation, Leave-one-out, andStrati�cationIn k-fold cross-validation, sometimes called rotation esti-mation, the dataset D is randomly split into k mutuallyexclusive subsets (the folds) D1;D2; : : :;Dk of approx-imately equal size. The inducer is trained and tested

k times; each time t 2 f1; 2; : : :; kg, it is trained onD n Dt and tested on Dt. The cross-validation estimateof accuracy is the overall number of correct classi�ca-tions, divided by the number of instances in the dataset.Formally, let D(i) be the test set that includes instancexi = hvi; yii, then the cross-validation estimate of accu-racy acccv = 1n Xhvi;yii2D �(I(D n D(i); vi); yi) : (4)The cross-validation estimate is a random numberthat depends on the division into folds. Completecross-validation is the average of all � mm=k� possibil-ities for choosing m=k instances out of m, but it isusually too expensive. Except for leave-one-one (n-foldcross-validation), which is always complete, k-fold cross-validation is estimating complete k-fold cross-validationusing a single split of the data into the folds. Repeat-ing cross-validation multiple times using di�erent splitsinto folds provides a better Monte-Carlo estimate to thecomplete cross-validation at an added cost. In strati-�ed cross-validation, the folds are strati�ed so thatthey contain approximately the same proportions of la-bels as the original dataset.An inducer is stable for a given dataset and a set ofperturbations, if it induces classi�ers that make the samepredictions when it is given the perturbed datasets.Proposition 1 (Variance in k-fold CV)Given a dataset and an inducer. If the inducer isstable under the perturbations caused by deleting theinstances for the folds in k-fold cross-validation, thecross-validation estimate will be unbiased and the vari-ance of the estimated accuracy will be approximatelyacccv �(1�acccv)=n, where n is the number of instancesin the dataset.Proof: If we assume that the k classi�ers produced makethe same predictions, then the estimated accuracy hasa binomial distribution with n trials and probability ofsuccess equal to the accuracy of the classi�er.For large enough n, a con�dence interval may be com-puted using Equation 3 with h equal to n, the numberof instances.In reality, a complex inducer is unlikely to be stablefor large perturbations, unless it has reached its maximallearning capacity. We expect the perturbations inducedby leave-one-out to be small and therefore the classi�ershould be very stable. As we increase the size of theperturbations, stability is less likely to hold: we expectstability to hold more in 20-fold cross-validation than in10-fold cross-validation and both should be more stablethan holdout of 1/3. The proposition does not applyto the resubstitution estimate because it requires the in-ducer to be stable when no instances are given in thedataset.

The above proposition helps understand one possibleassumption that is made when using cross-validation: ifan inducer is unstable for a particular dataset under a setof perturbations introduced by cross-validation, the ac-curacy estimate is likely to be unreliable. If the induceris almost stable on a given dataset, we should expecta reliable estimate. The next corollary takes the ideaslightly further and shows a result that we have observedempirically: there is almost no change in the variance ofthe cross-validation estimate when the number of foldsis varied.Corollary 2 (Variance in cross-validation)Given a dataset and an inducer. If the inducer is sta-ble under the perturbations caused by deleting the testinstances for the folds in k-fold cross-validation for var-ious values of k, then the variance of the estimates willbe the same.Proof: The variance of k-fold cross-validation in Propo-sition 1 does not depend on k.While some inducers are likely to be inherently morestable, the following example shows that one must alsotake into account the dataset and the actual perturba-tions.Example 1 (Failure of leave-one-out)Fisher's iris dataset contains 50 instances of each class,leading one to expect that a majority inducer shouldhave accuracy about 33%. However, the combination ofthis dataset with a majority inducer is unstable for thesmall perturbations performed by leave-one-out. Whenan instance is deleted from the dataset, its label is a mi-nority in the training set; thus the majority inducer pre-dicts one of the other two classes and always errs in clas-sifying the test instance. The leave-one-out estimatedaccuracy for a majority inducer on the iris dataset istherefore 0%. Moreover, all folds have this estimated ac-curacy; thus the standard deviation of the folds is again0%, giving the unjusti�ed assurance that the estimate isstable.The example shows an inherent problem with cross-validation that applies to more than just a majority in-ducer. In a no-information dataset, where the label val-ues are completely random, the best an induction algo-rithm can do is predict majority. Leave-one-out on sucha dataset with 50% of the labels for each class and amajority inducer (the best possible inducer) would stillpredict 0% accuracy.2.3 BootstrapThe bootstrap family was introduced by Efron and isfully described in Efron & Tibshirani (1993). Given adataset of size n, a bootstrap sample is created bysampling n instances uniformly from the data (with re-placement). Since the dataset is sampled with replace-ment, the probability of any given instance not beingchosen after n samples is (1 � 1=n)n � e�1 � 0:368; the

expected number of distinct instances from the originaldataset appearing in the test set is thus 0:632n. The �0accuracy estimate is derived by using the bootstrap sam-ple for training and the rest of the instances for testing.Given a number b, the number of bootstrap samples, let�0i be the accuracy estimate for bootstrap sample i. The.632 bootstrap estimate is de�ned asaccboot = 1b bXi=1(0:632 � �0i + :368 � accs) (5)where accs is the resubstitution accuracy estimate onthe full dataset (i.e., the accuracy on the training set).The variance of the estimate can be determined by com-puting the variance of the estimates for the samples.The assumptions made by bootstrap are basically thesame as that of cross-validation, i.e., stability of the al-gorithm on the dataset: the \bootstrap world" shouldclosely approximate the real world. The .632 bootstrapfails to give the expected result when the classi�er is aperfect memorizer (e.g., an unpruned decision tree or aone nearest neighbor classi�er) and the dataset is com-pletely random, say with two classes. The resubstitutionaccuracy is 100%, and the �0 accuracy is about 50%.Plugging these into the bootstrap formula, one gets anestimated accuracy of about 68.4%, far from the real ac-curacy of 50%. Bootstrap can be shown to fail if we adda memorizer module to any given inducer and adjust itspredictions. If the memorizer remembers the training setand makes the predictions when the test instance was atraining instances, adjusting its predictions can make theresubstitution accuracy change from 0% to 100% and canthus bias the overall estimated accuracy in any directionwe want.3 Related WorkSome experimental studies comparing di�erent accuracyestimation methods have been previously done, but mostof them were on arti�cial or small datasets. We nowdescribe some of these e�orts.Efron (1983) conducted �ve sampling experiments andcompared leave-one-out cross-validation, several variantsof bootstrap, and several other methods. The purposeof the experiments was to \investigate some related es-timators, which seem to o�er considerably improved es-timation in small samples." The results indicate thatleave-one-out cross-validation gives nearly unbiased esti-mates of the accuracy, but often with unacceptably highvariability, particularly for small samples; and that the.632 bootstrap performed best.Breiman et al. (1984) conducted experiments usingcross-validation for decision tree pruning. They choseten-fold cross-validation for the CART program andclaimed it was satisfactory for choosing the correct tree.They claimed that \the di�erence in the cross-validationestimates of the risks of two rules tends to be much moreaccurate than the two estimates themselves."

Jain, Dubes & Chen (1987) compared the performanceof the �0 bootstrap and leave-one-out cross-validationon nearest neighbor classi�ers using arti�cial data andclaimed that the con�dence interval of the bootstrapestimator is smaller than that of leave-one-out. Weiss(1991) followed similar lines and compared strati�edcross-validation and two bootstrap methods with near-est neighbor classi�ers. His results were that strati�edtwo-fold cross validation is relatively low variance andsuperior to leave-one-out.Breiman & Spector (1992) conducted a feature sub-set selection experiments for regression, and comparedleave-one-out cross-validation, k-fold cross-validationfor various k, strati�ed k-fold cross-validation, bias-corrected bootstrap, and partial cross-validation (notdiscussed here). Tests were done on arti�cial datasetswith 60 and 160 instances. The behavior observedwas: (1) the leave-one-out has low bias and RMS (rootmean square) error, whereas two-fold and �ve-fold cross-validationhave larger bias and RMS error only at modelswith many features; (2) the pessimistic bias of ten-foldcross-validation at small samples was signi�cantly re-duced for the samples of size 160; (3) for model selection,ten-fold cross-validation is better than leave-one-out.Bailey & Elkan (1993) compared leave-one-out cross-validation to .632 bootstrap using the FOIL inducerand four synthetic datasets involving Boolean concepts.They observed high variability and little bias in theleave-one-out estimates, and low variability but largebias in the .632 estimates.Weiss and Indurkyha (Weiss & Indurkhya 1994) con-ducted experiments on real-world data to determine theapplicability of cross-validation to decision tree pruning.Their results were that for samples at least of size 200,using strati�ed ten-fold cross-validation to choose theamount of pruning yields unbiased trees (with respect totheir optimal size).4 MethodologyIn order to conduct a large-scale experiment we decidedto use C4.5 and a Naive-Bayesian classi�er. The C4.5algorithm (Quinlan 1993) is a descendent of ID3 thatbuilds decision trees top-down. The Naive-Bayesian clas-si�er (Langley, Iba & Thompson 1992) used was the oneimplemented in MLC++ (Kohavi, John, Long, Manley& P eger 1994) that uses the observed ratios for nominalfeatures and assumes a Gaussian distribution for contin-uous features. The exact details are not crucial for thispaper because we are interested in the behavior of theaccuracy estimation methods more than the internalsof the induction algorithms. The underlying hypothe-sis spaces|decision trees for C4.5 and summary statis-tics for Naive-Bayes|are di�erent enough that we hopeconclusions based on these two induction algorithms willapply to other induction algorithms.Because the target concept is unknown for real-world

concepts, we used the holdout method to estimate thequality of the cross-validation and bootstrap estimates.To choose a set of datasets, we looked at the learningcurves for C4.5 and Naive-Bayes for most of the super-vised classi�cation datasets at the UC Irvine repository(Murphy & Aha 1995) that contained more than 500instances (about 25 such datasets). We felt that a min-imum of 500 instances were required for testing. Whilethe true accuracies of a real dataset cannot be computedbecause we do not know the target concept, we can esti-mate the true accuracies using the holdout method. The\true" accuracy estimates in Table 1 were computed bytaking a random sample of the given size, computing theaccuracy using the rest of the dataset as a test set, andrepeating 500 times.We chose six datasets from a wide variety of domains,such that the learning curve for both algorithms didnot atten out too early, that is, before one hundredinstances. We also added a no information dataset,rand, with 20 Boolean features and a Boolean randomlabel. On one dataset, vehicle, the generalization accu-racy of the Naive-Bayes algorithm deteriorated by morethan 4% as more instances were given. A similar phe-nomenon was observed on the shuttle dataset. Sucha phenomenon was predicted by Scha�er and Wolpert(Scha�er 1994, Wolpert 1994b), but we were surprisedthat it was observed on two real-world datasets.To see how well an accuracy estimation method per-forms, we sampled instances from the dataset (uniformlywithout replacement), and created a training set of thedesired size. We then ran the induction algorithm onthe training set and tested the classi�er on the rest ofthe instances in the dataset. This was repeated 50 timesat points where the learning curve was sloping up. Thesame folds in cross-validation and the same samples inbootstrap were used for both algorithms compared.5 Results and DiscussionWe now show the experimental results and discuss theirsigni�cance. We begin with a discussion of the bias inthe estimation methods and follow with a discussion ofthe variance. Due to lack of space, we omit some graphsfor the Naive-Bayes algorithm when the behavior is ap-proximately the same as that of C4.5.5.1 The BiasThe bias of a method to estimate a parameter � is de-�ned as the expected value minus the estimated value.An unbiased estimation method is a method that haszero bias. Figure 1 shows the bias and variance of k-foldcross-validation on several datasets (the breast cancerdataset is not shown).The diagrams clearly show that k-fold cross-validationis pessimistically biased, especially for two and �ve folds.For the learning curves that have a large derivative atthe measurement point, the pessimism in k-fold cross-

2 5 10 20 -5 -2 -1 folds45

75 % acc

Soybean

Vehicle

Rand

2 5 10 20 -5 -2 -1 folds96

96.5

97.5

98.5

99.5

100 % acc

Chess Hypo

Mushroom

Figure 1: C4.5: The bias of cross-validation with varyingfolds. A negative k folds stands for leave-k-out. Errorbars are 95% con�dence intervals for the mean. The grayregions indicate 95% con�dence intervals for the true ac-curacies. Note the di�erent ranges for the accuracy axis.validation for small k's is apparent. Most of the esti-mates are reasonably good at 10 folds and at 20 foldsthey are almost unbiased.Strati�ed cross-validation (not shown) had similar be-havior, except for lower pessimism. The estimated accu-racy for soybean at 2-fold was 7% higher and at �ve-fold,4.7% higher; for vehicle at 2-fold, the accuracy was 2.8%higher and at �ve-fold, 1.9% higher. Thus strati�cationseems to be a less biased estimation method.Figure 2 shows the bias and variance for the .632 boot-strap accuracy estimation method. Although the .632bootstrap is almost unbiased for chess, hypothyroid, andmushroom for both inducers, it is highly biased for soy-bean with C4.5, vehicle with both inducers, and randwith both inducers. The bias with C4.5 and vehicle is9.8%.5.2 The VarianceWhile a given method may have low bias, its perfor-mance (accuracy estimation in our case) may be poordue to high variance. In the experiments above, we haveformed con�dence intervals by using the standard de-viation of the mean accuracy. We now switch to thestandard deviation of the population, i.e., the expectedstandard deviation of a single accuracy estimation run.In practice, if one does a single cross-validation run, theexpected accuracy will be the mean reported above, butthe standard deviation will be higher by a factor of p50,the number of runs we averaged in the experiments.

Dataset no. of sample-size no. of duplicate C4.5 Naive-Bayesattr. / total size categories instancesBreast cancer 10 50/699 2 8 91.37�0.10 94.22�0.10Chess 36 900/3196 2 0 98.19�0.03 86.80�0.07Hypothyroid 25 400/3163 2 77 98.52�0.03 97.63�0.02Mushroom 22 800/8124 2 0 99.36�0.02 94.54�0.03Soybean large 35 100/683 19 52 70.49�0.22 79.76�0.14Vehicle 18 100/846 4 0 60.11�0.16 46.80�0.16Rand 20 100/3000 2 9 49.96�0.04 49.90�0.04Table 1: True accuracy estimates for the datasets using C4.5 and Naive-Bayes classi�ers at the chosen sample sizes. 1 2 5 10 20 50 100

samples45

% acc

Soybean Vehicle

Rand

Estimated

Soybean

Vehicle

Rand

1 2 5 10 20 50 100 samples96

96.5

97.5

98.5

99.5

100 % acc

Chess Hypo

Mushroom

Figure 2: C4.5: The bias of bootstrap with varying sam-ples. Estimates are good for mushroom, hypothyroid,and chess, but are extremely biased (optimistically) forvehicle and rand, and somewhat biased for soybean.In what follows, all �gures for standard deviation willbe drawn with the same range for the standard devi-ation: 0 to 7.5%. Figure 3 shows the standard devia-tions for C4.5 and Naive Bayes using varying numberof folds for cross-validation. The results for strati�edcross-validation were similarwith slightly lower variance.Figure 4 shows the same information for .632 bootstrap.Cross-validation has high variance at 2-folds on bothC4.5 and Naive-Bayes. On C4.5, there is high varianceat the high-ends too|at leave-one-out and leave-two-out|for three �les out of the seven datasets. Strati�ca-tion reduces the variance slightly, and thus seems to beuniformly better than cross-validation, both for bias andvariance.

2 5 10 20 -5 -2 -1 folds

C4.5

std dev

Mushroom Chess Hypo

Breast

Vehicle Soybean

Rand

2 5 10 20 -5 -2 -1 folds

Naive-Bayes

std dev

Mushroom

Chess Hypo

Breast

Vehicle

Soybean Rand

Figure 3: Cross-validation: standard deviation of accu-racy (population). Di�erent line styles are used to helpdi�erentiate between curves.6 SummaryWe reviewed common accuracy estimation methods in-cluding holdout, cross-validation, and bootstrap, andshowed examples where each one fails to produce a goodestimate. We have compared the latter two approacheson a variety of real-world datasets with di�ering charac-teristics.Proposition 1 shows that if the induction algorithmis stable for a given dataset, the variance of the cross-validation estimates should be approximately the same,independent of the number of folds. Although the induc-tion algorithms are not stable, they are approximatelystable. k-fold cross-validation with moderate k values(10-20) reduces the variance while increasing the bias.As k decreases (2-5) and the sample sizes get smaller,there is variance due to the instability of the training

1 2 5 10 20 50 100 samples

C4.5

std dev

Mushroom Chess

Hypo

Breast

Vehicle

Soybean

Rand

Figure 4: .632 Bootstrap: standard deviation in accu-racy (population).sets themselves, leading to an increase in variance. Thisis most apparent for datasets with many categories, suchas soybean. In these situations, strati�cation seems tohelp, but repeated runs may be a better approach.Our results indicate that strati�cation is generally abetter scheme, both in terms of bias and variance, whencompared to regular cross-validation. Bootstrap has lowvariance, but extremely large bias on some problems. Werecommend using strati�ed ten-fold cross-validation formodel selection.Acknowledgments We thank David Wolpert for athorough reading of this paper and many interesting dis-cussions. We thank Wray Buntine, Tom Bylander, BradEfron, Jerry Friedman, Rob Holte, George John, PatLangley, Rob Tibshirani, and Sholom Weiss for theirhelpful comments and suggestions. Dan Sommer�eldimplemented the bootstrap method in MLC++. All ex-periments were conducted using MLC++, partly partlyfunded by ONR grant N00014-94-1-0448and NSF grantsIRI-9116399 and IRI-9411306.ReferencesBailey, T. L. & Elkan, C. (1993), Estimating the ac-curacy of learned concepts, in \Proceedings of In-ternational Joint Conference on Arti�cial Intelli-gence", Morgan Kaufmann Publishers, pp. 895{900.Breiman, L. & Spector, P. (1992), \Submodel selectionand evaluation in regression. the x-random case",International Statistical Review 60(3), 291{319.Breiman, L., Friedman, J. H., Olshen, R. A. & Stone,C. J. (1984), Classi�cation and Regression Trees,Wadsworth International Group.Efron, B. (1983), \Estimating the error rate of a pre-diction rule: improvement on cross-validation",Journal of the American Statistical Association78(382), 316{330.Efron, B. & Tibshirani, R. (1993), An introduction tothe bootstrap, Chapman & Hall.

Jain, A. K., Dubes, R. C. & Chen, C. (1987), \Boot-strap techniques for error estimation", IEEE trans-actions on pattern analysis and machine intelli-gence PAMI-9(5), 628{633.Kohavi, R., John, G., Long, R., Manley, D. &P eger, K. (1994), MLC++: A machine learn-ing library in C++, in \Tools with Arti�cialIntelligence", IEEE Computer Society Press,pp. 740{743. Available by anonymous ftp from:starry.Stanford.EDU:pub/ronnyk/mlc/toolsmlc.ps.Langley, P., Iba, W. & Thompson, K. (1992), An anal-ysis of bayesian classi�ers, in \Proceedings of thetenth national conference on arti�cial intelligence",AAAI Press and MIT Press, pp. 223{228.Murphy, P. M. & Aha, D. W. (1995), UCIrepository of machine learning databases,http://www.ics.uci.edu/~mlearn/MLRepository.html.Quinlan, J. R. (1993), C4.5: Programs for MachineLearning, Morgan Kaufmann, Los Altos, California.Scha�er, C. (1994), A conservation law for generalizationperformance, in \Machine Learning: Proceedingsof the Eleventh International Conference", MorganKaufmann, pp. 259{265.Shao, J. (1993), \Linear model selection via cross-validation", Journal of the American Statistical As-sociation 88(422), 486{494.Weiss, S. M. (1991), \Small sample error rate estimationfor k-nearest neighbor classi�ers", IEEE Transac-tions on Pattern Analysis and Machine Intelligence13(3), 285{289.Weiss, S. M. & Indurkhya, N. (1994), Decision treepruning : Biased or optimal, in \Proceedings ofthe twelfth national conference on arti�cial intel-ligence", AAAI Press and MIT Press, pp. 626{632.Wolpert, D. H. (1992), \Stacked generalization", NeuralNetworks 5, 241{259.Wolpert, D. H. (1994a), O�-training set error and a pri-ori distinctions between learning algorithms, Tech-nical Report SFI TR 94-12-123, The Sante Fe In-stitute.Wolpert, D. H. (1994b), The relationship between PAC,the statistical physics framework, the Bayesianframework, and the VC framework, Technical re-port, The Santa Fe Institute, Santa Fe, NM.Zhang, P. (1992), \On the distributional properties ofmodel selection criteria", Journal of the AmericanStatistical Association 87(419), 732{737. View publication statsView publication stats

https://www.researchgate.net/publication/2352264