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 at optimizing 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.

在极端多标签分类中，通过对大量可能标签中选择一小部分相关标签来解决长尾标签问题，采用了预算 “在 k” 的广义度量方法并利用块协调上升算法，取得了在长尾性能方面有希望的结果。