Title: WORD EMBEDDING RE-EXAMINED: THEORETICAL ANALYSIS ABOUT WORD SIMILARITY AND ANALOGY STRUCTURE

Abstract: As observed in previous works, many word embedding methods exhibit two interesting properties: (1) words having similar semantic meanings are embedded closely; (2) analogy structure exists in the embedding space, such that "Paris is to France as Berlin is to Germany". We theoretically analyze the inner mechanism leading to these nice properties. Specifically, the embedding can be viewed as a low rank transformation from the word-context co-occurrence space to the embedding space. Such embedding transformation will preserve the relative distances among words. Furthermore, previous studies empirically observed that the parameter α has a strong influence on the performance of word embedding but did not provide theoretical explanation. We provide a theoretical explanation for this behavior, and derive a method to automatically find its optimal value. The experiments on real datasets verify our analysis.
1. What is the inner mechanism resulting in these two good properties of word embedding? 2. How does the parameter α influence the word embedding? Can we find a method to determine its optimal value?

1. INTRODUCTION:

Word embedding is a fundamental task in natural language processing. Many different approaches have been proposed, including LSA (Deerwester et al., 1990) , SGNS (Mikolov et al., 2013a; b) , GloVe (Pennington et al., 2014) and others. These methods have achieved huge success in information retrieval (Salton & Buckley, 1988) , entity recognition (Lample et al., 2016) , sentiment analysis (Socher et al., 2013) , machine translation (Sutskever et al., 2014 ) and so on. Previous studies have demonstrated three well-known facts about the word embedding: (1) Levy & Goldberg (2014b) showes many different kinds of word embeddings (e.g. SGNS) can be understood as the matrix factorization framework. For example, Levy & Goldberg (2014b) proves that SGNS is implicitly factorizing the shifted pointwise mutual information (PMI) matrix. (2) Mikolov et al. (2013b) ; Pennington et al. (2014) ; Levy et al. (2015) ; Tian et al. (2016) and other works observe that word embedding exhibits two nice properties: the word similarity such that words with similar semantic meanings are embedded closely in the embedding space, and the analogy structure such that "woman is to queen as man is to king". (3) Previous studies, including (Caron, 2001; Turney, 2012; Bullinaria & Levy, 2012; Levy et al., 2015; Artetxe et al., 2018) , empirically observe that α in word embedding E = U d • Σ α d1 has an important influence on the quality of word embedding. But these works did not provide theoretical explanation for this behavior of α or practical guide to set this parameter. In this paper, we show the word embedding can be understood as a low rank transformation process. Furthermore, we investigate the change of the relative distances between words which is the inner mechanism that leads to these two nice properties in the word embedding. Particularly, we find the parameter α has influence on the change of relative distance between words. Based on such analysis, we provide theoretical explanation the behavior of α and derive a method to automatically find its optimal value. To summarize, this research is motivated by two questions:

We make the following contributions in this paper:

• We reveal how the relative distances between words change during the embedding process which can be seen as a low rank transformation process. The nice properties of word embeddings are inherited from the original word-context co-occurrence matrix as the result of such low rank transformation.

• Compared with previous studies which empirically observed the influence of the parameter α on the word embedding, we theoretically explain the influence of parameter α on the word embedding by revealing it controls the change of relative distances between words.

Besides, we derive a method to automatically find its optimal value. We conduct experiments on real datasets to verify our ideas.

The following sections are organized as follows: section 2 introduces the background knowledge and necessary preliminaries; section 3 shows how the relative distances between words change during this linear transformation and it is the inner reason incurring these nice properties of word embedding. Based on such analysis, section 4 shows that symmetric factorization can be suboptimal and how to improve the word embedding model with asymmetric factorization. Section 5 contains the experiments on real datasets and section 6 discusses the related work. Finally, section ?? is the conclusion and describes a potential work.

2. BACKGROUND AND PRELIMINARIES:

The goal of word embedding is to find a good vector representation for every word in a corpus. As summarized in Yin & Shen (2018) , most existing word embedding methods can be formulated as low rank matrix approximations. So we can analyze the word embedding algorithms (e.g., SGNS) within the matrix factorization framework. Suppose M ∈ R n×n is the word-context matrix where M i,j represents some statistics between word w i and its context word w j . These word embedding algorithms are seeking a d-dimension word embedding matrix E ∈ R n×d accompanied with a context embedding matrix C ∈ R n×d to approximate the word-context matrix M , such that M ≈ EC T . The matrix M can have different forms due to the design of objective function in every embedding method. For example, M is the shifted pointwise mutual information matrix in the SGNS.

Explicitly performing singular value decomposition. This kind of methods can be summarized as follows. Firstly, a word-context matrix M is constructed to capture some co-occurrence statistics of every word and its context. For example, M can be the pointwise mutual information (PMI) matrix (Church & Hanks, 1990) , positive PMI (PPMI) matrix (Bullinaria & Levy, 2012) and Shifted PPMI (SPPMI) matrix (Levy & Goldberg, 2014b) . Then, SVD is used to factorize the word-context matrix Caron (2001) , Turney (2012), Bullinaria & Levy (2012), Levy et al. (2015) and Artetxe et al. (2018) discussed a more general approach which adds a parameter α to the truncated diagonal matrix Σ d and obtain the word embedding

M as M = U • Σ • V T .

= U d or E = U d • Σ d .

E = U d • Σ α d .

They observe α has an important influence on the embedding and suggest this parameter should be tuned. However, the reason is not theoretically clear and no clear method has been provided to tune α yet.

