Cost-Sensitive Learning based on Cost-Proportionate Example Weighting

Bianca Zadrozny zadrozny@cs.ucsd.edu Department of Computer Science and Engineering, University of California, San Diego, La Jolla, CA 92093

John Langford jcl@cs.cmu.edu Mathematical Sciences Department, IBM T. J. Watson Research Center, Yorktown Heights, NY 10598

Naoki Abe nabe@us.ibm.com Mathematical Sciences Department, IBM T. J. Watson Research Center, Yorktown Heights, NY 10598

Abstract

We propose and evaluate a family of methods for converting classification learning algorithms and classification theory into cost-sensitive algorithms and theory. The proposed conversion method is based on cost-proportionate weighting of the training examples, which can be realized either by feeding the weights to the classification algorithm (as often done in boosting), or (in a black-box manner) by careful subsampling.

We give some theoretical performance guarantees on the proposed methods, as well as empirical evidence that the method gives rise to practical alternatives to existing approaches.

In particular, one of the proposed methods, costing, based on cost-proportionate rejection sampling and ensemble aggregation, achieves excellent predictive performance on two publically avaliable data sets, while drastically reducing the computation required by existing methods.

1 Introduction

Classification learning problems naturally come with costs. For example, there is a cost associated with failing to predict rain and a cost associated with predicting rain when it is actually sunny. The optimal classification of “umbrella day” or not is inherently dependent on these costs. There are challenging real world data mining problems,such as fraud detection, medical diagnosis and various problems in business decision-making, that are inherently cost dependent and for which it is quite common to observe highly nonuniform costs. In many cases, one class is rare, but the cost of not recognizing some of the examples belonging to this class is high. In these domains, learning methods that do not take costs into account do not perform well. In extreme cases, ignoring costs may produce a model that is useless because it classifies every example as belonging to the most frequent class even though misclassifications of the least frequent class result in very large errors.

Recently a body of work has attempted to address this issue, with techniques known as “cost-sensitive learning” in the machine learning and data mining communities. Current research in cost-sensitive learning falls into three categories. The first category is concerned with making particular classifier learners cost-sensitive [3]. The second category uses Bayes risk theory to assign each example to its lowest risk class [2, 20, 16]. This requires estimating class membership probabilities and, in the case where costs are non-deterministic, also requires estimating expected costs [20]. The third category concerns meta-methods for converting arbitrary classification learning algorithms into cost-sensitive ones [2]. The work described here belongs to the last category.

In particular, the approach here is akin to the pioneering work of Domingos on MetaCost [2], which also is a general method for converting cost-sensitive learning problems to cost-insensitive learning problems. However, the method here is distinguished by the following properties: (1) it is even simpler; (2) it has some theoretical performance guarantees; and (3) it does not involve any probability density estimation in its process: MetaCost estimates conditional probability distributions via bagging with a classifier in its procedure, and as such it also belongs to the second category (the Bayes risk minimization approach) mentioned above.

The family of proposed methods is motivated by a folk theorem that is formalized and proved in section 2.1. This theorem states that altering the original sampling distribution D to another D̂, by mutiplying by a factor that is proportionate to the relative cost (or importance) of each example, makes any error-minimizing cost-insensitive classifier learner accomplish expected cost minimization on the original distribution. Representing samples drawn from D̂, however, is more challenging than it may seem. There are two basic methods for doing this, starting with a sample set drawn from D: (i) Transparent Box: Supply the relative costs of training data as example weights to the classification learning algorithm. (ii) Black Box: carefully subsample according to these same weights.

While the transparent box approach cannot be applied with arbitrary classifier learners, it can be applied to many, including any classifier which only uses the data to calculate expectations. We show (empirically) that this method results in good performance. The black box approach has the advantage that it can be applied to any classifier learner. It turns out, however, that simple resampling-with-replacement can result in severe overfitting related to duplicate examples.

We propose, instead, to employ cost-proportionate rejection sampling to realize the latter approach, which allows us to independently draw examples according to D̂. (In essence, this method accepts each example in the input sample with probability proportional to its associated weight.) This method comes with a theoretical guarantee: In the worst case this sampling method produces a classifier that achieves at least as good approximate cost minimization as applying the base classifier learning algorithm on the entire sample. This is a remarkable property for a subsampling scheme: in general, we expect any technique using only a subset of the examples to compromise predictive performance.

