Context Vectors Are Reflections of Word Vectors in Half the Dimensions (Extended Abstract)

1 Introduction andMain Result

Today word embeddings play an important role in many natural language processing tasks, from predictive language models and machine translation to image annotation and question answering, where they are usually plugged into a larger model. An understanding of their properties is of interest as it may allow the development of embeddings that are better both in interpretability and quality of models built upon them. This paper takes a step in this direction.

Notation: We let R denote the real numbers. Bold-faced lowercase letters (x) denote vectors in Euclidean space, boldfaced uppercase letters (X) denote matrices, plain-faced lowercase letters (x) denote scalars, plain-faced uppercase letters (X) denote scalar random variables, 'i.i.d.' stands for 'independent and identically distributed'. We use the sign ∼ to abbreviate the phrase 'distributed as', and the sign ∝ to abbreviate 'proportional to'.

Assuming that words have already been converted into indices, let {1, . . . , n} be a finite vocabulary of words. Following the setup of the widely used WORD2VEC model [Mikolov et al., 2013], we will use two vectors per each word i:

∗This paper is an extended abstract of an article in the Journal of Artificial Intelligence Research [Assylbekov and Takhanov, 2019].

1 Our modification of the SGNS is available at https://github.com/ zh3nis/word2vec wt

• wi is an embedding of the word i when i is a center word,
• ci is an embedding of the word i when i is a context word.

We make the following key assumptions in our work.

Assumption 1. A priori word vectors w1, . . . ,wn ∈ Rd are i.i.d. draws from isotropic multivariate Gaussian distribution:

This is motivated by the work of Arora et al. [2016], where the ensemble of word vectors consists of i.i.d. draws generated by v = s · ˆv, with ˆv being from the spherical Gaussian distribution N(0, I), and s being a scalar random variable with bounded expectation and range. In their work, the norm ‖vi‖ of the word vector for a word i is related to its unigram probability p(i), and to allow a sufficient dynamic range for these probabilities they needed the multiplier s. In our work, unigram probabilities are not mapped to vector lengths, and this is why we do not need such multiplier. Direct relationship between word probabilities and word vector norms is also implied by the model of Hashimoto et al. [2016].

Assumption 2. Context vectors c1, . . . , cn are related to word vectors according to

Notice, that ci iid∼ N (0, 1d I) .

This is mainly guided by the work of Press and Wolf [2017], who showed that context vectors in the SGNS model of Mikolov et al. [2013] are distributed similarly to word vectors in the sense that pairwise cosine distances between word (input) embeddings strongly correlate with the corresponding pairwise cosine distances between context (output) embeddings (see their Table 4). This is why we choose the transform from word vectors to context vectors to be orthogonal as it preserves inner products and consequently Euclidean norms.

Assumption 3. Given a word j, the probability of any word i being in its context 2 is given by

2 Context is a fixed-size symmetric window around the given word.

where pi = p(i) is the unigram probability for the word i, which is inverse proportional to its smoothed frequency rank ri, i.e.

This is similar to the log-linear model of Arora et al. [2016], but differs in the following aspects: ci is not assumed to do a random walk over the unit sphere with bounded displacement; we use the factor pi to directly capture word frequencies and do not model them via vector norms. Equation (3) can be interpreted as follows: probability that the word i occurs in the context of the word j is the probability that the word i occurs anywhere in a large corpus, corrected for the relationship between words i and j. This approach was already considered by Melamud et al. [2017] but in their work i is the entire left context of the word j, and ci is a vector representation of this entire context. Also, like Arora et al. [2016] but unlike Melamud et al. [2017], we use the model (3) for a theoretical analysis rather than for fitting to data. Smoothing of the unigram probabilities (i.e. raising them to power 1-α) is motivated by the works of Mikolov et al. [2013], Levy et al. [2015], Pennington et al. [2014], where α = 0.25 is a typical choice. We notice here that α = 0+ gives us Zipf's law [Zipf, 1935], whereas α = 1 gives us uniform distribution of word frequencies which is not valid empirically but on the other hand can be used to explain additivity of word vectors [Gittens et al., 2017].

The relationship between word (input) and context (output) vectors was addressed in several previous works. E.g., in recurrent neural network language modeling (RNNLM), tying input and output embeddings is a useful regularization technique introduced earlier [Bengio et al., 2001] and studied in more details recently [Press and Wolf, 2017; Inan et al., 2017]. This technique improves language modeling quality (measured as perplexity of a held-out text) while decreasing the total number of trainable parameters almost two-fold since most of the parameters in RNNLM are due to embedding matrices. The direct application of this regularization technique to SGNS worsens the quality of word vectors as was shown empirically by Press and Wolf [2017] and by Gulordava et al. [2018]. This worsening was predicted earlier by Goldberg and Levy [2014] using a simple linguistic observation that words usually do not appear in the contexts of themselves. This basically means that Q ̸= I in (2). At the same time, there is empirical evidence that the relationship between input and output embeddings is linear [Mimno and Thompson, 2017; Gulordava et al., 2018]. In this paper, we provide a theoretical justification for this and reveal the exact form of the transformQ. Our main contribution is the following