Implicitly performing matrix factorization. Recently, word embedding methods based on neural networks have been proposed (e.g., Bengio et al. (2003) ). Particularly, Mikolov et al. (2013a; b) proposed a popular word embedding approach SGNS based on the skip-gram with negative-sampling and it achieves the state-of-the-art results in different tasks. Besides, GloVe is another widely used word embedding method (Pennington et al., 2014) . While SGNS and GloVe learn word embeddings by optimizing some objective functions using stochastic gradient methods, it has been shown that these two methods are implicitly performing matrix factorizations. Specifically, Levy & Goldberg (2014b) showed SGNS is implicitly factorizing the shifted Pointwise Mutual Information matrix. Levy et al. (2015) showed the GloVe is implicitly factorizing the log-count word-context co-occurrence matrix. So these two neural network based embedding methods can also be formu-lated within the matrix factorization framework, and the parameter α equals to 0.5 as they are doing symmetric factorization of some word-context co-occurrence matrix M .

To summarize, same as the first assumption in Yin & Shen (2018) , our analysis assumes the word embeddings can be formulated as low rank matrix approximations, either explicitly or implicitly. Specifically, the embedding matrix E equals to U d • Σ α d where U d , Σ d and α are as defined before.

3 ANALYSIS: THE REASON WHY THE EMBEDDING EXHIBITS NICE

PROPERTIES:

Our start point is the relation between word embedding and matrix factorization. As mentioned in section 2, almost all word embedding methods can be formulated as explicit or implicit matrix factorization (e.g., SGNS is implicitly doing a symmetric factorization on the shifted pointwise mutual information matrix). We adopt the same notation in previous papers (Levy et al., 2015; Yin & Shen, 2018) to write M = U ΣV T as the SVD of some word-context co-occurrence matrix M . For example, M can be the pointwise mutual information matrix. 

EQUATION

)

The proof is in Appendix A.1.

Observation 1 reveals the process to compute E: (1) first multiplying the matrix V to the right side of M ; (2) then multiplying the diagonal matrix

Σ (1-α) pse on the intermediate result M V ; (3) finally removing the last n -d columns of M • V • Σ (α-1)

pse . The first step in this transformation process is a rotation because the matrix V is a unitary matrix. So the relative distances between words are not changed during the first transformation. In the second step, the matrix Σ pse is a diagonal matrix and it is multiplied on the right side of M V . So the second step scales every dimension of the rotated matrix. Because we keep the first d dimensions in the final step, we only care about the scaling in the first d dimensions which are determined by the corresponding d singular values with a power α.

By explictly expressing the process which transforms the word-context co-occurrence matrix M to the embedding matrix E, we can find a fact that the relative distances between words only changes within the scaling step. Considering vectors of all words are scaled the same at every dimension, it seems that the relative distances among words should be preserved to some extent. In fact, we have the following two theorems: Theorem 1. For any two words w i and w j , if M i,: -M j,:

2 ≤ δ (δ ≥ 0), then E i,: -E j,: 2 ≤ σ (α-1) d δ.

Theorem 2. For any two words w i and w j , if E i,: -E j,:

2 ≤ δ (δ ≥ 0), then M i,: -M j,: 2 ≤ σ (1-α) 1 δ + 2( n k=d+1 σ 2 k ) 1/2 .

The formal proof of theorem 1 and theorem 2 is in appendix A.2 and A.3.

These two theorems describe how the relative distances (measured in Euclidean distance) among words change during the embedding transformation. Particularly, theorem 1 shows that if the distance between two words w i and w j in M space is no more than δ, their distance in the embedding space is also within a constraint. This bound is related with the singular value σ d and the parameter α. So theorem 1 implies that the relative distances between words will not change dramatically during this transformation from M to E with suitable α. Theorem 2 demonstrates that if we observe two words are embedded closely in E ( E i,: -E j,: 2 is small), we can infer these two words are also close in the original M space. To sum up, the above two theorems indicate the neighborhood structure (relative distances to other words) for every word will be preserve to some extent during the transformation from M to E. In other words, matrix E inherits the neighborhood structure that exists in M . As the result, E will inherit the properties in M that are related with the relative distances among words. Now we can answer the question raised in the introduction: What is the inner mechanism resulting in the good properties of word embedding? In fact, we will show that these properties are the result of inheritance of neighborhood structure.

3.2. THE INNER MECHANISM RESULTING IN THE NICE PROPERTIES IN THE EMBEDDING:

Let us focus on two important properties in E: (1) words with similar semantic meanings are likely to be embedded closely in the embedding space;

(2) the word embedding tends to exhibit the analogy structure, e.g., "woman is to queen as man is to king". Note that these two properties are related with the relative distances among words. So, considering the previous analysis which shows matrix E inherits the neighborhood structure existing in M , these two properties in E also inherits from M as the result.

Words with similar semantic meanings are embedded closely. Harris (1954) indicated that if two words have almost identical environments we say that they are synonyms.. In other words, two words will have similar neighbors if they have similar semantic meanings. It means the corresponding rows in the word-context co-occurrence matrix M should be close for these words. So the words with similar semantic meanings are also close in the M space which has been empirically verified in Levy et al. (2015) . Remember that theorem 1 shows if the distance between two words in M is close (within a small range δ), these two words in E will also be close due to this low rank transformation process from M to E. So the low rank transformation in fact makes the embedding E inherit this property existing in the original word-context matrix M .

The analogy structure in the embedding. Different from word similarity which is about the relative distance between two words (e.g., king and queen), the analogy structure is related with the relative distance between two pairs (e.g., (king, queen) and (man, woman)). So let us first examine how the relative distance between two pairs change during the embedding process. Theorem 3. Let M γ1,: , M γ2,: , M β1,: and M β2,: be four rows in

M matrix. Denote M γ = (M γ1,: -M γ2,: ) and M β = (M β1,: -M β2,: ). If M γ,: -M β,: 2 ≤ δ (δ ≥ 0), then E γ,: -E β,: 2 ≤ σ (α-1) d δ.

Theorem 4. Let M γ1,: , M γ2,: , M β1,: and M β2,: be four rows in

M matrix. Denote M γ = (M γ1,: -M γ2,: ) and M β = (M β1,: -M β2,: ). If E γ,: -E β,: 2 ≤ δ (δ ≥ 0), then M γ,: -M β,: 2 ≤ σ (1-α) 1 δ + 4( n k=d+1 σ 2 k ) 1/2 .

