% This file was updated by Dale Schuurmans and Jennifer Dy for ICML-2004
% from a file modifed slightly by Terran Lane for to support/document 
% the new option to the ``usepackage'' statement that selects between the 
% review and final version of the paper.
% This file was updated slightly by Tom Fawcett for ICML-2003
% from the file made available from the ICML-2002 web site.
% This file was modified by Claude Sammut for ICML-2002 from the file
% made available by Pat Langley, Claude-Nicolas Fiechter, Mehmet Goker,
% Cynthia Thompson and Andrea Danyluck for ICML-2K and ICLML-2001.

% Use the following line _only_ if you're still using LaTeX 2.09.
%\documentstyle[icml2003,epsf,mlapa]{article}
% If you rely on Latex2e packages, replace the above line with: 
\documentclass{article}
% Use the following version of the ``usepackage'' statement for
% submitting the draft version of the paper for review.  This will set
% the note in the first column to ``Under review.  Do not distribute.''
\usepackage{icml2004}
% Use this version of the ``usepackage'' statement after the paper has
% been accepted, when creating the final version.  This will set the
% note in the first column to ``Appearing in''
%\usepackage[accepted]{icml2004}
\usepackage{epsf}
\usepackage{mlapa}
\usepackage{epsfig}
\usepackage{pslatex}

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

\begin{document} 

\twocolumn[
\icmltitle{Iterative Methods for Multi-class Cost-sensitive Learning}
 
\icmlauthor{}{}
\icmladdress{{\bf keywords:} cost-sensitive learning,multi-class classification,boosting,sampling,memory light learning}

\vskip 0.3in
]

\begin{abstract} 
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 the method and present empirical
evidence of effectiveness for real-world problems, both in terms of
predictive performance (cost minimization) and computational
efficiency.
\end{abstract} 

\section{Introduction}

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

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,ZaEl01,Margineantu}. This requires classifiers to
output class membership probabilities and sometimes requires
estimating costs \cite{ZaEl01} (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, BrFrOl84} 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 only apply to 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{Z03}.  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{BrFr0l84,Margineantu}, 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 employed in this method: (1) an iterative
process which empirically adjusts the example weighting according to
the difficulty of the learning problem (2) data expansion for
multi-class labels; and (3) a reduction to two-class classifier
learning.  This algorithm comse with some theoretical performance
guarantees for optimality at convergence and convergence given the
convexification of the objective cost function.  We test this
algorithm on several datasets and discover good 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 first define the problems we are concerned with.

\subsection{importance weighted binary classification}

In importance weighted binary classification, examples are drawn from
a distribution $D$ over a domain $X \times \{0,1\} \times R^+$. Given a
set of examples $S= (x,y,i)^m$ the goal is to find (or construct) a
classifer $h: X \rightarrow Y$ which has a small importance-weighted
loss:
\[
\min_h E_{(x,y,c)\sim D} c I(h(x)\neq y)
\]

\subsection{multiclass cost sensitive classification}

In multiclass cost sensitive classification, examples are drawn from a
distribution $D$ over a domain $X \times R^{+^k}$.  Given a set of
examples, $S=(x,c_1,c_2,...,c_k)$, the goal is to find (or construct)
a classifier $h: X \rightarrow \{1,...,m\}$ which minimizes the
expected cost of the classifier:
\[
\min_h E_{(x,c_1,...,c_k)\sim D} c_{h(x)}
\]

\subsection{other definitions}

{\bf This still needs work -John.}

Our methods use a component learner, analagous to a weak learner in
the context of boosting, and combine their hypotheses as a mixture (or
an ensemble of hypotheses).  Most of the proposed methods assume that
an output hypothesis of a weak/component learner is a function from
$X$ to $Y$, i.e.  \( h: X \rightarrow Y.  \) Some of the methods make
use of component learners outputting {\em relational} hypotheses, that
is, hypotheses $h$ that are relations over $X \times Y$, i.e.  $h: X
\times Y \rightarrow \{ 0, 1 \}$, that are not necessarily functions
from $X$ to $Y$.  We also view the functional hypotheses of the form
$h: X \rightarrow Y$ as special cases of conditional distributions,
that is,
\[ 
h: X \times Y \rightarrow [0, 1] 
\]
subject to 
\[ 
\forall x \in x \: \sum_{y \in Y} h(x,y) = 1. 
\] 