The runtime savings made possible by this sampling technique enable us to run the classification algorithm on multiple draws of subsamples and average over the resulting classifiers. This last method is what we call costing (cost-proportionate rejection sampling with aggregation). Costing allows us to use an arbitrary cost-insensitive learning algorithm as a black box in order to accomplish cost-sensitive learning, achieves excellent predictive performance and can achieve drastic savings of computational resources, both in terms of time and space.

2 Motivating Theory and Methods

2.1 A Folk Theorem

Standard analysis in learning theory has not incorporated a varying cost per example, so the model here is necessarily slightly nonstandard. In particular, we assume that examples are drawn independently from a distribution D with domain X ×Y ×C where X is the input space to a classifier, Y is a (binary) output space and C ⊂ [0, ∞) is the importance (extra cost) associated with mislabeling that example. The goal is to learn a classifier h: X → Y which minimizes the expected cost,

E_{x,y,c∼D}[cI(h(x) ≠ y)]

given training data of the form: (x,y,c), where I(·) is the indicator function that has value 1 in case its argument is true and 0 otherwise. This model does not explicitly allow using cost information at prediction time although X might include a cost feature if that is available.

As a side note, this formulation of cost-sensitive learning in terms of one number per example is more general than “cost matrix” formulations which are more typical in costsensitive learning [6, 2], when the output space is binary.^{1} In the cost matrix formulation, costs are associated with false negative, false positive, true negative, and true positive predictions. Given the cost matrix and an example, only two entries (false positive, true negative) or (false negative, true positive) are relevant for that example. These two numbers can be further reduced to one: (false positive - true negative) or (false negative - true positive), because it is the difference in cost between classifying an example correctly or incorrectly which controls the importance of correct classification. This difference is the importance c we use here. This setting is more general because the importance may vary on a example-by-example basis.

A basic folk theorem ^{2} states that if we have examples drawn from the distribution:

D̂(x,y,c) ≡ \frac{c}{E_{x,y,c∼D}[c]}D(x,y,c)

then optimal error rate classifiers for D̂ are optimal cost minimizers for data drawn from D.

Proposition 2.1. (Translation Theorem) For all distributions, D, there exists a constant N = E_{x,y,c∼D}[c] such that for all classifiers, h:

E_{x,y,c∼D̂}[I(h(x) ≠ y)] = \frac{1}{N} E_{x,y,c∼D}[cI(h(x) ≠ y)]

1How to formulate the problem in this way when the output space is not binary is nontrivial and is beyond the scope of this paper.

2We say “folk theorem” here because the result appears to be known by some and it is straightforward to derive it from results in decision theory, although we have not found it published.

Proof.

E_{x,y,c∼D}[cI(h(x) ≠ y)] = ∑_{x,y,c}D(x,y,c)cI(h(x) ≠ y)

= N ∑_{x,y,c}D̂(x,y,c)I(h(x) ≠ y)

= NE_{x,y,c∼D̂}[I(h(x) ≠ y)]

where D̂(x,y,c) = \frac{c}{N}D(x,y,c). □

Despite its simplicity, the translation theorem is useful to us because the right-hand side expresses the expectation we want to control (via the choice of h) and the left-hand side is the probability that h errs under another distribution. Choosing an h to minimize the rate of errors under D̂ is equivalent to choosing a h to minimize the expected cost under D. Similarly, ϵ-approximate error rate minimization under D̂is equivalent to Nϵ-approximate expected cost minimization under D.

The prescription for coping with cost-sensitive problems is straightforward: reweight the distribution in your training set according to the importances so that the training set is effectively drawn from D̂. Doing this in a correct and general manner is more challenging than it may seem and is the topic of the rest of the paper.

2.2 Transparent Box: Using Weights Directly

2.2.1 General conversion

Here we examine how importance weights can be used directly. The approach taken here is a transparent box approach where access to the source code is required, and not a black box approach (which we develop in the next section). In particular, we use the weights within the learning algorithm to accomplish cost-sensitive classification.

