Title: BREAKING THE SOFTMAX BOTTLENECK: A HIGH-RANK RNN LANGUAGE MODEL

Abstract: We formulate language modeling as a matrix factorization problem, and show that the expressiveness of Softmax-based models (including the majority of neural language models) is limited by a Softmax bottleneck. Given that natural language is highly context-dependent, this further implies that in practice Softmax with distributed word embeddings does not have enough capacity to model natural language. We propose a simple and effective method to address this issue, and improve the state-of-the-art perplexities on Penn Treebank and WikiText-2 to 47.69 and 40.68 respectively. The proposed method also excels on the large-scale 1B Word dataset, outperforming the baseline by over 5.6 points in perplexity. 1 * Equal contribution. Ordering determined by dice rolling. 1 Code is available at https://github.com/zihangdai/mos.

1. INTRODUCTION:

As a fundamental task in natural language processing, statistical language modeling has gone through significant development from traditional Ngram language models to neural language models in the last decade (Bengio et al., 2003; Mnih & Hinton, 2007; Mikolov et al., 2010) . Despite the huge variety of models, as a density estimation problem, language modeling mostly relies on a universal auto-regressive factorization of the joint probability and then models each conditional factor using different approaches. Specifically, given a corpus of tokens X = (X 1 , . . . , X T ), the joint probability P (X) factorizes as P (X) = t P (X t | X <t ) = t P (X t | C t ), where C t = X <t is referred to as the context of the conditional probability hereafter.

Based on the factorization, recurrent neural networks (RNN) based language models achieve stateof-the-art results on various benchmarks (Merity et al., 2017; Melis et al., 2017; Krause et al., 2017) . A standard approach is to use a recurrent network to encode the context into a fixed size vector, which is then multiplied by the word embeddings (Inan et al., 2016; Press & Wolf, 2017) using dot product to obtain the logits. The logits are consumed by the Softmax function to give a categorical probability distribution over the next token. In spite of the expressiveness of RNNs as universal approximators (Schäfer & Zimmermann, 2006) , an unclear question is whether the combination of dot product and Softmax is capable of modeling the conditional probability, which can vary dramatically with the change of the context.

In this work, we study the expressiveness of the aforementioned Softmax-based recurrent language models from a perspective of matrix factorization. We show that learning a Softmax-based recurrent language model with the standard formulation is essentially equivalent to solving a matrix factorization problem. More importantly, due to the fact that natural language is highly context-dependent, the matrix to be factorized can be high-rank. This further implies that standard Softmax-based language models with distributed (output) word embeddings do not have enough capacity to model natural language. We call this the Softmax bottleneck.

We propose a simple and effective method to address the Softmax bottleneck. Specifically, we introduce discrete latent variables into a recurrent language model, and formulate the next-token probability distribution as a Mixture of Softmaxes (MoS). Mixture of Softmaxes is more expressive than Softmax and other surrogates considered in prior work. Moreover, we show that MoS learns

2.1. SOFTMAX:

The majority of parametric language models use a Softmax function operating on a context vector (or hidden state) h c and a word embedding w x to define the conditional distribution P θ (x|c). More specifically, the model distribution is usually written as

EQUATION

where h c is a function of c, and w x is a function of x. Both functions are parameterized by θ. Both the context vector h c and the word embedding w x have the same dimension d. The dot product h c w x is called a logit.

To help discuss the expressiveness of Softmax, we define three matrices:

H θ =     h c1 h c2 • • • h c N     ; W θ =     w x1 w x2 • • • w x M     ; A =     log P * (x 1 |c 1 ), log P * (x 2 |c 1 ) • • • log P * (x M |c 1 ) log P * (x 1 |c 2 ), log P * (x 2 |c 2 ) • • • log P * (x M |c 2 ) . . . . . . . . . . . . log P * (x 1 |c N ), log P * (x 2 |c N ) • • • log P * (x M |c N )    

where

H θ ∈ R N ×d , W θ ∈ R M ×d , A ∈ R N ×M

, and the rows of H θ , W θ , and A correspond to context vectors, word embeddings, and log probabilities of the true data distribution respectively. We use the subscript θ because (H θ , W θ ) is effectively a function indexed by the parameter θ, from the joint function family U. Concretely, H θ is implemented as deep neural networks, such as a recurrent network, while W θ is instantiated as an embedding lookup.

We further specify a set of matrices formed by applying row-wise shift to A

F (A) = {A + ΛJ N,M |Λ is diagonal and Λ ∈ R N ×N },

where J N,M is an all-ones matrix with size N × M . Essentially, the row-wise shift operation adds an arbitrary real number to each row of A. Thus, F (A) is an infinite set. Notably, the set F (A) has two important properties (see Appendix A for the proof), which are key to our analysis. Property 1. For any matrix A , A ∈ F (A) if and only if Softmax(A ) = P * . In other words, F (A) defines the set of all possible logits that correspond to the true data distribution.

Property 2. For any

A 1 = A 2 ∈ F (A), |rank(A 1 ) -rank(A 2 )| ≤ 1.

In other words, all matrices in F (A) have similar ranks, with the maximum rank difference being 1.

Based on the Property 1 of F (A), we immediately have the following Lemma.

Lemma 1. Given a model parameter θ, H θ W θ ∈ F (A) if and only if P θ (X|c) = P * (X|c) for all c in L.