Theorem 1. Under Assumptions 1, 2, and 3 above, the context vector ci for a word i is a reflection of the word vector wi in approximately half of the dimensions.

In general, our word and context vectors live in a ddimensional vector space over real numbers (Rd ). By Theorem 1 we can settle them in a d/2-dimensional vector space over complex numbers (Cd/2 ) in such way that the context vector ˜ci ∈ Cd/2 for a word i is the complex conjugate of the word vector ˜wi ∈ Cd/2 . This is in line with the results of Allen et al. [2019], however they use a completely different set of basic assumptions and their primary goal is to encode statistical properties of words directly into word vectors.

2 Proof Sketch of Theorem 1

The proof is divided into three steps: first we show that the partition function in (3) concentrates around 1, and thus ∝ can be replaced by ≈; using this fact we show that Q is (approximately) an involutary matrix, i.e. similar to diag(q), q ∈ {+1,-1}d ; and finally we show that the word-word pointwise-mutual information matrix (PMI) is approximately a symmetric Gaussian random matrix with weakly dependent entries. Based on the theory of random matrices, the latter fact immediately implies a symmetric around 0 distribution of the PMI eigenvalues, and thus the statement of the Theorem 1.

The complete proof can be found in the full version [Assylbekov and Takhanov, 2019].

3 Empirical Verification

In this section we empirically verify two predictions of our theory: a symmetric distribution of a PMI spectrum and the involutarity of a matrix transforming input embeddings into output ones.

3.1 Symmetry of a PMI Spectrum

To verify that the real-world PMI matrices have indeed a symmetric (around 0) distribution of their eigenvalues, we consider a widely-used dataset text8 3 that consists of 17M tokens and from which we extract PMI matrices using the HYPERWORDS tool of Levy et al. [2015]. We use the default settings for all hyperparameters, except the word frequency threshold and context window size. We were ignoring words that appeared less than 100 times, resulting in a vocabulary of 11,815 words. We additionally experiment with the context window size 5, which by default is set to 2, and which we believe could affect the results. By default, HYPERWORDS zeroes out an entry PMIi,j if the words i and j do not co-occur in the corpus. 4 The eigenvalues of the PMI matrices are calculated using the TENSORFLOW library. The histograms of eigenvalues are provided in Figure 1. As we can see, the distributions are not perfectly symmetric with a little right skewness, but in general they seem to be symmetric. Notice, that this is in stark contrast with the equation (2.5) from Arora et al. [2016], which claims that the PMI matrix should be approximately positive semi-definite, i.e. that it should have mostly positive eigenvalues. Also, notice that the shapes of distributions are far from resembling the Wigner semicircle law x ↦→ 1 2π √4-x2 , which is the limiting distribution for the eigenvalues of many random symmetric matrices with i.i.d. entries [Wigner, 1955; Wigner, 1958]. This means that the entries of a typical PMI

3 http://mattmahoney.net/dc/textdata.html.

4 This means that apriori each i and j are assumed to be independent, and we follow this convention. Thus, our PMI matrices do not have any -∞'s, instead, they have lots of 0's, i.e. they are sparse.

matrix are dependent, otherwise we would observe approximately semicircle distributions for its eigenvalues. Interestingly, there is a striking similarity between the shapes of distributions in Figure 1 and of spectral densities of the scale-free random graphs with strong clustering [Farkas et al., 2001] which arise in physics and network science. Notice that the connection between human language structure and scale-free random graphs with strong clustering was observed previously by Cancho and Sol´e [2001], and we believe it is worth investigating this connection deeper.

3.2 Involutarity of Q for SGNS Embeddings

Our theory suggests that the matrix Q in Assumption 2 should be approximately involutary. To test this claim we train offthe-shelf skip-gram embeddings {wi} and {ci} on text8 dataset using the reference WORD2VEC implementation from the TENSORFLOW codebase. Let W ∈ Rn×d be a word embedding matrix in which i-th row is w⊤ i , and C ∈ Rn×d be a context embeddingmatrix inwhich i-th row is c⊤i . According to (2),

