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.

summaries: 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.

summaries: 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.

abstractText: 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.

authors:
Eneko Agirre
Enrique Alfonseca
Keith Hall
Jana Kravalova
Marius Paşca
Aitor Soroa

title: A study on similarity and relatedness using distributional and wordnet-based approaches

venue: In Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics,

authors:
Carl Allen
Timothy Hospedales

title: Analogies explained: Towards understanding word embeddings

venue: In Proceedings of the 36th International Conference on Machine Learning,

authors:
Sanjeev Arora
Yuanzhi Li
Yingyu Liang
Tengyu Ma
Andrej Risteski

title: A latent variable model approach to pmi-based word embeddings

venue: Transactions of the Association for Computational Linguistics,

authors:
Mikel Artetxe
Gorka Labaka
Iñigo Lopez-Gazpio
Eneko Agirre

title: Uncovering divergent linguistic information in word embeddings with lessons for intrinsic and extrinsic evaluation

venue: In Proceedings of the 22nd Conference on Computational Natural Language Learning,

authors:
Yoshua Bengio
Réjean Ducharme
Pascal Vincent
Christian Jauvin

title: A neural probabilistic language model

venue: Journal of machine learning research,

authors:
Elia Bruni
Gemma Boleda
Marco Baroni
Nam-Khanh Tran

title: Distributional semantics in technicolor

venue: In Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics: Long Papers-Volume

authors:
John A Bullinaria
Joseph P Levy

title: Extracting semantic representations from word co-occurrence statistics: stop-lists, stemming, and svd

venue: Behavior research methods,

title: Experiments with LSA scoring: Optimal rank and basis

venue: In Proceedings of the SIAM Computational Information Retrieval Workshop,

authors:
Kenneth Ward Church
Patrick Hanks

title: Word association norms, mutual information, and lexicography

venue: Computational linguistics,

authors:
Scott Deerwester
Susan T Dumais
George W Furnas
Thomas K Landauer
Richard Harshman

title: Indexing by latent semantic analysis

venue: Journal of the American society for information science,

authors:
Kawin Ethayarajh
David Duvenaud
Graeme Hirst

title: Towards understanding linear word analogies

venue: arXiv preprint arXiv:1810.04882,

authors:
Lev Finkelstein
Evgeniy Gabrilovich
Yossi Matias
Ehud Rivlin
Zach Solan
Gadi Wolfman
Eytan Ruppin

title: Placing search in context: The concept revisited

venue: ACM Transactions on information systems,

authors:
Alex Gittens
Dimitris Achlioptas
Michael W Mahoney

title: Skip-gram- zipf+ uniform= vector additivity

venue: In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers),

authors:
Guillaume Lample
Miguel Ballesteros
Sandeep Subramanian
Kazuya Kawakami
Chris Dyer

title: Neural architectures for named entity recognition

venue: In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies,

authors:
Omer Levy
Yoav Goldberg

title: Linguistic regularities in sparse and explicit word representations

venue: In Proceedings of the eighteenth conference on computational natural language learning,

title: Neural word embedding as implicit matrix factorization

venue: In Advances in neural information processing systems,

authors:
Omer Levy
Yoav Goldberg
Ido Dagan

title: Improving distributional similarity with lessons learned from word embeddings

authors:
Thang Luong
Richard Socher
Christopher Manning

title: Better word representations with recursive neural networks for morphology

venue: In Proceedings of the Seventeenth Conference on Computational Natural Language Learning,

authors:
Laurens van der Maaten
Geoffrey Hinton

title: Visualizing data using t-sne

title: Large text compression benchmark

venue: URL: http://www. mattmahoney. net/text/text. html,

authors:
Tomas Mikolov
Kai Chen
Greg Corrado
Jeffrey Dean

title: Efficient estimation of word representations in vector space

venue: arXiv preprint arXiv:1301.3781,

authors:
Tomas Mikolov
Ilya Sutskever
Kai Chen
Greg S Corrado
Jeff Dean

title: Distributed representations of words and phrases and their compositionality

authors:
Tomas Mikolov
Wen-tau Yih
Geoffrey Zweig

title: Linguistic regularities in continuous space word representations

venue: In Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies,

authors:
Jeffrey Pennington
Richard Socher
Christopher Manning

title: Glove: Global vectors for word representation

venue: In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP),

authors:
Kira Radinsky
Eugene Agichtein
Evgeniy Gabrilovich
Shaul Markovitch

title: A word at a time: computing word relatedness using temporal semantic analysis

venue: In Proceedings of the 20th international conference on World wide web,

authors:
Gerard Salton
Christopher Buckley

title: Term-weighting approaches in automatic text retrieval

venue: Information processing & management,

authors:
Richard Socher
Alex Perelygin
Jean Wu
Jason Chuang
Christopher D Manning
Andrew Ng
Christopher Potts

title: Recursive deep models for semantic compositionality over a sentiment treebank

venue: In Proceedings of the 2013 conference on empirical methods in natural language processing,

authors:
Ilya Sutskever
Oriol Vinyals
Quoc V Le

title: Sequence to sequence learning with neural networks. In Advances in neural information processing

authors:
Fei Tian
Bin Gao
En-Hong Chen
Tie-Yan Liu

title: Learning better word embedding by asymmetric low-rank projection of knowledge graph

venue: Journal of Computer Science and Technology,

title: Domain and function: A dual-space model of semantic relations and compositions

venue: Journal of Artificial Intelligence Research,

authors:
Zi Yin
Yuanyuan Shen

