\documentclass[12pt]{llncs}
\newcommand{\shrink}[1]{}
%\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}

\renewcommand{\baselinestretch}{0.91}
%\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 problem into a solver for
another problem. We discuss and analyze reductions which automatically
convert classification solvers into solvers for other
classification-like learning domains.
\end{abstract}

\section{Introduction}

There are many natural learning domains such as {\em classification},
{\em cost sensitive classification}, {\em importance weighted
classification}, and others. Two approaches are possible for dealing
with this variety of learning domains.  One possibility is to analyze
every domain in great detail, and produce specific analysis and
algorithms for each domain. The other possibility is to construct
reductions from new or unexplored domains to a thoroughly analyzed
domain, automatically transferring existing theory and algorithms from
the well-understood domain into new domains. Here, we investigate the
latter approach, which allows us to simultaneously:
\begin{enumerate}
\item Show how related these natural learning domains are. Two
learning domains are related if we have a short efficient reduction
from one to the other and vice versa.
\item Extend much of the hard work of existing theories into new domains.
\item Provide algorithms for solving these natural learning domains, when
combined with a basic learning algorithm.
\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, discuss the
relationship with prior work, and then present 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}
(Supervised Learning Domain) A tuple $(K,Y,l)$ where $K$ is
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 domain is (implicitly) a set of learning problems, each of which
requires more information to be fully specified.  Note that we have
separated the information at training time $K$, from the prediction
space $Y$.  This additional flexibility (also used in \cite{Haussler})
is required.
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
Name&
$K$&
$Y$&
$l$
\tabularnewline
\hline
Binary Classification&
$\{0,1\}$&
$\{0,1\}$&
$I(k \neq y)$
\tabularnewline
\hline
Multiclass Classification&
$\{0,r-1\}$&
$\{0,r-1\}$&
$I(k \neq y)$
\tabularnewline
\hline
Importance Weighted C.&
$\{0,r-1\} \times [0,\infty)$&
$\{0,r-1\}$&
$k_2 I(k_1 \neq y)$
\tabularnewline
\hline
Many-right C.&
$2^{\{0,r-1\}}$&
$\{0,r-1\}$&
$I(y \not \in k)$
\tabularnewline
\hline
Cost Sensitive C.&
$[0,\infty)^r$&
$\{0,r-1\}$&
$k_y$
\tabularnewline
\hline
\end{tabular}
\end{center}
Some of these domains are nonstandard.  Importance weighted,
many-right, and cost sensitive classification are domains which allow
additional flexibility by providing additional information to the
learning algorithm about the loss of different choices.
\begin{definition}
(Supervised Learning Problem) A tuple $(D,X,K,Y,l)$, where $(K,Y,l)$
is a supervised learning domain, $X$ is an arbitrary feature space and
$D$ is a distribution over $X\times K$.
\end{definition}
A supervised learning problem is solved by finding a hypothesis
$h:X\rightarrow Y$ which minimizes the expected loss:
$\arg\min_{h}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 learning time.
\begin{definition}
(Supervised Learning Algorithm)\footnote{Note that we do not require
the learned hypothesis to be restricted to some fixed subset of
hypotheses $H$ in advance, because that is unnecessary.  Of course,
such an $H$ exists implicitly as all the possible outputs of $A$.} An
algorithm $A$ mapping a set of examples $(X\times K)^m$ to a
hypothesis $h:X\rightarrow Y$.
\end{definition}
Standard supervised learning algorithms such as support vector
machines and logistic regression fit this definition.\footnote{Notice
that these algorithms do not actually work for {\it all} learning
problems in their domain since they don't actually work for an
arbitrary input space $X$.  However, our idealized supervised learning
algorithm does.} A ``good'' supervised learning algorithm find a
hypothesis $h$ with approximately minimal expected loss $h_D$ for
learning problems in some domain.

\subsection{Reductions}
A reduction solves problems in one learning domain using blackbox
access to a solver for another domain.  We are interested in
reductions that perform well whenever the solver performs well.

