%% 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[oneside,english]{amsart}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{graphicx}

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

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

\title{Reductions From Supervised Learning To Classification}

\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 supervised learning
problems. 
\end{abstract}
\maketitle

\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, simply due to the natural
character of this construction. One of the goals of this paper is
unifying the analysis of 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. 


\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 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 $(D,X,K,Y,l)$
where $D$ is a distrbution over $X\times K$, $Y$ is a prediction
space, and $l$ is a loss function $l:K\times Y\rightarrow[0,\infty)$. 
\end{defn}
A supervised learning problem is essentially a domain plus the extra
information necessary to make the problem well specified. The goal
in solving the supervised learning problem is to find a function $f:X\rightarrow Y$
which minimizes the loss with respect to $D$. \[
\arg\min_{f}E_{(x,k)\sim D}l(k,f(x))\]


\begin{defn}
(Supervised Learning Algorithm) A supervised learning algorithm $A$
takes as input a set of examples $(X\times K)^{*}$ and outputs a
prediction function $f:X\rightarrow Y$.
\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 don't actually work for arbitrary $X$,
but our idealized supervised learning algorithm does.

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

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

\begin{defn}
(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)$. 
\end{defn}
The importance weighted classification problem is appropriate when
we want a predictor, but some of these predictions are more important
than others.

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

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

\begin{defn}
(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}$.
\end{defn}
Cost sensitive classification is appropriate when each choice has
a varying value. The binary version of this problem is essentially
isometric to importance weighted binary classification.


\subsection{Reductions}