The proof of theorem 3 and theorem 4 is in appendix A.4 and A.5, which is quite similar to the proof of theorem 1 and theorem 2.

Theorems 3 and 4 show that the relative distance between two pairs will not change dramatically during the embedding process either. In other words, the relative distance between pairs of words will be preserved during the embedding transformation from M to E. Furthermore, Levy & Goldberg (2014a) revealed a fact that the original word-context co-occurrence M (e.g., M can be the PPMI matrix)2 also exhibits the analogy structure, such that M king -M queen ≈ M man -M woman . So neighbors of an arbitrarily chosen word summer with α equals to 0.0, 0.5 and 1.0 respectively. More results corresponding other α can be founded in appendix A.9. theorems 3 and 4 together with this fact indicate the analogy structure in E also inherits from M as the result of distance preserving in such low rank transformation process.

To summarize, we prove the bound about the change of relative distances of words during the embedding process. With appropriate α, the neighborhood structure (relative distance) of every word will not change much during the embedding process. So the embedding E inherites the word similarity and the analogy structure from M . We also theoretically explain how the parameter α influences the word embedding by controling the change of relative distances among words (the bounds in theorem 1-4). So a consideration is that we can optimize these bounds by choosing suitable α. We show the derivation of finding the suitable α with respect to the bounds in appendix A.7. It shows the suitable α depends on σ 1 and σ d , together with how to weight the two bounds in theorem 1 (3) and theorem 2 (4). However, the optimization over the bound only gives a rough estimation of the possible range of optimal α. In the next section, we optimize α by directly minimizing the change of neighborhood of words instead of optimizing over the bound.

4. IMPROVEMENT: WORD EMBEDDING PRESERVING THE DISTANCE STRUCTURE BETTER:

In previous section, we reveal the inner mechanism why the embedding exhibits such nice properties. Namely, the embedding is in fact a low rank transformation from M to E and the relative distances between words are preserved during such process. As a result, the embedding matrix E inherits these nice properties existing in the original word-context co-occurrence matrix M (e.g., the PMI matrix). Particularly, theorem 1, 2, 3 and 4 show that the parameter α has an important influence on how the relative distances between words change. For example, we arbitrarily select a word summer in the corpus3 and plot its nearest 20 neighbors with α equal to 0.0, 0.5 and 1.0 respectively. Figure 1 shows that the neighborhood of summer changes with different α. This observation gives us an inspiration that we can learn the embedding E = U d • Σ α d by selecting a good α, thus preserving the relative distances among words during the embedding transformation process.

Preserving neighborhood structure better by choosing optimal α for embedding E = U d • Σ α d . Let g X (w) represent the neighbors of word w in X space, e.g., X can be the word-context cooccurrence matrix M or the embedding matrix E. Let l(•, •) be a correlation function measuring the similarity of two different neighborhoods. This measurement captures how much the neighborhood structure changes incurred by the embedding process. For example, if we consider the top knn nearest neighbors as g X (•) and ignore the order of these nearest neighbors, g X (w) can be viewed as a set and l can be a similarity measurement defined on sets (e.g., Jaccard Similarity). Otherwise, if we consider the order of neighbors, g X (w) can be a ranking list such that the neighbors are ranked by their relative distance to w, and l now can be a measurement about the correlation between two rankings. We use L to denote the aggregated similarity score over all words

L = 1 n w∈W l(g M (w), g E (w)) (3)

where W is the word vocabulary to consider and its size is n. Based on previous analysis, we argue we can select an optimal α for embedding E = U d • Σ α d to preserve the relative distances among words during the embedding transformation, such that

α = arg max α 1 n w∈W l(g M (w), g E (w)) (4)

Leveraging the effect of α into the original SGNS network structure. The above analysis is based on the view that we compute the embedding matrix E by SVD such that

E = U d • Σ α d .

We can also think about to incorporate the effect of α into the original SGNS neural network structure. The original SGNS implicitly performing a symmetric factorization, thus implying the α equal to 0.5. Here, we consider to leverage the influence of α directly into the SGNS structure. Consider the embedding

E = U d • Σ α d and the context C = Σ (1-α) d • V T d learnt by SVD, we have log( ei 2 2 ) log( ei 2 2 ci 2 2 ) = α 4

, where e i and c i are the word vector w i and the context vector of w i respectively. We put it as a regularization term in the original SGNS objective function to add the influence of different α to the embedding learnt by SGNS. The detailed derivation is in appendix A.6.

To summarize, the α parameter in the embedding matrix E = U d • Σ α d influences how the relative distances between words change during the embedding process, thus influencing the quality of the learnt embedding matrix. We propose a method to choose the optimal α by preserving the relative distance among words during the embedding transformation. Besides, we come up with an idea to incorporate the effect of α into the original SGNS architecture. In the next section, we will test these ideas on real experiments.

5. EXPERIMENTS:

In this section, we conduct experiments to verify our previous analysis. The first test is to verify that a good embedding does maximize the correlation defined in equation 3 which measures to which extent the neighborhood structure is preserved during the embedding transformation. The second is to test if the proposed method to incorporate α into original SGNS architecture really has improvements.

5.1. EXPERIMENT SETTINGS:

Corpus We use the Text9 corpus (Mahoney, 2011) which is a standard benchmark used for various natural language tasks. We follow the same pre-processing steps in Levy et al. (2015) .

Word similarity task The purpose of the experiments is to verify whether the method proposed in section 4 to find the optimal α matches the real case. We adapt the same experiment as in Levy et al. (2015) to test the word embedding on the word similarity and analogy structure. There are six datasets acting as the ground truth for the word similarity: WordSim353 (Finkelstein et al., 2002) and its two subsets WS Similarity and WS Relatedness (Zesch et al., 2008; Agirre et al., 2009) , Bruni MEN (Bruni et al., 2012) , Radinsky Mechanical Turk (Radinsky et al., 2011) and Luong Rare Words (Luong et al., 2013) . These datasets5 contain word pairs together with human-assigned similarity scores. Same as Levy et al. (2015) , word embedding is evaluated by the correlation between the similarity computed by the embedding vector and the human-assigned similarity score. The function to compute correlation is the Spearman's correlation (same as Levy et al. (2015) ) Note that we discard the pairs in the test file if it contains a word that does not appear in the text9 corpus. We use the word similarity task as an example for verifying the proposed method (equation 3 and equation 4) to learn the optimal α for word embedding E = U d • Σ α d , and the proposed method to improve SGNS.