title: On the dimensionality of word embedding

authors:
Torsten Zesch
Christof Müller
Iryna Gurevych

title: Using wiktionary for computing semantic relatedness

venue: In AAAI,

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


summaries: The paper considers random projection forests for similarity measurements (which have been proposed earlier) and proposes to accelerate them by reusing projections. Tree levels up-to level-X use distinct random transformations, and subsequent levels cycle through existing projections (X of them). As this kind of reuse reduces the quality of trees, the paper proposes to (greatly) increase the number of trees in the forest. The paper also introduces a sensible "beta-similarity" which is based on average tree-distance between leafs into which the two data-points fall, rather than fraction of trees in which they fall into the same leaf-node.

summaries: This paper proposes the similarity measure called 'beta-similarity' generated by an ensemble of Random projection trees (RP trees) by Dasgupta & Freund (2008). To reduce the computational costs for building many RP trees, the paper develops an efficient approximate version called X-Projection trees by first generating X independent random projection directions, and then by sharing them at layers in turns. X-Forest is a set of X-Projection trees with X different random projections, and the proposed 'beta similarity' between x and y is defined by distances between a leaf region having x and one having y in PR trees. Experimental evaluations demonstrated that the use of beta similarity improves the clustering accuracy using it within three types of methods (kernel k-means, DBSCAN, Spectral clustering).

summaries: This paper proposes a new method for measuring pairwise similarity between data points. The idea is to define the similarity between two data points to be the probability (over the randomness in constructing the trees) that they are close in an RP tree. More concretely, the proposed method constructs a collection of RP trees (albeit with some modifications), and takes the similarity to be the average over different RP trees of a strictly decreasing function of the distance between the leaf nodes containing the data points in each RP tree. The key modification to the RP tree is to limit the number of projection vectors used in an RP tree and re-use previous projection vectors.

abstractText: Similarity measurement plays a central role in various data mining and machine learning tasks. Generally, a similarity measurement solution should, in an ideal state, possess the following three properties: high accuracy, high efficiency in terms of speed and independence from prior knowledge. Yet unfortunately, vital as similarity measurements are, no previous works have addressed all of them. In this paper, we propose X-Forest, consisting of a group of approximate Random Projection Trees, such that all three targets mentioned above are tackled simultaneously. Our key techniques are as follows. First, we introduced RP Trees into similarity measurement such that accuracy is improved. In addition, we enforce certain layers in each tree to share identical projection vectors, such that exalted speed is achieved. Last but not least, we introduce randomness into partition to eliminate its reliance on prior knowledge. We conduct experiments on three real-world datasets, whose results demonstrate that our model, X-Forest, reaches an efficiency of up to 3.5 times higher than RP Trees with negligible compromise on its accuracy, while also being able to outperform traditional Euclidean distance-based similarity metrics by as much as 20% with respect to clustering tasks.

title: Multidimensional binary search trees used for associative searching

venue: Communications of the ACM,

authors:
Daniel Billsus
Michael J Pazzani

title: Learning collaborative information filters

venue: In Icml,

title: Comprehensive survey on distance/similarity measures between probability density functions

authors:
Yihua Chen
Eric K Garcia
Maya R Gupta
Ali Rahimi
Luca Cazzanti

title: Similarity-based classification: Concepts and algorithms

venue: Journal of Machine Learning Research,

authors:
Sanjoy Dasgupta
Yoav Freund

title: Random projection trees and low dimensional manifolds

venue: In STOC,

title: Random projection trees for vector quantization

venue: IEEE Transactions on Information Theory,

authors:
Sanjoy Dasgupta
Kaushik Sinha

title: Randomized partition trees for nearest neighbor

venue: search. Algorithmica,

authors:
Dheeru Dua
Casey Graff

title: UCI machine learning repository, 2017

venue: URL http://archive. ics.uci.edu/ml

authors:
Martin Ester
Hans-Peter Kriegel
Jörg Sander
Xiaowei Xu

title: A density-based algorithm for discovering clusters in large spatial databases with noise

venue: In Kdd,

authors:
Xiaoli Z Fern
Carla E Brodley

title: Random projection for high dimensional data clustering: A cluster ensemble approach

venue: In Proceedings of the 20th international conference on machine learning

authors:
Anton F. Fliri
William T. Loging
Peter F. Thadeio
Robert A. Volkmann

title: Biological spectra analysis: Linking biological activity profiles to molecular structure

venue: Proceedings of the National Academy of Sciences,

authors:
Katherine R Gray
Paul Aljabar
Rolf A Heckemann
Alexander Hammers
Daniel Rueckert

title: Alzheimer’s Disease Neuroimaging Initiative, et al. Random forest-based similarity measures for multi-modal classification of alzheimer’s disease

authors:
John A Hartigan
Manchek A Wong

title: Algorithm as 136: A k-means clustering algorithm

venue: Journal of the Royal Statistical Society. Series C (Applied Statistics),

authors:
Jasmine Irani
Nitin Pise
Madhura Phatak

title: Clustering techniques and the similarity measures used in clustering: A survey

venue: International Journal of Computer Applications,

authors:
Raymond Austin Jarvis
Edward A Patrick

title: Clustering using a similarity measure based on shared near neighbors

venue: IEEE Transactions on computers,

authors:
Abhinav K Jha
Jeffrey J Rodríguez
Renu M Stephen
Alison T Stopeck

title: A clustering algorithm for liver lesion segmentation of diffusion-weighted mr images

venue: IEEE Southwest Symposium on Image Analysis & Interpretation (SSIAI),

