misclassified instances for the currently trained classifier Ck**. The probabilities for the next**
trial are generated by multiplying the probabilities of Ck**'s incorrectly classified instances**
by the factor βk = (1 − ǫk)/ǫk **and then renormalizing all probabilities so that their sum**
equals 1. Ada-Boosting combines the classifiers C1, . . . , Ck **using weighted voting where**
Ck has weight log(βk**). These weights allow Ada-Boosting to discount the predictions of**
classifiers that are not very accurate on the overall problem. Friedman et al (1998) have also suggested an alternative mechanism that fits together the predictions of the classifiers as an additive model using a maximum likelihood criterion.

In this work, we use the revision described by Breiman (1996b) where we reset all the weights to be equal and restart if either ǫk is not less than 0.5 or ǫk **becomes 0.**1 By resetting the weights we do not disadvantage the Ada-Boosting learner in those cases where it reaches these values of ǫk**; the Ada-Boosting learner always incorporates the same**
number of classifiers as other methods we tested. To make this **feasible, we are forced to use** the approach of selecting a data set probabilistically rather than weighting the examples, otherwise a deterministic method such as C4.5 would cycle and generate duplicate members of the ensemble. That is, resetting the weights to 1/N **would cause the learner to repeat**
the decision tree learned as the first member of the ensemble, **and this would lead to**
reweighting the data set the same as for the second member of the ensemble, and so on. Randomly selecting examples for the data set based on the example probabilities alleviates this problem.

Arcing-x4 (Breiman, 1996b) (which we will refer to simply as **Arcing) started out as a**
simple mechanism for evaluating the effect of Boosting methods where the resulting classifiers were combined without weighting the votes. Arcing uses a simple mechanism for determining the probabilities of including examples in the training set. For the i**th example**
in the training set, the value mi refers to the number of times that example was misclassified by the previous K classifiers. The probability pifor selecting example i **to be part of**
classifier K **+ 1's training set is defined as**

$$p_{i}\ =\ {\frac{1+m_{i}{}^{4}}{\sum_{j=1}^{N}(1+m_{j}{}^{4})}}$$

$$(1)$$

Breiman chose the value of the power (4) empirically after trying several different values
(Breiman, 1996b). Although this mechanism does not have the weighted voting of AdaBoosting it still produces accurate ensembles and is simple **to implement; thus we include**
this method (along with Ada-Boosting) in our empirical evaluation.

Figure 2 shows a hypothetical run of Boosting. Note that the first training set would be the same as Bagging; however, later training sets accentuate examples that were misclassified by the earlier member of the ensembles. In this figure, example 1 is a "hard" example that previous classifiers tend to misclassify. With **the second training set, example**
1 occurs multiple times, as do examples 4 and 5 since they were **left out of the first training**
set and, in this case, misclassified by the first learner. For the final training set, example 1