\documentclass[12pt]{llncs}
\newcommand{\shrink}[1]{}
\def\blackslug
     {\hbox{\hskip 1pt\vrule width 5pt height 8pt depth 1.5pt\hskip 1pt}}
\def\qed{\hfill\quad\blackslug\lower 8.5pt\null\par}
\newcommand{\dt}{{\mathrm{d}t}}

%\usepackage[T1]{fontenc}
%\usepackage[latin1]{inputenc}
\usepackage{graphicx,latexsym,amsmath,amssymb,pstricks}

\makeatletter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
 \numberwithin{equation}{section} %% Comment out for sequentially-numbered
 \numberwithin{figure}{section} %% Comment out for sequentially-numbered

\DeclareMathOperator*{\Exp}{E}

%\addtolength{\textwidth}{3.0in}
%\addtolength{\oddsidemargin}{-1.7in}
%\addtolength{\evensidemargin}{-1.5in}

\textwidth=15cm
\hoffset=-1.3cm
\textheight=8.5in %20cm
\voffset=0cm 

\renewcommand{\baselinestretch}{0.95}
%\usepackage{babel}
%\makeatother
\begin{document}

\title{Reductions Between Classification Tasks}

\author{Alina Beygelzimer$^1$ \and Varsha Dani$^2$ \and Tom Hayes$^3$ \and John Langford$^3$ \and \\ Bianca Zadrozny$^1$}
\institute{IBM TJ Watson \and University of Chicago \and TTI-Chicago}

\maketitle

\begin{abstract}
A reduction converts a solver for one task into a solver for another
task. We introduce a notion of reduction and analyze reductions
between different classification tasks.
\end{abstract}

\section{Introduction}
There are many natural supervised learning tasks; even classification
comes in a variety of different forms (binary, multiclass, cost
sensitive, importance weighted, etc.) There are two approaches that
one can take: One is to analyze all tasks independently and produce
algorithms for each.  The other approach is to use reductions to
convert new, unexplored tasks to tasks that have been thoroughly
analyzed, automatically transferring existing theory and algorithms
from well-understood domains into new domains.  We investigate the
latter approach for classification problems.  Reductions present a
powerful tool with a number of desirable properties:
\begin{enumerate}
\item
They show how similar different tasks are.
If two tasks are reducible to one another, it is reasonable to say
that they are similar, modulo the efficiency of the reduction.
The more efficient the reduction, the stronger the statement.
\item
If task $A$ can be reduced to task $B$, then techniques
for solving $B$ can be used to solve $A$, transfering
results from one learning domain to another.
\item
Reductions help to extend existing theories to new domains.
\end{enumerate}

In addition to the above theoretical motivations, there appears to
be some significant empirical evidence (see \cite{costing},
\cite{Boosting}, \cite{ECOC}) that this style of analysis often produces
learning algorithms that perform well in practice.

We present the basic definitions of our theoretical model, and cast
known reductions in this framework. We then present several
new reductions along with experimental results suggesting that analysis
in this model is predictive of performance on real-world problems.

\section{Basic Definitions}\label{defi}
\begin{definition}
A \emph{supervised learning task} is a tuple $(K,Y,l)$, where $K$ is
the information available at training time, $Y$ is the space of
predictions, and $l:K\times Y\rightarrow[0,\infty)$ is a loss function.
\end{definition}
%A task is (implicitly) a set of learning problems, each of which
%requires more information to be fully specified.  
We instantiate several tasks in the table below to give some intuition.

\begin{center}
\renewcommand{\arraystretch}{1.1}
\begin{tabular}{|c|c|c|c|}
\hline
Classification Task&
$K$&
$Y$&
$l$ \\
\hline
Binary &
$\{0,1\}$ &
$\{0,1\}$ &
$I(k \neq y)$ \\
\hline
Multiclass &
$\{1,\ldots,r\}$ &
$\{1,\ldots,r\}$ &
$I(k \neq y)$ \\
\hline
\hskip .1in Importance Weighted \hskip .1in &
$\,\{1,\ldots,r\} \times [0,\infty)\,$ &
$\,\{1,\ldots,r\}\,$ &
$\,k_2 I(k_1 \neq y)\,$ \\
\hline
Subset &
$2^{\{1,\ldots,r\}}$ &
$\{1,\ldots,r\}$ &
$I(y \not \in k)$
\tabularnewline
\hline
Cost Sensitive &
$[0,\infty)^r$ &
$\{1,\ldots,r\}$ &
$k_y$
\tabularnewline
\hline
\end{tabular}
\end{center}
Note that we have separated $K$, the information provided at training
time, from the prediction space $Y$. In some cases we indeed need this
additional flexibility (also used in \cite{Haussler}) to provide some
information to the learning algorithm about the loss of different
choices.  In importance weighted classification, for example, we want
to specify that predicting some classes correctly is more important
than predicting others, while in cost sensitive classification, $K$ is
used to give a varying value to each example.  In subset
classification, $K$ is the subset of correct predictions. 

A task is (implicitly) a set of learning problems, each of which
requires more information to be fully specified. 
\begin{definition}
A \emph{supervised learning problem} is a tuple $(D,X,K,Y,l)$, where $(K,Y,l)$
is a supervised learning task, $X$ is an arbitrary feature space, and
$D$ is a distribution over $X\times K$.
\end{definition}
The goal in solving a supervised learning problem is to find a hypothesis
$h:X\rightarrow Y$ minimizing the expected loss
$E_{(x,k)\sim D}l(k,h(x))$.  For any particular
hypothesis $h$, the loss rate $h_D = E_{(x,k) \sim D} l(k,h(x))$ is a
fundamental quantity of interest.  Finding $h$ is difficult because we
do \emph{not} assume that $D$ is known at training time.

\begin{definition}
A \emph{supervised learning algorithm for task $(K,Y,l)$} 
is a procedure mapping any finite set of examples $(X\times K)^m$ to a
hypothesis $h:X\rightarrow Y$.
\footnote{Note that we do not require
the learned hypothesis to belong to some predetermined class of
hypotheses $H$; this is unnecessary.  Of course,
such an $H$ exists implicitly as the set of all possible outputs of $A$.} 
\end{definition}
Standard supervised learning algorithms such as support vector
machines, neural networks, decision trees, and logistic regression fit
this definition.\footnote{Note, however, that these algorithms do not
actually work for {\it all} learning problems in their task since they
do not work for all input spaces.  We assume that our idealized
supervised learning algorithm does.}

