Entropy-based Pruning of Backoff Language Models

By Andreas Stolcke. 2000

359 citations recorded by the source corpus.

A criterion for pruning parameters from N-gram backoff language models is developed, based on the relative entropy between the original and the pruned model. It is shown that the relative entropy resulting from pruning a single N-gram can be computed exactly and efficiently for backoff models. The relative entropy measure can be expressed as a relative change in training set perplexity. This leads to a simple pruning criterion whereby all N-grams that change perplexity by less than a threshold are removed from the model. Experiments show that a production-quality Hub4 LM can be reduced to 26% its original size without increasing recognition error. We also compare the approach to a heuristic pruning criterion by Seymore and Rosenfeld (1996), and show that their approach can be interpreted as an approximation to the relative entropy criterion. Experimentally, both approaches select similar sets of N-grams (about 85% overlap), with the exact relative entropy criterion giving marginally better performance.

Subfields: Artificial Intelligence, Natural Language Processing

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 Natural Language Processing

Citations in the corpus

FastText.zip: Compressing text classification models (2016, methodology): “Classical approaches include feature pruning based on entropy (Stolcke, 2000) and quantization.”
Finding Function in Form: Compositional Character Models for Open Vocabulary Word Representation (2015, background): “In language modeling, it is frequent to prune higher order ngrams that do not encode any additional information (Seymore and Rosenfeld, 1996; Stolcke, 1998; Moore and Quirk, 2009).”
Randomized Language Models via Perfect Hash Functions (2008, methodology): “1/3 of its original size using entropy pruning (Stolcke, 1998).”
The A2iA Arabic Handwritten Text Recognition System at the Open HaRT2013 Evaluation (2014, methodology): “Due to computational constraints, in particular the limited memory size, the interpolated big LM was severely pruned using entropy pruning scheme [17].”
Deep Neural Network Language Models (2012, methodology): “This model is pruned to contain a total of 350K n-grams using entropy-based pruning (Stolcke, 1998) .”
Statistical Language Models Based on Neural Networks (2012, methodology): “Pruning was performed using SRILM toolkit and entropy pruning technique described in [73].”
Detecting Fake Content with Relative Entropy Scoring (2008, methodology): “Language model pruning can be performed using conditional probability estimates [14] or relative entropy between n-gram distributions [17].”
Bayesian Language Model Interpolation for Mobile Speech Input (2011, methodology): “Given that using the staticallyinterpolated models in a first pass followed by rescoring with the dynamically-interpolated model did not introduce significant search errors, we chose to increase the ‘distance’ between the two passes by pruning the statically-interpolated models using entropy pruning”
SRILM - an extensible language modeling toolkit (2002, methodology): “prune N-gram parameters, using an entropy criterion [10]”
Search by voice in Mandarin Chinese (2010, methodology): “In the experiments, Katz smoothing [3] and entropy-based pruning [4] were used, and count-cutoff thresholds of 0, 0, 0, 1 and 2 were used for n -gram units ( n is from 1 to 5) respectively.”
Recurrent neural network based language model personalization by social network crowdsourcing (2013, background): “[10, 16, 17], including various adaptation techniques, have been proven to work very well for many applications.”
Investigating Generative Adversarial Networks based Speech Dereverberation for Robust Speech Recognition (2018, methodology): “We also used entropy-based parameter pruning [31] and the threshold was set to be 10−8.”
Accurate and compact large vocabulary speech recognition on mobile devices (2013, methodology): “We then apply relative entropy pruning [16] as implemented in the OpenGrm toolkit [17].”