%% LyX 1.3 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass{llncs}
\newcommand{\shrink}[1]{}
%\usepackage[T1]{fontenc}
%\usepackage[latin1]{inputenc}
\usepackage{graphicx,latexsym,amsmath,amssymb}

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

\def\cd {{\cal D}}

%\usepackage{babel}
%\makeatother
\begin{document}

\title{Reductions From Supervised Learning To Classification}

\author{Alina Beygelzimer \and Varsha Dani \and Tom Hayes \and John Langford \and Bianca Zadrozny}
\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 in other supervised learning
domains. 
\end{abstract}

\section{Introduction}


\subsection{Motivation}

There are many natural learning problems such as {}``classification'',
{}``cost sensitive classification'', {}``ranking'', {}``reinforcement
learning'', {}``outlier detection'', and others. There are two
extremes we use to cope with the many learning problems: 

\begin{enumerate}
\item Attempt to analyze every problem in great detail, coming up with unique
analysis and algorithms for each problem.
\item Construct reductions from unanalyzed problems to a thoroughly analyzed
problem, attempting to transfer this thorough analysis into new domains.
\end{enumerate}
We investigate approach (2). The reductions we analyze simultaneously:

\begin{enumerate}
\item Show how related these natural problems are. Two learning problems
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 older theories into new domains.
\item Provide algorithms for solving these natural learning problems, when
combined with a basic learning algorithm.
\end{enumerate}
In addition to the above theoretical motivations, there appears to
be some significant evidence (see \cite{costing}, \cite{Boosting},
\cite{ECOC}) that this style of analysis often accurately predicts
good learning algorithm constructions. 


\subsection{Method}

A natural question when working with reductions is: {}``What should
we reduce to and from?'' Our answers are {}``to classification''
and {}``from any formalized prediction problem''. The choice of
classification is motivated on three counts:

\begin{enumerate}
\item Classification has been previously studied in significant detail.
\item Classification seems to be the simplest possible prediction problem.
\item Classification performance is upper and lower boundable under the
(occasionally met) assumption that data is drawn i.i.d. from some
(unknown but fixed) distribution $D$.
\end{enumerate}
Two reasonable alternatives are density estimation (which satisfies
(1) but not (2) and (3)) and regression (which satisfies (1) and (3),
but not (2)). We use classification because the strongest case can
be made for it. 

Another natural question is {}``What is a good reduction?'' It is
easy to agree that a good reduction has:

\begin{enumerate}
\item Good performance in the formalized problem's metric of success.
\item Low computational overhead.
\item Few invocations of the classifier.
\item Parallelizes invocations of the classifier.
\item Obeys the invariants the classification algorithm needs to succeed.
\end{enumerate}
Of the above, (1) is tricky. We \emph{know} that classification is
hard in general so it's difficult to say that any algorithm using
a classifier as a subroutine can perform well. To address this we
make an assumption: 

\begin{center}For the classification problems created by our reduction,
our classifier learning algorithm succeeds with error rate $\epsilon$
or less. \end{center}

This assumption is powerful because it allows us to abstract away
the difficulty of classification (impossible in the worst case, but
often feasible in practice) and focus on the efficiency and error
transform characteristics of the reduction itself. 

This assumption also invites abuse. Some very difficult problems (such
as predicting plain text given examples of cipher text and plain text)
can be phrased as learning problems. An analysis given this assumption
may suggest that a reduction will perform well on this problem. This
is not so, simply because the assumption is not met in practice. 

A more subtle form of assumption misuse occurs when an otherwise-reasonable
reduction fails to obey (5). One standard way this occurs is when
the classification problem created is too noisy. If we considered
{}``Adaboost'' in this framework, we might say that it fails to
obey (5) because it tends to concentrate learning on the subset of
examples which are noisy. Another common misuse, which occurs in {}``Bagging'',
is failing to produce a dataset which is drawn i.i.d. from the appropriate
distribution. 


\subsection{Prior Work}

There is actually quite a bit of significant prior work which is
deeply related to the reductions analyzed here, (perhaps this attests
to the natural character of the notions considered). One of the goals
of this paper is unifying these algorithms in a common framework.