authors:
Marcus A. Koch
Lars-Oliver Wittenberg
Sudipta Basu
Duraiswamy A. Jeyaraj
Eleni Gourzoulidou
Kerstin Reinecke
Alex Odermatt
Herbert Waldmann

title: Compound library development guided by protein structure similarity clustering and natural product structure

authors:
Yogiraj Singh Kushawah
Ashish Mohan Yadav

title: A survey on unsupervised clustering algorithm based on k-means clustering

authors:
Wei-Ying Ma
Bangalore S Manjunath

title: Texture features and learning similarity

venue: In Proceedings CVPR IEEE Computer Society Conference on Computer Vision and Pattern Recognition,

authors:
David Minnen
Charles Isbell
Irfan Essa
Thad Starner

title: Detecting subdimensional motifs: An efficient algorithm for generalized multivariate pattern discovery

venue: In Seventh IEEE International Conference on Data Mining (ICDM

authors:
Andrew Y Ng
Michael I Jordan
Yair Weiss

title: On spectral clustering: Analysis and an algorithm

authors:
Ricardo S Santos
Suzana MF Malheiros
Sergio Cavalheiro
JM Parente De Oliveira

title: A data mining system for providing analytical information on brain tumors to public health decision makers

venue: Computer methods and programs in biomedicine,

authors:
Wei Shen
Xiang Bai
Zihao Hu
Zhijiang Zhang

title: Multiple instance subspace learning via partial random projection tree for local reflection symmetry in natural images

venue: Pattern Recognition,

authors:
Jianbo Shi
Jitendra Malik

title: Normalized cuts and image segmentation

venue: Departmental Papers (CIS), pp

authors:
Donghui Yan
Ling Huang
Michael I Jordan

title: Fast approximate spectral clustering

venue: In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining,

authors:
Donghui Yan
Yingjie Wang
Jin Wang
Honggang Wang
Zhenpeng Li

title: K-nearest neighbors search by random projection forests

venue: IEEE Transactions on Big Data,

heading: 1 Introduction

heading: 1.1 Background and motivation

text:
Similarity measurement is to measure the similarity between every pair of items in a given dataset. Generally, an item can be represented by a data point in the space (e.g., Euclidean space). The target of similarity measurement is to generate a similarity matrix M whose element Mij represents the similarity value between two data points: i and j.
Similarity measurement plays a central role in data mining and machine learning, and also has practical applications in other fields such as biochemistry, biology, botany, etc. In data mining, similarity is a vital criterion in unsupervised clustering which is to classify objects into groups and eliminate inappropriate data Santos et al. (2013); Kushawah & Yadav (2016); Jarvis & Patrick (1973). The result of clustering can be applied in various specific fields, e.g., the accurate segmentation of liver lesions Jha et al. (2010), the characterization of chemical structures and biological activity spectra Fliri et al. (2005), or for ligand identification Koch et al. (2004). In machine learning, similarity can be used in social filtering algorithms to make predictions for recommendation systems Billsus & Pazzani (1998).
Therefore, these extensive applications require the similarity measurement solution to maintain high accuracy in different datasets Ma & Manjunath (1996), and this is the first design goal of this paper. The second design goal is to achieve efficient similarity measurement.

heading: 1.2 Prior art and their limitations

text:
For similarity measurement, existing works can be divided into two kinds: mathematical distance-based similarity and multi-partition based similarity. Currently the prevailing approaches belong to the first kind of solutions, such as Minkowski distance family, Fidelity or Squared-chord family, Shannon’s entropy Cha (2007), Cosine similarity Irani et al. (2016), etc. These similarity measurement solutions only depend on the pairwise information (i.e., partial information), but neglect the overall information, such as the dimensions, features, distribution of the dataset. Consequently, they have low versatility, i.e., lacking the flexibility
to adapt to different datasets. Furthermore, they are not accurate enough, because they may not preserve the perceptual similarity (intuitive similarity) of the dataset, especially when encountered with high dimension datasets Ma & Manjunath (1996); Dasgupta & Freund (2008).
The second kind of solutions such as Multiple RP+EM Fern & Brodley (2003) and RF similarity Gray et al. (2013) overcome the shortcomings of the first kind by projecting and partitioning the data. Unfortunately, this kind of solutions often depends on priori knowledge about data distribution or data labels, which can hardly be acquired in common circumstances. Consequently, The third design goal of this paper is to eliminate the dependence on priori knowledge. No existing works can achieve all the design goals at the same time.

heading: 1.3 Our contributions

text:
This paper aims to achieve the above three design goals at the same time. Towards the first and third goal, we introduce the Random Projection Tree (RP Tree) to similarity measurement. RP Tree is used to randomly partition a set of data points in a space into several disjoint subsets. It is well known that in an RP Tree, data points that are closely distributed, indicating their high level of similarity in space, are always partitioned into the same subset Dasgupta & Freund (2008). This means that RP Tree can achieve the first goal – high accuracy. As RP Tree uses random partitions, thus achieves the third goal – eliminating priori knowledge dependence.
Unfortunately, directly using RP Tree cannot achieve the second goal – high efficiency, because during each partition, we need to project all data points into a random vector which is time consuming (see details in Section 2). To address this problem, we propose the X-Forest. The key idea is to allow nodes at i, i+X, i+ 2X... (i=0,1,2...) layers of the tree to share the same projection vector for partitioning. For example, let us assume that we are given a complete binary RP Tree with 4 layers. The root node denotes the entire dataset and each node denotes a subset of the entire dataset. For each inner node, the standard RP Tree needs to project all data points into one random vector. In this way, it projects each data point four times. Our solution is to let the nodes at the first and third layers share the same projection vector, and do so for the second and fourth layers. For the nodes at the third layer, we reuse the projection results of the first layer, and do so for the four layer. In this way, we project each data point twice instead of four times.
Obviously, sharing vectors sacrifices the randomness of projection vectors, further degrading the accuracy. Fortunately, the accuracy loss can be almost eliminated by using a great many Trees and carefully choosing the sharing parameter – X (see details in Section 3.2).
We propose β-Similarity to record the results in X-Forest into a similarity matrix. It features better representing the similarity relationship between data points, which is proved by the higher accuracy in our clustering experiments.
Our key contributions are as follows:
• We introduce RP Trees into similarity measurement and proposed a new similarity matrix β-Similarity, which better reveals the similarity relationships between data points than traditional distance based similarity measurement.
• We propose X-Forest which significantly reduces the time of building procedure of RP Trees by sharing projection vectors. • We conduct extensive experiments on three real datasets, and our experimental results show that RP Trees achieves two design goals, while X-Forest achieves all three desigan goals at the same time.
We have released codes in github anonymously so as to meet the demand of reproducibility sou. The mathematical proofs of our algorithm is detailed in supplementary materials.

heading: 2 Background and Related Work

heading: 2.1 Similarity Measurement

text:
Existing solutions for similarity measurement can be classified into two categories: 1) mathematical distance based similarity and 2) multi-partition based similarity.
The first kind is Mathematical distance based similarity which is widely used. It includes Minkowski distance family, Fidelity or Squared-chord and Shannon’s entropy Cha (2007), Cosine similarity Irani et al. (2016), the correlation coefficient Billsus & Pazzani (1998), travel time, and edit distance Chen et al. (2009), etc. According to the applying method of distance, it can be divided into two cases: 1) distance is directly applied as similarity; 2) distance is first computed as a criterion for further similarity evaluation. An example of the second case is shared neighbours based clustering Jarvis & Patrick (1973). The k nearest neighbours of each data point are found using Euclidean distance. The similarity between data point i and j is defined as the number of common neighbours.
Existing works of the second kind, multi-partition based similarity, is rare, and an example is Multiple RP+EM Fern & Brodley (2003). In each operation of RP+EM, the dimension of the original dataset is degraded through a linear transformation. Then, it applies EM clustering to generate a probabilistic model θ of a mixture of k Gaussians. The similarity between data points i and j is defined as the average value of P θij = ∑k l=1 P (l | i, θ)×P (l | j, θ) of each RP+EM.
The first kind of solutions falls short in terms of leading to unsatisfied results, especially in high-dimensional spaces. And the second kind depends on prior knowledge about data labels or data distribution.