To define ``performs well'', note that a reduction is a process which
maps samples from one problem $(D,X,K,Y,l)$ into a new problem
$(D',X',K',Y',l')$.  The mapping of $X\rightarrow X'$ and $K
\rightarrow K'$ are explicit, but the map from a \emph{measure} $D$
over samples into a \emph{measure} $D'$ over new samples is implicit.

A set of examples $S=(x,k)^m$ input to the reduction induces a measure
$D_S$ over $X'\times K'$ given by:
$$D_S(x',k')=E_{S\prime \sim S}\frac{\#(x',k')}{|S'|},$$ where the
expectation is over possible sets of examples $S'$ generated by the
reduction\footnote{Note that the reduction can be randomized and the
expectation occurs over that randomization.} from $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
samples sets $S$ generated by $D$.  

One issue arises: What is $D'$ for the second sequential invocation
of the oracle? Suppose that the first invocation produces
a function $h$. We replace the first invocation with the oracle which
always returns $h$, and use the above definition to find $D'$ for
the second invocation.

With $D'$ defined, we state the formal definition.

\begin{definition}\label{reduction-definition}
(Supervised Learning Reduction) A learning reduction from domain
$(K,Y,l)$ to domain $(K',Y',l')$ is a learning algorithm for $(K,Y,l)$
that has oracle access to a learning algorithm $A'$ for $(K',Y',l')$.
The output hypothesis $h$ must satisfy:
\vskip .1in \noindent (Error Limitation) For all $X$, and for all
distributions $D$ over $X\times K$, $$h_D \leq 
g(\max_{h' \mbox{output by oracle calls}} h'_{D'})$$
for some continuous monotone nondecreasing function $g:
[0,\infty)\rightarrow [0,\infty)$ with $g(0)=0$.
\end{definition}
\noindent
One important thing to notice here is that while we talk about
``distributions'' and ``measures'' over samples, none of the above
definitions require that samples be drawn independently. Analysis in
this model is therefore directly applicable to a 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 $B$
solver as a black box.  

One critical difference is that in complexity theory reductions are
usually a means for classifying the relative hardness of problems.  A
reduction from $A$ to $B$ 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$).  

Another major difference is that meaningful Turing reductions must be
computationally limited, since we do not want a reduction to solve a
$A$ by brute force.  In machine learning a reduction is still
meaningful without a restriction on computational power.  This is
because the hardness of solving a learning problem is due to a lack of
{\it information}\footnote{In particular $D$, which defines the
optimal solution, is unknown.} rather than computation available to
the algorithm.  

Notice that this definition does not necessarily force the reduction
to use $A'$ in a nontrivial way; Some learning domains 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 show there exists enough
structure so that analysis can provide meaningful results.  

Naturally, reductions compose.
\begin{proposition}(Reduction Composition)
If $R_{12}$ is a reduction from domain ${\cal D}_1$ to ${\cal D}_2$
with error limitation $g_{12}$ and $R_{23}$ is a reduction from domain
${\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$,
$R_{23}$ yields a learning algorithm for ${\cal D}_2$ such that for
all $X_2$ and $D_2$, we have: $h'_{D_2} \leq g_{23}(\max_{h''
\mbox{output by A}} h''_{D_3})$. We also know that $R_{12}$ yields a
learning algorithm for ${\cal D}_1$ such that for all $X_1$ and $D_1$:
$$h_{D_1}\leq g_{12}(\max_{h' \mbox{ output by }R_{23}(A)} h'_{D_2}) \leq
g_{12}(g_{23}(\max_{h'' \mbox{ output by } A} h''_{D_3}))$$
Finally, notice that $g_{12}\circ g_{23}$ is continuous, monotone
nondecreasing and $g_{12}(g_{23}(0))=0$.
\end{proof}

\vskip .1in \noindent {\bf Efficiency}\label{sec:call}\quad If two
domains are reducible, it is reasonable to say that they are similar,
\emph{modulo the complexity of the reduction}.  The more restrictive
the reduction, the stronger the statement.  There are several forms of
efficiency.
\paragraph{Time Efficiency:} We want the transformation to be computationally
efficient, assuming that all calls to the oracle take unit time.
\paragraph{Call efficiency:}
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 and answered in parallel); (3) the
maximum expected number of samples input to the oracle.

Parallel calls to the oracle can often be turned into a single call,
at least theoretically.  Suppose that we want to 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)$.

\noindent {\bf Independence Preservation}\quad Many common
learning algorithms are built under the assumption that samples 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}
(Learning Preserving) \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'$, every oracle $A'$, if
$A'$ has loss rate $\epsilon$ on a sample $S'$ then $R'(R(A'))$ has
loss rate $\epsilon$ on a sample $S'$.
\end{definition}

