TRAINING NATURAL LANGUAGE GENERATION MOD- ELS
Year: 2019

Abstract:
We study an interesting problem in training neural network-based models for natural language generation tasks, which we call the representation degeneration problem. We observe that when training a model for natural language generation tasks through likelihood maximization with the weight tying trick, especially with big training datasets, most of the learnt word embeddings tend to degenerate and be distributed into a narrow cone, which largely limits the representation power of word embeddings. We analyze the conditions and causes of this problem and propose a novel regularization method to address it. Experiments on language modeling and machine translation show that our method can largely mitigate the representation degeneration problem and achieve better performance than baseline algorithms.

heading: 1 INTRODUCTION
text: Neural Network (NN)-based algorithms have made significant progresses in natural language generation tasks, including language modeling (Kim et al., 2016; Jozefowicz et al., 2016), machine translation (Wu et al., 2016; Britz et al., 2017; Vaswani et al., 2017; Gehring et al., 2017) and dialog systems (Shang et al., 2015). Despite the huge variety of applications and model architectures, natural language generation mostly relies on predicting the next word given previous contexts and other conditional information. A standard approach is to use a deep neural network to encode the inputs into a fixed-size vector referred as hidden state1, which is then multiplied by the word embedding matrix (Vaswani et al., 2017; Merity et al., 2018; Yang et al., 2018; Press & Wolf, 2017). The output logits are further consumed by the softmax function to give a categorical distribution of the next word. Then the model is trained through likelihood maximization.
While studying the learnt models for language generation tasks, we observe some interesting and surprising phenomena. As the word embedding matrix is tied with the softmax parameters (Vaswani et al., 2017; Merity et al., 2018; Inan et al., 2017; Press & Wolf, 2017), it has a dual role in the model, serving as the input in the first layer and the weights in the last layer. Given its first role as input word embedding, it should contain rich semantic information that captures the given context which will be further used for different tasks. Given its role as output softmax matrix, it should have enough capacity to classify different hidden states into correct labels. We compare it with
∗This work was done when Jun Gao was an intern at Microsoft Research Asia. 1The concept of hidden states has multiple meanings in the literature of neural networks. In this paper, we
use hidden state as the input to the last softmax layer.
word embeddings trained from Word2Vec (Mikolov et al., 2013) and the parameters in the softmax layer of a classical classification task (we refer it as categorical embedding). As shown in Figure 1, the word embeddings learnt from Word2Vec (Figure 1(b)) and the softmax parameters learnt from the classification task (Figure 1(c)) are diversely distributed around the origin using SVD projection; in contrast, the word embeddings in our studied model (Figure 1(a)) degenerated into a narrow cone. Furthermore, we find the embeddings of any two words in our studied models are positively correlated. Such phenomena are very different from those in other tasks and deteriorate model’s capacity. As the role of the softmax layer, those parameters cannot lead to a large margin prediction for good generalization. As the role of word embeddings, the parameters do not have enough capacity to model the diverse semantics in natural languages (Yang et al., 2018; McCann et al., 2017).
We call the problem described above the representation degeneration problem. In this paper, we try to understand why the problem happens and propose a practical solution to address it.
We provide some intuitive explanation and theoretical justification for the problem. Intuitively speaking, during the training process of a model with likelihood loss, for any given hidden state, the embedding of the corresponding ground-truth word will be pushed towards the direction of the hidden state in order to get a larger likelihood, while the embeddings of all other words will be pushed towards the negative direction of the hidden state to get a smaller likelihood. As in natural language, word frequency is usually very low comparing to the size of a large corpus, the embedding of the word will be pushed towards the negative directions of most hidden states which drastically vary. As a result, the embeddings of most words in the vocabulary will be pushed towards similar directions negatively correlated with most hidden states and thus are clustered together in a local region of the embedding space.
From the theoretical perspective, we first analyze the extreme case of non-appeared words. We prove that the representation degeneration problem is related to the structure of hidden states: the degeneration appears when the convex hull of the hidden states does not contain the origin and such condition is likely to happen when training with layer normalization (Ba et al., 2016; Vaswani et al., 2017; Merity et al., 2018). We further extend our study to the optimization of low-frequency words in a more realistic setting. We show that, under mild conditions, the low-frequency words are likely to be trained to be close to each other during optimization, and thus lie in a local region.
Inspired by the empirical analysis and theoretical insights, we design a novel way to mitigate the degeneration problem by regularizing the word embedding matrix. As we observe that the word embeddings are restricted into a narrow cone, we try to directly increase the size of the aperture of the cone, which can be simply achieved by decreasing the similarity between individual word embeddings. We test our method on two tasks, language modeling and machine translation. Experimental results show that the representation degeneration problem is mitigated, and our algorithm achieves superior performance over the baseline algorithms, e.g., with 2.0 point perplexity improvement on
the WikiText-2 dataset for language modeling and 1.08/0.93 point BLEU improvement on WMT 2014 English-German/German-English tasks for machine translation.