This leads us to a non-standard definition
of a stochastic ensemble hypothesis:  
A (stochastic) ensemble hypothesis $H$, that combines multiple 
weak hypotheses, is a conditional distribution defined as 
the mixture of all the component hypotheses, interpreted as 
conditional distributions. 

In this paper, we often use the more general notation of $h(x,y)$, 
even when $h$ is a deterministic function from $X$ to $Y$ 
(not only when they are necessary, as for hypotheses that are 
conditional distributions or relational hypotheses.)  

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$. 
Here we adopt this general formulation, but note that 
in the reasonable case in which the cost is minimized by the 
true label, the redundant information $y_2$ can be dropped 
and write $C(x, y_1)$ for $C(x,y_1,y_2)$. 

For any hypothesis $h$, which is a conditional distribution, define 
$h(x)$ to be $h(x, \cdot): Y \rightarrow [0,1]$, and the cost of $h$ at $x$, 
$C(x,h(x))$ as the average cost of its predicted labels, i.e. 
\[ 
C(x, h(x)) = \sum_{y \in Y} h(x,y) C(x,y). 
\]
We then set the maximization of the expectation of this function
\[ 
E_{x \in D} [\sum_{y \in Y} h(x,y) C(x,y)]
\]
as the objective of a cost-sensitive learner. 
Note that this is a convexification of the standard objective function 
that we usually expect a cost-sensitive learner to minimize, i.e. 
\[ 
E_{x \in D} [C(x, \arg \max_{y \in Y} h(x,y))] 
\]

\iffalse
Finally, we note that in this paper we use the following 
non-standard notation:  
\begin{eqnarray}
\mbox{sign}_{0,1}(x) & = & 0 \:\mbox{if}\: x < 0 \nonumber\\ 
	    & = & 1 \:\mbox{if}\: x \geq 0 \nonumber
\end{eqnarray}
\fi 

\section{The Methods} 

Our methods can conceptually be seen as {\em reductions}, which
translate a multi-class cost-sensitive learning problem to a
classifier learning problem. For this reason, they allow us to solve
the cost-sensitive learning problem using an arbitrary classifier
learning method as a component algorithm.  The reductions are derived
using three key ideas: 1) Iterative weighting; 2) Expanding data
space; and 3) Reduction to binary classification.  These ideas are
combined in a unified fashion, by employing a framework akin to
gradient boosting.  Theoretical performance guarantees are derived
using a convexification of the objective function by the expected cost
function.

\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 
cost per example, $C(x,y_2)$, can be further reduced to a 
formulation in terms of a single importance number per example. 
This is possible by associating a number indicating the 
importance of an example $(x,y_2)$, given by $|C(x,0) - C(x,1)|$.
This conversion allows us to {\em 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 {\em optimal} weighting.  
Our first method, which we call {\em IW (Iterative Weighting)}, 
is based on this idea, and is presented in Figure~\ref{fig:method1}. 

We can show that the final IW weights are the optimal weights   
in some sense, {\em provided} the algorithm converges. 

\begin{theorem}
\label{johnthm} 
At convergence, IW's weights satisfy 
\[
\sum_{x_i} w_{t,i} \cdot I(h_t(x_i) \neq y_i) = 
\sum_{x_i} C(x_i,h_t(x_i)) - C(x_i,y_i) 
\] 
\end{theorem}
{\bf Proof} \\ 
At convergence, say at iteration $t+1$, 
we must have $w_{t+1,i} = w_{t,i}$ for all $x_i$. 
Specifically, for all $x_i$ on which $h_t$ errs, we must have 
\[ 
w_{t+1,i} := \alpha_t w_{t,i} + (1 - \alpha_t)  
(C(x_i, h_t(x_i)) - C(x_i,y_i))
\]
and thus
\[
w_{t,i} = C(x_i, h_t(x_i)) - C(x_i, y_i).
\]
Noting that when $h_t$ does not err on $x_i$, 
$I(h_t(x_i) \neq y_i) = 0$, it follows that 
\[
\sum_{x_i} w_{t,i} \cdot I(h_t(x_i) \neq y_i) = 
\sum_{x_i} C(x_i,h_t(x_i)) - C(x_i,y_i) 
\] 
{\bf Q.E.D}

\subsection{Ensemble Method based on Gradient Boosting}
\label{subsec:method1e}

As it will be shown in the section on empirical evaluation, the above 
method IW is not convergent in practice. 
This motivates us to propose an ensemble version of IW.  
As it turns out, a slight variant of IW can be interpreted 
as a gradient boosting procedure \cite{Mason}, 
and a convergence property can be established. 
Below we explain how we apply the gradient boosting argument 
to derive this variant.

Let $H_t(x)$ denote the mixture hypothesis of the learning 
procedure at round $t$. 
The new 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}
%\label{eq:update}
H_t(x,y) = (1-\beta)H_{t-1}(x,y) + \beta h(x,y) \nonumber
\end{equation}
Thus, the loss (cost) function at a data point $(x,y)$ can be 
defined as the average cost of the mixture, namely, 
\begin{eqnarray}
C(x,H_t(x)) & = & C(x, (1-\beta)H_{t-1}(x) + \beta y_x)  \nonumber\\ 
	    & = & (1-\beta) C(x,H_{t-1}(x)) + \beta C(x,y) \nonumber
