Unbiased Loss Functions for Multilabel Classification with Missing Labels
This work addresses missing labels in extreme multi-label classification tasks like Wikipedia tagging, but it is incremental as it builds on existing unbiased estimation methods by extending them to non-decomposable loss functions.
The paper tackles the problem of missing labels in multilabel classification by deriving unique unbiased estimators for various multilabel reductions, including non-decomposable ones, and addresses issues like increased variance and ill-posed optimization with convex upper-bounds. Experimental results show that unbiased estimators alter the bias-variance trade-off, sometimes requiring stronger regularization that can negate benefits.
This paper considers binary and multilabel classification problems in a setting where labels are missing independently and with a known rate. Missing labels are a ubiquitous phenomenon in extreme multi-label classification (XMC) tasks, such as matching Wikipedia articles to a small subset out of the hundreds of thousands of possible tags, where no human annotator can possibly check the validity of all the negative samples. For this reason, propensity-scored precision -- an unbiased estimate for precision-at-k under a known noise model -- has become one of the standard metrics in XMC. Few methods take this problem into account already during the training phase, and all are limited to loss functions that can be decomposed into a sum of contributions from each individual label. A typical approach to training is to reduce the multilabel problem into a series of binary or multiclass problems, and it has been shown that if the surrogate task should be consistent for optimizing recall, the resulting loss function is not decomposable over labels. Therefore, this paper derives the unique unbiased estimators for the different multilabel reductions, including the non-decomposable ones. These estimators suffer from increased variance and may lead to ill-posed optimization problems, which we address by switching to convex upper-bounds. The theoretical considerations are further supplemented by an experimental study showing that the switch to unbiased estimators significantly alters the bias-variance trade-off and may thus require stronger regularization, which in some cases can negate the benefits of unbiased estimation.