\documentclass{amsart}
\usepackage{icml2003}
\usepackage{epsf}
\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
\theoremstyle{plain}    
\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}{Lemma}[section]
\newtheorem{prop}{Proposition}[section]
\newtheorem{defn}{Definition}[section]
\numberwithin{equation}{section} %% Comment out for sequentially-numbered
\numberwithin{figure}{section} %% Comment out for sequentially-numbered

\makeatother

\begin{document}
\thispagestyle{empty} %% remove page numbering on first page.
\twocolumn[
\icmltitle{Cost-Sensitive Learning based on Cost-Proportionate Example Weighting}
 
\icmlauthor{Bianca Zadrozny}
{zadrozny@cs.ucsd.edu}
\icmladdress{Department of Computer Science and Engineering, University of California, 
San Diego, La Jolla, CA 92093}
\icmlauthor{John Langford}{jcl@cs.cmu.edu}
\icmladdress{Mathematical Sciences Department,
IBM T.~J.~Watson Research Center, 
Yorktown Heights, NY 10598}
\icmlauthor{Naoki Abe}{nabe@us.ibm.com}
\icmladdress{Mathematical Sciences Department, 
IBM T.~J.~Watson Research Center, 
Yorktown Heights, NY 10598}
\vskip 0.3in
\vskip 0.3in
]
\renewcommand{\baselinestretch}{0.5}
\begin{abstract}
We propose and evaluate a family of methods for converting classification 
learning algorithms into cost-sensitive ones.  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 by resampling. 
We give some theoretical performance guarantee 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, C-RAG, 
based on cost-proportionate rejection sampling and ensemble aggregation, 
achieves excellent predictive performance on two publically avaliable 
data sets, while drastically reducing the computational required by 
existing methods. 
\end{abstract}

