Learning Compact Neural Word Embeddings by Parameter Space Sharing

1 Introduction

Machine readable representations that embed word meanings are important tools for tackling natural language understanding by computers. Many researchers have tried to preserve the word meaning into vector space models. The basic idea for constructing a vector space model is taken from the intuition that similar words tend to appear in similar contexts [Miller and Charles, 1991]. Within this traditional framework, recently developed new methodologies, which are inspired by neural network language models, such as vector log-bilinear language (vLBL) models, SkipGram and continuous bag-of-words (CBoW), have successfully been proven to capture high quality syntactic and semantic relationships in a vector space [Mnih and Kavukcuoglu, 2013; Mikolov et al., 2013a; 2013b]. Moreover, the 'word embedding vectors' obtained from these methods are now being applied to many tasks, such as syntactic and semantic parsing of text, sentiment analysis, machine translation, and question answering, in many different ways. For example, embedding vectors are incorporated as additional features for training machine leaning-based models, i.e., [Turian et al., 2010;

Guo et al., 2014], and as initialization parameters of neural network-based methods, i.e., [Hinton and Salakhutdinov, 2012; Chen and Manning, 2014; Liu et al., 2014]. As demonstrated in the above previous studies, word embedding vectors can significantly improve task performance. Moreover, studies in compositional semantics area reveal that the calculations underlying embedding vectors such as addition and inner product can be seen as good approximations of composed word meaning and evaluating the similarity between words, respectively. The obtained word embedding vectors have now become an important fundamental resource for tackling many applications in the AI field.

According to this background, improvements in neural word embedding methods will strongly support the advancement of AI research. Among many directions for various improvements, this paper focuses on the fact that the model size of a set of high-quality embedding vectors in memory space is mostly large, i.e., more than 1GB. In fact, the model size of the freely-available pre-trained embedding vectors trained by CBoW with approximately 100 billion words from the Google News data (GN100B) exceeds 3GB 1 , while that trained by GloVe [Pennington et al., 2014] with approximately 840 billion words of Common Crawl data occupies 2.5GB 2 . Model sizes are so large that the application of embedding vectors becomes problematic, particularly on limited memory devices, such as mobile devices. Thus, this paper tackles this issue, and proposes a method that can provide 'compact' sets of embedding vectors for the purpose of enhancing 'usability' in actual application.

The basic idea of our proposal is to incorporate parametersharing constraints into the optimization problem. These additional constraints force the embedding vectors to share parameter values, which significantly shrinks model size. This paper also proposes an efficient learning algorithm based on dual decomposition and ADMM techniques [Boyd et al., 2011] for optimizing the optimization problem with our parameter sharing constraints.

2 Neural Word EmbeddingMethod

At first, we define the following terms to reducing misunderstanding.

1 https://code.google.com/archive/p/word2vec/

2 http://nlp.stanford.edu/projects/glove/

Definition 1 (neural word embedding method). One of the simplest neural language models, it consists of only 'input' and 'output' embedding layers.

Examples of neural word embedding methods are SkipGram, CBoW and the family of vLBL models.

Definition 2 (word embedding vector). Vectors generated by any neural word embedding method.

2.1 Model definition

Let U and V be two sets of predefined vocabularies of possible input and output words, respectively. In this paper, the absolute value of set, i.e., ♣U♣ and ♣V♣, denotes the number of instances in the corresponding set. Generally, a neural word embedding method assigns a D-dimensional vector to each word in U and V.

Let ei represent the i-th input embedding vector, and oj represent the j-th output embedding vector. In the rest of this paper, notation 'i' is always used as the index of input embedding vectors, and 'j' as the index of output embedding vectors for convenience, where 1  i  ♣U♣ and 1  j  ♣V♣.

Definition 3 (input and output embedding vector [Suzuki and Nagata, 2015]). This paper refers to a vector assigned to a word in U as an 'input embedding vector', and that assigned to a word in V as an 'output embedding vector'.

This paper mainly follows the vLBL model definition [Mnih and Kavukcuoglu, 2013]'. This is because this definition covers several famous models, such as SkipGram, continuous bag-of-words (CBow) [Mikolov et al., 2013a], and GloVe [Pennington et al., 2014]. Let W be context window size before and after the word in the target position. If we set W = 5, the five words before and after the target position become the context (input) words of the word in the target position. Let z represent the distance between appearance of the i-th input word and the j-th output word in training data. Let rz denote a scaling (or decay) factor with respect to distance z. Suppose that single training data H in D consists of series of indices of input words with distance (i↪ z), and an index of output word. Namely, H = (I↪ j), where I is a list of (i↪ z), that are extracted within the context window. Then, the likelihood of the appearance of the j-th output word given the input words within W in D is estimated by the following form of the vLBL model 3 :

