On the Learnability of Multilabel Ranking
This work provides foundational insights into the learnability of multilabel ranking, a central task in machine learning, though it appears incremental as it builds on existing theory without introducing a new paradigm.
The paper addresses the fundamental question of learnability in multilabel ranking with relevance-score feedback, characterizing it for both batch and online settings and identifying equivalence classes of ranking losses used in practice.
Multilabel ranking is a central task in machine learning. However, the most fundamental question of learnability in a multilabel ranking setting with relevance-score feedback remains unanswered. In this work, we characterize the learnability of multilabel ranking problems in both batch and online settings for a large family of ranking losses. Along the way, we give two equivalence classes of ranking losses based on learnability that capture most, if not all, losses used in practice.