Addressing statistical and computational challenges in extreme multilabel classification with unbiased estimators, macro-averaged metrics, and hardware-aware implementations

Abstract

This thesis tackles statistical and computational challenges in extreme multilabel classification (XMC) problems, that is, in tasks where the label space is gigantic, possibly in the millions of labels. Such problems are plagued by missing labels and data scarcity, particularly in the form of tail labels, and the enormous label space turns operations that are cheap in typical machine learning problems, such as calculating the loss in the classification layer, into computationall challenging tasks.

Towards addressing the missing-label problem, this thesis derives unbiased estimators for generic multilabel loss functions under the assumption that a propensity model is available. A critical look at the propensity model that is in widespread usage in the current XMC literature is provided, in particular regarding the the problematic double role of using propensities both to compensate for missing labels and as a measure for performance on infrequent tail labels. As an alternative, macro-averaged performance metrics are proposed, and prediction algorithms aiming to optimize these metrics in two different inference frameworks are presented.

The thesis presents a new approach to train linear extreme classifiers, still an important baseline, significantly faster than before, owing to a new weight initialization scheme, and code that is aware of the memory layout of modern NUMA processors. Additionally, it presents a novel way to exploit weight sparsity, already at the training stage, to reduce the on-device memory consumption. This is achieved by combining dynamic sparse training algorithms with an efficient weight storage format that at the same time allows for a fast implementation of matrix multiplication.