Data scarcity, robustness and extreme multi-label classification

Rohit Babbar*, Bernhard Schölkopf

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

86 Citations (Scopus)
357 Downloads (Pure)


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
Publication statusPublished - 15 Sept 2019
MoE publication typeA1 Journal article-refereed


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


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

Cite this