Definition~\ref{reduction-definition} and reduction composition do not
imply learning preserving.  The distribution $D$ induces a
distribution $D'$ on $R(A')$ via $R'$ which further induces a
distribution $D''$ on $A$ recursively.  However,
Definition~\ref{reduction-definition} does \emph{not} generally imply
that $D'' = D$, even though these distributions have the same domains.
In general, good performance on $D$ says nothing about good
performance with respect to $D''$.

The next section shows a reduction which achieves the learning
preserving property.

\section{Prior Work on Reductions}
Many people have worked on reductions in learning.  One of the
goals of this paper is to unify these algorithms in a common
framework, and codify the best practices of reductions work.

Boosting algorithms \cite{Boosting} 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.  Some boosting variants
have suffered because they place too much emphasis on noisy data
points \cite{noise_boost}.

Bagging \cite{Bagging} can be seen as a self-reduction of
classification to classification. Bagging is useful because it turns
learning algorithms with high ``variance'' (dependence on the exact
examples seen) into voting classifiers with lower ``variance''.  Like
some Boosting variants, Bagging also suffers because the examples that
it feeds into the classifier learning algorithm are not necessarily
independently distributed according to the original distribution.

Error Correcting Output Codes (ECOC)~\cite{ECOC} are a technique for
solving multiclass classification given a solver for binary
classification (with significant positive empirical results).  

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

Pitt and Warmuth \cite{PW} constructed and analyzed a form of
reduction between classification problems called
\emph{prediction-preserving reducibility}.  The reductions presented
here have several differences: (1) they are between arbitrary learning
\emph{domains} rather than between 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 domains.

\section{Simple Analysis} 

The learning domains we consider have an ``easy'' direction for
reduction related to whether a particular domain is definable as a
subset of another domain.

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{figure}
%\includegraphics[scale=0.75]{easy.eps}
\hskip .3in \scalebox{0.7}{
\begin{pspicture}(2,3)
\put(1,2){\oval(3.1,1.2)}
\rput(1,2.3){\bf \small Binary}
\rput(1,1.8){\bf \small Classification}
\put(4.9,3.1){\oval(3.3,1.2)}
\rput(4.9,3.4){\bf \small Multiclass}
\rput(4.9,2.9){\bf \small Classification}
\put(9.1,3.1){\oval(3.3,1.2)}
\rput(9.1,3.4){\bf \small Many-right}
\rput(9.1,2.9){\bf \small Classification}
\put(13.3,2){\oval(3.3,1.2)}
\rput(13.3,2.3){\bf \small Cost-Sensitive}
\rput(13.3,1.8){\bf \small Classification}
\put(7,1.7){\oval(4.6,1.2)}
\rput(7,1.9){\bf \small Importance Weighted}
\rput(7,1.5){\bf \small Binary Classification}
\rput(2.15,2.6){\psline{->}(1.1,.4)}
\rput(6.55,3.05){\psline{->}(.9,0)}
\rput(10.75,3){\psline{->}(1.1,-.55)}
\rput(2.45,1.6){\psline{->}(2.25,0.0)}
\rput(9.3,1.6){\psline{->}(2.45,0.0)}
\end{pspicture}
}
\vskip -0.5in
\caption{\label{fig:easy} A figure showing the {}``easy'' direction for
reduction amongst the learning problems discussed here.}
\end{figure}

