PaperlayerView exact revision on arXiv

Source-linked AI summary

DiSMEC - Distributed Sparse Machines for Extreme Multi-label Classification

Rohit Babbar, Bernhard Shoelkopf

arXiv:1609.02521v1stat.MLcs.LG

TL;DR

Extreme multi-label classification combines enormous label spaces with power-law sparsity, challenging existing low-rank methods and conventional one-versus-rest solvers. DiSMEC uses distributed, doubly parallelized one-versus-rest linear classifiers with explicit sparsity control. Across large benchmarks, it reports higher accuracy than SLEEC and FastXML while learning compact models at scale.

  • Problem

    Extreme multi-label datasets contain hundreds of thousands or millions of labels with many tail labels, while low-rank embedding assumptions can break down in diverse power-law label spaces.

  • Method

    DiSMEC learns one-versus-rest linear classifiers using double-layer parallelization and explicit model sparsity induction without assuming a low-rank label matrix.

  • Results

    On three of seven datasets, DiSMEC achieves 10% absolute improvement in precision and nDCG over SLEEC and 15% over FastXML.

  • Takeaways & Limitations

    DiSMEC scales one-versus-rest learning to hundreds of thousands of labels while producing compact models suitable for real-time extreme-classification applications.

  • Takeaways & Limitations

    SLEEC’s locally low-rank assumption, approximate high-dimensional clustering, non-convex optimization, and multiple arbitrarily set hyperparameters remain limitations of that comparison method.

Abstract

from arXiv · show

Extreme multi-label classification refers to supervised multi-label learning involving hundreds of thousands or even millions of labels. Datasets in extreme classification exhibit fit to power-law distribution, i.e. a large fraction of labels have very few positive instances in the data distribution. Most state-of-the-art approaches for extreme multi-label classification attempt to capture correlation among labels by embedding the label matrix to a low-dimensional linear sub-space. However, in the presence of power-law distributed extremely large and diverse label spaces, structural assumptions such as low rank can be easily violated. In this work, we present DiSMEC, which is a large-scale distributed framework for learning one-versus-rest linear classifiers coupled with explicit capacity control to control model size. Unlike most state-of-the-art methods, DiSMEC does not make any low rank assumptions on the label matrix. Using double layer of parallelization, DiSMEC can learn classifiers for datasets consisting hundreds of thousands labels within few hours. The explicit capacity control mechanism filters out spurious parameters which keep the model compact in size, without losing prediction accuracy. We conduct extensive empirical evaluation on publicly available real-world datasets consisting upto 670,000 labels. We compare DiSMEC with recent state-of-the-art approaches, including - SLEEC which is a leading approach for learning sparse local embeddings, and FastXML which is a tree-based approach optimizing ranking based loss function. On some of the datasets, DiSMEC can significantly boost prediction accuracies - 10% better compared to SLECC and 15% better compared to FastXML, in absolute terms.

1 Introduction

Extreme multi-label classification must handle enormous, power-law-distributed label spaces that create computational, storage, and statistical challenges. DiSMEC revisits one-versus-rest learning with distributed training and explicit sparsity, reporting faster training, compact models, and improved prediction accuracy.

  • XMC setting: Extreme multi-label classification targets hundreds of thousands or millions of labels while predicting a relevant subset for each unseen instance.Applications include tagging Wikipedia pages, products, images, and text.
  • Scalability challenges: Direct off-the-shelf one-versus-rest solvers can require weeks of training, large in-memory resources, and models reaching hundreds of GBs or TBs.For WikiLSHTC-325K, Liblinear training can take 96 days and an ℓ2-regularized linear SVM model can occupy 870 GB.
  • Statistical challenge: A power-law label distribution leaves many labels with very few training instances, making good classifier learning difficult for tail labels.Only 100,000 of Amazon-670K’s 670,000 labels have more than 5 training instances.
  • Existing approaches: Embedding- and tree-based methods reduce the effective label space, but extreme power-law diversity can violate the low-rank assumption used by embedding approaches.SLEEC additionally relies on locally low-rank structure, approximate clustering, and non-convex optimization.
  • DiSMEC: DiSMEC distributes one-versus-rest learning with two parallelization layers and explicitly prunes spurious weights to scale training and reduce model size.On WikiLSHTC-325K, it learns the model in 6 hours on 400 cores; its model is 3 GB versus 870 GB for the cited linear SVM.
  • Empirical outcomes: DiSMEC improves prediction accuracy over established baselines on several large benchmark datasets while supporting compact models and real-time prediction.It reports 10% absolute improvement over SLEEC and 15% over FastXML on three of seven datasets.

2 Proposed Method