heading: 2 RELATED WORK
text: Language modeling and machine translation are important language generation tasks. Language modeling aims at predicting the next token given an (incomplete) sequence of words as context. A popular approach based on neural networks is to map the given context to a real-valued vector as a hidden state, and then pass the hidden state through a softmax layer to generate a distribution over all the candidate words. There are different choices of neural networks used in language modeling. Recurrent neural network-based model and convolutional neural network-based model are widely used (Mikolov et al., 2010; Dauphin et al., 2017).
Neural Machine Translation (NMT) is a challenging task that has attracted lots of attention in recent years. Based on the encoder-decoder framework, NMT starts to show promising results in many language pairs. The evolving structures of NMT models in recent years have pushed the accuracy of NMT into a new level. The attention mechanism (Bahdanau et al., 2015) added on top of the encoder-decoder framework is shown to be useful to automatically find alignment structure, and single-layer RNN-based structure has evolved towards deep models (Wu et al., 2016), more efficient CNN models (Gehring et al., 2017), and well-designed self-attention models (Vaswani et al., 2017).
In this paper, we mainly study the expressiveness of word embeddings in language generation tasks. A trend for language generation in recent years is to share the parameters between word embeddings and the softmax layer, which is named as the weight tying trick. Many state-of-the-art results in language modeling and machine translation are achieved with this trick (Vaswani et al., 2017; Merity et al., 2018; Yang et al., 2018; Press & Wolf, 2017). Inan et al. (2017) shows that weight tying not only reduces the number of parameters but also has theoretical benefits.

heading: 3 REPRESENTATION DEGENERATION PROBLEM
text: In this section, we empirically study the word embeddings learnt from sequence generation tasks, i.e., machine translation, and introduce the representation degeneration problem in neural sequence generation.

heading: 3.1 EXPERIMENTAL DESIGN
text: Our analysis reported in this section is mainly based on the state-of-the-art machine translation model Transformer (Vaswani et al., 2017). We use the official code (Vaswani et al., 2018) and set all the hyperparameters (the configurations of the base Transformer) as default. We train the model on the WMT 2014 English-German Dataset and achieve 27.3 in terms of BLEU score. Additionally, we also analyze the LSTM-based model (Wu et al., 2016) and find the observations are similar.
In neural sequence generation tasks, the weights in word embeddings and softmax layer are tied. Those parameters can be recognized not only as the inputs in the first layer but also as the weights in the last layer. Thus we compare this weight matrix with a word embedding matrix trained from conventional word representation learning task, and also compare it with the parameters in softmax layer of a conventional classification task. For simplicity and representative, we choose to use Word2Vec (Mikolov et al., 2013) to obtain word embeddings and use MNIST as the classification task trained with a two-layer convolutional neural network (Yue et al., 2018; Liu et al., 2016). For the classification task, We simply treat the row of the parameter matrix in the last softmax layer as the embedding for the category, like how the word embedding is used in the softmax layer for neural language generation model with weight tying trick.
To get a comprehensive understanding, we use low-rank approximation (rank = 2) for the learned matrices by SVD and plot them in a 2D plane, as shown in Figure 1. We also check the singular values distribution and find that our low-rank approximation is reasonable: other singular values are much smaller than the chosen ones.

