In recent years neural language models (LMs) have set state-of-the-art performance for several benchmarking datasets. While the reasons for their success and their computational demand are well-documented, a comparison between neural models and more recent developments in  -gram models is neglected. In this paper, we examine the recent progress in  -gram literature, running experiments on 50 languages covering all morphological language families. Experimental results illustrate that a simple extension of Modified Kneser-Ney outperforms an LSTM language model on 42 languages while a word-level Bayesian  gram LM (Shareghi et al., 2017) outperforms the character-aware neural model (Kim et al., 2016) on average across all languages, and its extension which explicitly injects linguistic knowledge (Gerz et al., 2018a) on 8 languages. Further experiments on larger Europarl datasets for 3 languages indicate that neural architectures are able to outperform computationally much cheaper  -gram models:  -gram training is up to 15 , 000 quicker. Our experiments illustrate that standalone  -gram models lend themselves as natural choices for resource-lean or morphologically rich languages, while the recent progress has signifi-cantly improved their accuracy. Statistical language models (LMs) are the pivot for several natural language processing tasks where a model trained on a text corpus is required to assign a probability to a given sequence  1  2 ...  (de-noted by   1 ). This probability indicates how likely is for   1 to belong to the corpus and is decomposed into conditional probabilities of words given their preceding contexts as  (   1 ) =   =1  (   |   11 ) . In  -gram LMs the unbounded conditional probabilities  (   |   11 ) are approximated by imposing a finite-order Markov assumption,  (   |   11 )   (   |   1    +1 ) . Several smoothing techniques address the statistical sparsity issue for computing the conditional probabilities (Kneser and Ney, 1995; Chen and Goodman, 1999; Teh, 2006; Shareghi et al., 2016a), while others avoided the above approximation with unbounded hierarchical nonparametric Bayesian frameworks (Wood et al., 2011; Shareghi et al., 2017). Alternatively, neural LMs compute  (   |   11 ) via recurrent neural units which, in theory, are capable of encoding an unbounded context   11 . In recent years, neural LMs have become the prominent class of language modeling and have established state-of-the-art results on almost all su-ciently large benchmarks (Melis et al., 2018; Yang et al., 2018). While outperforming  -grams in terms of predictive accuracy, the computational shortcomings of neural LMs are well-documented: Training neural LMs is computationally expensive to the point that running experiments on large data (  a few GiBs) is beyond the reach of academic research to this date (Chen et al., 2016; Patwary et al., 2018; Puri et al., 2018). 1 Similarly, querying is slower for neural LMs due to the required matrix-based operations, whereas most of the widely used  -gram LM toolkits rely on a few hash lookups and much cheaper scalar-based operations (Liu et al., 2018; Tang and Lin, 2018). Nonetheless, it has been shown that the best predictive performance is still achieved by combining the two models via a basic interpolation or a mixture model (Jozefowicz et al., 2016; Neubig and Dyer, 2016): this indicates that the progress in  -gram LM should eventually be reflected in improving the 1 For instance,  -gram LMs could be trained on 32GiB of data on a single CPU with  32GiB of RAM in half a day (Shareghi et al., 2016b). A ballpark estimate for neural LMs, based on Puri et al. (2018), requires 26 Tesla V100 16GB GPUs to finish within the same amount of time while its financial cost is at least 100 higher. state-of-the-art performance. Inspired by this, in this paper we shed new light on the most notable recent progress in  -gram statistical LMs which improves their predictive accuracy. We demonstrate that under a recent massively multilingual experimental setup of Gerz et al. (2018a), more recent extensions of Kneser-Ney fam-ily of  -gram LMs (Shareghi et al., 2016a, 2017) are highly competitive with neural LMs. More specifi-cally, we experiment on 50 languages from dierent morphological families, and illustrate that a word-level Bayesian  -gram LM (Shareghi et al., 2017) outperforms the character-level informed neural counterpart (Kim et al., 2016) on average, and its linguistically informed variant (Gerz et al., 2018a) on 8 languages. On larger Europarl datasets we find that  -gram models cannot reach the performance peaks of computationally much more expensive neural models, but a 2 decrease in perplexity comes at the cost of 15 , 000 longer training time. Our work reveals that recent  -gram LMs should be used as strong baselines, especially in resource-lean LM data and for morphologically rich languages. Additionally,  -gram LMs oer a stringent way of dealing with Out-of-Vocabulary (OOVs) and rare words in a full vocabulary setting without relying on any pruning (Heafield, 2013). However, in neural LMs this remains an open question (Kawakami et al., 2017; Kim et al., 2016; Cotterell et al., 2018), while a common practice is pruning the training corpus and imposing closed vocabulary assump-tion (Mikolov et al., 2010) where rare words at training and unseen words at test are treated as an UNK token. We provide the mathematical underpinnings of  -gram models and highlight how this popular treatment works in favor of neural LMs (in comparative studies), and enforces  -gram LMs to perform much worse than their full potential. We now provide an overview of established smoothing techniques for  -gram LMs and their recent extensions. Smoothing is typically achieved by interpolation, where the probability of seeing a word   after a context   1    +1  (   |   1    +1 , ) is smoothed by its probability after a shorter context,   1    +2 , and follows the following general form:  (   |   1    +1 , )+  (   1    +1 , )  (   |   1    +2 , ) . (1) The term  (  ) represents the existing mass for the  -gram (e.g. via maximum likelihood estimation),  (   |   1    +1 , )  KN [  (     +1 )   ] +  (   1    +1 )   MKN [  (     +1 )   (    +1)  ] +  (   1    +1 )   {1 , 2 , 3+}  GKN [  (     +1 )   (    +1)  ] +  (   1    +1 )   {1 ,..., 10+}  BKN [  (     +1 )     +1     +1 ] +  (   1    +1 )+     +1      +1 ,      +1 ,        +1 Table 1: Top-level interpolation for  -gram LMs smoothings and its parameters, and [  ] + def = max{ , 0} . is the weight used for redistributing the preserved mass (e.g. via discounting), and  are the parameters of the smoothing technique. The recursion stops at the unigram level where the conditioning context is empty. The recursion at lower levels relies on dierent quantities (e.g. pseudo-counts) but for brevity we focus on the top level of recursion and only the first term,  (   |   1    +1 , ) , which suces to highlight the key dierences between smoothing techniques (see Table 1). Kneser-Ney ( KN ). The key parameters of KN (Kneser and Ney, 1995) are the  -gram specific discounts   which control the amount of preserved and redistributed mass at  th level of recursion. While learning the discounts (on held-out data) is a possibility, the following estimation is shown to work well in practice:   = 1  2  2 (  )  1 (  ) . It captures the characteristics of dierent  -gram orders by looking at the number of unique  -grams which occurred once,  1 (  ) , or twice,  2 (  ) in the training data, defined as follows: where  1+ (   ) = | {    (  ) > 0} | , and is referred to as a form of pseudo-count, and  (  ) denotes the frequency of sequence  . KN considers one discount value at each level of recursion and the discounts are bounded, 0    < 1 . defined with modifications applied to the discounting mechanism in order to make them sensitive to the existing mass  . The discounts are estimated as:   =  0 , if  = 0  (  +1)   +1 (  )   (  )  1 (  )  1 (  )+2  2 (  ) , if  <   (  +1)  4 (  )  3 (  ) . 1 (  )  1 (  )+2  2 (  ) , if   (4) where   (  ) is defined in Eq. (3), and  = 3 . This leads to three discount parameters {  1  ,  2  ,  3+  } for each recursion level, and allows for discount values to be as large as  (     +1 ) . MKN is widely accepted as the state-of-the-art  -gram LM and is very frequently confused with KN in the literature. Generalized Modified Kneser-Ney ( GKN ). In conditions where statistical sparsity is more severe a more refined approach to model the distributions is necessary. Motivated by this, Shareghi et al. (2016a) provided the mathematical proof (based on leave-one-out log-likelihood) of the discount bounds used in MKN and proposed a natural extension of its discount binning to  = 10 . This was shown to be eective for further perplexity reduction in out-of-domain setting where OOV ratio is naturally high. Bayesian Kneser-Ney ( BKN ). The Bayesian generalization of KN is the Hierarchical Pitman-Yor Process ( HPYP ) language model (Teh, 2006). This can be interpreted as a richer parameterization of KN and MKN , where the additional parameters (in-troduced shortly) allow the model to have more flexibility in capturing the desired distribution. The Pitman-Yor Process (Pitman et al., 1997), PYP ( , ,  ) , is a distribution defined over probability vectors (each draw from a PYP is a multinomial distribution) and has three parameters: a base probability vector  which is the expected value of a draw from a PYP , the concentration parameter   <  which controls the variation of draws from a PYP around  , and the discount parameter 0   < 1 which allows the drawn vectors to capture the power-law behavior. In the LM context, given a sequence of words     +1 , a draw from a PYP is a multinomial distribution over the words following this sequence, denoted by      +1 . This distribution can be captured by a vector of two counts {        +1 ,        +1 }     which defines a partitioning arrangement of      +1 , while dierent partitioning correspond to dierent multinomial draws from PYP . Here,       +1 is the total number of evidence 2 for word   after the context     +1 ,       +1 is the total number of partitions dedicated to   constrained by 0        +1        +1 , and  is the vocabulary. The HPYP ties PYP distributions through their base and oers the statistical mean to smooth over infinitely long contexts (Wood et al., 2011). For instance, PYP (   ,   , PYP (   (  ) ,   (  ) ,  ) ) is a two-level HPYP where a draw from a child distribution  , is smoothed by a draw from its parent  (  ) . Here,  (  ) is  with its most earliest word dropped (e.g.,  =  ,  (  ) =  ). KN can be seen as a special case for BKN , when the concentration is 0 , and {        +1 =1}     . BKN can be considered as a richer parameterization of MKN : The product      +1        +1 (see Table 1) allows  1 discounting, simulating the discount range of MKN , while an additional parameter      +1 permits further adjustments of the distribution. BKN is shown to outperform MKN (Shareghi et al., 2017) but relies on expensive parameter sampling. Out-of-Vocabulary ( OOV ). To complete the definitions we now explain how unseen words or contexts are handled during the computation without resorting to pruning or closed vocabulary setting. This treatment is the same for both non-Bayesian and Bayesian methods described in this paper. Let us consider the generic interpolation form of Eq. (1) and the maximum likelihood estimation of the  ( . ) term (hence  is dropped) in the top level of the interpolation,  (   |   1    +1 ) =  (     +1 )  (   1    +1 ) . Regardless of the level of interpolation and the paradigm used for computing the  ( . ) term,  ( . ) and  ( . ) always share the same denominator (normalizing factor). An unseen word can appear as the target word   , which results in  ( . ) = 0 as  (     +1 ) = 0 . It can also appear as a part of the prediction context   1    +1 in which case both the  ( . ) and  ( . ) terms will be undefined (and ignored) as the denominator  (   1    +1 ) = 0 . This procedure is applied to all levels of interpolation without loss of generality, and as can be seen it only relies on the basic mathematical property of the involved computations rather than any other presumptions about data preprocessing or vocabulary. 3 2 This is equal to  (     +1 ) at the top level of recursion, hence not mentioned as a part of  in Table 1. 3 See Shareghi (2017) for a comprehensive explanation of the models covered in this section. As our main large-scale experiment we use a typologically diverse set of 50 languages. These LM datasets cover many languages which are challenging in terms of data size, as well as the type-token ratio. In a less challenging setup, we experiment on 3 languages with larger training data from the Europarl (Koehn, 2005) to compare the two classes of LMs based on perplexity reduction and training time. For full data statistics, actual sampling of languages and data curation see Gerz et al. (2018a,b). The common practice of setting a frequency threshold and mapping training data unigrams ((  = 1 )-gram) to an UNK token degrades the performance of  -gram LMs by discarding a range of discount parameters: e.g., using threshold ( < 3 ) results in  1 (1) ,  2 (1) = 0 , both included in Eq. (2) and Eq. (4), increases the average perplexity score of 5-gram KN in our experiments by 11% . Motivated by its significance, we base our comparison on reported results by Gerz et al. (2018a): they deal with the task in the full vocabulary setting (Adams et al., 2017) with word-level predictions, and follow a relatively comparable treatment of unseen words with both  -gram and neural LM families (although not identical) at test time without enforcing any threshold over the training data. The benchmarked neural LMs include three models with word-level predictions: a standard LSTM (Zaremba et al., 2014), a CharCNN-LSTM (denoted as CNN ) (Kim et al., 2016) which incorporates character-level information in the input, and the Attract-Preserve model (denoted as AP ) (Gerz et al., 2018a) which injects further subword-level information. All benchmarked  -gram LMs are 5 -grams, with the exception of BKN which is an  -gram model trained via 5 samples 4 following the recipe of Shareghi et al. (2017). GKN results are based on  = 5 , tuned on a development set. Results and Discussion. The main results on the 50-languages benchmark are summarized in Table 2. The results for the more recent  -gram LMs indicate that these  -gram models are highly competitive with neural LMs in this challenging resource-lean setup. 5 For instance, for 26/50 languages all  -gram models outperform a regular LSTM , while GKN and BKN extend the lead to 42/50 4 Marginal improvements achieved with more sampling. 5 The size of each dataset is  40 K sentences, which is at the level of the standard Penn Treebank dataset often used for LM evaluation in English (Marcus et al., 1993). and 48/50 languages, respectively. For certain morphologically rich languages (e.g., Tamil, Mongolian, Hebrew), the  -gram LMs are able to outscore even character-aware neural LMs. On average we observe  -grams succeed, especially the BKN model, for introflexive and agglutinative languages which are known to have productive morphological systems: as reported in Table 2, they have the higher OOV ratio compared to the other language families. Overall, the best performing  -gram model, BKN , outperforms both the LSTM ( 42% reduction in perplexity) and CNN models ( 3% reduction in perplexity), while falling behind AP by 8% . These results highlight that  -gram models can serve as strong baselines for such morphologically rich languages with high OOV rates and type-to-token ratios, which are especially problematic in scarce data setups. Additionally, they suggest that more sophisticated  -gram variants such as GKN or BKN should be used to provide adequate comparison points with  -gram LMs than the commonly used KN or MKN . As expected, experiments on 10  larger Europarl datasets for 3 languages show that neural models outperform  -gram models in less challenging data-intensive scenarios. However, training on large datasets comes at the expense of training e-ciency for neural models: e.g., according to Figure 1 training non-Bayesian  -grams is around 15,000  quicker than training neural models. We leave a full-fledged investigation on the relation of training corpus size and ecacy of  -gram vs. neural LM training for future work. In addition, motivated by these preliminary insights, we advocate investing further eorts in future work into coupling the ideas behind  -gram and neural LMs towards improved language modeling. We provided an overview of previous work and very recent progress in  -gram LMs. The recent developments, when tested on a challenging set of 50 languages, demonstrated superior or highly competitive performance compared with neural LMs, while being substantially cheaper to train. We also shed light on a common issue in the experimental setups, concerning OOV or rare words handling, when comparing  -grams and neural LMs. While being non-trivial, investigating any correlation between cheap-to-compute heuristics (e.g., basic data statistics) and the choice of the most suitable model for a given dataset is worth exploring. Also, motivated by our findings, we will work on utilizing continuous space representations as side information in sampling the parameters of BKN , i.e. similar to Zhao et al. (2018), which potentially can reduce the gap between BKN and neural models. This work is supported by the ERC Consolidator Grant LEXICAL (648909). The authors would like to thank the anonymous reviewers for their helpful suggestions. The first author would like to also thank the members of the Language Technology Lab for their comments on the presentation of this work.
abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain other abstain abstain objective abstain result result result abstain abstain result method other other abstain abstain objective abstain abstain abstain abstain abstain abstain abstain abstain objective abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain method abstain method abstain abstain other other other