heading: 2.2 Random Projection Tree

text:
Sanjoy Dasgupta and Yoav Freund first propose the idea of RP Tree Dasgupta & Freund (2008). An RP Tree is a variant of k − d tree Bentley (1975). The most popular application of RP Tree is in nearest neighbours finding, where it compensates k − d tree’s diminishing efficacy in high-dimensional spaces Dasgupta & Sinha (2015). Other applications of RP Tree cover clustering Yan et al. (2009), pattern discovering Minnen et al. (2007) and nearest neighbours finding, vector quantization Dasgupta & Freund (2009), local symmetry detection in natural images Shen et al. (2016), etc.
The details of building an RP Tree are as follows. In an RP Tree, the root node includes all items in a given set S. Through RP operation, RP Tree partitions S into two disjoint sets, each of which is a child node of the root node. The child node will be recursively partitioned until its size is smaller than a predefined threshold τ . In the end, each leaf node of an RP Tree forms a set of size less than τ . Figure 2 shows the structure of an RP Tree. The main operation of RP Tree, the RP operation, generates a random unit direction vector e for each partition. After all data points have been projected into the random direction, we uniformly choose a partition point at random within the projection range, where the projection range refers to the interval between the smallest and the largest projection value.
The formal description of an RP operation is as follows. RP Tree computes the projection value of each point in the set S into the unit directional vector e. Let P be the set of projection values, i.e., P = {x · e | x ∈ S}. Let Pmax be the maximum value in P and Pmin be the minimum value in P . The partition point Pτ is uniformly and randomly selected from
(Pmin,Pmax). Pτ partitions the set S into two disjoint subsets SL = {x · e 6 Pτ | x ∈ S} and SR = {x · e > Pτ | x ∈ S}. This is equivalent to partitioning the space into two parts with a (d− 1)-dimensional hyperplane xT · e = Pτ . When d = 2, as shown in Figure 1, the (d − 1)-dimensional hyperplane degrades to a line. Building an RP Tree suffers from high computation complexity since, a large number of RP operations are involved whenever an RP Tree is built, worsened by the fact that, it requires another large number of inner products to complete a single RP operation.

heading: 3 The X-Forest Algorithm

text: As detailed in Section 2.2, RP Tree cluster similarly data points into the same node. In this section, we first show how to use a number of RP Trees to generate the similarity matrix. Then we introduce X-Forest, which significantly accelerate the building procedure of these trees.

heading: 3.1 Similarity Matrix Generation