heading: 3.2 DISCUSSION
text: In the classification task, the category embeddings (blue triangles in Figure 1(c)) in the softmax layer are diversely distributed around the origin. This shows the directions of category embeddings are different from each other and well separated, which consequently leads to large margin classification results with good generalization. For the word embeddings learnt from Word2Vec (Figure 1(b)), the phenomena are similar, the embeddings are also widely distributed around the origin in the projection space, which shows different words have different semantic meanings. Observations on GLOVE (Pennington et al., 2014) reported in Mu et al. (2018) are also consistent with ours.
We observe very different phenomena for machine translation. We can see from Figure 1(a) that the word embeddings are clustered together and only lying in a narrow cone. Furthermore, we find the cosine similarities between word embeddings are positive for almost all cases. That is, the words huddle together and are not well separated in the embedding space.
Clearly, as the role of word embeddings, which are the inputs to the neural networks, the word representations should be widely distributed to represent different semantic meanings. As the role of softmax in the output layer, to achieve good prediction of next word in a target sentence, a more diverse distribution of word embeddings in the space is expected to obtain a large margin result. However, such representations of words limit the expressiveness of the learnt model. We call such a problem the representation degeneration problem.

heading: 4 UNDERSTANDING THE PROBLEM
text: We show in the previous section that in training natural language generation models, the learnt word embeddings are clustered into a narrow cone and the model faces the challenge of limited expressiveness. In this section, we try to understand the reason of the problem and show that it is related to the optimization of low-frequency words with diverse contexts.
In natural language generation tasks, the vocabulary is usually of large size and the words are of low frequencies according to Zipf’s law. For example, more than 90% of words’ frequencies are lower than 10e-4 in WMT 2014 English-German dataset. Note that even for a popular word, its frequency is also relatively low. For a concrete example, the frequency of the word “is” is only about 1% in the dataset, since “is” occurs at most once in most simple sentences. Our analysis is mainly based on the optimization pattern of the low-frequency words which occupy the major proportion of vocabulary.
The generation of a sequence of words (or word indexes) y = (y1, · · · , yM ) is equivalent to generate the words one by one from left to right. The probability of generating y can be factorized as P (Y = y) = ΠtP (Yt = yt|Y<t = y<t), where y<t denotes for the first t − 1 words in y. Sometimes, the generative model also depends on other context, e.g., the context from the source sentence for machine translation. To study the optimization of the word embeddings, we simply consider the generation of a word as a multi-class classification problem and formally describe the optimization as follows.
Consider a multi-class classification problem withM samples. Let hi denote the hidden state before the softmax layer which can be also considered as the input features, i = 1, · · · ,M . Without any loss of generality, we assume hi is not a zero vector for all i. Let N denote the vocabulary size. The conditional probability of yi ∈ {1, · · · , N} is calculated by the softmax function: P (Yi = yi|hi) = exp(〈hi,wyi 〉)∑N l=1 exp(〈hi,wl〉) , where wl is the embedding for word/category l, l = 1, 2, · · · , N .

