Consistent Multilabel Ranking through Univariate Losses
This addresses a fundamental problem in multilabel ranking for machine learning practitioners, offering a scalable solution to an inconsistency issue, though it is incremental as it builds on prior negative results.
The paper tackles the inconsistency of pairwise surrogate losses for rank loss minimization in multilabel classification by showing that simpler univariate variants of exponential and logistic surrogates are consistent, with derived regret bounds and convergence rates.
We consider the problem of rank loss minimization in the setting of multilabel classification, which is usually tackled by means of convex surrogate losses defined on pairs of labels. Very recently, this approach was put into question by a negative result showing that commonly used pairwise surrogate losses, such as exponential and logistic losses, are inconsistent. In this paper, we show a positive result which is arguably surprising in light of the previous one: the simpler univariate variants of exponential and logistic surrogates (i.e., defined on single labels) are consistent for rank loss minimization. Instead of directly proving convergence, we give a much stronger result by deriving regret bounds and convergence rates. The proposed losses suggest efficient and scalable algorithms, which are tested experimentally.