MULTICLASS LEARNING WITH GENERAL LOSSES: WHAT IS THE RIGHT OUTPUT CODING AND DECODING?

ABSTRACT

Many practical applications of machine learning involve multiclass learning problems with a large number of classes. Multiclass learning with the standard 0-1 loss is fairly well understood; however, in practice, applications with large numbers of classes often require performance to be measured via a different, problem-specific loss. What
is the right way to design principled and efficient learning algorithms for multiclass problems with general losses?

From a theoretical standpoint, an elegant approach for designing statistically consistent learning algorithms is via the design of convex calibrated surrogate losses. From a practical standpoint, an approach that is often favored is that of output coding, which reduces multiclass learning to a set of simpler binary classification problems (with the
widely used one-vs-all reduction being a specific instance of this approach). In this talk, I will discuss recent progress in bringing together these seemingly disparate approaches under a unifying lens to develop statistically consistent and computationally efficient learning algorithms for a wide range of problems, in some cases recovering
existing state-of-the-art algorithms, and in other cases providing new ones.

[This talk is based on joint work with Harish G. Ramaswamy, Balaji S. Babu, Ambuj Tewari, Bob Williamson, and Mingyuan (William) Zhang.]