Year: 2019

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.

heading: 1 INTRODUCTION
text: 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 = Ud ·Σαd 1 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:
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?
1We will explain the meaning of these variables (e.g., Ud) in the following sections.
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.

heading: 2 BACKGROUND AND PRELIMINARIES
text: 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 ∈ Rn×n is the word-context matrix where Mi,j represents some statistics between word wi and its context word wj . These word embedding algorithms are seeking a d-dimension word embedding matrix E ∈ Rn×d accompanied with a context embedding matrix C ∈ Rn×d to approximate the word-context matrix M , such that M ≈ ECT . 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 M as M = U ·Σ ·V T . Finally, only the top d singular values in Σ and the corresponding columns in U and V are kept, producing Σd, Ud and Vd respectively. The word embedding E ∈ Rn×d is obtained by E = Ud or E = Ud ·Σd. 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 E = Ud · Σα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 Ud ·Σαd where Ud, Σd and α are as defined before.

heading: 3 ANALYSIS: THE REASON WHY THE EMBEDDING EXHIBITS NICE PROPERTIES
text: 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. Besides, Σd is the truncated diagonal matrix containing top d singular values. Ud and Vd are the corresponding truncated U and truncated V respectively. The d-dimension word embedding matrix E is obtained by multiplying Ud with a power of Σd,
E = Ud ·Σαd (1)

heading: 3.1 WORD EMBEDDING AS LOW RANK TRANSFORMATION
text: The embedding E in equation 1 is indeed a low rank transformation from the original word-context co-occurrence space M . 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.
Observation 1. E is the first d columns of Epse
Epse = M · V ·Σ(α−1)pse (2)

