Abstract
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 language | English |
---|---|
Pages (from-to) | 1329-1351 |
Number of pages | 23 |
Journal | Machine Learning |
Volume | 108 |
Issue number | 8-9 |
Early online date | 18 Mar 2019 |
DOIs | |
Publication status | Published - 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.
Funding
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.
Keywords
- Extreme multi-label classification
- Large-scale classification
- Linear classification
- Robustness
ASJC Scopus subject areas
- Software
- Artificial Intelligence