What is the difference between bootstrapping and cross-validation?

Question

I used to apply K-fold cross-validation for robust evaluation of my machine learning models. But I'm aware of the existence of the bootstrapping method for this purpose as well. However, I cannot see the main difference between them in terms of performance estimation.

As far as I see, bootstrapping is also producing a certain number of random training+testing subsets (albeit in a different way) so what is the point, advantage for using this method over CV? The only thing I could figure out that in case of bootstrapping one could artificially produce virtually arbitrary number of such subsets while for CV the number of instances is a kind of limit for this. But this aspect seems to be a very little nuisance.

Answer 1

Both cross validation and bootstrapping are resampling methods.

• bootstrap resamples with replacement (and usually produces new "surrogate" data sets with the same number of cases as the original data set). Due to the drawing with replacement, a bootstrapped data set may contain multiple instances of the same original cases, and may completely omit other original cases.

• cross validation resamples without replacement and thus produces surrogate data sets that are smaller than the original. These data sets are produced in a systematic way so that after a pre-specified number $k$ of surrogate data sets, each of the $n$ original cases has been left out exactly once. This is called k-fold cross validation or leave-x-out cross validation with $x = \frac{n}{k}$, e.g. leave-one-out cross validation omits 1 case for each surrogate set, i.e. $k = n$.

• As the name cross validation suggests, its primary purpose is measuring (generalization) performance of a model. On contrast, bootstrapping is primarily used to establish empirical distribution functions for a widespread range of statistics (widespread as in ranging from, say, the variation of the mean to the variation of models in bagged ensemble models).

• The leave-one-out analogue of the bootstrap procedure is called jackknifing (and is actually older than bootstrapping).

• The bootstrap analogue to cross validation estimates of generalization error is called out-of-bootstrap estimate (because the test cases are those that were left out of the bootstrap resampled training set).

---

[cross validation vs. out-of-bootstrap validation] However, I cannot see the main difference between them in terms of performance estimation.

That intuition is correct: in practice there's often not much of a difference between iterated $k$-fold cross validation and out-of-bootstrap. With a similar total number of evaluated surrogate models, total error [of the model prediction error measurement] has been found to be similar, although oob typically has more bias and less variance than the corresponding CV estimates.

There are a number of attempts to reduce oob bias (.632-bootstrap, .632+-bootstrap) but whether they will actually improve the situation depends on the situation at hand.

Literature:

• Kohavi, R.: A Study of Cross-Validation and Bootstrap for Accuracy Estimation and Model Selection, Mellish, C. S. (ed.) Artificial Intelligence Proceedings 14$^th$ International Joint Conference, 20 -- 25. August 1995, Montréal, Québec, Canada, Morgan Kaufmann, USA, , 1137 - 1145 (1995).
• Kim, J.-H. Estimating classification error rate: Repeated cross-validation, repeated hold-out and bootstrap , Computational Statistics & Data Analysis , 53, 3735 - 3745 (2009). DOI: 10.1016/j.csda.2009.04.009
• Beleites, C.; Baumgartner, R.; Bowman, C.; Somorjai, R.; Steiner, G.; Salzer, R. & Sowa, M. G. Variance reduction in estimating classification error using sparse datasets, Chemom Intell Lab Syst, 79, 91 - 100 (2005).

---

The only thing I could figure out that in case of bootstrapping one could artificially produce virtually arbitrary number of such subsets while for CV the number of instances is a kind of limit for this.

Yes, there are fewer combinations possible for CV than for bootstrapping. But the limit for CV is probably higher than you are aware of. For a data set with $n$ cases and $k$-fold cross validation, you have

• CV $\binom{n}{k}$ combinations without replacement (for k < n that are far more than the $k$ possibilities that are usually evaluated) vs.
• bootstrap/oob $\binom{2 n - 1}{n}$ combinations with replacement (which are again far more than the, say, 100 or 1000 surrogate models that are typically evaluated)

Answer 2

Bootstrapping is any test or metric that relies on random sampling with replacement.It is a method that helps in many situations like validation of a predictive model performance, ensemble methods, estimation of bias and variance of the parameter of a model etc. It works by performing sampling with replacement from the original dataset, and at the same time assuming that the data points that have not been choses are the test dataset. We can repeat this procedure several times and compute the average score as estimation of our model performance. Also, Bootstrapping is related to the ensemble training methods, because we can build a model using each bootstrap datasets and “bag” these models in an ensemble using the majority voting (for classification) or computing the average (for numerical predictions) for all of these models as our final result.

Cross validation is a procedure for validating a model's performance, and it is done by splitting the training data into k parts. We assume that the k-1 parts is the training set and use the other part is our test set. We can repeat that k times differently holding out a different part of the data every time. Finally, we take the average of the k scores as our performance estimation. Cross validation can suffer from bias or variance. Increasing the number of splits, the variance will increase too and the bias will decrease. On the other hand, if we decrease the number of splits, the bias will increase and the variance will decrease.

In summary, Cross validation splits the available dataset to create multiple datasets, and Bootstrapping method uses the original dataset to create multiple datasets after resampling with replacement. Bootstrapping it is not as strong as Cross validation when it is used for model validation. Bootstrapping is more about building ensemble models or just estimating parameters.

Answer 3

• Cross-Validation: provide estimates of the test error.
• Bootstrap: provides the standard error of the estimates.