The codes used for the SVD embedding is adapted from https://bitbucket.org/ omerlevy/hyperwords and the codes used to learn the SGNS embedding is adapted from https://github.com/theeluwin/pytorch-sgns. We store the codes in a shared dropbox folder 6 for the double-blind review. Table 1 : The performance and similarity corresponding to α = 0 (SVD embedding) and α = 0.5 (symmetric embedding). Left is the peformance on every testset and right is the similarity computed by equation 3, considering the words appearing in that testset. 

5.2. RESULTS:

Firstly, let us verify that if the embedding E = U d • Σ α d is good (measured by the performance on the word similarity testsets), the embedding E should preserve the relative distances between words better (measured by equation 3). We use the "vanilla" setting in Levy et al. (2015) to construct the positive PMI (PPMI) matrix as M : window size is 2, no dynamic context window and no subsampling, the number of negative samples is 1 and the context distribution smoothing parameter is 1.0. For equation 3, we only consider the nearest neighbor for g X and use Jaccard Similarity as the l(•, •). Note that each testset only contains a subset of words in text9, and we also compute the overall correlation (the L in equation 3) considering the words in the corresponding testset. The 6 The dropbox link is https://www.dropbox.com/sh/5d5j4pthcgzutdf/ AABUvZPJpxUo8ugff1gQ7fIQa?dl=0 result is in figure 1 . Figure 1 shows that the performance (measured by these six word similarity groundtruth) and the proposed measurement are highly correlated, such that, for every testset, if α achieves high score word similarity test, the corresponding measurement in equation 3 is also high. More details can be found in appendix A.8. Besides we test whether the α in equation 4 really corresponds to α that achieves the best performance on the word similarity task. We plot the performance of E = U • Σ with different α in figure 2 . The black vertical line corresponds to α that achieves best accuracy and the blue vertical line corresponds to the α learnt by equation 4. We can see that α is very near to the optimal point in almost all datasets. The only exception is the Luong testset, which contains many rare words. We infer the reason is that the corpus cannot effectively capture this testset because more than two thirds words in Luong testsets are not in the text9 corpus. Secondly, we test the effect that incorporating α into SGNS. Table 2 is the performance of the original SGNS with α equals to 0.3 and 0.5 .According to the result (the gold line) in figure 2 , if we push the α from 0.5 to 0.3, the performance in the Luong testset should become better and the performance in all other testsets should drop. The results in table 2 is same with this inference. The only exception is the bruni men testset. We infer the reason is that the performances with α = 0.3 and α = 0.5 are very close (see gold line in figure 2 (a)).

6. RELATED WORK:

Explanation about the analogy structure. Mikolov et al. (2013c) observed the analogy structure existing in the embedding created by a neural network. Levy & Goldberg (2014a) afterwards found the same property also exists in the original word-context co-occurrence matrix. Levy & Goldberg (2014a) infers neural embedding process is not discovering novel patterns, but rather is doing a remarkable job at preserving the patterns inherent in the word-context co-occurrence matrix. However, it is not clear how the neural embedding process preserves such property. Later, several explanations were been proposed to explain the reason (Arora et al., 2016; Gittens et al., 2017; Allen & Hospedales, 2019; Ethayarajh et al., 2018) . For example, Gittens et al. (2017) and Allen & Hospedales (2019) referred to the paraphrasing to explain the analogy structure. Different from these previous studies, we analyze word embedding from the low rank transformation perspective and we reveal the inner mechanism how this property is inherited during the embedding transformation process.

Explanation about the α. The influence of α on the quality of word embedding has been observed in (Caron, 2001; Turney, 2012; Bullinaria & Levy, 2012; Levy et al., 2015; Artetxe et al., 2018) . These works empirically find that α has an important influence to the embedding and suggest this parameter should be tuned. However, these works do not provide theoretical explanation and no clear method has been provided to tune the α. Yin & Shen (2018) is the only work we know which discusses the meaning of α from the pairwise inner product (PIP) loss perspective. But their findings have some contradiction to the real experiments in Caron (2001) ,Turney (2012), Bullinaria & Levy (2012), Levy et al. (2015) and Artetxe et al. (2018) . Specifically, the analysis in Yin & Shen (2018) suggests small α is easier to result in over-fitting and lead to the performace drop, which implies that larger α is better. However, the real experiments in other papers show the performance also drops with very large α. To summarize, we explain the meaning of α in the word embedding transformation which once was not theoretically clear. Futhermore, we propose a method to find the best α for word embedding.

A APPENDIX:

A.1 PROOF OF OBSERVATION 1

Proof. Firstly, we have

EQUATION

d U :,d Besides,

EQUATION

d U :,d , 0, . . . , 0]

So E corresponds to the first d columns of E pse .

A.2 THE PROOF OF THEOREM 1:

We need the following lemma for the proof of theorem 1. Lemma 1. Unitary matrix does not change the norm of a vector, such that

U a 2 = a 2

where U is a unitary matrix and a ∈ R n is a n-dimension column vector.

Proof. The norm can be expressed by using the Hermitian product, (•, •)

U a 2 2 = ((U a, U a)) = (a, U * U a) = (a, a) = a 2 2 ⇒ U a 2 = a 2

Now we can prove the theorem 1. For any two words w i and w j , if M i,: -M j,: 2 ≤ δ, then

E i,: -E j,: 2 ≤ σ (α-1) 1 × δ.

Proof. Let Ẽ denote the E pse defined in section 3. It is obvious that E i,: -E j,: 2 = Ẽi,: -Ẽj,:

2 since E is the first d columns of Ẽ and the last (n -d) dimensions in Ẽ are zero.

Let h = (h 1 , h 2 , . . . , h n ) denote the (M i,: -M j,: )V . We have h 2 = (M i,: -M j,: )V 2 . According to lemma 1, (M i,: -M j,:

)V 2 = (M i,: -M j,: ) 2 . So we have h 2 = (M i,: -M j,: )V 2 = (M i,: -M j,: ) 2 ≤ δ. E i,: -E j,: 2 = Ẽi,: -Ẽj,: 2 = M i,: • V • Σ (α-1) pse -M j,: • V • Σ (α-1) pse 2 = (M i,: • V -M j,: • V ) • Σ (α-1) pse 2 = h • Σ (α-1) pse 2 =((σ (α-1) 1 h 1 ) 2 + (σ (α-1) 2 h 2 ) 2 + . . . + (σ (α-1) d h d ) 2 + 0 + . . . + 0) 1/2 ≤(σ 2(α-1) d • (h 2 1 + h 2 2 + . . . + h 2 d )) 1/2 (note σ d is the smallest singular value) ≤(σ 2(α-1) d • h 2 2 ) 1/2 ≤ σ (α-1) d • δ A.3 THE PROOF OF THEOREM 2 Proof. Let M pse be U Σ pse V T . It is easy to show that M pse equals to U d • Σ d • V T d .

Let M denote M pse . We first show that M i,: -Mi,:

(for every i) is constrained by the singular values of M . Firstly, we have

M i,: -Mi,: 2 = ( j (M i,j -Mi,j ) 2 ) 1/2 ≤ ( k j (M k,j -Mk,j ) 2 ) 1/2 = M -M 2 So we have M i,: -Mi,: 2 ≤ M -M 2 = U ΣV T -U Σ pse V T 2 = U (Σ -Σ pse )V T 2 = (Σ -Σ pse ) 2 (lemma 1) =(σ 2 d+1 + σ 2 d+2 + . . . + σ 2 n ) 1/2

Then we show if E i,: -E j,: 2 ≤ δ, then Mi,: -Mj,:

2 ≤ δσ (1-α) 1

.

Mi,: -Mj,:

2 = (E i,: -E j,: ) • Σ (1-α) d • V T d 2 = (E i,: -E j,: ) • Σ (1-α) d 2 (lemma 1) Let h = (h 1 , h 2 . . . , h n ) denote E i,:

-E j,: here. We have h 2 = E i,: -E j,: 2 ≤ δ. So the above equation becomes

(E i,: -E j,: ) • Σ (1-α) d 2 = (h 1 , h 2 . . . , h n ) • Σ (1-α) d 2 =(h 2 1 σ 2(1-α) 1 + h 2 2 σ 2(1-α) 2 + . . . + h 2 d σ 2(1-α) d ) 1/2 ≤((h 2 1 + h 2 2 + . . . + h 2 d )σ 2(1-α) 1 ) 1/2 ≤ h 2 σ (1-α) 1 ≤δσ (1-α) 1

With above preparations, we can now prove theorem 2.

M i,: -M j,: 2 = (M i,: -Mi,: ) -(M j,: -Mi,: ) 2 ≤ (M i,: -Mi,: ) 2 + -(M j,: -Mi,: ) 2 = (M i,: -Mi,: ) 2 + (M j,: -Mj,: ) -( Mi,: -Mj,: ) 2 = (M i,: -Mi,: ) 2 ≤( n k=d+1 σ 2 k ) 1/2 + (M j,: -Mj,: ) 2 ≤( n k=d+1 σ 2 k ) 1/2 + -( Mi,: -Mj,: ) 2 ≤δσ (1-α) 1 ≤δσ (1-α) 1 + 2( n k=d+1 σ 2 k ) 1/2

A.4 THE PROOF OF THEOREM 3

Proof. Similar to the proof in section A.2, let Ẽ denote the E pse and h = (h 1 , h , 2 . . . , h ) denote the ((M γ1,: -M γ2,: ) -(M β1,: -M β2,: ))V . We have h 2 = ((M γ1,: -M γ2,: ) -(M β1,: -M β2,: ))V 2 = ((M γ1,: -M γ2,: ) -(M β1,: -M β2,: )) 2 ≤ δ.

Besides, (E γ1,: -E γ2,: ) -(E β1,: -E β2,: ) 2 = ( Ẽγ1,: -Ẽγ2,: ) -( Ẽβ1,: -Ẽβ2,: )

2 since E

is the first d columns of Ẽ and the last (n -d) dimensions in Ẽ are zero.

(E γ1,: -E γ2,: ) -(E β1,: -E β2,: ) 2 = ( Ẽγ1,: -Ẽγ2,: ) -( Ẽβ1,: -Ẽβ2,: ) 2 = (M γ1,: -M γ2,: ) • V • Σ (α-1) pse -(M β1,: -M β2,: ) • V • Σ (α-1) pse 2 = ((M γ1,: -M γ2,: ) -(M β1,: -M β2,: )) • V • Σ (α-1) pse 2 = h • Σ (α-1) pse 2 =((σ (α-1) 1 h 1 ) 2 + (σ (α-1) 2 h 2 ) 2 + . . . + (σ (α-1) d h d ) 2 + 0 + . . . + 0) 1/2 ≤σ (α-1) d • (h 2 1 + h 2 2 + . . . + h 2 d ) 1/2 (note σ d is the smallest singular value) ≤σ (α-1) d • h 2 ≤ σ (α-1) d • δ ≤δσ (1-α) 1 =δσ (1-α) 1 + 4( n k=d+1 σ 2 k ) 1/2

A.6 THE PROOF OF ALPHA REGULARIZATION Proof. Firstly, we have

E =U d • Σ α d = [λ α 1 u 1 , λ α 2 u 2 , ..., λ α d u d ] C T =Σ 1-α d • V T d =      λ 1-α 1 v T 1 λ 1-α 2 v T 2 . . . λ 1-α d v T d     

Since U and V is orthogonal, we have We assume that the optimal α should minimize the outcome bounds in both Theorem 1 (B 1 ) and 2 (B 2 ) 7 . The reason is that if two words are close in the original M space, these two words should also be close in the E space because we do not want the relative distances of words change dramatically, and vice versa. Thus we derive the optimal α by minimizing the weighted summation of the bounds

EQUATION

B =λB 1 + (1 -λ)B 2 B 1 = σ (α-1) d δ, α ≤ 1 σ (α-1) 1 δ, α ≥ 1 B 2 = σ (1-α) 1 δ, α ≤ 1 σ (1-α) d δ, α ≥ 1

where λ is the weight coefficient in the summation.

We derive the optimal α in three cases, i.e. Case 1:

σ 1 ≥ σ d ≥ 1, Case 2: σ 1 ≥ 1 ≥ σ d , Case 3: σ d ≤ σ 1 ≤ 1.

For Case 1, when α ≥ 1, we have

B =λσ α-1 1 δ + (1 -λ)σ 1-α d δ ∂B ∂α =λδσ α-1 1 ln σ 1 -(1 -λ)δσ 1-α d ln σ d

Easy to prove that B is a convex function, so we derive α by solving the equation ∂B ∂α = 0, for simplicity, we use k

= 1-λ λ , ∂B ∂α = 0 ⇒ λδσ α-1 1 ln σ 1 = (1 -λ)δσ 1-α d ln σ d α = 1 + ln k ln σ d ln σ1 ln (σ 1 σ d )

7

The optimal α with respect to theorem 3 and theorem 4 can be derived in the same way.

Similarly, when α ≤ 1, we have

B = λσ α-1 d δ + (1 -λ)σ 1-α 1 δ ∂B ∂α = 0 ⇒ α = 1 + ln k ln σ1 ln σ d ln (σ 1 σ d )

Then we have the optimal α in terms of k as

α =          1 + ln k ln σ d ln σ 1 ln (σ1σ d ) ≥ 1, k ≥ ln σ1 ln σ d 1, ln σ d ln σ1 ≤ k ≤ ln σ1 ln σ d 1 + ln k ln σ 1 ln σ d ln (σ1σ d ) ≤ 1, k ≤ ln σ d ln σ1

For Case 2, from the formulation of B, we can easily derive the optimal α is 1.

For Case 3, similar with the derivation of Case 1, we have the optimal α in terms of k as, , autumn, spring, nights, rainy, days, night, week, annual, year weekend, seasons, winters, snow, summers, day, holiday, rain, month, weather 

α =                1 + ln k ln σ -1 1 ln σ -1 d ln (σ1σ d ) ≤ 1, k ≥ ln σ -1 d ln σ -1 1 1, ln σ -1 1 ln σ -1 d ≤ k ≤ ln σ -1 d ln σ -1 1 1 + ln k ln σ -1 d ln σ -1 1 ln (σ1σ d ) ≥ 1, k ≤ ln σ -1 1 ln σ -1 d A.

:

We will explain the meaning of these variables (e.g., U d ) in the following sections.

The word-context co-occurrence matrix M is called explicit representation inLevy & Goldberg (2014a)

We will introduce the corpus in section 5

Suppose we only consider the words for which ei 2 2 ci 2 2 = 1, to avoid the case that zero appears in the denominator.

These datasets can be downloaded from https://bitbucket.org/omerlevy/hyperwords

Figures and Tables:

Figure 1: Illustration of the local neighborhood structure in the embedding space E = U d • Σ α d with different α. From (a) to (c): t-SNE (Maaten & Hinton, 2008) visualization of the nearest 20neighbors of an arbitrarily chosen word summer with α equals to 0.0, 0.5 and 1.0 respectively. More results corresponding other α can be founded in appendix A.9.

Figure 2: Compare the best α (black vertical line) in terms of the performance on the word similarity task and the best α (blue vertical line) in terms of equation 4. α is searched from [-1, 1] with 0.1 as increment. From (a) to (e): y-axis is the correlation between the embedding score and the human assignend score. x-axis is different α.

OPTIMAL α IN TERMS OF MINIMIZING THE WEIGHTED SUMMATION OF THE BOUNDS IN THEOREM 1 AND 2

Besides, Σ d is the truncated diagonal matrix containing top d singular values. U d and V d are the corresponding truncated U and truncated V respectively. The d-dimension word embedding matrix E is obtained by multiplying U . Let us define another diagonal matrix Σ pse = diag(σ 1 , . . . , σ d , 0, . . . , 0) whose first d elements are the singular values in Σ and the remaining diagonal elements are zeros. We have the following observation.

Table content: <table><tr><td/><td>d with a</td></tr><tr><td>power of Σ d ,</td><td/></tr><tr><td>E = U d • Σ α d</td><td>(1)</td></tr><tr><td>3.1 WORD EMBEDDING AS LOW RANK TRANSFORMATION</td><td/></tr><tr><td colspan="2">The embedding E in equation 1 is indeed a low rank transformation from the original word-context</td></tr><tr><td>co-occurrence space M Observation 1. E is the first d columns of E pse</td><td/></tr></table>

The results of incorporating α to the original SGNS.

Table content: <table><tr><td>α</td><td>bruni men</td><td>Luong</td><td colspan="3">radinsky ws relatedness ws similarity</td><td>ws353</td></tr><tr><td>0.3</td><td>0.70680</td><td colspan="2">0.45004 0.67119</td><td>0.63262</td><td>0.77532</td><td>0.71247</td></tr><tr><td>0.5</td><td>0.70475</td><td colspan="2">0.43613 0.67177</td><td>0.63733</td><td>0.77679</td><td>0.71309</td></tr></table>

