BlackOut: Speeding up Recurrent Neural Network Language Models With Very Large Vocabularies

Introduction

Statistical language models are a crucial component of speech recognition, machine translation and information retrieval systems. In order to handle the data sparsity problem associated with traditional $n$-gram language models (LMs), neural network language models (NNLMs) (Bengio et al., 2001) represent the history context in a continuous vector space that can be learned towards error rate reduction by sharing data among similar contexts. Instead of using fixed number of words to represent context, recurrent neural network language models (RNNLMs) (Mikolov et al., 2010) use a recurrent hidden layer to represent longer and variable length histories. RNNLMs significantly outperform traditional $n$-gram LMs, and are therefore becoming an increasingly popular choice for practitioners (Mikolov et al., 2010; Sundermeyer et al., 2013; Devlin et al., 2014).

For language modeling applications, the input $x_{t}$ is a sparse vector of a 1-of-$V$ (or one-hot) encoding with the element corresponding to the input word $w_{t-1}$ being 1 and the rest of components of $x_{t}$ set to 0; the state of the network $s_{t}$ is a dense vector, summarizing the history context $\{w_{t-1},\cdots,w_{0}\}$ preceding the output word $w_{t}$; and the output $y_{t}$ is a dense vector, with the $i$-th element denoting the probability of the next word being $w_{i}$, that is, $p(w_{i}|w_{t-1},\cdots,w_{0})$, or more concisely, $p(w_{i}|s_{t})$. The input to output transformation occurs via:

where $\sigma(v)=1/(1+\exp(-v))$ is the sigmoid activation function, and $f(\cdot)$ is the softmax function $f(u_{i}):=\exp(u_{i})/\sum_{j=1}^{V}\exp(u_{j})$.

One can immediately see that if $x_{t}$ uses a 1-of-$V$ encoding, then the computations in equation (1) are relatively inexpensive (typically $h$ is of the order of a few thousand, and the computations are $\mathcal{O}(h^{2})$), while the computations in equation (2) are expensive (typically $V$ is of the order of a million, and the computations are $\mathcal{O}(Vh)$). Similarly, back propagating the gradients from the output layer to the hidden layer is expensive. Consequently, the training times for some of the largest models reported in literature are of the order of weeks (Mikolov et al., 2011; Williams et al., 2015).

In this paper, we ask the following question: Can we design an approximate training scheme for RNNLM which will improve on the state of the art models, while using significantly less computational resources? Towards this end, we propose BlackOut an approximation algorithm to efficiently train massive RNNLMs with million word vocabularies. BlackOut is motivated by using a discriminative loss, and we describe a weighted sampling strategy which significantly reduces computation while improving stability, sample efficiency, and rate of convergence. We also establish close connections between BlackOut, importance sampling, and noise contrastive estimation (NCE) (Gutmann & Hyvärinen, 2012; Mnih & Teh, 2012), and demonstrate that BlackOut mitigates some of the limitations of both previous methods. Our experiments, on the recently released one billion word language modeling benchmark (Chelba et al., 2014), demonstrate scalability and accuracy of BlackOut; we outperform the state-of-the art, achieving the lowest perplexity scores on this dataset. Moreover, unlike other established methods which typically require GPUs or CPU clusters, we show that a carefully implemented version of BlackOut requires only 1-10 days on a single CPU machine to train a RNNLM with a million word vocabulary and billions of parameters on one billion words.

One way to understand BlackOut is to view it as an extension of the DropOut strategy (Srivastava et al., 2014) to the output layer, wherein we use a discriminative training loss and a weighted sampling scheme. The connection to DropOut is mainly from the way they operate in model training and model evaluation. Similar to DropOut, in BlackOut training a subset of output layer is sampled and trained at each training batch and when evaluating, the full network participates. Also, like DropOut, a regularization technique, our experiments show that the models trained by BlackOut are less prone to overfitting. A primary difference between them is that DropOut is routinely used at input and/or hidden layers of deep neural networks, while BlackOut only operates at output layer. We chose the name BlackOut in light of the similarities between our method and DropOut, and the complementary they offer to train deep neural networks.