\end{eqnarray}
where $y_x$ denotes the hypothesis $p$ that assigns $p(x,y)=1$. 
If we now take the derivative of the cost function at this data point 
$(x,y)$ with respect to $\beta$, we get 
\begin{equation}
%\label{eq:derivative1}
\frac{\partial C(x, H_t(x))}{\partial \beta} 
= C(x, y) - C(x, H_{t-1}(x)) \nonumber
\end{equation}
Note that this is the difference between the cost 
of the current {\em ensemble} hypothesis at the data point in question, 
and the corresponding cost of the new weak hypothesis assigning 
probability one to the {\em correct} label. 

We take this derivative with respect to all data points, $x_i: i=1,..,m$, 
and obtain a gradient which is $m$-dimensional.  
We then wish to take a small step in the $m$-dimensional data space 
to the direction of the minus gradient, but this is not in general possible. 
Instead, we expect the component learner to find a hypothesis $h$ whose 
inner-product with the negative gradient is large 
(or maximized in the ideal case). 
Here the inner product is defined for any two $m$-dimensional vectors  
$f$ and $g$, both members of $[0,1]^m$, as follows. 
\begin{equation} 
\langle f, g \rangle = \frac{1}{Z} \sum_{i=1}^m 
f(x_i,y_i) \cdot g(x_i,y_i) \nonumber
\end{equation} 
where $Z$ is some normalization constant. 
That is, the output $h$ of the component learner should seek to 
maximize the following. 
\begin{equation}
%\label{eq:weaklearner}
- \langle h, \nabla C  \rangle  =  \frac{1}{W} \sum_{i=1}^m 
h(x_i,y_i) (C(x_i, H_{t-1}(x_i)) - C(x_i,y_i)) \nonumber
%& > & (\frac{1}{2} + \gamma)
%\frac{1}{m} \sum_{i=1}^m 
%(C(x_i, H_{t-1}(x_i)) - C(x_i,y_i)) 
\end{equation}
where $W$ denotes the sum of weights, i.e. 
$W = \sum_{i=1}^m C(x_i, H_{t-1}(x_i)) - C(x_i,y_i)$. 
The above argument gives rise to the method, 
IWE (Iterative Weighting Ensemble), shown in Figure~\ref{fig:method1e}. 
\begin{figure}[t]
\begin{itemize}
\item An input sample $S = \langle (x_i, y_i) | i=1,...,m \rangle$. 
\item A component learner $A$ that takes a sample $S$ and weights $\vec{w}$, 
and outputs a member $h$ of hypothesis space ${\cal H}$.
% which tries to minimize the weighted misclassification error.  
\item An integer $T$ specifying the number of iterations to be performed.
\end{itemize}
\begin{enumerate}
\item Set $w_{0,i} := \frac{1}{m}$, for $i:= 1$ to $m$.
\item {\bf For} $t:= 1$ to $T$ {\bf Do}
\begin{enumerate} 
\item Set $w_{t,i} := C(x_i, H_{t-1}(x_i)) - C(x_i,y_i)$, $i:= 1$ to $m$.  
\item Let $h_t := A(S, \vec{w}_t)$. 
\item Set $\alpha_t = \frac{1}{t}$ and set  
$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 IWE (Iterative Weighting Ensemble)}} 
\label{fig:method1e} 
\end{figure}