text:
In an RP Tree, two data points are regarded as similar if they are in the same leaf node. Therefore, given a number of trees that are built independently, we can consider the probability that two data points fall into the same leaf node as their similarity. Based on this idea, the well known similarity matrix is defined as follows.
Definition 1 Given m RP Trees T1, ..., Tm, for RP Tree Ti, suppose a data point xj belongs to the leaf node Li(xj) . The basic similarity matrix Mbasic is defined as
Mbasicjk = 1
m ( m∑ i=1 I [Li(xj) = Li(xk)] ) (1)
, where I is the indicator function.
The basic similarity matrix is the average of some 01 matrix, and each 01 matrix is a similarity matrix generated by one RP Tree. In a 01 matrix, the similarity between data points falling into the same leaf node is 1 and the similarity between data points falling into different leaf nodes is 0.
This definition does not consider the information of the structure of the RP Tree. This leads to the 01 matrix is too sparse, i.e., has a large number of 0s. To show that, consider the following example. Given n data points to build an RP Tree with each leaf nodes containing r data points, this RP Tree has nr leaf nodes and each leaf node fills the similarity matrix with r2 1s. Therefore, the size of this 01 matrix generated by this RP Tree is n2, but only nr elements are 1, accounting for rn of all elements (e.g. n = 150, r = 3, 1 accounted for only 0.02). The issue is that the similarity of data points in different leaf nodes should be a number between 0 and 1 rather than 0. Thus we can get a matrix better representing the similarity between data points, by reasonably eliminating some 0s. To achieve this, we need to consider information about the whole structure of an RP Tree. If the distance between two data points in an RP Tree is short (i.e., they are divided later), we should define their similarity as a value closer to 1. If the distance between two data points in an RP Tree is long (i.e., they are divided earlier), we should define their similarity as a value closer to 0. Based on this observation, we propose the β-Similarity matrix.
Definition 2 Given an RP Tree Ti, let DISi(X, Y) be the distance between nodes X and Y in Ti. The β-Similarity matrix Mβ is defined as
Mβjk = 1
m ( m∑ i=1 β DISi(Li(xj),Li(xk)) ) (2)
Here β is a parameter controlling the speed at which the similarity decays with increasing distance. When β → 0, the β-Similarity matrix degenerates into the basic similarity matrix. We use the most popular Iris flower dataset Dua & Graff (2017) to compare the basic similarity and β-Similarity and the result is shown in Figure 3. For basic similarity, most data points in the same class (number 1-50) have rather low similarity. For β-Similarity, the similarity between data points in the same class is significantly greater than that of the data points in different classes. In our experiments, we find that the accuracy of clustering can be significantly improved by properly choosing β (Figure 8 ).

heading: 3.2 X-Projection Tree and X-Forest

text:
Generating a similarity matrix requires a large number of different RP Trees. However, the process of building such a large number of RP Trees is rather slow. To address this issue, we propose X-Forest. The key idea is to allow nodes at i, i+X, i+ 2X, ...(i = 1, 2, ...) layers of the tree to share the same direction vector.
In order to introduce the X-Forest, we first introduce an equivalent RP Tree called Layer-by-Layer RP Tree. Compared to the standard RP Tree, Layer-by-Layer RP Tree allows nodes in each layer share the same projection direction. An example of a Layer-by-Layer RP Tree is shown in Figure 4. Theoretically, the Layer-by-Layer RP Tree is equivalent to the standard RP tree. Here we give a brief explanation: For a standard RP Tree, the partition of each node on the tree relies on a series of independent projection directions. Intuitively, a random partition of the dataset demands each data point to go through a series of mutually independent partitions. Thus, in an RP Tree, the nodes which are ancestor-descendant related (ADR) need mutually independent projection directions, and the nodes which are not ADR can share the same projection directions. Specifically, it is sufficient that the projection directions used by different layers are mutually independent. This shows the equivalence between the standard RP Tree and Layer-by-Layer RP Tree.
To further explore other avenues to economize computation time, X-Forest allows different layers share the same projection directions. Sharing projection directions sacrifices the randomness of partition, further affecting the similarity generated. To implement the tradeoff between speed and accuracy, we give a method by adjusting the sharing parameter X.
Here we describe the details about building an X-Forest, which is a group of X-Projection Trees. Given a dataset S, for each X-Projection Tree, we select X independent random projection directions e0, e1, · · · , eX−1, and compute the projection value of all data points into the X projection directions, i.e. Pi = {x · ei | x ∈ S}. When building an X-Projection
Tree, we rely on the following idea to allow data sharing of the projection directions: the root node uses the first projection direction e0 for partitioning. The node in the i-th layer uses the (i mod X)-th projection direction e(i mod X), and uses the pre-calculated projection value in P(i mod X) to partition the set. The rest of the recursive tree construction is identical to standard RP Tree. Figure 5 shows an example of using X = 2 version of X-Projection Tree to partition data points.
The X-Projection Tree is equivalent to a Layer-by-Layer RP Tree when its depth is no greater than X. When X = 1, it is equivalent to using a series of parallel (d− 1)-dimension hyperplanes to partition the space. This is the most efficient case because only one RP operation is required. According to our experimental analysis, we find out that: 1) the X = 2 version of X-Forest achieves the best trade-off between improvement in computational efficiency and loss in partition precision. 2) the X = 4 version of X-Forest almost achieves the accuracy of Layer-by-Layer RP Trees, while requiring little additional time compared to the X = 2 version. Further experimental details are discussed in Section 5.
Here we provide an analysis of the computational complexity of X-Forest. Given a ddimensional dataset S with n data points, for m RP Trees, the time complexity of building trees and generating the similarity matrix is O(m · n · (n + log n · d)) in the average, and O(m · n2 · d) in the worst case. And the complexity for X-Forest made of m X-Projection Trees is always O(m · n · (n+X · d)). Therefore, X-Forest is especially suitable for datasets satisfying d n/ log n. In term of implementation, X-Forest can calculate Pi in parallel for all projection directions. For the standard RP Tree, parallel acceleration cannot be used because information about which set of data points is to be projected into each direction remains uncertain.