DiSMEC learns one-versus-rest linear classifiers at scale using two-layer parallelization, then prunes ambiguous near-zero weights to control model size while preserving prediction accuracy.

  • One-versus-rest learning: DiSMEC learns one-versus-rest linear classifiers independently for each label using squared-hinge loss and l2 regularization.Each label uses a binary sign vector indicating whether the label is present in each training instance.
  • Double-layer parallelization: Its double-layer architecture batches labels across nodes and trains each batch in parallel across cores.Labels are grouped into batches of about 1,000, with OpenMP used for within-node parallel training.
  • Double-layer parallelization: Input features are stored once and shared across binary problems, while label-specific sign vectors are maintained separately.This avoids replicating the large input matrix for every one-versus-rest problem.
  • Model sparsity via restricted ambiguity: The ambiguity-control parameter ∆ prunes weights with absolute value below ∆, trading model size and prediction speed against reproducing the exact l2-regularized model.In practice, ∆ = 0.01 was fixed and observed to yield good performance.
  • Model sparsity via restricted ambiguity: ∆ = 0.01 reduces Wikipedia-31K's model from 30GB to 500MB and WikiLSHTC-325K's from 870GB to 3GB.The latter corresponds to around three orders of magnitude reduction; l1-regularization instead produced under-fitting and worse prediction performance than pruning after l2-regularization.
  • Prediction: The distributed sparse blocks support parallel inner-product computation for fast, potentially real-time prediction in XMC applications.The framework targets applications such as recommendation systems and personalized search.

3 Experimental evaluation

The evaluation uses public extreme-classification datasets and top-k metrics to compare DiSMEC with embedding-, tree-, and other baseline methods. The datasets and methods reflect the computational and statistical challenges of extreme label spaces.

  • Dataset description: The evaluation covers public datasets from Wikipedia, Amazon, and Delicious, with 13,330 to 670,091 labels and up to 4.3 million training points.The data use the repository’s prescribed train-test splits and sparse LibSVM format.
  • Evaluation metrics: Precision@k and nDCG@k for k=1, 3, and 5 are used because extreme classification emphasizes relevant predictions in limited top-k slots.nDCG@k additionally accounts for the ranking of correctly predicted labels.
  • Methods for comparison: The comparison includes embedding-based methods such as SLEEC, LEML, and RobustXML, alongside tree-based methods such as FastXML and LPSR-NB.The study also compares against PLT, L1-SVM, and PD-Sparse.
  • Methods for comparison: Embedding methods reduce label-space complexity through low-dimensional projections, whereas tree methods trade prediction accuracy for faster search by partitioning labels or features.The tree-based trade-off arises because errors at higher levels cannot be recovered.

4 Results

DiSMEC improves prediction accuracy over most baselines on large, diverse power-law datasets while retaining competitive performance on a dataset with stronger label correlations. Its distributed training and pruning reduce time and model size, with a tunable accuracy-size trade-off.

  • 4.1 Prediction Accuracy: 10% points absolute: DiSMEC improves precision@k over SLEEC on Amazon-670K, WikiLSHTC-325K, and Wiki-500K.The corresponding relative gains are reported as 20-to-25% points.
  • 4.1 Prediction Accuracy: SLEEC can perform slightly better than DiSMEC on Delicious-200k, which has a relatively larger average number of labels per training instance and likely stronger label correlations.This contrasts with the larger, more diverse datasets where DiSMEC outperforms embedding methods.
  • 4.1 Prediction Accuracy: 15%: DiSMEC’s gains in precision@k and nDCG@k over FastXML are reported for larger datasets.DiSMEC stores models in distributed batches that can be evaluated in parallel for prediction.
  • 4.2 Model Size: Three orders of magnitude smaller: DiSMEC reduces model size by filtering spurious parameters; WikiLSHTC-325K requires 3GB instead of 870GB.At 3GB, DiSMEC reaches 64.4% precision@1 versus SLEEC’s 52% using an ensemble of learners.
  • 4.3 Training and prediction Complexities: Within few hours: double-layer parallelization trains hundreds of thousands of labels at scale, including WikiLSHTC-325K in 6 hours on 400 cores or 3 hours on 1,000 cores.Wikipedia-31K trained in approximately 10 minutes on 300 cores.
  • 4.3 Training and prediction Complexities: Positive ∆ values produce sparser models, but increasing ∆ away from zero reduces prediction accuracy relative to ∆=0.01.The ∆=0 setting could not be tested because the resulting model was extremely large.

5 Conclusion and Future work

DiSMEC combines doubly parallelized learning with explicit model sparsity induction to improve prediction accuracy and scale to hundreds of thousands of labels. Its compact models support real-time extreme-classification applications, while tail-label coverage and criteria for choosing methods remain future work.

  • DiSMEC uses doubly parallelized architecture and explicit model sparsity induction to improve prediction accuracy over state-of-the-art industrial systems.The framework is presented as a carefully implemented one-vs-rest mechanism.
  • DiSMEC scales to problems involving hundreds of thousands of labels, and its compact models support real-time recommendation and ranking applications.
  • Future work will study classifier coverage of tail labels, which are normally under-represented in the training set.
  • Future work also includes formalizing degree correlation among labels to guide the choice between embedding-based and one-vs-rest methods.
  • The impact of the power-law exponent on method choice remains an open direction for study.
Loading 1609.02521v1…