\subsection{Reductions}
A reduction solves problems in one learning task using blackbox access
to a solver for another task.  We are interested in reductions that
perform well whenever the solver performs well, so a reduction must
map problems in one task to problems in another.  To define a
reduction, we must define this mapping from a \emph{measure} $D$ over
original examples in $X\times K$ to a \emph{measure} $D'$ over
generated examples in $X'\times K'$.

The reduction gets as input a set of examples $S$ drawn from $D$.
This set $S$ induces a measure $D_S$ over $X'\times K'$ defined by:
$$D_S(x',k')=E_{S' \sim S}\frac{\#(x',k')}{|S'|},$$ where the
expectation is over all possible sets of examples $S'$ generated by the
reduction\footnote{Note that the reduction can be randomized and the
expectation occurs over that randomization.} on input $S$, and $\#(x',k')$
is the number of times $(x',k')$ appears in $S'$.  The induced measure
$D'=E_{S\sim D}D_S$ is then defined by taking an expectation over
sets $S$ generated by $D$. 

This defines $D'$ for a single invocation of the oracle.  If the
reduction makes several sequential calls, we need to define $D'$ for
each invocation.  Suppose that the first invocation produces $h$. We
replace this invocation with the oracle that always returns $h$, and
use the above definition to find $D'$ for the consequent invocation.

We can now state the formal definition.

\begin{definition}\label{reduction-definition}
A \emph{supervised learning reduction from task
$(K,Y,l)$ to task $(K',Y',l')$} is a learning algorithm $A$ for $(K,Y,l)$
that has oracle access to a learning algorithm $A'$ for $(K',Y',l')$.
The algorithm $A$ must satisfy the following property for all $X$ 
and for all distributions $D$ over $X\times K$:

\vskip .05in \noindent
Given a set of examples $S$ drawn from $D$, let $h$ be 
the hypothesis output by $A$ on $S$, and let $h'_{D'}$ be the maximum 
loss rate over all hypotheses
output by $A'$ on inputs generated by the reduction (where $D'$ is
the corresponding induced measure on $X'\times K'$). Then
$$h_D \leq g( h'_{D'}),$$ 
for a continuous monotone nondecreasing
function $g: [0,\infty)\rightarrow [0,\infty)$ with $g(0)=0$.
\end{definition}
\noindent
Note that none of the above definitions require that examples be drawn
IID.  Analysis in this model is therefore directly applicable to many
real-world problems.

\bigskip\noindent This definition is analogous to a ``Turing
reduction'' in complexity theory. In both cases a reduction from
problem $A$ to problem $B$ is a procedure that solves $A$ using a
solver for $B$ as a black box.  One critical difference is that in
complexity theory reductions are typically viewed as tools for
classifying relative hardness of problems (since proving lower bounds
on any \emph{explicit} problem is notoriously hard).  If $A$ reduces
to $B$, it is interpreted as ``$B$ is at least as hard as $A$''.  In
machine learning, reductions are viewed as constructive tools for
reusing algorithms for one problem to solve another (showing that $A$
is no harder than $B$).  Also, learning reductions defined here are
\emph{informational} rather than \emph{computational}, i.e., the
hardness of solving a learning problem is due to the lack of {\it
information} (in particular $D$, which defines the optimal solution,
is unknown) rather than the computational power available to the
algorithm.  Notice that this definition does not necessarily force the
reduction to use $A'$ in a nontrivial way. Some learning tasks may be
(near) optimally solvable, so the reduction may never need to invoke
the oracle.

\subsection{Properties of Reductions}
In a new theoretical model, it is important to show that there exists enough
structure to warrant meaningful results. 
First, it is easy to see that reductions compose.

