Adversarial Extreme Multi-label Classification
This work addresses the challenge of handling long-tail labels in large-scale classification, which is incremental but offers practical gains for applications with many rare categories.
The paper tackles the problem of extreme multi-label classification, particularly for tail labels with few training examples, by framing it as a robust optimization problem and showing that a regularized objective with proximal gradient optimization achieves up to 20% relative improvement over PFastreXML and 60% over SLEEC on propensity scored metrics.
The goal in extreme multi-label classification is to learn a classifier which can assign a small subset of relevant labels to an instance from an extremely large set of target labels. Datasets in extreme classification exhibit a long tail of labels which have small number of positive training instances. In this work, we pose the learning task in extreme classification with large number of tail-labels as learning in the presence of adversarial perturbations. This view motivates a robust optimization framework and equivalence to a corresponding regularized objective. Under the proposed robustness framework, we demonstrate efficacy of Hamming loss for tail-label detection in extreme classification. The equivalent regularized objective, in combination with proximal gradient based optimization, performs better than state-of-the-art methods on propensity scored versions of precision@k and nDCG@k(upto 20% relative improvement over PFastreXML - a leading tree-based approach and 60% relative improvement over SLEEC - a leading label-embedding approach). Furthermore, we also highlight the sub-optimality of a sparse solver in a widely used package for large-scale linear classification, which is interesting in its own right. We also investigate the spectral properties of label graphs for providing novel insights towards understanding the conditions governing the performance of Hamming loss based one-vs-rest scheme vis-à-vis label embedding methods.