Multiclass Learning with Simplex Coding
This addresses the scalability issue in multiclass classification for machine learning practitioners, though it appears incremental as it builds on existing binary relaxation approaches.
The paper tackles multiclass learning by introducing a simplex coding framework that generalizes binary classification relaxation, achieving a provably consistent regularized method with training complexity independent of the number of classes.
In this paper we discuss a novel framework for multiclass learning, defined by a suitable coding/decoding strategy, namely the simplex coding, that allows to generalize to multiple classes a relaxation approach commonly used in binary classification. In this framework, a relaxation error analysis can be developed avoiding constraints on the considered hypotheses class. Moreover, we show that in this setting it is possible to derive the first provably consistent regularized method with training/tuning complexity which is independent to the number of classes. Tools from convex analysis are introduced that can be used beyond the scope of this paper.