Error-Correcting Tournaments

Alina Beygelzimer, John Langford, Pradeep Ravikumar

Abstract:   We present a family of pairwise tournaments reducing k-class classification to binary classification. These reductions are provably robust against a constant fraction of binary errors, and match the best possible computation and regret up to a constant.

Download: pdf, arXiv version


  • Error-Correcting Tournaments (pdf, arXiv, software)
    A. Beygelzimer, J. Langford, P. Ravikumar.
    In International Conference on Algorithmic Learning Theory (ALT), 2009.