\begin{proposition}(Reduction Composition)
If $R_{12}$ is a reduction from task ${\cal D}_1$ to ${\cal D}_2$
with error limitation $g_{12}$ and $R_{23}$ is a reduction from task
${\cal D}_2$ to ${\cal D}_3$ with error limitation $g_{23}$, then the
composition $R_{12}\circ R_{23}$ is a reduction from ${\cal D}_1$ to
${\cal D}_3$ with error limitation $g_{12} \circ g_{23}$.
\end{proposition}
\begin{proof}
Given oracle access to any learning algorithm $A$ for ${\cal D}_3$,
reduction $R_{23}$ yields a learning algorithm for ${\cal D}_2$ such that for
any $X_2$ and $D_2$, it produces a hypothesis with loss rate 
$h'_{D_2} \leq g_{23}(h''_{D_3})$,
where 
$h''_{D_3}$ is the maximum loss rate 
of a hypothesis $h''$ output by $A$ (over all invocations).
We also know that $R_{12}$ yields a
learning algorithm for ${\cal D}_1$ such that for all $X_1$ and $D_1$ we have:
$$h_{D_1}\leq g_{12}(h'_{D_2}) \leq
g_{12}(g_{23}(h''_{D_3}),$$ where $h'_{D_2}$ is the maximum
loss rate of a hypothesis $h'$ output by $R_{23}(A)$.
Finally, notice that $g_{12}\circ g_{23}$ is continuous, monotone
nondecreasing, and $g_{12}(g_{23}(0))=0$.
\qed
\end{proof}

\subsubsection*{Efficiency}\label{sec:call}\quad If two
tasks are reducible, it is reasonable to say that they are equivalent,
\emph{modulo the complexity of the reduction}.  The more restrictive
the reduction, the stronger the statement.  We consider several forms of
efficiency.

\vskip .05in \noindent {\em Error Efficiency} of a reduction
\emph{for a given example} is defined as the maximum ratio
of the loss of the hypothesis output by the reduction on this example
and the total loss of the oracle hypotheses on the examples generated
by the reduction.

\vskip .05in \noindent {\em Time Efficiency} \quad
We want the transformation to be computationally
efficient assuming that all oracle calls take unit time.

\vskip .05in \noindent {\em Call efficiency} \quad
We quantify how extensively a reduction uses its oracle based on (1)
the number of oracle calls it makes; (2) whether the calls are
adaptive (i.e., depend on the answers to previous queries) or parallel
(i.e., all queries can be asked before any of them is answered); (3) 
the maximum expected number of examples input to the oracle.

\vskip .05in \noindent Note that parallel calls to the oracle can be
turned into a single call.  Suppose that we make several parallel
queries to the oracle. Let $\{S_i\}$ be the corresponding inputs
(i.e., representing sample sets over the same feature space $X$), and
let the corresponding hypotheses be $\{h_i\}$.  We could instead
create a new sample set $S = \{ (\langle x,i\rangle,k) : \langle
x,k\rangle \in S_i \}$, call the oracle on $S$ to get a hypothesis
$h$, and define $h_i(x) = h(\langle x,i\rangle)$.

\vskip .05in \noindent {\em Independence Preservation}\quad Many common
learning algorithms are built under the assumption that examples are
drawn independently from some distribution $D'$.  Reductions which
take an independently drawn dataset, and construct dependent datasets
for the oracle learning algorithm are often undesirable for this
reason.

\begin{definition} \quad A reduction $R$ from
$(Y,K,l)$ to $(Y',K',l')$ is \emph{learning preserving} if there
exists a reduction $R'$ from $(Y',K',l')$ back to $(Y,K,l)$ such that
for every distribution $D'$ over $X'\times K'$ and every oracle $A'$ for 
$(Y',K',l')$, if $A'$ has loss rate $\epsilon$ with respect to 
$D'$, then $R'(R(A'))$ also has loss rate $\epsilon$ with respect to $D'$.
\end{definition}

\noindent
Definition~\ref{reduction-definition} and reduction composition do not
generally imply that a reduction is learning preserving.
For all distributions $D'$ and all oracles $A'$,
the loss rate of the double reduction $R'(R(A'))$ on $D'$ is bounded
in terms of the loss rate of the oracle $R(A')$ on the \emph{induced} (by
$R'$ on $D'$) distribution $D''$,
which is in turn bounded by the loss rate of the
oracle $A'$ on the \emph{induced} (now by $R$ on $D''$) distribution $D'''$.
A reduction is {\em learning preserving} if the 
loss rate of the double reduction $R'(R(A'))$ on $D'$ is the same
as the loss rate of $A'$ on the \emph{same} distribution $D'$ (not the
induced $D'''$). In general, good performance on $D'''$ says nothing about
good performance on $D'$.
Intuitively, a learning preserving reduction does not reduce
easy problems to hard queries for the oracle. 


\shrink{%--john's paragraph
The distribution $D$ induces a
distribution $D'$ on $R(A')$ via $R'$ which further induces a
distribution $D''$ on $A$.  However,
Definition~\ref{reduction-definition} does \emph{not} generally imply
that $D'' = D$, even though these distributions have the same tasks.
% alina: but D'' does not have to be equal to D for the loss rate to be the same
In general, good performance on $D$ says nothing about good
performance with respect to $D''$.
% alina: good performance on D'' says nothing about D not vice versa.
}

Theorem~\ref{preserving} in the Appendix gives a reduction which 
achieves the learning preserving property.

\section{Prior Work on Reductions}
Many people have worked on reductions in learning.  One of our goals
is a unification of these algorithms in a common framework and
distillation of best practices.

Boosting algorithms \cite{Boosting,noise_boost} are reductions from binary
(sometimes multiclass) classification with a small error rate to
importance weighted classification with a loss rate of nearly
$\frac{1}{2}$, a rather surprising capability.

Bagging \cite{Bagging} can be seen as a self-reduction of
classification to classification. Bagging turns learning algorithms
with high ``variance'' (i.e., dependence on the exact examples seen)
into voting classifiers with lower ``variance''.  Bagging performance
sometimes suffers because the examples that fed into the classifier
learning algorithm are not necessarily independently distributed
according to the original distribution.

Error Correcting Output Codes (ECOC)~\cite{ECOC} are a generalization
of the tree reduction \cite{Tree} and the one-against-all reduction
\cite{One-vs-all} used for solving multiclass classification given a
solver for binary classification.

The ``Costing'' algorithm \cite{costing} is a reduction of importance
weighted classification to classification.

Pitt and Warmuth \cite{PW} also introduced a form of
a reduction between classification problems called
\emph{prediction-preserving reducibility}.  The reductions presented
here differ in several respects: (1) they are between arbitrary learning
\emph{tasks} rather than between restricted sets of classification problems;
(2) they are representation independent; (3) prediction-preserving
reducibility is a \emph{computational} notion, while the reductions
here are \emph{informational}; (4) prediction-preserving reductions
make only one call to the oracle (i.e., problem they reduce to) and
output the oracle's answer as its own answer. We enforce no
restriction on how the oracle is used, making the setting directly
applicable to ECOC, Boosting, and other common
transformations\footnote{Abe and Watanabe~\cite{naoki} defined a
Turing analogue of the prediction preserving reducibility, and showed
that new reductions are feasible in this setting.}; (5)
prediction-preserving reductions are typically used to show negative,
{\it non}predictability results, while we show positive results
transferring learning algorithms between tasks.

We include a table of results and refer to the Appendix for details.

\begin{center}
\renewcommand{\arraystretch}{1.1}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
Name&    $g(\epsilon)$& %               Learn Preserve& 
Time& \#Calls& Indep. Preserve
\tabularnewline
\hline
Costing& $\epsilon$& %                          Yes& 
$O(Tm)$& $T$ parallel& Yes
\tabularnewline
\hline
1-vs-all& $(r - 1) \epsilon$& %                 No&
$O(|S| r)$&$r$ parallel& Yes
\tabularnewline
\hline
Tree& $\epsilon \log_2 r$& %                   Yes& 
$O(|S| r)$&\hskip .05in $r - 1$ parallel \hskip .1in & Yes
\tabularnewline
\hline
ECOC& $4 \epsilon $& %                          No& 
$O(r|S|)$& $2 r$ parallel&  Yes
\tabularnewline
\hline
\end{tabular}
\end{center}

\section{Reducing To Importance Weighted Binary Classification}

In this section we analyze reductions to importance weighted binary
classification.  The ``Costing'' reduction from importance weighted
classification to classification composes to produce new (or
alternative) reductions to binary classification.

\subsection{From Subset Classification: Weighted One-against-all}
In this section we present a weighted one-against-all 
reduction from subset classification to importance 
weighted binary classification. It appears to be new.

Recall that a training example in subset classification is labeled 
by some subset $Q$ of $r$ possible labels.  The reduction maps each example
$(x,Q)$, $|Q|=n\leq r$, to $r$ examples in the form: 
$$(\langle x,y\rangle, I(y\in Q),i_{I(y\in Q)}) \ \, \mbox{for}\ y\in
\{1,\ldots,r\},$$ where $i_{0}=\frac{r}{n+1}$, and
$i_{1}=\frac{r}{n+1}$ if $r\leq n^{2}+n$, otherwise
$i_{1}=\frac{r-n}{n}$.  The oracle uses these examples to construct a
binary classifier $h$.  To construct a subset classifier from $h$, we
do the following: If there exists a label $y \in \{1,\ldots,r\}$ such
that $h(\langle x,y \rangle )=1$, then predict $y$, breaking ties
randomly; predict randomly otherwise.

Next, we prove an error rate transformation bound.
\begin{theorem}\label{thm:subset}
{\em (Error Efficiency of Subset Classification)} Let $c(r,n)=
\frac{r}{n+1}$ if $r\leq n^{2}+n$, otherwise $c(r,n)=
\frac{r+1}{n+1}-\frac{n}{r}$.  For any input space $X$ and distribution $D$ over
$X\times 2^{\{1,\ldots,r\}}$, if the binary classifier 
has a normalized loss rate $\epsilon$ (on the induced distribution), 
then the weighted
one-against-all reduction has loss rate at most\[ \epsilon
E_{(x,Q)\sim D}c(r,n).\]
\end{theorem}
The proof of this theorem is deferred to the appendix.

This theorem should be compared directly with the one-against-all
reduction to binary classification which has error efficiency of
$r-1$. Here, with $n=1$, we get 
$c(r,n)=\frac{r+1}{2}-\frac{1}{r}=\frac{(r+2)(r-1)}{2r}$
implying error efficiency of about $\frac{r}{2}$, or about half
the loss rate of the earlier reduction. 

\begin{figure}[t]
\begin{center}
\rotatebox{270}{\includegraphics[scale=0.75]{combined.ps}}
\caption{\label{fig:acc} A figure showing comparative performance of
the weighted-one-against-all reduction (+ costing) and the
one-against-all reduction on several multiclass datasets with Boosted
Naive Bayes (BNB) and Support Vector Machine (SVM) classifiers.  Note
that for these experimens we used $r$ classifiers rather than $1$ as
in the theorem.}
\end{center}
\end{figure}
                                                                                
We tested the reduction on several UCI multiclass datasets using
Boosted Naive Bayes and linear SVM as the oracle learning algorithms
and obtained the average test set error rates shown in figure
\ref{fig:acc}.  From these results, we see that there is a consistent
benefit to using this reduction over the simple one-against-all
reduction. 

\subsection{From Cost-Sensitive Classification: Weighted All-pairs}

We reduce (multiclass) cost-sensitive classification to importance
weighted (binary) classification using maps of the form
\[
(x, k_1, \dots, k_r) \mapsto ((x,i,j), I(k_i < k_j), v_j - v_i),
\]
for all pairs $(i,j)$ with $i < j$.  The values $v_1, \dots, v_r$ are
functions of $k_1, \dots k_r$ defined below.  The values are
order-preserving (for all $i,j$, $k_i < k_j$ iff $v_i < v_j$).

Given $m$ samples of training data for a cost sensitive problem, we
generate $m \binom{r}{2}$ training inputs for an importance weighted
problem, by iterating through all $\binom{r}{2}$ possibilities for $i$
and $j$.  Now we use our oracle and this training data to generate a
classifier, $h$.  Given an input $x$ for the cost sensitive problem,
we evaluate $h(x,i,j)$, for all the $\binom{r}{2}$ pairs $i,j \in
[r]$, with $i< j$.  Say label $i$ ``beats'' label $j$ for input $x$ if
either $i< j$ and $h(x,i,j) = 1$, or $i > j$ and $h(x,j,i) = 0$.  Note
that, if our classifier makes no errors and $k_i \ne k_j$, then label
$i$ beats label $j$ exactly when $k_i < k_j$ (we will not be concerned
with the case $k_i = k_j$).  Our algorithm outputs a label $i$ which
beats the maximum number of labels $j \ne i$.  The mechanism for
breaking ties will not affect our main result.

The values $v_i$ can be defined in either of two equivalent ways.
The first is
\[
v_i = \int_{0}^{k_i} 1/L(t) \mbox{\emph{dt}},
\]
where $L(t) = \# \{j \mid k_j < t\}$.  (This form assumes
the minimum cost $k_{\min} = 0$.)

