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

By Michalis K. Titsias. 2016

58 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

SHOPPER: A Probabilistic Model of Consumer Choice with Substitutes and Complements (2017, methodology): “We solve the problem with the approach developed by Titsias (2016).”
On the Properties of the Softmax Function with Application in Game Theory and Reinforcement Learning (2017, background): “It can be shown that, where (14) is referred as “one-vs-each” bound, which can be generalized to bounds on arbitrary probabilities [40].”
Multimodal Explanations by Predicting Counterfactuality in Videos (2018, methodology): “On the bound (13), we utilize the relationship (1 + ∑ i ai) ≤ ∏ i(1 + ai) [3].”
Multi-Class Gaussian Process Classification Made Conjugate: Efficient Inference via Data Augmentation (2019, background): “Using large categorical distributions is a challenging problem (Ruiz et al., 2018; Titsias, 2016).”
Bayesian Few-Shot Classification with One-vs-Each Pólya-Gamma Augmented Gaussian Processes (2020, methodology): “Instead, we propose a Gaussian process classifier based on a novel combination of Pólya-gamma augmentation and the one-vs-each softmax approximation [31] that allows us to efficiently marginalize over functions rather than model parameters.”
Augment and Reduce: Stochastic Inference for Large Categorical Distributions (2018, methodology): “5 For the softmax model, we compare A&R against the one-vs-each (OVE) bound (Titsias, 2016).”
cosFormer: Rethinking Softmax in Attention (2022, background): “…key properties that affect its empirical performance: (i) elements in the attention matrix are non-negative (Tsai et al., 2019; Katharopoulos et al., 2020); (ii) the non-linear re-weighting scheme acts as a stabilizer for the attention weights (Titsias, 2016; Gao & Pavel, 2017; Jang et al., 2016).”