Now the expressiveness question becomes: does there exist a parameter θ and A ∈ F (A) such that

H θ W θ = A .

This is essentially a matrix factorization problem. We want the model to learn matrices H θ and W θ that are able to factorize some matrix A ∈ F (A). First, note that for a valid factorization to exist, the rank of H θ W θ has to be at least as large as the rank of A . Further, since The above corollary indicates that when the dimension d is too small, Softmax does not have the capacity to express the true data distribution. Clearly, this conclusion is not restricted to a finite language L. When L is infinite, one can always take a finite subset and the Softmax bottleneck still exists. Next, we discuss why the Softmax bottleneck is an issue by presenting our hypothesis that A is high-rank for natural language.

H θ ∈ R N ×d and W θ ∈ R M ×d ,

2.2. HYPOTHESIS: NATURAL LANGUAGE IS HIGH-RANK:

We hypothesize that for a natural language L, the log probability matrix A is a high-rank matrix. It is difficult (if possible) to rigorously prove this hypothesis since we do not have access to the true data distribution of a natural language. However, it is suggested by the following intuitive reasoning and empirical observations:

• Natural language is highly context-dependent (Mikolov & Zweig, 2012) . For example, the token "north" is likely to be followed by "korea" or "korean" in a news article on international politics, which however is unlikely in a textbook on U.S. domestic history. We hypothesize that such subtle context dependency should result in a high-rank matrix A.

• If A is low-rank, it means humans only need a limited number (e.g. a few hundred) of bases, and all semantic meanings can be created by (potentially) negating and (weighted) averaging these bases. However, it is hard to find a natural concept in linguistics and cognitive science that corresponds to such bases, which questions the existence of such bases. For example, semantic meanings might not be those bases since a few hundred meanings may not be enough to cover everyday meanings, not to mention niche meanings in specialized domains.

• Empirically, our high-rank language model outperforms conventional low-rank language models on several benchmarks, as shown in Section 3. We also provide evidences in Section 3.3 to support our hypothesis that learning a high-rank language model is important.

Given the hypothesis that natural language is high-rank, it is clear that the Softmax bottleneck limits the expressiveness of the models. In practice, the embedding dimension d is usually set at the scale of 10 2 , while the rank of A can possibly be as high as M (at the scale of 10 5 ), which is orders of magnitude larger than d. Softmax is effectively learning a low-rank approximation to A, and our experiments suggest that such approximation loses the ability to model context dependency, both qualitatively and quantitatively (Cf. Section 3).

2.3. EASY FIXES?:

Identifying the Softmax bottleneck immediately suggests some possible "easy fixes". First, as considered by a lot of prior work, one can employ a non-parametric model, namely an Ngram model (Kneser & Ney, 1995) . Ngram models are not constrained by any parametric forms so it can universally approximate any natural language, given enough parameters. Second, it is possible to increase the dimension d (e.g., to match M ) so that the model can express a high-rank matrix A.

However, these two methods increase the number of parameters dramatically, compared to using a low-dimensional Softmax. More specifically, an Ngram needs (N × M ) parameters in order to express A, where N is potentially unbounded. Similarly, a high-dimensional Softmax requires (M × M ) parameters for the word embeddings. Increasing the number of model parameters easily leads to overfitting. In past work, Kneser & Ney (1995) used back-off to alleviate overfitting. Moreover, as deep learning models were tuned by extensive hyper-parameter search, increasing the dimension d beyond several hundred is not helpful3 (Merity et al., 2017; Melis et al., 2017; Krause et al., 2017) .

Clearly there is a tradeoff between expressiveness and generalization on language modeling. Naively increasing the expressiveness hurts generalization. Below, we introduce an alternative approach that increases the expressiveness without exploding the parametric space.

2.4. MIXTURE OF SOFTMAXES: A HIGH-RANK LANGUAGE MODEL:

We propose a high-rank language model called Mixture of Softmaxes (MoS) to alleviate the Softmax bottleneck issue. MoS formulates the conditional distribution as

P θ (x|c) = K k=1 π c,k exp h c,k w x x exp h c,k w x ; s.t. K k=1 π c,k = 1

where π c,k is the prior or mixture weight of the k-th component, and h c,k is the k-th context vector associated with context c. In other words, MoS computes K Softmax distributions and uses a weighted average of them as the next-token probability distribution. Similar to prior work on recurrent language modeling (Merity et al., 2017; Melis et al., 2017; Krause et al., 2017) , we first apply a stack of recurrent layers on top of X to obtain a sequence of hidden states

(g 1 , • • • , g T ).

The prior and the context vector for context c t are parameterized as

π ct,k = exp w π,k gt K k =1 exp w π,k gt and h ct,k = tanh(W h,k g t ) where w π,k and W h,k are model parameters.

Our method is simple and easy to implement, and has the following advantages:

• Improved expressiveness (compared to Softmax). MoS is theoretically more (or at least equally) expressive compared to Softmax given the same dimension d. This can be seen by the fact that MoS with K = 1 is reduced to Softmax. More importantly, MoS effectively approximates A by

ÂMoS = log K k=1 Π k exp(H θ,k W θ )

where Π k is an (N × N ) diagonal matrix with elements being the prior π c,k . Because ÂMoS is a nonlinear function (log_sum_exp) of the context vectors and the word embeddings, ÂMoS can be arbitrarily high-rank. As a result, MoS does not suffer from the rank limitation, compared to Softmax.

