Error-Correcting Tournaments

Text of 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, simultaneously matching the best possible computation O(log k) and regret O(1). The construction also works for robustly selecting the best of k-choices by tournament. We strengthen previous results by defeating a more powerful adversary than previously addressed while providing a new form of analysis. In this setting, the error correcting tournament has depth O(log k) while using O(klogk) comparators, both optimal up to a small constant. Keywords: reductions, multiclass classification, cost-sensitive learning, tournaments, robust search 1. Introduction We consider the classical problem of multiclass classification, where given an instance x X, the goal is to predict the most likely label y {1,...,k}, according to some unknown probability distribution. A common general approach to multiclass learning is to reduce a multiclass problem to a set of binary classification problems [2, 7, 11, 12, 15].