Accelerating Extreme Classification via Adaptive Feature Agglomeration

Ankit Jalan, Purushottam KarIJCAI 2019 · DOI

TL;DR

This paper introduces DEFRAG, a novel technique for accelerating extreme classification (assigning data points to one of millions of labels) by adaptively agglomerating features. DEFRAG significantly reduces training and prediction times by up to 40% without sacrificing accuracy, and also offers new methods for handling rare labels and missing data.

What Problem Does This Paper Address?

Extreme classification (XC) is a challenging machine learning task where each data point must be assigned one or more labels from an enormous label space, often millions of labels. This problem is prevalent in areas like recommendation systems and search advertising. The core challenges in XC are:

  • High Precision: Accurately identifying the few relevant labels among millions of irrelevant ones.
  • Speed: Predictions must be made within milliseconds for real-time applications.
  • Scalability: Datasets are massive, with millions of data points and high-dimensional feature vectors.
  • Label Imbalance (Parity): Most labels are rare, meaning they apply to very few data points, making it difficult for algorithms to learn them effectively.

Existing methods struggle to balance these competing demands, often sacrificing speed or accuracy for scalability, or failing to adequately address the issue of rare labels.

Methods

The paper proposes DEFRAG (Adaptive Extreme FeatuRe AGGlomeration), a technique that reduces feature dimensionality by clustering features and then summing them within each cluster. This process is hierarchical and can be guided by different criteria:

  • DEFRAG-X: Clusters features based on their co-occurrence patterns across data points. It represents each feature as a vector of its values across all data points.
  • DEFRAG-XY: Clusters features based on their co-predictive patterns, considering how features relate to labels. It represents each feature as a weighted aggregate of label vectors from data points where the feature is active.

DEFRAG employs a novel hierarchical clustering approach that offers provable performance guarantees. The clustering process itself is designed to be efficient, with a time complexity of O(nnz(X) log d), where nnz(X) is the number of non-zero elements in the feature matrix and d is the original dimensionality.

Beyond feature agglomeration, the paper also introduces:

  • REFRAG: A method that leverages DEFRAG's agglomerates to re-rank labels, specifically improving the prediction of rare labels.
  • FIAT: A feature imputation technique that uses DEFRAG's clusters to handle missing features more robustly than traditional methods.

Datasets

The authors evaluated their methods on several large-scale extreme classification datasets:

  • EURLex-4K
  • AmazonCat-13K
  • Wiki10-31K
  • Delicious-200K
  • WikiLSHTC-325K
  • Wikipedia-500K
  • Amazon-670K
  • Amazon-3M

These datasets are standard benchmarks in the extreme classification community and are available through the Extreme Classification Repository.

Key Insights and Ideas

  • Feature Agglomeration as a Scalability Solution: The core insight is that by intelligently grouping features, dimensionality can be drastically reduced without losing essential predictive information. This is particularly effective for sparse, high-dimensional data common in XC.
  • Provable Performance Guarantees: The paper provides theoretical backing, showing that DEFRAG preserves the performance of linear models, which form the basis of many XC algorithms. This is a crucial theoretical contribution.
  • Task Adaptivity (DEFRAG-XY): The DEFRAG-XY variant, which considers label information during feature clustering, demonstrates that being "task-adaptive" can lead to better performance than generic dimensionality reduction.
  • Addressing Rare Labels: REFRAG's ability to improve coverage for rare labels is a significant practical contribution, as this is a persistent problem in XC.
  • Robustness to Missing Data: FIAT's resilience to feature erasures highlights the practical utility of DEFRAG's clustered representations for real-world scenarios where data is often incomplete.

Key Results

  • Speedup: DEFRAG reduces training and prediction times by up to 40% for several leading XC algorithms.
  • Accuracy Preservation: The reductions in time are achieved with little to no significant drop in precision. In some cases, DEFRAG variants even outperform baseline methods.
  • Rare Label Performance: REFRAG significantly improves coverage for rare labels, more than tripling it on the Wiki10 dataset compared to Parabel.
  • Feature Imputation: FIAT shows superior robustness to feature erasures compared to standard methods, with performance gaps widening as noise levels increase.
  • Dimensionality Reduction: DEFRAG variants can reduce feature dimensionality by orders of magnitude (e.g., 16x on Delicious-200K) while maintaining or improving performance.

Limitations and Future Work

  • Hyperparameter Tuning: While DEFRAG has a primary hyperparameter (maximum leaf size for clusters), its optimal setting might require tuning. The paper explores trade-offs with this parameter.
  • Ensemble Benefits: The paper notes that ensemble training of DEFRAG variants can boost accuracy, suggesting further exploration of ensemble strategies.
  • Cluster Averaging: While cluster averaging is explored as a potential improvement for certain classifiers, its benefits are not uniform across all datasets and methods.
  • Further Exploration of DEFRAG-N: The paper mentions DEFRAG-N (using nDCG for splitting) is more expensive but can offer slightly superior performance in some cases, suggesting further investigation into its trade-offs.
  • Adaptation to Non-Linear Models: The theoretical guarantees are primarily for linear models. Extending these to non-linear models would be a valuable future direction.

Summary updated

BibTeX
@inproceedings{jalan2019accelerating,
  author = {Ankit Jalan and Purushottam Kar},
  title = {{Accelerating Extreme Classification via Adaptive Feature Agglomeration}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/361},
}
Figure