\subsection{Easy Directions and Completeness}
\label{sec:easy}
                                                                                
The learning tasks we consider have an ``easy'' direction for
reduction related to whether a particular task is expressible as
another task.  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.
                                                                                
%\vskip -.2in
\begin{figure}[h]
\centering
\begin{pspicture}(15,3)
%\put(0,0){\framebox(15,3)[cc]{}}
\put(1,1){\framebox(1.9,.9)[cc]{Binary}}
\rput(2.9,1.9){\psline{->}(1.6,.4)}
\rput(2.9,1){\psline{->}(2.1,-.3)}
\put(4.5,2){\framebox(2.1,.9)[cc]{Multiclass}}
\rput(6.6,2.45){\psline{->}(1.9,0)}
\put(8.5,2){\framebox(1.9,.9)[cc]{Subset}}
\rput(10.4,2.3){\psline{->}(1.6,-.4)}
\put(5,.5){\framebox(5,.9)[cc]{Importance Weighted Binary}}
\rput(10,.7){\psline{->}(2,.3)}
\put(12,1){\framebox(2.5,.9)[cc]{Cost-Sensitive}}
\end{pspicture}
\caption{\label{fig:easy} The {}``easy'' direction for
reductions between the learning problems discussed here.}
\end{figure}
                                                                                
Note that all supervised learning tasks we consider can be embedded
into cost-sensitive classification using the mapping $k_y' =
\lossfunc(k,y)$ for the task $(k,y,\lossfunc)$.  Consequently,
cost-sensitive classification is (vacuously) ``complete'' for the set
of supervised learning tasks. Section~\ref{weighted-all-pairs} shows
that cost-sensitive classification is reducible to binary
classification.  Thus we can consider binary classification as
complete for the set of supervised learning tasks considered.  Stated
another way, a learning machine consisting of a turing machine with a
generalizing classification oracle can solve any supervised learning
task.