The mechanisms for realizing the transparent box approach have been described elsewhere for a number of weak learners used in boosting, but we will describe them here for completeness. The classifier learning algorithm must use the weights so that it effectively learns from data drawn according to D̂. This specific requirement is easy to apply for all learning algorithms which fit the statistical query model [15].

As shown in figure 2.1, many learning algorithms can be divided into two components: a portion which calculates the (approximate) expected value of some function (or query), say f, and “the rest”— a portion which forms these queries and uses their output to construct a classifier. For example, neural networks (with batch-mode gradient updates), decision trees, and Naive Bayes classifiers can be constructed in this manner. Support vector machines are not easily constructible in this way, because the individual classifier is

Figure 2.1.A figure showing the statistical query model of learning algorithms. For any learning algorithm decomposable in this form, there is a generic method for learning from a reweighted distribution directly.

explicitly dependent upon individual examples (rather than on statistics derived from the sample set).

With finite data we cannot precisely calculate the expectation E_{x,y∼D}[f(x,y)]. However, with high probability we can approximate the expectation, given a set of samples drawn independently from the underlying distribution D.

Whenever we have a learning algorithm that can be decomposed as in figure 2.1, there is a simple recipe for using the weights directly. Instead of simulating the expectation with \frac{1}{|S|}∑_{(x,y)∈S}f(x,y), we use \frac{1}{∑_{(x,y,c)∈S}c} ∑_{(x,y,c)∈S}cf(x,y). This

method is equivalent to importance sampling for D̂ using the distribution D, and so the modified expectation is an unbiased Monte Carlo estimate of the expectation w.r.t. D̂.

Note that even when a learning algorithm does not have a statistical query form, it may be possible to incorporate importance weights directly. We now discuss how to incorporate importance weights into some specific learning algorithms.

2.2.2 Naive Bayes and boosting

Naive Bayes learns by calculating empirical probabilities for each output y using Bayes’ rule and assuming that each feature is independent given the output:

P(y|x) = \frac{P(x|y)P(y)}{P(x)}= \frac{∏ _{i}P(x_{i}|y)P(y)}{∏ _{i}P(x_{i})}

Each probability estimate in the above expression can be thought of as a function of empirical expectations according to D, and thus it can be formulated in the statistical query model. For example, p(x_{i}|y) is just the expectation of I(x_{i} = x_{i}) ∧ I(y = y) divided by the expectation of I(y = y). More specifically, to compute the empirical estimate of P(x_{i}|y) with respect to D, we need to count the number of training examples that have y as output, and those having x_{i} as the i-th input dimension among those. When we compute these empirical estimates with respect to D̂, we simply have to sum the weight of each example, instead of counting the examples. (This property is used in the implementation of boosted Naive Bayes [5].)

To incorporate importance weights into AdaBoost [9], we give the importance weights to the weak learner in the first iteration, thus effectively drawing examples from D̂. In the subsequent iterations, we use the standard AdaBoost rule to update the weights. Therefore, the weights are adjusted according to the accuracy on D̂, which corresponds to the expected cost on D.

2.2.3 Support Vector Machine

In its basic form, the SVM algorithm [19, 13] learns the parameters a and b describing a linear decision rule h(x) = sign(a · x + b), so that the smallest distance between each training example and the decision boundary (called the margin) is maximized. It works by solving the following optimization problem:

minimize: V (a,b,ξ) = \frac{1}{2}a · a + C ∑ _{i=1}^{n} ξ_{i}
subject to: ∀i: y_{i}[a · x_{i}+ b] ≥ 1 − ξ_{i}, ξ_{i} > 0

The constraints require that all examples in the training set are classified correctly up to some slack ξ_{i}. If a training example lies on the wrong side of the decision boundary, the corresponding ξ_{i} is greater than 1. Therefore, ∑ _{i=1}^{n} ξ_{i} is an upper bound on the number of training errors. The factor C is a parameter that allows one to trade off training error and model complexity. The algorithm can be generalized to non-linear decision rules by replacing inner products with a kernel function [19] in the formulas above.

The SVM algorithm does not have the form of a statistical query algorithm. Despite this drawback, it is possible to incorporate importance weights in a natural way which results in good behavior. First, we note that ∑ _{i=1}^{n} c_{i}ξ_{i}, where c_{i} is the importance of example i, is an upper bound on the total cost. Therefore, we can modify V (a,b,ξ) to

