resulting class distribution yields the best possible classification performance for a training set of size n. 

The sampling strategy relies on several assumptions. First, we assume that the cost of executing the learning algorithm is negligible compared to the cost of procuring examples, so that the learning algorithm may be run multiple times. This certainly will be true when training data are costly. We further assume that the cost of procuring examples is the same for each class and hence the budget n represents the number of examples that can be procured as well as the total cost. This assumption will hold for many, but not all, domains. For example, for the phone data set described in Section 1 the cost of procuring business and consumer "examples" is equal, while for the telephone fraud domain the cost of procuring fraudulent examples may be substantially higher than the cost of procuring non-fraudulent examples. The algorithm described in this section can be extended to handle non-uniform procurement costs. 

The sampling algorithm selects minority-class and majority-class training examples such that the resulting class distribution will yield classifiers that tend to perform well. The algorithm begins with a small amount of training data and progressively adds training examples using a geometric sampling schedule (Provost, Jensen & Oates, 1999). The proportion of minority-class examples and majority-class examples added in each iteration of the algorithm is determined empirically by forming several class distributions from the currently available training data, evaluating the classification performance of the resulting classifiers, and then determining the class distribution that performs best. The algorithm implements a beam-search through the space of possible class distributions, where the beam narrows as the budget is exhausted. 

We say that the sampling algorithm is *budget-efficient* if all examples selected during any iteration of the algorithm are used in the final training set, which has the heuristically determined class distribution. The key is to constrain the search through the space of class distributions so that budget-efficiency is either guaranteed, or very likely. As we will show, the algorithm described in this section is guaranteed to be budget-efficient. Note, however, that the class distribution of the final training set, that is heuristically determined, is not guaranteed to be the best class distribution; however, as we will show, it performs well in practice. 

The algorithm is outlined in Table 7, using pseudo-code, followed by a line-by-line explanation (a complete example is provided in Appendix C). The algorithm takes three user-specified input parameters: µ, the geometric factor used to determine the rate at which the training-set size grows; n, the budget; and *cmin*, the minimum fraction of minority-class examples and majorityclass examples that are assumed to appear in the final training set in order for the budgetefficiency guarantee to hold.5 For the results presented in this section, µ is set to 2, so that the training-set size doubles every iteration of the algorithm, and *cmin* is set to 1/32. 

The algorithm begins by initializing the values for the *minority* and *majority* variables, which represent the total number of minority-class examples and majority-class examples requested by the algorithm. Then, in line 2, the number of iterations of the algorithm is determined, such that the initial training-set size, which is subsequently set in line 5, will be at most *cmin* - n. This will allow all possible class distributions to be formed using at most *cmin* minority-class examples and *cmin* majority-class examples. For example, given that µ is 2 and *cmin* is 1/32, in line 2 variable K will be set to 5 and in line 5 the initial training-set size will be set to 1/32 n. 