%0 Journal Article
%T Error-Correcting Tournaments
%A Alina Beygelzimer
%A John Langford
%A Pradeep Ravikumar
%J Computer Science
%D 2009
%I arXiv
%X 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. The results improve on the PECOC construction \cite{SECOC} with an exponential improvement in computation, from $O(k)$ to $O(\log_2 k)$, and the removal of a square root in the regret dependence, matching the best possible computation and regret up to a constant.
%U http://arxiv.org/abs/0902.3176v4