Interpolated Spectral NGram Language Models

Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 5926–5930 Florence, Italy, July 28 - August 2, 2019. c⃝2019 Association for Computational Linguistics 5926 Interpolated Spectral NGram Language Models Ariadna Quattoni and Xavier Carreras dMetrics Brooklyn, NY 11211 {ariadna.quattoni,xavier.carreras}@dmetrics.com Abstract Spectral models for learning weighted non- deterministic automata have nice theoretical and algorithmic properties. Despite this, it has been challenging to obtain competitive results in language modeling tasks, for two main rea- sons. First, in order to capture long-range de- pendencies of the data, the method must use statistics from long substrings, which results in very large matrices that are difficult to de- compose. The second is that the loss func- tion behind spectral learning, based on mo- ment matching, differs from the probabilis- tic metrics used to evaluate language mod- els. In this work we employ a technique for scaling up spectral learning, and use in- terpolated predictions that are optimized to maximize perplexity. Our experiments in character-based language modeling show that our method matches the performance of state- of-the-art ngram models, while being very fast to train. 1 Introduction In the recent years we have witnessed the develop- ment of spectral methods based on matrix decom- positions to learn Probabilistic Non-deterministic Finite Automata (PNFA) and related models (Hsu et al., 2009, 2012; Bailly et al., 2009; Balle et al., 2011; Cohen et al., 2012; Balle et al., 2014). Es- sentially, PNFA can be regarded as recurrent neu- ral networks where the function that predicts the dynamic state representation from previous states is linear. Despite the expressiveness of PNFA and the strong theoretical properties of spectral learn- ing algorithms, it has been challenging to get com- petitive results on language modeling tasks. We argue and confirm with our experiments that there are two main reasons why using spectral meth- ods for language modeling is challenging. The first reason is a scalability problem to handle long range dependencies. The spectral method is based on computing a Hankel matrix that contains statis- tics of expectations over substrings generated by the target language. If we want to incorporate long-range dependencies we need to consider long substrings. A consequence of this is that the Han- kel matrix can become too large to make it prac- tical to perform algebraic decompositions. To ad- dress this problem we use the basis selection tech- nique by Quattoni et al. (2017) to scale spectral learning and model long range dependencies. Our experiments confirm that modeling long range de- pendencies is essential to obtain competitive lan- guage models. The second limitation of classical spectral methods when applied to language modeling is that the loss function that the learning algorithm attempts to minimize is not aligned with the loss function that is used to evaluate model perfor- mance. Spectral methods minimize the ℓ2 dis- tance on the prediction of expectations of sub- strings up to a certain length (see Balle et al. (2012) for a formulation of spectral learning in terms of loss minimization), while …

Content truncated to 500 words