• Improved generalization (compared to Ngram). Ngram models and high-dimensional Softmax (Cf. Section 2.3) improve the expressiveness but do not generalize well. In contrast, MoS does not have a generalization issue due to the following reasons. First, MoS defines the following generative process: a discrete latent variable k is first sampled from {1, • • • , K}, and then the next token is sampled based on the k-th Softmax component. By doing so we introduce an inductive bias that the next token is generated based on a latent discrete decision (e.g., a topic), which is often safe in language modeling (Blei et al., 2003) . Second, since ÂMoS is defined by a nonlinear function and not restricted by the rank bottleneck, in practice it is possible to reduce d to compensate for the increase of model parameters brought by the mixture structure. As a result, MoS has a similar model size compared to Softmax and thus is not prone to overfitting.

2.5. MIXTURE OF CONTEXTS: A LOW-RANK BASELINE:

Another possible approach is to directly mix the context vectors (or logits) before taking the Softmax, rather than mixing the probabilities afterwards as in MoS. Specifically, the conditional distribution is parameterized as

EQUATION

where h c,k and π c,k share the same parameterization as in MoS. Despite its superficial similarity to MoS, this model, which we refer to as mixture of contexts (MoC), actually suffers from the same rank limitation problem as Softmax. This can be easily seen by defining

h c = K k=1 π c,k h c,k , which turns the MoC parameterization (2) into P θ (x|c) = exp h c wx x exp h c w x

. Note that this is equivalent to the Softmax parameterization (1). Thus, performing mixture in the feature space can only make the function family U more expressive, but does not change the fact that the rank of H θ W θ is upper bounded by the embedding dimension d. In our experiments, we implement MoC as a baseline and compare it experimentally to MoS.

3. EXPERIMENTS:



3.1. MAIN RESULTS:

We conduct a series of experiments with the following settings:

• Following previous work (Krause et al., 2017; Merity et al., 2017; Melis et al., 2017) , we evaluate the proposed MoS model on two widely used language modeling datasets, namely Penn Treebank (PTB) (Mikolov et al., 2010) and WikiText-2 (WT2) (Merity et al., 2016) based on perplexity. For fair comparison, we closely follow the regularization and optimization techniques introduced by Merity et al. (2017) . We heuristically and manually search hyper-parameters for MoS based on the validation performance while limiting the model size (see Appendix B.1 for our hyper-parameters). • To investigate whether the effectiveness of MoS can be extended to even larger datasets, we conduct an additional language modeling experiment on the 1B Word dataset (Chelba et al., 2013) . Specifically, we lower-case the text and choose the top 100K tokens as the vocabulary. A standard neural language model with 2 layers of LSTMs followed by a Softmax output layer is used as the baseline. Again, the network size of MoS is adjusted to ensure a comparable number of parameters. are used as baselines. For evaluation, we include both the perplexity and the precision/recall of Smoothed Sentence-level BLEU, as suggested by Zhao et al. (2017) . When generating responses, we use beam search with beam size 10, restrict the maximum length to 30, and retain the top-5 responses.

The language modeling results on PTB and WT2 are presented in Table 1 and The improvement on the large-scale dataset is even more significant. As shown in Further, the experimental results on Switchboard are summarized in Table 4 5 . Clearly, on all metrics, MoS outperforms MoC and Softmax, showing its general effectiveness.

3.2. ABLATION STUDY:

To further verify the improvement shown above does come from the MoS structure rather than adding another hidden layer or finding a particular set of hyper-parameters, we conduct an ablation study on both PTB and WT2. Firstly, we compare MoS with an MoC architecture with the same number of layers, hidden sizes, and embedding sizes, which thus has the same number of parameters. In addition, we adopt the hyper-parameters used to obtain the best MoS model (denoted as MoS hyper-parameters), and train a baseline AWD-LSTM. To avoid distractive factors and save computational resources, all ablative experiments excluded the use of finetuing and dynamic evaluation.

The results are shown in Table 5 . Compared to the vanilla AWD-LSTM, though being more expressive, MoC performs only better on PTB, but worse on WT2. It suggests that simply adding another hidden layer or employing a mixture structure in the feature space does not guarantee a better performance. On the other hand, training AWD-LSTM using MoS hyper-parameters severely hurts the performance, which rules out hyper-parameters as the main source of improvement. 

3.3. VERIFY THE ROLE OF RANK:

While the study above verifies that MoS is the key to achieving the state-of-the-art performance, it is still not clear whether the superiority of MoS comes from its potential high rank, as suggested by our theoretical analysis in Section 2. In the sequel, we take steps to verify this hypothesis.

