Error-Correcting Tournaments

2009/02/18 by Alina Beygelzimer, John Langford, Beygelzimer, Alina +3 · 2 citations
Computer Science · #Imbalanced Data Classification Techniques #Machine Learning and Algorithms #Bayesian Modeling and Causal Inference

paper · pdf · doi:10.48550/arxiv.0902.3176

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 \citeSECOC with an exponential improvement in computation, from O(k) to O(log₂ k), and the removal of a square root in the regret dependence, matching the best possible computation and regret up to a constant.

Cited by

• Reinforcement and Imitation Learning via Interactive No-Regret Learning
• On the boosting ability of top-down decision tree learning algorithm for\n multiclass classification

Related

• Using tournaments to calculate AUROC for zero-shot classification with LLMs
• An efficient reduction of ranking to classification
• Constructing Multiclass Classifiers using Binary Classifiers Under\n Log-Loss
• Don't Fear the Bit Flips: Optimized Coding Strategies for Binary Classification
• Optimal Binary Classification Beyond Accuracy