heading: The proof is in Appendix A.1.
text: 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 MV ; (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 MV . 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 wi and wj , if ‖Mi,: −Mj,:‖2 ≤ δ (δ ≥ 0), then ‖Ei,: −Ej,:‖2 ≤ σ (α−1) d δ.
Theorem 2. For any two words wi and wj , if ‖Ei,: −Ej,:‖2 ≤ δ (δ ≥ 0), then ‖Mi,: −Mj,:‖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 wi and wj 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 (‖Ei,: −Ej,:‖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.

heading: 3.2 THE INNER MECHANISM RESULTING IN THE NICE PROPERTIES IN THE EMBEDDING
text: 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 Mking −Mqueen ≈Mman −Mwoman. So
2The word-context co-occurrence matrix M is called explicit representation in Levy & Goldberg (2014a)
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.

heading: 4 IMPROVEMENT: WORD EMBEDDING PRESERVING THE DISTANCE STRUCTURE BETTER
text: 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 = Ud ·Σα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 = Ud ·Σαd . Let gX (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 gX (·) and ignore the order of these nearest neighbors, gX (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, gX (w) can be a ranking list such that the neighbors are ranked
3We will introduce the corpus in section 5
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(gM (w), gE(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 = Ud · Σαd to preserve the relative distances among words during the embedding transformation, such that
α? = argmax α
1
n ∑ w∈W l(gM (w), gE(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 = Ud ·Σα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 = Ud · Σαd and the context C = Σ (1−α) d · V Td learnt by SVD, we have log(‖ei‖22) log(‖ei‖22‖ci‖ 2 2)
= α 4, where ei and ci are the word vector wi and the context vector of wi 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 = Ud ·Σα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.

heading: 5 EXPERIMENTS
text: 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.

heading: 5.1 EXPERIMENT SETTINGS
text: 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
4Suppose we only consider the words for which ‖ei‖22 ‖ci‖ 2 2 6= 1, to avoid the case that zero appears in the
denominator. 5These datasets can be downloaded from https://bitbucket.org/omerlevy/hyperwords
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 = Ud ·Σα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.

heading: 5.2 RESULTS
text: Firstly, let us verify that if the embedding E = Ud ·Σα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 gX 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
6The 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)).

heading: 6 RELATED WORK
text: 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.

heading: A APPENDIX

heading: A.1 PROOF OF OBSERVATION 1
text: Proof. Firstly, we have
E =Md ·Σαd
= [U:,1,U:,2, . . . ,U:,d] · σ1 . . . σd  = [ σ (α) 1 U:,1, σ (α) 2 U:,2, . . . , σ (α) d U:,d
] Besides,
Epse =M · V ·Σ(α−1)pse =U ·Σ · V T · V ·Σ(α−1)pse =U ·Σ · I ·Σ(α−1)pse (V is unitary matrix, so V T · V = I)
=U ·Σ ·Σ(α−1)pse
=[U:,1,U:,2, . . . ,U:,n] ·  σ1 . . . σd σd+1
. . . σn
 ·  σ (α−1) 1 . . . σ (α−1) d 0 . . .
0

=[U:,1,U:,2, . . . ,U:,n] ·  σ (α) 1 . . . σ (α) d 0 . . .
0  =[σ
(α) 1 U:,1, σ (α) 2 U:,2, . . . , σ (α) d U:,d, 0, . . . , 0]
So E corresponds to the first d columns of Epse.

heading: A.2 THE PROOF OF THEOREM 1
text: 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
‖Ua‖2 = ‖a‖2 where U is a unitary matrix and a ∈ Rn is a n-dimension column vector.
Proof. The norm can be expressed by using the Hermitian product, (·, ·)
‖Ua‖22 = ((Ua,Ua)) = (a,U ∗Ua) = (a,a) = ‖a‖22
⇒‖Ua‖2 = ‖a‖2
Now we can prove the theorem 1. For any two words wi and wj , if ‖Mi,: −Mj,:‖2 ≤ δ, then ‖Ei,: −Ej,:‖2 ≤ ( σ (α−1) 1 ) × δ.
Proof. Let Ẽ denote the Epse defined in section 3. It is obvious that ‖Ei,: −Ej,:‖2 =∥∥∥Ẽi,: − Ẽj,:∥∥∥ 2 since E is the first d columns of Ẽ and the last (n− d) dimensions in Ẽ are zero.
Let h = (h1, h2, . . . , hn) denote the (Mi,: −Mj,:)V . We have ‖h‖2 = ‖(Mi,: −Mj,:)V ‖2. According to lemma 1, ‖(Mi,: −Mj,:)V ‖2 = ‖(Mi,: −Mj,:)‖2. So we have ‖h‖2 = ‖(Mi,: −Mj,:)V ‖2 = ‖(Mi,: −Mj,:)‖2 ≤ δ.
‖Ei,: −Ej,:‖2 = ∥∥∥Ẽi,: − Ẽj,:∥∥∥
2 = ∥∥∥Mi,: · V ·Σ(α−1)pse −Mj,: · V ·Σ(α−1)pse ∥∥∥
2 = ∥∥∥(Mi,: · V −Mj,: · V ) ·Σ(α−1)pse ∥∥∥
2 = ∥∥∥h ·Σ(α−1)pse ∥∥∥
2
=((σ (α−1) 1 h1) 2 + (σ (α−1) 2 h2) 2 + . . .+ (σ (α−1) d hd) 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 · δ

heading: A.3 THE PROOF OF THEOREM 2
text: Proof. Let Mpse be UΣpseV T . It is easy to show that Mpse equals to Ud ·Σd · V Td . Let M̃ denote Mpse. We first show that ∥∥∥Mi,: − M̃i,:∥∥∥2
2 (for every i) is constrained by the singular
values of M . Firstly, we have∥∥∥Mi,: − M̃i,:∥∥∥ 2 = ( ∑ j (Mi,j − M̃i,j)2)1/2 ≤ ( ∑ k ∑ j (Mk,j − M̃k,j)2)1/2 = ∥∥∥M − M̃∥∥∥ 2
So we have ∥∥∥Mi,: − M̃i,:∥∥∥ 2
≤ ∥∥∥M − M̃∥∥∥
2 = ∥∥UΣV T −UΣpseV T∥∥2
= ∥∥U(Σ−Σpse)V T∥∥2 = ‖(Σ−Σpse)‖2 (lemma 1) =(σ2d+1 + σ 2 d+2 + . . .+ σ 2 n) 1/2
Then we show if ‖Ei,: −Ej,:‖2 ≤ δ, then ∥∥∥M̃i,: − M̃j,:∥∥∥
2 ≤ δσ(1−α)1 .∥∥∥M̃i,: − M̃j,:∥∥∥
2 = ∥∥∥(Ei,: −Ej,:) ·Σ(1−α)d · V Td ∥∥∥
2 = ∥∥∥(Ei,: −Ej,:) ·Σ(1−α)d ∥∥∥
2 (lemma 1)
Let h = (h1, h2 . . . , hn) denote Ei,: − Ej,: here. We have ‖h‖2 = ‖Ei,: −Ej,:‖2 ≤ δ. So the above equation becomes ∥∥∥(Ei,: −Ej,:) ·Σ(1−α)d ∥∥∥
2 = ∥∥∥(h1, h2 . . . , hn) ·Σ(1−α)d ∥∥∥
2
=(h21σ 2(1−α) 1 + h 2 2σ 2(1−α) 2 + . . .+ h 2 dσ 2(1−α) d ) 1/2 ≤((h21 + h22 + . . .+ h2d)σ 2(1−α) 1 ) 1/2 ≤‖h‖2 σ (1−α) 1 ≤δσ(1−α)1
With above preparations, we can now prove theorem 2.
‖Mi,: −Mj,:‖2 = ∥∥∥(Mi,: − M̃i,:)− (Mj,: − M̃i,:)∥∥∥
2 ≤ ∥∥∥(Mi,: − M̃i,:)∥∥∥ 2 + ∥∥∥−(Mj,: − M̃i,:)∥∥∥ 2
= ∥∥∥(Mi,: − M̃i,:)∥∥∥ 2 + ∥∥∥(Mj,: − M̃j,:)− (M̃i,: − M̃j,:)∥∥∥ 2
= ∥∥∥(Mi,: − M̃i,:)∥∥∥
2︸ ︷︷ ︸ ≤( ∑n k=d+1 σ 2 k) 1/2
+ ∥∥∥(Mj,: − M̃j,:)∥∥∥
2︸ ︷︷ ︸ ≤( ∑n k=d+1 σ 2 k) 1/2
+ ∥∥∥−(M̃i,: − M̃j,:)∥∥∥
2︸ ︷︷ ︸ ≤δσ(1−α)1
≤δσ(1−α)1 + 2( n∑
k=d+1
σ2k) 1/2

heading: A.4 THE PROOF OF THEOREM 3
text: Proof. Similar to the proof in section A.2, let Ẽ denote the Epse and h = (h1, 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 = ∥∥∥(Ẽγ1,: − Ẽγ2,:)− (Ẽβ1,: − Ẽβ2,:)∥∥∥ 2 since E is the first d columns of Ẽ and the last (n− d) dimensions in Ẽ are zero.
‖(Eγ1,: −Eγ2,:)− (Eβ1,: −Eβ2,:)‖2 = ∥∥∥(Ẽγ1,: − Ẽγ2,:)− (Ẽβ1,: − Ẽβ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 h1) 2 + (σ (α−1) 2 h2) 2 + . . .+ (σ (α−1) d hd) 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 · δ

heading: A.5 THE PROOF OF THEOREM 4
text: The proof is quite similar to the proof in section A.3. Let Mpse be UΣpseV T . According to section A.3, we know Mpse equals to Ud ·Σd · V td .
Let M̃ denote Mpse. According to section A.3, we have ∥∥∥Mi,: − M̃i,:∥∥∥
2 ≤ (σ2d+1 + σ2d+2 + . . .+
σ2n) 1/2 (for every i).
Then with the same process in section A.3, we show if ‖(Eγ1,: −Eγ2,:)− (Eβ1,: −Eβ2,:)‖2 ≤ δ, then ∥∥∥((M̃γ1,: − M̃γ2,:)− (M̃β1,: − M̃β2,:))∥∥∥ 2 ≤ δσ(1−α)1 .
∥∥∥((M̃γ1,: − M̃γ2,:)− (M̃β1,: − M̃β2,:))∥∥∥ 2
= ∥∥∥((Eγ1,: −Eγ2,:)− (Eβ1,: −Eβ2,:)) ·Σ(1−α)d · V Td ∥∥∥
2 = ∥∥∥((Eγ1,: −Eγ2,:)− (Eβ1,: −Eβ2,:)) ·Σ(1−α)d ∥∥∥
2 (lemma 1)
Let h = (h1, h2 . . . , hn) denote ((Eγ1,: − Eγ2,:) − (Eβ1,: − Eβ2,:)) here. We have ‖h‖2 = ‖((Eγ1,: −Eγ2,:)− (Eβ1,: −Eβ2,:))‖2 ≤ δ. So the above equation becomes∥∥∥((Eγ1,: −Eγ2,:)− (Eβ1,: −Eβ2,:)) ·Σ(1−α)d ∥∥∥
2 = ∥∥∥(h1, h2 . . . , hn) ·Σ(1−α)d ∥∥∥
2
=(h21σ 2(1−α) 1 + h 2 2σ 2(1−α) 2 + . . .+ h 2 dσ 2(1−α) d ) 1/2 ≤(h21 + h22 + . . .+ h2d)1/2σ (1−α) 1 = ‖h‖2 σ (1−α) 1 =δσ (1−α) 1
With above preparations, we can now prove theorem 4.
Proof.
‖Mγ,: −Mβ,:‖2 = ∥∥∥(Mγ,: − M̃γ,:)− (Mβ,: − M̃γ,:)∥∥∥
2 ≤ ∥∥∥(Mγ,: − M̃γ,:)∥∥∥ 2 + ∥∥∥−(Mβ,: − M̃γ,:)∥∥∥ 2
= ∥∥∥(Mγ,: − M̃γ,:)∥∥∥ 2 + ∥∥∥(Mβ,: − M̃β,:)− (M̃γ,: − M̃β,:)∥∥∥ 2
≤ ∥∥∥(Mγ,: − M̃γ,:)∥∥∥ 2 + ∥∥∥(Mβ,: − M̃β,:)∥∥∥ 2 + ∥∥∥−(M̃γ,: − M̃β,:)∥∥∥ 2
= ∥∥∥(Mγ1,: − M̃γ1,:)− (Mγ2,: − M̃γ2,:)∥∥∥ 2 + ∥∥∥(Mβ1,: − M̃β2,:)− (Mβ2,: − M̃β2,:)∥∥∥ 2 + ∥∥∥−(M̃γ,: − M̃β,:)∥∥∥ 2
≤ ∥∥∥(Mγ1,: − M̃γ1,:)∥∥∥
2︸ ︷︷ ︸ ≤( ∑n k=d+1 σ2 k )1/2
+ ∥∥∥−(Mγ2,: − M̃γ2,:)∥∥∥
2︸ ︷︷ ︸ ≤( ∑n k=d+1 σ2 k )1/2
+ ∥∥∥(Mβ1,: − M̃β2,:)∥∥∥
2︸ ︷︷ ︸ ≤( ∑n k=d+1 σ2 k )1/2
+ ∥∥∥−(Mβ2,: − M̃β2,:)∥∥∥
2︸ ︷︷ ︸ ≤( ∑n k=d+1 σ2 k )1/2
+ ∥∥∥−(M̃γ,: − M̃β,:)∥∥∥
2︸ ︷︷ ︸ ≤δσ(1−α)1
=δσ (1−α) 1 + 4( n∑ k=d+1 σ2k) 1/2

heading: A.6 THE PROOF OF ALPHA REGULARIZATION
text: Proof. Firstly, we have E =Ud ·Σαd
= [λα1u1, λ α 2u2, ..., λ α dud]
CT =Σ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
eTi ej =
{ λ2αi , i = j
0, i 6= j
cTi cj =
{ λ2−2αi , i = j
0, i 6= j
Then, if (‖ei‖22 · ‖ci‖ 2 2) 6= 1, we have
log(‖ei‖22) log(‖ei‖22 · ‖ci‖ 2 2) = α
A.7 THE OPTIMAL α IN TERMS OF MINIMIZING THE WEIGHTED SUMMATION OF THE BOUNDS IN THEOREM 1 AND 2
We assume that the optimal α should minimize the outcome bounds in both Theorem 1 (B1) and 2 (B2) 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
B =λB1 + (1− λ)B2
B1 = { σ (α−1) d δ, α ≤ 1 σ (α−1) 1 δ, α ≥ 1
B2 = { σ (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 =λσα−11 δ + (1− λ)σ 1−α d δ
∂B ∂α =λδσα−11 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⇒ λδσα−11 lnσ1 = (1− λ)δσ 1−α d lnσd α = 1 + ln k lnσdlnσ1 ln (σ1σd)
7The optimal α with respect to theorem 3 and theorem 4 can be derived in the same way.
Similarly, when α ≤ 1, we have
B = λσα−1d δ + (1− λ)σ 1−α 1 δ
∂B ∂α = 0⇒ α = 1 + ln k lnσ1lnσ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σ1lnσd 1, lnσdlnσ1 ≤ k ≤ lnσ1 lnσd
1 + ln k ln σ1 ln σd
ln (σ1σd) ≤ 1, k ≤ lnσdlnσ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,
α =  1 + ln k ln σ −1 1 ln σ −1 d ln (σ1σd) ≤ 1, k ≥ lnσ −1 d lnσ−11 1, lnσ−11 lnσ−1d ≤ k ≤ lnσ −1 d lnσ−11
1 + ln k ln σ
−1 d
ln σ −1 1
ln (σ1σd) ≥ 1, k ≤ lnσ
−1 1 lnσ−1d

heading: A.8 PERFORMANCE ON WORD SIMILARITY TASK AND THE CORRELATION SCORE DEFINED
text: IN EQUATION 3 WITH DIFFERENT α
A.9 THE NEIGHBORHOOD OF summer WITH DIFFERENT α
top 20 nearest words
PMI winter, olympics, autumn, during, and, spring, annual, season, in, at night, year, on, weather, after, rainy, day, including, festival, seasonal
α top 20 nearest words
-1.0 winter, autumn, spring, rainy, monsoon, summers, winters, warmest, nights, coldestseasons, precipitation, temperatures, humidity, year, snowfall, freezing, months, average, climates -0.9 winter, autumn, spring, rainy, monsoon, summers, winters, warmest, nights, coldestseasons, precipitation, temperatures,humidity, snowfall, year, freezing, months, average, climates -0.8 winter, autumn, spring, rainy, monsoon, summers, winters, warmest, nights, coldestseasons, precipitation, snowfall, temperatures, humidity, year, freezing, climates, months, average -0.7 winter, autumn, spring, rainy, summers, monsoon, winters, warmest, nights, coldestseasons, precipitation, snowfall, humidity, temperatures, year, freezing, climates, humid, months -0.6 winter, autumn, spring, rainy, summers, monsoon, winters, warmest, nights, coldestsnowfall, precipitation, seasons, humidity, temperatures, year, freezing, climates, humid, months -0.5 winter, autumn, rainy, spring, summers, monsoon, winters, warmest, nights, coldestsnowfall, precipitation, seasons, humidity, temperatures, year, freezing, climates, humid, months -0.4 winter, autumn, rainy, spring, summers, monsoon, winters, warmest, nights, coldestsnowfall, precipitation, humidity, seasons, temperatures, year, freezing, climates, humid, months -0.3 winter, autumn, rainy, spring, summers, monsoon, winters, nights, warmest, coldestsnowfall, precipitation, humidity, temperatures, seasons, year, climates, freezing, humid, windy -0.2 winter, autumn, rainy, spring, summers, winters, monsoon, nights, warmest, coldestsnowfall, precipitation, humidity, temperatures, seasons, year, climates, humid, freezing, windy -0.1 winter, autumn, rainy, spring, summers, winters, monsoon, nights, warmest, coldestsnowfall, precipitation, humidity, temperatures, seasons, climates, year, humid, freezing, windy 0.0 winter, autumn, rainy, spring, summers, winters, monsoon, nights, warmest, coldestsnowfall, precipitation, humidity, temperatures, seasons, climates, humid, year, windy, freezing 0.1 winter, autumn, rainy, spring, summers, winters, monsoon, nights, warmest, coldestsnowfall, precipitation, temperatures, humidity, seasons, year, humid, climates, windy, freezing 0.2 winter, autumn, rainy, spring, summers, winters, monsoon, nights, warmest, coldestsnowfall, precipitation, temperatures, humidity, seasons, year, humid, climates, windy, sunny 0.3 winter, autumn, rainy, spring, summers, winters, monsoon, nights, warmest, snowfallcoldest, precipitation, temperatures, seasons, humidity, year, humid, windy, climates, sunny 0.4 winter, autumn, rainy, spring, summers, winters, nights, monsoon, snowfall, warmestcoldest, precipitation, seasons, temperatures, year, humidity, windy, humid, climates, days 0.5 winter, autumn, rainy, spring, summers, nights, winters, monsoon, snowfall, warmestcoldest, seasons, precipitation, year, days, temperatures, weekend, windy, sunny, humidity 0.6 winter, autumn, rainy, spring, nights, summers, winters, monsoon, snowfall, warmestcoldest, seasons, year, days, weekend, precipitation, annual, sunny, temperatures, month 0.7 winter, autumn, rainy, spring, nights, summers, winters, monsoon, snowfall, warmestdays, coldest, year, seasons, weekend, annual, week, sunny, month, snow 0.8 winter, autumn, spring, rainy, nights, winters, summers, days, monsoon, yearweekend, seasons, snowfall, annual, week, night, warmest, coldest, snow, month 0.9 winter, autumn, spring, nights, rainy, days, winters, summers, night, yearweekend, annual, week, seasons, monsoon, snow, holiday, rain, month, day 1.0 winter, autumn, spring, nights, rainy, days, night, week, annual, yearweekend, seasons, winters, snow, summers, day, holiday, rain, month, weather

Review summaries:
In this paper, the authors study the word embedding, with a particular emphasize on the word2vec or similar strategies. To this end, the authors consider the matrix factorization framework, previously introduced in the literature, and also study the influence of an hyperparameter denoted by alpha. Roughly speaking, there are two major parts in the paper. On one hand, it explains the reasons why the word embedding schemas provide nice properties, by defining the embedding as a low rank transformation mechanism. On the other hand, they propose to choose optimally the hyperparameter alpha in order to ameliorate word embedding by better preserving the distance structure. Conducted experiments are convincing.

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.

This paper provides a closer look at the well-studied problem of learning word embeddings. In particular, it looks at the set of embedding methods that explicitly or implicitly perform a matrix factorization and tries to understand why the word embeddings exhibit analogy structure and why words that are semantically similar get embedded close together. The mechanism it comes up with has to do with the alpha parameter that represents the powers of singular values of the matrix that was factorized to estimate the embeddings. It turns out that alpha controls the distance between the words in the embedding transformation process. Next the paper discusses how to choose/estimate alpha to get better quality embeddings. Results are shown on several word similarity tasks.