• Firstly, we verify that MoS does induce a high-rank log-probability matrix empirically, while MoC and Softmax fail. On the validation or test set of PTB with tokens X = {X 1 , . . . , X T }, we compute the log probabilities {log P (X i | X <i ) ∈ R M } T t=1 for each token using all three models. Then, for each model, we stack all T log-probability vectors into a T × M matrix, resulting in ÂMoS , ÂMoC and ÂSoftmax . Theoretically, the number of non-zero singular values of a matrix is equal to its rank. However, performing singular value decomposition of real valued matrices using numerical approaches often encounter roundoff errors. Hence, we adopt the expected roundoff error suggested by Press (2007) when estimating the ranks of ÂMoS , ÂMoC and ÂSoftmax . The estimated ranks are shown in Table 6 . As predicted by our theoretical analysis, the matrix ranks induced by Softmax and MoC are both limited by the corresponding embedding sizes. By contrast, the matrix rank obtained from MoS does not suffer from this constraint, almost reaching full rank (M = 10000). In appendix C.1, we give additional evidences for the higher rank of MoS. • Secondly, we show that, before reaching full rank, increasing the number of mixture components in MoS also increases the rank of the log-probability matrix, which in turn leads to improved performance (lower perplexity). Specifically, on PTB, with other hyper-parameters fixed as used in section 3.1, we vary the number of mixtures used in MoS and compare the corresponding empirical rank and test perplexity without finetuning. Table 7 summarizes the results. This clear positive correlation between rank and performance strongly supports the our theoretical analysis in section 2. Moreover, note that after reaching almost full rank (i.e., using 15 mixture components), further increasing the number of components degrades the performance due to overfitting (as we inspected the training and test perplexities).

• In addition, as performance improvement can often come from better regularization, we investigate whether MoS has a better, though unexpected, regularization effect compared to Softmax. We consider the 1B word dataset where overfitting is unlikely and no explicit regularization technique (e.g., dropout) is employed. As we can see from the left part of Table 3 , MoS and Softmax achieve a similar generalization gap, i.e., the performance gap between the test set and the training set. It suggests both models have similar regularization effects. Meanwhile, MoS has a lower training perplexity compared to Softmax, indicating that the improvement of MoS results from improved expressiveness.

• The last evidence we provide is based on an inverse experiment. Empirically, we find that when Softmax does not suffer from a rank limitation, e.g., in character-level language modeling, using MoS will not improve the performance. Due to lack of space, we refer readers to Appendix C.2 for details.

3.4. ADDITIONAL ANALYSIS:



MoS computational time:

The expressiveness of MoS does come with a computational costcomputing a K-times larger Softmax. To give readers a concrete idea of the influence on training time, we perform detailed analysis in Appendix C.3. As we will see, computational wall time of MoS is actually sub-linear w.r.t. the number of Softmaxes K. In most settings, we observe a two to three times slowdown when using MoS with up to 15 mixture components.

Qualitative analysis Finally, we conduct a case study on PTB to see how MoS improves the next-token prediction in detail. Due to lack of space, we refer readers to Appendix C.4 for details.

The key insight from the case study is that MoS is better at making context-dependent predictions. Specifically, given the same immediate preceding word, MoS will produce distinct next-step prediction based on long-term context in history. By contrast, the baseline often yields similar next-step prediction, independent of the long-term context.

4. RELATED WORK:

In language modeling, Hutchinson et al. (2011; 2012) have previously considered the problem from a matrix rank perspective. However, their focus was to improve the generalization of Ngram language models via a sparse plus low-rank approximation. By contrast, as neural language models already generalize well, we focus on a high-rank neural language model that improves expressiveness without sacrificing generalization. Neubig & Dyer (2016) proposed to mix Ngram and neural language models to unify and benefit from both. However, this mixture might not generalize well since an Ngram model, which has poor generalization, is included. Moreover, the fact that the two components are separately trained can limit its expressiveness. Levy & Goldberg (2014) also considered the matrix factorization perspective, but in the context of learning word embeddings.

In a general sense, Mixture of Softmaxes proposed in this work can be seen as a particular instantiation of the long-existing idea called Mixture of Experts (MoE) (Jacobs et al., 1991) . However, there are two core differences. Firstly, MoE has usually been instantiated as mixture of Gaussians to model data in continuous domains (Jacobs et al., 1991; Graves, 2013; Bazzani et al., 2016) . More importantly, the motivation of using the mixture structure is distinct. For Gaussian mixture models, the mixture structure is employed to allow for a parameterized multi-modal distribution. By contrast, Softmax by itself can parameterize a multi-modal distribution, and MoS is introduced to break the Softmax bottleneck as discussed in Section 2.

There has been previous work (Eigen et al., 2013; Shazeer et al., 2017) proposing architectures that can be categorized as instantiations of MoC, since the mixture structure is employed in the feature space. 6 The target of Eigen et al. (2013) is to create a more expressive feed-forward layer through the mixture structure. In comparison, Shazeer et al. (2017) focuses on a sparse gating mechanism also on the feature level, which enables efficient conditional computation and allows the training of a very large neural architecture. In addition to having different motivations from our work, all these MoC variants suffer from the same rank limitation problem as discussed in Section 2.

Finally, several previous works have tried to introduce latent variables into sequence modeling (Bayer & Osendorfer, 2014; Gregor et al., 2015; Chung et al., 2015; Gan et al., 2015; Fraccaro et al., 2016; Chung et al., 2016) . Except for (Chung et al., 2016) , these structures all define a continuous latent variable for each step of the RNN computation, and rely on the SGVB estimator (Kingma & Welling, 2013) to optimize a variational lower bound of the log-likelihood. Since exact integration is infeasible, these models cannot estimate the likelihood (perplexity) exactly at test time. Moreover, for discrete data, the variational lower bound is usually too loose to yield a competitive approximation compared to standard auto-regressive models. As an exception, Chung et al. (2016) utilizes Bernoulli latent variables to model the hierarchical structure in language, where the Bernoulli sampling is replaced by a thresholding operation at test time to give perplexity estimation.

