Multilabel reductions: what is my loss optimising?

NeurIPS 2019

TL;DR

When solving multilabel classification problems, researchers often "reduce" the task into simpler binary or multiclass problems. This paper reveals a fundamental trade-off: unnormalised reductions (like standard one-versus-all) are mathematically geared toward optimising precision@k, while normalised reductions (where losses are scaled by the number of relevant labels) are consistent for recall@k.

The Problem: Scaling Multilabel Classification

In multilabel classification, the goal is to predict a set of relevant tags for an object—think of tagging an image with "sunset," "beach," and "vacation." Because predicting every possible combination of labels is computationally impossible (known as the "label powerset" problem), practitioners use reductions. They might treat every label as an independent binary choice or pick one positive label at random to turn it into a multiclass problem.

While these tricks work well in practice, there has been a theoretical "black box" regarding what they actually optimize. Specifically, how do these choices affect two of the most important metrics in information retrieval:

  • Precision@k: How many of my top $k$ guesses are right?
  • Recall@k: How many of the actual correct labels did I find in my top $k$?

Methods: Five Common Reductions

The authors provide a unified theoretical framework to analyze five common reductions:

  1. One-Versus-All (OVA): Independent binary classifiers for each label.
  2. Pick-All-Labels (PAL): Creating a multiclass training instance for every positive label.
  3. One-Versus-All Normalised (OVA-N): Like OVA, but the loss for each instance is divided by its number of relevant labels.
  4. Pick-All-Labels Normalised (PAL-N): Like PAL, but normalized.
  5. Pick-One-Label (POL): Randomly sampling a single positive label for each instance to treat it as a standard multiclass problem.
Example loss function instantiations for the five analyzed reductions.

The researchers used the concept of Fisher consistency to determine if these reductions, given infinite data and a perfect model, would actually converge to the "Bayes-optimal" scorer for precision or recall.

Key Insights and Results

The Normalization Toggle

The most striking insight is that the presence or absence of a normalization factor (dividing by the number of relevant labels) acts as a switch. Unnormalised methods optimize for precision; normalised methods optimize for recall.

Summary of multilabel reductions and their theoretical consistency for Precision@k and Recall@k.

Fundamental Incompatibility

The authors prove that, in general, no single reduction can be optimal for both precision and recall. The ranking of labels required to maximize precision is mathematically different from the ranking required to maximize recall, unless the number of relevant labels happens to be constant across all instances.

The "Hidden" Transformation

For metrics like recall@k, the optimal "scorer" isn't just the marginal probability of a label. Instead, it's a non-linearly weighted version of that probability. Normalised reductions like POL and PAL-N implicitly learn this transformed probability.

Interpreting Scores

The paper warns that scores from PAL or POL shouldn't be treated as raw probabilities of a label being "true." Because they involve instance-dependent scaling, a "low" score in a PAL model might still represent a highly relevant label if the instance has many other relevant tags.

Empirical Validation

The paper primarily uses a synthetic dataset to validate its theoretical findings. By using a controlled environment (a mixture of two Gaussians in $\mathbb{R}^2$ with 10 possible labels), the authors could precisely manipulate the number of relevant labels per instance.

In their experiments, the PAL method significantly outperformed its normalized counterpart (PAL-N) on precision@k. Conversely, PAL-N showed a clear and significant gain over PAL when measured by recall@k. The performance curves for different methods converge only when $k$ reaches the maximum number of labels possible for an instance, confirming that the choice of reduction matters most when we are forced to be selective (small $k$).

Limitations and Future Work

  • Scope of Metrics: The study focuses on precision@k and recall@k. While these are foundational, other metrics like F1-score or Normalized Discounted Cumulative Gain (NDCG) were not explicitly analyzed in this framework.
  • Linear Models: The empirical validation used linear models on synthetic data. While this proves the theory, the behavior of high-capacity deep neural networks on massive, long-tailed datasets (Extreme Classification) remains an area for further practical exploration.
  • Generalization: The paper focuses on "consistency" (the infinite data limit). The authors suggest that future work could look at "generalization analysis"—how these reductions behave when data is scarce.

Summary updated

BibTeX
@inproceedings{2019multilabel,
  title = {{Multilabel reductions: what is my loss optimising?}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
}
Figure