Boosting algorithms \cite{Boosting} are about reducing (typically
binary but sometimes multiclass) classification with a small error
rate to solving importance weighted classification problems with a
loss rate of nearly $\frac{1}{2}$, a rather surprising statement.
Some boosting variants have suffered with respect to criterion (5)
above: they end up placing too much emphasis on noisy datapoints (see
\cite{noise_boost} for an analysis). 

Bagging \cite{Bagging} can be thought of as a self-reduction of classification
to classification. Bagging turns out to be useful because it turns
learning algorithms with a high {}``variance'' (dependence on the
exact feature values) into a voting classifier with a lower {}``variance''.
Bagging also suffers with respect to criterion (5) since the subproblems
it creates are not independently distributed according to the original
distribution. 

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

Pitt and Warmuth \cite{PW} also constructed and analyzed a form of
reduction between classification problems.  The reductions presented
here agree in the sense that we focus on preservation of accuracy but
differ because they are between supervised learning \emph{domains}
(defined next) rather than between sets of classification problems.
Our definitions and requirements are also representation independent
and ``turing'' making the setting directly applicable to ECOC,
Boosting, and other common transformations.

\subsection{Layout}

\begin{enumerate}
\item We first formally define several natural problems. These problems
are the ones that we reduce from and to.
\item We state reductions to binary classification.
\item We state reductions to importance weighted classification.
\item We discuss the meaning of these results. 
\end{enumerate}

\section{Basic Definitions}

\subsection{Supervised Learning}

We first formalize some basic definitions which we rely upon throughout
the paper.

\begin{defn}
(Supervised Learning Domain) A supervised learning domain is % specified by 
a set $(K,Y,l)$ where $K$ is some extra information available at training
time and to the loss function, $Y$ is the space of predictions and
$l:K\times Y\rightarrow[0,\infty)$ is a loss function.
\end{defn}
A domain is (implicitly) a set of learning problems, each of which
requires more information to be fully specified.

\begin{defn}
(Supervised Learning Problem) A supervised learning problem is a tuple 
$(D,X,K,Y,l)$, where $(K,Y,l)$ is a supervised learning domain, and $D$ 
is a distribution over $X\times K$.
\end{defn}
A supervised learning problem is essentially a domain plus the extra
information necessary to make the problem well specified. The goal
% ab: the term "extra information" here may be confused with the 
% "extra information" used in defining a learning domain.
in solving the supervised learning problem is to find a ``hypothesis'' $h:X\rightarrow Y$
which minimizes the loss with respect to $D$, i.e.  \[
\arg\min_{h}E_{(x,k)\sim D}l(k,h(x)).\]
Naturally, 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.
\begin{defn}
(Supervised Learning Algorithm) A supervised learning algorithm $A$
takes as input a set of examples $(X\times K)^m$ and outputs a
hypothesis $h:X\rightarrow Y$.
% ab: we need to say that the set of examples is finite.
% Kleene closure (by definition) generates an infinite set.
\end{defn}
Standard supervised learning algorithms such as {}``support vector
machines'' and {}``logistic regression'' fit this definition. A
{}``good'' supervised learning algorithm approximately achieves the
learning problem goal for natural learning problems in some domain.
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 $X$.  However our idealized supervised learning algorithm
does as an abstraction.

We instantiate several domains next to give some intuition (and for
future use).

\begin{example}
(Binary Classification) Binary classification is a supervised learning
domain where $K=Y=\{0,1\}$ and $l(k,y)=I(k\neq y)$. 
\end{example}
The binary classification domain is appropriate when we want a predictor
for {}``right'' or {}``wrong'' choice. 

\begin{example}
(Multiclass Classification) Multiclass classification is a supervised
learning domain where $Y=K=\{1,...,\ell\}$ and $l(k,y)=I(k\neq y)$.
\end{example}
Multiclass classification is the obvious generalization of classification
to situations with more than two choices.

\begin{example}
(Importance Weighted Classification) Importance weighted
classification is a supervised learning domain where
$Y=\{1,...,\ell\}$, $K=\{1,...,\ell\}\times[0,\infty)$ and
$l((k,i),y)=iI(k\neq y)$.  Since all importance weighted
classification problems are unchanged under a rescaling of importance,
we assume that $E_{(x,k,i) \sim D} i = 1$.
\end{example}
The importance weighted classification problem is appropriate when
we want a predictor, but some of these predictions are more important
than others.

