Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR04-077 | 17th July 2004 00:00

Reductions Between Classification Tasks

RSS-Feed




TR04-077
Authors: Alina Beygelzimer, Varsha Dani, Tom Hayes, John Langford
Publication: 17th September 2004 20:35
Downloads: 1057
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint