Large-scale Long Short-Term Memory (LSTM) cells are often the building blocks of many state-of-the-art algorithms for tasks in Natural Language Processing (NLP). However, LSTMs are known to be computationally inefficient because the memory capacity of the models depends on the number of parameters, and the inherent recurrence that models the temporal dependency is not parallelizable. In this paper, we propose simple, but effective, low-rank matrix factorization (MF) algorithms to compress network parameters and significantly speed up LSTMs with almost no loss of performance (and sometimes even gain). To show the effectiveness of our method across different tasks, we examine two settings: 1) compressing core LSTM layers in Language Models, 2) compressing biLSTM layers of ELMo~\citep{ELMo} and evaluate in three downstream NLP tasks (Sentiment Analysis, Textual Entailment, and Question Answering). The latter is particularly interesting as embeddings from large pre-trained biLSTM Language Models are often used as contextual word representations. Finally, we discover that matrix factorization performs better in general, additive recurrence is often more important than multiplicative recurrence, and we identify an interesting correlation between matrix norms and compression performance.

 Long Short-Term Memory (LSTM) networks (Hochreiter & Schmidhuber, 1997; BID11 have become the core of many models for tasks that require temporal dependency. They have particularly shown great improvements in many different NLP tasks, such as Language Modeling (Sundermeyer et al., 2012; Mikolov, 2012) , Semantic Role Labeling (He et al., 2017) , Named Entity Recognition (Lee et al., 2017) , Machine Translation BID0 , and Question Answering (Seo et al., 2016) . Recently, a bidirectional LSTM has been used to train deep contextualized Embeddings from Language Models (ELMo) (Peters et al., 2018a) , and has become a main component of state-of-the-art models in many downstream NLP tasks.However, there is an obvious drawback of scalability that accompanies these excellent performances, not only in training time but also during inference time. This shortcoming can be attributed to two factors: the temporal dependency in the computational graph, and the large number of parameters for each weight matrix. The former problem is an intrinsic nature of RNNs that arises while modeling temporal dependency, and the latter is often deemed necessary to achieve better generalizability of the model (Hochreiter & Schmidhuber, 1997; BID11 . On the other hand, despite such belief that the LSTM memory capacity is proportional to model size, several recent results have empirically proven the contrary, claiming that LSTMs are indeed over-parameterized BID4 James Bradbury & Socher, 2017; Merity et al., 2018; Melis et al., 2018; Levy et al., 2018) . Naturally, such results motivate us to search for the most effective compression method for LSTMs in terms of performance, time, and practicality, to cope with the aforementioned issue of scalability. There have been many solutions proposed to compress such large, over-parameterized neural networks including parameter pruning and sharing BID12 Huang et al., 2018) , low-rank Matrix Factorization (MF) (Jaderberg et al., 2014) , and knowledge distillation (Hinton et al., 2015) . However, most of these approaches have been applied to Feed-forward Neural Networks and Convolutional Neural Networks (CNNs), while only a small attention has been given to compressing LSTM architectures (Lu et al., 2016; BID1 , and even less in NLP tasks. Notably, See et al. (2016) applied parameter pruning to standard Seq2Seq (Sutskever et al., 2014) architecture in Neural Machine Translation, which uses LSTMs for both encoder and decoder. Furthermore, in language modeling, BID13 uses Tensor-Train Decomposition (Oseledets, 2011 BID18 uses binarization techniques, and Kuchaiev & Ginsburg (2017) uses an architectural change to approximate low-rank factorization.All of the above mentioned works require some form of training or retraining step. For instance, Kuchaiev & Ginsburg (2017) requires to be trained completely from scratch, as well as distillation based compression techniques (Hinton et al., 2015) . In addition, pruning techniques (See et al., 2016) often accompany selective retraining steps to achieve optimal performance. However, in scenarios involving large pre-trained models, e.g. ELMo (Peters et al., 2018a) , retraining can be very expensive in terms of time and resources. Moreover, compression methods are normally applied to large and over-parameterized networks, but this is not necessarily the case in our paper. We consider strongly tuned and regularized state-of-the-art models in their respective tasks, which often already have very compact representations. These circumstances make the compression much more challenging, but more realistic and practically useful.In this work, we advocate low-rank matrix factorization as an effective post-processing compression method for LSTMs which achieve good performance with guaranteed minimum algorithmic speed compared to other existing techniques. We summarize our contributions as the following:• We thoroughly explore the limits of several different compression methods (matrix factorization and pruning), including fine-tuning after compression, in Language Modeling, Sentiment Analysis, Textual Entailment, and Question Answering.• We consistently achieve an average of 1.5x (50% faster) speedup inference time while losing ∼1 point in evaluation metric across all datasets by compressing additive and/or multiplicative recurrences in the LSTM gates.• In PTB, by further fine-tuning very compressed models (∼98%) obtained with both matrix factorization and pruning, we can achieve ∼2x (200% faster) speedup inference time while even slightly improving the performance of the uncompressed baseline.• We discover that matrix factorization performs better in general, additive recurrence is often more important than multiplicative recurrence, and we identify clear and interesting correlations between matrix norms and compression performance. In conclusion, we exhaustively explored the limits of compressing LSTM gates using low-rank matrix factorization and pruning in four different NLP tasks. Our experiment results and norm analysis show that show that Low-Rank Matrix Factorization works better in general than pruning, but if the matrix is particularly sparse, Pruning works better. We also discover that inherent low-rankness and low nuclear norm correlate well, explaining why compressing multiplicative recurrence works better than compressing additive recurrence. In future works, we plan to factorize all LSTMs in the model, e.g. BiDAF model, and try to combine both Pruning and Matrix Factorization. In this section, we provide the semi-NMF algorithm and we elaborate the optimization and the aim of each step. This algorithm is an extension of NMF, where the data matrix is remained unconstrained BID7 . The original NMF optimization function shows in 8. Semi-NMF ignores the constraint in U as showed in 9. DISPLAYFORM0 Exploring the relationships between matrix factorization and K-means clustering has implications for the interpretability of matrix factors Ding et al. FORMULA0 1. Initialize U and run k-means clustering Hartigan & Wong (1979) . DISPLAYFORM1 The objective function of k-means clustering DISPLAYFORM2 We can relax the range of v ki over the values in (0, 1) or (0, ∞). This restricts V to accept only nonnegative values and allow U to have mixed signs values.2. Update U by fixing V using this constraint. By fixing V, the solution of U can be obtained by calculating the derivative of dJ/dU = −2WV T + 2U VV T = 0. Then we can get the DISPLAYFORM3 The positive and negative parts are computed A DISPLAYFORM4 According to BID7 , this method will reach convergence. By fixing U, the residual ||W − UV T || 2 will decrease monotonically, and after fixing V, we get the optimal solution for the objective function.The algorithm is computed by using an iterative updating algorithm that alternates between the update of U and V BID7 . The steps are very similar to coordinate descent Luo & Tseng (1992) with some modifications. The optimization is convex in U or V, not both.In the latent space derived by the NMF factorization family, each axis captures the centroid of a particular cluster, and each sample is represented as an additive combination of the centroids. The cluster membership of each document can be easily determined by finding the corresponding cluster centroid (the axis) with which the document has the largest projection value. Note in particular that the result of a K-means clustering run can be written as a matrix factorization W = UV , where W ∈ R nm is the data matrix, U ∈ R nr contains the cluster centroids, and V ∈ R rm contains the cluster membership indicators.• Perform the NMF or semi-NMF on W to obtain the two non-negative matrices U and V.• Matrix U contains r n−dimensional cluster centers and matrix V contains membership weight for each of the m samples in each of the r clusters. One can assign data i to the cluster c if c = argmax j V ij . DISPLAYFORM5 The algorithm complexity in terms of time and memory is shown in TAB4 .
We propose simple, but effective, low-rank matrix factorization (MF) algorithms to speed up in running time, save memory, and improve the performance of LSTMs. Proposes to accelerate LSTM by using MF as the post-processing compression strategy and conducts extensive experiements to show the performance.