\begin{example}
(Manyright Classification) Manyright classification is a supervised
learning domain where $Y=\{1,...,\ell\}$, $K=2^{\{1,...,\ell\}}$
and $l(k,y)=I(y\not\in k)$.
\end{example}
Manyright classification is a generalization of multiclass classification
to situations with multiple {}``right'' choices.

\begin{example}
(Cost Sensitive Classification) Cost sensitive classification is a
supervised learning domain where $Y=\{1,...,\ell\}$,
$K=[0,\infty)^{\ell}$ and $l(k,y)=k_{y}$. The cost sensitive
classification problem is unchanged under two transformations: 1) for
each example subtracting a constant so that the minimal cost is zero
2) rescaling the costs.  Using these symmetries, we assume that
$\min_i c_i = 0$ and $\sum_i c_i = 1$.
\end{example}
Cost sensitive classification is appropriate when each choice has
a varying value. The binary version of this problem is essentially
equivalent to importance weighted binary classification.

\subsection{Reductions}
We propose the notion of error limiting reducibility between learning
domains. Here, one learning domain reduces to another if we can solve
problems in the first domain using a black box that solves problems in
the second.  The meta-algorithm that does this our reduction.  We are
fundamentally interested in reductions that perform well whenever the
oracle learning algorithm performs well. This leads to the following
definition.

\begin{defn}
(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 reduction must satisfy the following property for some monotone 
non-decreasing function $g: [0,\infty)\rightarrow [0,\infty)$ with $g(0)=0$.

\vskip .1in \noindent (Error Limitation) For all $X$, and for all
distributions $D$ over $X\times K$, $$E_{(x,k)\sim D}l(k,h(x))\leq
g(\epsilon),$$ where $\epsilon= \max_{\textrm{invoked } D'}E_{(x',k')\sim D'}l'(k',h_{D'}(x'))$
and $h$ is the output of an invocation of $A'$ on examples drawn from
a distribution $D'$ induced on $X'\times K'$ by the reduction (defined
next).
\end{defn}

\noindent
% ab: you don't want to say (x,k)^m 
To relate the performance of the reduction to the performance of the
oracle $A'$, we must specify a distribution $D'$ for each invocation
of $A'$. A set of examples $S=\{(x_1,k_1),\ldots,(x_m,k_m)\}$ input to
the reduction induces a measure $D_S$ over $X'\times K'$.  This
distribution is given by: $$D_S(x',k')=E_{S' \sim \textrm{ reduction on }S}\frac{\#(x',k')}{|S'|}$$
where $\#(x',k')$ is the number of times $(x',k')$ appears in $S'$.  The
measure $D_S$ is a measure on a discrete set of points. We extend this
to a more general measure by taking the expectation over $S$. More
precisely, $D'=E_{S}D_S$.  This gives us a well defined distribution
to measure performance with respect to, given a distribution on the
inputs of the reduction.
                                                                                
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.

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.

It is not hard to see that reductions compose.

\begin{prop}
If $R$ is a reduction from domain $E_1$ to $E_2$ and $R'$ 
is a reduction from domain $E_2$ to $E_3$, then the composition $R\cdot R'$
is a reduction from $E_1$ to $E_3$.
\end{prop}
%\begin{proof} Please fill me in.  -John
%
%\end{proof}

Our definition of a reduction is reminiscent of 
the definition of a Turing reduction 
in complexity theory. In both cases a reduction from problem $A$ to problem $B$
is a procedure that solves $A$ using $B$ as a black box. (In the standard
definition of a Turing reduction, both $A$ and $B$ are sets, and a reduction
decides the membership in $A$ using a membership oracle for $B$.)
However, there are several important differences between reductions
in machine learning and complexity theory. First, in complexity theory
reductions are viewed mainly as means for classifying the relative hardness of
problems. This is motivated by the fact that showing any explicit problem
to be hard is seemingly difficult, so one turns to tools
for showing relative hardness.
If $A$ reduces to $B$, it is interpreted as saying that $B$ is at
least as hard as $A$; in particular, if $A$ is firmly believed to be hard, then
a reduction indicates that $B$ is also hard 
(indeed, otherwise $A$ would be easy). 