heading: 4 Applications of X-Forest

text:
In this section, we demonstrate how to apply the similarity matrix to some classical clustering algorithms, including Kernel K-means, density clustering, and spectral clustering.
Kernel K-means: K-means Hartigan & Wong (1979) is the most popular unsupervised clustering algorithm. It partitions all data points into K clusters by finding K optimal cluster centers. The optimization goal is to minimize the sum of the distances of each data point to its nearest cluster center. The Kernel K-means is an optimization of K-means clustering. The input data points are mapped into a feature space using a nonlinear mapping φ. A kernel function Fjk = 〈φ(xj), φ(xk)〉 is used to calculate the distance in feature space. For this application, X-Forest maps data points to unit vectors in the feature space, and the kernel function is given by the similarity matrix M.
Fjk = 〈φ(xj), φ(xk)〉 = Mjk (3)
Density clustering: DBSCAN Ester et al. (1996) is the most popular density-based clustering method. In DBSCAN, a point is considered as a dense part if its -neighborhood has enough points. In the process of clustering, DBSCAN arbitrarily selects an unvisited dense part and its -neighborhood as a cluster, and recursively adds the -neighborhoods of the dense parts already added into this cluster, until no more points can be added. This process is repeated until all dense parts are visited.
In this application, the similarity matrix M can be used to express the inner product of two data points in the feature space φ. The distance of any two data points in the feature space can be obtained by the following formula.
‖φ(xj)− φ(xk)‖2 = (〈φ(xj)− φ(xk), φ(xj)− φ(xk)〉) 1 2 = √ (2− 2 ·Mjk) (4)
Spectral clustering: Spectral clustering Ng et al. (2002); Shi & Malik (2000) is an algorithm derived from graph theory and has been widely used in clustering. By defining the weight (similarity) between two data points, spectral clustering embeds data points into
an undirected weighted complete graph. The complete graph is divided into K sub-graphs by cutting off the edge set with minimum weight to achieve the purpose of clustering.
Classic spectral clustering uses exp ( −‖xj − xk‖2/2σ2 ) as the weight of the edge, where σ is the bandwidth of the graph. In this application, we directly use Mjk of the similarity matrix M as the edge weight.

heading: 5 Experimental Results

text: We first show the accuracy improvement of some classical clustering methods after using the β-Similarity generated by X-Forest. Then, we compare the performance in terms of computation time of X-Forest under different parameter settings.

heading: 5.1 Experimental Setup

text:
Choice of Datasets: As is shown in Table 1, we conduct experiments on three real datasets from the UC Irvine machine learning library Dua & Graff (2017), including Wine, Soybean and WDBC. All three datasets are labeled, allowing us to evaluate the actual performance of the clustering.
Choice of Clustering Algorithms: In the first part of this section, we compare the accuracy of Kernel K-means, Density Clustering and Spectral Clustering using β-Similarity generated by X-Forest and distance similarity. In the second part, we use Kernel K-means as clustering algorithm to compare the performance of X-Forest under different parameter settings.
Evaluation Metrics: We use Accuracy as an evaluation metric of the performance of clustering. The definition of Accuracy is given by the formula below. It measures the fraction of matching labels given by the clustering algorithm divided by the real label.
Definition 3 Let S = {x1 : y1,x2 : y2, · · · ,xn : yn} be the dataset, ŷ(.) be the label obtained by the clustering algorithm, and σ(.) be the permutation of n elements.
Accuracy = max σ
( 1
n n∑ i=1 I [ŷ(xi) = σ(yi)]
) (5)
Default Configuration: Table 2 shows the default parameter configuration of X-Forest on 3 data sets, and lists the average depth of the X-Projection trees on these datasets. Since all the average depths are between 8 and 16, we regard the X = 16 X-Forest as standard RP Trees and layer-by-layer RP Trees. In the experiment, we generate 1000 similarity matrices for each parameter configuration and show the average value of Accuracy and Time. All experiments are conducted on laptop with 2.6 GHZ Intel Core i7 CPU.

heading: 5.1.1 Experiments on Accuracy

text:
Accuracy vs. Different Similarity (Figure 6): In this experiment, we use different clustering algorithms (Kernel K-means, DBSCAN, Spectral Clustring) and different similarity measurements (β-Similarity, distance similarity). Figure 6 shows that the Accuracy of Kernel K-means using β-Similarity are respectively about 11.1%, 9%, 24% higher than the of that of using distance similarity on the three datasets. The Accuracy of DBSCAN using β-Similarity are respectively about 27.6%, 5.5%, 33.7% higher than that of using distance similarity on the three datasets. The Accuracy of Spectral Clustering using β-Similarity are respectively about 21.3%, 28.6%, 34.8% higher than that of using distance similarity on the three datasets.
Accuracy vs. β (Figure 8): In this experiment, we change β ([0, 1)) and use Kernel K-means for clustering. For the soybean dataset (Figure 8(a)), the accuracy of the β = 0.9 version of β-Similarity is about 25.9% higher than that of the β = 0 version of
β-Similarity. For the WDBC dataset (Figure 8(b)), the accuracy of the β = 0.7 version of β-Similarity is about 0.9% higher than that of the β = 0 version of β-Similarity, while the variance is 5.28 times smaller. For the wine dataset (Figure 8(c)), the accuracy of the β = 0.9 version of β-Similarity is about 3.8% higher than that of the β = 0 version of β-Similarity , while the variance is 2.16 times smaller.

