Fast, Small and Exact: Infinite-order Language Modelling with Compressed Suffix Trees

Fast, Small and Exact: Infinite-order Language Modelling with Compressed Suffix Trees Ehsan Shareghi,♭ Matthias Petri,♮ Gholamreza Haffari♭ and Trevor Cohn♮ ♭ Faculty of Information Technology, Monash University ♮ Computing and Information Systems, The University of Melbourne first.last@{monash.edu,unimelb.edu.au} Abstract Efficient methods for storing and querying are critical for scaling high-order m-gram lan- guage models to large corpora. We propose a language model based on compressed suffix trees, a representation that is highly compact and can be easily held in memory, while sup- porting queries needed in computing language model probabilities on-the-fly. We present several optimisations which improve query runtimes up to 2500×, despite only incurring a modest increase in construction time and memory usage. For large corpora and high Markov orders, our method is highly competi- tive with the state-of-the-art KenLM package. It imposes much lower memory requirements, often by orders of magnitude, and has run- times that are either similar (for training) or comparable (for querying). 1 Introduction Language models (LMs) are fundamental to many NLP tasks, including machine translation and speech recognition. Statistical LMs are probabilis- tic models that assign a probability to a sequence of words wN 1 , indicating how likely the sequence is in the language. m-gram LMs are popular, and prove to be accurate when estimated using large corpora. In these LMs, the probabilities of m-grams are often precomputed and stored explicitly. Although widely successful, current m-gram LM approaches are impractical for learning high-order LMs on large corpora, due to their poor scaling prop- erties in both training and query phases. Prevailing methods (Heafield, 2011; Stolcke et al., 2011) pre- compute all m-gram probabilities, and consequently need to store and access as many as a hundred of bil- lions of m-grams for a typical moderate-order LM. Recent research has attempted to tackle scalabil- ity issues through the use of efficient data structures such as tries and hash-tables (Heafield, 2011; Stol- cke et al., 2011), lossy compression (Talbot and Os- borne, 2007; Levenberg and Osborne, 2009; Guthrie and Hepple, 2010; Pauls and Klein, 2011; Church et al., 2007), compact data structures (Germann et al., 2009; Watanabe et al., 2009; Sorensen and Allauzen, 2011), and distributed computation (Heafield et al., 2013; Brants et al., 2007). Fundamental to all the widely used methods is the precomputation of all probabilities, hence they do not provide an adequate trade-off between space and time for high m, both during training and querying. Exceptions are Ken- nington et al. (2012) and Zhang and Vogel (2006), who use a suffix-tree or suffix-array over the text for computing the sufficient statistics on-the-fly. In our previous work (Shareghi et al., 2015), we extended this line of research using a Compressed Suffix Tree (CST) (Ohlebusch et al., 2010), which provides a considerably more compact searchable means of storing the corpus than an uncompressed suffix array or suffix tree. This approach showed favourable scaling properties with m and had only a modest memory requirement. However, the method only supported Kneser-Ney smoothing, not its modi- fied variant (Chen …

Content truncated to 500 words