heading: 4.1 EXTREME CASE: NON-APPEARED WORD TOKENS
text: Note that in most NLP tasks, the frequencies of rare words are rather low, while the number of them is relatively large. With stochastic training paradigm, the probabilities to sample a certain infrequent word in a mini-batch are very low, and thus during optimization, the rare words behave similarly to a non-appeared word. We first consider the extreme case of non-appeared word in this section and extend to a more general and realistic scenario in the next section.
We assume yi 6= N for all i. That is, the N -th word with embedding wN does not appear in the corpus, which is the extreme case of a low-frequency rare word. We focus on the optimization
process of wN and assume all other parameters are fixed and well-optimized. By log-likelihood maximization, we have
max wN
1
M M∑ i=1 log exp(〈hi, wyi〉)∑N l=1 exp(〈hi, wl〉) . (1)
As all other parameters are fixed, this is equivalent to
min wN
1
M M∑ i=1 log(exp(〈hi, wN 〉) + Ci), (2)
where Ci = ∑N−1 l=1 exp(〈hi, wl〉) and can be considered as some constants. Definition 1. We say that vector v is a uniformly negative direction of hi, i = 1, · · · ,M , if 〈v, hi〉 < 0 for all i.
The following theorem provides a sufficient condition for the embedding wN approaching unbounded during optimization. We leave the proof of all the theorems in the appendix. Theorem 1. A. If the set of uniformly negative direction is not empty, it is convex. B. If there exists a v that is a uniformly negative direction of hi, i = 1, · · · ,M , then the optimal solution of Eqn. 2 satisfies ‖ w∗N ‖=∞ and can be achieved by setting w∗N = limk→+∞ k · v.
From the above theorem, we can see that if there exists a set of uniformly negative direction, the embedding wN can be optimized along any uniformly negative direction to infinity. As the set of uniformly negative direction is convex, wN is likely to lie in a convex cone and move to infinity during optimization. Next, we provide a sufficient and necessary condition for the existence of the uniformly negative direction. Theorem 2. There exists a v that is a uniformly negative direction of a set of hidden states, if and only if the convex hull of the hidden states does not contain the origin.
Discussion on whether the condition happens in real practice From the theorem, we can see that the existence of the uniformly negative direction is highly related to the structure of the hidden states, and then affects the optimization of word embeddings. Note that a common trick used in sequence generation tasks is layer normalization (Ba et al., 2016; Vaswani et al., 2017; Merity et al., 2018), which first normalizes each hidden state vector into standard vector2, and then rescales/translates the standard vector with scaling/bias term. In the appendix, we show that under very mild conditions, the space of hidden states doesn’t contain the origin almost for sure in practice.

heading: 4.2 EXTENSION TO RARELY APPEARED WORD TOKENS
text: In the previous section, we show that under reasonable assumptions, the embeddings of all nonappeared word tokens will move together along the uniformly negative directions to infinity. However, it is not realistic that there exist non-appeared word tokens and the weights of embedding can be trained to be unbounded with L2 regularization term. In this section, we extend our analysis to a more realistic setting. The key we want to show is that the optimization of a rarely appeared word token is similar to that of non-appeared word tokens. Following the notations in the previous section, we denote the embedding of a rare word as wN and fix all other parameters. We study the optimization for this particular token with the negative log-likelihood loss function.
To clearly characterize the influence of wN to the loss function, we divide the loss function into two pieces. Piece AwN contains the sentences that do not contain wN , i.e., all hidden states in such sentences are independently of wN and the ground truth label of each hidden state (denoted as w∗h) is not wN . Then wN can be considered as a “non-appeared token” in this set. Denote the space of the hidden state in piece AwN as HAwN with probability distribution PAwN , where HAwN and PAwN can be continuous. The loss function on piece AwN can be defined as
LAwN (wN ) = − ∫ HAwN log exp(〈h,w∗h〉)∑N l=1 exp(〈h,wl〉) dPAwN (h), (3)
2the mean and variance of the values of the vector are normalized to be 0 and 1 respectively
which is a generalized version of Eqn. 1. Piece BwN contains the sentences which contain wN , i.e., wN appears in every sentence in piece BwN . Then in piece BwN , in some cases the hidden states are computed based on wN , e.g., when the hidden state is used to predict the next token after wN . In some other cases, the hidden states are used to predict wN . Denote the space of the hidden state in piece BwN asHBwN with probability distribution PBwN . The loss function on piece BwN can be defined as
LBwN (wN ) = − ∫ HBwN log exp(〈h,w∗h〉)∑N l=1 exp(〈h,wl〉) dPBwN (h), (4)
Based on these notations. the overall loss function is defined as
L(wN ) = P (sentence s in AwN )LAwN (wN ) + P (sentence s in BwN )LBwN (wN ). (5)
The loss on piece AwN is convex while the loss on piece BwN is complicated and usually nonconvex with respect to wN . The general idea is that given the fact that LAwN (wN ) is a convex function with nice theoretical properties, if P (sentence s in AwN ) is large enough, e.g., larger than 1− , and LBwN (wN ) is a bounded-smooth function. The optimal solution of L(wN ) is close to the optimal solution of LAwN (wN ) which can be unique if LAwN (wN ) is strongly-convex. A formal description is as below. Theorem 3. Given an α-strongly convex function f(x) and a function g(x) that satisfies its Hessian matrix H(g(x)) −βI , where I is the identity matrix, and |g(x)| < B. For a given > 0, let x∗ and x∗ be the optimum of f(x) and (1 − )f(x) + g(x), respectively. If < αα+β , then ‖ x∗ − x∗ ‖22≤ 4 Bα− (α+β) .
We make some further discussions regarding the theoretical results. In natural language generation, for two low-frequency wordsw andw′, pieceAw andAw′ has large overlaps. Then the loss LAw(w) and LAw′ (w
′) are similar with close optimum. According to the discussion above, the learnt word embedding of w and w′ is likely to be close to each other, which is also observed from the empirical studies.