8 PERFORMANCE ON WORD SIMILARITY TASK AND THE CORRELATION SCORE DEFINED IN EQUATION 3 WITH DIFFERENT α The performance and similarity corresponding to different α. Left is the peformance on every testset and right is the similarity computed by equation 3, considering the words appearing in that testset. , spring, rainy, monsoon, summers, winters, warmest, nights, coldest seasons, precipitation, temperatures,humidity, snowfall, year, freezing, months, average, climates -0.8 winter, autumn, spring, rainy, monsoon, summers, winters, warmest, nights, coldest seasons, precipitation, snowfall, temperatures, humidity, year, freezing, climates, months, average -0.7 winter, autumn, spring, rainy, summers, monsoon, winters, warmest, nights, coldest seasons, precipitation, snowfall, humidity, temperatures, year, freezing, climates, humid, months -0.6 winter, autumn, spring, rainy, summers, monsoon, winters, warmest, nights, coldest snowfall, precipitation, seasons, humidity, temperatures, year, freezing, climates, humid, months -0.5 winter, autumn, rainy, spring, summers, monsoon, winters, warmest, nights, coldest snowfall, precipitation, seasons, humidity, temperatures, year, freezing, climates, humid, months -0.4 winter, autumn, rainy, spring, summers, monsoon, winters, warmest, nights, coldest snowfall, precipitation, humidity, seasons, temperatures, year, freezing, climates, humid, months -0.3 winter, autumn, rainy, spring, summers, monsoon, winters, nights, warmest, coldest snowfall, precipitation, humidity, temperatures, seasons, year, climates, freezing, humid, windy -0.2 winter, autumn, rainy, spring, summers, winters, monsoon, nights, warmest, coldest snowfall, precipitation, humidity, temperatures, seasons, year, climates, humid, freezing, windy -0.1 winter, autumn, rainy, spring, summers, winters, monsoon, nights, warmest, coldest snowfall, precipitation, humidity, temperatures, seasons, climates, year, humid, freezing, windy 0.0 winter, autumn, rainy, spring, summers, winters, monsoon, nights, warmest, coldest snowfall, precipitation, humidity, temperatures, seasons, climates, humid, year, windy, freezing 0.1 winter, autumn, rainy, spring, summers, winters, monsoon, nights, warmest, coldest snowfall, precipitation, temperatures, humidity, seasons, year, humid, climates, windy, freezing 0.2 winter, autumn, rainy, spring, summers, winters, monsoon, nights, warmest, coldest snowfall, precipitation, temperatures, humidity, seasons, year, humid, climates, windy, sunny 0.3 winter, autumn, rainy, spring, summers, winters, monsoon, nights, warmest, snowfall coldest, precipitation, temperatures, seasons, humidity, year, humid, windy, climates, sunny 0.4 winter, autumn, rainy, spring, summers, winters, nights, monsoon, snowfall, warmest coldest, precipitation, seasons, temperatures, year, humidity, windy, humid, climates, days 0.5 winter, autumn, rainy, spring, summers, nights, winters, monsoon, snowfall, warmest coldest, seasons, precipitation, year, days, temperatures, weekend, windy, sunny, humidity 0.6 winter, autumn, rainy, spring, nights, summers, winters, monsoon, snowfall, warmest coldest, seasons, year, days, weekend, precipitation, annual, sunny, temperatures, month 0.7 winter, autumn, rainy, spring, nights, summers, winters, monsoon, snowfall, warmest days, coldest, year, seasons, weekend, annual, week, sunny, month, snow 0.8 winter, autumn, spring, rainy, nights, winters, summers, days, monsoon, year weekend, seasons, snowfall, annual, week, night, warmest, coldest, snow, month 0.9 winter, autumn, spring, nights, rainy, days, winters, summers, night, year weekend, annual, week, seasons, monsoon, snow, holiday, rain, month, day