BlackOut: A sampling-based approximation

We will primarily focus on estimation of the matrix $W_{out}$. To simplify notation, in the sequel we will use $\theta$ to denote $W_{out}$ and $\theta_{j}$ to denote the $j$-th row of $W_{out}$. Moreover, let $\left\langle\cdot,\cdot\right\rangle$ denote the dot product between two vectors. Given these notations, one can rewrite equation (2) as

RNNLMs with a softmax output layer are typically trained using cross-entropy as the loss function, which is equivalent to maximum likelihood (ML) estimation, that is, to find the model parameter $\theta$ which maximizes the log-likelihood of target word $w_{i}$, given a history context $s$:

The gradient of log-likelihood is expensive to evaluate because (1) the cost of computing $p_{\theta}(w_{j}|s)$ is $\mathcal{O}(Vh)$ and (2) the summation above takes time linear in the vocabulary size $\mathcal{O}(V)$.

To alleviate the computational bottleneck of computing the gradient (5), we propose to use the following discriminative objective function for training RNNLM:

where $S_{K}$ is a set of indices of $K$ words drawn from the vocabulary, and $i\notin S_{K}$. Typically, $K$ is a tiny fraction of $V$, and in our experiments we use $K\approx V/200$. To generate $S_{K}$ we will sample $K$ words from the vocabulary using an easy to sample distribution $Q(w)$, and set $q_{j}:=\frac{1}{Q(w_{j})}$ in order to compute

Equation 6 is the cost function of a standard logistic regression classifier that discriminates one positive sample $w_{i}$ from $K$ negative samples $w_{j},\forall j\in S_{K}$. The first term in (6) corresponds to the traditional maximum likelihood training, and the second term explicitly pushes down the probability of negative samples in addition to the implicit shrinkage enforced by the denominator of (7). In our experiments, we found the discriminative training (6) outperforms the maximum likelihood training (the first term of Eq. 6) in all the cases, with varying degree of accuracy improvement depending on $K$.

The weighted softmax function (7) can be considered as a stochastic version of the standard softmax (3) on a different base measure. While the standard softmax (3) uses a base measure which gives equal weights to all words, and has support over the entire vocabulary, the base measure used in (7) has support only on $K+1$ words: the target word $w_{i}$ and $K$ samples from $Q(w)$. The noise portion of (7) has the motivation from the sampling scheme, and the $q_{i}$ term for target word $w_{i}$ is introduced mainly to balance the contributions from target word and noisy sample words.It’s shown empirically in our experiments that setting $q_{i}=1$ in (7) hurts the accuracy significantly. Other justifications are discussed in Sec. 2.1 and Sec. 2.2, where we establish close connections between BlackOut, importance sampling, and noise contrastive estimation.

Due to the weighted sampling property of BlackOut, some words might be sampled multiple times according to the proposal distribution $Q(w)$, and thus their indices may appear multiple times in $S_{K}$. As $w_{i}$ is the target word, which is assumed to be included in computing (7), we therefore set $i\notin S_{K}$ explicitly.

Then taking derivatives with respect to $u_{j},\forall j\in\left\{i\right\}\cup S_{K}$, yields

Next we turn our attention to the proposal distribution $Q(w)$. In the past, a uniform distribution or the unigram distribution have been advocated as promising candidates for sampling distributions (Bengio & Senécal, 2003; Jean et al., 2015; Bengio & Senécal, 2008; Mnih & Teh, 2012). As we will see in the experiments, neither one is suitable for a wide range of datasets, and we find that the power-raised unigram distribution of Mikolov et al. (2013) is very important in this context:

Note that $Q_{\alpha}(w)$ is a generalization of uniform distribution (when $\alpha=0$) and unigram distribution (when $\alpha=1$). The rationale behind our choice is that by tuning $\alpha$, one can interpolate smoothly between sampling popular words, as advocated by the unigram distribution, and sampling all words equally. The best $\alpha$ is typically dataset and/or problem dependent; in our experiments, we use a holdout set to find the best value of $\alpha$. It’s worth noting that this sampling strategy has been used by Mikolov et al. (2013) in a similar context of word embedding, while here we explore its effect in the language modeling applications.

