\documentclass{acm_proc_article-sp}

\newtheorem{theorem}{Theorem} 
\newtheorem{corollary}{Corollary} 
\newtheorem{lemma}{Lemma}  
\newtheorem{proposition}{Proposition}
\newtheorem{define}{Definition} 
\newtheorem{conjecture}{Conjecture} 

\DeclareMathOperator*{\E}{E}
\DeclareMathOperator*{\Ehat}{\widehat{E}}


\begin{document}
\title{An Iterative Method for Multi-class Cost-sensitive Learning}
\numberofauthors{2}
\author{
\alignauthor Naoki Abe and Bianca Zadrozny\\
       \affaddr{Mathematical Sciences Dept.}\\
       \affaddr{IBM T.~J.~Watson Res. Ctr.}\\
       \affaddr{Yorktown Heights, NY 10598}\\
       \email{nabe,zadrozny@us.ibm.com}
\alignauthor John Langford\\
       \affaddr{Toyota Technological Institute at Chicago}\\
       \affaddr{1427 East 60th Street, 2nd Flr.}\\% - Press Building}\\
       \affaddr{Chicago, IL 60637}\\
       \email{jl@tti-c.org}
}
\date{27 February 2004}
\maketitle

\begin{abstract} 
Cost-sensitive learning addresses the issue of classification 
in the presence of varying costs associated with different types of 
misclassification. In this paper, we present a method for solving 
multi-class cost-senstive learning problems using any binary 
classification algorithm.  This algorithm 
is based on a number of techniques: iterative weighting, data space
expansion, and gradient boosting with stochastic ensembles.  We
establish some theoretical performance guarantees concerning the
convergence and optimality of a variant of the method and present 
empirical evidence of effectiveness for real-world problems in terms of
predictive performance (cost minimization).
\end{abstract} 

\keywords{cost-sensitive learning, multi-class classification, boosting, 
sampling, memory light learning}

\section{Introduction}

Classification in the presence of varying costs associated with 
different types of misclassification is important for practical 
applications, including many data mining applications. 
A body of work on this subject has become known as 
{\em cost-sensitive learning}, in the areas of machine learning and 
data mining. 

\iffalse
We often idealize classification as a problem where every example is
equally important, and the cost of misclassification is always the
same.  The real world is messier.  Typically some examples are much
more important than others, and the cost of misclassifying in one way
differs from the cost of misclassifying in another way.  A body of
work on this subject has become known as {\em cost-sensitive
learning}.
\fi

Research in cost-sensitive learning falls into three main
categories. The first category is concerned with making particular
classifier learners cost-sensitive, including methods specific for
decision trees \cite{Knoll,Bradford}, neural networks \cite{GeWy03}
and support vector machines \cite{FuRo02}.  The second category uses
Bayes risk theory to assign each example to its lowest expected cost
class \cite{Domingos,ZaEl01b}.%,Margineantu}.
This requires classifiers to
output class membership probabilities and sometimes requires
estimating costs \cite{ZaEl01b} (when the costs are unknown at
classification time).  The third category concerns methods that modify
the distribution of training examples before applying the classifier
learning method, so that the classifier learned from the modified
distribution is cost-sensitive.  We call this approach {\em
cost-sensitive learning by example weighting}.  Work in this area
includes stratification methods \cite{ChSt98,Breiman84} and the {\em
costing} algorithm \cite{ZLA03}.  This approach is very general since
it reuses arbitrary classifier learners and does not require accurate
class probability estimates from the classifier.  Empirically this
approach attains similar or better cost-minimization performance.

Unfortunately, current methods in this category suffer from a major
limitation: they are well-understood only for two-class problems. 
In the two-class case, 
it is easy to show that each example should be weighted
proportionally to the difference in cost between predicting correctly
or incorrectly \cite{ZLA03}.  However, in the multi-class case there is
more than one way in which a classifier can make a mistake, breaking
the application of this simple formula.  Heuristics, such as weighting
examples by the average misclassification cost, have been proposed
\cite{Breiman84,MargThesis}, but they are not well-motivated
theoretically and do not seem to work very well in practice when
compared to methods that use Bayes risk minimization \cite{Domingos}.

In this paper, we propose a method for multi-class cost-sensitive
learning based on iterative example weighting schemes.  There are a
number of key techniques we employ in this method: (1) an iterative
process which empirically adjusts the example weighting according to
the performance of learning; (2) data expansion for
multi-class labels; and (3) gradient boosting \cite{Mason00} 
with stochastic ensembles. 
We establish a theoretical performance guarantee for a variant of 
this algorithm, given that the component classification algorithm 
satisfies a certain {\em weak learning assumption}.  
We test this and related algorithms on several datasets and discover good 
performance in terms of predictive performance 
(cost minimization).
% deleted for now
%performance both in terms of predictive performance 
%(cost minimization) and computational efficiency.

The paper presents some algorithmic motivations, the algorithm itself,
along with some analysis, and empirical results for this algorithm on
several datasets.

\section{Preliminaries} 
\label{sec:prelim}

We begin by introducing some general concepts and notation we use in 
the rest of the paper. 

\subsection{Cost-sensitive learning and related problems} 
\label{subsec:problems}

A popular formulation of the cost-sensitive learning problem is via
the use of a cost matrix.  A cost matrix, $C(y_1,y_2)$, specifies how
much cost is incurred when misclassifying an example labelled $y_2$ as
$y_1$, and the goal of a cost-sensitive learning method is to minimize
the expected cost.  Zadrozny and Elkan \cite{ZaEl01b} noted that this
formulation is not applicable in situations in which misclassification
costs depend on particular instances, and proposed a more general form
of cost function, $C(x,y_1,y_2)$, that allows dependence on the
instance $x$.  This formulation is actually over-general, because for
any one example $x$ there is only one possible cost per prediction,
$C(x,y)$.  

Once we allow the costs to depend on each example, it is natural to 
assume that the costs are generated according to some distribution, 
along with the examples, which leads to the following formulation. 
In (multiclass) cost sensitive classification, examples of the form 
$(x, c_1, ..., c_k)$ are drawn from a distribution $D$ 
over a domain $X \times R^{+^k}$.  
(Throughout the paper, we will let $k$ denote the number of labels.)  
Given a set of examples, 
$S = (x, c_1, ..., c_k)^m$,
the goal is to find a classifier 
$h: X \rightarrow \{1,...,k\}$ 
which minimizes the expected cost of the classifier:
\begin{equation}
\arg \min_{h} \E_{(x,c_1,...,c_k) \sim D} c_{h(x)}
\label{eq:pre1}
\end{equation}
The above optimization is invariant to two normalizations.  First, for
every example drawn we can subtract a constant so that the minimal
cost is $0$.  For any learning problem we do this implying,
\[
\forall (x,c_1,...,c_k)\,\,\,\, \min_y c_y = 0. 
\] 
The above optimization is also invariant to a rescaling of the costs.
Using this invariant, we rescale so that the expected sum of costs is $1$.
In particular, 
\[
\E_{(x,c_1,...,c_k) \sim D} \sum_{y=1}^k c_y = 1
\]
Since every cost sensitive distribution can be altered to obey these
results without changing the optimization, these normalizations
simplify the space of problems we must consider without reducing the
space of problems we solve.

Note that with this normalization, the above formulation of cost is
equivalent to the common formulation in terms of misclassification
cost, i.e.,
\[
\min_{h} \E_{(x,c_1,...,c_k) \sim D} [c_{h(x)}I(h(x) \neq \arg\min_y c_y)]
\]

