Dynamically Hierarchy Revolution: DirNet for Compressing Recurrent Neural Network on Mobile Devices

1 Introduction

Deep learning technique is becoming the dominant force of recent breakthroughs in artificial intelligence area [Geng et al., 2017]. Recently, Recurrent Neural Networks (RNNs) have gained wide attentions with dramatic performance improvements in sequential data modeling, e.g., automatic speech recognition (ASR) [Sak et al., 2014], language modeling [Mikolov et al., 2011], image captioning [Vinyals et al., 2017], neural machine translation [Cho et al., 2014], etc. Recently, due to the success of RNN-ASR [Lei et al., 2013], personal assistant system (e.g., Amazon's Alexa, Apple's Siri, Google Now, Samsung's Bixby, Microsoft's Cortana) has become a standard system configuration of smartphones.

Generally, the trained deep learning models are deployed on the cloud which requires strict Internet connection and also may compromise user privacy. Therefore, there is a high demand to deploy such RNNs with millions of parameters on mobile devices. Deep model compression techniques have been proposed to solve the mobile deployment problem. Specifically for RNNs model compression, a pruning based method [Narang et al., 2017] was introduced which progressively prunes away small parameters using a monotonically increasing threshold during training. Another representative method is to apply singular value decomposition (SVD) low rank approach for decomposing RNNs weight matrices [Prabhavalkar et al., 2016]. Although some good results for compressing RNNs have been reported, these works fail to consider the hierarchical changes of weight matrices. In addition, none of the existing methods can dynamically adjust the compression rate according to the requirement of the deployed mobile devices.

∗Work was done during the first author's internship at Samsung Research America.

†Corresponding author.

In this work, we propose a dynamically hierarchy revolution (DirNet) to address the problems in existing RNNs model compression methods (Fig. 1). To further compress the model with considering different degrees of redundancies among layers, we exploit a novel way of dynamically mining dictionary atoms from original network structures without manual setting the compression rate for different layers. Our approach achieves significant improvement in model compression compared to previous approaches. It also has much higher re-training's convergence rate and lower accuracy loss compared to the state-of-the-art. In addition, considering different functionalities among hierarchical hidden layers, we come up with the idea of adaptively adjusting sparsity of different hidden layers in RNNs. This can improve the precise structure approximation to the original network with minimizing the performance drop.

Our most significant contributions can be summarized into threefold: Firstly, this is the first work dynamically exploring dictionary learning in weight matrix of both RNN and LSTM that jointly compresses both hidden layer and inter layer to reconstruct original weight matrices. Secondly, our approach is a dynamic model compression algorithm. It can dynamically mine the dictionary atoms of the projection dictionary matrix within the layer to better learn a common codebook representation across inter-layer and recurrent layer. This can find the optimal numbers of neurons among layers to better control the degree of compression with negligible accuracy loss. Thirdly, given a hierarchical RNN structure, our approach can adaptively set various sparsities of sparse codes for each layer to minimize the performance drop for the compressed network. The experimental results demonstrate that DirNet achieves significant improvement in terms of compression scale and speedup rate compared to the state-of-theart approaches.

2 RelatedWork

In general, we can summarize existing RNN compression methods into three categories: Pruning, low-rank approximation, and knowledge distillation. The first pruning work was proposed by Han et al. [2015b] where a hard threshold was applied as the pruning criterion to compress the deep neural network. Li et al. [2017] discussed the optimization of non-tensor layers such as pooling and normalization without tensor-like trainable parameters for deep model compression. Xue et al. [2013] used low-rank approximation to reduce parameter dimensions in order to save storage and reduce time complexity. Denile et al. [2013] showed that the given neural network can be represented by a small number of parameters. Sainath et al. [2013] reduced the number of model parameters by applying the low-rank matrix factorization to simplify the neural network architecture.