5. CONCLUSIONS:

Under the matrix factorization framework, the expressiveness of Softmax-based language models is limited by the dimension of the word embeddings, which is termed as the Softmax bottleneck. Our proposed MoS model improves the expressiveness over Softmax, and at the same time avoids overfitting compared to non-parametric models and naively increasing the word embedding dimensions.

Our method improves the current state-of-the-art results on standard benchmarks by a large margin, which in turn justifies our theoretical reasoning: it is important to have a high-rank model for natural language.

A PROOFS

Proof of Property 1:

Proof. For any A ∈ F (A), let P A (X|C) denote the distribution defined by applying Softmax on the logits given by A . Consider row i column j, by definition any entry in A can be expressed as

A ij = A ij + Λ ii . It follows P A (x j |c i ) = exp A ij k exp A ik = exp(A ij + Λ ii ) k exp(A ik + Λ ii ) = exp A ij k exp A ik = P * (x j |c i )

For any A ∈ {A | Softmax(A ) = P * }, for any i and j, we have

P A (x j |c i ) = P A (x j |c i )

It follows that for any i, j, and k,

P A (x j |c i ) P A (x k |c i ) = exp A ij exp A ik = exp A ij exp A ik = P A (x j |c i ) P A (x k |c i ) As a result, A ij -A ij = A ik -A ik

This means each row in A can be obtained by adding a real number to the corresponding row in A. Therefore, there exists a diagonal matrix Λ ∈ R N ×N such that

A = A + ΛJ N,M It follows that A ∈ F (A).

Proof of Property 2:

Proof. For any A 1 and A 2 in F (A), by definition we have A 1 = A + Λ 1 J N,M , and

A 2 = A + Λ 2 J N,M

where Λ 1 and Λ 2 are two diagonal matrices. It can be rewritten as

A 1 = A 2 + (Λ 1 -Λ 2 )J N,M

Let S be a maximum set of linearly independent rows in A 2 . Let e N be an all-ones vector with dimension N . The i-th row vector a 1,i in A 1 can be written as 

a 1,i = a 2,i + (Λ 1,ii -Λ 2,ii )e N Because a 2,i is a linear combination of vectors in S, a 1,i is a linear combination of vectors in S ∪ {e N }. It follows that rank(A 1 ) ≤ rank(A 2 ) + 1 Similarly, we can derive rank(A 2 ) ≤ rank(A 1 ) + 1 Therefore, |rank(A 1 ) -rank(A 2 )| ≤ 1 Proof of

B EXPERIMENT SETTING AND HYPER-PARAMETERS B.1 PTB AND WT2:

The hyper-parameters used for MoS in language modeling experiment is summarized below. (Gal & Ghahramani, 2016) . See (Merity et al., 2017) for more detailed descriptions.

The hyper-parameters used for dynamic evaluation of MoS is summarized below. 

C.4 QUALITATIVE ANALYSIS:

Since MoC shows a stronger performance than Softmax on PTB, the qualitative study focuses on the comparison between MoC and MoS. Concretely, given the same context (previous tokens), we search for prediction steps where MoS achieves lower negative log loss than MoC by a margin. We show some representative cases in Table 14 with the following observations:

• Comparing the first two cases, given the same preceding word "N", MoS flexibly adjusts its top predictions based on the different topic quantities being discussed in the context. In comparison, MoC emits quite similar top choices regardless of the context, suggesting its inferiority in make context-dependent predictions. • In the 3rd case, the context is about international politics, where country/region names are likely to appear. MoS captures this nuance well, and yields top choices that can be used to complete a country name given the immediate preceding word "south". Similarly, in the 4th case, MoS is able to include "ual", a core entity of discussion in the context, in its top predictions. In contrast, MoC gives rather generic predictions irrieselevant to the context in both cases. • For the 5th and the 6th example, we see MoS is able to exploit less common words accurately according to the context, while MoC fails to yield such choices. This well matches our analysis that MoS has the capacity of modeling context-dependent language.

#1 Context managed properly and with a long-term outlook these can become investment-grade quality properties <eos> canadian <unk> production totaled N metric tons in the week ended oct. N up N N from the preceding week 's total of N __?__ (Mikolov et al., 2010) . The context shown only includes the previous sentence and the current sentence the prediction step resides in.

:

We use capital letters for variables and small letters for constants.

This is also confirmed by our preliminary experiments.

https://github.com/snakeztc/NeuralDialog-CVAE/tree/master/data

The numbers are not directly comparable toZhao et al. (2017) since their Seq2Seq implementation and evaluation scripts are not publicly available.

Although Shazeer et al. (2017) name their architecture as MoE, it is not a standard MoE(Jacobs et al., 1991) and should be classified as MoC under our terminology.

Figures and Tables:

If there exists a parameter θ such that P θ (X|c) = P * (X|c) for all c in L, by Lemma 1, we have H θ W θ ∈ F (A). As a result, there exists a matrixA ∈ F (A) such that H θ W θ = A . Because H θ and W θ are of dimensions (N × d) and (M × d) respectively, we have d ≥ rank(A ) ≥ min A ∈F (A) rank(A ) If d ≥ min A ∈F (A) rank(A ), there exist matrices A ∈ F (A), H ∈ R N ×d and W ∈ R M ×d ,such that A can be factorized as A = H W . Because U is a universal approximator, there exists θ such that H θ = H and W θ = W . By Lemma 1, P θ (X|c) = P * (X|c) for all c in L.