\section{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 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.

Recently there has been a body of work done to address this issue, 
in the machine learning and data mining communities, which has 
become known as ``cost-sensitive learning.''
Current research in cost-sensitive learning falls into three 
categories. The first category is concerned with making particular
classifier learners cost-sensitive \cite{Holte}. The second
category uses Bayes risk theory to assign each example to its
lowest risk class \cite{Domingos,ZaEl01,Margineantu}. This requires
estimating class membership probabilities and, in the case where costs
are non-deterministic, also requires estimating expected costs
\cite{ZaEl01}. The third category concerns meta-methods for converting 
arbitrary classification learning algorithms into cost-sensitive ones 
\cite{Domingos}. The work described in the current paper belongs 
to the last category. 

In particular, our approach is akin to the pioneering work of Domingos 
on MetaCost \cite{Domingos}, which also is a general method for converting
cost-sensitive learning problems to cost-insensitive learning
problems.  We emphasize, however, that our method is distinguished by
the following properties: (1) it is even simpler; (2) it admits certain 
theoretical performance guarantee; 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 methods we propose is motivated by 
a folk theorem that we formalize and prove in section \ref{sec-folk}.
This theorem states that altering the original sampling 
distribution \( D \) to another \( \hat{D} \),  
by mutiplying by a factor that is proportionate to the relative 
cost (or importantce) of each example, 
makes any error-minimizing cost-insensitive classifier learner
accomplish expected cost minimization on the original distribution.
Representing samples drawn from \( \hat{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: Resample according to these same weights. 

While the transparent-box approach cannot be applied on 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 learners.
It turns out, however, that simple resampling-with-replacement can 
result in severe overfitting related to duplicate examples.  

We propose, instead, to employ {\em cost-proportionate rejection sampling} 
to realize the latter approach, which allows us to independently draw 
examples according to \( \hat{D} \).  
(In essence, this method accepts each example in the input sample with
probability proportional to its associated weight.)  
We show a theoretical guarantee about this method, which says that 
this sampling method will produce 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 about a sampling scheme: in general, 
we would expect any sampling method that uses less examples to compromise 
on the predictive performance.  

We can take advantage of the runtime savings made possible by this sampling 
technique by running the classification algorithm on multiple draws of 
sample and averaging over the resulting classifiers.  
This last method is what we call {\em C-RAG} 
(cost-proportionate rejection sampling with aggregation).  
C-RAG 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. 

\section{Motivating Theory and Methods} 

\subsection{A Folk Theorem}

\label{sec-folk}

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\times Y\times C \) where \( X
\) is the input space to a classifier,  \( Y \) is a (binary) output 
space and \( C \subset [0,\, \, \infty ) \) is the importance (extra cost) associated with 
mislabeling that example. The goal is to learn a classifier \( h:X\rightarrow Y \) which 
minimizes the expected cost, 
$$E_{x,y,c\sim D}[c \, I(h(x)\neq y)]$$ given training data of
the form: \( (x,y,c) \), where $I(\cdot )$ 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
cost-sensitive learning \cite{Elkan,Domingos}, when the output space is binary.\footnote{How to formulate the problem in this way when the output space is not binary is nontrivial 
and is beyond the scope of this paper.} 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 any particular 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 basis. 

A basic folk theorem \footnote{ We say ``folk theorem'' here because
the result appears to be known and understood by some.  It is 
straightforward to derive from results in decision theory.} 
states that if we have examples drawn from the distribution:
\[
\hat{D}(x,y,c)\equiv \frac{c}{E_{x,y,c\sim D}[c]}D(x,y,c)\]
then optimal error rate classifiers for \( \hat{D} \) are optimal cost 
minimizers for data drawn from \( D \).

\begin{prop}
\label{th:translate}(Translation Theorem) 
For all distributions, $D$, there exists a 
constant $N=E_{x,y,c\sim D}[c]$ such that for all classifiers, $h$:
\[ 
E_{x,y,c\sim \hat{D}}[I(h(x)\neq y)] = N \, E_{x,y,c\sim D}[c \, I(h(x)\neq y)]
\]
\end{prop}
\begin{proof}
$$
E_{x,y,c\sim D}[c \, I(h(x)\neq y)]
=\sum _{x,y,c}D(x,y,c)c \, I(h(x)\neq y)$$

$=N\sum _{x,y,c}\hat{D}(x,y,c)I(h(x)\neq y)$

$=N E_{x,y,c\sim \hat{D}}[I(h(x)\neq y)]$

where \( \hat{D}(x,y,c)=\frac{c}{N}D(x,y,c) \).
\end{proof}
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 $\hat{D}$ is equivalent to
choosing a $h$ to minimize the expected cost under $D$.  Similarly,
$\epsilon$-approximate error rate minimization under $\hat{D}$ is
equivalent to $N\epsilon$-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 \( \hat{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.

\subsection{Transparent Box: Using Weights Directly}

\label{sec-weights}

\subsubsection{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 \emph{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 else-where for a number of {\em weak learners} used in boosting, 
but we will describe them here for completeness. 
%However, the ability to take a weight vector as input is \emph{not} 
%sufficient. 
%Naoki: I think that the weak learners in boosting are supposed to 
%minimize errors with respect to the distribution specified by the weights.
The classifier learning algorithm is 
to use the weights so that it effectively learns from data drawn
according to \( \hat{D} \).  This specific requirement is easy to
apply to all learning algorithms which fit the statistical query model
\cite{SQ}.

\begin{figure}
\begin{center}
\epsfxsize=7cm
\leavevmode\epsfbox{sq_model.eps}
\caption{\label{fig:sq}A figure showing the statistical query model of learning algorithms.
%Many learning algorithms have a data-independent portion which forms functions
%(queries) for which an expected value is calculated on the training data in
%a ``query oracle''. 
For any learning algorithm decomposable in this form,
there is a generic method for learning from a reweighted distribution directly. }
\end{center}
\end{figure}

As shown in figure \ref{fig:sq}, 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 explicitly dependent upon
individual examples (rather than on statistics derived from the sample
set).

Although with finite data we cannot precisely calculate
the expectation \( E_{x,y\sim D}[f(x,y)] \), with high probability 
we can approximate expectations (dependent on the training set size), 
given a set of samples drawn from the underlying distribution \( D \). 

Whenever we have a learning algorithm that can be decomposed as in
figure \ref{fig:sq}, there is a simple recipe for using the weights
directly. Instead of simulating the expectation with \(
\frac{1}{|S|}\sum _{(x,y)\in S}f(x,y) \), we use \( \frac{1}{\sum
_{(x,y,c)\in S}c}\sum _{(x,y,c)\in S}cf(x,y) \).  This method is
equivalent to importance sampling for \( \hat{D} \) using the
distribution \( D \), and so the modified expectation is an unbiased
Monte Carlo estimate of the expectation w.r.t. \( \hat{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.

\subsubsection{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{\prod_i P(x_i|y)P(y)}{\prod_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({\bf x_i}=x_i) \wedge I({\bf y} = y)$
%divided by the expectation of  $I({\bf 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 $\hat{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
\cite{Bnb}.)  

To incorporate importance weights into AdaBoost \cite{Adaboost}, 
we give the 
importance weights to the weak learner in the first iteration, thus
effectively drawing examples from $\hat{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 $\hat{D}$, which corresponds to the expected cost on $D$.  

\iffalse
Note that AdaCost \cite{Adacost}, a variant of AdaBoost for
cost-sensitive learning, has also been proposed. AdaCost uses a
modified update rule to incorporate costs and improved
performance is observed.  In contrast, 
Proposition~\ref{th:translate} implies that such a modification is
not necessary if we start with examples drawn from $\hat{D}$.  This
may seem contradictory, but note that Proposition~\ref{th:translate} is
purely about error translation and \emph{not} about learning algorithm
design.  From the viewpoint of the proposition, AdaCost is a
learning algorithm with a different bias than the AdaBoost bias.  Just
as other boosting algorithms such as LogitBoost \cite{Logitboost} are
sometimes superior to AdaBoost, AdaCost may be sometimes superior to
AdaBoost.
%Note that AdaCost 
%performance on our problem is similar to reweighted Adaboost (although 
%computationally, fewer iterations are required).
%Commented out by Bianca:it's confusing to talk about experiments here
%maybe we can add something later on, but I am not confident that my experiments
%with AdaCost are correct.
\fi 

\subsubsection{Support Vector Machine} In its basic form, the SVM algorithm \cite{Vapnik,Joachims} 
learns the parameters $a$ and $b$ describing a linear decision rule 
$h(x) = \mbox{sign}(a\cdot 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: 
$$\begin{array}{l}
\mbox{minimize:}~V(a,b,\xi)=\frac{1}{2}a\cdot a + C \sum_{i=1}^{n} \xi_i\\
\mbox{subject to:}~~ \forall i: ~~y_i[a \cdot x_i + b]\geq 1 - \xi_i, ~\xi_i > 0 \\
\end{array}
$$ 
The constraints require that all examples in the training set are
classified correctly up to some slack $\xi_i$. If a training example
lies on the wrong side of the decision boundary, the corresponding
$\xi_i$ is greater than 1. Therefore, $\sum_{i=1}^{n} \xi_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. We can generalize the algorithm to non-linear decision
rules by replacing inner products with a kernel function \cite{Vapnik}
in the formulas above.

The SVM algorithm does \emph{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
$\sum_{i=1}^{n} c_i \xi_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,\xi)$ to
$$\begin{array}{l}
V(a,b,\xi)=\frac{1}{2}a\cdot a + C \sum_{i=1}^{n} c_i \xi_i.
\end{array}
$$
Now $C$ controls the trade off model complexity and total cost.

The SVMLight package \cite{SVMLight} allows users to input importance weights 
$c_i$ and works with the modified $V(a,b,\xi)$ as above, although this feature 
has not yet been documented.

\subsection{Black-box: Resampling methods}

\label{sec-resample} 

Now suppose we do not have ``transparent box'' access to the learner.
In this case, resampling is the obvious method to use in converting a
cost-insensitive learner into a cost-sensitive learner. It turns out
that simple methods for doing this do not work, as discussed next.


\subsubsection{Resampling fails}

Resampling with replacement is a method where the sample \( (x,y,c) \) is drawn
according to the distribution \( p(x,y,c)=\frac{c}{\sum _{(x,y,c)\in 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 \( \hat{D} \). 

In fact, very poor performance can result when using this technique. 
(See Table~\ref{table:resampling} in Section~\ref{section:results}.)  
The poor performance of resampling is essentially due to 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 \ref{table:resampling}, 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\footnote{ This 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 \cite{Framework} have proposed a
modification to bagging, in which partitioning is used in place of
resampling to address this issue.}.  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 that
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
\emph{independently} from \( \hat{D} \). In particular, if \( \hat{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.

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}{\sum _{(x,y,c)\in 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 \( \hat{D} \) as desired.


\subsubsection{Cost-proportionate rejection sampling}

There is another technique called rejection sampling 
% citation would be good !
which allows us to draw samples independently from the distribution 
\( \hat{D} \),
given samples drawn independently from \( D \), and thus avoids the
duplication problem.  In rejection sampling, samples from \( \hat{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)\in S}c\leq Z \).\footnote{In
practice, we choose the minimal $Z= \max _{(x,y,w)\in S}c$ so as
to maximize the size of the resampled set $S'$.  A data-dependent choice
of $Z$ is \emph{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. } 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 \( \hat{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.

\begin{thm}
(Correctness) For all cost-sensitive sample sets $S$, if cost-proportionate 
rejection sampling produces a sample set $S'$ and $A(S')$ achieves $\epsilon$ 
classification error:
\[ E_{x,y \sim \hat{D}} [I(h(x)\neq y)] \leq \epsilon
\]
then $h=A(S')$ approximately minimizes cost:
\[
E_{x,y,c \sim D} [c \, I(h(x)\neq y)] \leq \epsilon N
\]
where $N= E_{x,y,c\sim D}[c]$.
\label{thmcorrect}
\end{thm}
\begin{proof}
Rejection sampling produces a sample set \( S' \) drawn independently
from \( \hat{D} \).  By assumption \( A(S') \) outputs a classifier 
which approximately minimizes errors under the distribution \( \hat{D} \).  
An application of the translation theorem (Proposition~\label{th:translate})
completes the proof.
%It may be a good idea to expand this proof a bit ? - Naoki 
\end{proof}

\subsubsection{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, as we show theoretically using the 
so-called {\em agnostic PAC-learning model} 
\cite{Valiant,agnostic}, which formalizes the notion of probably 
approximately optimal learning from a worst case distribution $D$. 

\begin{defn} 
(Agnostic PAC-learning)  A learning algorithm $A$  is a $m(1/\epsilon,
1/\delta)$-learner  if for all  distributions $D$,  the classification
error rate of its output $h$  is at most $\epsilon$ more than the best
achievable  by  any member  of  $H$ with  probability  at  least $1  -
\delta$, whenever the sample size exceeds $m(1/\epsilon,1/\delta)$.
\end{defn}

By analogy an $m(1/\epsilon,1/\delta)$ cost-sensitive learner has at
most $\epsilon$ expected cost given $m(1/\epsilon,1/\delta)$ samples.

We want to compare the cost-sensitive PAC-learning sample complexity
of two methods: rejection sampling and using the original dataset.
Let $m_\textrm{trivial}(1/\epsilon, 1/\delta)$ be the cost-sensitive
sample complexity of using the original sample set and
$m_\textrm{reject}(1/\epsilon, 1/\delta)$ be the cost-sensitive sample
complexity of the rejection sampling transformation.

\begin{thm} (Sample Complexity Comparison)
\[
m_{\textrm{trivial}}(1/\epsilon, 1/\delta) 
= \Omega ( m_{\textrm{reject}}(1/\epsilon, 1/\delta)).
\]
\end{thm}
\begin{proof}
The cost-sensitive sample complexity of using the original sample set
satisfies $m_{\textrm{trivial}}(1/\epsilon, 1/\delta) =
\Theta(m(Z/\epsilon, 1/\delta))$ where $m(1/\epsilon, 1/\delta)$ is
the misclassification sample complexity of the learning algorithm.

From Theorem~\ref{thmcorrect} and noting that the central limit
theorem implies rejection sampling reduces the sample size by a factor
of $\Theta(N/Z)$, the cost-sensitive sample complexity of rejection
sampling is:
\begin{equation} 
m_{\textrm{reject}}\left( \frac{1}{\epsilon}, \frac{1}{\delta} \right) = 
\Theta\left( \frac{Z}{N} m\left(\frac{N}{\epsilon}, 
\frac{1}{\delta}\right) \right). 
\label{eqngrej}
\end{equation} 
A fundamental theorem from the PAC-learning theory, states
$m(1/\epsilon,1/\delta) = \Omega(\frac{1}{\epsilon} \ln
\frac{1}{\delta})$ \cite{EHKV}.  When $m(1/\epsilon,1/\delta) =
\frac{1}{\epsilon} \ln \frac{1}{\delta}$, Equation~(\ref{eqngrej})
implies:
\begin{eqnarray*} 
m_{\textrm{reject}}\left( \frac{1}{\epsilon}, \frac{1}{\delta} \right) 
%& = & \Theta\left(\max \left\{\frac{Z}{N} \cdot f\left(\frac{\epsilon}{N}, \delta\right), 
%\log \frac{1}{\delta}\right\}\right) 
%\:\:\mbox{Eq~(\ref{eqngrej})}\\
& = & \Theta\left(\frac{Z}{N} \frac{N}{\epsilon} \ln \frac{1}{\delta} \right) \\ 
%& = & \Theta\left(\frac{Z}{N} \cdot N \cdot f\left(\epsilon, \delta\right)\right) 
%\:\:\mbox{by (super)linearity of $f$ in $\frac{1}{\epsilon}$} \\ 
%& = & \Theta(Z \cdot f(\epsilon, \delta)) \\ 
& = & \Theta\left(\frac{Z}{\epsilon} \ln \frac{1}{\delta} \right) \\ 
& = & \Theta\left(m_{\textrm{trivial}}\left(\frac{1}{\epsilon}, \frac{1}{\delta}\right)\right) 
%\:\:\mbox{Equation~(\ref{eqngtri})}
\label{eqnrt1}
\end{eqnarray*}
Finally, note that when $m(1/\epsilon, 1/ \delta)$ grows faster than
linear in $1/\epsilon$, we have $ m_{\textrm{reject}}(1/\epsilon,
1/\delta) = o(m_{\textrm{trivial}}(1/\epsilon, 1/\delta))$, which
finishes the proof.
\end{proof}

Note that the linear dependence of sample size on $1/\epsilon$ 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 
{\em cost-proportionate rejection sampling} will typically do better 
in terms of cost minimization than no sampling.

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 
{\em distills} the original sample and obtains a sample of
smaller size, which is at least as informative as the original.

\subsubsection{Cost-proportionate rejection sampling with aggregation (C-RAG)}
\label{sec-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 ``C-RAG'':

\textbf{C-RAG(Learner \( A \), Sample Set \( S \), count \( t \))}
\begin{enumerate}
\item \textbf{For \( i=1 \) to \( t \) do}
\begin{enumerate}
\item \textbf{\( S'= \) rejection sample from \( S \)}
\item \textbf{Let \( h_{i}\equiv A(S') \)}
\end{enumerate}
\item \textbf{Output \( h(x)=\textrm{sign}\left( \sum _{i=1}^{t}h_{i}(x)\right)  \)}
\end{enumerate}

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).

\section{Empirical evaluation}
\label{section:results}
 
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.

\subsection{The datasets used}
\subsubsection{KDD-98 dataset}

This is the well-known and challenging
dataset from the KDD-98 competition, now available at the UCI KDD
repository \cite{KDD}.  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 (non-respondents), it is fixed at $\$0.68$. 

\subsubsection{DMEF2 dataset}

This dataset can be obtained from the DMEF dataset library \cite{DMEF}
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. 

\subsection{Experintal results}

\subsubsection{results on transparent-box approach}

Table \ref{table:resultsWeights} (top) shows the results obtained when
we apply Naive Bayes, boosted Naive Bayes (100 iterations) and
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.  Cost-sensitive boosted Naive Bayes gives
results comparable to the best so far with this dataset \cite{ZaEl01}
using more complicated methods.
 
We optimized the parameters of the SVM by cross-validation on the
training set.  The best parameters (polynomial kernel with degree 3
and $C=5\times10^{-5}$) were used to obtain the results in table
\ref{table:resultsWeights} (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 \ref{table:resultsWeights} (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.


\begin{table}
\begin{center}
KDD98:
\begin{tabular}{|l|c|c|}\hline
Method & Without Weights & With Weights\\ \hline
Naive Bayes & \$0.24 & \$12367 \\
Boosted N. B. &  -\$1.36    &	\$14489 \\
SVMLight &  \$0  &  \$13683 \\ \hline
\end{tabular}
\vspace{5pt}

DMEF2:
\begin{tabular}{|l|c|c|}\hline
Method & Without Weights & With Weights\\ \hline
Naive Bayes & \$16462 & \$32608 \\
Boosted N. B. &  \$121  & \$36381 \\
SVMLight & \$0  &  \$36443 \\ \hline
\end{tabular}
\end{center}
\caption{Profits on the KDD-98 and DMEF2 datasets using 
learners that accept importance weights directly.}
\label{table:resultsWeights}

\end{table}

\subsubsection{results on black-box approach}

Table~\ref{table:resampling} 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 \cite{C4.5} and Naive Bayes. The training set profits are on
the original training set from which we draw the resampled sets.

\begin{table}
KDD-98:
\begin{tabular}{|c|c|c|c|c|c|c|} \hline
 & \multicolumn{2}{|c|}{Naive Bayes}&\multicolumn{2}{|c|}{C4.5} \\ \hline
Sample Size & Training & Test & Training &  Test \\ \hline
1000   & \$9835 & \$9624     & \$11873 & \$9185  \\ 
10000  & \$10889  & \$11002  & \$21502 & \$10045 \\ 
50000  & \$12726  & \$12297  & \$50977 & \$4135  \\ \hline
\end{tabular}

\vspace{5pt}

DMEF2:
\begin{tabular}{|c|c|c|c|c|c|c|} \hline
 & \multicolumn{2}{|c|}{Naive Bayes}&\multicolumn{2}{|c|}{C4.5} \\ \hline
Sample Size & Training & Test & Training &  Test \\ \hline
1000   & \$31832  & \$32199  & \$28768 & \$27505  \\ 
10000  & \$32171  & \$34748  & \$36006 & \$16323 \\ 
50000  & \$33296  & \$34865  & \$114690 & \$5585  \\ \hline
\end{tabular}
\caption{Profits on the KDD-98 and DMEF2 datasets using resampling.}
\label{table:resampling}
\vspace{-0.5cm}
\end{table}

Figure \ref{fig:costing} shows the results of C-RAG 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.

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 \ref{sec-weights} 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.

\begin{figure}
\begin{center}
\epsfxsize=8cm
\leavevmode\epsfbox{costingKDD98.eps}
\epsfxsize=8cm
\leavevmode\epsfbox{costingDMEF2.eps}
\vspace{-10pt}
\caption{Costing. The graphs shows how profit grows as the number of resampled sets
is increased from 1 to 100.}
\label{fig:costing}
\end{center}
\end{figure}   

\section{Discussion}

{C-RAG 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 cost-sensitive 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.

{\bf Acknowledgments.} Bianca Zadrozny is supported by an IBM Ph.D. 
Fellowship.

\small
\begin{thebibliography}{1}
\bibitem{DMEF} Anifantis, S. (2002). The DMEF Data Set Library. 
The Direct Marketing Association, New York, NY.
\texttt{[http://www.the-dma.org/dmef/dmefdset.shtml]}
\bibitem{Domingos} Domingos, P. (1999). {MetaCost}: A general method 
for making classifiers cost sensitive. {\em Proceedings of the 5th International Conference on 
Knowledge Discovery and Data Mining} (pp. 155-164).
\bibitem{Holte} Drummond, C. \& Holte, R. C. (2000). Exploiting the cost 
(in)sensitivity of decision tree splitting criteria. {\em Proceedings of the 17th
International Conference on Machine Learning} (pp. 239-246).
\bibitem{EHKV} Ehrenfeucht, A., Haussler, D., Kearns, M. \& Valiant, L. (1989). A general lower bound 
on the number of examples needed for learning. {\em Information and Computation}, {\em 82:3}, 247-261.
\bibitem{Bnb} Elkan, C. (1997). {\em Boosting and naive bayesian learning} (Technical Report).
University of California, San Diego.
\bibitem{Elkan} Elkan, C. (2001). The foundations of cost-sensitive learning. {\em Proceedings of the 
17th International Joint Conference on Artificial Intelligence} (pp. 973-978).
\bibitem{Adacost} Fan, W., Stolfo, S. J., Zhang, J. \& Chan, P. K. (1999). 
AdaCost: Misclassification cost-sensitive boosting.  {\em Proceedings of the 16th 
International Conference on Machine Learning}. 97-105.
\bibitem{Framework} Fan, W., Wang, H., Yu, P. \& Stolfo, S.J. (2002).
A framework for scalable cost-sensitive learning based on 
combining probabilities and benefits. {\em Proceedings of the 2nd SIAM International Conference on 
Data Mining} (pp. 97-105).
\bibitem{Adaboost} Freund, Y. \& Schapire, R. E. (1997). A decision-theoretic generalization of on-line learning and an 
application to boosting. {\em Journal of Computer and System Sciences}, {\em 55:1}, 119-139.
\bibitem{Logitboost} Friedman, J., Hastie, T. \& Tibshirani, R. (1998).
{\em Additive logistic regression: a statistical view of boosting} (Technical Report). Stanford University.
\bibitem{KDD} Hettich, S. \& Bay, S. D. (1999). 
The UCI KDD Archive. University of California, Irvine. \texttt{[http://kdd.ics.uci.edu/]}.
\bibitem{SVMLight} Joachims, T. (1999). Making large-scale SVM learning practical. 
In {\em Advances in Kernel Methods - Support Vector Learning}. MIT Press.
\bibitem{Joachims} Joachims, T. (2000). 
Estimating the generalization performance of a SVM efficiently. {\em Proceedings of the 17th International 
Conference on Machine Learning} (pp. 431-438).
\bibitem{agnostic} Kearns, M., Schapire, R., \& Sellie, L. (1998). 
Toward Efficient Agnostic Learning. {\em Machine Learning}, {\em 17}, 115-141.
\bibitem{SQ} Kearns, M. (1998). Efficient noise-tolerant learning from statistical queries. 
{\em Journal of the ACM}, {\em 45:6}, 983-1006.
\bibitem{Margineantu} Margineantu, D. (2002). Class probability estimation and cost-sensitive classification decisions.
{\em Proceedings of the 13th European Conference on Machine Learning} (pp. 270-281).
\bibitem{C4.5} Quinlan, J. (1993). {\em C4.5: Programs for Machine Learning}. San Mateo, CA: Morgan Kaufmann.
\bibitem{Valiant} Valiant, L. (1984). A theory of the learnable. 
{\em Communications of the ACM}, {\em 27:11}, 1134-1142.
\bibitem{Vapnik} Vapnik, V. (1998). {\em Statistical Learning Theory}. Chichester, UK: Wiley.
\bibitem{ZaEl01} Zadrozny, B. and Elkan, C. (2001). Learning and making decisions when costs 
and probabilities are both unknown. {\em Proceedings of the 7th International Conference on 
Knowledge Discovery and Data Mining} (pp. 203-213).
\end{thebibliography}



\end{document}
