Timezone: »

Generalized test utilities for long-tail performance in extreme multi-label classification
Erik Schultheis · Marek Wydmuch · Wojciech Kotlowski · Rohit Babbar · Krzysztof Dembczynski

Thu Dec 14 08:45 AM -- 10:45 AM (PST) @ Great Hall & Hall B1+B2 #1025

Extreme multi-label classification (XMLC) is a 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 \emph{expected test utility} (ETU) framework, which aims at optimizing the expected performance on a given test set. We derive optimal prediction rules and construct their computationally efficient approximations with provable regret guarantees and being robust against model misspecification. Our algorithm, based on block coordinate descent, scales effortlessly to XMLC problems and obtains promising results in terms of long-tail performance.

Author Information

Erik Schultheis (Aalto University)
Marek Wydmuch (Poznan University of Technology)
Wojciech Kotlowski (Poznan University of Technology, Poland)
Rohit Babbar (University of Bath)
Krzysztof Dembczynski (Yahoo Research)

More from the Same Authors