Figure 1: Cumulative percentage of normalized singulars given a value in [0, 1].

Notably, dropout was not used, since we found it not helpful to either model (see Appendix B.2 for more details). Single model perplexity on validation and test sets on Penn Treebank. Baseline results are obtained fromMerity et al. (2017) andKrause et al. (2017). † indicates using dynamic evaluation.

Table content: <table><tr><td>Model</td></tr></table>

Single model perplexity over WikiText-2. Baseline results are obtained fromMerity et al. (2017) andKrause et al. (2017). † indicates using dynamic evaluation.

Table content: <table/>

Table 2 respectively.With a comparable number of parameters, MoS outperforms all baselines with or without dynamic evaluation, and substantially improves over the current state of the art, by up to 3.6 points in perplexity.

Table content: <table><tr><td>Model</td><td colspan="3">#Param Train Validation</td><td>Test</td></tr><tr><td>Softmax</td><td>119M</td><td>41.47</td><td>43.86</td><td>42.77</td></tr><tr><td>MoS</td><td>113M</td><td>36.39</td><td>38.01</td><td>37.10</td></tr></table>

Perplexity comparison on 1B word dataset. Train perplexity is the average of the last 4,000 updates.

Table content: <table/>

MoS outperforms Softmax by over 5.6 points in perplexity. It suggests the effectiveness of MoS is not limited to small datasets where many regularization techniques are used. Note that with limited computational resources, we didn't tune the hyper-parameters for MoS.

Table content: <table><tr><td/><td>Perplexity</td><td colspan="2">BLEU-1</td><td colspan="2">BLEU-2</td><td colspan="2">BLEU-3</td><td colspan="2">BLEU-4</td></tr><tr><td>Model</td><td/><td>prec</td><td>recall</td><td>prec</td><td>recall</td><td>prec</td><td>recall</td><td>prec</td><td>recall</td></tr><tr><td>Seq2Seq-Softmax</td><td>34.657</td><td colspan="8">0.249 0.188 0.193 0.151 0.168 0.133 0.141 0.111</td></tr><tr><td>Seq2Seq-MoC</td><td>33.291</td><td colspan="8">0.259 0.198 0.202 0.159 0.176 0.140 0.148 0.117</td></tr><tr><td>Seq2Seq-MoS</td><td>32.727</td><td colspan="8">0.272 0.206 0.213 0.166 0.185 0.146 0.157 0.123</td></tr></table>

Evaluation scores on Switchboard.

Table content: <table/>

Ablation study on Penn Treebank and WikiText-2 without finetuning or dynamical evaluation.

Table content: <table><tr><td>PTB</td><td>WT2</td></tr></table>

Published as a conference paper at ICLR 2018

Table content: <table><tr><td>Model</td><td colspan="2">Validation Test</td><td colspan="3">#Softmax Rank Perplexity</td></tr><tr><td>Softmax</td><td>400</td><td>400</td><td>3</td><td>6467</td><td>58.62</td></tr><tr><td>MoC</td><td>280</td><td>280</td><td>5</td><td>8930</td><td>57.36</td></tr><tr><td>MoS</td><td>9981</td><td>9981</td><td>10</td><td>9973</td><td>56.33</td></tr><tr><td/><td/><td/><td>15</td><td>9981</td><td>55.97</td></tr><tr><td colspan="3">Table 6: Rank comparison on PTB. To ensure com-</td><td>20</td><td>9981</td><td>56.17</td></tr><tr><td colspan="3">parable model sizes, the embedding sizes of Softmax,</td><td/><td/><td/></tr><tr><td colspan="3">MoC and MoS are 400, 280, 280 respectively. The</td><td colspan="3">Table 7: Empirical rank and test perplexity on</td></tr><tr><td colspan="3">vocabulary size, i.e., M , is 10,000 for all models.</td><td colspan="3">PTB with different number of Softmaxes.</td></tr></table>

Hyper-parameters used for MoS. V-dropout abbreviates variational dropout

Table content: <table><tr><td>Hyper-parameter</td><td>PTB</td><td>WT2</td></tr><tr><td>Learning rate</td><td>20</td><td>15</td></tr><tr><td>Batch size</td><td>12</td><td>15</td></tr><tr><td>Embedding size</td><td>280</td><td>300</td></tr><tr><td>RNN hidden sizes</td><td colspan="2">[960, 960, 620] [1150,1150,650]</td></tr><tr><td>Number of mixture components</td><td>15</td><td>15</td></tr><tr><td>Word-level V-dropout</td><td>0.10</td><td>0.10</td></tr><tr><td>Embedding V-dropout</td><td>0.55</td><td>0.40</td></tr><tr><td>Hidden state V-dropout</td><td>0.20</td><td>0.225</td></tr><tr><td>Recurrent weight dropout (Wan et al., 2013)</td><td>0.50</td><td>0.50</td></tr><tr><td>Context vector V-dropout</td><td>0.30</td><td>0.30</td></tr></table>

Hyper-parameters used for Softmax and MoS in experiment on 1B word dataset. HIGHER EMPIRICAL RANK OF MOS COMPARED TO MOC AND SOFTMAX In section 3, we compute the rank of different models based on the non-zero singular values of the empirical log-likelihood matrix. Since there can be roundoff mistakes, a less error-prone approach is to directly study the distribution of singular values. Specifically, if more singular values have relatively larger magnitude, the rank of the matrix tends to be higher. Motivated from this intuition,

