Subset &
$2^{\{1,\ldots,r\}}$ &
$\{1,\ldots,r\}$ &
$I(y \not \in k)$
\tabularnewline
\hline

\tabularnewline
\hline
1-vs-all& $(r - 1) \epsilon$& %                 No&
$O(|S| r)$&$r$ parallel& Yes

\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 $r$
labels and only one is correct.
The other error modes to consider involve (possibly multiple) false positives.
If there are $n$ false positives, the error probability is either
$\frac{n}{n+1}$ or $1$ if there was also a false negative.
The efficiency of these modes in creating errors (i.e., the ratio
of the probability of a multiclass error to the number of binary errors) is
$\frac{\frac{r-1}{r}}{1}=\frac{r-1}{r}$,
$\frac{\frac{n}{n+1}}{n}=\frac{1}{n+1}$,
and $\frac{1}{n+1}$, respectively.
Taking the maximum, we get $\frac{r-1}{r}$.
Multiplying by $r$ (since we have $r$ opportunities to err, one
for each classifier), we get the bound.
\qed
\end{proof}

We first present a weighted one-against-all reduction from subset
classification to importance weighted classification.

In the next sections, we prove the following efficiency guarantees:
\begin{center}
\renewcommand{\arraystretch}{1.1}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
Name&    $g(\epsilon)$& %  Learn Preserve&  
Time&   \#Calls&  Indep. Preserve
\tabularnewline
\hline
weighted 1-vs-all&$\frac{r}{n+1} \epsilon$ & % No& 
$O(|S| r)$& $1$ &No
\tabularnewline
\hline
weighted all-pairs& $2\epsilon$& % ??& 
$O(r^2)$& $1$ & No
\tabularnewline
\hline
\end{tabular}
\end{center}

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

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

The following theorem gives an error limitation bound 
for this reduction.
\begin{theorem}\label{thm:subset}
{\em (Error Limitation of Weighted One-against-all)} Let $c(r,n)=
\frac{r}{n+1}$ if $r\leq n^{2}+n$, otherwise $c(r,n)=
\frac{r+1}{n+1}-\frac{n}{r}$.  For any input space $X$ and distribution $D$ over
$X\times 2^{\{1,\ldots,r\}}$, if the binary classifier 
has a normalized loss rate $\epsilon$ (on the induced distribution), 
then the weighted one-against-all reduction has loss rate at most:
\[ \epsilon E_{(x,Q)\sim D}c(r,n).\]
\end{theorem}
The proof of this theorem is deferred to Appendix~\ref{subset-theorem}.
The theorem should be compared directly with the one-against-all
reduction to binary classification which has error efficiency of
$r-1$. Here, with $n=1$, we get 
$c(r,n)=\frac{r+1}{2}-\frac{1}{r}=\frac{(r+2)(r-1)}{2r}$
implying error efficiency of about $\frac{r}{2}$, or about half
the loss rate of the earlier reduction. 

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

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

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

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

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

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

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

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