After BlackOut training, we evaluate the predictive performance of RNNLM by perplexity. To calculate perplexity, we explicitly normalize the output distribution by using the exact softmax function (3). This is similar to DropOut (Srivastava et al., 2014), wherein a subset of network is sampled and trained at each training batch and when evaluating, the full network participates.

BlackOut has a close connection to importance sampling (IS). To see this, differentiating the logarithm of Eq. 7 with respect to model parameter $\theta$, we have

In contrast with Eq. 5, it shows that the weighted softmax function (7) corresponds to an IS-based estimator of the standard softmax (3) with a proposal distribution $Q(w)$.

Importance sampling has been applied to NNLMs with large output layers in previous works (Bengio & Senécal, 2003; 2008; Jean et al., 2015). However, either uniform distribution or unigram distribution is used for sampling and all aforementioned works exploit the maximum likelihood learning of model parameter $\theta$. By contrast, BlackOut uses a discriminative training (6) and a power-raised unigram distribution $Q_{\alpha}(w)$ for sampling; these two changes are important to mitigate some of limitations of IS-based approaches. While an IS-based approach with a uniform proposal distribution is very stable for training, it suffers from large bias due to the apparent divergence of the uniform distribution from the true data distribution $p_{\theta}(w|s)$. On the other hand, a unigram-based IS estimate can make learning unstable due to the high variance (Bengio & Senécal, 2003; 2008). Using a power-raised unigram distribution $Q_{\alpha}(w)$ entails a better trade-off between bias and variance, and thus strikes a better balance between these two extremes. In addition, as we will see from the experiments, the discriminative training of BlackOut speeds up the rate of convergence over the traditional maximum likelihood learning.

2 Connection to Noise Contrastive Estimation

The basic idea of NCE is to transform the density estimation problem to the problem of learning by comparison, e.g., estimating the parameters of a binary classifier that distinguishes samples from the data distribution $p_{d}$ from samples generated by a known noise distribution $p_{n}$ (Gutmann & Hyvärinen, 2012). In the language modeling setting, the data distribution $p_{d}$ will be the distribution $p_{\theta}(w|s)$ of interest, and the noise distribution $p_{n}$ is often chosen from the ones that are easy to sample from and possibly close to the true data distribution (so that the classification problem isn’t trivial). While Mnih & Teh (2012) uses a context-independent (unigram) noise distribution $p_{n}(w)$, BlackOut can be formulated into the NCE framework by considering a context-dependent noise distribution $p_{n}(w|s)$, estimated from $K$ samples drawn from $Q(w)$, by

Similar to Gutmann & Hyvärinen (2012), noise samples are assumed $K$ times more frequent than data samples so that data points are generated from a mixture of two distributions: $\frac{1}{K+1}p_{\theta}(w|s)$ and $\frac{K}{K+1}p_{n}(w|s)$. Then the conditional probability of sample $w_{i}$ being generated from the data distribution is

which is exactly the weighted softmax function defined in (7). Note that due to the noise distribution proposed in Eq. 13, the expensive denominator (or the partition function $Z$) of $p_{\theta}(w_{j}|s)$ is canceled out, while in Mnih & Teh (2012) the partition function $Z$ is either treated as a free parameter to be learned or approximated by a constant. Mnih & Teh (2012) recommended to set $Z=1.0$ in the NCE training. However, from our experiments, setting $Z=1.0$ often leads to sub-optimal solutionsSimilarly, Chen et al. (2015) reported that setting $\ln(Z)=9$ gave them the best results. and different settings of $Z$ sometimes incur numerical instability since the log-sum-exp trickhttps://en.wikipedia.org/wiki/LogSumExp can not be used there to shift the scores of the output layer to a range that is amenable to the exponential function. BlackOut does not have this hyper-parameter to tune and the log-sum-exp trick still works for the weighted softmax function (7). Due to the discriminative training of NCE and BlackOut, they share the same objective function (6).

3 Related Work