This model becomes identical to CBoW if we set rz constant regardless of distance z, such as rz =1 for all z.

Moreover, the SkipGrammodel emerges if all I consist of just one instance:

2.2 Optimization problem for embedding

Let E and O represent lists of all input and output embedding vectors, respectively. Namely, E = (ei)♣U♣ i=1 and O =

3 To simplify the discussion, we ignore bias terms in this paper.

(oj )♣V♣ j=1 4 . D represents training data. Given the above, embedding vectors are obtained by solving the following form of minimization problem:

where represents an objective function, and ˆE and ˆO are lists of solution vectors.

For example, the objective function of 'SkipGram with negative sampling (SGNS)' can be written as follows:

where L(x) represents a logistic loss function, namely, L(x) = log(1 + exp(-x)), and sH is that shown in Eq. (2). Moreover, D0 denotes the explicit representation of negative sampling data. To simplify the discussion, we assume that D0 is automatically generated based on the distribution of D as described in the original paper [Mikolov et al., 2013b]. Note that 'CBoWwith negative sampling' also takes the same form as Eq. (4) except for the definition of sH, which is Eq. (1) instead of Eq. (2).

3 Embedding with Parameter Space Sharing

This section explains our proposed method. The main purpose of our method is to obtain a 'compact' set of embedding vectors in order to significantly reduce the model size and thus support real-world applications.

3.1 Preparation

To explain the details of our method, we introduce a few definitions and assumptions used through this paper.

Definition 4 (vector concatenation operator ⊙). Let v be n-dimensional vector v = (v1↪ ▷ ▷ ▷ ▷vn), and w be mdimensional vector w = (w1↪ ▷ ▷ ▷ ↪wm). Then, we define ⊙ as an operator that concatenates two vectors. Namely, v ⊙ w = x, where x is (n + m)-dimensional vector x = (v1↪ ▷ ▷ ▷ ↪ vn↪ w1↪ ▷ ▷ ▷ ↪ wm).

We also use a big operator JBb=1 vb, which is a short notation of concatenating multiple vectors from b = 1 to b = B, that is, v1 ⊙ v2 ⊙ · · · ⊙ vB = JBb=1 vb 5 .

Definition 5 (Block-splitting sub-vector). If ei = JBb=1 ei↪b, we refer to ei↪b for all (i↪ b) as 'block-splitting sub-vectors' of ei, where ei↪b denotes the b-th block of the i-th input embedding vector.

Assumption 6. Our method assumes that all embedding vectors are equally split into B-blocks of C-dimensional blocksplitting sub-vectors. Therefore, the relation D = B ⇥ C always holds.

4 The notation (ei)♣U♣ i=1 is a short notation of a list of vectors (e1↪ · · · ↪ e♣U♣) = (ei)♣U♣ i=1 .