Table content: <table><tr><td colspan="2">Hyper-parameter</td><td>PTB</td><td>WT2</td></tr><tr><td>Batch size</td><td/><td>100</td><td>100</td></tr><tr><td colspan="2">learning rate (η)</td><td colspan="2">0.002 0.002</td></tr><tr><td/><td/><td colspan="2">0.001 0.002</td></tr><tr><td>λ</td><td/><td>0.075</td><td>0.02</td></tr><tr><td colspan="4">Table 9: Hyper-parameters used for dynamic evaluation of MoS. See (Krause et al., 2017) for more detailed</td></tr><tr><td>descriptions.</td><td/><td/></tr><tr><td>B.2 1B WORD DATASET</td><td/><td/></tr><tr><td colspan="4">For training, we use all of the 100 training shards. For validation, we use two shards from the</td></tr><tr><td colspan="4">heldout set, namely [heldout-00, heldout-10]. For test, we use another three shards from</td></tr><tr><td colspan="4">the heldout set, namely [heldout-20, heldout-30, heldout-40].</td></tr><tr><td>The hyper-parameters are listed below.</td><td/><td/></tr><tr><td>Hyper-parameter</td><td colspan="2">Softmax</td><td>MoS-7</td></tr><tr><td>Learning rate</td><td>20</td><td/><td>20</td></tr><tr><td>Batch size</td><td>60</td><td/><td>60</td></tr><tr><td>BPTT langth</td><td>35</td><td/><td>35</td></tr><tr><td>Embedding size</td><td colspan="2">1024</td><td>900</td></tr><tr><td>RNN hidden sizes</td><td colspan="3">[1024, 1024] [1024,1024]</td></tr><tr><td>Dropout rate</td><td>0</td><td/><td>0</td></tr><tr><td>C ADDITIONAL EXPERIMENTS</td><td/><td/></tr><tr><td>C.1</td><td/><td/></tr></table>

Empirical expected pairwise KLD on PTB.What's more, another indicator of high rank is that the model can precisely capture the nuance of difference contexts. If a model can better capture the distinctions among contexts, we expect the nextstep conditional distributions to be less similar to each on average. Based on this intuition, we use the expected pairwise Kullback-Leibler divergence (KLD), i.e., E c,c ∼C [KLD(P (X | c) P (X | c ))] where C denotes all possible contexts, as another metric to evaluate the ranks of the three models (MoS, MoC and Softmax). Practically, we sample c, c from validation or test data of PTB to get the empirical estimations for the three models, which are shown in the right half of Table11. As we expected, MoS achieves higher expected pairwise KLD, indicating its superiority in covering more contexts of the next-token distribution.

Table content: <table><tr><td colspan="6">C.2 AN INVERSE EXPERIMENT ON CHARACTER-LEVEL LANGUAGE MODELING</td></tr><tr><td>Model</td><td/><td colspan="4">#Param Train Validation Test</td></tr><tr><td colspan="2">Softmax (hid1024, emb1024)</td><td>8.42M</td><td>1.35</td><td>1.41</td><td>1.49</td></tr><tr><td>MoS-7</td><td>(hid910, emb510)</td><td>8.45M</td><td>1.35</td><td>1.40</td><td>1.49</td></tr><tr><td>MoS-7</td><td>(hid750, emb750)</td><td>8.45M</td><td>1.38</td><td>1.42</td><td>1.50</td></tr><tr><td colspan="2">MoS-10 (hid860, emb452)</td><td>8.43M</td><td>1.35</td><td>1.41</td><td>1.49</td></tr><tr><td colspan="2">MoS-10 (hid683, emb683)</td><td>8.43M</td><td>1.38</td><td>1.42</td><td>1.50</td></tr></table>

BPC

Table content: <table/>

Referencecanadian <unk> production totaled N metric tons in the week ended oct. N up N N from the preceding week 's total of N tons statistics canada a federal agency said <eos> #2 Context the thriving <unk> street area offers <unk> of about $ N a square foot as do <unk> locations along lower fifth avenue <eos> by contrast <unk> in the best retail locations in boston san francisco and chicago rarely top $ N __?__ Reference by contrast <unk> in the best retail locations in boston san francisco and chicago rarely top $ N a square foot <eos> #3 Context as other <unk> governments particularly poland and the soviet union have recently discovered initial steps to open up society can create a momentum for radical change that becomes difficult if not impossible to control <eos> as the days go by the south __?__ Reference as the days go by the south african government will be ever more hard pressed to justify the continued <unk> of mr. <unk> as well as the continued banning of the anc and enforcement of the state of emergency <eos> #4 Context shares of ual the parent of united airlines were extremely active all day friday reacting to news and rumors about the proposed $ N billion buy-out of the airline by an <unk> group <eos> wall street 's takeover-stock speculators or risk arbitragers had placed unusually large bets that a takeover would succeed and __?__ Reference wall street 's takeover-stock speculators or risk arbitragers had placed unusually large bets that a takeover would succeed and ual stock would rise <eos> #5 Context the government is watching closely to see if their presence in the <unk> leads to increased <unk> protests and violence if it does pretoria will use this as a reason to keep mr. <unk> behind bars <eos> pretoria has n't forgotten why they were all sentenced to life <unk> in the first place for sabotage and __?__ Reference pretoria has n't forgotten why they were all sentenced to life <unk> in the first place for sabotage and conspiracy to <unk> the government <eos> #6 Context china 's <unk> <unk> program has achieved some successes in <unk> runaway economic growth and stabilizing prices but has failed to eliminate serious defects in state planning and an <unk> drain on state budgets <eos> the official china daily said retail prices of <unk> foods have n't risen since last december but acknowledged that huge government __?__ Reference the official china daily said retail prices of <unk> foods have n't risen since last december but acknowledged that huge government subsidies were a main factor in keeping prices down <eos>