Hinton et al [2015] learned a small student network to mimic the original teacher network by minimizing the loss between the student and teacher output. Kim et al. [2016] integrated knowledge distillation to approximately match the sequence-level distribution of the teacher network. Chen et al. [2017] introduced a knowledge of cross sample similarities for model compression and acceleration.

In addition, there are some other compression methods. Low-precision quantization [Xu et al., 2018] is a scalar-level compression method without considering the relation among learned parameters in layers. Compared to these works, our approach dynamically adjusts the compression rate across layers and explores the sparsity of weight matrices to compress RNN. It achieves better compression rate with less accuracy loss compared with above methods.

Recently, Han et al. [2017] used a pruning method to compress the LSTM on speech recognition problem and it reduced the parameters of the weight matrix to 10% and achieved 5X compression rate (each non-zero element is represented by its value and index in the matrix). However, DirNet considers the sparsity of various matrices and dynamically adjusts the sparsity based on the feature of models and gets a better compression rate. Our approach can compress the model by around 8X with negligible performance loss.

3 Methods

In this section, we first introduce the background of RNNs. Then, we present the basic sparse coding based RNN compression method without considering the mobile requirement and the hierarchical network structure. Further, we present the proposed approach DirNet.

3.1 RNN Background

Let t = 0, 1, · · · , T denotes time steps and l = 1, 2, · · · ,L denotes the hidden layers in RNN. At time t, hlt ∈ RN l denotes the activations of the l-th hidden layer with N l node. Therefore, the inputs to this layer at time t are donated by hl-1 t ∈ RN l-1 . Then, we can define the output activations of the l-th and (l + 1)-th layers in a classical RNN:

where σ(·) denotes a non-linear activation function and bl ∈ RN l and bl+1 ∈ RN l+1 represent bias vectors. W lx ∈ RN l+1×N l and W lh ∈ RN l×N l denote inter-layer and recurrent weight matrices, respectively.

Different from traditional RNNs, LSTM contains specialized cells called memory cell in the recurrent hidden layer. Empirically, LSTM has a memory cell for storing information for long periods of time, we use clt ∈ R to denote the long-term memory. LSTM can decide to overwrite the memory cell, retrieve it, or keep it for the next time step [Zaremba et al., 2014]. In this paper, our LSTM architecture is the same as [Graves et al., 2013]. The general structure is illustrated in Figure 2.

where i, o, f and g are input gate, output gate, forget gate and input modulation gate, respectively. And c denotes the memory cells and all gates are the same size as the memory cells. ⊙ is the element-wise product of the vectors. n and 4n denote the dimension of one gate and four gate, respectively.

3.2 Sparse Coding basedModel Compression

As indicated above, one direct way to compress RNN is to sparsify weight matrix W lx and W lh . Given a weight matrix W ∈ Rp×t , each wi ∈ Rp . Sparse coding aims to learn a dictionary D where D ∈ Rp×m and a sparse code matrix Z ∈ Rm×t . The original matrix W is modeled by a sparse linear combination of D and Z as W ≈ DZ. We can formulate the following optimization problem:

where Ψ = {D ∈ Rp×m : ∀j ∈ 1, · · · ,m, ||dj||2 ≤ 1}, dj denotes the jth column of D and Z = (z1, · · · , zt). λ is the positive regularization parameter and ||W||F denotes the Frobenius norm of the matrix.

For RNNs, we can compress simultaneously the weight matrices of both recurrent layer and inter-layer (from Eq. (1) or Eq. (2)). Such joint compression can be achieved by a projection matrix [Sak et al., 2014], denoted by Dl ∈ Rpl×N l (pl < N l ), such that, W lh = DlZ lh and W lx = DlZ lx . Therefore, we can incorporate this idea into Eq. (1) and Eq. (2), then we get the followings:

where Z lh ∈ Rpl×N l and Z lx ∈ Rpl×N l+1 . Therefore, we can calculate the compression rate by N l×N l+N l+1×N l pl×N l+pl×N l+pl×N l+1 .

