Efficient Exact Gradient Update for training Deep Networks with Very Large Sparse Targets

By Pascal Vincent, Alexandre de Brébisson, Xavier Bouthillier. 2014

50 citations recorded by the source corpus.

An important class of problems involves training deep neural networks with sparse prediction targets of very high dimension D. These occur naturally in e.g. neural language models or the learning of word-embeddings, often posed as predicting the probability of next words among a vocabulary of size D (e.g. 200 000). Computing the equally large, but typically non-sparse D-dimensional output vector from a last hidden layer of reasonable dimension d (e.g. 500) incurs a prohibitive O(Dd) computational cost for each example, as does updating the D x d output weight matrix and computing the gradient needed for backpropagation to previous layers. While efficient handling of large sparse network inputs is trivial, the case of large sparse targets is not, and has thus so far been sidestepped with approximate alternatives such as hierarchical softmax or sampling-based approximations during training. In this work we develop an original algorithmic approach which, for a family of loss functions that includes squared error and spherical softmax, can compute the exact loss, gradient update for the output weights, and gradient for backpropagation, all in O(d^2) per example instead of O(Dd), remarkably without ever computing the D-dimensional output. The proposed algorithm yields a speedup of D/4d , i.e. two orders of magnitude for typical sizes, for that critical part of the computations that often dominates the training time in this kind of network architecture.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Optimization & Training

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

In Computer Vision and Pattern Recognition

In Optimization & Training

Citations in the corpus

Exploring the Limits of Language Modeling (2016, background): “, 2003; Bengio & Senécal, 2008), Negative Contrast Estimation (NCE) (Gutmann & Hyvärinen, 2010; Mnih & Kavukcuoglu, 2013), self normalizing partition functions (Vincent et al., 2015) or Hierarchical Softmax (Morin & Bengio, 2005; Mnih & Hinton, 2009) – they all offer good solutions to this problem.”
Deep Reinforcement Learning that Matters (2017, methodology): “By intuition, in gradient based methods (as used in most deep RL) a large and sparse output scale can result in problems regarding saturation and inefﬁciency in learning (LeCun et al. 2012; Glorot and Bengio 2010; Vincent, de Br´ebisson, and Bouthillier 2015).”
Efficient softmax approximation for GPUs (2016, background): “[44] have also proposed an efficient way to train model with high dimensional output space.”
From Softmax to Sparsemax: A Sparse Model of Attention and Multi-Label Classification (2016, background): “…2001; Menke & Martinez, 2008), the multinomial probit (Albert & Chib, 1993), the spherical softmax (Ollivier, 2013; Vincent, 2015; de Br´ebisson & Vincent, 2015), or softmax approximations (Bouchard, 2007), while theoretically or computationally advantageous for certain scenarios, lack some of…”
BlackOut: Speeding up Recurrent Neural Network Language Models With Very Large Vocabularies (2015, methodology): “• Exact gradient on limited loss functions (Vincent et al., 2015) introduces an algorithmic approach to efﬁciently compute the exact loss, gradient update for the output weights in O ( h 2 ) per training example instead of O ( V h ) .”
Augment and Reduce: Stochastic Inference for Large Categorical Distributions (2018, methodology): “Other methods replace the softmax with a scalable spherical family of losses (Vincent et al., 2015; de Brébisson & Vincent, 2016).”
Deep Unsupervised Similarity Learning Using Partially Ordered Sets (2017, background): “(4) can scale to an arbitrary number of classes, since it does not depend on a ﬁxed-sized output target layer, avoiding the shortcomings of large output spaces in CNN learning [31] 1 .”
Sampled Softmax with Random Fourier Features (2019, background): “…[5] partitions the classes into a tree based on class similarities, allowing for O ( d log n ) training and inference time; spherical softmax [6, 7] replaces the exponential function by a quadratic function, enabling efﬁcient algorithm to compute the updates of the output weights…”
An Exploration of Softmax Alternatives Belonging to the Spherical Loss Family (2015, methodology): “The spherical family described in Vincent et al. (2015) is composed of the functions that can be expressed using only the o c associated to non-zero y c , q = k o k 2 = i o 2 i the squared norm of the whole output vector and s = sum( o ) = i o i : Vincent et al. (2015) showed that for such loss…”