This method of assigning importances is nearly optimal.
\begin{theorem}\label{thm:CSCtoIW}
If the IW binary classifier has loss rate at most $\epsilon$,
then the CS classifier defined by the above reduction has
expected cost at most $2\epsilon$.  Moreover, for any
other assignments of importances $w_{i,j}$ to the sample
points $(x,i,j)$ in the above algorithm, there exists a
distribution with expected cost at least $\epsilon/2$.
\end{theorem}
The following observation is helpful in the proof:
\begin{lemma}\label{lem:crossings}
Suppose label $i$ is the winner.  Then, for every $j \in \{1, \ldots,
i-1\}$, there must be at least $\lceil j/2 \rceil$ pairs $(a,b)$,
where $a \le j < b$, and $b$ beats $a$.
\end{lemma}

\begin{proof}[of Lemma~\ref{lem:crossings}]
Let $a$ be the winner of the tournament on $\{1, \dots, j\}$.  

\par\noindent {\bf Case 1:} Suppose some $a$ beats at least $\lceil
j/2 \rceil$ of the others.  If no label $b > j$ beat any label $c \le
j$, then $a$ would beat at least $\lceil j/2 \rceil + 1$ more labels
than any $b > j$.  Thus, in order to have label $b > j$ beat as many
labels as $a$, at least $\lceil j/2 \rceil$ edges of the form $(a,c)$
or $(d,b)$ must be reversed.