Many approaches have been proposed to address the difficulty of training deep neural networks with large output spaces. In general, they can be categorized into four categories:

Hierarchical softmax (Morin & Bengio, 2005; Mnih & Hinton, 2008) uses a hierarchical binary tree representation of the output layer with the $V$ words as its leaves. It allows exponentially faster computation of word probabilities and their gradients, but the predictive performance of the resulting model is heavily dependent on the tree used, which is often constructed heuristically. Moreover, by relaxing the constraint of a binary structure, Le et al. (2011) introduces a structured output layer with an arbitrary tree structure constructed from word clustering. All these methods speed up both the model training and evaluation considerably.

Sampling-based approximations select at random or heuristically a small subset of the output layer and estimate gradient only from those samples. The use of importance sampling in Bengio & Senécal (2003; 2008); Jean et al. (2015), and the use of NCE (Gutmann & Hyvärinen, 2012) in Mnih & Teh (2012) all fall under this category, so does the more recent use of Locality Sensitive Hashing (LSH) techniques (Shrivastava & Li, 2014; Vijayanarasimhan et al., 2014) to select a subset of good samples. BlackOut, with close connections to importance sampling and NCE, also falls in this category. All these approaches only speed up the model training, while the model evaluation still remains computationally challenging.

Self normalization (Devlin et al., 2014) extends the cross-entropy loss function by explicitly encouraging the partition function of softmax to be as close to 1.0 as possible. Initially, this approach only speeds up the model evaluation and more recently it’s extended to facilitate the training as well with some theoretical guarantees (Andreas & Klein, 2014; Andreas et al., 2015).

Exact gradient on limited loss functions (Vincent et al., 2015) introduces an algorithmic approach to efficiently compute the exact loss, gradient update for the output weights in $\mathcal{O}(h^{2})$ per training example instead of $\mathcal{O}(Vh)$. Unfortunately, it only applies to a limited family of loss functions that includes squared error and spherical softmax, while the standard softmax isn’t included.

As discussed in the introduction, BlackOut also shares some similarity to DropOut (Srivastava et al., 2014). While DropOut is often applied to input and/or hidden layers of deep neural networks to avoid feature co-adaptation and overfitting by uniform sampling, BlackOut applies to a softmax output layer, uses a weighted sampling, and employs a discriminative training loss. We chose the name BlackOut in light of the similarities between our method and DropOut, and the complementary they offer to train deep neural networks.

Implementation and Further Speed-up

We implemented BlackOut on a standard machine with a dual-socket 28-core Intel®Xeon®Intel and Xeon are trademarks of Intel Corporation in the U.S. and/or other countries. Haswell CPU. To achieve high throughput, we train RNNLM with Back-Propagation Through Time (BPTT) (Rumelhart et al., 1988) with mini-batches (Chen et al., 2014). We use RMSProp (Hinton, 2012) for learning rate scheduling and gradient clipping (Bengio et al., 2013) to avoid the gradient explosion issue of recurrent networks. We use the latest Intel MKL library (version 11.3.0) for SGEMM calls, which has improved support for tall-skinny matrix-matrix multiplications, which consume about 80% of the run-time of RNNLMs.

It is expensive to access and update large models with billions of parameters. Fortunately, due to the 1-of-$V$ encoding at input layer and the BlackOut sampling at output layer, the model update on $W_{in}$ and $W_{out}$ is sparse, i.e., only the model parameters corresponding to input/output words and the samples in $S_{K}$ are updated at each training batch. However, subnet updates have to be done carefully due to the dependency within RMSProp updating procedure. We therefore propose an approximated RMSProp that enables an efficient subnet update and thus speeds up the algorithm even further. Details can be found in Appendix C.

Experiments

In our experiments, we first compare BlackOut, NCE and exact softmax (without any approximation) using a small dataset. We then evaluate the performance of BlackOut on the recently released one billion word language modeling benchmark (Chelba et al., 2014) with a vocabulary size of up to one million. We compare the performance of BlackOut on a standard CPU machine versus the state-of-the-arts reported in the literature that are achieved on GPUs or on clusters of CPU nodes. Our implementation and scripts are open sourced at https://github.com/IntelLabs/rnnlm.

