great deal of research on improving the speed of the softmax function by various approximations. Hierarchical NNLM is a class-based model that consists of a neural network that predicts the class and separate neural networks that predict the word inside a class [@Kuo:2012]. This can reduce training time of feedforward networks considerably, because different n-grams are used to train each word prediction model. Hierarchical softmax is a single model that factors the output probabilities into the product of multiple softmax functions. The idea has originally been used in maximum entropy training [@Goodman:2001], but exactly the same idea can be applied to neural networks [@Morin:2005]. SOUL combines a shortlist for the most frequent words with hierarchical softmax for the out-of-shortlist words [@Le:2011]. Adaptive softmax [@Grave:2016] is a similar approach that optimizes the word cluster sizes to minimize computational cost on GPUs.

Another group of methods do not modify the model, but use sampling during training to approximate the expensive softmax normalization. These methods speed up training, but use normal softmax during evaluation. Importance sampling is a Monte Carlo method that samples words from a distribution that should be close to the network output distribution [@Bengio:2003:AISTATS]. Noise-contrastive estimation (NCE) samples random words, 