Typically learning methods attempt to (approximately) minimize the
expected cost by minimizing the empirical cost on the given training
data over some hypothesis class ${\cal H}$:
\begin{equation}
\arg \min_{h \in {\cal H}} 
\Ehat_{(x,c_1,...,c_k) \sim S} c_{h(x)} = 
\frac{1}{|S|} \sum_{(x,c_1,...,c_k) \in S} c_{h(x)}
\label{eq:csfun}
\end{equation}

As a building block of our method, we make use of methods for solving 
importance weighted classification problems, which we define below.
In importance weighted classification, examples of the form $(x,y,c)$
are drawn from a distribution $D$ over a domain $X \times Y \times R^+$. 
Given a set of examples $S= (x,y,c)^m$, 
the goal is to find a classifer $h: X \rightarrow Y$ 
having minimum importance-weighted misclassificaton error:
\[
\arg \min_h \E_{(x,y,c)\sim D} c \cdot I(h(x)\neq y)
\]
Again, usually, a learning method attempts to meet this goal by 
minimizing the empirical weighted error in  
some hypothesis class ${\cal H}$: 
\begin{equation}
\arg \min_{h \in {\cal H}} 
\Ehat_{(x,y,c) \sim S} c \cdot I(h(x)\neq y) = 
\frac{1}{|S|} \sum_{(x,y,c) \in S} c \cdot I(h(x) \neq y)
\label{eq:iwc}
\end{equation}
\iffalse
We also write $A(S,\vec{c})$, where it is understood that 
the learning algorithm $A$ is takes as input 
the unweighted portion $S$ of the sample and 
the weight vector $\vec{c}$ separately.
\fi

We note that importance weighted classification can be solved 
very well with a classification method, by use of weighted 
rejection sampling techniques \cite{ZLA03}. 

\subsection{Hypothesis representations and other notation} 
\label{subsec:hypo}

We often write `$x \in S$' as a shorthand for `$\exists y \in Y \:
(x,y) \in S$'.

\subsubsection{Stochastic Hypotheses}

In the above, we assumed that the hypotheses output by a cost-sensitive 
learner is a functional hypothesis $h$, i.e. 
\( 
h: X \rightarrow Y. 
\)
We also consider {\em stochastic} hypotheses, $h(y|x)$, which produce a distribution over 
labels given the unlabeled data subject to the stochastic condition:
\[ 
\forall x \in X \: \sum_{y \in Y} h(y|x) = 1. 
\] 
With stochastic hypotheses, cost-sensitive learning is defined as 
that of minimizing the following expected cost:
\[
\arg \min_{h \in {\cal H}} \E_{(x,c_1,...,c_k) \sim D} \E_{y \sim h(\cdot|x)} c_y
\]
Note that in the special case that $h$ is deterministic, 
this formulation is equivalent to the definition given in 
Eq.~\ref{eq:pre1}. 
Also, this is a {\em convexification} of the standard objective 
function that we usually expect a stochastic cost-sensitive learner 
to minimize, i.e. 
\[ 
\E_{(x,c_1,...,c_k) \sim D} c_{\arg \max_y h(y|x)} 
\]

\subsubsection{``Relational'' hypotheses}

One trick we use is embedding the label inside the feature space to
produce a binary classification.  This {\em relational} hypothesis $h:
X \times Y \rightarrow \{ 0, 1 \}$ predicts a $0$ or $1$ given an
input feature $x$ and a label $y$.  Note that a relational hypothesis
may predict $1$ for several hypotheses.

Note that any normal hypothesis $h(x)$ can be thought of as a
relational hypothesis $h(x,y) = I(h(x)=y)$.

\section{The Methodology} 

Our method can be interpreted as a {\em reduction}, which translates a
multi-class cost-sensitive learning problem to a classifier learning
problem.  This method is derived using three key ideas: 1) iterative
weighting; 2) data space expansion; and 3) gradient boosting with
stochastic ensembles.  The first two ideas are combined in a unified
framework given by the third.  We explain the first two key ideas by
exhibiting a prototypical method based on each, and then derive our
main learning method based on these ideas.

\subsection{Iterative cost weighting}
\label{subsec:method1}