Table content: <table><tr><td>α</td><td>bruni men</td><td>Luong</td><td>radinsky</td><td colspan="2">ws relatedness ws similarity</td><td>ws353</td></tr><tr><td colspan="4">-1.0 0.686 / 0.492 0.480 / 0.457 0.504 / 0.487</td><td>0.591 / 0.532</td><td colspan="2">0.759 / 0.522 0.694 / 0.535</td></tr><tr><td colspan="4">-0.9 0.691 / 0.490 0.482 / 0.458 0.508 / 0.495</td><td>0.597 / 0.532</td><td colspan="2">0.761 / 0.522 0.697 / 0.535</td></tr><tr><td colspan="4">-0.8 0.697 / 0.489 0.484 / 0.459 0.513 / 0.493</td><td>0.605 / 0.538</td><td colspan="2">0.762 / 0.526 0.701 / 0.539</td></tr><tr><td colspan="4">-0.7 0.703 / 0.490 0.487 / 0.460 0.520 / 0.501</td><td>0.612 / 0.538</td><td colspan="2">0.765 / 0.526 0.706 / 0.539</td></tr><tr><td colspan="4">-0.6 0.709 / 0.488 0.491 / 0.462 0.526 / 0.499</td><td>0.621 / 0.538</td><td colspan="2">0.765 / 0.522 0.711 / 0.537</td></tr><tr><td colspan="4">-0.5 0.715 / 0.488 0.493 / 0.462 0.534 / 0.499</td><td>0.630 / 0.538</td><td colspan="2">0.766 / 0.518 0.715 / 0.535</td></tr><tr><td colspan="4">-0.4 0.721 / 0.488 0.496 / 0.462 0.540 / 0.501</td><td>0.637 / 0.544</td><td colspan="2">0.769 / 0.526 0.719 / 0.539</td></tr><tr><td colspan="4">-0.3 0.728 / 0.489 0.499 / 0.460 0.551 / 0.503</td><td>0.645 / 0.544</td><td colspan="2">0.774 / 0.526 0.724 / 0.539</td></tr><tr><td colspan="4">-0.2 0.734 / 0.492 0.502 / 0.467 0.562 / 0.509</td><td>0.651 / 0.547</td><td colspan="2">0.779 / 0.529 0.729 / 0.544</td></tr><tr><td colspan="4">-0.1 0.740 / 0.489 0.504 / 0.466 0.576 / 0.509</td><td>0.659 / 0.549</td><td colspan="2">0.782 / 0.533 0.733 / 0.546</td></tr><tr><td>0.0</td><td colspan="3">0.746 / 0.492 0.507 / 0.469 0.588 / 0.507</td><td>0.667 / 0.552</td><td colspan="2">0.786 / 0.533 0.737 / 0.549</td></tr><tr><td>0.1</td><td colspan="3">0.751 / 0.497 0.509 / 0.469 0.601 / 0.509</td><td>0.676 / 0.558</td><td colspan="2">0.791 / 0.536 0.742 / 0.553</td></tr><tr><td>0.2</td><td colspan="3">0.755 / 0.504 0.510 / 0.471 0.618 / 0.513</td><td>0.685 / 0.558</td><td colspan="2">0.796 / 0.540 0.747 / 0.553</td></tr><tr><td>0.3</td><td colspan="3">0.758 / 0.520 0.512 / 0.473 0.635 / 0.521</td><td>0.693 / 0.570</td><td colspan="2">0.802 / 0.555 0.750 / 0.563</td></tr><tr><td>0.4</td><td colspan="3">0.759 / 0.519 0.511 / 0.475 0.652 / 0.525</td><td>0.698 / 0.570</td><td colspan="2">0.807 / 0.555 0.751 / 0.565</td></tr><tr><td>0.5</td><td colspan="3">0.759 / 0.518 0.509 / 0.475 0.666 / 0.525</td><td>0.701 / 0.573</td><td colspan="2">0.812 / 0.558 0.750 / 0.569</td></tr><tr><td>0.6</td><td colspan="3">0.756 / 0.515 0.504 / 0.478 0.675 / 0.517</td><td>0.700 / 0.576</td><td colspan="2">0.816 / 0.558 0.748 / 0.572</td></tr><tr><td>0.7</td><td colspan="3">0.750 / 0.518 0.496 / 0.481 0.675 / 0.517</td><td>0.693 / 0.567</td><td colspan="2">0.813 / 0.562 0.741 / 0.565</td></tr><tr><td>0.8</td><td colspan="3">0.740 / 0.527 0.485 / 0.472 0.672 / 0.511</td><td>0.677 / 0.576</td><td colspan="2">0.805 / 0.573 0.728 / 0.572</td></tr><tr><td>0.9</td><td colspan="3">0.726 / 0.516 0.468 / 0.465 0.663 / 0.517</td><td>0.649 / 0.567</td><td colspan="2">0.794 / 0.555 0.708 / 0.558</td></tr><tr><td>1.0</td><td colspan="3">0.707 / 0.505 0.448 / 0.456 0.649 / 0.513</td><td>0.619 / 0.561</td><td colspan="2">0.780 / 0.547 0.687 / 0.556</td></tr></table>

Peer review (iclr2020):
This paper explores the role of the implicit alpha parameter when learning word embeddings. More concretely, word embeddings work by either implicitly or explicitly factorizing a co-occurrence matrix, and the underlying parameter alpha controls how the singular values are weighted between the word and the context vectors. The authors provide theoretical insights on the role of alpha in relation with the original co-occurrence matrix, and propose a new method to find its optimal value. I think that this is overall a solid work. The paper provides a new perspective in the workings of word embeddings that I find interesting, it is theoretically well-founded (although I did not check all derivations in detail), and the presentation is clear. However, I think that the paper does a poor job in putting its contributions into context in relation to previous work. In particular, the role of alpha in word embeddings was already studied empirically by Artetxe et al. (CoNLL*18, https://www.aclweb.org/anthology/K18-1028.pdf) for both word analogy and word similarity tasks, to the extent that Figure 2 in both papers is showing the exact same curves. However, the authors do not even cite it. As acknowledged in the paper, other authors like Levy et al. (TACL*15) also observed that the value of alpha was important in their experiments. I think that the right narrative for the paper should more in the line of *previous work showed that alpha behaves this and that way; we provide a theoretical explanation for this behavior, and derive a method to automatically find its optimal value*. However, starting from the title (*word embedding re-examined: is the symmetrical factorization optimal?*, when it was already known that it wasn*t) and the abstract (where only the statement that *we propose a method to find the optimal alpha* corresponds to a novel contribution), the paper does a poor job in identifying and properly contextualizing its real contributions. More importantly, the paper does not try to establish any connection between the authors own theory and the empirical findings from previous work. In terms of the actual content, the authors constantly claim that word2vec is performing a symmetric factorization (e.g. *the original word2vec is implicitly performing a symmetric factorization, thus implying the alpha equal to 0.5) as if it was something obvious or well-known. I might be missing something here, but I do not see why this is the case. Following your notation, let*s say that word2vec is implicitly factorizing M = E*C^T, where E are the word embeddings and C are the context embeddings. One could multiply E with any arbitrary invertible matrix W, and C by the transpose of its inverse W^-T, which could be chosen to completely break any symmetry, yet the objective value of word2vec would not change at all, as (E*W)*(C*W^-T)^T = E*C^T. In other words, there is nothing in the training objective of word2vec that forces a symmetric factorization, and there is always an optimal solution with respect to this training objective that is arbitrarily asymmetric. Another point that raises concerns to me is that the optimal value of alpha is determined by the vocabulary of the evaluation task. It would make sense if the optimal alpha depended on the nature of the task (e.g. syntactic vs semantic), but I do not have any intuition (nor do the authors provide) as of why the vocabulary would be anyhow relevant. More importantly, this does not seem generalizable beyond a few intrinsic tasks as, in the general case, one wants good embeddings for the full vocabulary. In either case, I think that this point deserves more attention in the paper. I also find the experimental evaluation to be somewhat weak. In particular, the proposed theory focuses in two phenomena (word similarity and word analogy) as stated in the abstract itself, but the empirical evaluation is limited to the word similarity task. Also, this is a minor detail and it did not influence my score, but I dislike that the authors use *word2vec* to refer to skip-gram with negative sampling throughout the paper. I would suggest to either use SGNS (which is quite standard) or simply skip-gram.