In the context of machine learning, reductions are actually 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 for a Turing reduction to be meaningful, it has to
be computationally limited.  If a reduction yields a solution to $A$,
it should not be due to significant computations hidden in the
reduction itself.  Thus restricting the power of a reduction is a way
of enforcing that the reduction does something qualitatively different
than directly solving $A$, i.e., uses its oracle in a meaningful
way. In the context of learning, on the other hand, reductions without
a restriction of the computational power are still meaningful. The
hardness of solving a learning problem is not so much due to the lack
of computational power as to the lack of {\it information} available
to the algorithm when it is run.  (The learning domain is typically
known, but the learning {\it problem} is given only in the form
examples.)  Computational analogs of learning reductions (capturing
efficient transformations of algorithms) were investigated elsewhere
by Pitt and Warmuth \cite{PW}.

The error limitation in our definition of a reduction states
that for any $D$, the loss incurred by the reduction
is upper bounded by a function of the loss incurred by the oracle on
the derived problems $D'$.  Notice that this does not necessarily 
force the reduction to use $A'$ in a nontrivial way; for some choices
is may be the case that a learning domain is (near) optimally solvable, 
and the reduction does well regardless of the performance of the oracle. 
Reductions from easy, solvable domains may simply be uninteresting.
In complexity theory, such uninteresting cases are ruled out by 
considering only ``efficient reductions'' that are in some computational 
sense weaker than the best known algorithms for the problems they reduce from.

\subsection{Reduction properties}

There are several additional properties of reductions which seems
worth analyzing. 

\subsubsection{Double Reduction}

Suppose we have a reduction $R$ from $(Y,K,l)$ to $(Y',K',l')$.  

A reduction $R$ is \emph{Learning Preserving} if there exists a
reduction $R'$ from $(Y',K',l')$ back to $(Y,K,l)$ such that for every
oracle learning algorithm $A'$, $R'(R(A'))$ solves the same set of
problems as $A'$ and for every learning oracle $A$, $R(R'(A))$ solves
the same set of problems as $A$.

The double reduction property implies that a reduction is not reducing
easy instances to hard problems for the oracle learning algorithm.

Satisfying this definition appears very difficult, but we can
sometimes show that at least $R'(R(A'))$ solves the same set of
problems as $A'$.

\subsubsection{Time efficiency}

Reductions have some amount of computational overhead which is useful
to quantify.  We quantify the computational efficiency of the
reduction assuming that all calls to the oracle take unit time.

\subsubsection{Call efficiency}
\label{sec:call}

The call efficiency is an important parameter when the amount of work
being done by the oracle learning algorithm is greater than the amount
of work being done by the reduction.  The call efficiency can be
quantified in several ways:
\begin{enumerate}
\item The total number of calls.
\item Whether the calls are adaptive or parallelized.
\item The maximum expected number of samples input to the oracle learning algorithm.
\end{enumerate}
It's worth noting that parallel calls to the oracle can often be
turned into one call to the oracle (at least theoretically).  Suppose
we have $T$ parallel sample sets $S_t$ inputs to the oracle learning
algorithm all using the same feature space $X'$ and producing
hypotheses $h_t$.  We could instead create a new sample set $S = \{
((x,t),k) : (x,k) \in S_t \}$ call the oracle learning algorithm to
get a hypothesis $h$ and define $h_t(x) = h(x,t)$.  It is unclear
whether this is a better mechanism in practice.

\subsection{Independence Preservation}

Many common learning algorithms are built under the assumption that
samples are drawn independently.  Reductions which take an
independently drawn dataset and construct dependent datasets for the
oracle learning algorithm are sometimes undesirable for this reason.

\section{Reductions, the easy way}\label{the-easy-way}

The learning problems above have an 'easy' direction for reduction
related to whether a particular problem is definable as a subset of
other problems. 

For example, solving binary classification with importance weighted
binary classification is easy because importance weighted binary classification
for $i=1$ is identical to binary classification. Figure \ref{fig:easy}
shows the easy direction for these reductions. The remainder of this
paper is devoted to reductions in the other {}``hard'' direction.
\vspace{-1cm}
%
\begin{figure}
\includegraphics[scale=0.75]{easy.eps}
\caption{\label{fig:easy} A figure showing the {}``easy'' direction for
reduction amongst the learning problems discussed here.}
\end{figure}



\section{Reductions to Binary Classification}

In this section we discuss the characteristics of several reductions
to the binary classification domain.

\subsection{Reduction from Importance Weighted Classification to Classification}