\par\noindent{\bf Case 2:} There is no label $a \in \{1, \dots, j\}$
beating $\lceil j/2 \rceil$ of the rest of $\{1, \dots, j\}$.  There
must be a $j$-way tie with $(j-1)/2$ losses per label in
$\{1,\ldots,j\}$.  In this case, although every label beats $(j+1)/2$
more labels than any $b > j$, it is still necessary to reverse at
least $(j+1)/2 \ge \lceil j/2 \rceil$ edges, in order to ensure that
some $b > j$ beats as many labels as each of $\{1, \dots, j\}$.  \qed
\end{proof}
\begin{proof}[of Theorem~\ref{thm:CSCtoIW}]
For a particular input $(x, k_1, \dots, k_r)$,
suppose our algorithm chooses the wrong label.
We will show that this requires the classifier
to incur a comparable loss.
For notational simplicity, assume
$k_1 \le \dots \le k_r$ and that our algorithm
chooses label $i > 1$.  

Lemma~\ref{lem:crossings} and the definition of $v_i$, imply the
penalty incurred to make label $i$ win is at least:
\[
\int_{0}^{k_i} \frac{\left\lceil L(t) / 2 \right\rceil}{L(t)} \dt
\ge \int_{0}^{k_i} \frac12 \dt = \frac{k_i}{2}.
\]
On the other hand, the total importance assigned to queries for this
instance equals:
\[
\sum_{i<j} v_j - v_i = \sum_{i<j} \int_{k_i}^{k_j} \frac{1}{L(t)}\dt 
= \int_{0}^{k_r} \frac{L(t) R(t)}{L(t)} \dt
= \int_{0}^{k_r} R(t) \dt = \sum_{i=1}^{r} \int_0^{k_i} \dt = \sum_{i=1}^{r} k_i,
\]
where $R(t) = r - L(t)$ is the number of labels whose value is greater
than $t$ and the second equality follows from switching the order of
summation and counting the number of time a pair $(i,j)$ satisfies
$i<t<j$.  The second to last inequality follows from the definition of
$R(t)$.

Consequently, for every example $(x,k_1,\ldots,k_r)$, the total
importance assigned to queries for $x$ equals $\sum_i k_i$, and the
cost incurred by our algorithm on instance $x$ is at most twice the
importance of errors made by the binary classifier on instance $x$.
Averaging over the choice of $x$ shows that the cost of the reduction
is at most $2$.

For the lower bound, consider examples $\left(x,0,\frac{1}{r-1},\ldots,\frac{1}{r-1} \right)$.
Suppose we run our algorithm, using some $w_{i,j}$ as the importance
for the query $(x,i,j)$.  Any classifier which errs on $(x,1,i)$ and
$(x,1,j)$, where $i \ne j$, causes our algorithm to choose label $2$
as the winner, thereby giving a cost of $1/(r-1)$, out of a total cost
of $1$.  The importance of these two errors is $w_{1,i} + w_{1,j}$,
out of a total importance of $\sum_{i,j} w_{i,j}$.  Choosing $i, j$ so
that $w_{1,i} + w_{1,j}$ is minimal, the adversary's penalty is at
most $2 \sum_{i=2}^r w_{1,i}/(r-1)$, and hence less than $2/(r-1)$
times the total importance for $x$.  This shows that the cost of the
reduction cannot be reduced below $1/2$ merely by improving the choice
of weights.  \qed
\end{proof}

We did experiments comparing the weighted all-pairs reduction to the original all-pairs reduction 
\cite{All-pairs} (which ignores the costs) and to a state-of-the-art multi-class 
cost-sensitive learning algorithm called MetaCost \cite{MetaCost}. We used 
boosted Naive Bayes as the oracle classifier learner and applied the methods to five 
UCI multiclass datasets. Since these datasets do not have costs associated 
with them, we generated artificial costs in the same manner that was done in the MetaCost 
paper (except that we fixed the cost of classifying correctly at zero). We repeated the experiments 
for 20 different settings of the costs. The average and standard error of the test 
set costs obtained with each method are shown in table \ref{table:cost-results}.

\begin{table}
\begin{center}
\begin{tabular}{|l|c|c|c|c|}
\hline
Dataset & All-Pairs & MetaCost & Weighted All-Pairs v.1 & Weighted All-Pairs v.2 \\ \hline
splice & 59.8 $\pm$ 24   & 49.8 $\pm$ 3.05   & 197 $\pm$ 23     & 46.5 $\pm$ 3.5 \\
solar  & 3989 $\pm$ 1415 & 5317 $\pm$ 390   & 24.7 $\pm$ 2.0   & 36.8 $\pm$ 11 \\  
anneal & 310 $\pm$ 205   & 207 $\pm$ 43    & 29.9 $\pm$ 3.0   & 164 $\pm$ 43 \\ 
kdd-99 & 234 $\pm$ 62    & 49.4 $\pm$ 9.3 & 0.956 $\pm$ 0.12 & 1.76 $\pm$ 0.66 \\
satellite & 137 $\pm$ 33 & 104 $\pm$ 6.4  & 428 $\pm$ 21  & 148 $\pm$ 8.5 \\  \hline
\end{tabular}
\label{table:cost-results}
\caption{Results comparing the performance
of the weighted all-pairs reduction with the original all-pairs reduction 
and MetaCost on five UCI datasets (with artificial costs).}
\end{center}
\end{table}

We present results for two versions of this reduction. One is the
exact version used in the proof above. In the other version,
we learn one classifier per pair as is done in the original all-pairs
reduction. More specifically, for each $i$ and $j$ (with $i<j$) we
learn a classifier using the following mapping to generate training
examples:
\[
(x, k_1, \dots, k_r) \mapsto (x, I(k_i < k_j), |v_i - v_j|).
\] 
In the results, we see that the first version appears to works well
for some problems and badly for others, while the second version is
more stable. This is probably caused by the fact that we make some
problems more difficult for the classifier learner by bundling
examples from different pairs together, while making other problems
easier. Also, the training examples given to the learner in the first
version are not drawn IID from a fixed distribution as learning
algorithms often expect.

\section{Conclusion}
The table below summarizes the reductions presented in the paper.
\begin{center}
\renewcommand{\arraystretch}{1.1}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
Name&    $g(\epsilon)$& %  Learn Preserve&  
Time&   Call&  Indep. Preserve
\tabularnewline
\hline
weighted 1-vs-all&$\frac{r}{n+1} \epsilon$ & % No& 
$O(|S| r)$& $1$ &No
\tabularnewline
\hline
weighted all-pairs& $\epsilon$& % ??& 
$O(r^2)$& $1$ & No
\tabularnewline
\hline
\end{tabular}
\end{center}
Our experiments often worked with a variant of the above reductions
where we used a seperate classifier for each pair (in the weighted all
pairs) or label (in the weighted one-against-all).  The theoretical
impact of this design choice is that we gain independence
preservation, but the error transformation $g(\epsilon)$ only holds
when each classifier has the same (normalized) weight.

