MULTI-CLASS LEARNING: SIMPLEX CODING AND RELAXATION ERROR

Abstract. We study multi-category classification in the framework of computational learning theory. We show how a relaxation approach, which is commonly used in binary classification, can be generalized to the multi-class setting. We propose a vector coding, namely the simplex coding, that allows to introduce a new notion of multi-class margin and cast multi-category classification into a vector valued regression problem. The analysis of the relaxation error be quantified and the binary case is recovered as a special case of our theory. From a computational point of view we can show that using the simplex coding we can design regularized learning algorithms for multi-category classification that can be trained at a complexity which is independent to the number of classes. 1. Problem Setting. We consider an input space X ⊂ Rd, and output space Y = {1,..., T}. Given a prob-ability distribution ρ on X × Y we let ρX be the marginal probability on X and ρj(x) = ρ(j|x) the conditional distribution of class j given x, for each j = 1,..., T and x ∈ X. A training set is a sequence (xi, yi)ni=1 sampled i.i.d. with respect to ρ. A classification rule is a map c: X → Y and its properties can be measured via the misclassification error (or misclassification risk), R(c) = P(c(x) 6 = y), which is minimized, by the Bayes rule bρ(x) = arg maxj={1,...,T} ρj(x). This risk functional cannot be directly minimized for two reasons: 1) the true probability distribution is unknown, 2) it requires optimizing a non conve