Models are trained and evaluated on two different corpora: a small dataset provided by the RNNLM Toolkithttp://www.rnnlm.org/, and the recently released one billion word language modeling benchmarkhttps://code.google.com/p/1-billion-word-language-modeling-benchmark/, which is perhaps the largest public dataset in language modeling. The small dataset has 10,000 training sentences, with 71,350 words in total and 3,720 unique words; and the test perplexity is evaluated on 1,000 test sentences. The one billion word benchmark was constructed from a monolingual/English corpora; after all necessary preprocessing including de-duplication, normalization and tokenization, 30,301,028 sentences (about 0.8 billion words) are randomly selected for training, 6,075 sentences are randomly selected for test and the remaining 300,613 sentences are reserved for future development and can be used as holdout set.

1 Results On Small Dataset

We evaluate BlackOut, NCE and exact softmax (without any approximation) on the small dataset described above. This small dataset is used so that we can train the standard RNNLM algorithm with exact softmax within a reasonable time frame and hence to provide a baseline of expected perplexity. There are many other techniques involved in the training, such as RMSProp for learning rate scheduling (Hinton, 2012), subnet update (Appendix C), and mini-batch splicing (Chen et al., 2014), etc., which can affect the perplexity significantly. For a fair comparison, we use the same tricks and settings for all the algorithms, and only evaluate the impact of the different approximations (or no approximation) on the softmax output layer. Moreover, there are a few hyper-parameters that have strong impact on the predictive performance, including $\alpha$ of the proposal distribution $Q_{\alpha}(w)$ for BlackOut and NCE, and additionally for NCE, the partition function $Z$. We pay an equal amount of effort to tune these hyper-parameters for BlackOut and NCE on the validation set as number of samples increases.

Figure 2 shows the perplexity reduction as a function of number of samples $K$ under two different vocabulary settings: (a) a full vocabulary of 3,720 words, and (b) using the most frequent 2,065 words as vocabulary. The latter is a common approach used in practice to accelerate RNNLM computation by using RNNLM to predict only the most frequent words and handling the rest using an $n$-gram model (Schwenk & Gauvain, 2005). We will see similar vocabulary settings when we evaluate BlackOut on the large scale one billion word benchmark.

As can be seen, when the size of the samples increases, in general both BlackOut and NCE improve their prediction accuracy under the two vocabulary settings, and even with only 2 samples both algorithms still converge to reasonable solutions. BlackOut can utilize samples much more effectively than NCE as manifested by the significantly lower perplexities achieved by BlackOut, especially when number of samples is small; Given about 20-50 samples, BlackOut and NCE reach similar perplexities as the exact softmax, which is expensive to train as it requires to evaluate all the words in the vocabularies. When the vocabulary size is 2,065, BlackOut achieves even better perplexity than that of the exact softmax. This is possible since BlackOut does stochastic sampling at each training example and uses the full softmax output layer in prediction; this is similar to DropOut that is routinely used in input layer and/or hidden layers of deep neural networks (Srivastava et al., 2014). As in DropOut, BlackOut has the benefit of regularization and avoids feature co-adaption and is possibly less prone to overfitting. To verify this hypothesis, we evaluate the perplexities achieved on the training set for different algorithms and provide the results in Figure 5 at Appendix B. As can been seen, the exact softmax indeed overfits to the training set and reaches lower training perplexities than NCE and BlackOut.

Next we compare the convergence rates of BlackOut and NCE when training the RNNLMs with 16 hidden units for a full vocabulary of 3,720 words. Figures 3 and 3 plot the learning curves of BlackOut and NCE when 10 samples or 50 samples are used in training, respectively. The figure shows that BlackOut enjoys a much faster convergence rate than NCE, especially when number of samples is small (Figure 3); but this advantage gets smaller when number of samples increases (Figure 3). We also observed similar behavior when we evaluated BlackOut and NCE on the large scale one billion word benchmark.

2 Results On One Billion Word Benchmark

