Data scarcity, robustness and extreme multi-label classification

Rohit Babbar, Bernhard Schölkopf

Research output: Contribution to journalArticlepeer-review

90 Citations (SciVal)


The goal in extreme multi-label classification (XMC) 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. The distribution of training instances among labels in XMC exhibits a long tail, implying that a large fraction of labels have a very small number of positive training instances. Detecting tail-labels, which represent diversity of the label space and account for a large fraction (upto 80%) of all the labels, has been a significant research challenge in XMC. In this work, we pose the tail-label detection task in XMC as robust learning in the presence of worst-case perturbations. This viewpoint is motivated by a key observation that there is a significant change in the distribution of the feature composition of instances of these labels from the training set to test set. For shallow classifiers, our robustness perspective to XMC naturally motivates the well-known ℓ1-regularized classification. Contrary to the popular belief that Hamming loss is unsuitable for tail-labels detection in XMC, we show that minimizing (convex upper bound on) Hamming loss with appropriate regularization surpasses many state-of-the-art methods. Furthermore, we also highlight the sub-optimality of the co-ordinate descent based solver in the LibLinear package, which, given its ubiquity, 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.

Original languageEnglish
Pages (from-to)1329-1351
Number of pages23
JournalMachine Learning
Issue number8-9
Early online date18 Mar 2019
Publication statusPublished - 15 Sept 2019

Bibliographical note

Funding Information:
Open access funding provided by Aalto University. Funding was provided by Aalto Yliopisto (Grant No. TT Package). The authors wish to acknowledge CSC - IT Center for Science, Finland, for computational resources, and Triton cluster team at Aalto University.


  • Extreme multi-label classification
  • Large-scale classification
  • Linear classification
  • Robustness

ASJC Scopus subject areas

  • Software
  • Artificial Intelligence


Dive into the research topics of 'Data scarcity, robustness and extreme multi-label classification'. Together they form a unique fingerprint.

Cite this