\subsubsection{Learning Preserving Reductions}

Our definition of error limiting reduction does not eliminate the
possibility that easy learning problems are reduced to very hard
learning problems.  Consequently, we mention an additional requirement
which does prove this.

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

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

Theorem~\ref{preserving} shows that the tree reduction \cite{Tree}
from multiclass classification to binary classification is learning
preserving.  In general, few of the reductions commonly used in
machine learning satisfy the ``learning preserving'' property, often
for relatively trivial reasons.  We primarily consider error limiting
reductions instead because of analytic tractability.

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

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

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

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

\subsubsection{Learning Preserving and the Tree Reduction}

We show that the tree reduction is learning preserving.

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

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