The ``Costing'' algorithm \cite{costing} is a reduction of importance
weighted classification to classification with the following
characteristics:

\begin{tabular}{|c|c|c|c|c|}
\hline 
$g(\epsilon)$&
Learn Preserve&
Time&
Call&
Indep. Preserve\tabularnewline
\hline
$\epsilon E_{(x,y,i)\sim D}i$&
No&
$O(Tm)$&
$T$ parallel&
Yes\tabularnewline
\hline
\end{tabular}

\subsection{Reduction from Multiclass Classification to Binary Classification}

There are several well known methods of reduction which we analyze for
error efficiency next.  Before we start, it's 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 $\ell$ classifiers $h_{i}$,
using the mapping:\[
(x,y)\rightarrow(x,I(y=i))\]
In order to construct a multiclass classifier from the binary classifier
we use the following procedure: 

Predict$(h,x)$ 
\begin{enumerate}
\item If there exists a label $i$ such that $h_{i}(x)=1$ then predict
$i$, breaking ties with randomization.
\item Otherwise predict randomly.
\end{enumerate}
This reduction has the following properties.

\begin{tabular}{|c|c|c|c|c|}
\hline 
$g(\epsilon)$&
Learn Preserve&
Time&
Call&
Indep. Preserve\tabularnewline
\hline
$(\ell - 1) \epsilon$&
No&
$O(|S| \ell)$&
$\ell$ parallel&
Yes\tabularnewline
\hline
\end{tabular}
\begin{thm}
(One-against-all error efficiency) If the binary classifiers have
error rate $\epsilon$, the one-against-all reduction has error rate
at most: \[
(\ell-1)\epsilon\]
\end{thm}
\begin{proof}
A {}``false negative'' when the output should be $1$ but is actually
$0$ produces an error a $\frac{\ell-1}{\ell}$ fraction of the time. 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 creating errors is: $\frac{\frac{\ell-1}{\ell}}{1}=\frac{\ell-1}{\ell}$, $\frac{\frac{n}{n+1}}{n}=\frac{1}{n+1}$,
and $\frac{1}{n+1}$. Taking the maximum, we get $\frac{\ell-1}{\ell}$.
Multiplying by $\ell$ (because we have $\ell$ opportunities to err, one
for each classifier) we get the bound.
\end{proof}
Note, that the many-calls to one call trick in section \ref{sec:call}
(call efficiency) applies here.

\subsubsection{The Tree Reduction}

In the tree reduction we construct $\ell-1$ binary classifiers which
distinguish between the labels using a binary tree. The tree has depth
$\log_{2}\ell$, and each internal node is associated with a set of labels
that can reach the node, assuming each classifier above it predicts
correctly. The set of labels at that node is split into two sets of
half the size, and a classifier is learned to distinguish between
the two sets of labels. 

Predictions are made by following the chain of classifications down to
the leaves, which are associated with a unique label. This reduction
has the following properties:

\begin{tabular}{|c|c|c|c|c|}
\hline 
$g(\epsilon)$&
Learn Preserve&
Time&
Call&
Indep. Preserve\tabularnewline
\hline
$\epsilon \log_2 \ell$&
No&
$O(|S| (\ell - 1))$&
$\ell - 1$ parallel&
Yes\tabularnewline
\hline
\end{tabular}

Note, that the many-calls to one call trick in section \ref{sec:call}
(call efficiency) can be applied here.

\begin{thm}
(Tree error efficiency) If the binary classifiers have error rate
$\epsilon$, the tree reduction has error rate at most: \[
\epsilon\log_{2}\ell\]

\end{thm}
\begin{proof}
An error occurs only if some classifier on the path from root to leaf
errs.
\end{proof}

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

In the (limiting) ECOC reduction \cite{ECOC}, we learn a classifier
for each of the $2^{\ell}$ subsets of labels. Any particular label will
have a $2^{\ell}$ length binary vector associated with it corresponding
to inclusion or not in the subset. Predictions are made by choosing
the label smallest hamming distance to the classifications. 

\begin{tabular}{|c|c|c|c|c|}
\hline 
$g(\epsilon)$&
Learn Preserve&
Time&
Call&
Indep. Preserve\tabularnewline
\hline
$4 \epsilon $&
No&
$O(|S| 2^\ell)$&
$2^\ell$ parallel&
Yes\tabularnewline
\hline
\end{tabular}