We note that the weighting scheme proposed in \cite{ZLA03}, called
{\em costing}, exploits the following observation: For the binary
class case, the above formulation in terms of per example costs,
$x,c_1,c_2$, can be further reduced to a formulation in terms of a
single importance number per example because either $c_1=0$ or
$c_2=0$.  In particular, the importance weighted example $(x,\arg
\min_y c_y, |c_1 - c_2|)$ contains all the information needed to solve
the problem optimally.  This conversion allows us to reduce the
cost-sensitive learning problem to a weighted classifier learning
problem, but it is not immediately obvious how that would be done for
the multi-class scenario.  It is therefore natural to consider
iterative weighting schemes, in which example weights are iteratively
modified in search for the optimal weighting.  The technique, which we
call {\em IW (Iterative Weighting)}, presented in
Figure~\ref{fig:method1}, is an example of such a scheme.
%[John - please add intuitive explanation of why this iterative weighting
%here should work.]
We can show that the final weights of IW are the optimal weights
in some sense, {\em provided} the algorithm converges.
%[John - please fill in intuitive explanation of why this property
%is desirable, why this is optimal in some sense, etc.]
\begin{figure}[t]
\begin{itemize}
\item An input sample 
$S = (x, c_1,...,c_k)^m$.
\item A component learner $A$ that chooses $h:X\rightarrow Y$
given an importance-weighted sample $S'= (x,y,c)^m$.
\item An integer $T$ specifying the number of iterations to be performed.
\end{itemize}
\begin{enumerate}
\item Let $S' =$
\[ 
\{ (x, \arg\min_y c_y, \max_y c_y) | (x, c_1,...,c_k) \in S \}\]
\item {\bf For} $t:= 1$ to $T$ {\bf do}
\begin{enumerate}
\item Let $h_t := A(S')$.
\item Choose $\alpha_t \in [0,1)$, for example $\alpha_t := 1/t$.
\item For each example $(x,y,c) \in S'$ with an error $h_t(x) \neq y$ 
update the importance weight by 
\[
c := \alpha_t c_{h(x)}
+ (1 - \alpha_t) c
\]
\end{enumerate}
\item Return $h_{T}$.
\end{enumerate}
\caption{Method {\em IW (Iterative Weighting)}}
\label{fig:method1}
\end{figure}

\begin{theorem}
\label{johnthm}
Assume IW converges to hypothesis $h$.  Then, 
\[
\Ehat_{(x,y,c) \sim S'} c \cdot I(h(x) \neq y)
= \Ehat_{(x,c_1,...,c_k) \sim S} c_{h(x)}
\]
\end{theorem}

This theorem says that, if the iterative algorithm converges, then the
loss of the component learner with respect to the final weights (right
hand side) is equal to the expected cost for the problem that we wish
to solve (left hand side).

{\bf Proof}

The first equality is just the definition of importance-weighted loss.

At convergence, say at iteration $t+1$, for every example $(x,y,c)$
that the $h_{t+1}$ errs on, we must have:
\[
c = \alpha_t c_{h_t(x)} + (1 - \alpha_t) c
\]
and thus
\[
c = c_{h_t(x)}
\]
Noting that when $h_t$ does not err on $x$,
$I(h_t(x) \neq y) = 0$, it follows that
\[
\Ehat_{(x,y,c)\sim S'} c \cdot I(h_t(x) \neq y) = 
\Ehat_{(x,c_1,...,c_k)\sim S} c_{h_t(x)}
\]
{\bf Q.E.D}

\subsection{Data space expansion}
\label{subsec:methodb}

One drawback to iterative weighting is an inability to directly take
into account the different costs associated with multiple ways of
misclassifying examples.  This can cause issues with non-convergence
of the method in practice.  We address this issue by the technique of
data space expansion, as we describe below.

The objective of minimizing the empirical cost on the original
training sample is equivalent to minimization on the following {\em
expanded} sample. Given a labeled sample $S$ consisting of
$(x,c_1,...,c_k)$ of size $m$ , we define a sample $S'$ of size $m k$
for classification, where $k$ is the size of the label set, i.e. $k =
|Y|$.  First, let $C = \max_{(x,c_1,...,c_k)\in S} \max_y c_y$, then
define $S'$ as follows:
\[
S' = \{ (x, y, C - c_y) | (x, c_1,...,c_k) \in S \}
\]
Minimizing the importance weighted loss,
\begin{equation}
\Ehat_{(x,y,c) \in S'} c \cdot I(h(x) \neq y)
\nonumber
\end{equation}
on this new dataset also minimizes the cost on our original 
sample.  The algorithm DSE (Data Space Expansion), shown in
Figure~\ref{fig:methodb}, takes advantage of this observation. 

\begin{figure}[t]
\begin{itemize}
\item An input sample 
$S = (x, c_1,...,c_k)^m$.
\item A component learner $A$ that takes an importance-weighted sample
$S'= (x,y,c)^m$ and outputs a functional hypothesis $h$, 
possibly by weighted sampling. 
% which tries to minimize the weighted misclassification error.
\end{itemize}
\begin{enumerate}
\item Set $C = \max_{(x,c_1,...,c_k) \in S} \max_{y} c_y$.
\item Set $S' = \{ (x,y,C - c_y) | (x, c_1,...,c_k) \in S, y \in Y \}$
\item return $A(S')$ (by weighted sampling)
\end{enumerate}
\caption{Method {\em DSE (Data Space Expansion)}}
\label{fig:methodb}
\end{figure}

\subsection{Gradient Boosting with Stochastic Ensembles} 
\label{subsec:gradient}

Having described two key ideas, namely iterative weighting and data
space expansion, we now apply them together to arrive at our main
method.  We do so by casting the {\em stochastic} multiclass
cost-sensitive learning in the framework of gradient boosting
\cite{Mason00}, with the objective function defined as the expected
cost of the {\em stochastic ensemble}, obtained as a mixture of
individual hypotheses, on the {\em expanded} data set.  To do this, we
think of an ensemble over $T$ stochastic hypotheses $h_1,...,h_T$ as a
stochastic hypothesis.  In particular,
\[
\forall x \in X, \forall y \in Y, H(y|x) = \Ehat_{h_t \in \{1,...,T\}} h_t(y|x)
\]
Let $H_t$ denote the mixture hypothesis of the learning 
procedure at round $t$. 
The procedure is to update its current combined hypothesis 
by the mixture of the previous combined hypothesis and 
a new hypothesis, i.e. by setting 
\begin{equation}
H_t(y|x) = (1-\alpha)H_{t-1}(y|x) + \alpha h(y|x)
\label{eq:update}
\end{equation}
Now, using Eq.~\ref{eq:update}, the expected cost of the $t$-th
mixture hypothesis at a data point $(x,c_1,...,c_k)$, can be evaluated as
follows.
\begin{eqnarray}
&\E_{y\sim H_t(\cdot|x)} c_y  = & (1-\alpha)\Ehat_{y\sim H_{t-1}(\cdot|x)} c_y + \alpha c_{h(x)}h(y|x) \nonumber\\ 
\nonumber
\end{eqnarray}
If we take the derivative of this cost function at data point 
$(x,c_1,...,c_k)$ with respect to $\alpha$, we get 
\begin{equation}
\frac{\partial \Ehat_{y\sim H_t(\cdot|x)} c_y }{\partial \alpha} 
= c_{h(x)} - \Ehat_{y\sim H_{t-1}(\cdot|x)} c_y
\nonumber
\label{eq:derivative2}
\end{equation}

This is the difference between the per label average cost of the
current {\em ensemble} hypothesis and the cost of the new hypothesis
prediction.

We can consider the output of the hypothesis as a vector
$(h(1|x),...,h(k|x))$ of length $k$.  In this notation, the negative
gradient which the weak learner optimizes is:
\begin{equation}
\label{eq:weaklearner2} 
\Ehat_{(x,c_1,...,c_k \sim S)} \sum_{y \in Y}
\left( -c_y + \Ehat_{y\sim H_{t-1}(\cdot|x)} c_y \right) h(y|x) 
\end{equation}

Note that the individual terms of this expectation can be positive or
negative since $h(x)$ is not necessarily the best (least cost) label.
While the minimization of weighted misclassification with positive and
negative weights makes perfect sense as an optimization problem, its
interpretation as a classification problem is not immediately clear.

We deal with this problem by converting a relational version of the
weighted multi-class classification problem (i.e. of finding $h$ to
maximize Eq.~\ref{eq:weaklearner2}) in each iteration to a weighted
binary classification problem.  Specifically we convert each example
$(x,c_1,...,c_k)$ into a set of \emph{relational} importance weighted
examples $$\left((x,y),\,\,I\left( c_y \leq \Ehat_{y\sim H_{t-1}(\cdot|x)} c_y \right),\,\, 
\left| c_y - \Ehat_{y\sim H_{t-1}(\cdot|x)} c_y \right| \right)$$ one for each value of $y$.

Given the output $g(x,y)$ of this relational importance weighted
classifier, we need to convert it into a stochastic classifier for
combination in the stochastic ensemble.  We do this using the obvious
mapping,
\[ h(y|x) = \frac{1}{\sum_y g(x,y)} \sum_{y} g(x,y)
\]
whenever there is some $y$ such that $g(x,y) = 1$.  Otherwise, we use
$h(y|x) = \frac{1}{k}$.

The overall process, consisting of multiple iterations of such a
reduction, constitutes a reduction of {\em stochastic} multi-class
cost-sensitive classification to binary weighted classification.

With the foregoing definitions, we can now state our main method, 
{\em GBSE} (Gradient Boosting with Stochastic Ensembles),  
which is shown in Figure~\ref{fig:gbse}. 
\begin{figure}[t]
\begin{itemize}
\item An input sample $S = (x, c_1,...,c_k)^m$.
\item A component learner $A$ for (importance weighted) 
binary classification that takes a sample of the form 
$((x, y), l, w)^m$,
and outputs a relational hypothesis $h$ 
belonging to some given hypothesis space ${\cal H}$. 
\item A subprocedure {\bf Stochastic}, as specified in 
Figure~\ref{fig:method2sub}.  
\end{itemize}
\begin{enumerate}
\item Initialize $H_0$ by \\
$\forall x \in X, y \in Y \: H_0(y|x) = 1/k$. 
\item {\bf For} $t:= 1$ to $T$ {\bf Do}
\begin{enumerate} 
\item Let $w_{x,y} = \{- c_y + \Ehat_{y \sim H_{t-1}(\cdot|x)} c_y : y \in Y \mbox{ and } (x,c_1,...,c_k) \in S\}$ 
\item Let 
$S' = \{ ((x, y),\,\,I(w_{x,y}\geq 0),\,\, |w_{x,y}|) : x \in S \mbox{ and } y \in Y \}$.   
\item Let $g := A(S')$
\item $h_t(y|x) := \frac{1}{\sum_y g(x,y)} \sum_{y} g(x,y)$ or $\frac{1}{k}$ if $g(x,y) = 0$ always.
\item Choose $\alpha \in [0,1)$, and set 
$H_t := (1-\alpha) H_{t-1} + \alpha h_t$. 
\item {\bf End For} 
\end{enumerate}
\item Return $H_{T}$. 
\end{enumerate}
\caption{Method {\em GBSE (Gradient Boosting with Stochastic Ensemble)}} 
\label{fig:gbse}
\end{figure}
\begin{figure}[t]
{\bf Stochastic}($h$: a relational hypothesis, 
$F$: a stochastic hypothesis)  
\begin{enumerate}
\item Define $f$ by setting for each $x \in X$:  
\begin{itemize} 
\item if $|\{ y \in Y | h_t(x,y) = 1 \}| = 0$ then 
define for all $y \in Y$, $f_t(x,y) = F_t(x,y)$.
\item if $|\{ y \in Y | h_t(x,y) = 1 \}| = k > 0$ 
then for all $y \in Y$ such that $h_t(x,y) = 1$, 
define $f_t(x,y) = 1/k$, 
and for all other $y' \neq y$ 
define $f_t(x,y') = 0$.
\end{itemize} 
\item Output $f$.
\end{enumerate}
\caption{Sub-procedure {\bf Stochastic}} 
\label{fig:method2sub} 
\end{figure}

\subsection{A Theoretical Performance Guarantee on a Variant} 

Method GBSE was derived using the gradient boosting framework 
with respect to the minimization of empirical cost on the 
{\em expanded} sample.  
It turns out that a strong theoretical performance guarantee can be 
proved on a variant of this method, which is derived by  
applying the gradient boosting framework 
with respect to the empirical cost on the {\em original} sample. 

We begin by defining {\em the per label average cost}, $\tilde{C}(x,H(x))$, 
of a stochastic hypothesis $H$, in general, as follows. 
\begin{equation}
\tilde{C}(x,H(x)) = \frac{1}{k} \sum_{y\in Y} H(x,y) C(x,y)
\end{equation}
so that the empirical loss (cost) of $H$ on sample $S$, 
$C(H,S)$, can be expressed as the sum 
of this per label cost over the {\em expanded data set} 
$S' = \{ (x, y) | x \in S, y \in Y \}$.  
\begin{eqnarray}
C(H,S) & = & 
\sum_x \sum_y H(x,y)C(x,y) \nonumber\\
& = & \sum_x \sum_y \tilde{C}(x,H(x)) \nonumber
\end{eqnarray}
Given the above definition of {\em per label average cost}  
and Eq.~\ref{eq:update}, the cost of the $t$-th mixture hypothesis 
on a sample $S$, $C(H_t, S)$, can be rewritten as follows. 
\begin{eqnarray}
C(H_t,S) & = & \sum_x C(x,H_t(x)) \nonumber\\ 
& = & 
\sum_x \sum_y (1-\beta)H_{t-1}(x,y) C(x,y)+ \beta h(x,y) C(x,y) \nonumber\\ 
& = & 
\sum_x \sum_y \bigl( 
(1-\beta) \frac{1}{k} \sum_y H_{t-1}(x,y) C(x,y) \nonumber\\ 
& & + \beta h(x,y) C(x,y) \bigr) \nonumber\\ 
& = & 
\sum_x \sum_y (1-\beta)\tilde{C}(x,H_{t-1}(x))+ \beta h(x,y) C(x,y)  \nonumber
\end{eqnarray}
It thus leads us to define the {\em per label cost} of $H_{t}$ 
on $(x,y)$, 
$\tilde{C}(x,y,H_{t}(x))$, as follows,  
\begin{equation}
\tilde{C}(x,y,H_{t}) = 
(1-\beta)\tilde{C}(x,H_{t-1}(x))+ \beta h(x,y) C(x,y) 
\nonumber
\end{equation}
so that we have 
\[
C(H_t,S) = \sum_x \sum_y \tilde{C}(x,y,H_{t})
\]
We then take the derivative of the per label cost function 
at each data point $(x,y)$ with respect to $\beta$, 
when $h$ correctly gets the specified label, i.e. $h(x,y) = 1$, we get 
\begin{equation}
\frac{\partial \tilde{C}(x,y,H_t)}{\partial \beta} 
= C(x, y) - \tilde{C}(x, H_{t-1}(x)) 
\nonumber
%\label{eq:derivative1}
\end{equation}

Note that this is analogous to the derivation in the previous section 
for GBSE, except now the average cost by the current ensemble,  
$C(x, H_{t-1}(x))$, is replaced by the average {\em per label} cost, 
$\tilde{C}(x, H_{t-1}(x))$.
Taking the derivative with respect to all $mk$ 
data points will give us a variant of GBSE, GBSE-T, 
which is summarized in Figure~\ref{fig:gbset}.

\begin{figure}[t]
Identical to Method {\em GBSE} of Figure~\ref{fig:gbse}, except 
for the following changes.
\begin{enumerate}
\item 
line 2 is to be replaced by the following: \\
Initialize for all $(x,y) \in S$, 
$w_{x,y} := \tilde{C}(x,F_0(x)) - C(x,y)$. 
\item
line 3.(a) is to be replaced by the following: \\
Set $w_{x,y} := \tilde{C}(x, F_{t-1}(x)) - C(x,y)$, 
for all $(x,y)$ in $S$. 
\end{enumerate}
\caption{Method {\em GBSE-T (Gradient Boosting with Stochastic Ensembles - Theoretical variant)}} 
\label{fig:gbset}
\end{figure}

We can show that GBSE-T has a boosting property 
given a version of weak learning condition on the 
component classifier. This weak learning condition, which we 
make precise below, is one that is sensitive to class imbalance. 
\begin{define}
We say that an algorithm $A$ for the binary 
importance weighted classification problem, 
as defined in Section~\ref{sec:prelim}, 
%by Eq~\ref{eq:iwc}, 
satisfies the {\em weak learning condition} 
for a given classification sample $S = (x,y)^m$, 
if for arbitrary distribution over $S$, 
$\langle w \rangle^m, \sum w = 1$, when it is given 
$S' = (x,y,w)^m$ as input, its output $h$ satisfies 
the following, for some fixed $\gamma > 0$:
\begin{equation}
\sum_{(x,y,w) \in S'} w \cdot I(h(x) = y)
\geq \sum_{y = 0} w + \gamma \sum_{y = 1} w
\label{eq:weak2}
\end{equation}
\label{def:weaklearning}
\end{define} 

\begin{theorem}
\label{prop2} 
Suppose that the component learner $A$ satisfies the weak learning 
condition for the input sample $S$.
Then, the output of GBSE-T will converge to a stochastic ensemble hypothesis 
achieving minimum expected cost on the (original) sample $S$. 
\iffalse
among the class of linear combinations of members of ${\cal F}$, 
where ${\cal F} = \cup_{t=1}^\infty {\cal F}_t$ with 
${\cal F}_t = \{ {\bf Stochastic}(h, F) | h \in {\cal H}, 
F \in {\cal F}_{t-1} \}$. 
\fi 
In particular, if we set $\alpha_t = \alpha$ for all $t$, 
%whenever $T \geq \frac{1}{\gamma \alpha} \log \frac{1}{\epsilon}$, 
\[
\sum_x \sum_y F_T(x,y)C(x,y) 
\leq \mbox{exp} \{ - \frac{\gamma \alpha}{k} T \}
\sum_x \sum_y F_0(x,y)C(x,y)
\]
\end{theorem}
\iffalse 
As explained above, for IEB
we effectively assume that there are $m \times |Y|$ examples, and 
calcuate the corresponding boosting weights. But, 
in order to address the duplication problem, when applying 
this weighting scheme in practice, one would want to do a two-stage 
rejection sampling (sample $x$ with probability proportional to 
$\max_y w(xi, y)$ and then subsequently perform rejection sampling 
with probability $w(x_i, y_i)/\max_y w(x_i,y)$ to ensure that: 
(i) the resulting distribution will be the same as specified by 
the boosting weights; and (ii) duplicate $x$'s are not selected. 
\fi 
{\bf Proof} \\ 
We first establish the following simple correspondence between 
the {\em weak learning conditions} on the relational multi-class 
classification problem that we wish to solve in each iteration, 
and the binary classification problem that is given to the 
component algorithm to solve it. 
\iffalse
The following definitions are 
a restatement of the definitions given in Section~\ref{sec:prelim} 
for the present context.
\fi 
\begin{define}
Let $S$ be a weighted sample of the form 
$S = (x,y,w)^m$, where weights $w$ can be both 
positive and negative, and $y \in Y$. %with $|Y| > 2$. 
Then define a transformed sample $S'$ from $S$ by 
$S' = ((x,y), l, |w|)^m$ where $l = I(w \geq 0)$.
\begin{enumerate}
\item
The relational weighted multi-class classification problem for $S$ 
is to find a relational hypothesis $h: X \times Y \rightarrow \{ 0,1 \}$ 
that maximizes the following sum: 
\[
a(h,S) = \frac{1}{W} \sum_{(x,y,w) \in S} w \cdot h(x,y)
\]
where $W = \sum_{(x,y,w) \in S} |w|$. 
\item 
The weighted binary classification problem for $S'$ 
is to find a hypothesis $h': X \times Y \rightarrow \{ 0, 1 \}$ 
that maximizes the following weighted classification accuracy: 
\[
a'(h',S') = \frac{1}{W} \sum_{((x,y),l,|w|) \in S'} |w| I(h'(x,y) = l)
\]
\end{enumerate}
\label{def:reduction1} 
\end{define} 
\begin{lemma} 
Assume the notatation of Definition~\ref{def:reduction1}.
Then, for arbitrary $\epsilon > 0$, $h$ satisfies the following 
condition on the relational multi-class classification problem for $S$ 
\[
a(h,S) \geq \epsilon
%\nonumber
%\label{eq:weak1}
\]
if and only if (the same) $h$ satisfies the corresponding 
condition on the transformed binary classification problem for $S'$ 
\[
a'(h,S') \geq \frac{\sum_{l = 0} |w|}{W} + \epsilon
%\nonumber
\]
\label{lemma:weak}
\end{lemma} 
{\bf Proof of Lemma~\ref{lemma:weak}}
\begin{eqnarray}
& & W \cdot a(h,S') \nonumber \\
& = & \sum_{((x,y),l,|w|) \in S'} |w| I(h(x,y) = l) \nonumber \\
& = & \sum_{w \geq 0} w I(h(x,y) = 1) \nonumber \\ 
& & +  \sum_{w < 0} - w I(h(x,y) = 0) \nonumber \\	
& = & \sum_{w \geq 0} w h(x,y) 
+ \sum_{w < 0} - w (1 - h(x,y)) \nonumber \\
& = & \sum_{(x,y,w) \in S} w h(x,y)
+ \sum_{w < 0} |w| \nonumber \\
& = & W \cdot a(h,S) + \sum_{(x,y,w) \in S: w < 0} |w| \nonumber
%\label{eq:lemmaweak}
\end{eqnarray}
Hence the lemma follows. 
{\bf Q.E.D.}

{\bf Proof of Theorem~\ref{prop2}}\\
\iffalse
Analogously to 
$F_t := (1-\alpha_t) F_{t-1} + \alpha_t f_t$, 
define   
$H_t := (1-\alpha_t) F_{t-1} + \alpha_t h_t$. 
\fi 
First, note that applying {\bf Stochastic} to $h_t$ can 
increase the expected cost only for $x$'s such that 
$|\{ y | h_t(x,y)=1 \}| = 0$, and for such $x$'s 
the cost of $f_t$ equals that of $F_{t-1}$ by the definition of 
{\bf Stochastic}.
Hence, the empirical cost of $f_t$ on the original sample $S$, 
$C(f_t,S)$, satisfies the following. 
\iffalse
where the expectation is with respect 
to the randomization of the {\bf Functional} procedure, 
here and thereafter.
\fi
\begin{equation}
C(f_t,S) - C(h_t,S) \leq 
\sum_{x: \forall y \: h(x,y)=0} \sum_y \tilde{C}(x, F_{t-1}(x))
\label{eq:thm3a}
\end{equation}
\iffalse
Since 
\begin{equation}
C(F_t,S) - C(H_t,S') = \alpha_t (C(f_t,S') - C(h_t,S'))
\end{equation}
it follows from Eq.~\ref{eq:thm3a} that  
\begin{equation}
C(F_t,S') - C(H_t,S') \leq \alpha_t 
(\sum_{x: \forall y \: h(x,y)=0} \sum_y C(x, F_{t-1}(x,y)))
\label{eq:thm3b}
\end{equation}
\fi 
Now recall that the expected empirical cost of $F_t$ equals the 
following, where we drop the subscript $t$ from $\alpha_t$. 
\begin{eqnarray} 
C(F_t,S) & = & \sum_x \sum_y \tilde{C}(x, F_t(x)) \nonumber \\ 
& = & \sum_{x,y} (1 - \alpha) \tilde{C}(x, F_{t-1}(x))
+ \alpha \sum_{x,y} f(x,y)C(x,y)  \nonumber \\ 
\label{eq:thm3c}
\end{eqnarray} 
Hence, by combining Eq.~\ref{eq:thm3a} and Eq.~\ref{eq:thm3c}, we can 
show the following bound on the decrease in empirical cost in each iteration. 
\begin{eqnarray} 
& & C(F_{t-1},S) - C(F_t,S) \nonumber \\
& = & 
\sum_x \alpha (\sum_y \tilde{C}(x, F_{t-1}(x)) - \sum_y f(x,y)C(x,y)) 
\nonumber \\ 
& = & 
\sum_x \alpha (\sum_y \tilde{C}(x, F_{t-1}(x)) - \sum_y h(x,y)C(x,y)) 
\nonumber \\ 
&  & 
+ \sum_x \alpha (\sum_y h(x,y)C(x,y) - \sum_y f(x,y)C(x,y)) \nonumber \\ 
& \geq & 
\sum_x \alpha (\sum_y \tilde{C}(x, F_{t-1}(x)) - \sum_y h(x,y)C(x,y)) 
\nonumber \\ 
& & - \alpha \sum_{x: \forall y \: h(x,y)=0} \sum_y \tilde{C}(x, F_{t-1}(x)))
\nonumber \\ 
& \geq & \alpha \bigl( \sum_x \bigl(\sum_{y:h(x,y)=1} h(x,y) 
(\tilde{C}(x, F_{t-1}(x)) - C(x,y)) \nonumber \\ 
& & + \sum_{y:h(x,y)=0} \tilde{C}(x, F_{t-1}(x)) \nonumber \\ 
& & - \sum_{x: \forall y \: h(x,y)=0} \sum_y \tilde{C}(x, F_{t-1}(x)) \bigr) \bigr)
\nonumber \\ 
& = & \alpha \bigl( \sum_x (\sum_y h(x,y) 
(\tilde{C}(x, F_{t-1}(x)) - C(x,y)) \nonumber \\ 
& & + (\sum_x \sum_{y:h(x,y)=0} \tilde{C}(x, F_{t-1}(x)) \nonumber \\ 
& & - \sum_{x: \forall y \: h(x,y)=0} \sum_y \tilde{C}(x, F_{t-1}(x))) \bigr)
\nonumber \\ 
& \geq & 
\alpha \sum_x (\sum_y h(x,y)(\tilde{C}(x, F_{t-1}(x)) - C(x,y)) 
\nonumber \\ 
& \geq & 
\alpha \gamma \sum_x \sum_{y: \tilde{C}(x, F_{t-1}(x)) - C(x,y) > 0}
\tilde{C}(x, F_{t-1}(x)) - C(x,y)
\nonumber \\ 
& \geq & 
\alpha \gamma \sum_x \tilde{C}(x, F_{t-1}(x)) 
= \frac{\alpha \gamma}{k} C(F_{t-1}, S) 
\nonumber
\end{eqnarray} 
In the above derivation, 
the second to last inequality follows from the weak learning condition 
and applying Lemma~\ref{lemma:weak} with weights 
$\tilde{C}(x, F_{t-1}(x)) - C(x,y)$.
The last equality follows from
the fact that the weights are normalized 
so that the minimim achievable cost is zero for all $x$.
Noting that the sum of these weights is positive whenever 
the current ensemble hypothesis is sub-optimal, this guarantees 
a positive progress in each iteration unless optimality is achieved. 
Since the expected empirical cost function as defined by 
$\sum_x \sum_y F(x,y) C(x,y)$ is convex (in fact linear), 
this implies convergence to the global optimum.  
Noting that in each iteration, the empirical cost 
is reduced at least by a factor of $1 - \frac{\gamma \alpha}{k}$, 
\iffalse
and the fact that the expected empirical 
cost on the original sample $S$ %(Eq.~\ref{eq:expobj1}) 
is equal to that on the expanded sample $S'$ %(Eq.~\ref{eq:expobj2}), 
\fi 
the theorem follows. {\bf Q.E.D.} \\ 

Note that at earlier iterations, the binary classifier used as the 
component learner is likely to be given weighted sample with balanced 
positive and negative examples. As the number of iterations increases 
and progress is made, however, it will receive samples that are 
increasingly more negative.  (This is because the positive examples 
correspond to labels that can further improve the current performance.)
It therefore becomes easier to attain high weighted accuracy 
by simply classifying all examples to be negative. 
The weak learning condition of Eq.~\ref{eq:weak2} appropriately 
deals with this issue, as it requires that the weak learner 
achieve better weighted accuracy than that attainable by 
assigning all examples to the negative class. 

\iffalse
It is important to note that the output $F_T$ of the procedure described 
above is a stochastic hypothesis. For the original cost-sensitive 
learning problem, this needs to be converted to a classifier. 
The obvious method is to, for each $x$, choose that $y$ that is given 
the maximum value by $H_T$.  It is easy to see that the resulting 
functional hypothesis will also be optimal at convergence, 
in the realizable case, i.e. when the optimal labeling of the 
training data can be realized by the hypothesis space at hand.  

\begin{corollary} 
Define a modified version of GBSE in which the final hypothesis 
$F_T$ is translated to a deterministic hypothesis $G_T: X \rightarrow Y$ by 
\[ 
G_T(x) = \arg \max F_T(x,y) 
\]  
Then, in the realizable case, i.e. when the class of linear combinations 
of ${\cal F}$, written $LIN({\cal F})$, contains a member $F^*$ 
which attains the minimum cost on the input sample, 
with the same weak learning condition as in Theorem~\ref{prop2}, 
$G_T$ will approximately minimize the empirical cost 
on the original sample $S$, namely as $T$ tends to infinity, we have 
\[ 
\lim_{T \rightarrow \infty} 
\sum_{x_i \in S} \tilde{C}(x,F_T(x)) = 
\min_{F \in LIN({\cal F})} \sum_{x_i \in S} \tilde{C}(x_i,F(x_i))
\]
\end{corollary} 
{\bf Proof} 
In the realizable case, the optimal stochastic hypothesis is one that 
classifies all the examples in the expanded training data correctly
and is {\em functional} on the training data.  
\iffalse
Hence, its empirical 
loss is equal to that of the optimal functional hypothesis. 
\fi
Thus, at convergence the functional modification $G_T$ is 
identical to $F_t$ on the training data, 
and its empirical cost equals that of 
the empirically optimal functional hypothesis.
Hence the corollary follows from Theorem~\ref{prop2}.
{\bf Q.E.D.} 
\fi 



\iffalse
\subsection{Variants} 

The method just described, IEB, is a natural result of combining 
the ideas of iterative weighting and data expansion in a gradient 
boosting framework with stochastic ensembles. 
Here we also consider slight variants of IEB. 

Recall that the weighting schemes used in {\em  IWE} and {\em IEB} 
make use of the following weight for an example pair $(x,y)$. 
\begin{equation} 
\label{eq:weight} 
w(x,y) = C(x, H_{t-1}(x)C) - (x, y)
\end{equation} 
Since, in {\em IWE}, each $x$ is labeled with the ``best'' label $y^*$, 
namely that $y$ which has the least cost for $x$, $C(x,y)$, {\em IW}'s
weighting scheme, written $w_1$, is related to that of {\em IEB}, 
$w_2$, by the following relationship.  
\begin{equation} 
\label{eq:weight2} 
w_1(x,y^*) = \max_{y \in Y} w_2(x,y)
\end{equation} 

Now observe that the distribution $D$ on $X \times Y$ can be 
expressed as as the following product: 
\begin{equation} 
\label{eq:distribution2} 
D(x,y) = V(x) \cdot W(y|x) 
\end{equation} 
It is thus natural to consider the weighting scheme, in which 
IWE's weighting, $w_1$, is used for $V(x)$, and 
IEB's weighting, $w_2$, is used for $W(y|x)$. 
This informal argument is for the case in which the 
weights are probabilities (non-negative), but 
we abuse and apply this motivation to our present context 
involving positive and negative weights and arrive at the following 
weighting scheme.
\begin{equation} 
\label{eq:weight3a} 
V(x) = w_1(x,y^*) = \max_{y \in Y} C(x, H_{t-1}(x)) - C(x, y) 
\end{equation} 
\begin{equation} 
\label{eq:weight3b} 
W(y|x) = \frac{|w_2(x,y^*)|}{\sum_{y \in Y} |w_2(x,y)|} = 
\frac{|C(x, H_{t-1}(x)) - C(x, y)|}
{\sum_{y \in Y} C(x, H_{t-1}(x)) - C(x, y)}
\end{equation} 
We call this variant IEB2 (Iterative Expand Binary 2-level weights). 
It is also possible to define a variant in which 
$W(y|x) = 1$ for all labels $y$. We call this variant IEB2-A 
(Iterative Expand Binary 2-level weights with all lables). 

This two-level weight variant is an alternative way of combining 
the techniques of iterative weighting and data expansions.  
One advantage that this approach has over that of IEB is that 
by using the weights, $w_1$, of IWE for the choice of $x$, 
it is assigning importance weights to $x$ according to the 
maximum progress still possible on that $x$ at each stage.
Note that the weak learning assumption required for the performance 
guarantee of IEB becomes harder to meet, as more progress is made
and less further progress is possible. Thus the use of $w_1$ weights 
can be viewed as shifting the distribution so as to make it 
easier for the weak learner to meet that requirement. 

\fi

\iffalse
\begin{figure}[t]
\begin{itemize}
\item An input sample $S = \{ (x_i, y_i) | i=1,...,m \}$. 
\item A weak binary classification learner $A$ that takes a sample 
of the form 
$\{\langle (x_i, y), l \rangle | i=1,...,m, y \in Y, l \in \{ 0, 1 \} \}$,  
and outputs a member $h'$ of some given hypothesis space ${\cal H}'$, 
which weakly minimizes the misclassification error.  
%\item Normalized costs $C(x_i, y) \in [0,1]$ for all data pairs. 
\item A constant $\delta \in [0,1)$ determining how to mix current weights 
with uniform weights. 
\end{itemize}
\begin{enumerate}
\item Define $H_0$ by $\forall x, y\: H_0(x,y) = 1/k$. 
\item Initialize 
$w_{i,y} := (\frac{1}{k}\sum_{y'\in Y} C(x_i,y')) - C(x_i,y)$, 
for $i:= 1$ to $m$, and $y \in Y$.
\item Initialize 
$u_{i} := 1/m$, for $i:= 1$ to $m$. 
\item Initialize 
$w_{i} := \max_{y} w_{i,y}$, for $i:= 1$ to $m$. 
\item Initialize 
$v_{i} := \delta u_i + (1 - \delta) w_i$. 
\item {\bf For} $t:= 1$ to $T$ {\bf Do}
\begin{enumerate} 
\item Set $w_{i,y} := C(x_i, H_{t-1}(x_i)) - C(x_i,y)$, for 
$i:= 1$ to $m$, and for $y \in Y$.   
\item Set 
$w_{i} := \max_{y} w_{i,y}$, for $i:= 1$ to $m$. 
\item Set
$v_i := \delta u_i + (1 - \delta) w_i$. 
\item 
Obtain subsample $X_t = \{ x_i | i = 1,...,m_t \}$ by performing 
rejection sampling from original sample $S$ 
with acceptance probability $v_i$ for each ($i$-th) example.
%\item 
%Obtain subsample $S_t = \{ (x_i,y_i) \}$ by labeling each $x_i$ in $X_t$ 
%by a member of $Y$, with probability proportional to $|w_{i,y}|$. 
\item Set 
$S_t' = \{ \langle (x_i, y), I(w_{i,y}\geq 0) \rangle | i=1,...,m_t, y \in Y \}$.   
\item Define $\vec{|w|} = \langle |w_i| \rangle_{i,y}$. 
\item Let $h_t := A(S, \vec{|w|})$ (either by weighted sampling or feeding 
weights to $A$.) 
\item Choose $\alpha_t \in [0,1)$ and set 
%\[ 
%\alpha = \arg \max_{a} - L((1-a)H_{t-1}+ a h_t, S) 
%\]
$H_t := (1-\alpha_t) H_{t-1} + \alpha_t h_t$. 
\item {\bf End For} 
\end{enumerate}
\item Return $H_{T}$. 
\end{enumerate}
\caption{Method {\em IEB2 (Iterative Expand Binary 2)}} 
\label{fig3} 
\end{figure}
\fi 

\iffalse
\begin{conjecture}
\label{prop3} 
Suppose that the component learner $A$ is a distribution-free strong 
learner.  Then, in the realizable case, 
the output of Method 3 will converge to an ensemble hypothesis 
achieving approximately minimal average cost on the expanded sample $S'$ 
(as defined in the section on Method 2) 
among the class of linear combinations of members of ${\cal H}$. 
That is, as $T$ tends to infinity, 
\[ 
E[\sum_x \sum_y H_T(x,y)C(x,y)] \approx 
\min_{H \in LIN({\cal H})} 
E[\sum_x \sum_y H(x,y)C(x,y)]
\]
\end{conjecture}
{\bf Proof Idea} 
Note that the proof of Theorem~\ref{prop2} can be generalized 
for an arbitrary distribution over $X$.  
Applying the strong learning condition on $A$, rather than the 
weak learning condition, will imply that Method 2's weighting scheme 
will guarantee almost perfect labeling on the training data, with 
respect to whatever distribution $D_t$ over $X$ used at each 
iteration $t$. Thus, the output hypothesis satisfies 
the strong learning condition of Theorem~\ref{prop1},  
and hence argument similar to the proof of Theorem~\ref{prop1}  
will show a guaranteed positive progress in each iteration. 
{\bf Q.E.D.} 
\fi 

\section{Experimental Evaluation} 
\label{sec:experiments}

We use the C4.5 decision tree learner \cite{Quinlan} as the base classifier 
learning method, because it is a standard for empirical comparisons and 
it was used as the base learner by Domingos on the {\em MetaCost} method 
\cite{Domingos}. 

We compare our methods against three representative methods 
also used in \cite{Domingos}: Bagging \cite{Breiman}, 
Averaging cost \cite{ChSt98,Domingos} and MetaCost.
We refer the reader to \cite{Domingos} for their descriptions, 
and only remark on the deviations that exist in our implementation. 
The main deviation is that we use {\em rejection} sampling for all methods, 
while other sampling schemes such as resampling with replacement are 
used in the original methods. 
We do this for two reasons: (1) inadequacy of resampling with replacement, 
especially for C4.5, has been noted by various authors \cite{ZLA03}; 
(2) since our proposed methods use rejection sampling, 
we do the same for the other methods for fairness of comparison.  
We stress that this deviation should only improve their performance.  
Another deviation is that we use a variant of MetaCost that skips the 
last step of running a classifier on a related labeled training data set.  
It has been observed that this variant performs at least as well 
as MetaCost, in termsof cost minimization. 
(This variant has been called {\em BagCost} by Margineantu \cite{MargThesis}.) 

The methods were applied to five benchmark datasets available from 
the UCI machine learning repository \cite{uci} and one dataset 
from the UCI KDD archive \cite{kdd}.
These datasets were selected by the criteria of having approximately 
1,000 data or more, besides being multiclass problems. 
A summary of these datasets is given in Table~\ref{table:datasets}. 
Except for the KDD-99 dataset, these datasets do not have standard 
misclassification costs associated with them. 
For this reason, we follow Domingos and generate cost matrices according to a model that gives higher 
costs for misclassifying a rare class as a frequent one, 
and inversely for lowest.
(Note therefore that our experiments 
do not exploit the full generality of the instance-dependent cost 
formulation presented in Section~\ref{sec:prelim}.)  This reflects 
a situation that is found in many practical data mining applications, 
including direct marketing and fraud detection, 
where the rare classes are the most valuable to identify correctly. 
\begin{table} 
\begin{center}
\begin{tabular}{|c|c|c|c|}\hline
Dataset & \# of examples & \# of classes & Class ratio \\ \hline
Annealing & 898 & 5 & 0.01316 \\
KDD-99 & 197710 & 5 & 0.0001278\\
Letter & 20000 & 26 & 0.9028 \\
Satellite & 6435 & 6 & 0.4083\\
Solar flare & 1389 & 7 & 0.002562 \\
Splice & 3190 & 3 & 0.4634 \\ \hline
\end{tabular}
\end{center}
\caption{Data set characteristics: data size, number of classes, and the 
ratio between the frequency of the most common class to the least common.}
\label{table:datasets}
\end{table} 

Our cost model is as follows:
\iffalse
Let $C(y_1,y_2)$ be the cost of predicting that an example belongs 
to class $y_1$ when its actual label is $y_2$. 
\fi 
Let $\hat{P}(y_1)$ and  $\hat{P}(y_2)$ be the empirical probabilities of 
occurence of classes $y_1$ and $y_2$ in the training data. 
First, we choose the non-diagonal entries of the cost matrix 
$C(y_1,y_2)$, $y_1 \neq y_2$ with uniform probability from 
the interval $[0,2000 \hat{P}(y_1)/\hat{P}(y_2)]$. 
Then, we choose the diagonal entries $C(y_1,y_1)$ uniformly from the interval 
$[0,min_{y_2\neq y_1}C(y_2,y_1)]$. This ensures that the cost of correct classification is always less 
than the cost of classifying incorrectly. 
Note that Domingos, 
chooses the diagonal entries from the interval $[0,1000]$, 
which often leads to cost matrices in which the correct label is 
not the least costly one. Besides being unreasonable 
(see Elkan \cite{El01}), these cost matrices can give 
an unfair advantage to cost-sensitive methods over cost-insensitive ones.
\begin{table*}[t] 
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}\hline
Dataset & Bagging & AverageCost & MetaCost & DSE & GBSE \\ \hline
Annealing & $1103 \pm 170$ & $150 \pm 13$ & $234\pm 37$ & $104 \pm 16$ &  \boldmath$63 \pm 8$  \\
KDD-99 & $336 \pm 64$ & $34 \pm 7$ & $55 \pm 9$ & $69 \pm 11$ & \boldmath$3 \pm 1$  \\
Letter & $182 \pm 4$ & $197 \pm 4$ & \boldmath$155 \pm 4$ & $231 \pm 4$ & $201 \pm 12$\\
Satellite & $283 \pm 14$ & $235 \pm 12$ & $197 \pm 14$ & $235 \pm 14$ & $208 \pm 14$\\
Solar & $5419 \pm 356$  &  $297 \pm 63$ & $5149 \pm 362$ &  $180 \pm 16$ &  \boldmath$83 \pm 22$ \\
Splice & $339 \pm 36$ & $334 \pm 36$ & $325 \pm 37$ & $338 \pm 36$ & $328 \pm 37$\\ \hline
\end{tabular}
\end{center}
\caption{Experimental results: the average cost and standard error.}
\label{table:results}
\end{table*} 

In all experiments, we randomly select 2/3 of the examples in the dataset 
for training and use the remaining 1/3 for testing. 
Also, for each training/test split we generate a 
different cost matrix according to the rules above. 
Thus, the standard deviations that we report 
reflect both variations in the data and in the misclassification costs.

We remark on how the choice of the mixture weight $\alpha_t$ is 
made in our experiments, which was unspecified in the algorithm 
description in Figure~\ref{fig:gbse}. 
In particular, we optimize the choice of $\alpha_t$ by performing 
a simple line search to approximately minimize the empirical cost of 
the resulting ensemble hypothesis on (a part of) the training data. 
Here the optimization is done with respect to the objective of 
minimizing the empirical cost of the functional hypothesis 
derived from the resulting mixture hypothesis by outputting $y$ 
with the maximum probability, namely, 
\[
\max_\alpha \Ehat_{(x,c_1,...,c_k)\sim S} c_{\arg \max_y (1-\alpha) H_{t-1}(x,y) + 
\alpha h_t(x,y)} 
\]

%We note that the mixture weights, $\alpha_t$, of GBSE were optimized 
%by line search using a random subset of the training data. 

The results of these experiments are summarized in Table~\ref{table:results}. 
MetaCost appears to be the best among the existing methods 
used for comparison.  Of the proposed methods in the paper, 
GBSE is the best performing. This confirms our claim that 
the combination of various techniques involved is 
indeed necessary to attain this level of performance. 
(We found that the IW method was non-convergent in practice and 
did not perform extensive evaluation.) 
With regard to the relative performance between GBSE and MetaCost, 
examining these results in conjunction with the data characteristics 
in Table~\ref{table:datasets} reveals a definite trend.  
GBSE's performance is (statistically) significantly better than 
MetaCost on 3 data sets (Annealing, KDD-99 and Solar flare), 
all of which have a very large skew in class frequencies 
(i.e. have very small class ratios.)   
MetaCost does significantly better than GBSE on 1 dataset (letter), 
which has almost no class skew with a class ratio being close to unity. 
The two methods are almost tied on the other two datasets (Satelite 
and Splice), both of which have moderate skew with class ratios 
between 0.4 and 0.5. 

\section{Discussion} 

%We have proposed a novel method for multiclass cost-sensitive learning 
%based on gradient boosting with stochastic ensembles. 
It is not the first time that the issue of incorporating cost-sensitivity 
to boosting has been addressed. For example, AdaCost \cite{Adacost}  
suggested a way of modifying AdaBoost's exponential loss using 
a function (called {\em cost adjustment function}) of the cost 
and confidence.  The rational choice of this cost adjustment function, 
however, appears not to be well-understood. 
The stochastic ensemble that we employ in the prepsent paper 
provides a straightforward but reasonable way of incorporating 
cost and confidence, i.e. in terms of expected cost. 
An interesting future direction is to investigate the 
relationship between these alternative approaches to cost-sensitive 
boosting.  Also note that AdaCost, being a modification of AdaBoost, 
is restricted to the two-class problems. 
Cost-sensitive extension of various multiclass versions of boosting 
is another interesting future research topic. 

\iffalse
[Bianca: Please write this section.]
[Overview: we conduct a subset of the experiments conducted by Domingos
on MetaCost]
[Briefly describe the methods used for comparion, citing literature: 
MetaCost, AveCost, Bagging]
[Describe the method for generating cost matrices]
[Describe the results]
[Discuss the results: predictive accuracy, data size comparison, 
dependence of relative performance on the data characteristics, 
cost skewness, data size, etc]
\fi

%\nocite{aha:thesis90,fisher:aaai89,jones:mlj94,langley:book95,maloof:tr98,shrager:book90}


\section{Acknowledgments}


\iffalse
\section{Additional authors} 
Additional authors: 
Bianca Zadrozny (Mathematical Sciences Dept., 
IBM T.~J.~Watson Research Center, 
Yorktown Heights, NY 10598, 
email: {\texttt{zadrozny@us.ibm.com}}) 
Edwin Pednault (Mathematical Sciences Dept., 
IBM T.~J.~Watson Research Center, 
Yorktown Heights, NY 10598, 
email: {\texttt{pednault@us.ibm.com}}) 
Chidanand Apte (Mathematical Sciences Dept., 
IBM T.~J.~Watson Research Center, 
Yorktown Heights, NY 10598, 
email: {\texttt{apte@us.ibm.com}}) 
\fi 

%
% The following two commands are all you need in the
% initial runs of your .tex file to
% produce the bibliography for the citations in your paper.
\bibliographystyle{abbrv}
\bibliography{kdd04multi}  % sigproc.bib is the name of the Bibliography in this case
% You must have a proper ".bib" file
%  and remember to run:
% latex bibtex latex latex
% to resolve all references
%
% ACM needs 'a single self-contained file'!
%
%APPENDICES are optional
\balancecolumns


% That's all folks!
\end{document}

