Abstract
We consider training probabilistic classifiers in the case that the number of classes is too large to perform exact normalisation over all classes. We show that the source of high variance in standard sampling approximations is due to simply not including the correct class of the datapoint into the approximation. To account for this we explicitly sum over a subset of classes and sample the remaining. We show that this simple approach is competitive with recently introduced non likelihood-based approximations.
Introduction
Training classifiers with massive label sets—such as the 100,000+ words encountered in natural language processing—presents a significant computational challenge known as the "Softmax Bottleneck." Calculating the probability of a single class requires summing the scores of every other class to normalize the result.
Standard Importance Sampling (IS) is often used to estimate this total sum, but it is notoriously unstable. This paper identifies the root cause: if a random sample misses the "correct" class for a given data point, the estimated probability becomes highly inaccurate. This leads to unbounded gradients that can cause the model to diverge during training.
Methodology: Complementary Sum Sampling (CSS)
The authors propose Complementary Sum Sampling (CSS), an elegantly simple modification to stabilize training. The approach follows three steps:
- Split the Sum: The total normalization sum is divided into a small set of "important" classes and a "complementary" set containing the rest.
- Always Include the Target: For every training example, the correct class ($c_n$) is explicitly included in the "important" set.
- Sample the Remainder: A sampling technique (such as Importance Sampling or Bernoulli Sampling) is used only to estimate the sum of the remaining "negative" classes.
By ensuring the correct class is always present in the denominator, the resulting gradient weights are mathematically guaranteed to stay within a stable range (between -1 and 1), preventing the exploding updates that plague standard IS.
Experimental Setup
The paper evaluates CSS on two main tasks:
- Synthetic Softmax Regression: A controlled environment with 1,000 classes and 2,000 data points used to visualize how different approximations track the true likelihood.
- Neural Word Prediction: A large-scale task using the Europarl dataset (English part of the European Parliament Proceedings), involving 2 million sentences and a vocabulary of 47,170 distinct words.
Key Insights
- The Stability Gap: In standard IS, the gradient is not bounded. If the model is confident about the correct class but that class is missing from the sample, the math breaks. CSS bridges this gap by ensuring the target is always present.
- Likelihood vs. Discriminative Objectives: Unlike alternatives like Noise Contrastive Estimation (NCE) or BlackOut, which change the training objective to a discrimination task, CSS stays true to the original Maximum Likelihood objective.
- Ranking as a Special Case: The authors demonstrate that common "Ranking" or "Hinge Loss" approaches are essentially crude, single-sample versions of CSS, providing a theoretical bridge between these methodologies.
Results
CSS demonstrated high stability in synthetic tests, where it was virtually indistinguishable from exact calculations. On the Europarl word prediction task, the "IS Correct Class" variant performed as well as BlackOut, the reigning state-of-the-art.
Crucially, CSS allowed for a 50-fold decrease in computation cost per minibatch compared to exact softmax while maintaining high accuracy. Furthermore, CSS proved more robust than NCE in scenarios where self-normalization assumptions were not met.
Limitations and Future Work
While CSS provides a consistent estimator, it remains a biased estimator of the log-likelihood. However, the authors argue the stability gains outweigh this bias. Additionally, while CSS speeds up training, it does not address the inference bottleneck (predicting the top class for new inputs), which still requires checking all classes unless combined with techniques like Hierarchical Softmax. Future research may explore adaptive sampling distributions to further reduce the variance of the complementary sum.
Summary updated