V (a,b,ξ) = \frac{1}{2}a · a + C ∑ _{i=1}^{n} c_{i}ξ_{i}.

Now C controls the trade off model complexity and total cost.

The SVMLight package [12] allows users to input importance weights c_{i} and works with the modified V (a,b,ξ) as above, although this feature has not yet been documented.

2.3 Black Box: Sampling methods

Now suppose we do not have transparent box access to the learner. In this case, sampling is the obvious method to use in converting from one distribution of examples to another to obtain a cost-sensitive learner using the translation theorem (Proposition 2.1) . As it turns out, straightforward sampling methods do not work well in this case, motivating us to propose an alternative method based on rejection sampling.

2.3.1 Resampling

Resampling-with-replacement is a sampling scheme where each sample (x,y,c) is drawn according to the distribution p(x,y,c) = \frac{c}{∑_{(x,y,c)∈S}c}. Many samples are drawn to create a resampled dataset S′. This method, at first pass, appears useful because every sample is effectively drawn from the distribution D̂. In fact, very poor performance can result when using this technique, which is essentially due to overfitting because of the fact that the samples in S′ are not drawn independently from D̂, as we will elaborate in the section on experimental results (Section 3.)

Resampling-without-replacement is also not a solution to this problem. In resampling-without-replacement, a sample, (x,y,c) is drawn from the distribution p(x,y,c) = \frac{c}{∑_{(x,y,c)∈S}c} and the next sample is drawn from the set S − {x,y,c}. This process is repeated, drawing from a smaller and smaller set according to the weights of the samples remaining in the set.

To see how this method fails, note that resampling-without-replacement m times from a set of size m results in the original set, which (by assumption) is drawn from the distribution D, and not D̂ as desired.

2.3.2 Cost-proportionate rejection sampling

There is another sampling scheme called rejection sampling which allows us to draw samples independently from the distribution D̂, given samples drawn independently from D, and thus avoids the duplication problem. In rejection sampling, samples from D̂ are drawn by first drawing samples from D, and then keeping the sample with probability \frac{c}{Z} where Z is some constant chosen so that max_{(x,y,c)∈S}c ≤ Z.^{3} Rejection sampling results in a set S′ which is generally smaller than S. Furthermore, because inclusion of a sample in S′is independent of other samples, and the samples in S are drawn independently, we know that the samples in S′are distributed independently according to D̂.

Using cost-proportionate rejection sampling to create a set S′and then using a learning algorithm A(S′) is guaranteed to produce an approximately cost-minimizing classifier, as long as the learning algorithm A achieves approximate minimization of classification error.

Theorem 2.1. (Correctness) For all cost-sensitive sample sets S, if cost-proportionate rejection sampling produces a sample set S′and A(S′) achieves ϵ classification error:

3In practice, we choose the minimal Z = max_{(x,y,w)∈S}c so as to maximize the size of the resampled set S′. A data-dependent choice of Z is not formally allowed for rejection sampling. However, the introduced bias appears small when |S| >> 1. A precise measurement of “small” is an interesting theoretical problem.

E_{x,y,c∼D̂}[I(h(x) ≠ y)] ≤ ϵ

then h = A(S′) approximately minimizes cost:

E_{x,y,c∼D}[cI(h(x) ≠ y)] ≤ ϵN

where N = E_{x,y,c∼D}[c].

Proof. Rejection sampling produces a sample set S′drawn independently from D̂. By assumption A(S′) outputs a classifier h such that

E_{x,y,c∼D̂}[I(h(x) ≠ y)] ≤ ϵ

By the translation theorem (Proposition 2.1), we know that

E_{x,y,c∼D̂}[I(h(x) ≠ y)] = \frac{1}{N} E_{x,y,c∼D}[cI(h(x) ≠ y)]

Thus,

\frac{1}{N} E_{x,y,c∼D}[cI(h(x) ≠ y)] ≤ ϵ

and

E_{x,y,c∼D}[cI(h(x) ≠ y)] ≤ ϵN □

2.3.3 Sample complexity of cost-proportionate rejection sampling