heading: 5.1.2 Experiments on Speed

text: Building Speed X-Forest vs. X (Figure 9): In this experiment, we vary X (1, 2, 4, 8, 16) and the number of X-Projection trees (160, 320, 640, 1280) in X-Forest and use Kernel K-means for clustering. When the number of X-Projection trees is 1280, for the soybean dataset (Figure 9(a)), the speed of the X = 2 and X = 4 versions of X-Forest are respectively about 2.98 and 1.74 times faster than standard RP Trees. For the WDBC dataset (Figure 9(b)), the speed of the X = 2 and X = 4 versions of X-Forest are respectively about 3.61 and 2.57 times faster than standard RP Trees. For the wine dataset (Figure 9(c)), the speed of the X = 2 and X = 4 versions of X-Forest are respectively about 1.34 and 1.03 times faster than standard RP Trees.

heading: 6 Conclusion

text: The design goals of an ideal similarity measurement solution are respectively high accuracy, high efficiency in terms of speed and independence from priori knowledge of the dataset. We propose X-Forestto achieve all the above goals: 1) We introduce RP Tree into similarity measurement because it better represents the similarity value between item pairs; 2) We manage to reduce computational time through sharing projection values in the partition process of some layers; 3) We rely on randomness in partition to get rid of the need of priori knowledge of the dataset, such as data distribution characteristics.

heading: A Appendix