The ECOC reduction is typically applied to a subset of the power set
rather than the full power set. The same basic result (with a worsened
constant but much smaller running time) applies.  

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

\begin{thm}
(ECOC error efficiency) If the binary classifiers have error rate
$\epsilon$, the ECOC reduction has error rate less than:\[
4\epsilon\]
\end{thm}
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 will be highly
\emph{dependent}.

\begin{proof}
When the error rate is zero, the correct label will be consistent
with every classifier (out of $2^{\ell}$) and wrong labels will be consistent
with only half of the classifiers ($2^{\ell-1}$). In order to misclassify
the multiclass label, we must have at least $2^{\ell-2}$ classifiers
err simultaneously. 

Since every multiclass error implies at least $\frac{1}{4}$ of the
binary classifiers erred, a binary error rate of $\epsilon$ can produce
at most a multiclass error rate of $4\epsilon$
\end{proof}

\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{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:

\begin{tabular}{|c|c|c|c|c|}
\hline 
$g(\epsilon)$&
Learn Preserve&
Time&
Call&
Indep. Preserve\tabularnewline
\hline
$e^{-2T (1/2 - \epsilon)^2)}$&
No&
$O(|S|T)$&
$T$ Adaptive&
Yes\tabularnewline
\hline
\end{tabular}

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.

\subsection{Manyright Classification}

\subsubsection{The One-against-all importance Reduction }

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

In the one-against-all reduction, we learn $\ell$ classifiers, one for
each possible output label using data from the mapping:\[
(x,y_{1},y_{2},...,y_{n})\rightarrow(x,I(\ell\in\{
y_{1},...,y_{n}\}),i_{I(\ell\in\{ y_{1},...,y_{n}\})})\] where
$i_{0}=\frac{\ell}{n+1}$ and $i_{1}=\frac{\ell}{n+1}$ if $\ell\leq
n^{2}+n$ or $i_{1}=\frac{\ell-n}{n}$ for $\ell\geq n^{2}+n$.  We use
the same prediction function as in section
\ref{sub:The-one-against-all-reduction}.

The reduction has the following characteristics:

\begin{tabular}{|c|c|c|c|c|}
\hline 
$g(\epsilon)$&
Learn Preserve&
Time&
Call&
Indep. Preserve\tabularnewline
\hline
$\frac{\ell}{n+1} \epsilon$&
No&
$O(|S| \ell)$&
$\ell$ parallel&
Yes\tabularnewline
\hline
\end{tabular}

The value of $g(\epsilon)$ is actually slightly better than for the
standard one-against-all reduction for multiclass to binary.  We
tested the reduction on several UCI multiclass datasets using boosted
naive bayes as the oracle learning algorithm and discovered the
following average test set performance:

\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline 
reduction&
splice&
solar&
anneal&
sat&
letter&
pendigits&
soybean
\tabularnewline
\hline 
One-against-all&
$0.0652$&
$0.1630$&
$ 0.0054$&
$0.183$&
$0.4104$&
$0.1462$&
$0.188$
\tabularnewline
\hline
One-against-all imp.&
$0.0652$&
$0.1558$&
$0.00037$&
$0.018$&
$0.3736$&
$0.13815$&
$0.188$
\tabularnewline
\hline
\end{tabular}

Apparently, there is a small benefit to using this reduction over the
simple one-against-all reduction.  Next, we prove the $g(\epsilon)$
claim.
\begin{thm}
(Manyright classification error efficiency) Let $c_{\ell n}=\frac{\ell}{n+1}$
for $\ell\leq n^{2}+n$ or $c_{\ell n}=\frac{\ell+1}{n+1}-\frac{n}{\ell}$ otherwise.
If the binary classifiers have (normalized) loss rate $\epsilon$,
the one-against-all reduction has error rate at most:\[
\epsilon E_{x,y_{1},...,y_{n}\sim D}c_{\ell n}\leq\epsilon E_{x,y_{1},...,y_{n}\sim D}\frac{\ell}{n}\]

\end{thm}
This theorem should be compared directly with the one-against-all
reduction to binary classification which had an error efficiency of
$\ell-1$. Here, with $n=1$, we get $c_{\ell n}=\frac{\ell+1}{2}-\frac{1}{\ell}=\frac{(\ell+2)(\ell-1)}{2\ell}$
implying an error efficiency of about $\frac{\ell}{2}$, or about half
the error rate of the earlier reduction. Reducing to importance weighted
binary classification has an improved efficiency. 