Much of the prior work on reductions can be analyzed here.  We include
a table of results and refer to the appendix for details.

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
Name&    $g(\epsilon)$&                Learn Preserve& Time& \#Calls& Indep. Preserve
\tabularnewline
\hline
Costing& $\epsilon$&                           ??& $O(Tm)$& $T$ parallel& Yes
\tabularnewline
\hline
1-vs-all& $(r - 1) \epsilon$&                  ??&$O(|S| r)$&$r$ parallel& Yes
\tabularnewline
\hline
Tree& $\epsilon \log_2 r$&                    Yes& $O(|S| r)$&$r - 1$ parallel& Yes
\tabularnewline
\hline
ECOC& $4 \epsilon $&                           ??& $O(r|S|)$& $2 r$ parallel&  Yes
\tabularnewline
\hline
Boosting&$e^{-2T (1/2 - \epsilon)^2)}$&        ??& $O(|S|T)$& $T$ Adaptive&  Yes
\tabularnewline
\hline
\end{tabular}
\end{center}

\section{To Importance Weighted Classification}

In this section we analyze and discuss reductions to weighted binary
classification, a less explored possibility.  Given the ``Costing''
reduction from importance weighted classification to classification,
the results here compose to produce new (or alternative) reductions to
binary classification.

\subsection{The Weighted One-against-all Reduction }

This reduction is an optimized one-against-all reduction for many-right
classification to importance weighted binary classification. It appears
to be new.

In the weighted one-against-all reduction, we learn one classifier,
using data from the mapping:\[
(x,k_{1},k_{2},...,k_{n})\rightarrow \forall y\,\,\,((x,y),I(y \in \{
k_{1},...,k_{n}\}),i_{I(y \in \{ k_{1},...,k_{n}\})})\] where
$i_{0}=\frac{r}{n+1}$ and $i_{1}=\frac{r}{n+1}$ if $r\leq n^{2}+n$ or
$i_{1}=\frac{r-n}{n}$ for $r\geq n^{2}+n$.  To construct a multiclass
classifier from the binary classifiers, we use the following
procedure: If there exists a label $y$ such that $h(x,y)=1$, then
predict $y$, breaking ties randomly; predict randomly otherwise.

\begin{figure}[t]
\rotatebox{270}{\includegraphics[scale=0.75]{combined.ps}}
\caption{\label{fig:acc} A figure showing comparative performance
between the weighted-one-against-all + costing reduction to the
one-against-all reduction on several multiclass datasets with Boosted
Naive Bayes (BNB) and Support Vector Machine (SVM) classifiers.}
\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.  Next, we prove an error rate transformation bound.
\begin{theorem}
(Many-right classification error efficiency) Let $c_{r
n}=\frac{r}{n+1}$ for $r\leq n^{2}+n$ or $c_{r
n}=\frac{r+1}{n+1}-\frac{n}{r}$ otherwise.  If the binary classifiers
have normalized loss rate $\epsilon$, then the weighted
one-against-all reduction has error rate at most:\[ \epsilon
E_{x,k_{1},...,k_{n}\sim D}c_{r n}\]

\end{theorem}
This theorem should be compared directly with the one-against-all
reduction to binary classification which had an 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 an error efficiency of about $\frac{r}{2}$, or about half
the error rate of the earlier reduction. Reducing to importance weighted
binary classification has an improved efficiency.

\begin{proof}
There are two forms of errors, false positive and false negative.
First, we'll show that an adversarial binary classifier which tries to
induce multiclass errors with maximal efficiency has three possible
strategies, then analyze these strategies.

