Computations for the softmax function in neural network models are expensive when the number of output classes is large. This can become a significant issue in both training and inference for such models. In this paper, we present Doubly Sparse Softmax (DS-Softmax), Sparse Mixture of Sparse of Sparse Experts, to improve the efficiency for softmax inference. During training, our method learns a two-level class hierarchy by dividing entire output class space into several partially overlapping experts. Each expert is responsible for a learned subset of the output class space and each output class only belongs to a small number of those experts. During inference, our method quickly locates the most probable expert to compute small-scale softmax. Our method is learning-based and requires no knowledge of the output class partition space a priori. We empirically evaluate our method on several real-world tasks and demonstrate that we can achieve significant computation reductions without loss of performance. Deep learning models have demonstrated impressive performance in many classification problems BID15 . In many of these models, the softmax function/layer is commonly used to produce categorical distributions over the output space. Due to its linear complexity, the computation for the softmax layer can become a bottleneck with large output dimensions, such as language modeling BID3 , neural machine translation BID1 and face recognition BID33 . In some models, softmax contributes to more than 95% computation. This becomes more of an issue when the computational resource is limited, like mobile devices BID13 .Many methods have been proposed to reduce softmax complexity for both training and inference phases. For training, the goal is to reduce the training time. Sampling based BID11 and hierarchical based methods BID9 BID25 were introduced. D-Softmax BID6 and Adaptive-Softmax BID10 , construct two levelhierarchies for the output classes based on the unbalanced word distribution for training speedup. The hierarchies used in these methods are either pre-defined or constructed manually, which can be unavailable or sub-optimal. Unlike training , in inference, our goal is not to computing the exact categorical distribution over the whole vocabulary, but rather to search for top-K classes accurately and efficiently. Existing work BID31 BID30 BID37 on this direction focus on designing efficient approximation techniques to find the top-K classes given a trained model. Detailed discussions of related works are to be found in Section 4.Our work aims to improve the inference efficiency of the softmax layer. We propose a novel Doubly Sparse softmax (DS-Softmax) layer. The proposed method is motivated by BID29 , and it learns a two-level overlapping hierarchy using sparse mixture of sparse experts. Each expert is trained to only contain a small subset of entire output class space, while each class is permitted to belong to more than one expert. Given a set of experts and an input vector , the DS-Softmax first selects the top expert that is most related to the input (in contrast to a dense mixture of experts), and then the chosen expert could return a scored list of most probable classes in it sparse subset. This method can reduce the linear complexity in original softmax significantly since it does not need to consider the whole vocabulary.We conduct experiments in different real tasks, ranging from language modeling to neural machine translation. We demonstrate our method can reduce softmax computation dramatically without loss of prediction performance. For example, we achieved more than 23x speedup in language modeling and 15x speedup in translation with similar performances. Qualitatively, we demonstrate learned two-level overlapping hierarchy is semantically meaningful on natural language modeling tasks.2 DS-SOFTMAX: SPARSE MIXTURE OF SPARSE EXPERTS 2.1 BACKGROUND Before introducing our method, we first provide an overview of the background.Hierarchical softmax. Hierarchical softmax uses a tree to organize output space where a path represents a class BID25 . There are a few ways to construct such hierarchies. Previous work BID25 BID6 BID10 focus on building hierarchies with prior knowledge. Other approaches, like BID24 , performed clustering on embeddings to construct a hierarchy. Our work aims to learn a two-level hierarchy while the major difference is that we allow overlapping in the learned hierarchy.Sparsely-gated mixture-of-experts. BID29 designed a sparsely gated mixture of experts model so that outrageously large networks can achieve significantly better performance in language modeling and translation. They borrowed conditional computation idea to keep similar computation even though the number of parameters increases dramatically. Their proposed sparsely-gated Mixture of Experts (MoE) only use a few experts selected by the sparsely gating network for computation on each example. The original MoE cannot speedup softmax computation but serves as an inspiration for our model design.Group lasso. Group lasso has been commonly used to reduce effective features in linear model BID7 BID21 . Recently, it has been applied in a neural network for regularization BID28 and convolutional deep neural network speedup BID36 . It has been demonstrated as an effective method to reduce the number of nodes in the neural network. In this work, we use group lasso to sparsify the experts. In this paper, we present doubly sparse: sparse mixture of sparse experts for efficient softmax inference. Our method is trained end-to-end. It learns a two-level overlapping class hierarchy. Each expert is learned to be only responsible for a small subset of the output class space. During inference, our method first identifies the responsible expert and then perform a small scale softmax computation just for that expert. Our experiments on several real-world tasks have demonstrated the efficacy of our proposed method.
We present doubly sparse softmax, the sparse mixture of sparse of sparse experts, to improve the efficiency for softmax inference through exploiting the two-level overlapping hierarchy.  This paper proposes a fast approximation to the softmax computation when the number of classes is very large. This paper proposes a sparse mixture of sparse experts that learns a two-level class hierarchy for efficient softmax inference.