IWE is essentially an ensemble version of IW, since the weight update 
step of IW is equivalent to the weight update step of IWE; 
To see why this holds, observe that by 
the linearity of the expected cost function, i.e., 
\[
C(x_i, H_{t-1}(x_i)) = \sum_{s=1}^{t-1} \alpha_s C(x_i, h_s(x_i))
\]
the IWE update 
\[
w_{t,i} := C(x_i, H_{t-1}(x_i)) - C(x_i,y_i).
\]
equals 
\[
w_{t,i} := \sum_{s=1}^{t-1} \alpha_s (C(x_i, h_s(x_i)) - C(x_i,y_i))
\]
which is the same as the IW weight update
\[
w_{t,i} := \alpha_t w_{t-1,i} + (1 - \alpha_t)  
(C(x_i, h_{t-1}(x_i)) - C(x_i,y_i)).
\]

\begin{corollary}
\label{johnthm2} 
At convergence, IWE's weights satisfy: 
\[
\sum_{x_i} w_{t,i} \cdot I(h_t(x_i) \neq y_i) = 
\sum_{x_i} C(x_i,h_t(x_i)) - C(x_i,y_i) 
\] 
\end{corollary}
{\bf Proof:} It follows from Theorem~\ref{johnthm} using 
the fact the two weight update rules (for IW and IWE) are equivalent. 
{\bf Q.E.D.}

\subsection{Expanding Data Space} 
\label{subsec:methodb}

One serious drawback of iterative weighting is an inability to
directly take into account the different costs associated with
misclassifying examples. We address this issue by the technique of
expanding data space, as we describe below.

We begin by noting that the empirical cost on the original 
training sample $S$, i.e. 
\begin{equation} 
\sum_{x_i \in S} C(x_i,h(x)) 
\label{eq:expobj}
\end{equation}  
can be written as follows, when we use the more general formulation 
in terms of a relational hypothesis. 
\begin{equation} 
\sum_{x_i \in S} \sum_{y \in Y} C(x_i,y) h(x,y) 
\label{eq:expobj1}
\end{equation} 
Thus, the objective of minimizing the empirical cost on the 
original training sample is equivalent to that of the empirical 
cost on the following {\em expanded} sample. That is, 
given a labeled sample $S$ consisting of $(x_i,y_i)$, $i = 1,...,m$, 
we define another sample $S'$ of size $m k$, where $k$ is 
the size of the label set, i.e. $k = |Y|$, as follows. 
\begin{equation} 
S' = \{ (x_i, y) | i = 1,...,m, y \in Y \} 
\end{equation} 
Then, the objective function of Equation~\ref{eq:expobj1} is 
\begin{equation} 
\sum_{(x_i,y) \in S'} C(x_i,y) h(x,y) 
\label{eq:expobj2}
\end{equation} 
This observation suggests the possibility of feeding the expanded sample 
to a component classifier learner. 
Since the goal of a classifier is to {\em maximize} the agreement 
with the labels specified in the data, we need to convert this 
into a maximization problem.  This can be done by simply converting 
the cost function into a {\em benefit} function, for example, by 
the following definition. 
\begin{equation} 
B(x,y) = C_{max} - C(x,y)
\label{eq:costbenefit}
\end{equation} 
where we used $C_{max}$ to denote $\max_{x_i \in S, y \in Y} C(x_i,y)$. 
Thus, the goal of a component learner is to maximize 
\begin{equation} 
\sum_{(x_i,y) \in S'} B(x_i,y) h(x,y) 
\label{eq:expobj3}
\end{equation} 
This can be done using a classifier with weighted sampling, 
and gives rise to our next method, DSE (Data Space Expansion) 
shown in Figure~\ref{fig:methodb}.
\begin{figure}[t]
\begin{itemize}
\item An input sample $S = \langle (x_i, y_i) | i=1,...,m \rangle$. 
\item A component learner $A$ that takes a sample $S$  
and weights $\vec{w}$, 
and outputs a member $h$ of hypothesis space ${\cal H}$.
% which tries to minimize the weighted misclassification error.  
\item An integer $T$ specifying the number of iterations to be performed.
\end{itemize}
\begin{enumerate}
\item Let 
$S' = \{ (x_i, y) | i=1,...,m, y \in Y \}$.   
\item Set $C_{max} = \max_{x_i \in S, y \in Y} C(x_i,y)$.
\item Set $B(x_i,y) := C_{max} - C(x_i,y)$,   
for $i:= 1$ to $m$ and $y \in Y$.
\item Set $b_{min} = \min_{x_i \in S, y \in Y} B(x_i,y)$.
\item Set $w_{i,y} := B(x_i,y) - B_{min}$, 
for $i:= 1$ to $m$ and $y \in Y$.
\item {\bf For} $t:= 1$ to $T$ {\bf Do}
\begin{enumerate} 
\item Let $h_t := A(S, \vec{w})$ (by weighted sampling) 
\item Set $\alpha_t = \frac{1}{t}$ and set  
$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 DSE (Data Space Expansion)}} 
\label{fig:methodb} 
\end{figure}

