One-vs-Each Approximation to Softmax for Scalable Estimation of Probabilities

Abstract

The softmax representation of probabilities for categorical variables plays a prominent role in modern machine learning with numerous applications in areas such as large scale classification, neural language modeling and recommendation systems. However, softmax estimation is very expensive for large scale inference because of the high cost associated with computing the normalizing constant. Here, we introduce an efficient approximation to softmax probabilities which takes the form of a rigorous lower bound on the exact probability. This bound is expressed as a product over pairwise probabilities and it leads to scalable estimation based on stochastic optimization. It allows us to perform doubly stochastic estimation by subsampling both training instances and class labels. We show that the new bound has interesting theoretical properties and we demonstrate its use in classification problems.

arXiv commentTo appear in NIPS 2016

References in corpus (3)

• BlackOut: Speeding up Recurrent Neural Network Language Models With Very Large Vocabularies
• Deep Networks With Large Output Spaces
• Scalable Bayesian Modelling of Paired Symbols

Cited by in corpus (8)

• Understanding Negative Samples in Instance Discriminative Self-supervised Representation Learning
• Fast Predictive Uncertainty for Classification with Bayesian Deep Networks
• Multi-Class Gaussian Process Classification Made Conjugate: Efficient Inference via Data Augmentation
• Bayesian Few-Shot Classification with One-vs-Each Pólya-Gamma Augmented Gaussian Processes
• Extreme Classification via Adversarial Softmax Approximation
• Variational Estimation for Multidimensional Generalized Partial Credit Model
• Statistical optimality and stability of tangent transform algorithms in logit models
• Preferential Batch Bayesian Optimization