The definition of a reduction we outline here covers a
variety of existing supervised learning algorithms. 
The analysis of error limitation for
these reductions suggests improved reductions, which appear to have
superior empirical performance.

There are many open problems remaining.  We do not yet have the most
efficient reductions between the tasks analyzed in this paper.
There are new natural tasks not discussed here which need to be
formalized and connected via reductions.

Our definition of a reduction is limited to the supervised learning
task. It nonetheless appears that a natural generalization capturing
even broader tasks is possible.

\begin{thebibliography}{15}
\bibitem{naoki}Naoki Abe and Osamu Watanabe. Polynomially Sparse Variations and Reducibility among Prediction Problems, 
{\em IEICE Transactions on Communications, Electronics, Information, and Systems}, E75-D(4):449--458, 1992.
\bibitem{ASS}Erin Allwein, Robert Schapire, Yoram Singer. Reducing
Multiclass to Binary: A Unifying Approach for Margin Classifiers,
{\em Journal of Machine Learning Research}, 1:113--141, September 2001.
\bibitem{Bagging}Leo Breiman. Bagging predictors, 
{\em Machine Learning}, 26(2):123--140, 1996.
\bibitem{ECOC}Thomas G. Dietterich and Ghulum Bakiri. Solving
Multiclass Learning Problems via Error-correcting Output Codes,
{\em Journal of Artificial Intelligence Research}, 2:263--286, January 1995.
\bibitem{MetaCost}Pedro Domingos. Metacost: A general method for make classifiers cost sensitive. 
{\em Proceedings of the Fifth International Conference on Knowledge Discovery and Data Mining}, 
pages 155-164.  ACM Press, 1999.
\bibitem{Boosting}Yoav Freund and Robert E. Schapire. 
A decision-theoretic generalization
of on-line learning and an application to boosting. {\em Journal of Computer
and System Sciences}, 55(1):119--139, 1997.
\bibitem{Tree}John Fox. {\em Applied Regression Analysis, Linear Models, and Related Methods}, Sage Publications, 1997.
\bibitem{Guruswami}Venkatesan Guruswami and Amit Sahai. Multiclass Learning,
Boosting, and Error-correcting codes, {\em Proceedings of the 12th Annual Conference on Computational Learning Theory (COLT)}, 145--155, 1999.
\bibitem{All-pairs}Trevor Hastie and Robert Tibshirani. 
Classification by pairwise
coupling. {\em Proceedings of the 1997 Conference on 
Advances in Neural Information Processing Systems}, 507--513, MIT
Press, 1998.
\bibitem{Haussler}David Haussler. Decision Theoretic Generalizations
of the PAC Model for Neural Net and Other Learning Applications,
{\em Information and Computation}, 100:78--150, September 1992.
\bibitem{noise_boost}Adam Kalai and Rocco Servedio. 
Boosting in the Presence of Noise, {\em
Proceedings of the 35th Annual ACM Symposium
on the Theory of Computing (STOC)}, 195--205, 2003.
\bibitem{PW}Lenny Pitt and Manfred Warmuth. Prediction-Preserving
Reducibility, {\em Journal of Computer and System Sciences}, 41:430--467,
1990.
\bibitem{One-vs-all} Ryan Rifkin and Aldebaro Klautau. In Defense of One-Vs-All
Classification, {\em Journal of Machine Learning Research}, 5:101--141, 2004.
\bibitem{adaboost.m2}Robert E. Schapire and Yoram Singer. Improved
boosting algorithms using confidence-rated predictions. {\em Machine
Learning}, 37(3):297--336, 1999.
\bibitem{adaboost.oc}Robert E. Schapire. Using output codes to boost
multiclass learning problems, {\em Proceedings of
the Fourteenth International Conference on Machine Learning (ICML)}, 313--321,
1997.
\bibitem{costing}Bianca Zadrozny, John Langford, and Naoki Abe. Cost
Sensitive Learning by Cost-Proportionate Example Weighting, {\em Proceedings of
the 3rd IEEE International Conference on Data Mining (ICDM)}, 2003.
\end{thebibliography}

\appendix
\section{Easy Directions}
                                                                                
The learning tasks we consider have an ``easy'' direction for
reduction related to whether a particular task is definable as a
subset of another task.
For example, solving binary classification with importance weighted
binary classification is easy, because importance weighted binary
classification with $k_2=1$ is identical to binary
classification. Figure \ref{fig:easy} shows the easy direction for
these reductions.
                                                                                
\begin{center}
\vskip -.2in
\begin{figure}
\begin{pspicture}(15,3)
%\put(0,0){\framebox(15,3)[cc]{}}
\put(1,1){\framebox(1.9,.9)[cc]{Binary}}
\rput(2.9,1.9){\psline{->}(1.6,.4)}
\rput(2.9,1){\psline{->}(2.1,-.3)}
\put(4.5,2){\framebox(2.1,.9)[cc]{Multiclass}}
\rput(6.6,2.45){\psline{->}(1.9,0)}
\put(8.5,2){\framebox(1.9,.9)[cc]{Subset}}
\rput(10.4,2.3){\psline{->}(1.6,-.4)}
\put(5,.5){\framebox(5,.9)[cc]{Importance Weighted Binary}}
\rput(10,.7){\psline{->}(2,.3)}
\put(12,1){\framebox(2.5,.9)[cc]{Cost-Sensitive}}
\end{pspicture}
\caption{\label{fig:easy} The {}``easy'' direction for
reductions between the learning problems discussed here.}
\vskip -.5in
\end{figure}
\end{center}

\section{Reduction from Multiclass Classification to Binary Classification}
In this section we analyze several well known reductions for efficiency.
Before we start, it is important
to note that there are (see \cite{adaboost.oc},\cite{adaboost.m2})
boosting algorithms for solving multiclass classification given weak
binary importance weighted classification.  Some of these methods
require extra-powerful classification algorithms, but others are
genuine reductions, as defined here.  A reductionist approach for
creating a multiclass boosting algorithm is to simply compose any one
of the following reductions with \emph{binary} boosting.