For small error rates, it is never more efficient to have multiple
false positive errors because the expected probability of an error
grows sublinearly.  For any number $p$ of true positives,
$\frac{2}{p+2}<\frac{1}{p+1}+\frac{1}{p+1}$ and for $p=0$, only one
false negative is required to always err.

If the optimal error rate occurs for $f$ false negatives when $f < n$
then there must be $1$ false positive (since the error rate is $0$
otherwise).  For $f$ false negatives and $1$ false positive, we have
an error rate of $\frac{1}{n-f+1}$ with the adversary paying
importance $fi_{1}+i_{0}$. Since:
\[
\begin{array}{ccc}
\frac{\frac{1}{n-(f+1)+1}}{(f+1)i_{1}+i_{0}}&>&\frac{\frac{1}{n-f+1}}{fi_{1}+i_{0}}\\
\Leftrightarrow i_{0}&>&i_{1}(n-2f)\\
\end{array}
\]
The adversary can improve the error efficiency by increasing $f$
whenever $i_{0}>i_{1}(n-2f)$ and by decreasing $f$
otherwise.  An optimal adversary must choose $f=0$ or $f=n$.

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

For the $f=n$ case there are again two possibilities: $0$ or $1$
false positives. These cases have an error rate of $\frac{r-n}{r}$
and $1$ with an importance consumption of $ni_{1}$ or $ni_{1}+i_{0}$.

The adversaries 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 multiclass error 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\geq n^{2}+n$.
Taking the expectation over $n$ and $r$ drawn according to $D$, we get
the result.

\end{proof}

