A Tale of Two Efficient and Informative Negative Sampling Distributions
This work provides a more efficient and accurate negative sampling method for researchers and practitioners working with large-scale softmax classifiers, particularly in natural language processing and information retrieval.
This paper addresses the computational cost of softmax classifiers with a large number of classes by introducing two adaptive negative sampling distributions. Their C++ CPU implementation significantly outperforms optimized TensorFlow implementations on NVIDIA V100 GPUs in both wall-clock time and accuracy.
Softmax classifiers with a very large number of classes naturally occur in many applications such as natural language processing and information retrieval. The calculation of full softmax is costly from the computational and energy perspective. There have been various sampling approaches to overcome this challenge, popularly known as negative sampling (NS). Ideally, NS should sample negative classes from a distribution that is dependent on the input data, the current parameters, and the correct positive class. Unfortunately, due to the dynamically updated parameters and data samples, there is no sampling scheme that is provably adaptive and samples the negative classes efficiently. Therefore, alternative heuristics like random sampling, static frequency-based sampling, or learning-based biased sampling, which primarily trade either the sampling cost or the adaptivity of samples per iteration are adopted. In this paper, we show two classes of distributions where the sampling scheme is truly adaptive and provably generates negative samples in near-constant time. Our implementation in C++ on CPU is significantly superior, both in terms of wall-clock time and accuracy, compared to the most optimized TensorFlow implementations of other popular negative sampling approaches on powerful NVIDIA V100 GPU.