We follow the experiments from Williams et al. (2015) and Le et al. (2015) and compare the performance of BlackOut with the state-of-the-art results provided by them. While we evaluated BlackOut on a dual-socket 28-core Intel®Xeon®Haswell machine, Williams et al. (2015) implemented RNNLM with the NCE approximation on NVIDIA GTX Titan GPUs, and Le et al. (2015) executed an array of recurrent networks, including deep RNN and LSTM, without approximation on a CPU cluster. Besides the time-to-solution comparison, these published results enable us to cross-check the predictive performance of BlackOut with another implementation of NCE or with other competitive network architectures.

Following the experiments in Williams et al. (2015), we evaluate the performance of BlackOut on a vocabulary of 64K most frequent words. This is similar to the scenario in Figure 2 where the most frequent words are kept in vocabulary and the rest rare words are mapped to a special token. We first study the importance of $\alpha$ of the proposal distribution $Q_{\alpha}(w)$ and the discriminative training (6) as proposed in BlackOut. As we discussed in Sec. 2, when $\alpha=0$, the proposal distribution $Q_{\alpha}(w)$ degenerates to a uniform distribution over all the words in the vocabulary, and when $\alpha=1$, we recover the unigram distribution. Thus, we evaluate the impact of $\alpha$ in the range of $$. Figure 4 shows the evolution of test perplexity as a function of$\alpha$for the RNNLMs with 256 hidden units. As can be seen,$\alpha$has a significant impact on the prediction accuracy. The commonly used uniform distribution (when$\alpha=0$) and unigram distribution (when$\alpha=1$) often yield sub-optimal solutions. For the dataset and experiment considered,$\alpha=0.4$gives the best perplexity (consistent on holdout set and test set). We therefore use$\alpha=0.4$ in the experiments that follow. The number of samples used is 500, which is about 0.8% of the vocabulary size.

Figure 4 demonstrates the impact of discriminative training (6) over the maximum likelihood training (the first term of Eq. 6) on the RNNLMs with 512 hidden units using two different $\alpha$’s. In general, we observe 1-3 points of perplexity reduction due to discriminative training over traditional maximum likelihood training.

Finally, we evaluate the scalability of BlackOut when number of hidden units increases. As the dataset is large, we observed that the performance of RNNLM depends on the size of the hidden layer: they perform better as the size of the hidden layer gets larger. As a truncated 64K word vocabulary is used, we interpolate the RNNLM scores with a full size 5-gram to fill in rare word probabilities (Schwenk & Gauvain, 2005; Park et al., 2010). We report the interpolated perplexities BlackOut achieved and compare them with the results from Williams et al. (2015) in Table 1. As can be seen, BlackOut reaches lower perplexities than those reported in Williams et al. (2015) within comparable time frames (often 10%-40% faster). We achieved a perplexity of 42.0 when the hidden layer size is 4096. To the best of our knowledge, this is the lowest perplexity reported on this benchmark.

2.2 When vocabulary size is 1M

In the final set of experiments, we evaluate the performance of BlackOut with a very large vocabulary of 1,000,000 words, and the results are provided in Table 2. This is the largest vocabulary used on this benchmark that we could find in existing literature. We consider the RNNLM with 1,024 hidden units (about 2 billion parameters) and 2,048 hidden units (about 4.1 billion parameters) and compare their test perplexities with the results from Le et al. (2015). We use 2,000 samples, 0.2% of the vocabulary size, for BlackOut training with $\alpha=0.1$. Comparing to the experiments with the 64K word vocabulary, a much smaller $\alpha$ is used here since the sampling rate (0.2%) is much lower than that is used (0.8%) when the vocabulary size is 64K, and a smaller $\alpha$ strikes a better balance between sample coverage per training example and convergence rate. In contrast, NCE with the same setting converges very slowly (similar to Figure 3) and couldn’t reach a competitive perplexity within the time frame considered, and its results are not reported here.

