performance metric. The "Pick Best" strategy selects the class distribution that performs best over the 13 evaluated class distributions (see Tables 5 and 6). Given that we only consider the 13 class distributions, this strategy will always yield the best results but, as we shall see, is more costly than the other strategies. The value representing the best, budget-efficient performance 
(lowest error rate, highest AUC) is underlined for each data set. A detailed iteration-by-iteration description of the algorithm, for all seven data sets, is provided in Appendix C, Table C3. 

Table 8 also specifies the cost for each strategy, based on the number of training examples requested by the algorithm. This cost is expressed with respect to the budget n (each strategy yields a final training set with n examples). The "Pick Natural/Balanced" strategy always requires exactly n examples to be selected and therefore has a cost of n and is budget-efficient. The "Pick Best" strategy has a total cost of 1.93n and hence is not budget-efficient (because it evaluates class distributions with between 2% and 95% minority-class examples, it requires .95n minorityclass examples and .98n majority-class examples). The cost of the sampling algorithm depends on the performance of the induced classifiers: with the changes to the algorithm described in this section, it is no longer guaranteed to be budget-efficient. Nonetheless, in all cases—for both error rate and AUC—the sampling algorithm has a cost of exactly n and hence turns out to be budget-efficient. 

Sampling Algorithm Pick Best Pick Natural/Balanced

Data Set ER AUC Cost ER AUC Cost ER AUC Cost

phone 12.3% .851 n 12.6% .849 n 12.3% .853 1.93n

adult 17.1% .861 n 17.3% .851 n 16.9% .861 1.93n

covertype 5.0% .984 n 5.0% .980 n 5.0% .984 1.93n

kr-vs-kp 1.2% .998 n 1.4% .998 n 1.2% .998 1.93n

weather 33.1% .740 n 33.7% .736 n 33.1% .740 1.93n letter-a 2.8% .954 n 2.8% .937 n 2.6% .954 1.93n

blackjack 28.4% .715 n 28.4% .713 n 28.4% .715 1.93n

The results in Table 8 show that by using the budget-sensitive progressive sampling algorithm to choose the training data it is possible to achieve results that are as good as or better than the strategy of always using the natural distribution for error rate and the balanced distribution for AUC—without requiring that any extra examples be procured. In particular, when comparing these two strategies, the progressive sampling strategy has a win-tie-loss record of 10-4-0. While in some cases these wins do not lead to large improvements in performance, in some cases they do (e.g., for the kr-vs-kp data set the sampling strategy yields a relative reduction in error rate of 17%). The results in Table 8 also show that the sampling algorithm performs nearly as well as the "Pick Best" strategy (it performs as well in 11 of 14 cases), which is almost twice as costly. Because the progressive sampling strategy performs nearly as well as the "Pick Best" strategy, we conclude that when the progressive sampling strategy does not substantially outperform the 
"Pick Natural/Balanced" strategy, it is not because the sampling strategy cannot identify a good 
(i.e., near-optimal) class distribution for learning, but rather that the optimal class distribution happens to be near the natural (balanced) distribution for error rate (AUC). Note that there are some data sets (optdigits, contraceptive, solar-flare, car) for which this is not the case and hence the "Pick Natural/Balanced" strategy will perform poorly. Unfortunately, because these data sets would yield relatively small training sets, the progressive sampling algorithm could not be run on them. 