Error-Correcting Tournaments

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. 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.

Minor wording improvements

References in corpus (1)

• Multi-Label Prediction via Compressed Sensing

Cited by in corpus (6)

• Reinforcement and Imitation Learning via Interactive No-Regret Learning
• Multiclass learnability and the ERM principle
• On the computational complexity of the probabilistic label tree algorithms
• On the boosting ability of top-down decision tree learning algorithm for multiclass classification
• Aggressive Sampling for Multi-class to Binary Reduction with Applications to Text Classification
• Candidates vs. Noises Estimation for Large Multi-Class Classification Problem