With the rapid development in deep learning, deep neural networks have been widely adopted in many real-life natural language applications. Under deep neural networks, a pre-defined vocabulary is required to vectorize text inputs. The canonical approach to select pre-defined vocabulary is based on the word frequency, where a threshold is selected to cut off the long tail distribution. However, we observed that such a simple approach could easily lead to under-sized vocabulary or oversized vocabulary issues. Therefore, we are interested in understanding how the end-task classification accuracy is related to the vocabulary size and what is the minimum required vocabulary size to achieve a specific performance. In this paper, we provide a more sophisticated variational vocabulary dropout (VVD) based on variational dropout to perform vocabulary selection, which can intelligently select the subset of the vocabulary to achieve the required performance. To evaluate different algorithms on the newly proposed vocabulary selection problem, we propose two new metrics: Area Under Accuracy-Vocab Curve and Vocab Size under X% Accuracy Drop. Through extensive experiments on various NLP classification tasks, our variational framework is shown to significantly outperform the frequency-based and other selection baselines on these metrics. Over the past decade, deep neural networks have become arguably the most popular model choice for a vast number of natural language processing (NLP) tasks and have constantly been delivering state-of-the-art results. Because neural network models assume continuous data, to apply a neural network on any text data, the first step is to CutoffFreq. vectorize the discrete text input with a word embedding matrix through look-up operation, which in turn assumes a pre-defined vocabulary set. For many NLP tasks, the vocabulary size can easily go up to the order of tens of thousands, which potentially makes the word embedding the largest portion of the trainable parameters. For example, a document classification task like AG-news (Zhang et al., 2015) can include up to 60K unique words, with the embedding matrix accounting for 97.6% of the trainable parameters (Table 1), which leads to under-representation of the neural networks' own parameters. Intuitively, using the full or very large vocabulary are neither economical, as it limits model applicability on computationor memory-constrained scenarios (Yogatama et al., 2015; Faruqui et al., 2015), nor necessary, as many words may contribute little to the end task and could have been safely removed from the vocabulary. Therefore, how to select the best vocabulary is a problem of both theoretical and practical interests. Somewhat surprisingly, this vocabulary selection problem is largely under-addressed in the literature: The de facto standard practice is to do frequency-based cutoff (Luong et al., 2015; Kim, 2014), and only retain the words more frequent than a certain threshold (Table 1). Although this simple heuristic has demonstrated strong empirical performance, its task-agnostic nature implies that likely it is not the optimal strategy for many tasks (or any task). Task-aware vocabulary selection strategies and a systematic comparison of different strategies are still lacking. In this work, we present the first systematic study of the vocabulary selection problem. Our study will be based on text classification tasks, a broad family of NLP tasks including document classification (DC), natural language inference (NLI), natural language understanding in dialog systems (NLU), etc. Specifically, we aim to answer the following questions: 1. How important a role does the vocabulary selection algorithm play in text classification? 2. How to dramatically reduce the vocabulary size while retaining the accuracy? The rest of the paper is organized as follows: We first formally define the vocabulary selection problem (subsection 2.1) and present a quantitative study on classification accuracy with different vocabulary selections to showcase its importance in the end task (subsection 2.2). We also propose two new metrics for evaluating the performance of vocabulary selection in text classification tasks (subsection 2.3). We then propose a novel, task-aware vocabulary selection algorithm called Varitional Vocabulary Dropout (VVD) (sec-tion 3) which draws on the idea of variational dropout (Kingma et al., 2015): If we learn a dropout probability p w for each given word w in the vocabulary V during the model training on a given task, the learned dropout probabilities p w will imply the importance of word w to the end task and can, therefore, be leveraged for vocabulary selection. We propose to infer the latent dropout probabilities under a Bayesian inference framework. During test time, we select the sub vocabulary  V by only retaining words with dropout probability lower than a certain threshold. For any words deselected using VVD, we will simply regard them as a special token with null vector representation [0 , 0 ,    , 0] . Please note that our proposed algorithm needs to re-train a word embedding matrix, thus it is tangential to the research of pre-trained word embedding like Word2Vec (Mikolov et al., 2013) or Glove (Pen-nington et al., 2014) though we can use them to initialize our embedding. We conduct comprehensive experiments to evaluate the performance of VVD (section 4) on different end classification tasks. Specifically, we compare against an array of strong baseline selection algorithms, including the frequency-based algorithm (Luong et al., 2015), TF-IDF algorithm (Ramos et al., 2003), and structure lasso algorithm (Friedman et al., 2010), and demonstrate that it can consistently outperform these competing algorithms by a remarkable margin. To show that the conclusions are widely held, our evaluation is based on a wide range of text classification tasks and datasets with different neural networks including Convolutional Neural Network (CNN) (Kim, 2014), Bi-directional Long-Short Term Memory (BiLSTM) (Bahdanau et al., 2014) and Enhanced LSTM (ESIM) (Chen et al., 2017). In summary, our contributions are three-fold: 1. We formally define the vocabulary selection problem, demonstrate its importance, and propose new evaluation metrics for vocabulary selection in text classification tasks. 2. We propose a novel vocabulary selection algorithm based on variational dropout by re-formulating text classification under the Bayesian inference framework. The code will be released in Github 1 . 3. We conduct comprehensive experiments to demonstrate the superiority of the proposed vocabulary selection algorithm over a number of strong baselines. We now formally define the problem setting and introduce the notations for our problem. Conventionally, we assume the neural classification model vectorizes the discrete language input into a vector representation via an embedding matrix W  RV  D , where V denotes the size of the vocabulary, and D denotes the vector dimension. The embedding is associated with a pre-defined word-to-index dictionary V = { w i : i | 1  i  V } where w i denotes a literal word corresponding to i th row in the embedding matrix. The embedding matrix W covers the subset of a vocabulary of interests for a particular NLP task, note that the value of V 1 https://github.com/wenhuchen/ Variational-Vocabulary-Selection.git  5% Vocab@5% 42.5 85.1 80.1 33.2 Document Classification Natural Language Understanding Evaluation Metrics Figure 1: Monte-Carlo simulation on vocabulary selection. is known to be very large due to the rich variations in human languages. Here we showcase the embedding matrix size of a popular text classification model 2 on AG-news dataset (Zhang et al., 2015) in Table 1. From which we can easily observe that the embedding matrix is commonly occupying most of the parameter capacity, which could be the bottleneck in many real-world applications with limited computation resources. In order to alleviate such redundancy problem and make embedding matrix as efficient as possible, we are particularly interested in discovering the minimum row-sized embedding  W to achieve nearly promising performance as using the full row-sized embedding W . More formally, we define the our problem as follows: argmin  W,   # Row (  W ) s.t. Acc ( f   ( x ;  W ) , y )  Acc ( f  ( x ; W ) , y )  (cid:15) (1) where #Row is a the number of rows in the matrix  W , f  is the learned neural model with parameter  to predict the class given the inputs x , Acc is the function which measure accuracy between model prediction and y (reference output), and (cid:15) is the tolerable performance drop after vocabulary selection. It is worth noting that here  includes all the parameter set of the neural network except embedding matrix W . For each vocabulary selection algorithm A , we propose to draw its characteristic curve Acc ( f   ( x ;  W ) , y ) = g A (# Row (  W )) to understand the relationship between the vocabulary capacity and classification accuracy, which we call as (characteristic) accuracy-vocab curve throughout our paper. In order to investigate the importance of the role played by the vocabulary selection algorithm, we design a Monte-Carlo simulation strategy to approximate accuracy's lower bound and upper bound of a given vocabulary size reached by a possible selection algorithm A . More specifically, for a given vocabulary size of  V , there exist (cid:0) V  V (cid:1) algorithms which can select distinct vocabulary subset  V from the full vocabulary V . Directly enumerating these possibilities are impossible, we instead propose to use a Monte-Carlo vocabulary selection strategy which can randomly pick vocabulary subset  V to simulate the possible selection algorithms by running it N times. After simulation, we obtain various point estimations ( Acc 1 ,    , Acc N |  V ) at each given  V and depict the point estimates in Figure 1 to approximately visualize the upper and lower bound of the accuracy-vocab curve. From Figure 1, we can easily observe that the accuracy range under a limited-vocabulary is extremely large, when the budget  V increases, the gap gradually shrinks. For example, for document classification with a budget of 1000, a selection algorithm A can yield a potential accuracy ranging from 42 . 5 to 85 . 1 , while for natural language understanding task with a budget of 27, a selection algorithm A can yield a potential accuracy ranging from 33 . 2 to 80 . 1 . Such a Monte-Carlo simulation study has demonstrated the significance of vocabulary selection strategy in NLP tasks and also implicate the enormous potential of an optimal vocabulary selection algorithm. In order to evaluate how well a given selection algorithm A performs, we propose evaluation metrics as depicted in Figure 1 by quantitatively studying its characteristic accuracy-vocab curve. These metrics namely Area Under Curve (AUC) and Vocab@-X% separately measure the vocabulary selection performance globally and locally. Specifically, AUC computes enclosed area by the curve, which gives an overview of how well the vocabulary selection algorithm performs. In comparison, Vocab@-X% computes the minimum vocabulary size required if X% performance drop is allowed, which straightforwardly represents how large vocabulary is required to achieve a given accuracy. For the local evaluation metric, we mainly consider Vocab@-3% and Vocab@-5%. However, we observe that directly computing AUC lays too much emphasis on the large-vocabulary region, thus unable to represent an algorithm's selection capability under the low-vocabulary conditions. Therefore, we propose to take the logarithm of the vocabulary size and then compute the normalized enclosed area by: AUC = (cid:82)  V Acc (log( V )) d log( V ) (cid:82)  V Acc ( V ) d log( V ) (2) It is worth noting that Vocab@-X% takes value from range [0 , V ] with smaller values indicate better performance. Since AUC is normalized by Acc(V), it takes value from range [0 , 1] regardless of the classification error. Inspired by DNN dropout (Srivastava et al., 2014; Wang and Manning, 2013), we propose to tackle the vocabulary selection problem from word-level dropout perspective, where we assume each word w i (an integer index) is associated with its characteristic dropout rate p i , which represents the probability of being replaced with an empty placeholder, specifically, higher dropout probability indicates less loss suffered from removing it from the vocabulary. Hence, the original optimization problem in Equation 1 can be thought of as inferring the latent dropout probability vector p = [ p 1 ,    , p V ] . The overview of our philosophy is depicted in Figure 2, where we associate with each row of the embedding matrix a dropout probability and then re-train the complete system, which grasps how much contribution each word from the vocabulary makes to the end NLP task and remove those less contributory words from the vocabulary without hurting the performance. Here we first assume that the neural network vectorizes the discrete inputs with an embedding matrix W to project given words x into vector space RD , and then propose to add random dropout noise into the embedding input to simulate the dropout process as follows: where OneHot is a function to transform a word x into its one-hot form OneHot ( x )  RV , and b  RV is the Bernouli dropout noise with b i  Bern (1  p i ) . The embedding output vector E ( x | b ) is computed with a given embedding matrix W under a sampled Bernouli vector b . In order to infer the latent Bernouli distribution with parameters p under the Bayesian framework where training pairs ( x = x 1    x n , y ) are given as the evidence, we first define an objective function as L ( f  ( x ) , y ) and then derive its lower bound as follows (with  p = 1  p ): where P ( b ) is the prior distribution, and Bern ( p ) denotes the Bernouli approximate posterior with parameter p . Here we use E ( x ) as the simplied form of { E ( x 1 ) ,    , E ( x n ) } , we separate the text classification model's parameters  with the embedding parameters W and assume the classification model f  directly takes embedding E as input. However, the Bernouli distribution is hard to repa-rameterize, where we need to enumerate 2 V different values to compute the expectation over the stochastic dropout vector b . Therefore, we follow Wang and Manning (2013) to use a continuous Gaussian approximation, where the Bernouli noise b is replaced by a Gaussian noise z : where z  RV follows Gaussian distribution z i  N (1 ,  i = p i 1  p i ) . It is worth noting that and p are one-to-one corresponded, and  is a monotonously increasing function of p . For more details, please refer to Wang and Manning (2013). Based on such approximation, we can use  as dropout criteria, e.g. throw away words with  above a certain given threshold  T . We further follow Louizos et al. (2017); Kingma et al. (2015); Molchanov et al. (2017) to re-interpret the input noise as the intrinsic stochasticity in the embedding weights B itself as follows: E ( x | z ) = OneHot ( x )  B (5) log L ( f  ( x ) , y )) = log (cid:90) BL ( f  ( E ( x | z )) , y )) P ( B ) dB  EB N ( , ) [log L ( f  ( E ( x | z )) , y )]  KL ( N ( ,  ) ||P ( B )) = L ( B,  ) P (log | B ij | ) = const  P ( | B ij | )  1 | B | (6) Since there exists no closed-form expression for such KL-divergence, we follow Louizos et al. (2017) to approximate it by the following formula with minimum variance: DKL =  k 1  ( k 2 + k 3 log  ) + 1 2 log(1 + 1  ) + k 1 k 1 = 0 . 63576 k 2 = 1 . 87320 k 3 = 1 . 48695 (7) By adopting the improper log-uniform prior, more weights are compressed towards zero, and the KL-divergence is negatively correlated with dropout ratio  . Intuitively, the dropout ratio  i is an redundancy indicator for i th word in the vocabulary, with larger  i meaning less performance loss caused by dropping i th word. During training, we use re-parameterization trick (Kingma and Welling, 2013) to sample embedding weights from the normal distribution to reduce the Monte-Carlo variance in Bayesian training. After optimization, we can obtain the dropout ratio  i associated with each word w i . We propose to select vocabulary subset based on the dropout ratio by using a threshold  T . Therefore, the remaining vocabulary subset is described as follows: where we use  V to denote the subset vocabulary of interest, by adjusting  T we are able to control the selected vocabulary size. We compare the proposed vocabulary selection algorithm against several strong baselines on a wide range of text classification tasks and datasets. The main datasets we are using are listed in Table 2, which provides an overview of its description and capacities. Specifically, we follow (Zhang et al., 2015; Goo et al., 2018; Williams et al., 2018) to pre-process the document classification datasets, natural language understanding dataset and natural language inference dataset. We exactly replicate their experiment settings to make our method comparable with theirs. Our models is implemented with TensorFlow (Abadi et al., 2015). In order to evaluate the generalization ability of VVD selection algorithm in deep learning architectures, we study its performance under different established architectures (depicted in Figure 3). In natural language understanding, we use the most recent attention-based model for intention tracking (Goo et al., 2018), this model first uses BiLSTM recurrent network to leverage left-to-right and right-to-left context information to form the hidden representation, then computes self-attention weights to aggregate the hidden representation and predicts user intention. In document classification, we mainly follow the CNN architecture (Kim, 2014) to extract n-gram features and then aggregate these features to predict document category. In natural language inference, we follow the popular ESIM architecture (Williams et al., 2018; Chen et al., 2017) us-Datasets ing the Github implementation 3 . In this structure, three main components input encoding, local inference modeling, and inference composition are used to perform sequential inference and composition to simulate the interaction between premises and hypothesis. Note that, we do not apply the syntax-tree based LSTM proposed in (Chen et al., 2017) because we lost the parse tree (Klein and Manning, 2003) after the vocabulary compression, instead, we follow the simpler sequential LSTM framework without any syntax parse as input. Besides, the accuracy curve is obtained using the publicly available test split rather than the official online evaluation because we need to evaluate lots of times at different vocabulary capacity. Frequency-based (task-agnostic) This approach is already extensively talked about in section 1, its basic idea is to rank the word based on its frequency and then set a threshold to cut off the long tail distribution. TF-IDF (task-agnostic) This algorithm views the vocabulary selection as a retrieval problem (Ramos et al., 2003), where term frequency is viewed as the word frequency and document 3 https://github.com/coetaur0/ESIM frequency is viewed as the number of sentences where such word appears. Here we follow the canonical TF-IDF approach to compute the retrieval score as follows: tfidf ( w, D ) = tf ( w )   (log N n w ) 1   (9) where tf ( w ) denotes the word frequency,  is the balancing factor, N denotes the number of sentences and n w denotes the number of sentences in which w appears. We rank the whole vocabulary based on the tfidf and cut off at given threshold. Group Lasso (task-aware) This baseline aims to find intrinsic sparse structures (Liu et al., 2015; Park et al., 2016; Wen et al., 2016) by grouping each row of word embedding. The regularization objective is described as follows, which aims at finding the row-wise sparse structure: L reg = (cid:88) i ( (cid:88) j W 2 ij ) 12 (10) After optimized with the above regularization, we use a threshold-based selection strategy on the row-norm of embedding matrix, the selected vocabulary is described as  V = { w i  V ||| W i || 2 >  T } , where  T is the threshold. natural language inference separately in Table 3. From these tables, first of all, we can observe that VVD is able to maintain or even improve the reported accuracy on DC and NLU tasks, the accuracy of VVD is reported under dropping out the words with dropout rate larger than 0 . 95 . The exception is in NLI (Williams et al., 2018), where the common approach uses GloVe (Pennington et al., 2014) for initialization, and we use random initialization, which makes our model fall slightly behind. It is worth noting that Frequency-based/TF-IDF methods are based on the model trained with cross entropy, while both Group-Lasso and VVD modify the objective function by adding additional regularization. It can be seen that VVD is performing very similar to the baseline models on DC and NLU tasks, while consistently outperforming the baseline methods (with random initialized embedding) on more challenging NLI and Yelp-Review tasks, that said, VVD can also be viewed as a generally effective regularization technique to sparsify features and alleviate the over-fitting problem in NLP tasks. In terms of the vocabulary selection capability, our proposed VVD is demonstrated to outperform the competing algorithms in terms of both AUC and Vocab@-X% metrics consistently over different datasets as shown in Table 3. In order to better understand the margin between VVD and frequency-based method, we plot their accuracy-vocab curves in Figure 4, from which we can observe that the accuracy curves start from nearly the same accuracy with the full vocabulary, by gradually decreasing the budget  V , VVD decreases at a much lower rate than the competing algorithms, which clearly reflects its superiority under limited-budget scenario. From the empirical result, we can conclude that: 1) the retrieval-based selection algorithm can yield Figure 4: The accuracy-vocab curve of VVD, TF-IDF and frequency-based baseline, the datasets used are AG-news, DBPedia and Yelp-review respectively. when, showing, use, watch, photograph, eat, soundtrack, hear, painting, tell, trailer easy, d, zero, people, series, am, three, serves, one, area, five, textbook, new, get, with, two, she + Figure marginal improvement over the AUC metric, but the vocab@-X% metric deteriorates. 2) group-lasso and VVD algorithm directly considers the connection between each word and end classification accuracy; such task-awareness can greatly in improving both evaluation metrics. Here we show that NLU datasets are relatively simpler, which only involves detecting key words from hu-Figure 7: The vocabulary cloud of Snips NLU dataset. man voice inputs to make decent decisions, a keyword vocabulary within 100 is already enough for promising accuracy. For DC datasets, which involve better inner-sentence and inter-sentence understanding, hundred-level vocabulary is required for most cases. NLI datasets involve more complicated reasoning and interaction, which requires a thousand-level vocabulary. Case Study To provide an overview of what words are selected, we depict the selection spectrum over different NLP tasks in Figure 5, from which we observe that most of the selected vocabulary are still from the high-frequency area to ensure coverage, which also explains why the frequency-based algorithm is already very strong. Furthermore, we use the Snips dataset (Coucke et al., 2018) to showcase the difference between the vocabularies selected by VVD and by frequency-based baseline. The main goal of this dataset is to understand the speaker's intention such as BookRestaurant, PlayMu-sic, and SearchLocalEvent. We show the se-lected/unselected words by our algorithm in Figure 6 under a vocabulary budget of 100, it is observed that many non-informative but frequent functional words like get, with, and five are unselected while more task-related but less frequent words like neighborhood, search, the-atre are selected. More vividly, we demonstrate the word cloud of the selected vocabulary of Snips (Coucke et al., 2018) in Figure 7. Training Speed Due to the stochasticity of VVD, the training of text classification takes longer than canonical cross entropy objective. More importantly, we observe that with the increase the full vocabulary size, the convergence time of VVD also increases sub-linearly but the convergence time of Cross Entropy remains quite consistent. We conjecture that this is due to the fact that the VVD algorithm has a heavier burden to infer the drop out the probability of the long tail words. Therefore, we propose to use a two-step vocabulary reduction to dramatically decrease VVD's training time, in the first step, we cut off the rare words without having any harm on the final accuracy, then we continue training with VVD on the shrunk vocabulary. By applying such a hybrid methodology, we are able to decrease the training time dramatically. Evaluation Speed As we know, at each vocabulary point, the network needs to perform once evaluation on the whole test set. Therefore, it is not practical to draw each vocabulary size from 1 to V and perform V times of evaluation. Given the limited computational resources, we need to sample some vocabulary size and estimate the area under curve relying on only these points. Uniformly sampling the data points are proved wasteful, since when the accuracy curve will converge to a point very early, most of the sampled point is actually getting equivalent accuracy. Therefore, we propose to increase the interval exponentially to cover more samples at extremely low vocabulary size. For example, given the total vocabulary of 60000, the interval will be split into 1, 2, 4, 8, 24, 56, ..., 60K. Using such sampling method achieve a reasonably accurate estimation of ROC with only O ( log ( | V | )) sample points, which is affordable under many cases. Neural Network Compression In order to better apply the deep neural networks under limited-resource scenarios, much recent research has been performed to compress the model size and decrease the computation resources. In summary, there are mainly three directions, weight matrices approximation (Le et al., 2015; Tjan-dra et al., 2017), reducing the precision of the weights (Hubara et al., 2017; Han et al., 2015) and sparsification of the weight matrix (Wen et al., 2016). Another group of sparsification relies on the Bayesian inference framework (Molchanov et al., 2017; Neklyudov et al., 2017; Louizos et al., 2017). The main advantage of the Bayesian sparsification techniques is that they have a small number of hyperparameters compared to pruning-based methods. As stated in (Chirkova et al., 2018), Bayesian compression also leads to a higher sparsity level (Molchanov et al., 2017; Neklyudov et al., 2017; Louizos et al., 2017). Our proposed VVD is inspired by these predecessors to specifically tackle the vocabulary redundancy problem in NLP tasks. Vocabulary Reduction An orthogonal line of research for dealing similar vocabulary redundancy problem is the character-based approaches to reduce vocabulary sise (Kim et al., 2016; Zhang et al., 2015; Costa-Juss`a and Fonollosa, 2016; Lee et al., 2017), which decomposes the words into its characters forms for better handling open world inputs. However, these approaches are not applicable to character-free languages like Chinese and Japanese. Moreover, splitting words into characters incurs potential lose of word-level surface form, and thus needs more parameters at the neural network level to recover it to maintain the end task performance (Zhang et al., 2015), which contradicts with our initial motivation of compressing the neural network models for computation-or memory-constrained scenarios. In this paper, we propose a vocabulary selection algorithm which can find sparsity in the vocabulary and dynamically decrease its size to contain only the useful words. Through our experiments, we have empirically demonstrated that the commonly adopted frequency-based vocabulary selection is already a very strong mechanism, further applying our proposed VVD can further improve the compression ratio. However, due to the time and memory complexity issues, our algorithm and evaluation are more suitable for classification-based application. In the future, we plan to investigate broader applications like summarizaion, translation, question answering, etc. The authors would like to thank the anonymous reviewers for their thoughtful comments. This research was sponsored in part by NSF 1528175. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
abstain abstain abstain result result result objective result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain objective abstain objective objective objective objective objective other objective abstain method abstain method abstain result objective objective objective objective objective method method abstain other abstain method abstain abstain method abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain method abstain method method abstain other method method abstain method other method abstain method abstain method method abstain other abstain abstain abstain result abstain other method abstain abstain other abstain abstain abstain abstain abstain abstain abstain result result abstain abstain abstain result abstain abstain abstain result abstain abstain result abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain other other other other other objective other other abstain objective objective abstain objective other other other