Thus, ˆQ := W†C should give an approximately involutary matrix, where W† is the pseudo-inverse of W. This means that ˆQ2 should be approximately an identity matrix. The distribution of diagonal and off-diagonal elements of ˆQ2 is given in Fig. 2. We see that the diagonal elements are concentrated around their mean 0.68, while the off-diagonal elements are concentrated around 0, i.e. ˆQ2 ≈ 0.68 · I. However, our theory predicts ˆQ2 ≈ I. We attribute this mismatch to the underlying gap between Assumption 2 and the empirical observations: in SGNS the transform between word and context vectors is not exactly orthogonal. We stress here that our assumptions are motivated by but are not exactly consistent with the skip-gram embeddings. Despite this, our theory is quite applicable to the SGNS model as is shown in Section 4.

4 Weight Tying in the Skip-gramModel

We would like to apply our results to tie embeddings in the skip-gram model of Mikolov et al. [2013] in a theoretically grounded way. One may argue that our key Assumption 3 differs from the softmax-prediction of the skip-gram model. Although this is true, in fact the softmax normalization is never used in practice when training skip-gram. Instead it is common to replace the softmax cross-entropy by the negative sampling objective (Eq. (4) in Mikolov et al. [2013]), and its optimization is almost equivalent to finding a low-rank approximation of the shifted word-word PMI matrix in the form w⊤ i cj ≈ PMIij -log k [Levy and Goldberg, 2014b]. Since our Assumptions lead to the same conclusion up to a constant shift [Assylbekov and Takhanov, 2019, Eq. (26)], we believe that Theorem 1 can be directly applied to tie word (wi) and context (ci) embeddings in the SGNS model. For this purpose we form a vector q = [+1, . . . ,+1,-1 . . . ,-1] ∈ Rd consisting of equal number of +1's and -1's, and then put for all words i in the vocabulary. This is equivalent to (2) when the matrix Q has a diagonal form with the first d/2 diagonal entries being +1 and the rest d/2 entries being -1. Such modification of the SGNS is refered to as 'SGNS + WT'. We also experiment with random flipping of signs: for this purpose we form q ∈ Rd as a random vector consisting of d i.i.d. draws from the Rademacher distribution 5 and then put ci as in (5). Such variant of weight tying is referred to as 'SGNS + WTR'.

The word embeddings wi are initialized randomly, and then trained on text8 and enwik9 using the reference WORD2VEC implementation from the TENSORFLOW codebase with all hyperparameters set to their default values 6 except that we choose the learning rate to decay 20% faster in the weight-tied model. This additional tuning of the learning rate decay is not surprising: the model with tied embeddings has two times fewer parameters compared to the model with untied weights, and this leads to a significant change of the optimization landscape, which in turn results in the need to tune the most sensitive hyperparameter - the learning rate (or its decay schedule). As is standard nowadays the trained embeddings are evaluated on several word similarity and word analogy tasks. We used the HYPERWORDS tool of Levy et al. [2015] and we refer the reader to their paper for the methodology of evaluation. We only mention here a few key points:

5 Rademacher distribution is a discrete probability distribution where a random variate X has a 50% chance of being +1 and a 50% chance of being -1.

6 Embedding size d = 200, 15 epochs to train, initial learning rate 0.2 on text8 and 0.15 on enwik9, 100 negative samples per training example, batch size 16, windows size 5.

• Our goal is not to beat state of the art, but to empirically validate the statement of Theorem 1. This is why we were evaluating only word (input) embeddings for both SGNS and SGNS+WT. I.e., we were not adding context vectors to word vectors in the similarity tasks, as it is usually done nowadays.
• Word similarity datasets contain word pairs together with human-assigned similarity scores. The word vectors are evaluated by ranking the pairs according to their cosine similarities and measuring the correlation (Spearman's ρ) with the human ratings.
• For answering analogy questions (a is to b as c is to ?) we use the 3COSMUL of Levy and Goldberg [2014a] and the evaluation metric for the analogy questions is the percentage of correct answers.

The results of evaluation are provided in Table 1. First of all, notice that random flipping of signs (SGNS+WTR) gives practically the same results as non-random flipping (SGNS+WT). Next, SGNS+WT produces embeddings comparable in quality with those produced by the baseline SGNS model despite having 50% fewer parameters. This also empirically validates the statement of our Theorem 1. We notice that similar results can be obtained by letting the linear transform Q be a trainable matrix as shown by Gulordava et al. [2018]. The main difference of our approach is that we know exactly the form of Q, and thus we do not need to learn it.

5 Conclusion

There is a remarkable relationship between human language and other branches of science, and we can get interesting and practical results by studying such relationships deeper. For example, the modern theory of random matrices is replete with theoretical results that can be immediately applied to models of natural language once such models are cast into the appropriate probabilistic setting, as is done in this paper.

Acknowledgements

This work is supported by the Nazarbayev University Collaborative Research Program 091019CRP2109.