The accuracy of a learned classifier generally increases monotonically with the number of samples in the training set. Since cost-proportionate rejection sampling produces a smaller training set (by a factor of about N/Z), worse performance than observed using the original dataset may result.

This turns out to not be the case, in the agnostic PAClearning model [18, 14], which formalizes the notion of probably approximately optimal learning from a worst-case distribution D.

Definition 2.1. (Agnostic PAC-learning) A learning algorithm A has sample complexity m(1/ϵ,1/δ) if for all distributions D, the classification error rate of its output h is at most ϵ more than the best achievable by any member of H with probability at least 1 − δ, whenever the sample size exceeds m(1/ϵ,1/δ).

By analogy, we can formalize the notion of probably approximately cost-sensitive optimal learning from a worstcase distribution D.

Definition 2.2. (Agnostic cost-sensitive PAC-learning) A learning algorithm A has cost-sensitive sample complexity m(1/ϵ,1/δ) if for all distributions D, the expected cost of its output h is at most ϵ more than the best achievable by any member of H with probability at least 1 − δ, whenever the sample size exceeds m(1/ϵ,1/δ).

We want to use this formalism to compare the cost-sensitive PAC-learning sample complexity of two methods: using a sample obtained through rejection sampling and using the original training set. Let m_{orig}(1/ϵ,1/δ) be the costsensitive sample complexity of using the original training set and m_{rej}(1/ϵ,1/δ) be the cost-sensitive sample complexity of using rejection sampling.

Theorem 2.2. (Sample Complexity Comparison) The costsensitive sample complexity of using the original training set is lower bounded by the cost-sensitive sample complexity of using rejection sample, that is

m_{orig}(1/ϵ,1/δ) = Ω(m_{rej}(1/ϵ,1/δ)).

Proof. Since Z is an upper bound on the cost of misclassifying an example, we have that the cost-sensitive sample complexity of using the original training set satisfies

m_{orig}(1/ϵ,1/δ) = Θ(m(Z/ϵ,1/δ))

where m(1/ϵ,1/δ) is the (cost-insensitive) sample complexity of the learning algorithm.

From Theorem 2.1 and noting that the central limit theorem implies that rejection sampling reduces the sample size by a factor of Θ(N/Z), the cost-sensitive sample complexity of rejection sampling is:

(2.1) m_{rej}(1/ϵ,1/δ)= Θ( \frac{Z}{N}m(N/ϵ,1/δ)) .

A fundamental theorem from PAC-learning theory states that m(1/ϵ,1/δ) = Ω((1/ϵ)ln(1/δ)) [4]. When m(1/ϵ,1/δ) = (1/ϵ)ln(1/δ), Equation (2.1) implies:

m_{rej}(1/ϵ,1/δ) = Θ( \frac{Z}{N} \frac{N}{ϵ} ln(1/δ))
= Θ( \frac{Z}{ϵ} ln(1/δ))
= Θ(m_{orig}(1/ϵ,1/δ))

Finally, note that when m(1/ϵ,1/δ) grows faster than linear in 1/ϵ, we have m_{rej}(1/ϵ,1/δ) = o(m_{orig}(1/ϵ,1/δ)), which finishes the proof. □

Note that the linear dependence of sample size on 1/ϵ is only achievable by an ideal learning algorithm, and in practice super-linear dependence is expected, especially in the presence of noise. Thus, the above theorem implies that cost-proportionate rejection sampling minimizes cost better than no sampling for worst case distributions.

This is a remarkable property about any sampling scheme, since one generally expects that predictive performance is compromized by using a smaller sample. For worst-case distributions, cost-proportionate rejection sampling distills the original sample and obtains a sample of smaller size, which is at least as informative as the original.

2.3.4 Cost-proportionate rejection sampling with aggregation (costing)

The fact that cost-proportionate rejection sampling produces a much smaller training set means that the computational time required for learning a classifier is generally much smaller. If we repeatedly perform rejection sampling from S to produce multiple resampled sets S′_{1},...,S′_{m}, we can learn a classifier for each set and output a final classifier by taking the average over all learned classifiers. We call this technique “costing”:

Costing(Learner A, Sample Set S, count t)

(1) For i = 1 to t do

(a) S′= rejection sample from S

(b) Let h_{i} ≡ A(S′)