\shrink{
\subsection{Multiclass cost sensitive classification}

Here we attempt to reduce multiclass cost sensitive classification
to importance weighted classification.

\subsubsection{The One-wrong reduction}

Consider the reduction which maps $(x,k_{0},k_{2},...,k_{r})\rightarrow(x,y,\max_{i}k_{i}-k_{y})$
for a uniformly chosen $y\in\{0,...,r-1\}$. This dataset is fed into
the importance weighted classification solver resulting in a classifier
$c:X\rightarrow\{0,...,r-1\}$ which is used to solve the classification
problem.

It is possible for a reduction to create extra hard subproblems which
are perhaps impossible to solve.  This is the case with the one-wrong
reduction.  It's only for lucky distributions where just one of the
costs is large\footnote{Thus the name.} that the problem we reduce to
can have a small error rate. Nonetheless, in this lucky case, a very
strong statement can be made.

\begin{theorem}
(error transformation) If the importance weighted classifier has loss
rate $\epsilon$, then the cost sensitive classifier has expected
cost less than $\epsilon$.
\end{theorem}
\begin{proof}
Assume that \[
\epsilon=E_{x,y,i\sim D^{*}}iI(c(x)\neq y)\]
\[
=E_{x,k_{0},...,k_{r-1}\sim D,y\sim\{0,...,r-1\}}(\max_{i}k_{i}-k_{y})I(c(x)\neq y)\]
\[
=E_{x,k_{0},...,k_{r-1}\sim D,y\sim\{0,...,r-1\}}\max_{i}k_{i}I(c(x)\neq y)-E_{x,k_{0},...,k_{r-1}\sim D,y\sim\{0,...,r-1\}}k_{y}I(c(x)\neq y)\]
\[
=\frac{r-1}{r}E_{x,k_{0},...,k_{r-1}\sim D}\max_{i}k_{i}-E_{x,k_{0},...,k_{r-1}\sim D}\frac{\sum_{i}k_{i}-k_{c(x)}}{r}\]
\[
=E_{x,k_{0},...,k_{r-1}\sim D}\frac{(r-1)\max_{i}k_{i}-\sum_{i}k_{i}+k_{c(x)}}{r}\]
\[
=E_{x,k_{0},...,k_{r-1}\sim D}\frac{k_{c(x)}-\max_{i}k_{i}}{r}+\max_{i}k_{i}-E_{i\sim\{0,...,r-1\}}k_{i}\]
Rewriting, we get: \[
E_{x,k_{0},...,k_{r-1}\sim D}k_{c(x)}=\epsilon-r[E_{x,k_{0},...,k_{r-1}\sim D}\max_{i}k_{i}-E_{i\sim\{0,...,r-1\}}k_{i}]+E_{x,k_{0},...,k_{r-1}\sim D}\max_{i}k_{i}
\]
\[
=\epsilon-E_{x,k_{0},...,k_{r-1}\sim D}(r-1)\max_{i}k_{i}-\sum_{i}k_{i}\]
\[
\leq\epsilon\]
Where the last inequality follows because on of the $k_{i}$ is $0$.
\end{proof}

\subsection{The weighted all pairs reduction}
The One-wrong reduction may not work well for general multiclass
classification, so we state a more general reduction next.

We learn %$\binom{r}{2}$ classifiers $h_{i,j}$
$(j>i)$ using the mapping
\[
(x, k_1, k_2, \ldots, k_{r}) \rightarrow
(x, I(k_i \le k_j), \sum_{n=1}^{r} k_n).
\]
We say
label $i$ beats label $j$ if $h_{i,j}$ outputs 1, otherwise $j$ beats $i$.
The cost sensitive classifier predicts the label that beats the maximum number
of other labels (breaking ties at random).

\begin{theorem} If the binary classifiers have error rate at most $\epsilon$ then
the cost sensitive classifier defined by the above reduction has expected cost
at most $\frac{r}{2} \epsilon$.
\end{theorem}
\begin{proof}
Suppose $x \in X$ and $0= k_{i_1} \le k_{i_2} \le \ldots \le k_{i_r}$ are
the true costs for $x$, where $i_1, i_2, \ldots i_r$ is some permutation of
the labels.  Let $C = \sum_{j=1}^{r} k_j$.

%Note that when there are no errors, the label $i_m$ beats exactly $r - m$
%others. Now suppose we want the classifier to select $i_m$. If we  make $n_1$
%errors in favor of $i_m$ then it beats $r -m +n_1$

%Consider the tournament digraph with vertices $i_1, i_2, \ldots i_r$, with
%an edge from $i_m$ to $i_n$ when $i_m$ beats $i_n$. When there are no errors,
%vertex $i_m$ has outdegree $r -m$. An error corresponds to reversing an edge
%in the graph.

In order for label $i_{n}$ to win
the tournament outright (over label $i_1$ in particular),
at least $n-1$ of the $2r-3$
classifiers subscripted with $i_1$ and/or
$i_{n}$ must err.  If at least $n-2$ of these classifiers
err, it is possible for labels $i_1$ and $i_n$ to tie
(possibly in a 3-way tie with label $i_2$, however this is
not an efficient use of errors for our adversary).
Thus, if $n$ errors are made by the binary classifiers,
and $1 \le n \le r -2$,
then the cost incurred by our cost sensitive
classifier is
at most $\max(k_{i_{n+1}}, k_{i_{n+2}}/2)$.

Since the sum of the costs is $C$,
for any $n$ the largest possible value of $k_{i_n}$
is achieved when
\[
0 = k_{i_1} = k_{i_2} = \dots
= k_{i_{n-1}} < k_{i_n} =\ldots = k_{i_r} = C/(r + 1 - n).
\]
So whenever $1 \le n < r$ errors occur, the cost incurred is
at most $C/(r-n)$, which is $\le Cn/(r -1)$.
The same upper bound holds for $n \ge r$, since $r -1$
errors are already enough to produce the maximum possible output.

Then by definition,
\[
\Exp_{(x,k_1,k_2,\ldots,k_r) \sim D}(Cn) = \sum_{i<j} E_{(x,k) \sim D'} l(k,h_{i,j}(x)) \le \binom{r}{2}\epsilon.
\]
It follows that the expected cost for our cost-sensitive classifier
is at most $\frac{1}{r-1} \binom{r}{2} \epsilon
= \frac{r}{2} \epsilon$.
\end{proof}
}
\subsection{A better CSC to IWC reduction}

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_i - v_j|
),
\]
for all pairs $(i,j)$ with $i < j$.  The values $v_1, \dots, v_r$
are functions of $k_1, \dots k_r$, which will be defined below,
but which are order-preserving in the sense that, for all $i,j$,
$k_i < k_j$ iff $v_i < v_j$.