As the standard RNN/LSTM algorithms (without approximation) are used in Le et al. (2015), a cluster of 32 CPU machines (at least 20 cores each) are used to train the models for about 60 hours. BlackOut enables us to train this large model using a single CPU machine for 175 hours. Since different model architectures are used in the experiments (deep RNN/LSTM vs. standard RNNLM), the direct comparison of test perplexity isn’t very meaningful. However, this experiment demonstrates that even though our largest model is about 2-3 times larger than the models evaluated in Le et al. (2015), BlackOut, along with a few other optimization techniques, make this large scale learning problem still feasible on a single box machine without using GPUs or CPU clusters.

Last, we collect all the state of the art results we are aware of on this benchmark and summarize them in Table 3. Since all the models are the interpolated ones, we interpolate our best RNN modelTo be consistent with the benchmark in Chelba et al. (2014), we retrained it with the full-size vocabulary of about 0.8M words. from Table 2 with the KN 5-gram model and achieve a perplexity score of 47.3. Again, different papers provide their best models trained with different architectures and vocabulary settings. Hence, an absolutely fair comparison isn’t possible. Regardless of these discrepancies, our models, within different groups of vocabulary settings, are very competitive in terms of prediction accuracy and model size.

Conclusion

We proposed BlackOut, a sampling-based approximation, to train RNNLMs with very large vocabularies (e.g., 1 million). We established its connections to importance sampling and noise contrastive estimation (NCE), and demonstrated its stability, sample efficiency and rate of convergence on the recently released one billion word language modeling benchmark. We achieved the lowest reported perplexity on this benchmark without using GPUs or CPU clusters.

As for future extensions, our plans include exploring other proposal distributions $Q(w)$, and theoretical properties of the generalization property and sample complexity bounds for BlackOut. We will also investigate a multi-machine distributed implementation.

Acknowledgments

We would like to thank Oriol Vinyals, Andriy Mnih and the anonymous reviewers for their excellent comments and suggestions, which helped improve the quality of this paper.

References

Appendix B Perplexities on Training set

Appendix C Subnet Update With Approximated RMSProp

RMSProp (Hinton, 2012) is an adaptive learning rate method that has found much success in practice. Instead of using a single learning rate to all the model parameters in $\Omega$, RMSProp dedicates a learning rate for each model parameter and normalizes the gradient by an exponential moving average of the magnitude of the gradient:

where $\beta\in(0,1)$ denotes the decay rate. The model update at time step $t$ is then given by

where $\epsilon$ is the learning rate and $\lambda$ is a damping factor, e.g., $\lambda=10^{-6}$. While RMSProp is one of the most effective learning rate scheduling techniques, it requires a large amount of memory to store per-parameter $v_{t}$ in addition to model parameter $\Omega$ and their gradients.

It is expensive to access and update large models with billions of parameters. Fortunately, due to the 1-of-$V$ encoding at input layer and the BlackOut sampling at output layer, the model update on $W_{in}$ and $W_{out}$ is sparse, e.g., only the model parameters corresponding to input/output words and the samples in $S_{K}$ are to be updated.The parameter update on $W_{r}$ is still dense, but its size is several orders of magnitude smaller than those of $W_{in}$ and $W_{out}$. For Eq. 16, however, even a model parameter is not involved in the current training, its $v_{t}$ value still needs to be updated by $v_{t}=\beta v_{t-1}$ since its $(\nabla J)^{2}=0$. Ignoring this update has detrimental effect on the predictive performance; in our experiments, we observed $5-10$ point perplexity loss if we ignore this update completely.

We resort to an approximation to $v_{t}=\beta v_{t-1}$. Given $p_{u}(w)$ is the probability of a word $w$ being selected for update, the number of time steps elapsed when it is successfully selected follows a geometric distribution with a success rate $p_{u}(w)$, whose mean value is $1/p_{u}(w)$. Assume that an input/output word is selected according to the unigram distribution $p_{uni}(w)$ and the samples in $S_{K}$ are drawn from $Q_{\alpha}(w)$, Eq. 16 can be approximated by

where $B$ is the mini-batch size and $T$ is the BPTT block size. Now we can only update the model parameters, typically a tiny fraction of $\Omega$, that are really involved in the current training, and thus speed up the RNNLM training further.