(2) Output h(x) = sign(∑ _{i=1}^{t} h_{i}(x))

The goal in averaging is to improve performance. There are several empirical and theoretical pieces of evidence suggesting that averaging can be useful. On the empirical side, many people have observed good performance from bagging despite throwing away a 1/e fraction of the samples (and the weakened overfitting control as noted earlier). On the theoretical side, there has been considerable work which proves that the “complexity” (ability to overfit) of an average of classifiers might be smaller than naively expected when a large margin exists. The preponderance of learning algorithms producing averaging classifiers provides significant evidence that averaging is useful.

Note that despite the extra computational cost of averaging, the overall computational time of costing may be smaller than for a learning algorithm using sample set S (with or without weights).

3 Empirical evaluation

We show empirical results using two real-world datasets. We selected datasets that are publicly available and for which misclassification cost information is available on a per example basis. Both datasets are from the direct marketing domain. Although there are many other domains that are cost-sensitive, such as credit card fraud detection and medical diagnosis, publicly available cost-sensitive datasets are lacking.

3.1 The datasets used

3.1.1 KDD-98 dataset

This is the well-known and challenging dataset from the KDD-98 competition, now available at the UCI KDD repository [11]. The dataset contains information about persons who have made donations in the past to a particular charity. The decision-making task is to choose which donors to mail a request for a new donation. The measure of success is the total profit obtained in the mailing campaign.

The dataset is divided in a fixed way into a training set and a test set. Each set consists of approximately 96000 records for which it is known whether or not the person made a donation and how much the person donated, if a donation was made. The overall percentage of donors is about 5%. Mailing a solicitation to an individual costs the charity $0.68. The donation amount for persons who respond varies from $1 to $200. The profit obtained by soliciting every individual in the test set is $10560, while the profit attained by the winner of the KDD-98 competition was $14712.

The importance of each example is the absolute difference in profit between mailing and not mailing an individual. Mailing results in the donation amount minus the cost of mailing. Not mailing results in zero profit. Thus, for positive examples (respondents), the importance varies from $0.32 to $199.32. For negative examples (nonrespondents), it is fixed at $0.68.

3.1.2 DMEF2 dataset

This dataset can be obtained from the DMEF dataset library [1] for a nominal fee. It contains customer buying history for 96551 customers of a nationally known catalog. The decision-making task is to choose which customers should receive a new catalog so as to maximize the total profit on the catalog mailing campaign. Information on the cost of mailing a catalog is not available, so we fixed it at $2.

The overall percentage of respondents is about 2.5%. The purchase amount for customers who respond varies from $3 to $6247. As is the case for the KDD-98 dataset, the importance of each example is the absolute difference in profit between mailing and not mailing a customer, where not mailing results in zero profit. Therefore, for positive examples (respondents), the importance varies from $1 to $6246. For negative examples (non-respondents), it is fixed at $2.

We divided the data set in half to create a training set and a test set. As a baseline for comparison, the profit obtained by mailing a catalog to every individual on the training set is $26474 and on the test set is $27584.

3.2 Experimental results

3.2.1 Transparent box results

Table 1 (top) shows the results obtained when we apply Naive Bayes, boosted Naive Bayes (100 iterations) and

KDD98:

Method  Without Weights With Weights
Naive Bayes  $0.24  $12367
Boosted N. B.  -$1.36  $14489
SVMLight  $0  $13683

DMEF2:

Method  Without Weights With Weights
Naive Bayes  $16462  $32608
Boosted N. B.  $121  $36381
SVMLight  $0  $36443

Table 1. Profits on the KDD-98 and DMEF2 datasets using learners that accept importance weights directly.

SVMLight to this dataset. When using cost-insensitive versions of the learners (without weights), the classifiers label very few of the examples positive, resulting in small (and even negative) profits. With the costs given as weights to the learners, the results improve significantly. Costsensitive boosted Naive Bayes gives results comparable to the best so far with this dataset [20] using more complicated methods.

We optimized the parameters of the SVM by crossvalidation on the training set. The best parameters (polynomial kernel with degree 3 and C = 5 × 10^{−5} ) were used to obtain the results in table 1 (with weights), which are not so impressive. This may be a relatively hard problem for margin-based classifiers because the data is very noisy. Note also that running SVMLight on this dataset takes about 3 orders of magnitude longer than AdaBoost with 100 iterations on the same machine.