\subsection{Reduction to Binary Classification} 

Having described two key ideas, namely iterative weighting and 
data space expansion, we now apply them together. 
As we will see shortly, applying iterative weighting on expanded data 
space will give rise to weights that are both positive and negative, 
and naturally leads to a reduction of (a relational variant of) 
multi-class cost-sensitive learning problem to that of binary 
classification. We will elaborate on this below. 

We expand the data space, as was explained in 
Subsection~\ref{subsec:methodb}.
\begin{equation} 
S' = \{ (x_i, y) | i = 1,...,m, y \in Y \} 
\end{equation} 
\iffalse
Analogously to the IW method, the cost function at a data point 
$(x,y)$ is 
\begin{eqnarray}
C(x,H_t(x)) & = & C(x, (1-\beta)H_{t-1}(x) + \beta y_x)  \\ 
	    & = & (1-\beta) C(x,H_{t-1}(x)) + \beta C(x,y)
\end{eqnarray}
\fi 
As in Subsection~\ref{subsec:method1e}, the 
derivative of the cost function at each data point $(x,y)$ 
with respect to $\beta$ is:
\begin{equation} 
\label{eq:derivative2}
\frac{\partial C(x,y,H_t(x))}{\partial \beta} =  
C(x, y) - C(x, H_{t-1}(x))
\end{equation} 
We now take this derivative with respect to all data points in 
the expanded data set, $(x_i, y) \in S'$, and thus the gradient 
is $mk$-dimensional.  
\iffalse 
We then expect the weak learner to find a hypothesis $h$ whose 
inner-product with the negative gradient is large.  
Here the inner product is defined for two $mk$-dimensional vectors 
$f$ and $g$, both members of $[0,1]^{mk}$.
\begin{equation} 
\langle f, g \rangle = \frac{1}{Z} \sum_{i=1}^m \sum_{y \in Y}
f(x_i,y) \cdot g(x_i,y) 
\end{equation} 
where $Z$ is some normalization constant. 
\fi 
The output $h$ of the weak learner seeks to maximize 
the following sum. 
\begin{equation}
\label{eq:weaklearner2} 
- \langle h, \nabla C  \rangle 
= \frac{1}{W} \sum_{i=1}^m \sum_{y \in Y}
(C(x_i, H_{t-1}(x_i)) - C(x_i, y)) h(x_i,y) 
%& = & \frac{1}{mk} \sum_{i=1}^m 
%(\sum_{y \in Y} h(x_i,y) C(x_i, H_{t-1}(x_i)) - 
%\sum_{y \in Y} h(x_i,y) C(x_i, y_i)) 
\end{equation}
where $W$ denotes the sum of absolute values of the weights, i.e.  
$W = \sum_{i=1}^m \sum_{y \in Y} |C(x_i, H_{t-1}(x_i)) - C(x_i, y)|$. 
\iffalse
In particular, if the following condition holds for some $\gamma > 0$ 
we say that the weak learning condition holds. 
\begin{equation} 
\label{eq:weaklearner2b} 
- \langle h, \nabla C  \rangle 
\geq \gamma
\end{equation} 
\fi 

An important point to observe here is that, the weights 
$w_{i,y} := C(x_i,H_{t-1}(x_i)) - C(x_i,y)$,  
can be negative. This means that the weak learner now receives both 
positive and negative weights.  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. 
In particular, it prohibits the use of weighted sampling as a means 
of realizing the weighted classification problem. 

