Classes for fast maximum entropy training

By Joshua Goodman. 2001

262 citations recorded by the source corpus.

Maximum entropy models are considered by many to be one of the most promising avenues of language modeling research. Unfortunately, long training times make maximum entropy research difficult. We present a speedup technique: we change the form of the model to use classes. Our speedup works by creating two maximum entropy models, the first of which predicts the class of each word, and the second of which predicts the word itself. This factoring of the model leads to fewer nonzero indicator functions, and faster normalization, achieving speedups of up to a factor of 35 over one of the best previous techniques. It also results in typically slightly lower perplexities. The same trick can be used to speed training of other machine learning techniques, e.g. neural networks, applied to any problem with a large number of outputs, such as language modeling.

Subfields: Artificial Intelligence, Probabilistic & Bayesian Methods

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 Probabilistic & Bayesian Methods

Citations in the corpus

Recurrent Neural Network Grammars (2016, methodology): “To further reduce the computational complexity of modeling the generation of a word, we use a class-factored softmax (Baltescu and Blunsom, 2015; Goodman, 2001).”
Adaptive Input Representations for Neural Language Modeling (2018, background): “The hierarchical softmax does this by introducing latent variables or clusters to simplify normalization (Goodman, 2001; Morin & Bengio, 2005; Mikolov et al., 2011).”
Bag of Tricks for Efficient Text Classification (2016, methodology): “In order to improve our running time, we use a hierarchical soft-max (Goodman, 2001) based on the Huffman coding tree (Mikolov et al., 2013).”
Efficient softmax approximation for GPUs (2016, methodology): “…or of a subset of them (Bengio et al., 2003b; Ji et al., 2015), from (ii) the approaches that compute exact probabilities for an approximate model yielding a lower computational time, such as the popular hierarchical softmax (Goodman, 2001a; Mnih & Hinton, 2009; Morin & Bengio, 2005).”
Unsupervised Learning by Predicting Noise (2017, background): “However, computing this loss is linear in the number of targets, making it impractical for large output spaces (Goodman, 2001).”
A bit of progress in language modeling (2001, methodology): “This is one of the main benefits of these models, according to their proponents, although other techniques (Goodman, 2001) also reduce the burden of normalization.”
Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention (2020, background): “For many years, softmax has been the bottleneck for training classification models with a large number of categories (Goodman, 2001; Morin & Bengio, 2005; Mnih & Hinton, 2009).”
Learning Longer Memory in Recurrent Neural Networks (2014, neutral): “A common trick introduced in Goodman (2001a) is to replace the soft-max function by a hierarchical soft-max.”
Joint Language and Translation Modeling with Recurrent Neural Networks (2013, methodology): “A well established efﬁciency trick uses word-classing to create a more efﬁcient two-step process (Goodman, 2001; Emami and Jelinek, 2005; Mikolov et al., 2011b) where each word is assigned a unique class.”
Compositional Morphology for Word Representations and Language Modelling (2014, methodology): “Our approach to reducing the computational cost of normalisation is to use a class-based decomposition of the probabilistic model (Goodman, 2001; Mikolov et al., 2011).”
Fast Parametric Learning with Activation Memorization (2018, background): “, 2016a) or hierarchical softmax (Goodman, 2001) due to the very large vocabulary size.”
Strategies for Training Large Vocabulary Neural Language Models (2015, methodology): “We follow Goodman (2001) and Mikolov et al. (2011b) and model a two-level tree.”
Understanding Contrastive Representation Learning through Alignment and Uniformity on the Hypersphere (2020, methodology): “However, due to its pairwise nature, Luniform is much simpler in form and avoids the computationally expensive softmax operation in Lcontrastive (Goodman, 2001; Bengio et al.; Gutmann & Hyvärinen, 2010; Grave et al., 2017; Chen et al., 2018).”
Dynamic Entity Representations in Neural Language Models (2017, background): “CFSM is a class factorized softmax function (Goodman, 2001; Baltescu and Blunsom, 2015).”
The QT21/HimL Combined Machine Translation System (2016, methodology): “The 5-gram language model is trained using KenLM (Heaﬁeld et al., 2013) on the Romanian part of the Common Crawl corpus concatenated with the Romanian part of the training data.”
Factored recurrent neural network language model in TED lecture transcription (2012, background): “Like [10, 16], we assume that each word belongs to exactly one class and divide the output layer into two parts: the first estimates the posterior probability distribution over all classes, y c = g( ∑”
Toward Deep Learning Software Repositories (2015, background): “One solution to controlling this complexity is to factorize the output layer [3], [17], [49], [58].”
Extensions of recurrent neural network language model (2011, methodology): “An even more promising approach was based on the assumption that words can be mapped to classes [13] [14].”