Table 1 (bottom) shows the results obtained when we apply Naive Bayes, boosted Naive Bayes (100 iterations) and SVMLight to this dataset, with and without giving the weights to the learners. In this case, the best setting for the SVM (found through cross-validation) is a linear kernel with C = 0.0005. Again, we see that weighting the examples is crucial for obtaining good performance in terms of profit.

3.2.2 results on black-box approach

Table 2 shows the results of applying different learning algorithms to the KDD-98 and DMEF2 data using resampled training sets of different sizes. We use the C4.5 decision tree learner [17] and Naive Bayes. The training set profits are on the original training set from which we draw the resampled sets.

These results here confirm that straightforward application of resampling to implement the black-box approach can result in very poor performance, as we remarked earlier. The poor performance of resampling is essentially due to

KDD-98:

Naive Bayes  C4.5
Sample Size Training Test Training Test
1000  $9835 $9624 $11873 $9185
10000  $10889 $11002 $21502 $10045
50000  $12726 $12297 $50977 $4135

DMEF2:

Naive Bayes  C4.5
Sample Size Training Test Training Test
1000  $31832 $32199 $28768 $27505
10000  $32171 $34748 $36006 $16323
50000  $33296 $34865 $114690 $5585

Table 2. Profits on the KDD-98 and DMEF2 datasets using resampling.

overfitting. When there are large differences in the magnitude of importance weights, it is typical for an example to be picked twice (or more). In table 2, we see that as we increase the resampled training set size and, as a consequence, the number of duplicate examples in the training set, the more overfitting we see for C4.5. The training profit becomes larger while the test profit becomes smaller.

Examples which appear multiple times in the training set of a learning algorithm defeat the complexity-control methods built into learning algorithms^{4}. For example, suppose that we have a decision tree algorithm which divides the training data into a “growing set” (used to construct a tree) and a “pruning set” (used to prune the tree for complexity control purposes). If the pruning set contains examples which appear in the growing set, the complexity control mechanism is defeated. Note that learning algorithms which cannot overfit much (such as Naive Bayes), are not much affected by this problem.

The fundamental difficulty here is that the samples in S′ are not drawn independently from D̂. In particular, if D̂ is a density, the probability of observing the same example twice given independent draws is 0, while the probability using resampling is greater than 0. Thus resampling-with-replacement fails because the resampled set S′is not constructed independently.

Figure 3.1 shows the results of costing on the KDD-98 and DMEF-2 datasets, with C4.5, SVMLight and Naive Bayes as the base learners and Z = 200 or Z = 6247, respectively. In the KDD-98 case, each resampled set has only about 600 examples, because the importance of the examples varies from 0.68 to 199.32 and there are few “important” examples. About 55% of the examples in each set are positive, even though on the original dataset the percentage of positives is only 5%. With t > 50, the C4.5 version yields profits close to $15000, which is exceptional performance for this dataset.

4This observation has implications for the practice of bagging, although the loss of complexity control is not as severe as observed here. Uniform resampling from a set of size m, m times produces only about \frac{m}{e} duplicates. Since (with high probability)

not all examples are duplicates, complexity control in bagging is only weakened and not removed. We note that Fan et al [8] have proposed a modification to bagging, in which partitioning is used in place of resampling to address this issue.

In the DMEF2 case, each set has only about 35 examples, because the importances vary even more widely (from 2 to 6246) and there are even fewer examples with a large importance than in the KDD-98 case. The percentage of positive examples in each set is about 50%, even though on the original dataset it was only 2.5%. With t = 100, the profits are $38697 for Naive Bayes, $37965 for C4.5 and $36383 for SVM.

For learning the SVMs, we used the same kernels as we did in section 2.2 and the default setting for C. In that section, we saw that by feeding the weights directly to the SVM, we obtain a profit of $13683 on the KDD-98 dataset and of $36443 on the DMEF2 dataset. Here, with t > 10, we obtain profits around $13200 and $36500, respectively. However, this did not require parameter optimization and, even with t = 100, was much faster to train. The reason for the speed-up is that the time complexity of SVM learning is generally superlinear in the number of training examples.

