Adversarial Extreme Multi-label Classification
arXiv:1803.01570
Abstract
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.
14 pages
References in corpus (6)
- Understanding Adversarial Training: Increasing Local Stability of Neural Nets through Robust Optimization
- Robustness and Regularization of Support Vector Machines
- Adversarial Examples for Evaluating Reading Comprehension Systems
- Parseval Networks: Improving Robustness to Adversarial Examples
- Logarithmic Time One-Against-Some
- Subset Labeled LDA for Large-Scale Multi-Label Classification