On the benefits of output sparsity for multi-label classification
This work addresses scalability issues in multi-label classification for applications with many labels, but it is incremental as it builds on existing loss functions by adding sparsity weighting.
The authors tackled the curse of dimensionality in large-scale multi-label classification by introducing a sparse weighted Hamming loss that exploits output sparsity, resulting in generalization bounds and convergence rates linear in output-sparsity rather than the number of labels, with experiments showing improved performance over non-weighted techniques.
The multi-label classification framework, where each observation can be associated with a set of labels, has generated a tremendous amount of attention over recent years. The modern multi-label problems are typically large-scale in terms of number of observations, features and labels, and the amount of labels can even be comparable with the amount of observations. In this context, different remedies have been proposed to overcome the curse of dimensionality. In this work, we aim at exploiting the output sparsity by introducing a new loss, called the sparse weighted Hamming loss. This proposed loss can be seen as a weighted version of classical ones, where active and inactive labels are weighted separately. Leveraging the influence of sparsity in the loss function, we provide improved generalization bounds for the empirical risk minimizer, a suitable property for large-scale problems. For this new loss, we derive rates of convergence linear in the underlying output-sparsity rather than linear in the number of labels. In practice, minimizing the associated risk can be performed efficiently by using convex surrogates and modern convex optimization algorithms. We provide experiments on various real-world datasets demonstrating the pertinence of our approach when compared to non-weighted techniques.