\subsubsection{The one-against-all reduction }
\label{sub:The-one-against-all-reduction}
In the one-against-all reduction, we learn $r$ classifiers $h_{i}$,
using the mapping $(x,y)\rightarrow(x,I(y=i))$.
In order to construct a multiclass classifier from the binary classifiers,
we use the following procedure: If there exists a label
$i$ such that $h_{i}(x)=1$, then predict $i$, breaking ties randomly;
predict randomly otherwise.  
Note that the trick of combining many calls into one described in
Section~\ref{sec:call} applies here.

\begin{theorem}
(One-against-all error efficiency) If the binary classifiers have
error rate $\epsilon$, the one-against-all reduction has error rate
at most \[
(r-1)\epsilon.\]
\end{theorem}
\begin{proof}
We analyze how false negatives and false positives 
produced by the binary classifiers lead to errors in the
multiclass classifier.
A false negative produces an error in the multiclass classifier
a $\frac{r-1}{r}$ fraction of the time
(assuming all the other classifiers
are correctly outputting 0), because we are choosing randomly between $l$
labels and only one is correct.
The other error modes to consider involve (possibly multiple) false positives.
If there are $n$ false positives, the error probability is either
$\frac{n}{n+1}$ or $1$ if there was also a false negative.
The efficiency of these modes in creating errors (i.e., the ratio
of the probability of a multiclass error to the number of binary errors) is
$\frac{\frac{r-1}{r}}{1}=\frac{r-1}{r}$,
$\frac{\frac{n}{n+1}}{n}=\frac{1}{n+1}$,
and $\frac{1}{n+1}$, respectively.
Taking the maximum, we get $\frac{r-1}{r}$.
Multiplying by $r$ (since we have $r$ opportunities to err, one
for each classifier), we get the bound.
\qed
\end{proof}

\noindent
The one-against-all reduction above is not learinng
preserving, but two simple modifications would make it learning
preserving without affecting the error limitation bound.
First, we learn binary classifiers only for those
labels that actually appear in the training set; i.e., if there was
no example with label $i$, we do not learn $h_i$. Similarly for
prediction; if no learned $h_i$ predicts 1, we predict randomly 
among the labels seen during training.
Second, if we train a pair of binary classifiers on sets of examples 
with complementary labels, we ignore one of the classifiers.
A moment's thought shows that the error limitation bound still holds.

The modified reduction is learning preserving. For every $r > 1$,
there exists a reduction $R$ from binary classification to
$r$-class classification such that for every input space $X$, distribution 
$D$ over $X\times \{0,1\}$, and every binary learning algorithm $A$, 
if $A$ has loss rate $\epsilon$ on $D$, then $R(\mbox{one-against-all}(A))$
has loss rate $\epsilon$ on $D$.

The back reduction $R$ takes a set of examples with
binary labels and simply feeds it to the oracle for $r$-class classification.
If the oracle's prediction is not in $\{0,1\}$, predict randomly; otherwise
answer with the oracle's prediction.

Let $S\sim D$ be a binary training set input to $R$. Under the reduction,
$R$ feeds $S$ to the oracle $\mbox{one-against-all}(A)$, which in turn
feeds $S$ to its oracle $A$, making the loss rates of $A$ 
and $R(\mbox{one-against-all}(A))$ equal. It's clear that an adversarial 
$A$ can easily make the unmodified one-against-all reduction not learning 
preserving.

\shrink{ % not true -- ignore 
\noindent

\begin{theorem}\label{preserving}
The one-against-all reduction is learning preserving. For every $r > 1$,
there exists a reduction $R$ from binary classification to
$r$-class classification such that for every binary learning
problem $L$ and every binary learning algorithm $A$, if $A$ has loss
rate $\epsilon$ on $L$, then $R(\mbox{one-against-all}(A))$ 
has loss rate $\epsilon$ on $L$.
\end{theorem}
\begin{proof}
For any input space $X$, distribution $D$ over $X\times \{0,1\}$, 
and oracle $A$, the loss rate 
of the reduction $R(\mbox{one-against-all}(A))$ on $D$ is the same
as the loss rate of the oracle $\mbox{one-against-all}(A)$ on the distribution
induced by $R$ on $D$ (the oracle never outputs a label not in $\{0,1\}$).
This loss rate is, in turn, the same as the loss rate of $A$ 
on the distribution 
induced by the one-against-all reduction, since the one-against-all reduction 
will learn two classifiers, $h_0$ and $h_1$, and 
\qed
\end{proof}
}

\subsubsection{The Tree Reduction}
In the tree reduction (which is well known, see chapter 15 of
\cite{Tree}), we construct $r-1$ binary classifiers, which distinguish
between the labels using a binary tree. The tree has depth
$\log_{2}r$, and each internal node is associated with a set of labels
that can reach the node, assuming that each classifier above it
predicts correctly.  The set of labels at that node is split in half,
and a classifier is trained to distinguish between the two sets of
labels.  In particular, we start with the set of all labels
$\{1,\ldots,r\}$ at the top most node, and split the labels into
ordered intervals $\{1,\ldots,r/2 - 1\}, \{r/2, r\}$ at each node.
Predictions are made by following a chain of classifications down to
the leaves, each of which is associated with a unique label.

Note that the trick of combining many calls into one described in
Section~\ref{sec:call} applies here as well. Also, instead of $r - 1$
parallel, one could use $\log_2r$ queries.

\begin{theorem}
(Tree error efficiency) If the binary classifiers have loss rate
$\epsilon$, the tree reduction has loss rate at most \[
\epsilon\log_{2}r.\]

\end{theorem}
\begin{proof}
A multiclass error occurs only if some binary classifier on
the path from the root to the leaf errs. \qed
\end{proof}

\vskip .1in\noindent
We will show that the tree reduction is learning preserving.

\begin{theorem}\label{preserving}
The tree reduction TREE is learning preserving.  For every $r > 1$,
there exists a reduction $R$ from binary classification to
$r$-class classification such that for every binary learning
problem $L$ and every binary learning algorithm $A$, if $A$ has error
rate $\epsilon$ on $L$, then $R(TREE(A))$ has error $\epsilon$ on $L$.
\end{theorem}
\begin{proof}
The converse reduction $R$ takes a set of examples $S$ with
binary labels, and feeds the set $\{ (x, (r-1) y + 1 ) |
(x,y) \in S \}$ to the oracle for $r$-class
classification.  The binary classifier $h$ is constructed from the resulting
$r$-class classifier $h_r$ as $h(x) = I(h_r(x) > r/2 -1)$.