Given $m$ samples of training
data for the CSC problem, we generate $m \binom{r}{2}$
training inputs for the IWC problem, by iterating
through all $\binom{r}{2}$ possibilities for $i$ and $j$.
Now we use our oracle and this training data to generate
an IW classifier, $h$.  Given an input $x$ for the CSC 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$.)
Equivalently,
\[
v_i = \sum_{j=1}^{s-1} (w_{j+1} - w_j)/j,
\]
where $w_1 \le w_2 \le \dots \le w_r$, and, as multisets,
$\{w_1, \dots, w_r\} = \{k_1, \dots, k_r\}$, and $s$ is
defined so that $w_s = k_i$.  The equivalence of
these definitions is clear, considering that the function
$L(t)$ is piecewise linear with slope $1/j$ on each
interval $(w_{j}, w_{j+1})$.

Our next result says that this method of assigning importances is
essentially optimal.

\begin{theorem}
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}

\begin{remark}
It should be noted that this result is not quite
as good as it might first appear.  If $r$ is large,
a loss rate of $1/r$ may be very good for the IWC
problem.  However, an expected cost of $1/r$ for
the CSC problem can be achieved by selecting labels
uniformly at random.  So our theorem is only nontrivial
when $\epsilon < 1/2r$.
\end{remark}

\begin{proof}
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$.


\end{proof}

\section{Conclusion}

\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$ & ??& $O(|S| r)$& $r$ parallel&Yes
\tabularnewline
\hline
weighted all-pairs& $\epsilon$& ??& $O(r^2)$& $1$& Yes
\tabularnewline
\hline
\end{tabular}

The definitions of reduction we outline here cover 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 characteristics.

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

Our definition of reduction here is limited to the supervised learning
domain. It nonetheless appears that natural generalizations capturing
even broader domains is possible. More work on basic definitions must
be done.

\begin{thebibliography}{1}
\bibitem{naoki}N. Abe and O.~Watanabe. TIEICE: IEICE Transactions on
Communications/Electronics/Information and Systems, 1992.
\bibitem{ASS}Erin Allwein, Robert Schapire, Yoram Singer ``Reducing
Multiclass to Binary: A Unifying Approach for Margin Classifiers'',
Journal of Machine Learning Research, 2000
\bibitem{Bagging}L. Breiman. Bagging predictors. Machine Learning, 26(2):123-140, 1996.
\bibitem{ECOC}Thomas G. Dietterich and Ghulum Bakiri, {}``Solving
Multiclass Learning Problems via Error-correcting Output Codes''
Journal of Artificial Intelligence Research, 2:263-286, January 1995.
\bibitem{Boosting}Yoav Freund and Robert E. Schapire. A decision-theoretic generalization
of on-line learning and an application to boosting. Journal of Computer
and System Sciences, 55(1):119-139, 1997.
\bibitem{Tree}J. Fox, ``Applied Regression Analysis, Linear Models, and Related Methods'', Sage.
\bibitem{Guruswami}V. Guruswami and A. Sahai. ``Multiclass Learning,
Boosting, and Error-correcting codes'', Proceedings of COLT'99.
\bibitem{All-pairs}Hastie and Tibshirani.Classification by pairwise
coupling.in Advances in Neural Information Processing Systems 10, MIT
Press, 1998
\bibitem{Haussler}David Haussler, "Decision Theoretic Generalizations
of the PAC Model for Neural Net and Other Learning Applications",
Information and Computation, Vol. 100, September, 1992, pp. 78-150.
\bibitem{noise_boost}Adam Kalai and Rocco Servedio, {}``Boosting in the Presence of Noise''
To appear in Proceedings of the Thirty-Fifth Annual ACM Symposium
on the Theory of Computing (STOC 2003).
\bibitem{PW}Lenny Pitt and Manfred Warmuth, ``Prediction-Preserving
Reducibility'', Journal of Computer and System Sciences, 41:430--467,
1990.
\bibitem{One-vs-all} Rifkin and Klautau. In Defense of One-Vs-All
Classification." Journal of Machine Learning Research, Volume 5,
pp. 101-141, 2004
\bibitem{adaboost.m2}Robert E. Schapire and Yoram Singer. Improved
boosting algorithms using confidence-rated predictions. Machine
Learning, 37(3):297--336, 1999.
\bibitem{adaboost.oc}Robert E. Schapire. ``Using output codes to boost
multiclass learning problems''. In Machine Learning: Proceedings of
the Fourteenth International Conference, 1997 (ICML 1997).
\bibitem{costing}Bianca Zadrozny, John Langford, and Naoki Abe. ``Cost
Sensitive Learning by Cost-Proportionate Example Weighting'', ICDM
SW2003.
\end{thebibliography}