However, a problem exists in this deep compression model is that the compression rate and the sparsity are manually set which limits the compression space. It would be much more efficient and promising to automatically set the compression rate and sparsity based on the understanding of deep neural network's structure. Also we should consider minimizing the training time during the model compression which may take weeks or even months, especially for RNN based sequential models. In this paper, we propose DirNet, which can dynamically adjust the sparsity of Eq. (5) and Eq. (7), to meet this requirement.

Algorithm 1: DirNet

input : Inter-layer matrixWh and recurrent matrixWx, shift operators △, K, M, λ1 = 0.1, λ2 output: Compressed weight matrices Zh, Zx and projection matrix D 1 begin 2 for l = 1 → L do 3 Initialize Dl and Z lh 4 repeat 5 Update sparse code zk i ←CD(dki , zk-1 i , wi) 6 Update dictionary dk ← arg min{di}Ki=1 ∑Mj=1 1 2 ||xj - ∑Ki=1 zijδij(di)||22 , s.t.||dk||2 = 1 7 until convergence; 8 hlt = σ(W l-1 x hl-1 t +DlZ lhhlt-1 + bl ) 9 while model is unempty do 10 t = 0 11 repeat 12 t = t +1 13 Fix Θlt update zlt according to Eq. 14 14 Fix zlt update Θlt according to Eq. 15 15 until Convergence; 16 Θτ+1 0 = Θτt 17 τ = τ +1 18 hl+1 t = σ(DlZ lxhlt +W l+1 h hl+1 t-1 + bl+1 ) 19 return Zh, Zx, D;

DirNet is mainly composed of two steps and depicted graphically in Fig. 1: In Step 1, a dynamically adaptive dictionary learning (Sec. 3.3) is proposed to adapt the atoms in shared dictionary among inter-layer and recurrent layer to adjust the sparsity (compression rate and accuracy) within the layer (Eq. (5)). In Step 2, we propose an adaptive sparsity learning approach with considering the network's hierarchical structure (Sec. 3.4) to optimize the Z and sparsity parameter Θ hierarchically with an appropriate sparsity degree. The sparsity (compression rate and accuracy) achieved by different layers is depending on the number of neurons and the architecture of the specific layer. In general, the non-zero values in Z are ten to twenty percent of the original weight matrices W in our work. From this, we can find the proposed approach adaptively set various sparsity among the hierarchical RNN architecture on Eq. 7 instead of using a fixed fraction function of explained variance as advocated in Prabhavalkar et al. [2016]. We summarize the key steps of DirNet in Algorithm 1.

3.3 Dynamically Adaptive Dictionary Learning

It is an essential step to dynamically adjust the dimension of the projection matrices Dl to get the optimal compression rate. We introduce a shift operation △ on atoms to better adjust the compression rate. Given a set of shift operations △ which contains only small shifts relative to the size of the (time window), for every j there exist coefficients zij ∈ R

and shift operators δij ∈ △ [Hitziger et al., 2013], such that wj = ∑Ki=1 zijδij(di).

Now, we can formulate the dynamically adaptive dictionary learning problem as follows:

The problem becomes Eq. 4 when △ = {I}, thus we use alternate minimization to solve it.

Sparse Codes Update It is known that updating the sparse code is the most time consuming part [Mairal et al., 2009]. One of the state-of-the-art methods for solving such lasso problem is Coordinate descent (CD) [Friedman et al., 2007]. Given an input vector wi, CD initializes z0 i = 0 and then updates the sparse codes many times via matrix-vector multiplication and thresholding. However, the iteration takes thousands of steps to converge. Lin et al. [2014] observed that the support (non-zero element) of the coordinates after less than ten steps of CD is very accurate. Besides, the support of the sparse code is usually more important than the exact value of the sparse code. Therefore, we update the sparse code zi by using a few steps of CD operation because the original sparse coding is a non-convex problem and do not need to run CD to the final convergence. For the k-th epoch, we denote the updated sparse code as zk i . It will be used as an initial sparse code for the k + 1-th epoch.