Let $S_r$ be the set of examples induced by $R$ on the inputs to the oracle 
$TREE(A)$.  Under the tree reduction, these examples are 
converted according to $\{(x,I(y_r \geq r/2 -1) :
(x,y_r) \in S_r \}$.  Consequently, we have $S = S_r$ and so the
loss rate of $A$ on $S$ is exactly the loss rate of the root
classifier in $TREE(A)$.  Since the loss rates of all other
classifiers are irrelevant under the mapping $h(x) = I(h_r(x) > r/2
-1)$, we know that the loss rate of the classifier given by
$R(TREE(A))$ equals the loss rate of $A$.
\qed
\end{proof}

\subsubsection{The error correcting output code (ECOC) reduction.}

Let $C \subseteq \{0,1\}^n$ be an error-correcting code with $l$
codewords a minimum distance of $d$ apart.  Let $C_{i,j}$ denote the
$i$'th bit of the $j$'th codeword of $C$.  The ECOC reduction
corresponding to $C$ learns $n$ classifiers: the $i$'th classifier
predicts $C_{i,y}$ where $y$ is the correct label given input $x$.
The loss rate for this reduction is at most $2n\epsilon/d$, as we
shall prove in Theorem~\ref{thm:ECOC} below.

We mention three codes of particular interest.
The first is when the codewords are a subset of the rows of
an Hadamard matrix (an $n \times n$ $\{0,1\}$-matrix for which any
two rows differ in exactly $n/2$ places).
Such matrices exist and are easy to construct when $n$ is a power of
$2$.
(The famous Hadamard conjecture states that they exist whenever $n$ is
a multiple of $4$.)
Thus, for Hadamard codes,
the number of classifiers needed is less than $2 r$, and
the loss rate is at most $4 \epsilon$.

A second code of interest is when the codewords are the
binary representations of $0, 1, \dots, r-1$.  In this case,
the ECOC reduction is the same as the tree reduction above.

A third code of interest is the $r \times r$ identity matrix,
for which the ECOC reduction is the same as the one-against-all
reduction.

Also note that the ``many calls to one call'' trick in section
\ref{sec:call} (call efficiency) can be applied here.

\begin{theorem} \label{thm:ECOC}
(ECOC loss efficiency) If the binary classifiers have loss rate
$\epsilon$, the ECOC reduction has loss rate less than:
\[
\frac{2n}{d} \epsilon.
\]
\end{theorem}
This theorem is identical to Lemma 2 of \cite{Guruswami} (which was
generalized in \cite{ASS}), except for one small difference.  Here, we
are concerned with the loss rate on the distribution $D$ generating
examples rather than the loss rate on a training set.

Sometimes ECOC is analyzed assuming the errors are independent. This
gives much better results, but seems less justifiable in practice. For
example, in any setting with label noise, errors are highly
\emph{dependent}.

\begin{proof}
When the loss rate is zero, the correct label is consistent with all
$n$ classifiers, and wrong labels are consistent with at most $n - d$
classifiers, since $C$ has minimum distance $d$.  In order to wrongly
predict the multiclass label, at least $d/2$ binary classifiers must
err simultaneously. Since every multiclass error implies at least a
fraction $d/2n$ of the binary classifiers erred, a binary loss rate
of $\epsilon$ can yield at most a multiclass loss rate of
$2n\epsilon/d$.
\qed
\end{proof}

\section{proof of weighted one-against-all}

\begin{proof} (of theorem \ref{thm:subset}
There are two forms of errors, false positives (predicting 1 when the
correct label is 0) and false negatives (predicting 0 when the correct 
label is 1).
First, we will show that an adversarial binary classifier trying to
induce subset errors with maximal efficiency has three possible
strategies, then analyze these strategies.

First, notice that it is never more efficient to have multiple
false positives because the expected probability of a subset error
grows sublinearly. For any number $p$ of true positives,
the probability of a subset error with two false positives is
$\frac{2}{p+2}$, which is less than $\frac{2}{p+1}$, the probability
of erring on two subset examples when investing one false positive in each.
For $p=0$, only one false positive is required to always err.

Now let $f$ be the number of false negatives. If $f<n$ (note that 
$f$ can be at most $n$),
there must be one false positive; otherwise the error rate would be 0.
For $f$ false negatives and one false positive, we have
a loss rate of $\frac{1}{n-f+1}$ with the adversary paying
importance $fi_{1}+i_{0}$. To improve error efficiency, it is beneficial
for the adversary to increase $f$ if
\[
\frac{\frac{1}{n-(f+1)+1}}{(f+1)i_{1}+i_{0}}>\frac{\frac{1}{n-f+1}}{fi_{1}+i_{0}},
\]
or equivalently if
$
i_{0}>i_{1}(n-2f).
$
Otherwise, it is more efficient to decrease $f$. Thus
an optimal adversary must choose either $f=0$ or $f=n$.

For the $f=0$ case we have error efficiency $\frac{\frac{1}{n+1}}{i_{0}}$.

For the $f=n$ case, the adversary can have $0$ or $1$
false positives. These cases have loss rates of $\frac{r-n}{r}$
and $1$ with importance consumption of $ni_{1}$ or $ni_{1}+i_{0}$, respectively.

Thus the adversary's most efficient strategy is given by
$$\max\left\{ \frac{r-n}{r ni_{1}},\frac{1}{ni_{1}+i_{0}},\frac{1}{(n+1)i_{0}}\right\} = \frac{1}{r}.
$$

Since the maximal error efficiency is $\frac{1}{r}$ and there are $r$
classifications, a binary importance weighted loss of $\epsilon$
implies a subset loss rate of $\epsilon$. However, the importance
weighted loss is unnormalized since
$\frac{n}{r}i_{1}+\frac{r-n}{r}i_{0}=\frac{r}{n+1}$ for $r\leq
n^{2}+n$ or $(\frac{r+1}{n+1}-\frac{n}{r})$ for $r > n^{2}+n$.
Taking an expectation over $n$ according to $D$, we get the result.
\qed
\end{proof}

\end{document}
