Does Tail Label Help for Large-Scale Multi-Label Learning

Tong Wei, Yu-Feng LiIJCAI 2018 · OpenReview

Abstract

Large-scale multi-label learning (LMLL) involves annotating relevant labels for unseen data from a massive pool of candidate labels. It is well-known that in LMLL, labels exhibit a long-tail distribution where a significant fraction of labels are rare. This paper investigates the impact of these tail labels on standard performance metrics like Top-$k$ precision and nDCG@$k$. We demonstrate that tail labels have a negligible impact compared to common labels when they are missing or misclassified. Leveraging this insight, we propose ADATTL (Adaptively Trimming off Tail Labels), a low-complexity algorithm that facilitates fast prediction and compact models by adaptively trimming tail labels. Experiments show that prediction time and model size can be significantly reduced without sacrificing predictive performance.

Introduction

In large-scale multi-label learning, the goal is to tag data with relevant labels from a pool that can reach millions (e.g., categorizing Wikipedia articles). A defining characteristic of these datasets is the "power law" or long-tail distribution: a few "common" labels appear frequently, while the vast majority ("tail labels") appear in only a handful of examples. Historically, it was assumed that accurate prediction of these tail labels was essential for high performance. However, maintaining millions of rare labels makes models computationally expensive and memory-intensive. This research asks: Do tail labels actually matter for the metrics used to evaluate these models?

Theoretical Analysis of Metric Bias

The researchers mathematically modeled scenarios where labels are either randomly missing from the ground truth or randomly misclassified. In both cases, they proved that common labels have a significantly higher impact on Top-$k$ precision and nDCG than tail labels. Because tail labels appear so infrequently, missing or misidentifying them barely registers on aggregate ranking scores. This suggests that standard metrics are inherently biased toward frequent labels; failing to predict a tail label affects only one instance, whereas failing on a common label affects thousands.

The ADATTL Algorithm

Based on the theoretical insight that tail labels are often "noise" relative to ranking metrics, the authors developed ADATTL, a wrapper algorithm applicable to existing LMLL models. The process involves:

  1. Sampling: The algorithm samples small data subsets and trims varying fractions of tail labels.
  2. Regression: It builds polynomial regressors to predict how trimming a percentage of labels ($\lambda$) affects predictive performance, prediction time, and model size.
  3. Optimization: It identifies the "adaptive point"—the optimal fraction of tail labels to remove to maximize efficiency gains while minimizing accuracy loss.
Figure 6: The adaptive point identifies the threshold where model efficiency is maximized before performance drops sharply.

Experimental Results

The study utilized standard benchmarks including Bibtex, Delicious, EUR-Lex, and Wiki10. The results across both embedding-based and tree-based methods were striking. For instance, in the Wiki10 dataset, trimming 50% of the tail labels actually resulted in a slight increase in P@1 and nDCG@1 while nearly halving prediction time.

Figure 2: Comparison of the entire label set versus trimming 50% of tail labels on Wiki10 and EUR-Lex datasets.

Key findings include:

  • Wiki10 (with LEML): ADATTL achieved a 92.1% reduction in prediction time and a 20% reduction in model size with no significant drop in precision.
  • EUR-Lex (with FastXML): Prediction time was reduced by 43.3% and model size by 33%.
  • Structural Benefits: Trimming simplifies model structures. In tree-based models, fewer labels lead to shallower trees and faster inference. In embedding-based models, it helps preserve low-rank assumptions by removing noisy tail data.

Conclusion and Future Work

This research demonstrates a "free lunch" in LMLL: trimming a large portion of the long tail can drastically improve efficiency with negligible impact on ranking performance. However, the authors note that if an application specifically requires finding rare items (e.g., rare disease diagnosis), trimming is inappropriate. Future work should focus on designing performance metrics that better balance common and tail labels if the goal is to incentivize true long-tail learning, such as propensity-scored metrics.

Summary updated

Abstract

Large-scale multi-label learning annotates relevant labels for unseen data from a huge number of candidate labels. It is well known that in large-scale multi-label learning, labels exhibit a long tail distribution in which a significant fraction of labels are tail labels. Nonetheless, how tail labels make impact on the performance metrics in large-scale multi-label learning was not explicitly quantified. In this paper, we disclose that whatever labels are randomly missing or misclassified, tail labels impact much less than common labels in terms of commonly used performance metrics (Top-$k$ precision and nDCG@$k$). With the observation above, we develop a low-complexity large-scale multi-label learning algorithm with the goal of facilitating fast prediction and compact models by trimming tail labels adaptively. Experiments clearly verify that both the prediction time and the model size are significantly reduced without sacrificing much predictive performance for state-of-the-art approaches.
BibTeX
@inproceedings{wei2018does,
  author = {Tong Wei and Yu-Feng Li},
  title = {{Does Tail Label Help for Large-Scale Multi-Label Learning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  url = {https://openreview.net/forum?id=BJbtIVzOWB},
}
Figure