5 This is similar to the notation of set union SBb=1 Ab = A1 [ A1 · · · [ AB ✓ A when Ab for all b are the subsets of A.

In other word, we assume that all block-splitting subvectors have dimension of C. For example, we get D = 256, C = 8 and B = 32 if we split an embedding vector, whose dimension is 256, into 32-blocks of 8-dimensional blocksplitting sub-vectors.

Definition 7 (reference vector). We define special vectors for explaining our parameter sharing approach as 'reference vectors for parameter sharing', or 'reference vectors' for short, to distinguish them from other vectors.

Assumption 8. The dimension of the reference vectors is determined in accordance with that of the block-splitting subvectors of embedding vectors. More precisely, the dimension of the reference vectors is C if the dimension of the blocksplitting sub-vectors is defined as C.

3.2 Basic idea

To simplify the discussion, this section explains our idea for just input embedding vector ei.

The basic idea of our method is as follows. First, we introduce and assign a limited number of reference vectors to each block of block-splitting vectors. For example, the number of reference vectors becomes K⇥B if we assign K reference vectors to each block. Let pb↪k denote the k-th reference vector assigned to the b-th block, and Pb = (pb↪k)Kk=1 . Similarly, P denotes a list of all the reference vectors assigned to all the blocks, that is, P = (Pb)Bb=1 . Then, in our method, we add the constraints that every block-splitting sub-vector ei↪b matches one of the reference vectors in Pb during the parameter estimation of embedding vectors. This also means that we force every embedding vector to be represented by the concatenation (combination) of the reference vectors. As a result, we can significantly reduce the model size since embedding vectors can be restored from just a set of reference vectors with selection information.

3.3 Memory requirement

Neural word embedding methods like SkipGram and CBoW generate ♣U♣ input embedding vectors, each has dimension of D. Therefore, we need ♣U♣⇥D⇥F-binary digits ('bits' for short) to store the complete embedding vectors in memory (or storage), where F denotes the bits required to represent a real value in the computer, i.e., F =64 in the case of double precision floating-point. Hereafter, we assume the use of single precision floating-point F =32 following it adoption by the famous word2vec implementation.

As we described, all reference vectors have dimension of C, and the number of reference vectors is predefined as K⇥B. Thus, C⇥K⇥B⇥F-bits are required to store the reference vectors in memory. Next, we need dlogKe-bits to represent the selection of reference vectors, namely, one of the integers from 1 to K. Thus, B⇥dlogKe-bits are required to represent a single embedding vector, and thus, ♣U♣ ⇥B⇥dlogKe-bits to represent all input embedding vectors. Finally, our method requires ♣U♣⇥B⇥dlogKe +C⇥K⇥B⇥F-bits in total.

Table 1 shows model sizes obtained in typical settings. Note that our method also considers output embedding vectors as well as input embedding vectors.

Table 1: Comparison of obtained model size between a conventional method and proposed method in typical settings.

typical conventional method: (♣U♣ + ♣V ♣) ⇥ D ⇥ F -bits

400,000 400,000 256 32

♣U ♣

♣V♣ D F total (MB)

781MB

400,000 400,000 512 32 1,565MB

2,000,000 2,000,000 256 32 3,906MB

2,000,000 2,000,000 512 32 7,813MB

proposed method: (♣U♣ + ♣V ♣)⇥B⇥dlogKe+C⇥K⇥B⇥F-bits

3.4 Formulation

Following the assignment of pb↪k for input embedding vector, let qb↪k denote the k-th reference vector assigned to the b-th block of the output embedding vector. Moreover, similar to Pb and P, we define Qb = (qb↪k)Kk=1 and Q= (Qb)Bb=1 . Then, we define the following minimization problem for obtaining embedding vectors with the parameter sharing property:

where ei = JBb=1 ei↪b 8i and oj = JBb=1 oj↪b 8j. The difference between Eqs. (3) and (5) is obvious: our proposed optimization problem shown in Eq. (5) has additional (parameter sharing) constraints.

Definition 9 (parameter sharing constraint). The constraints shown in Eq. (5), namely ei↪b 2 Pb and oj↪b 2 Qb are referred to as parameter sharing constraints in this paper. The meaning of constraint e 2 P is that vector e must take values equivalent to one of the vectors in P. That is, 9k e = pk, where P = ¶pk♦Kk=1 .

Our proposed method does not rely on the form of the loss function (E↪O♣D) if the loss function is valid for neural word embedding. We assume that the loss function in Eq. (5) is one of those used in the conventional neural embedding methods, i.e., Eq. (1).

3.5 Optimization algorithm

We have several possible approaches for optimizing Eq. (5). This paper introduces an efficient algorithm based on the dual decomposition technique.

At first, we introduce vector representations of auxiliary variables ui and vj. Similar to E and O, U and V denote U = (ui)♣U♣ i=1 and V = (vj)♣V♣ j=1 , respectively. Based on the dual decomposition technique [Everett, 1963], we reformulate Eq. (5) by incorporating equivalence constraints, ei = ui for all i and oj = vj for all j, into the optimization problem to detach ei and oj from the 'parameter sharing constraints':

where ui = JBb=1 ui↪b 8i and vj = JBb=1 vj↪b 8j. Note that Eqs. (5) and (6) are basically equivalent problems.

Then, to relax the equivalence conditions ei = ui and oj = vj, we apply an augmented Lagrangian method [Hestenes, 1969; Powell, 1969]. The optimization problem in Eq. (6) can be transformed into the following form:

Objective function Φ takes the following form:

where ↵i and βj represent Lagrange multipliers (or dual variables), and A = (↵i)♣U♣ i=1 and B = (βj)♣V♣ j=1 . Moreover, ⇢ is a tunable parameter to control the strength of constraint satisfaction during parameter estimation, where ⇢>0.

Unfortunately, the joint optimization of Eq. (8) over all parameter sets is a hard problem. Thus, we leverage the 'alternating direction method of multiplier (ADMM)' algorithm [Gabay and Mercier, 1976; Boyd et al., 2011], as it provides an efficient optimization framework to solve problems in dual decomposition form like Eq. (8). The notable characteristic of ADMM is that it virtually decomposes the original optimization problem into several sub-problems, whose optimization variables are a (disjoint) subset of the original optimization variables. It sequentially and iteratively solves the sub-problems over the selected variable set while holding the other variables fixed. Detailed derivation for the general case can be found in [Boyd et al., 2011]. Fig. 1 shows our sequential and iterative parameter update procedure derived from the ADMM framework as applied to Eq. (8).

Step1: If we discard all the terms that are independent from original optimization variables E and O, the objective function Φ in Eq. (8) can be rewritten as follows:

where e0i = ui - 1⇢ ↵i and o0j = vj - 1⇢ βj. Obviously, the minimization problem in Eq. (9) with Φ1 in Eq. (12) can be viewed as a conventional neural word embedding method with 'shifted' L2-norm regularizers. Therefore, this optimization problem can be solved by gradient-based algorithms widely used in conventional neural word embedding methods, such as SGD or its variants.

Step2: If we discard all the terms that are independent from auxiliary variables U, V, P and Q, we can further separate the sub-problem into two distinct parts (U↪P) and (V↪Q). Thus, the objective functions Φ2↪U and Φ2↪V in Eq. (10) can Step1: Find the minimizer of Eq. (7) using only 'original optimization variables', E and O, while holding all the other variables, U, V, P, Q, A and B in Eq. (7), fixed.

Step2: Find the minimizer of Eq. (7) using only 'auxiliary variables', U V, P and Q, with the parameter sharing constraints while holding all other variables, E, O, A and B, fixed:

Step3: Perform one step of gradient ascent procedure for the dual variables A and B while holding all other variables, E, O, U, V, P and Q, fixed:

Figure 1: Our sequential and iterative parameter update procedure derived from the ADMM framework.

be written as follows:

where u0i↪b = ei↪b + 1⇢ ↵i↪b and v0j↪b = oj↪b + 1⇢ βj↪b, respectively. Note that Pi ku0i - uik22 = Pi Pb ku0i↪b - ui↪bk22 .

We can further transform objective functions Φ2↪U and Φ2↪V in Eq. (13) by combining the parameter sharing constraints into the objective function. Finally, we obtain the following objective functions:

as the replacements of Φ2↪U and Φ2↪V that include their constraints. Interestingly, both equations shown in Eq. (14) match the form of the objective function used as a standard k-means clustering problem. We can easily obtain a local optimum (or stationary point) by simply applying a standard k-means clustering algorithm.

Step3: In the ADMM framework, dual variables are generally updated by one step of gradient ascent to tighten the constraints ei=ui and oj =vj, that is,

where ⇠ represents the learning rate of the gradient ascent method.

4 Experiments

We followed the experimental settings used in a series of neural word embedding papers. First, our training data was

Table 3: Hyper-parameters selected in our experiments and their candidate parameter sets.

¶1↪ 2↪ 5↪ 10↪ 15♦

taken from a Wikipedia dump (Aug. 2014). We used the hyperwords tool 6 for data preparation [Levy et al., 2015]. Finally, we obtained approximately 1.6 billion tokens of training data D. We selected 400,000 most frequent words in the training data as vocabularies of input and output words (♣U♣ = ♣V♣ = 400↪ 000).

Table 2 summarizes the benchmark datasets used in our experiments. We prepared three types of linguistic benchmark tasks: word similarity (WordSim), word analogy (Analogy), and sentence completion (SentComp). The 'OOV' column represents the number of words (problems) in each benchmark data that were out of vocabulary relative to our training data. Thus, these numbers also indicate the number of problems that are impossible to solve correctly in our experiments.

4.1 Methods for comparing in our experiments

We selected SGNS as the baseline method since this is one of the most famous methods and is known to work well in many situations [Levy et al., 2015]. We used the word2vec implementation but modified the code to save the context vectors as well as the word vectors 7 . Many tunable hyper-parameters were set based on the recommended default values or suggested values explained in [Levy et al., 2015]. Table 3 summarizes the hyper-parameters used consistently in all our experiments unless otherwise noted (See [Levy et al., 2015] for details of in Table 3). Moreover, we selected ⇠=0▷01, and ⇢=1▷0 for hyper-parameters of our proposed method.

6 https://bitbucket.org/omerlevy/hyperwords

7 https://code.google.com/p/word2vec/ (trunc42)

For a fair evaluation, we also examined two naive methods that can reduce the model size of embedding vectors.

1. m-bit quantization: After obtaining the embedding vectors, we calculate the minimum and maximum values of every coordinate independently, and then evenly quantize the interval between minimum and maximum values into 2m-bins.
2. block-wise k-means clustering 8 : We applied k-means clustering with exactly the same setting as the procedure of Step2 shown in Eq. (14).

These two methods can be categorized as post-processing for model size reduction.

8 Note that simple vector-wise k-means clustering does not work for the purpose of model size reduction.

4.2 Task performance vs. model size

It is worth emphasizing here that our proposed method, which we refer to as 'PS-SGNS', is not intended to improve task performance. Our goal for PS-SGNS is to reduce the model size as much as possible while maintaining the task performance of the baseline method, SGNS.

Baseline results with different model size (dimension)

We first evaluated the impact of dimension D since it deeply affect to both performance and model size of our baseline method, SGNS. Table 4 shows the results. In our setting, D=512 provided the best results. Thus, we selected 'SGNS with D=512' as the base setting of our method, PS-SGNS.

Comparison with original SGNS

Table 5 summarizes our main results. Moreover, Table 6 shows results of individual benchmark datasets. PS-SGNS with 'K = 16↪B = 256' had successfully reduces the model size nearly 16-fold compared to SGNS while generally matching SGNS task performance. In addition, the model size of PS-SGNS with 'K = 16↪ B = 64' was just 24MB, approximately 65 times smaller than that of original SGNS. Interestingly, the proposal still offered acceptable performance for WordSim and SentComp. Therefore, the embedding vectors obtained from PS-SGNS will be highly effective in applications running on limited memory devices. Analogy, on the other hand, seems to be very sensitive to model compaction. However, we emphasize that PS-SGNS provided significantly better results than all the baseline methods.

In addition, we note that our method easily manage CBoW and similar word embedding method instead of SGNS as a baseline method. We omit to show PS-CBoW results since the tendency and relation of CBoW and PS-CBoW were essentially the same as SGNS and PS-SGNS.

Comparison with SGNS with block-wise k-means

SGNS with the block-wise k-means post-processing method can be seen as a form of PS-SGNS. This is because SGNS with block-wise k-means post-processing essentially matches a single iteration of the ADMM-based algorithm shown in Fig. 1. Thus, comparing these two results roughly demonstrates the effectiveness of our method in terms of performing multiple iterations of ADMM updates. Obviously, multiple iterations significantly improved task performance. In addition, it is hard to prove that the proposed ADMM-based algorithm will converge to certain stationary point. This is because the original SGNS optimization problem is already a non-convex optimization problem. Therefore, these results provide empirical evidence that our ADMM-based algorithm has ability to find better solution by the iterative parameter update procedure.

5 RelatedWork

Several papers have recently attempted to reduce the model size of neural networks in deep learning settings (NN/DL), i.e., [Droniou and Sigaud, 2013; Chen et al., 2015; Gupta et al., 2015; Courbariaux et al., 2015]. The motivation and purpose of our method are exactly the same as those studies. However, the methods developed for NN/DL cannot be directly or straightforwardly used in word embedding methods (like SGNS) in most cases.

The first simple reason is that the target of most methods for NNs is to reduce the information of transformation matrices U in the transformation function o = f(Ue + b) since this part is generally the largest component of NNs. However, embedding methods like SGNS have no transformation matrices, U, in their models, namely, v = e · o. In addition, we emphasize that the problem for reducing the embedding vectors is much harder than that for NNs since the model capacity is already very limited. Moreover, the required properties are different. A simple example is provided by Analogy task. The embedding vectors are required to preserve the relation of angles and distances among all embedding vectors in the vector space. This basically is a very hard requirement. Based on these two reasons, our proposed method, PS-SGNS, seems to be much complicated compared to the methods used in NN/DL listed above.

Our ADMM-based algorithm essentially is an extension of our previous study [Suzuki and Nagata, 2014]. However, there is an essential difference between them. The method introduced in this paper is realized by the fact that each dimension of embedding vectors has no interpretable meaning, and thus, exchangeable.

6 Conclusion

This paper proposed a novel neural word embedding method that incorporates parameter sharing constraints during embedding vector learning. The embedding vectors obtained from our method strictly share the parameters in a certain predefined limited space. As a result, our method only needs to remember the set of shared parameters and selection information for recovering completely all embedding vectors; our approach can significantly reduce the model size. This paper also introduced an efficient learning algorithm based on the ADMM framework for solving the optimization problem with our parameter sharing constraints. Our experiments showed that SGNS with our parameter sharing constraints, which we call PS-SGNS, successfully reduced the model size by more than one order of magnitude while matching the task performance of the original SGNS.