4 Discussion

Costing is a technique which produces a cost-sensitive classification from a cost-insensitive classifier using only black box access. This simple method is fast, results in excellent performance and allows us to automatically apply any future results in cost-insensitive classification to costsensitive classification.

Another nice property of any reduction is that it applies to the theory of classification as well as to learning algorithms. Thus, a bound on the future error rate of A(S′) implies a bound on the expected cost w.r.t. the distribution D. This additional property of a reduction is especially important because cost-sensitive learning theory is still young and relatively unexplored.

One direction for future work is multiclass cost-sensitive learning. If there are K classes, the minimal representation of costs is K − 1 weights. A reduction to cost-insensitive classification using these weights is an open problem.

Acknowledgments. Bianca Zadrozny is supported by an IBM Ph.D. Fellowship.

References

[1] Anifantis, S. (2002). The DMEF Data Set Library. The Direct Marketing Association, New York, NY. [http://www.the-dma.org/dmef/dmefdset.shtml] Figure 3.1.Costing. The graphs shows how profit grows as the number of resampled sets is increased from 1 to 100.

[2] Domingos, P. (1999). MetaCost: A general method for making classifiers cost sensitive. Proceedings of the 5th International Conference on Knowledge Discovery and Data Mining (pp. 155-164).

[3] Drummond, C. & Holte, R. C. (2000). Exploiting the cost (in)sensitivity of decision tree splitting criteria. Proceedings of the 17th International Conference on Machine Learning (pp. 239-246).

[4] Ehrenfeucht, A., Haussler, D., Kearns, M. & Valiant, L. (1989). A general lower bound on the number of examples needed for learning. Information and Computation, 82:3, 247-261.

[5] Elkan, C. (1997). Boosting and naive bayesian learning (Technical Report). University of California, San Diego.

[6] Elkan, C. (2001). The foundations of cost-sensitive learning. Proceedings of the 17th International Joint Conference on Artificial Intelligence (pp. 973-978).

[7] Fan, W., Stolfo, S. J., Zhang, J. & Chan, P. K. (1999). Ada-Cost: Misclassification cost-sensitive boosting. Proceedings of the 16th International Conference on Machine Learning. 97-105.

[8] Fan, W., Wang, H., Yu, P. & Stolfo, S.J. (2002). A framework for scalable cost-sensitive learning based on combining probabilities and benefits. Proceedings of the 2nd SIAM International Conference on Data Mining (pp. 97-105).

[9] Freund, Y. & Schapire, R. E. (1997). A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55:1, 119-139.

[10] Friedman, J., Hastie, T. & Tibshirani, R. (1998). Additive logistic regression: a statistical view of boosting (Technical Report). Stanford University.

[11] Hettich, S. & Bay, S. D. (1999). The UCI KDD Archive. University of California, Irvine. [http://kdd.ics.uci.edu/].

[12] Joachims, T. (1999). Making large-scale SVM learning practical. In Advances in Kernel Methods - Support Vector Learning. MIT Press.

[13] Joachims, T. (2000). Estimating the generalization performance of a SVM efficiently. Proceedings of the 17th International Conference on Machine Learning (pp. 431-438).

[14] Kearns, M., Schapire, R., & Sellie, L. (1998). Toward Efficient Agnostic Learning. Machine Learning, 17, 115-141.

[15] Kearns, M. (1998). Efficient noise-tolerant learning from statistical queries. Journal of the ACM, 45:6, 983-1006.

[16] Margineantu, D. (2002). Class probability estimation and cost-sensitive classification decisions. Proceedings of the 13th European Conference on Machine Learning (pp. 270-281).

[17] Quinlan, J. (1993). C4.5: Programs for Machine Learning. San Mateo, CA: Morgan Kaufmann.

[18] Valiant, L. (1984). A theory of the learnable. Communications of the ACM, 27:11, 1134-1142.

[19] Vapnik, V. (1998). Statistical Learning Theory. Chichester, UK: Wiley.

[20] Zadrozny, B. and Elkan, C. (2001). Learning and making decisions when costs and probabilities are both unknown. Proceedings of the 7th International Conference on Knowledge Discovery and Data Mining (pp. 203-213).