heading: 5 ADDRESSING THE PROBLEM
text: In this section, we propose an algorithm to address the representation degeneration problem. As shown in the previous study, the learnt word embeddings are distributed in a narrow cone in the Euclid space which restricts the expressiveness of the representation. Then a straightforward approach is to improve the aperture of the cone which is defined as the maximum angle between any two boundaries of the cone. For the ease of optimization, we minimize the cosine similarities between any two word embeddings to increase the expressiveness.
For simplicity, we denote the normalized direction ofw as ŵ, ŵ = w‖w‖ . Then our goal is to minimize∑ i ∑ j 6=i ŵi
T ŵj as well as the original log-likelihood loss function. By introducing hyperparameter γ to trade off the log-likelihood loss and regularization term, the overall objective is,
L = LMLE + γ 1
N2 N∑ i N∑ j 6=i ŵi T ŵj . (6)
We call this new loss as MLE with Cosine Regularization (MLE-CosReg). In the following, we make some analysis about the regularization term.
Denote R = ∑N i ∑N j 6=i ŵi
T ŵj , and denote the normalized word embedding matrix as Ŵ = [ŵ1, ŵ2, ..., ŵN ]
T . It is readily to check the regularizer has the matrix form as R =∑N i ∑N j 6=i ŵi T ŵj = ∑N i ∑N j ŵi T ŵj − ∑N i ‖ ŵ ‖2= Sum(ŴŴT ) − N , where the Sum(·) operator calculates the sum of all elements in the matrix. Since N is a constant, it suffices to consider the first term Sum(ŴŴT ) only.
Since ŴŴT is a positive semi-definite matrix, all its eigenvalues are nonnegative. Since ŵi is a normalized vector, every diagonal element of ŴŴT is 1. Then the trace of ŴŴT , which is also the sum of the eigenvalues, equals to N .
As the cosine similarities between the word embeddings are all positive. According to Theorem 4, when ŴŴT is a positive matrix, we have the largest absolute eigenvalue of ŴŴT is upper bounded by Sum(ŴŴT ). Then minimizingR is equivalent to minimize the upper bound of the largest eigenvalue. As the sum of all eigenvalues is a constant, the side effect is to increase other eigenvalues, consequently improving the expressiveness of the embedding matrix.
Theorem 4. (Merikoski, 1984) For any matrix A, which is a real and nonnegative n × n matrix. The spectral radius, which is the largest absolute value of A’s eigenvalues, is less than or equals to Sum(A).

heading: 6 EXPERIMENTS
text: We conduct experiments on two basic natural language generation tasks: language modeling and machine translation, and report the results in this section.

heading: 6.1 EXPERIMENTAL SETTINGS