Table content: <table><tr><td>MoS top-5</td><td>million 0.38</td><td>tons 0.24</td><td>billion 0.09</td><td>barrels 0.06</td><td>ounces 0.04</td></tr><tr><td>MoC top-5</td><td>billion 0.39</td><td>million 0.36</td><td>trillion 0.05</td><td>&lt;eos&gt; 0.04</td><td>N 0.03</td></tr><tr><td>MoS top-5</td><td>&lt;eos&gt; 0.36</td><td>a 0.13</td><td>to 0.07</td><td>for 0.07</td><td>and 0.06</td></tr><tr><td>MoC top-5</td><td>million 0.39</td><td>billion 0.36</td><td>&lt;eos&gt; 0.05</td><td>to 0.04</td><td>of 0.03</td></tr><tr><td>MoS top-5</td><td>africa 0.15</td><td>african 0.15</td><td>&lt;eos&gt; 0.14</td><td>korea 0.08</td><td>korean 0.05</td></tr><tr><td>MoC top-5</td><td>&lt;eos&gt; 0.38</td><td>and 0.08</td><td>of 0.06</td><td>or 0.05</td><td>&lt;unk&gt; 0.04</td></tr><tr><td>MoS top-5</td><td>the 0.14</td><td>that 0.07</td><td>ual 0.07</td><td>&lt;unk&gt; 0.03</td><td>it 0.02</td></tr><tr><td>MoC top-5</td><td>the 0.10</td><td>&lt;unk&gt; 0.06</td><td>that 0.05</td><td>in 0.02</td><td>it 0.02</td></tr><tr><td>MoS top-5</td><td>&lt;unk&gt; 0.47</td><td>violence 0.11</td><td>conspiracy 0.03</td><td>incest 0.03</td><td>civil 0.03</td></tr><tr><td>MoC top-5</td><td>&lt;unk&gt; 0.41</td><td>the 0.03</td><td>a 0.02</td><td>other 0.02</td><td>in 0.01</td></tr><tr><td>MoS top-5</td><td>subsidies 0.15</td><td>spending 0.08</td><td>officials 0.04</td><td>costs 0.04</td><td>&lt;unk&gt; 0.03</td></tr><tr><td>MoC top-5</td><td>officials 0.04</td><td>figures 0.03</td><td>efforts 0.03</td><td>&lt;unk&gt; 0.03</td><td>costs 0.03</td></tr></table>

Compaison of next-token prediction on Penn Treebank test data. N stands for a number as the result of preprocessing

Table content: <table/>

Peer review (iclr2018):
 The authors argue in this paper that due to the limited rank of the context-to-vocabulary logit matrix in the currently used version of the softmax output layer, it is not able to capture the full complexity of language. As a result, they propose to use a mixture of softmax output layers instead where the mixing probabilities are context-dependent, which allows to obtain a full rank logit matrix in complexity linear in the number of mixture components (here 15). This leads to improvements in the word-level perplexities of the PTB and wikitext2 data sets, and Switchboard BLEU scores. The question of the expressiveness of the softmax layer, as well as its suitability for word-level prediction, is indeed an important one which has received too little attention. This makes a lot of the questions asked in this paper extremely relevant to the field. However, it is unclear that the rank of the logit matrix is the right quantity to consider. For example, it is easy to describe a rank D NxM matrix where up to 2^D lines have max values at different indices. Further, the first two "observations" in Section 2.2 would be more accurately described as "intuitions" of the authors. As they write themselves "there is no evidence showing that semantic meanings are fully linearly correlated." Why then try to link "meanings" to basis vectors for the rows of A? To be clear, the proposed model is undoubtedly more expressive than a regular softmax, and although it does come at a substantial computational cost (a back-of-the envelope calculation tells us that computing 15 components of 280d MoS takes the same number of operations as one with dimension 1084 = sqrt (280*280*15)), it apparently manages not to drastically increase overfitting, which is significant. Unfortunately, this is only tested on relatively small data sets, up to 2M tokens and a vocabulary of size 30K for language modeling. They do constitute a good starting place to test a model, but given the importance of regularization on those specific tasks, it is difficult to predict how the MoS would behave if more training data were available, and if one could e.g. simply try a 1084 dimension embedding for the softmax without having to worry about overfitting. Another important missing experiment would consist in varying the number of mixture components (this could very well be done on WikiText2). This could help validate the hypothesis: how does the estimated rank vary with the number of components? How about the performance and pairwise KL divergence? This paper offers a promising direction for language modeling research, but would require more justification, or at least a more developed experimental section. Pros: - Important starting question - Thought-provoking approach - Experimental gains on small data sets Cons: - The link between the intuition and reality of the gains is not obvious - Experiments limited to small data sets, some obvious questions remain