We deal with this problem by converting the weighted multi-class 
classification problem to a weighted binary classification problem 
by converting each example pair $(x,y)$ to $\langle (x,y), l \rangle$, 
and setting $l = 1$ if the weight on $(x,y)$ is positive, and $l = 0$ 
if the weight is negative.  This is a reduction of a {\em relational} 
variant of multi-class weighted classification, in which 
relational hypotheses over $X \times Y$ are used, 
to binary weighted classification. 
\iffalse
and it is especially useful since we have shown elsewhere how to 
transform a weighted binary classification problem to a pure 
classfication problem (via ``costing'').
\fi 
(This will be made precise later.)

With the foregoing definitions, we can now state the {\em IEB} 
(Iterative Expand Binary) method, 
which is shown in Figure~\ref{fig:method2}. 
\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 a weight vector $\vec{w}$, and 
outputs a member $h'$ of some given hypothesis space ${\cal H}'$, 
which weakly minimizes the weighted misclassification error.  
%\item $mk$-dimensional inner product $\langle h, - \nabla L  \rangle$ 
%defined as above. 
%\item Normalized costs $C(x_i, y) \in [0,1]$ for all data pairs. 
%\item (A la Bianca and John) define ``benefits'' by 
%$B(x_i, y_i) = 1 - C(x_i, y_i)$, for all data pairs. 
\end{itemize}
\begin{enumerate}
\item Define $H_0$ by $\forall x \in X, y \in Y \: H_0(x,y) = 1/|Y|$. 
\item Initialize 
$w_{i,y} := C(x_i,H_0(x_i)) - C(x_i,y)$, 
for $i:= 1$ to $m$, and $y \in Y$.
\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$.   
%(Note that this is equivalent to $w_i := B(x_i,y_i) - B(x_i, H_{t-1}(x_i))$.)
\item Let 
$S' = \{ \langle (x_i, y),I(w_{i,y}\geq 0) \rangle | i=1,...,m, 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 Define $h_t$ from $h'_t$ by randomly breaking evens, i.e. 
%\begin{itemize} 
%\item if $|\{ y \in Y | h_t(x,y) = 1 \}| = 0$ then randomly pick $y' \in Y$ 
%and set $h'_t((x,y')) = 1$, and for all other $y \neq y'$, set 
%$h'_t((x,y)) = 0$.
%\item if $|\{ y \in Y | h_t(x,y) = 1 \}| = k > 0$ 
%then randomly pick $y' \in Y$ such that $h_t(x,y') = 1$ and 
%set $h'_t((x,y')) = 1$, and for all other $y \neq y'$ set $h'_t((x,y)) = 0$.
%\end{itemize} 
%\item {\bf If} $- \langle h, \nabla L  \rangle \leq \gamma$ {\bf Then} 
%\begin{enumerate} 
%\item Return $H_{t-1}$. 
%\item {\bf End If} 
%\end{enumerate}
\item Choose $\alpha_t \in [0,1)$. 
%\[ 
%\alpha = \arg \max_{a} - L((1-a)H_{t-1}+ a h_t, S) 
%\]
and set $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 IEB (Iterative Expand Binary)}} 
\label{fig:method2} 
\end{figure}