Update zk i via one or a few steps of coordinate descent:

Specifically, for j from 1 to m, we update the jth coordinate zk-1 i,j of zk-1 i cyclicly as follows:

where s is the soft thresholding shrinkage function [Combettes and Wajs, 2005]. We call above updating cycle as one step of CD. The updated sparse code is then denoted by zk i .

Dictionary Update For updating the dictionary, we use block coordinate descent [Tseng, 2001] for updating each atom dk .

This can be solved in two steps, the solution of the unconstrained problem by differentiation followed by normalization and can be summarized by

As in [Mairal et al., 2009], we found that one update loop through all of the atoms was enough to ensure fast convergence of Algorithm 1. The only difference of this update compared to common dictionary learning is the shift operator δij . In Eq. (10), δδt = I. If the shift operator is a non-circular operators, the inverse δ-1 kj needs to be replaced by the adjoint δtkj and the rescaling function φ = (∑Mj=1 z2 kj δkjδtkj )-1 needs to be applied to the update term.

Besides, we used a random selection method (randomly select ˆl samples from matrices W lh to construct initial dictionaries Dl ) to initialize the dictionaries for different layers in DirNet. Then, we set all the sparse codes Z lh to be zero in the beginning and k = 10 epoch.

3.4 Adaptively Hierarchical Network

Considering different functionalities among hierarchical hidden layers, we propose the method of adaptively changing sparsity in different hidden layers. We use an initial perturbations as [Zhang et al., 2016] to let all features can be selected by competing with each other. Then we gradually shrank the network by using stronger l1-penalties and fewer features remaining in the progressive shrinking. Therefore, DirNet will go through the self-adjusting sequential stages before reaching the final optimal.

We note that sharing Dl across the inter-layer and recurrent-layer matrices allows more efficient parameterization for the weight matrices. Besides, this does not result in a significant loss of performance. By adjusting the dimensions of the projection matrices (pl ) in each of the layers of the network, the compression rate of the model will be determined. Therefore, after fixing the dictionary to Dl , solving Eq. 7 is equivalent to solve a LASSO problem [Tibshirani, 1996]. The objective function of solving Z lx as follow:

After we get dictionary Dl from Eq. 5, we can determine Z lx as the solution to the following LASSO problem with adaptive weights to regularize the model coefficients along with different features:

where λ2 is different across layers and we selected the best value from 10-3 to 103 in this work. Θ denotes regularization weight, we will receive different penalized matrices Z l+1 h instead of controlling the sparsity by λ2 as in Eq. (11). In addition, |Θ⊙Z l+1 h |1 = ∑i θi|zl+1 i | and Θ = |Zols|-γ , where Zols is the ordinal least-square solution.

Therefore, we can consider the following linear regression problem with the inter weight matrix W lx ∈ RN l+1×N l , where N l+1 is the sample size and N l is the dimension of the target response vector. We use n to represent N l+1 . Then, we use an adaptive weight vector Θ = [θ1, θ2, · · · , θn]T ∈ Rn to regularize over different covariates, as

where ||Θ-γ ⊙Z lx ||1 = ∑ni=1 θ-γ i · |Z lx | and we alternatively optimize Θ and Z lx in the learning process.

Suppose we initialize Θl , with |Θl | = Θl0 , l denotes l-th layer. Then, we alternatively update Θl and Z lx in Eq. (13) under this equality norm constraint until convergence. We will start the second stage of iterations with an updated norm constraint |Θl | = Θl1 after the initial stage, which imposes a stronger l1 penalty. Then we alternatively update Θl and Z lx until the second stage ends. We keep strengthening the global l1-norm regularization stage by stage during the updating procedure. We use τ to denote the index of each stage and Θl = Θlτ is the compose of iteration.

To solve Eq. (13), we first fix Θ and solve Z lx , which can be computationally converted to a LASSO problem:

Then, when we fix Z lx update Θ, the problem becomes the following constrained optimization problem:

