# Are K-Fold Cross Validation , Bootstrap ,Out of Bag fundamentally same?

Can Anyone tell me how K-Fold Cross Validation ,Bootstrap and Out of Bag Approach differ as they use

1)Separate data into training data and testing data

2)Make model using training data and prediction using testing data

3)Use Random Sampling with repeatition approach

4)Repeat the above procedure N times

5)Average all predicted value to get a single value for each prediction of a response variable y

Altough these 3 approaches consists in dividing a dataset into several subsets, they are still different in the main purpose of this division.

K-Fold Cross Validation (CV)

It consists in dividing the original set of observations into k subset of more or less same size. Then, you will use one of the subset as test set and the remaining subsets will be used to form your training set. You will repeat this kth times, where each time the subset used as test set will change. As an example, if you use 3-fold CV, your original set will be divided into k1, k2, k3. First, k1 will form the test set, k2 and k3 will form the training set. Then, k2 will form the test set, k1 and k3 will form the training set. Finally, k3 will form the test set, k1 and k3 will form the training set. For each fold, you output the results and you aggregate these to obtain the final result.

Bootstrap

A bootstrap is a random subset of your original data, sometimes drawn with replacement (check http://www.stat.washington.edu/courses/stat527/s13/readings/EfronTibshirani_JASA_1997.pdf on the .632 rule), sometimes not. But the idea is that a bootstrap contains only a part of your whole set of observations. It is different from CV as it does not contain a testing set. Bootstrap is used to train a different classifier each time on a different set of observations. To output your results, a combination method is used, like averaging for example.

Out-of-bag

As said above, not all observations are used to form bootstrap. The part not used forms the out-of-bag classifier, and can be used to assess the error rate of your classifier. Out-of-bag are typically used to compute the error-rate, and not to train your classifier.

• i think the fold formation in CV are random ? What you say ? Apr 12 '16 at 9:07
• Yes indeed, you are right. I changed it in my answer. Did I answered your question? Is there something you still don't understand ? Apr 12 '16 at 9:53
• just one confusion. please correct me if i am wrong In CV we split each step into training and testing data and then average the result In Bootstrap we just increase our data size by randomly adding obs from our training data (kind of simulation) and calculate whatever we want to calculate. (can we use this data for prediction ?) Apr 12 '16 at 10:21
• In Bootstrap we just increase our data size by randomly adding obs from our training data (kind of simulation) and calculate whatever we want to calculate. (can we use this data for prediction ?) Out-of-bag is similar to bootstrap but the data that we are not using in Bootstrap is now being used in Out-of-bag as testing data so each step contain training data and testing data which leads to prediction of each obs certain times and we average it in the end and use these set of averaged observation as our prediction model and test it on our test data . Right ? Apr 12 '16 at 10:22
• You are right for CV. For out-of-bag (oob), it is actually the data that is not used in bootstrap. For example if you have 10 observations in your original set, you will form a bootstrap of size 10 containing observation 1,2,4,5,6,7,10, where observation 2, 4 and 6 are repeated so your bootstrap look like this : 1,2,2,4,4,5,6,6,7,10. The remaining info, 3, 8, 9 forms the out of bag data. You will train you classifier on you bootstrap and then test it on your out of bag data. The same process applies for each bootstrap. The final result is the averaged result over each bootstrap. Apr 12 '16 at 10:32

First of all, you're right about the similarities: they are all types of resampling-based error estimates. Now about the differences.

cross validation vs. out-of-bootstrap: cross validation (as well as random splitting procedures known as set validation or hold-out validation) use resampling without replacement whereas bootstrap procedures resample with replacement. In cross validation, the resampling without replacement is done in a way that ensures each sample is tested exactly once per "run" of the cross validation.
(There are also non-random splitting procedures for cross validation such as venetian blinds or contiguous blocks which are used in special situations.)
Which of these procedures is best for your model validation depends e.g. on your sample situation and on the model you're validating (bootstrap is of no use with a modeling algorithm that deletes duplicates).

Out-of-bag estimates are very different from the "normal" out-of-bootstrap or cross validation estimates, because they do not estimate the generalization error of single models (typically the one model built on the whole data set) but the generalization error of an aggregated (ensemble) model (bag = bootstrap aggregation). So this difference is like the difference between a single decision tree and a random forest.
Again, you can also use resampling without replacement (e.g. cross validation) to generate the model ensemble for the aggregation - the principle works exactly the same. (Ask me if you need a literature example)

@benmaq already pointed out, bootstrapping is often used for other purposes than validation, particularly to estimate variability due to the random process of sampling that lead to the sample at hand.
An analogous procedure with resampling without replacement or more precisely, using the surrogate models of leave-one-out cross validation is known as jackknifing.