\begin{theorem}
\label{prop2} 
Suppose that the weak learner $A$ satisfies the weak learning condition, 
namely; 
\begin{equation}
a(h,S') \geq \frac{\sum_{w(x,y)<0} |w(x,y)|}{W} + \gamma
\label{eq:weak2}
\end{equation}
\iffalse
That is, for any weights $w_i$, over $X \times Y$, 
it finds a hypothesis $h$ satisfying 
\begin{equation}
\label{eq:weaklearner2c}
\frac{\sum_{i=1}^{mk} w_i h(x_i,y_i)}{\sum_{i=1}^{mk} w_i} 
\geq \frac{\sum_{i: w_i < 0} w_i}{\sum_{i=1}^{mk} w_i} + \gamma 
\gamma 
\end{equation}
for some positive $\gamma$.  
\fi 
Then, the output of IEB 
will converge to an ensemble hypothesis 
achieving approximately minimal expected cost on the original sample $S$, 
among the class of linear combinations of members of ${\cal H}$. 
In particular, if $T \geq \frac{1}{\gamma \alpha} \log \frac{1}{\epsilon}$, 
\[ 
\sum_x \sum_y H_T(x,y)C(x,y) - 
\min_{H \in LIN({\cal H})} 
\sum_x \sum_y H(x,y)C(x,y)
\leq \epsilon
\]
\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} condition on the original relational multi-class 
classification problem and the {\em weak learning} condition on the 
associated binary classification problem, as defined in 
Definitions~\ref{def:reduction1} and \ref{def:reduction2}. 
\begin{define}
Let $S$ be a weighted sample of the form 
$S = \{ \langle (x,y), w(x,y) \rangle \}$, 
where weights $w(x,y) \in \Re$ can be both 
positive and negative, and $y \in Y$, where $|Y| > 2$. 
The relational weighted multi-class classification problem for $S$ 
is to find a hypothesis $h: X \times Y \rightarrow \{ 0,1 \}$ 
that maximizes the following sum: 
\[
a(h,S) = \frac{\sum_{(x,y) \in S} w(x,y) h(x,y)}{W}
\]
where $W = \sum_{(x,y) \in S} |w(x,y)|$. 
\label{def:reduction1} 
\end{define}
\begin{define}
Given a weighted sample $S = \{ \langle (x,y), w(x,y) \rangle \}$, 
define a transformed sample 
$S' = \{ \langle ((x,y), l(x,y)), |w(x,y)| \rangle \}$ 
by letting $l(x,y) = 1$ if $w(x,y) \geq 0$ and $l(x,y) = 0$ otherwise. 
The weighted binary classification problem for $S'$ (associated with $S$)
is to find a hypothesis $h': X \times Y \rightarrow \{ 0, 1 \}$ 
that maximizes the following weighted classification accuracy: 
\[
a(h',S') = \frac{\sum_{(x,y) \in S'} |w(x,y)| I(h'(x,y) = l(x,y))}{W}
\]
\label{def:reduction2} 
\end{define} 