heading: 6.1.1 LANGUAGE MODELING
text: Language modeling is one of the fundamental tasks in natural language processing. The goal is to predict the probability of the next word conditioned on previous words. The evaluation metric is perplexity. Smaller the perplexity, better the performance. We used WikiText-2 (WT2) corpus, which is popularly used in many previous works (Merity et al., 2017; Inan et al., 2017; Grave et al., 2017). WikiText-2 is sourced from curated Wikipedia articles and contains approximately a vocabulary of over 30,000 words. All the text has been tokenized and processed with the Moses tokenizer (Koehn et al., 2006). Capitalization, punctuation and numbers are retained in this dataset.
AWD-LSTM (Merity et al., 2018) is the state-of-the-art model for language modeling. We directly followed the experimental settings as in Merity et al. (2018) to set up the model architecture and
hyperparameter configurations. We used a three-layer LSTM with 1150 units in the hidden layer and set the size of embedding to be 400. The ratio for dropout connection on recurrent weight is kept the same as Merity et al. (2018). We trained the model with Averaged Stochastic Gradient Descent. Our implementation was based on open-sourced code3 by Merity et al. (2018). For our proposed MLE-CosReg loss, we found the hyperparameter γ is not very sensitive and we set it to 1 in the experiments. We added neural cache model (Grave et al., 2017) to further reduce perplexity.

heading: 6.1.2 MACHINE TRANSLATION
text: Machine Translation aims at mapping sentences from a source domain to a target domain. We focus on English→ German and German→ English in our experiments. We used the dataset from standard WMT 2014, which consists of 4.5 million English-German sentence pairs and has been widely used as the benchmark for neural machine translation (Vaswani et al., 2017; Gehring et al., 2017). Sentences were encoded using byte-pair encoding (Sennrich et al., 2016), after which we got a shared source-target vocabulary with about 37000 subword units. We measured the performance with tokenized case-sensitive BLEU (Papineni et al., 2002).
We used state-of-the-art machine translation model Transformer (Vaswani et al., 2017), which utilizes self-attention mechanism for machine translation. We followed the setting in Vaswani et al. (2017) and used the official code (Vaswani et al., 2018) from Transformer. For both English → German and German → English tasks, we used the base version of Transformer (Vaswani et al., 2017), which has a 6-layer encoder and 6-layer decoder, the size of hidden nodes and embedding are set to 512. For English→ German task, we additionally run an experiment on the big version of Transformer, which has 3x parameters compared with the base variant. All the models were trained with Adam optimizer, and all the hyperparameters were set as default as in Vaswani et al. (2017). γ is set to 1 as in the experiments of language modeling.

heading: 6.2 EXPERIMENTAL RESULTS
text: We present experimental results for language modeling in Table 1 and machine translation in Table 2.
For language modeling, we compare our method with vanilla AWD-LSTM (Merity et al., 2018) in three different settings, without finetune, with finetune and with further continuous cache pointer. Our method outperforms it with 0.8/1.7/2.0 improvements in terms of test perplexity. For machine translation, comparing with original base Transformer (Vaswani et al., 2017), our method improves performance with 1.08/0.93 for the English→ German and German→ English tasks, respectively, and achieves 0.54 improvement on the big Transformer.
Note that for all tasks, we only add one regularization term to the loss function, while no additional parameters or architecture/hyperparameters modifications are applied. Therefore, the accuracy improvements purely come from our proposed method. This demonstrates that by regularizing the similarity between word embeddings, our proposed MLE-CosReg loss leads to better performance.
3https://github.com/salesforce/awd-lstm-lm

heading: 6.3 DISCUSSION
text: The study above demonstrates the effectiveness of our proposed method in terms of final accuracy. However, it is still unclear whether our method has improved the representation power of learnt word embeddings. In this subsection, we provide a comprehensive study on the expressiveness of the model learnt by our algorithm.
For a fair comparison with the empirical study in Section 3, we analyze the word embeddings of our model on English→ German translation task. We project the word embeddings into 2-dimensional space using SVD for visualization. Figure 2(a) shows that the learnt word embeddings are somewhat uniformly distributed around the origin and not strictly in a narrow cone like in Figure 1(a). This shows that our proposed regularization term effectively expands word embedding space. We also compare the singular values for word embedding matrix of our learnt model and the baseline model, as shown in the Figure 2(b). According to the figure, trained with vanilla Transformer, only a few singular values dominate among all singular values, while trained with our proposed method, the singular values distribute more uniformly. Again, this demonstrates the diversity of the word embeddings learnt by our method.