We used the Lagrangian of Eq. 15, and drop the nonnegativity constraint. Let ci = |zi|1. Then the Lagrangian can be written as

By setting ∂J/∂θi = 0, we have

Plugging the above relation in the constraint ∑i θi = ϑ, then we have

Finally, we plug the above equation into Eq. 16 and get

Since ci = ∑j |zij | ≥ 0 and ϑ ≥ 0, the solution will satisfy the non-negative constraints automatically. After we trained the original RNN model and retrieved the weight matrices of both inter-layer and recurrent layer, the proposed algorithm is applied to learn the new matrices Zh, Zx and D of each layer, which are used to initialize parameters of neural network layers in the new network structure (Fig.1 (b)). After the initialization, we fine-tune the neural network as Han et al. [2015a] and the sparsity is preserved by only updating non-zero elements in the sparse matrix. Fine-tune step is also required for other compression works, e.g., [Prabhavalkar et al., 2016].

3.5 ExtendedModel Compression

We extend the Sec. 3.3 - Sec. 3.4 from standard RNNs to LSTM. In LSTM, the recurrent-weight matrix W lh and the inter-layer matrix W lx are both concatenation of four gates, which are input gate, output gate, forget gate and input modulation gate. We stack them vertically and denote as (i, o, f, g)T .

In this work, we do not consider the peephole weights because it already narrows and will not compress a lot of parameters. Thus, we rewrite the Eq. (1) and Eq. (2) as follows:

Besides, compressing a single-layer LSTMmodel is a special case for the proposed DirNet: (1) we can still learn the shared Dl using W lx and W lh of the single LSTM/RNN layer as in Fig.1 (b) to achieve a high compression rate on a singlelayer LSTM model; (2) compressing multiple LSTM/RNN layers, which can adaptively change the sparsity of the sparse codes relying on cross-layer information, will achieve higher compression rate than a single-layer LSTM/RNN model.

4 Experimental Results and Discussion

The proposed approach is a general algorithm for compressing recurrent neural networks including vanilla RNN, LSTM and GRU, etc, and thus can be directly used in many problems, e.g., language modeling (LM), speech recognition, machine translation and image captioning. In this paper, we select two popular domains: LM and speech recognition. We compare DirNet with (1) LSTM-SVD and LSTM-ODL. LSTMSVD is the method proposed by Prabhavakar et al. [2016] which compresses RNNs by low-rank SVD. LSTM-ODL is the method which compresses RNNs by online dictionary learning [Mairal et al., 2009]. To train DirNet, it takes 10 hours on PTB with 1 K80 GPU and around 120 hours on LibriSpeech using 16 Nvidia K80 GPUs.

4.1 Language Modeling

We conduct word-level prediction on the Penn Tree Bank (PTB) dataset [Marcus et al., 1993], which consists of 929k training words, 73k validation words and 82k test words. We first train a two-layer unrolled LSTM model with 650 units per layer, which is using the same network setting of LSTMmedium in [Zaremba et al., 2014]. For comparison, the same model is compressed using LSTM-SVD, LSTM-ODL as well as DirNet. We report the result of testing data in Table 1. We observe that DirNet achieves superior performances regarding compression rates and speedup rates while maintaining the accuracy. The reason is that dynamically adjusting the projection matrices D can achieve better compression rate and adapt different sparsities across layers can receive negligible accuracy loss.

4.2 Speech Recognition

Dataset: The LibriSpeech corpus is a large (1000 hour) corpus of English read speech derived from audiobooks in the LibriVox project, sampled at 16kHz. The accents are various and not marked, but the majority are US English. It is publicly available at http://www.openslr.org/12/ [Panayotov et al., 2015]. LibriSpeech comes with its own train, validation and test sets and we use all the available data for training and validating our models. Moreover, we use the 100-hour "test clean" set as the testing set. Mel-frequency cepstrum (MFCC) [Davis and Mermelstein, 1990] features are computed with 26 coefficients, a 25 ms sliding window and 10 ms stride. We use nine time slices before and nine after, for a total of 19 time points per window. As a result, with 26 cepstral coefficients, there are 494 data points per 25 ms observation.

