There are two approaches to solving a new supervised learning task: either
analyze the task independently or reduce it to a task that has already
been thoroughly analyzed. This paper investigates the latter approach for
classification problems. In addition to obvious theoretical motivations,
there is fairly strong empirical evidence that this style of analysis
often produces learning algorithms that perform well in practice. We
present a theoretical framework for analyzing reductions and discuss
several known reductions from this standpoint. We also present two new
reductions along with experimental evidence suggesting that analysis in
this model is predictive of performance on real-world problems.