Skip to yearly menu bar Skip to main content


Extreme Multi-label Classification from Aggregated Labels

Yanyao Shen · Hsiang-Fu Yu · Sujay Sanghavi · Inderjit Dhillon

Keywords: [ Large Scale Learning and Big Data ] [ Supervised Learning ] [ Other ] [ Semi-supervised learning ] [ Optimization - Large Scale, Parallel and Distributed ]


Extreme multi-label classification (XMC) is the problem of finding the relevant labels for an input, from a very large universe of possible labels. We consider XMC in the setting where labels are available only for groups of samples - but not for individual ones. Current XMC approaches are not built for such multi-instance multi-label (MIML) training data, and MIML approaches do not scale to XMC sizes. We develop a new and scalable algorithm to impute individual-sample labels from the group labels; this can be paired with any existing XMC method to solve the aggregated label problem. We characterize the statistical properties of our algorithm under mild assumptions, and provide a new end-to-end framework for MIML as an extension. Experiments on both aggregated label XMC and MIML tasks show the advantages over existing approaches.

Chat is not available.