heading: 7 CONCLUSION AND FUTURE WORK
text: In this work, we described and analyzed the representation degeneration problem in training neural network models for natural language generation tasks both empirically and theoretically. We proposed a novel regularization method to increase the representation power of word embeddings explicitly. Experiments on language modeling and machine translation demonstrated the effectiveness of our method.
In the future, we will apply our method to more language generation tasks. Our proposed regularization term is based on cosine similarity. There may exist some better regularization terms. Furthermore, it is interesting to combine with other approaches, e.g. (Gong et al., 2018), to enrich the representation of word embeddings.

heading: 8 ACKNOWLEDGEMENTS
text: This work was partially supported by National Basic Research Program of China (973 Program) (grant no. 2015CB352502), NSFC (61573026) and BJNSF (L172037). We would like to thank Zhuohan Li and Chengyue Gong for helpful discussions, and the anonymous reviewers for their valuable comments on our paper.

heading: A PROOFS
text: In this section, we add proofs of all the theorems in the main sections.
Theorem 1. A. If the set of uniformly negative direction is not empty, it is convex. B. If there exists a v that is a uniformly negative direction of hi, i = 1, · · · ,M , then the optimal solution of Eqn. 2 satisfies ‖ w∗N ‖=∞ and can be achieved by setting w∗N = limk→+∞ k · v.
Proof. The first part is straight forward and we just prove the second part. Denote v as any uniformly negative direction, and k as any positive value. We have limk→+∞ ∑M i=1 log(exp(〈hi, k · v〉) + Ci) = ∑M i=1 log(Ci). As ∑M i=1 log(Ci) is the lower bound of the objective function in Eqn. 2 and the objective function is convex, we have w∗ = limk→∞ k ·v is local optimum and also the global optimum. Note that the lower bound can be achieved only if 〈hi, wN 〉 approaches negative infinity for all i. Then it is easy to check for any optimal solution ‖ w∗N ‖=∞.
Theorem 2. There exists a v that is a uniformly negative direction of a set of hidden states, if and only if the convex hull of the hidden states does not contain the origin.
Proof. We first prove the necessary condition by contradiction. Suppose there areM hidden states in the set. If the convex hull of hi, i = 1, · · · ,M , contains the origin and there exists a uniformly negative direction (e.g. v). Then from the definition of convex hull, there exists αi, i = 1, · · · ,M , such that ∑M i αihi = 0, αi ≥ 0 and ∑ i αi = 1. Multiplying v on both sides, we have ∑ i αi〈hi, v〉 = 0, which contradicts with 〈hi, v〉 < 0 for all i. For the sufficient part, if the convex hull of hi, i = 1, · · · ,M , does not contain the origin, there exists at least one hyperplane H that passes through the origin and does not cross the convex hull. Then it is easy to check that a normal direction of the half space derived by the H is a uniformly negative direction. The theorem follows.
Theorem 3. Given an α-strongly convex function f(x) and a function g(x) that satisfies its Hessian matrix H(g(x)) −βI , where I is the identity matrix, and |g(x)| < B. For a given > 0, let x∗ and x∗ be the optimum of f(x) and (1 − )f(x) + g(x), respectively. If < αα+β , then ‖ x∗ − x∗ ‖22≤ 4 Bα− (α+β) .
Proof. We first prove the function (1− )f(x) + g(x) is α− (α+ β)-strongly convex. Let’s consider the Hessian matrix of it. As f(x) is α-strongly convex and H(g(x)) −βI , using the definition of positive-definite matrix, the following inequality holds:
∀v, vT (H(g) + βI)v > 0; (7) vT (H(f)− αI)v > 0. (8)
To make it clear, we omit x here. Then for the Hessian matrix of (1− )f(x) + g(x), we have:
∀v, vT (H((1− )f + g)− (α− (α+ β))I)v (9) = vT (H((1− )f) + H( g)− (1− )αI + βI)v (10) = vT ((1− )H(f) + H(g)− (1− )αI + βI)v (11) = vT ((1− )(H(f)− αI) + (H(g) + βI))v (12) = vT ((1− )(H(f)− αI))v + vT ( (H(g) + βI))v (13) = (1− )vT (H(f)− αI)v + vT (H(g) + βI)v (14) > (1− )0 + 0 (15) = 0. (16)
Thus, H((1− )f(x)+ g(x))−(α− (α+β))I is positive-definite, which means (1− )f(x)+ g(x) is α− (α+ β)-strongly convex. Then, with the properties in strong convexity, we have:
‖ x∗ − x∗ ‖22 ≤ 2
α− (α+ β) (f(x∗) + g(x∗)− f(x∗ )− g(x∗ )) (17)
≤ 2 α− (α+ β) ( g(x∗)− g(x∗ )) (18)
≤ 4 B α− (α+ β) . (19)