text:
The growth of the individual X-Projection Tree in X-Forest involves randomness both in projection directions and partition thresholds. A natural concern of the X-Forest would be whether the distances in the similarity kernel maintain the characteristics of the Euclidean space Rn. In this appendix, we will prove that during the growth of the X-Forest, far-away points in the Euclidean space will be partitioned with higher probability than the near points.
Recall that during the partition of a tree node, we will choose a partition threshold randomly in the range of the projection values. As the behavior of the partition depends on this range, we first introduce the definition of the range as follows
Definition 4 Let S be a set of points. Define the range of one particular projection as the following
L(S, e) = sup x1,x2∈S {|x1 · e− x2 · e|}
and define its boundaries as ρ(S) = sup
e∈I L(S, e)
δ(S) = inf e∈I L(S, e)
where I is the set of unit direction vectors, i.e., I = {e | e ∈ Rn ∧ ‖e‖ = 1}.
The upper bound ρ(S) can be seen as the largest distance of two points in Rn, and the lower bound δ(S) is called neck size in Yan et al. (2019). Based on this definition, we will state that the probability of two points not being partitioned in a tree can be bounded by a function. Without loss of generality, we give the theorem and the proof under the 2-dimensional case with X = 2. When it comes to the high-dimensional, the proof can become much more difficult because projection directions are chosen on the hyper-sphere. This may be desirable for the future work.
Theorem 1 Let S be a set of points in R2 on which the algorithm X-Forest runs. Given two point A,B ∈ S having distance l, the probability of this two point not being partitioned in a X-Projection Tree after 2n steps satisfies
Pr(A and B not partitioned) ≤ F 2n ( l ρ(S) )
Fn(x) := 2
π(n− 1)!
∫ π 2
0
dθ ∫ 1 xcos(θ) (− log z)n−1 dz
Proof. Let V be a random variable defined as below
V = { 0, A and B not partitioned 1, otherwise
Since the parameter is set as X = 2, two projection directions will be chosen at the beginning of the algorithm. Let a, b represent them respectively. Let Y1, Y2 be random variables representing the angle between the two directions and AB respectively. It is obvious that the angle locates in the interval [0, π/2]. Because these vectors are uniformly and independently chosen at random from I, we have Y1, Y2 ∼ i.i.d U[0,π/2]. We first analyze the probability of A and B not being partitioned given particular θ1 and θ2, i.e., Pr (V = 0 | Y1 = θ1, Y2 = θ2). We notice that the partition performed on the direction a affects the partition on direction b. This is because the partition on direction a will reduce the elements of S, which shrinks the length L(S,b). If we assume that partitions on two directions are independent with each other, then this shrink will not happen. In this case, the probability of A and B not partitioned in a tree becomes larger. That is
Pr(V = 0 | Y1 = θ1, Y2 = θ2) ≤ Pr(Va = 0 | Y1 = θ1) · Pr(Vb = 0 | Y2 = θ2) (6)
where Va and Vb are random variables representing whether point A and B are partitioned on direction a and b respectively, similar to V . It is obvious that Pr(Va = 0 | Y1 = θ1) has the same form as Pr(Vb = 0 | Y2 = θ2), therefore we just need to focus on the direction a. Recall that when the depth of a tree node is even, direction a will be used. Therefore, n partition thresholds will be chosen on direction a. We can simplify the procedure of choosing n partition thresholds as shrinking the total length L(S,a) by n times. The probability of the final total length being bigger than l cos(θ1) is the probability of the two points A and B not being partitioned in direction a. In our algorithm, the partition threshold is uniformly chosen at random in the current range recursively, which means that the shrink factor satisfies U[0,1]. Therefore, we have
Pr(Va = 0 | Y1 = θ1) = Pr ( L(S,a) · Z1Z2 · · ·Zn ≥ l cos(θ1) ) = Pr ( Z(n) ≥ l cos(θ1)
L(S,a)
) (7)
where Z1, Z2, . . . , Zn are i.i.d random variables such that Zi ∼ U[0,1], and Z(n) is the product of Z1, Z2, . . . , Zn.
We now derive the upper bound of the probability as the following
Pr(V = 0) = Pr ( V ≤ 0, Y1 ≤ π
2 , Y2 ≤
π
2 ) = ∫ π 2
0
dθ1
∫ π 2
0
dθ2 · Pr(V = 0 | Y1 = θ1, Y2 = θ2) · fY1(θ1) · fY2(θ2)
where fY1 and fY2 is the probability density function (PDF) of Y1 and Y2. Combining (6), (7) and the result from Lemma 2, we find
Pr(V = 0) ≤ ∫ π 2
0
dθ1
∫ π 2
0
dθ2 · Pr ( Z(n) ≥ l cos(θ1)
L(S,a)
) · Pr ( Z(n) ≥ l cos(θ2)
L(S,b) ) · 4 π2
≤ 4 π2
∫ π 2
0
dθ1
∫ π 2
0
dθ2 · Pr ( Z(n) ≥ l cos(θ1)
ρ(S)
) · Pr ( Z(n) ≥ l cos(θ2)
ρ(S) ) = 4
π2(n− 1)!2
∫ π 2
0
dθ1
∫ π 2
0
dθ2 ∫ 1 l cos(θ1)
ρ(S)
dz1 ∫ 1 l cos(θ2)
ρ(S)
dz2 · (log z1 log z2)n−1
= F 2n ( l ρ(S) )
The inequality of Theorem 1 shows that the probability of the two point not being partitioned has an upper bound F 2n(l/ρ(S)). However, the reader may want to know whether Fn gives a reasonable bound for the probability. Therefore, we give a lemma to further illustrate the feature of Fn.
Lemma 1 Fn(x) is a strictly monotonically decreasing function with respect to x in (0, 1), and satisfies
Fn(0) = 1 , Fn(1) = 0
Proof. First we prove that Fn is strictly monotonically decreasing. It is obvious that (− log z)n−1 > 0 for any z ∈ (0, 1). Therefore, given x1, x2 ∈ (0, 1) such that x1 < x2, we have
∫ 1 x1cos(θ) (− log z)n−1 dz > ∫ 1 x2cos(θ) (− log z)n−1 dz
Apply the inequality above to the expression of Fn yields
Fn(x1) = 2
π(n− 1)!
∫ π 2
0
dθ ∫ 1 x1cos(θ) (− log z)n−1 dz
> 2
π(n− 1)!
∫ π 2
0
dθ ∫ 1 x2cos(θ) (− log z)n−1 dz
= Fn(x2)
which indicates that Fk is strictly monotonically decreasing. Now we calculate
Fn(0) = 2
π(n− 1)!
∫ π 2
0
dθ ∫ 1 0 (− log z)n−1 dz
= 1
(n− 1)! ∫ 1 0 (− log z)n−1 dz
= 1
(n− 1)! ∫ ∞ 0 un−1 · e−u du (u = − log z)
= 1
(n− 1)! Γ(n)
= 1
Fn(1) = 2
π(n− 1)!
∫ π 2
0
dθ ∫ 1 1 (− log z)n−1 dz
= 0
The combination of Theorem 1 and Lemma 1 shows that the probability of far-away points not being partitioned in a X-Projection Tree is low. This is because far-away points will have a bigger l, resulting in a smaller F 2n(l/ρ(S)) which approaches 0. On the other hand, near points will have a loose upper bound approaching 1, therefore they are more likely to stay together. In summary, we state that the characteristics of the Euclidean space are maintained in our X-Forest algorithm.
Lemma 2 Suppose Z1, Z2, . . . , Zn are i.i.d random variables such that Zi ∼ U[0,1]. Let Z(n) = Z1Z2 · · ·Zn. The probability density function (PDF) of Z(n) is
fZ(n)(x) =
{ (− log x)n−1
(n−1)! , 0 < x ≤ 1 0, otherwise
Proof. We use mathematical induction on n to prove the lemma.
Base case. When n = 1, we have Z(n) = Z1 ∼ U[0,1]. Obviously the statement is true.
Inductive step. Assume the statement holds for n = k. For brevity, we rewrite fZ(k)(x) as fk(x).
First we calculate the cumulative distribution function (CDF) of Z(k + 1) based on the assumption. For x ∈ [0, 1] we find
Pr ( Z(k + 1) ≤ x ) = ∫ 1 0 Pr ( Z(k + 1) ≤ x | Z(k) = y ) fk (y) dy
= ∫ x 0 1 · fk (y) dy + ∫ 1 x x y · fk (y) dy
= Pr ( Z(k) ≤ x ) + x ∫ 1 x fk (y) y dy
Differentiating both sides we have
fk+1 (x) = fk (x) + ∫ 1 x fk (y) y dy − x · fk (x) x
= ∫ 1 x fk (y) y dy
= ∫ 1 x (− log y)k−1 (k − 1)! · 1 y dy
= ∫ 0 log x (−t)k−1 (k − 1)! dt (t = log y)
= (− log x)k
k · (k − 1)!
Therefore, the statement holds for n = k+ 1 when x ∈ [0, 1]. For x < 0 or x > 1, it is obvious that fk+1(x) = 0. In summary, the lemma holds for n = k + 1.

title: X-Forest: Approximate Random Projection Trees for Similarity Measurement