\begin{lemma} 
Assume the notatation of Definitions~\ref{def:reduction1} and  
\ref{def:reduction2}. 
Then $h$ satisfies the following ``weak learning condition'' 
on the original relational multi-class classification problem for $S$
\begin{equation}
a(h,S) \geq \gamma
\label{eq:weak1}
\end{equation}
if and only if (the same) $h$ satifies the corresponding 
``weak learning condition'' 
on the transformed binary classification problem 
associated with $S$. 
\begin{equation}
a(h,S') \geq \frac{\sum_{w(x,y)<0} |w(x,y)|}{W} + \gamma \nonumber
\end{equation}
\label{lemma:weak}
\end{lemma} 
{\bf Proof of Lemma}
\begin{eqnarray}
& & W \cdot a(h,S') \nonumber \\
& = & \sum_{(x,y) \in S'} |w(x,y)| I(h(x,y) = l(x,y)) \nonumber \\
& = & \sum_{w(x,y) \geq 0} w(x,y) I(h(x,y) = 1) \nonumber \\ 
& & +  \sum_{w(x,y) < 0} - w(x,y) I(h(x,y) = 0) \nonumber \\
& = & \sum_{w(x,y) \geq 0} w(x,y) h(x,y) 
+ \sum_{w(x,y) < 0} - w(x,y) (1 - h(x,y)) \nonumber \\
& = & \sum_{(x,y) \in S} w(x,y) h(x,y)
+ \sum_{w(x,y) < 0} |w(x,y)| \nonumber \\
& = & W \cdot a(h,S) + \sum_{w(x,y) < 0} |w(x,y)| 
\label{eq:lemmaweak}
\end{eqnarray}
Hence the lemma follows. 
{\bf Q.E.D.}

The loss (average cost) incurred by the $t$-th ensemble hypothesis, 
$H_t$, on the expanded sample set can be evaluated as follows. 
(Note that we drop the subscript $t$ from $\alpha_t$.) 
\begin{eqnarray} 
C(H_t) & = & \sum_x \sum_y C(H_t(x,y)) \nonumber \\ 
& = & \sum_x (1 - \alpha) C(x, H_{t-1}(x) + \alpha \sum_y h(x,y)C(x,y) 
\nonumber 
\end{eqnarray} 
Hence, the decrease in the cost $\Delta C(H_t, H_{t-1})$ 
from round $t-1$ to $t$ can be calculated as follows. 
\begin{eqnarray} 
& & -\Delta C(H_t,H_{t-1})\nonumber \\
& = & 
\sum_x \alpha (\sum_y C(x, H_{t-1}(x,y)) - \sum_y h(x,y)C(x,y)) \nonumber \\ 
& = & 
\alpha \sum_x (\sum_{y:h(x,y)=1} h(x,y) (C(x, H_{t-1}(x)) - C(x,y)) \nonumber \\ 
& & + \sum_{y:h(x,y)=0} C(x, H_{t-1}(x))) \nonumber \\ 
& = & 
\alpha \sum_x (\sum_y h(x,y)(C(x, H_{t-1}(x)) - C(x,y)) \nonumber \\ 
& & + \sum_{y:h(x,y)=0} C(x, H_{t-1}(x)))  \nonumber \\ 
& \geq & 
\alpha \gamma \sum_x \sum_y |C(x, H_{t-1}(x)) - C(x,y)| 
\end{eqnarray} 
The last inequality follows from the weak learning condition 
by applying Lemma~\ref{lemma:weak} with weights 
$C(x, H_{t-1}(x)) - C(x,y)$, and the fact that costs are nonnegative.
Noting that the sum of these weights is non-negative and 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 H(x,y) C(x,y)$ is convex (in fact linear), 
guaranteed progress in each iteration implies convergence to the 
global optimum.  Noting that in each iteration, the relative empirical 
cost (with respect to the optimal) is reduced at least by a factor 
of $1 - \gamma \alpha$, and the fact that the expected empirical 
cost on the original sample $S$ (Equation~\ref{eq:expobj}) 
is equal to that on the expanded sample $S'$ (Equasion~\ref{eq:expobj2}), 
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 Equation~\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. 

It is important to note that the output $H_T$ of the procedure described 
above is a mapping from $X \times Y$ to $\{ 0, 1\}$, and this needs to be
converted to a classifier, i.e. a mapping from $X$ to $Y$.  
One obvious way to do this is to choose that $y$ that is given the 
maximum value by $H_T$ for each $x$.  We can quantify how well the 
resulting hypothesis works in the realizable case, namely assuming that 
the optimal labeling of the training data can be realized by the 
class of linear combinations of the given hypothesis class.
\begin{corollary} 
Define a modified version of IEB in which the final hypothesis 
$H_T$ is translated to a deterministic mapping $H'_T: X \rightarrow Y$ by 
\[ 
H'_T(x) = \arg \max H_T(x,y) 
\]  
Then, in the realizable case, i.e. when the class of linear combinations 
of ${\cal H}$, written $LIN({\cal H})$, contains a member $h^*$ 
which attains the minimum cost on the input sample, 
with the same weak learning condition as in Theorem~\ref{prop2}, 
the modified version will approximately minimize the empirical cost 
on the original sample $S$, namely as $T$ tends to infinity, we have 
\[ 
\sum_{x_i \in S} C(x,H'_T(x)) \approx
\min_{H \in LIN({\cal H})} \sum_{x_i \in S} C(x_i,H(x_i))
\]
\end{corollary} 
{\bf Proof} 
In the realizable case, the optimal relational 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 $H'_T$ is 
identical to $H_t$, and it equals the optimal functional hypothesis. 
Hence the corollary follows from Theorem~\ref{prop2}.
{\bf Q.E.D.} 

\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}{|Y|}\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} 

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 in the MetaCost paper \cite{Domingos}. 

We compare our methods against three different methods:
\begin{itemize}
\item Bagging: standard bagging, ignoring costs.
\item Averaging cost:
\item MetaCost: 
\end{itemize}

The methods were applied to five benchmark datasets available from the UCI machine learning 
repository \cite{UCI-ML} and one dataset from the UCI KDD archive \cite{UCI-KDD}. 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. 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. Our cost model is 
as follows:

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$. 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 
$C(y_1,y_2)$, $y_1 \neq y_2$ with uniform probability from the interval $0,2000 P(y_1)/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.

Domingos, instead, 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 
give an unfair advantage to cost-sensitive methods over cost-insensitive ones. 

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.


\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}

\bibliography{blindformat}
\bibliographystyle{mlapa}

\end{document} 