\appendix
\section{Reduction from Multiclass Classification to Binary Classification}
We analyze several well known reductions for efficiency, and then
present a number of new reductions.  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 (predicting 0 when the correct label is 1)
and false positives (predicting 1 when the correct label is 0)
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.
\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 $\{0,...,r
-1\}$ at the top most node, and split the labels into ordered
intervals $\{0,...,r/2-1\}, \{r/2 -1, r -1\}$ at each node.

Predictions are made by following the 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$ adaptive queries.

\begin{theorem}
(Tree error efficiency) If the binary classifiers have error rate
$\epsilon$, the tree reduction has error 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.
\end{proof}

\vskip .1in\noindent
To illustrate the invertibility property, we show that this reduction
satisfies it.

\begin{theorem}
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 sequence of examples $S$ with
binary labels, constructs a multiclass dataset $\{ (x, (r-1) y ) |
(x,y) \in S \}$, and feeds it to the oracle for $l$-class
classification.  A binary classifier is constructed from the resulting
$l$-class classifier $h_l$ according to $h(x) = I(h_l(x) > r/2 -1)$.

The sample set $S_l$ induced by $R$ on the inputs to $TREE(A)$ has
support $X\times \{0,r-1\}$.  Under the tree reduction, these
samples are converted according to $S'=\{(x,I(y_r \geq r/2 -1) :
(x,y_r) \in S_l \}$.  Consequently, we have $S = S_r$ and so the
error rate of $A$ on $S$ is exactly the error rate of the root
classifier in $TREE(A)$.  Since the error rates of all other
classifiers are irrelevant under the mapping $h(x) = I(h_l(x) > r/2
-1)$, we know that the error rate of the classifier given by
$R(TREE(A))$ equals the error rate of $A$.

\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 error 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 error 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 error efficiency) If the binary classifiers have error rate
$\epsilon$, the ECOC reduction has error 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 error rate on the distribution $D$ generating
examples rather than the error 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 error 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 error rate
of $\epsilon$ can yield at most a multiclass error rate of
$2n\epsilon/d$.
\end{proof}
\section{Boosting}

The algorithm Adaboost \cite{Boosting} run for $T$ rounds can be
thought of as a reduction from classification to importance weighted
classification with the following properties:

The $g(\epsilon)$ entry above deserves some explanation.  Adaboost is
typically analyzed with respect to weak learning on an importance
weighted \emph{training set} rather than weak learning with respect to
the importance weighted distribution constructed by randomizing over
the samples input to the boosting algorithm.  Nonetheless, the same
analysis holds when we assume weak learning on the importance weighted
distributions created for the oracle (``weak'') learning algorithm.

\end{document}