\begin{proof}
Outline: For a particular example with $n$ {}``right'' labels out
of $\ell$ possible labels. We first show that there are $3$ possible
{}``most efficient'' methods for a binary classifier to induce a
multiclass error. These possibilities are: 1) a single false positive
error, 2) all possible false negative errors, or 3) (1) and (2). After
showing these are the only possibilities, we analyze which is the
worst, and then take an expectation over $n$ and $\ell$. 

There are two forms of errors, false positive and false negative.
It is never more efficient to have multiple false positive errors.
This is because for any number $n\geq p>0$ 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 err with probability
$1$. 

If the optimal error rate occurs for $f<n$ false negatives then there
must be $1$ false positive (since the error rate is $0$ otherwise).
For $f<n$ false negatives and $1$ false positive, we have an error
rate of $\frac{1}{n-f+1}$ using an importance $fi_{1}+i_{0}$ giving
us an efficiency of $\frac{\frac{1}{n-f+1}}{fi_{1}+i_{0}}$. Since
\[
\frac{\frac{1}{n-f}}{(f+1)i_{1}+i_{0}}>\frac{\frac{1}{n-f+1}}{fi_{1}+i_{0}}\]
 \[
\Leftrightarrow\frac{fi_{1}+i_{0}}{n-f}>\frac{(f+1)i_{1}+i_{0}}{n-f+1}\]
\[
\Leftrightarrow(fi_{1}+i_{0})(n-f+1)>((f+1)i_{1}+i_{0})(n-f)\]
\[
\Leftrightarrow fi_{1}+i_{0}>i_{1}(n-f)\]
\[
\Leftrightarrow i_{0}>i_{1}(n-2f)\]
We can always improve the error efficiency by increasing $f$ whenever
$i_{0}>i_{1}(n-2f)$ and by decreasing $f$ otherwise. Consequently,
the number of false negative errors is either $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: one or zero
false positives. These cases have an error rate of $\frac{\ell-n}{\ell}$
and $1$ with an importance consumption of $ni_{1}$ or $ni_{1}+i_{0}$
implying error efficiencies of $\frac{\frac{\ell-n}{\ell}}{ni_{1}}$ and
$\frac{1}{ni_{1}+i_{0}}$. 

The next step is determining which of these failure modes is {}``most
efficient'' in the sense that it induces the largest number of multiclass
error for the least cost in {}``importance''.

The maximal error efficiency is $\max\left\{ \frac{\ell-n}{\ell ni_{1}},\frac{1}{ni_{1}+i_{0}},\frac{1}{(n+1)i_{0}}\right\} $.
There are two regimes for this maximum, $\ell\geq n^{2}+n$ and $\ell\leq n^{2}+n$. 

For $\ell\leq n^{2}+n$, we get:$\max\left\{ \frac{\ell-n}{\frac{\ell^{2}n}{n+1}},\,\frac{1}{\ell},\,\frac{1}{\ell}\right\} =\frac{1}{\ell}$.

For $\ell\geq n^{2}+n$, we get: $\max\left\{ \frac{1}{\ell},\frac{1}{\ell-n+\frac{\ell}{n+1}},\frac{1}{\ell}\right\} =\frac{1}{\ell}$. 

Since the maximal error efficiency is $\frac{1}{\ell}$ and there are
$\ell$ 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}{\ell}i_{1}+\frac{\ell-n}{\ell}i_{0}=\frac{\ell}{n+1}$
for $\ell\leq n^{2}+n$ or $(\frac{\ell+1}{n+1}-\frac{n}{\ell})$ for $\ell\geq n^{2}+n$.
Taking the expectation over $n$ and $\ell$ drawn according to $D$,
we get the result. 
\end{proof}

\subsection{Multiclass cost sensitive classification}

Here we attempt to reduce multiclass cost sensitive classification
to simpler problems.


\subsubsection{The One-wrong reduction}

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

The difficulty with this reduction is that it can be simply impossible
to produce a predictor with a small error rate. In particular, 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.  

The characteristics of this reduction are given in the following
table:

\begin{tabular}{|c|c|c|c|c|}
\hline 
$g(\epsilon)$&
Learn Preserve&
Time&
Call&
Indep. Preserve\tabularnewline
\hline
$\epsilon$&
No&
$O(|S|)$&
$1$&
Yes\tabularnewline
\hline
\end{tabular}

\begin{thm}
(error transformation) If the importance weighted classifier has loss
rate $\epsilon$, then the cost sensitive classifier has expected
cost less than $\epsilon$.
\end{thm}
\begin{proof}
Assume that \[
\epsilon=E_{x,y,i\sim D^{*}}iI(c(x)\neq y)\]
\[
=E_{x,\ell_{1},...,\ell_{l}\sim D,y\sim\{1,...,l\}}(\max_{i}\ell_{i}-\ell_{y})I(c(x)\neq y)\]
\[
=E_{x,\ell_{1},...,\ell_{l}\sim D,y\sim\{1,...,l\}}\max_{i}\ell_{i}I(c(x)\neq y)-E_{x,\ell_{1},...,\ell_{l}\sim D,y\sim\{1,...,l\}}\ell_{y}I(c(x)\neq y)\]
\[
=\frac{l-1}{l}E_{x,\ell_{1},...,\ell_{l}\sim D}\max_{i}\ell_{i}-E_{x,\ell_{1},...,\ell_{l}\sim D}\frac{\sum_{i}\ell_{i}-\ell_{c(x)}}{l}\]
\[
=E_{x,\ell_{1},...,\ell_{l}\sim D}\frac{(l-1)\max_{i}\ell_{i}-\sum_{i}\ell_{i}+\ell_{c(x)}}{l}\]
\[
=E_{x,\ell_{1},...,\ell_{l}\sim D}\frac{\ell_{c(x)}-\max_{i}\ell_{i}}{l}+\max_{i}\ell_{i}-E_{i\sim\{1,...,l\}}\ell_{i}\]
Rewriting, we get: \[
E_{x,\ell_{1},...,\ell_{l}\sim D}\ell_{c(x)}=\epsilon-l[E_{x,\ell_{1},...,\ell_{l}\sim D}\max_{i}\ell_{i}-E_{i\sim\{1,...,l\}}\ell_{i}]+E_{x,\ell_{1},...,\ell_{l}\sim D}\max_{i}\ell_{i}\]


\[
=\epsilon-E_{x,\ell_{1},...,\ell_{l}\sim D}(l-1)\max_{i}\ell_{i}-\sum_{i}\ell_{i}\]
\[
\leq\epsilon\]
Where the last inequality follows because on of the $\ell_{i}$ is $0$. 
\end{proof}

\subsubsection{sdf}

Nothing here is coherent yet. 

Suppose we want to reduce from multiclass cost sensitive classification
to cost sensitive classification. Then what?

Suppose we pick some threshold $w$. For example below the threshold,
we try to learn to classify {}``1'', while for those above we learn
to classify {}``0''. What should the importance weights be?

Choose importance weights so that the most efficient error mechanism
is completely false negative and 1 or 0 false positives.

No more than 1 false positive: Suppose we have $2$ false positives
with costs $c_{1}$ and $c_{2}$ and importances $i_{1}$ and $i_{2}$.
Suppose we also have $p>0$ true positives with an average cost of
$c_{p}$. Then, the change in the expected cost is $\frac{c_{1}+c_{2}}{p+2}$
incurring a loss of $i_{1}+i_{2}$. Suppose instead that we committed
each individual false positive independently. Then, $\frac{c_{1}}{p+1}+\frac{c_{2}}{p+1}>\frac{c_{1}+c_{2}}{p+2}$
, implying a greater error efficiency. The same is true for $p=0$.

Complete false negative: Must show that it is always desirable to
decrease the number to $0$ or increase the number to all. 

$\frac{E_{l}c_{l}}{\sum_{l:c_{l}<w}i_{l}},\frac{c_{l}}{i_{l}+\sum_{l:c_{l}<w}i_{l}},\frac{1}{i_{l}}\frac{c_{l}+nc_{w}}{n+1}$


\section{Conclusion}

The definitions of reduction we outline here appear to includ a
variety of past 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{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{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'', ???
\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. 
\bibitem{costing}Bianca Zadrozny, John Langford, and Naoki Abe Cost Sensitive Learning
by Cost-Proportionate Example Weighting ICDM 2003 \end{thebibliography}

\end{document}