Baseline Model: Following [Prabhavalkar et al., 2016], our baseline model for speech recognition is a 5-layer RNN model with the Connectionist Temporal Classification (CTC) loss function [Graves et al., 2006], which predicts 41 contextindependent (CI) phonemes [Sak et al., 2015]. Each hidden RNN layer is composed of 500 LSTM units. We train all models for 100 epochs using Adam optimizer [Kingma and Ba, 2014] with an initial learning rate of 0.001. It takes around 35 and 55 epochs to converge of DirNet and the baseline model, respectively. The size of the batch is 32. The model is first trained to convergence for optimizing the CTC criterion, followed which are sequences discriminatively trained to optimize the state-level minimum Bayes risk (sMBR) criterion [Kingsbury, 2009]. We implement DirNet by Tensorflow [Abadi et al., 2016] and use Samsung Galaxy S8 smartphone as the mobile platform to evaluate the performance.

Results: To give a comprehensive evaluation of the proposed approach, we list the word error rate along with parameter number and the execution time comparison between different approaches in Table 2. There are two sets of experiments: 1) compare the maximum compression rate obtained by different approaches without the accuracy drop 2) measure the word error rate among different approaches with the same compression rate.

As indicated in the first row of Table 2, the basic LSTM model can achieve 12.7% (WER) before any compression. It includes 10.3M parameters in total and takes 1.77s to recognize 1s audio. Our proposed approach DirNet can compress the model by 4.3 times without losing any accuracy. The speed up achieved by DirNet is 4.2 times faster compared to 1.4 and 2.6 times obtained by LSTM-SVD and LSTMODL. These results indicate the superiority of the proposed DirNet over current compressing algorithms. Moreover, such significant improvement shows that dynamically adjust sparsity across layers might help the compression models receive higher compression rates. From the results listed in the second row of Table 2, we can find that when compressing the model size by 7.9 times, LSTM-ODL and LSTM-SVD lose lots of accuracy, especially SVD based compression algorithm, which is 3.4% (16.1%-12.7%) compared to 0.2% achieved by DirNet.

4.3 Adaptively Shrinking Parameter Selection

In this section, we study how the performance of our approach is affected by the following two parameters: Θ0 that controls the initial "sparsity" of the system and the shrinking factor γ that controls the compression rate of the system. We use F-score on LibriSpeech dataset to measure the performance.

First, we examine the performance of choosing different Θ0 values. The range is from 10-3 to 1010 , and the result is shown on the left side of the Fig. 3. We notice that when Θ0 is below 105 , the performance quickly drops and the lower initial sparsity even fails to start the whole system with sufficient energy. As a result the iterations could quickly stop at a local optimal. Therefore, we choose the best performance Θ0 = 107 in all experimental settings.

Second, we study the influence of varying shrinking factor γ. The explored value range is from 10-6 to 100 . We observe that the performance sharply increases first and becomes stable afterward. Besides, the system evolves slowly such that the shrinking stage is sufficient when the shrinking scheme γ → 1. In practice, we choose γ = 0.4 to strike a balance between efficiency and the quality of shrinking procedure.

4.4 Adaptive Hierarchy of the Network

We also compare the performance of DirNet (O) adaptive cross-layers' compression capability with LSTM-SVD (G). All the results are listed in Table 3. We can find that DirNet achieves much lower WER compared to LSTM-SVD even with the same number of neurons. Also, these results further demonstrate the superiority of DirNet adaptive adjusting sparse features in deep model compression.

5 Conclusions

In this paper, we introduce DirNet that dynamically adjusts the compression rate of each layer in the network, and adaptively change the hierarchical structures among different layers on their weight matrices. Experimental results show that compared to other RNN compression methods, DirNet significantly improves the performance before retraining. In our ongoing work, we will integrate scalar level compression with our DirNet to further compress the deep model.