Beyond Standard Performance Measures in Extreme Multi-label Classification

Extreme multi-label classification (XMLC) is the task of selecting, for a given instance, a small subset of relevant labels from a very large set of possible labels. XMLC datasets are characterized by having a long-tailed label distribution, meaning that most of the labels have very few positive instances. With standard performance measures such as precision or nDCG at k, a classifier can ignore a significant portion of the tail labels completely and still get reasonably good performance. However, it is often argued that good predictions in the tail are more “interesting” or “rewarding,” yet as of now the XMLC community does not have a way to formalize what this means, nor a set of performance metrics that evaluate this in a principled manner. This paper aims at starting this discussion, first by providing a list of potential performance metrics to be used, as well as some scenarios from which we might infer a more specific meaning of “rewarding.” Second, we provide a preliminary investigation into one such metric, coverage, and present an efficient greedy strategy aiming to maximize it. A short empirical evaluation shows, that the proposed approach achieves very good results on the measure.