A reduction is a meta-algorithm which uses another learning algorithm
as an oracle (or black box) to handle some critical subproblem of
another learning problem. We are fundamentally interested in meta-algorithms
which perform well whenever the oracle learning algorithm performs
well. A learning algorithm is said to perform $\epsilon$ well with
respect to a distribution $D'$ if: \[
f_{D'}^{*}<\max_{D}\min_{f}E_{x,k\sim D}l(k,f(x))\]
 A performance metric implies that we must specify a distribution
$D'$ for each invocation of the black box. In general, a set of data
$(x,k)^{m}$input to the meta-algorithm induces a a measure $D^{'}|(x,k)^{m}((x',k')^{n})$
over $(x',k')^{n}$ given $(x,k)^{m}$. This distribution can be made
into a distribution $D'|(x,k)^{m}$ over $X'\times K'$ by averaging
over the index, \[
D^{''}|(x,k)^{m}(x',k')=E_{i\sim\{1,...,n\}}D_{i}'|(x,k)^{m}\]
where $D_{i}'$ is the measure on the $i$th component of $(x',k')^{m}$.
The measure $D''|(x,k)^{m}$ is often a measure on a discrete set
of points. We extend this to a more general measure by taking the
expectation over $(x,k)^{m}$. In particular, $D'=E_{(x,k)^{m}\sim D}D''|(x,k)^{m}$.
This gives us a well defined distribution to measure performance with
respect to, given a distribution on the inputs of the meta algorithm. 

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

\begin{defn}
(Supervised Learning Reduction) A supervised learning reduction $R_{(K,Y,I)\rightarrow(K',Y',l')}(A')$
given a supervised learning algorithm $A'$ for domain $(K',Y',l')$
is a supervised learning algorithm for domain $(K,Y,l)$ satisfying
the following properties: 
\end{defn}
\begin{enumerate}
\item (Error Transformation) $\forall A'$, $\forall X$, $\forall D\sim X\times K$,
if $A'$ performs well on all invoked problems $(D'(D),X',K',Y',l')$
then $R(A')$ performs well on $(D,X,K,Y,l)$.
\item (Error Transformation II) $\forall A'$, $\forall X$, $\forall D\sim X\times K$,
if $A'$ performs badly on all invoked problems $(D'(D),X',K',Y',l')$
then $R(A')$ performs badly on $(D,X,K,Y,l)$.
\item (Nontriviality) $\exists A',X,D$ such that $A'$ performs well. 
\end{enumerate}
The error transformation property is the important element of the
above definition. It states the the performance of the derived algorithm
on $D$ is intrinsically related to the performance of $A'$ on the
derived problems $D'$. This implies that $A'$ is used in a nontrivial
way to solve the prediction problem.


\subsection{Reduction analysis method: Error transformation efficiency}

One of our primary methods for comparing reductions is according to
their error transformation efficiency. A typical theorem statement
has the form {}``If the oracle has error rate $\epsilon$, then the
reduction has error rate $f(\epsilon)$'' for some continuous $f(x)$
with $f(x)=0$. 


\subsection{Reduction Analysis method: Double reduction}

Suppose we have two reductions $R_{(X,Y,l)\rightarrow(X',Y',l')}$
and $R_{(X',Y',l')\rightarrow(X,Y,L)}$. We would like to observe
that: $R_{(X',Y',l')\rightarrow(X,Y,L)}(R_{(X,Y,l)\rightarrow(X',Y',l')}(A'))=A'$.
In particular, this implies that the set of problems solvable by $A'$
are the same as the set of problems solvable by the double reduction
$R_{(X',Y',l')\rightarrow(X,Y,L)}(R_{(X,Y,l)\rightarrow(X',Y',l')}(A'))$. 

This desire is too strong to hope for in general, but we can sometimes
prove weakenings of this statement. 


\section{Reductions, 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.

%
\begin{figure}
\includegraphics{easy.eps}


\caption{\label{fig:easy} A figure showing the {}``easy'' direction for
reduction amongst the learning problems discusses here.}
\end{figure}



\section{Reductions to Binary Classification}


\subsection{Reduction from Importance Weighted Classification to Classification}


\subsection{Reduction from Multiclass Classification to Binary Classificaton}

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 $k$ classifiers $h_{\ell}$,
using the mapping:\[
(x,y)\rightarrow(x,I(y=\ell))\]
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 $\ell$ such that $h_{\ell}(x)=1$ then predict
$\ell$, breaking ties with randomization.
\item Otherwise predict randomly.
\end{enumerate}
\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: \[
(k-1)\epsilon\]

\end{thm}
\begin{proof}
A {}``false negative'' when the output should be $1$ but is actually
$0$ produces an error a $\frac{k-1}{k}$ 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{k-1}{k}}{1}=\frac{k-1}{k}$, $\frac{\frac{n}{n+1}}{n}=\frac{1}{n+1}$,
and $\frac{1}{n+1}$. Taking the maximum, we get $\frac{k-1}{k}$.
Multiplying by $k$ (because we have $k$ opportunities to err, one
for each classifier) we get the bound.
\end{proof}
Note, it's actually possible to do the one-against-all reduction using
$(x,y)\rightarrow\forall l\,\,\,\left((x,l),I(y=l)\right)$, and learning
one classifier. This method has the same error transfer efficiency. 


\subsubsection{The Tree Reduction}

In the tree reduction we construct $k-1$ binary classifiers which
distinguish between the labels using a binary tree. The tree has depth
$\log_{2}k$, 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.

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

\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^{k}$ subsets of labels. Any particular label will
have a $2^{k}$ 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{thm}
(ECOC error efficiency) If the binary classifiers have error rate
$\epsilon$, the ECOC reduction has error rate less than:\[
4\epsilon\]

\end{thm}
The ECOC reduction is typically applied to a subset of the powerset
rather than the full powerset. The same basic result (with a worsened
constant) applies. 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^{k}$) and wrong labels will be consistent
with only half of the classifiers ($2^{k-1}$). In order to misclassify
the multiclass label, we must have at least $2^{k-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{Reductions to Importance Weighted Binary Classification}


\subsection{Classification to Weak Importance Weighted Binary Classification
(aka boosting)}


\subsection{Multilabel Classification}


\subsubsection{The One-against-all Reduction }

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

In the one-against-all reduction, we learn $k$ 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{k}{n+1}$ and $i_{1}=\frac{k}{n+1}$ if $k\leq n^{2}+n$
or $i_{1}=\frac{k-n}{n}$ for $k\geq n^{2}+n$

Suppose we use the same prediction function as in section \ref{sub:The-one-against-all-reduction}.
Then, we can prove the following theorem:

\begin{thm}
(Multilabel classification error efficiency) Let $c_{kn}=\frac{k}{n+1}$
for $k\leq n^{2}+n$ or $c_{kn}=\frac{k+1}{n+1}-\frac{n}{k}$ 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_{kn}\leq\epsilon E_{x,y_{1},...,y_{n}\sim D}\frac{k}{n}\]

\end{thm}
This theorem should be compared directly with the one-against-all
reduction to binary classication which had an error efficiency of
$k-1$. Here, with $n=1$, we get $c_{kn}=\frac{k+1}{2}-\frac{1}{k}=\frac{(k+2)(k-1)}{2k}$
implying an error efficiency of about $\frac{k}{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 $k$ 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 $k$. 

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{k-n}{k}$
and $1$ with an importance consumption of $ni_{1}$ or $ni_{1}+i_{0}$
implying error efficiencies of $\frac{\frac{k-n}{k}}{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{k-n}{kni_{1}},\frac{1}{ni_{1}+i_{0}},\frac{1}{(n+1)i_{0}}\right\} $.
There are two regimes for this maximum, $k\geq n^{2}+n$ and $k\leq n^{2}+n$. 

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

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

Since the maximal error efficiency is $\frac{1}{k}$ and there are
$k$ 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}{k}i_{1}+\frac{k-n}{k}i_{0}=\frac{k}{n+1}$
for $k\leq n^{2}+n$ or $(\frac{k+1}{n+1}-\frac{n}{k})$ for $k\geq n^{2}+n$.
Taking the expectation over $n$ and $k$ 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 XYZ reduction}

Consider the reduction which maps $(x,k_{1},k_{2},...,k_{l})\rightarrow(x,y,\max_{i}k_{i}-k_{y})$
for a uniformly shosen $y\in\{1,...,l\}$. This dataset is fed into
the importance weighted classification solve 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
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{thm}
(error transformation) If the importance weighted classifier has loss
rate $\epsilon$, then the cost sensitive classifier has expected
cost $\epsilon$.
\end{thm}
\begin{proof}
Assume that \[
\epsilon=E_{x,y,i\sim D^{*}}iI(c(x)\neq y)\]
\[
=E_{x,k_{1},...,k_{l}\sim D,y\sim\{1,...,l\}}(\max_{i}k_{i}-k_{y})I(c(x)\neq y)\]
\[
=E_{x,k_{1},...,k_{l}\sim D,y\sim\{1,...,l\}}\max_{i}k_{i}I(c(x)\neq y)-E_{x,k_{1},...,k_{l}\sim D,y\sim\{1,...,l\}}k_{y}I(c(x)\neq y)\]
\[
=\frac{l-1}{l}E_{x,k_{1},...,k_{l}\sim D}\max_{i}k_{i}-E_{x,k_{1},...,k_{l}\sim D}\frac{\sum_{i}k_{i}-k_{c(x)}}{l}\]
\[
=E_{x,k_{1},...,k_{l}\sim D}\frac{(l-1)\max_{i}k_{i}-\sum_{i}k_{i}+k_{c(x)}}{l}\]
\[
=E_{x,k_{1},...,k_{l}\sim D}\frac{k_{c(x)}-\max_{i}k_{i}}{l}+\max_{i}k_{i}-E_{i\sim\{1,...,l\}}k_{i}\]
Rewriting, we get: \[
E_{x,k_{1},...,k_{l}\sim D}k_{c(x)}=\epsilon-l[E_{x,k_{1},...,k_{l}\sim D}\max_{i}k_{i}-E_{i\sim\{1,...,l\}}k_{i}]+E_{x,k_{1},...,k_{l}\sim D}\max_{i}k_{i}\]


\[
=\epsilon-E_{x,k_{1},...,k_{l}\sim D}(l-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}

\subsubsection{sdf}

Nothing here is coherent yet. 

Suppose we want to reduce from multiclass2 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}

We should construct a table of results here.

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