Generalized test utilities for long-tail performance in extreme multi-label classification
This work addresses the challenge of accurately measuring and enhancing performance on rare labels in XMLC, which is crucial for applications where tail labels are important, though it is incremental in refining existing metric frameworks.
The paper tackles the problem of evaluating and optimizing classifiers for long-tail labels in extreme multi-label classification, where standard metrics like precision@k fail to capture performance on rare labels. The authors propose generalized test utilities as an alternative, derive optimal prediction rules, and develop an efficient algorithm that scales to large problems and shows promising results in improving long-tail performance.
Extreme multi-label classification (XMLC) is the task of selecting a small subset of relevant labels from a very large set of possible labels. As such, it is characterized by long-tail labels, i.e., most labels have very few positive instances. With standard performance measures such as precision@k, a classifier can ignore tail labels and still report good performance. However, it is often argued that correct predictions in the tail are more "interesting" or "rewarding," but the community has not yet settled on a metric capturing this intuitive concept. The existing propensity-scored metrics fall short on this goal by confounding the problems of long-tail and missing labels. In this paper, we analyze generalized metrics budgeted "at k" as an alternative solution. To tackle the challenging problem of optimizing these metrics, we formulate it in the expected test utility (ETU) framework, which aims to optimize the expected performance on a fixed test set. We derive optimal prediction rules and construct computationally efficient approximations with provable regret guarantees and robustness against model misspecification. Our algorithm, based on block coordinate ascent, scales effortlessly to XMLC problems and obtains promising results in terms of long-tail performance.