Extreme Classification via Adversarial Softmax Approximation

Robert Bamler, Stephan Mandt

Abstract

Training a classifier over a large number of classes, known as 'extreme classification', has become a topic of major interest with applications in technology, science, and e-commerce. Traditional softmax regression induces a gradient cost proportional to the number of classes $C$, which often is prohibitively expensive. A popular scalable softmax approximation relies on uniform negative sampling, which suffers from slow convergence due a poor signal-to-noise ratio. In this paper, we propose a simple training method for drastically enhancing the gradient signal by drawing negative samples from an adversarial model that mimics the data distribution. Our contributions are three-fold: (i) an adversarial sampling mechanism that produces negative samples at a cost only logarithmic in $C$, thus still resulting in cheap gradient updates; (ii) a mathematical proof that this adversarial sampling minimizes the gradient variance while any bias due to non-uniform sampling can be removed; (iii) experimental results on large scale data sets that show a reduction of the training time by an order of magnitude relative to several competitive baselines.

Introduction

In "extreme classification" tasks—such as tagging a Wikipedia article with a few categories out of hundreds of thousands or recommending one product out of millions—the standard tool is softmax regression. However, the softmax function requires a "normalization constant" that sums over every possible class. When $C$ (the number of classes) reaches the millions, every model update requires millions of calculations, making training prohibitively slow.

Researchers often use negative sampling to bypass this. Instead of calculating the sum for all classes, the model considers the correct class (the "positive") and a small subset of random "negative" classes. The drawback of uniform negative sampling is that random negatives are often "too easy" for the model to distinguish (e.g., a model easily tells a "Boston Terrier" apart from a "Bicycle"). This results in a weak gradient signal, leading to slow convergence and requiring many more iterations to reach high accuracy.

Methodology

The proposed Adversarial Softmax Approximation enhances the training signal through three main components:

  1. Adversarial Negative Sampling: Instead of picking negatives at random, the method uses an auxiliary model to pick "hard" negatives—classes that the current model is likely to confuse with the correct one.
  2. Probabilistic Decision Tree Sampler: To maintain computational efficiency, the adversarial sampler is implemented as a probabilistic binary decision tree. This allows the model to suggest "hard" negatives in $O(\log C)$ time, ensuring that the gradient updates remain inexpensive even as the number of classes grows.
  3. Bias Removal: Sampling non-uniformly introduces mathematical bias into the model's scores. The authors provide a rigorous proof and a correction formula to "un-bias" these scores at test time, ensuring valid probability estimates.

Datasets and Experimental Setup

The method was evaluated on two massive benchmarks from the Extreme Classification Repository. The scale of these datasets, involving hundreds of thousands of classes and millions of training points, represents the primary challenge the paper seeks to solve.

Dataset statistics and hyperparameter settings for Wikipedia-500K and Amazon-670K.

Both datasets utilized 512-dimensional XML-CNN features as inputs for the classification task.

Key Results and Insights

The core insight of this work is that the signal-to-noise ratio (SNR) of the training gradient is maximized when negative samples are difficult to distinguish from the positive ones. The authors mathematically prove that the ideal distribution for drawing negative samples is one that perfectly mimics the true data distribution.

Comparison of training time vs. predictive log-likelihood and accuracy across Wikipedia-500K and Amazon-670K datasets.
  • Speed: The proposed adversarial method reached peak accuracy roughly 10 times faster than competitive baselines like Noise Contrastive Estimation (NCE) or uniform negative sampling.
  • Accuracy: On the Wikipedia-500K dataset, the adversarial method achieved significantly higher predictive accuracy (~15%) compared to uniform sampling (~10%) within the same training timeframe.
  • Convergence: As shown in the performance curves, the method demonstrates much smoother and faster convergence in both log-likelihood and accuracy across both major datasets.

Conclusion

Adversarial Softmax Approximation offers a significant leap in efficiency for extreme classification. While the authors note a small "performance gap" compared to full softmax regression (which remains the gold standard for accuracy if computational resources are unlimited), the order-of-magnitude speedup makes this approach highly practical for real-world applications. Future work may explore "online" updates to the adversarial sampler to further improve the quality of the gradient signal during the training process.

Summary updated

Abstract

Training a classifier over a large number of classes, known as 'extreme classification', has become a topic of major interest with applications in technology, science, and e-commerce. Traditional softmax regression induces a gradient cost proportional to the number of classes $C$, which often is prohibitively expensive. A popular scalable softmax approximation relies on uniform negative sampling, which suffers from slow convergence due a poor signal-to-noise ratio. In this paper, we propose a simple training method for drastically enhancing the gradient signal by drawing negative samples from an adversarial model that mimics the data distribution. Our contributions are three-fold: (i) an adversarial sampling mechanism that produces negative samples at a cost only logarithmic in $C$, thus still resulting in cheap gradient updates; (ii) a mathematical proof that this adversarial sampling minimizes the gradient variance while any bias due to non-uniform sampling can be removed; (iii) experimental results on large scale data sets that show a reduction of the training time by an order of magnitude relative to several competitive baselines.
BibTeX
@inproceedings{bamler2020extreme,
  author = {Robert Bamler and Stephan Mandt},
  title = {{Extreme Classification via Adversarial Softmax Approximation}},
  booktitle = {International Conference on Learning Representations},
  year = {2020},
  url = {https://openreview.net/forum?id=B-zdG9gvlq},
}

Loading related content...

Figure