
| A sample of a single classifier on an imaginary set of data. (Original) Training Set Training-set-1: 1, 2, 3, 4, 5, 6, 7, 8 A sample of Bagging on the same data. (Resampled) Training Set Training-set-1: 2, 7, 8, 3, 7, 6, 3, 1 Training-set-2: 7, 8, 5, 6, 4, 2, 7, 1 Training-set-3: 3, 6, 2, 7, 5, 6, 2, 2 Training-set-4: 4, 5, 1, 4, 6, 4, 3, 8 A sample of Boosting on the same data. (Resampled) Training Set Training-set-1: 2, 7, 8, 3, 7, 6, 3, 1 Training-set-2: 1, 4, 5, 4, 1, 5, 6, 4 Training-set-3: 7, 1, 5, 8, 1, 8, 1, 4 Training-set-4: 1, 1, 6, 1, 1, 3, 1, 5   |
| |

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.
of selecting an example is not equal across the training set. **This probability depends on how** often that example was misclassified by the previous K **classifiers. Ada-Boosting can use**
the approach of (a) selecting a set of examples based on the probabilities of the examples, or
(b) simply using all of the examples and weight the error of each example by the probability for that example (i.e., examples with higher probabilities **have more effect on the error).**
This latter approach has the clear advantage that each example is incorporated (at least in part) in the training set. Furthermore, Friedman et al. (1998) have demonstrated that this form of Ada-Boosting can be viewed as a form of additive modeling for optimizing a logistic loss function. In this work, however, we have chosen to use the approach of subsampling the data to ensure a fair empirical comparison (in part due to the **restarting reason discussed**
below).

Both Arcing and Ada-Boosting initially set the probability **of picking each example to**
be 1/N. These methods then recalculate these probabilities after **each trained classifier is**
added to the ensemble. For Ada-Boosting, let ǫk **be the sum of the probabilities of the**