next up previous
Next: 2.2 Boosting Classifiers Up: 2. Classifier Ensembles Previous: 2. Classifier Ensembles

   
2.1 Bagging Classifiers

Bagging [Breiman1996a] is a ``bootstrap'' [Efron Tibshirani1993] ensemble method that creates individuals for its ensemble by training each classifier on a random redistribution of the training set. Each classifier's training set is generated by randomly drawing, with replacement, N examples - where N is the size of the original training set; many of the original examples may be repeated in the resulting training set while others may be left out. Each individual classifier in the ensemble is generated with a different random sampling of the training set.

Figure 2 gives a sample of how Bagging might work on a imaginary set of data. Since Bagging resamples the training set with replacement, some instance are represented multiple times while others are left out. So Bagging's training-set-1 might contain examples 3 and 7 twice, but does not contain either example 4 or 5. As a result, the classifier trained on training-set-1 might obtain a higher test-set error than the classifier using all of the data. In fact, all four of Bagging's component classifiers could result in higher test-set error; however, when combined, these four classifiers can (and often do) produce test-set error lower than that of the single classifier (the diversity among these classifiers generally compensates for the increase in error rate of any individual classifier).


  
Figure 2: Hypothetical runs of Bagging and Boosting. Assume there are eight training examples. Assume example 1 is an ``outlier'' and is hard for the component learning algorithm to classify correctly. With Bagging, each training set is an independent sample of the data; thus, some examples are missing and others occur multiple times. The Boosting training sets are also samples of the original data set, but the ``hard'' example (example 1) occurs more in later training sets since Boosting concentrates on correctly predicting it.
\begin{figure}
\par\begin{center}
\par\begin{tabular}{\vert lc\vert} \hline
\mul...
...1, 6, 1, 1, 3, 1, 5 \\ \hline
\end{tabular}\par\end{center}\par\par\end{figure}

Breiman [1996a] showed that Bagging is effective on ``unstable'' learning algorithms where small changes in the training set result in large changes in predictions. Breiman [1996a] claimed that neural networks and decision trees are examples of unstable learning algorithms. We study the effectiveness of Bagging on both these learning methods in this article.


next up previous
Next: 2.2 Boosting Classifiers Up: 2. Classifier Ensembles Previous: 2. Classifier Ensembles
David Opitz
1999-08-24