heading: B COMPUTATION OF THE COSINE REGULARIZATION
text: In this section, we provide analysis of the computational cost of the proposed regularization term.
Proposition 1. The cosine regularization in Eqn. 6 can be computed in Θ(N) time where N is the size of vocabulary.
Proof. The regularization term can be simplified as below:
N∑ i N∑ j 6=i ŵTi ŵj = ( N∑ i ŵi) T ( N∑ j ŵj)− N∑ i ŵTi ŵi (20)
= ( N∑ i ŵi) T ( N∑ i ŵi)−N (21)
= || N∑ i ŵi||22 −N. (22)
From the above equations, we can see that we only need to compute the sum of all the normalized word embedding vectors, and thus the computational time is linear with respect to the vocabulary size N .

heading: C DISCUSSION ON LAYER NORMALIZATION
text: In this section, we show the condition on the existence of the uniformly negative direction holds almost for sure in practice with models where layer normalization is applied before last layer.
Let h1, h2, · · · , hn be n vectors in Rd Euclidean space. Let −→ 1 / −→ 0 be the d-dimensional vector filled with ones/zeros respectively. By applying layer normalization we have:
µi = 1
d
−→ 1 Thi, (23)
σ2i = 1
d ‖ hi −
−→ 1 µi ‖22, (24)
h′i = g hi −
−→ 1 µi
σi + b, (25)
where µi and σ2i are the mean and variance of entries in vector hi, g and b are learnt scale/bias vectors and denotes the element-wise multiplication. Here we simply assume that σ2i and each entry in g and b are not zero (since the exact zero value can be hardly observed using gradient optimization in real vector space). If the convex hull of h′1, h ′ 2, · · · , h′n contains the origin, then there exist λ1, λ2, · · · , λn, such that: n∑ i=1 λih ′ i = −→ 0 ; n∑ i=1 λi = 1;λi ≥ 0,∀i = 1, 2, · · · , n. (26)
By combining 25 and 26 we have: n∑ i=1 λih ′ i = n∑ i=1 λi(g hi − −→ 1 µi σi + b) (27)
= b + n∑ i=1 λi(g hi − −→ 1 µi σi ) (28)
= b + g n∑ i=1 λi hi − −→ 1 µi σi = −→ 0 . (29)
Denote bg = ( b1 g1 , b2g2 , · · · , bd gd ), thus we have ∑n i=1 λi hi− −→ 1 µi σi = − bg . Since −→ 1 T hi− −→ 1 µi σi = 0 for all i, there exist λ1, λ2, · · · , λn that satisfy Eqn. 26 only if −→ 1 T bg = − −→ 1 T ∑n i=1 λi hi− −→ 1 µi σi =
− ∑n i=1 λi −→ 1 T hi− −→ 1 µi σi
= 0, which can hardly be guaranteed using current unconstrained optimization. We also empirically verify this.

heading: D (SUB)WORD FREQUENCY DISTRIBUTION ON WMT2014 ENGLISH-GERMAN AND WIKITEXT 2 DATASETS
text: In this section, we show the (sub)word frequency distribution on the datasets we use in experiments in the Figure 3.

Review summaries:
This work proposes a simple regularization term which penalize cosine similarity of word embedding parameters in the loss function. The motivation comes from empirical studies of word embedding parameters in three tasks, translation, word2vec and classification, and showed that the parameters for the translation task are not distributed when compared with other tasks. The problem is hypothesized by the rare word problem especially when parameters are tied for softmax and input embedding, and proposes a cosine similarity regularization. Experiments on English/German show consistent gains over non-regularized loss.