Title: UNDERSTANDING COMPOSITION OF WORD EMBED-DINGS VIA TENSOR DECOMPOSITION

Abstract: Word embedding is a powerful tool in natural language processing. In this paper we consider the problem of word embedding composition -given vector representations of two words, compute a vector for the entire phrase. We give a generative model that can capture specific syntactic relations between words. Under our model, we prove that the correlations between three words (measured by their PMI) form a tensor that has an approximate low rank Tucker decomposition. The result of the Tucker decomposition gives the word embeddings as well as a core tensor, which can be used to produce better compositions of the word embeddings. We also complement our theoretical results with experiments that verify our assumptions, and demonstrate the effectiveness of the new composition method. Guevara (2010) get around this drawback by first training word embeddings for each word and also for tokenized adjective-noun pairs. Then, the composition model is trained by using the constituent adjective and noun embeddings as input and the adjective-noun token embedding as the predictive target. Maillard & Clark (2015) treat adjectives as matrices and nouns as vectors, so that the composition of an adjective and noun is just matrix-vector multiplication. The matrices and vectors are learned through an extension of the skip-gram model with negative sampling. In contrast to these approaches, our model gives rise to a syntax-aware composition function, which can be learned

1. INTRODUCTION:

Word embeddings have become one of the most popular techniques in natural language processing. A word embedding maps each word in the vocabulary to a low dimensional vector. Several algorithms (e.g., Mikolov et al. (2013) ; Pennington et al. (2014) ) can produce word embedding vectors whose distances or inner-products capture semantic relationships between words. The vector representations are useful for solving many NLP tasks, such as analogy tasks (Mikolov et al., 2013) or serving as features for supervised learning problems (Maas et al., 2011) .

While word embeddings are good at capturing the semantic information of a single word, a key challenge is the problem of composition: how to combine the embeddings of two co-occurring, syntactically related words to an embedding of the entire phrase. In practice composition is often done by simply adding the embeddings of the two words, but this may not be appropriate when the combined meaning of the two words differ significantly from the meaning of individual words (e.g., "complex number" should not just be "complex"+"number").

In this paper, we try to learn a model for word embeddings that incorporates syntactic information and naturally leads to better compositions for syntactically related word pairs. Our model is motivated by the principled approach for understanding word embeddings initiated by Arora et al. (2015) , and models for composition similar to Coecke et al. (2010) . Arora et al. (2015) gave a generative model (RAND-WALK) for word embeddings, and showed several previous algorithms can be interpreted as finding the hidden parameters of this model. However, the RAND-WALK model does not treat syntactically related word-pairs differently from other word pairs. We give a generative model called syntactic RAND-WALK (see Section 3) that is capable of capturing specific syntactic relations (e.g., adjective-noun or verb-object pairs). Taking adjective-noun pairs as an example, previous works (Socher et al., 2012; Baroni & Zamparelli, 2010; Maillard & Clark, 2015) have tried to model the adjective as a linear operator (a matrix) that can act on the embedding of the noun. However, this would require learning a d × d matrix for each adjective while the normal embedding only has dimension d. In our model, we use a core tensor T ∈ R d×d×d to capture the relations between a pair of words and its context. In particular, using the tensor T and the word embedding for the adjective, it is possible to define a matrix for the adjective that can be used as an operator on the embedding of the noun. Therefore our model allows the same interpretations as many previous models while having much fewer parameters to train.

One salient feature of our model is that it makes good use of high order statistics. Standard word embeddings are based on the observation that the semantic information of a word can be captured by words that appear close to it. Hence most algorithms use pairwise co-occurrence between words to learn the embeddings. However, for the composition problem, the phrase of interest already has two words, so it would be natural to consider co-occurrences between at least three words (the two words in the phrase and their neighbors).

Based on the model, we can prove an elegant relationship between high order co-occurrences of words and the model parameters. In particular, we show that if we measure the Pointwise Mutual Information (PMI) between three words, and form an n × n × n tensor that is indexed by three words a, b, w, then the tensor has a Tucker decomposition that exactly matches our core tensor T and the word embeddings (see Section 2, Theorem 1, and Corollary 1). This suggests a natural way of learning our model using a tensor decomposition algorithm.

Our model also allows us to approach the composition problem with more theoretical insights. Based on our model, if words a, b have the particular syntactic relationships we are modeling, their composition will be a vector v a + v b + T (v a , v b , •). Here v a , v b are the embeddings for word a and b, and the tensor gives an additional correction term. By choosing different core tensors it is possible to recover many previous composition methods. We discuss this further in Section 3.

Finally, we train our new model on a large corpus and give experimental evaluations. In the experiments, we show that the model learned satisfies the new assumptions that we need. We also give both qualitative and quantitative results for the new embeddings. Our embeddings and the novel composition method can capture the specific meaning of adjective-noun phrases in a way that is impossible by simply "adding" the meaning of the individual words. Quantitative experiment also shows that our composition vector are better correlated with humans on a phrase similarity task.

1.1. RELATED WORK:

Syntax and word embeddings Many well-known word embedding methods (e.g., Pennington et al. (2014) ; Mikolov et al. (2013) ) don't explicitly utilize or model syntactic structure within text. Andreas & Klein (2014) find that such syntax-blind word embeddings fail to capture syntactic information above and beyond what a statistical parser can obtain, suggesting that more work is required to build syntax into word embeddings.

Several syntax-aware embedding algorithms have been proposed to address this. Levy & Goldberg (2014a) propose a syntax-oriented variant of the well-known skip-gram algorithm of Mikolov et al. (2013) , using contexts generated from syntactic dependency-based contexts obtained with a parser. Cheng & Kartsaklis (2015) build syntax-awareness into a neural network model for word embeddings by indroducing a negative set of samples in which the order of the context words is shuffled, in hopes that the syntactic elements which are sensitive to word order will be captured.

Word embedding composition Several works have addressed the problem of composition for word embeddings. On the theoretical side, Gittens et al. (2017) give a theoretical justification for additive embedding composition in word models that satisfy certain assumptions, such as the skipgram model, but these assumptions don't address syntax explicitly. Coecke et al. (2010) present a mathematical framework for reasoning about syntax-aware word embedding composition that motivated our syntactic RAND-WALK model. Our new contribution is a concrete and practical learning algorithm with theoretical guarantees. Mitchell & Lapata (2008; 2010) explore various composition methods that involve both additive and multiplicative interactions between the component embeddings, but some of these are limited by the need to learn additional parameters post-hoc in a supervised fashion.

along with the word embeddings in an unsupervised fashion, and which generalizes many previous composition methods (see Section 3.3 for more discussion).

Tensor factorization for word embeddings As Levy & Goldberg (2014b) and Li et al. (2015) point out, some popular word embedding methods are closely connected matrix factorization problems involving pointwise mutual information (PMI) and word-word co-occurrences. It is natural to consider generalizing this basic approach to tensor decomposition. Sharan & Valiant (2017) demonstrate this technique by performing a CP decomposition on triple word co-occurrence counts. Bailey & Aeron (2017) explore this idea further by defining a third-order generalization of PMI, and then performing a symmetric CP decomposition on the resulting tensor. In contrast to these recent works, our approach arives naturally at the more general Tucker decomposition due to the syntactic structure in our model. Our model also suggests a different (yet still common) definition of third-order PMI.

2. PRELIMINARIES:

Notation For a vector v, we use v to denote its Euclidean norm. For vectors u, v we use u, v to denote their inner-product. For a matrix M , we use M to denote its spectral norm,

M F = i,j M 2 i,j

to denote its Frobenius norm, and M i,: to denote it's i-th row. In this paper, we will also often deal with 3rd order tensors, which are just three-way indexed arrays. We use ⊗ to denote the tensor product:

if u, v, w ∈ R d are d-dimensional vectors, T = u ⊗ v ⊗ w is a d × d × d tensor whose entries are T i,j,k = u i v j w k .

Tensor basics Just as matrices are often viewed as bilinear functions, third order tensors can be interpreted as trilinear functions over three vectors. Concretely, let T be a d × d × d tensor, and let x, y, z ∈ R d . We define the scalar T (x, y, z) ∈ R as follows

T (x, y, z) = d i,j,k=1 T i,j,k x(i)y(j)z(k).

This operation is linear in x, y and z. Analogous to applying a matrix M to a vector v (with the result vector M v), we can also apply a tensor T to one or two vectors, resulting in a matrix and a vector, respectively:

T (x, y, •)(k) = d i,j=1 T i,j,k x(i)y(j), T (x, •, •) j,k = d i=1 T i,j,k x(i)

We will make use of the simple facts that z, T (x, y, •) = T (x, y, z) and [T (x, •, •)] y = T (x, y, •).

Tensor decompositions Unlike matrices, there are several different definitions for the rank of a tensor. In this paper we mostly use the notion of Tucker rank Tucker (1966) . A tensor T ∈ R n×n×n has Tucker rank d, if there exists a core tensor S ∈ R d×d×d and matrices A, B, C ∈ R n×d such that

T i,j,k = d i ,j ,k =1 S i ,j ,k A i,i B j,j C k,k = S(A i,: , B j,: , C k,: ),

The equation above is also called a Tucker decomposition of the tensor T . The Tucker decomposition for a tensor can be computed efficiently.

When the core tensor S is restricted to a diagonal tensor (only nonzero at entries S i,i,i ), the decomposition is called a CP decomposition Carroll & Chang (1970); Harshman (1970) which can also be written as T = d i=1 S i,i,i A i,: ⊗ B i,: ⊗ C i,: . In this case, the tensor T is the sum of d rank-1 tensors (A i,: ⊗ B i,: ⊗ C i,: ). However, unlike matrix factorizations and the Tucker decomposition, the CP decomposition of a tensor is hard to compute in the general case (Håstad, 1990; Hillar & Lim, 2013) . Later in Section 4 we will also see why our model for syntactic word embeddings naturally leads to a Tucker decomposition. 

3. SYNTACTIC RAND-WALK MODEL:

In this section, we introduce our syntactic RAND-WALK model and present formulas for inference in the model. We also derive a novel composition technique that emerges from the model.

RAND-WALK model:

We first briefly review the RAND-WALK model (Arora et al., 2015) . In this model, a corpus of text is considered as a sequence of random variables w 1 , w 2 , w 3 , . . ., where w t takes values in a vocabulary V of n words. Each word w ∈ V has a word embedding v w ∈ R d . The prior for the word embeddings is v w = s • v, where s is a positive bounded scalar random variable with constant expectation τ and upper bound κ, and v ∼ N (0, I).

The distribution of each w t is determined in part by a random walk {c t ∈ R d | t = 1, 2, 3 . . .}, where c t -called a discourse vector -represents the topic of the text at position t. This random walk is slow-moving in the sense that c t+1 -c t is small, but mixes quickly to a stationary distribution that is uniform on the unit sphere, which we denote by C.

Let C denote the sequence of discourse vectors, and let V denote the set of word embeddings. Given these latent variables, the model specifies the following conditional probability distribution:

EQUATION

The graphical model depiction of RAND-WALK is shown in Figure 1a .

3.1. SYNTACTIC RAND-WALK:

One limitation of RAND-WALK is that it can't deal with syntactic relationships between words.

Observe that conditioned on c t and V , w t is independent of the other words in the text. However, in natural language, words can exhibit more complex dependencies, e.g. adjective-noun pairs, subject-verb-object triples, and other syntactic or grammatical structures.

In our syntactic RAND-WALK model, we start to address this issue by introducing direct pairwise word dependencies in the model. When there is a direct dependence between two words, we call the two words a syntactic word pair. In RAND-WALK, the interaction between a word embedding v and a discourse vector c is mediated by their inner product v, c . When modeling a syntactic word pair, we need to mediate the interaction between three quantities, namely a discourse vector c and the word embeddings v and v of the two relevant words. A natural generalization is to use a trilinear form defined by a tensor T , i.e.

T (v, v , c) = d i,j,k=1 T i,j,k v(i)v (j)c(k).

Here, T ∈ R d×d×d is also a latent random variable, which we call the composition tensor.

We model a syntactic word pair as a single semantic unit within the text (e.g. in the case of adjectivenoun phrases). We realize this choice by allowing each discourse vector c t to generate a pair of words w t , w t with some small probability p syn . To generate a syntactic word pair w t , w t , we first generate a root word w t conditioned on c t with probability proportional to exp( c t , w t ), and then we draw w t from a conditional distribution defined as follows:

Pr[w t = b | w t = a, C , V ] ∝ exp( c t , v b + T (v a , v b , c t )).

(2) Here exp( c t , v b ) would be proportional to the probability of generating word b in the original RAND-WALK model, without considering the syntactic relationship. The additional term T (v a , v b , c t ) can be viewed as an adjustment based on the syntactic relationship.

We call this extended model Syntactic RAND-WALK. Figure 1b gives the graphical model depiction for a syntactic word pair, and we summarize the model below. 

3.2. INFERENCE IN THE MODEL:

We now calculate the marginal probabilities of observing pairs and triples of words under the syntactic RAND-WALK model. We will show that these marginal probabilities are closely related to the model parameters (word embeddings and the composition tensor). All proofs in this section are deferred to supplementary material.

Throughout this section, we consider two adjacent context vectors c t and c t+1 , and condition on the event that c t generated a single word and c t+1 generated a syntactic pair 1 . The main bottleneck in computing the marginal probabilities is that the conditional probailities specified in equations ( 1) and ( 2) are not normalized. Indeed, for these equations to be exact, we would need to divide by the appropriate partition functions, namely Z ct := w∈V exp( v w , c t ) for the former and Z ct,a := w∈V exp( c t , v w + T (v a , v w , c t )) for the latter. Fortunately, we show that under mild assumptions these quantities are highly concentrated. To do that we need to control the norm of the composition tensor. Definition 2. The composition tensor T is (K, )-bounded, if for any word embedding v a , v b , we have

T (v a , •, •) + I 2 ≤ Kd 2 log 2 n ; T (v a , •, •) + I 2 F ≤ Kd; T (v a , v b , •) 2 ≤ Kd.

To make sure exp( c t , v w +T (v a , v w , c t )) are within reasonable ranges, the value K in this definition should be interpreted as an absolute constant (like 5, similar to previous constants κ and τ ). Intuitively these conditions make sure that the effect of the tensor cannot be too large, while still making sure the tensor component T (v a , v b , c) can be comparable (or even larger than) v b , c . We have not tried to optimize the log factors in the constraint for

T (v a , •, •) + I 2 .

Note that if the tensor component T (v a , •, •) has constant singular values (hence comparable to I), we know these conditions will be satisfied with

K = O(1) and = O( log n

Lemma 1 (Concentration of partition functions). For the syntactic RAND-WALK model, there exists a constant Z such that Pr

c∼C [(1 -z )Z ≤ Z c ≤ (1 + z )Z] ≥ 1 -δ, for z = Õ(1/ √ n) and δ = exp(-Ω(log 2 n)).

Furthermore, if the tensor T is (K, )-bounded, then for any fixed word a ∈ V , there exists a constant

Z a such that Pr c∼C [(1 -z,a )Z a ≤ Z c,a ≤ (1 + z,a )Z a ] ≥ 1 -δ, for z,a = O( ) + Õ(1/ √ n) and δ = exp(-Ω(log 2 n)).

Using this lemma, we can obtain simple expressions for co-occurrence probabilities. In particular, for any fixed w, a, b ∈ V , we adopt the following notation:

p(a) := Pr[w t+1 = a] p(w, a) := Pr[w t = w, w t+1 = a] p([a, b]) := Pr[w t+1 = a, w t+1 = b] p(w, [a, b]) := Pr[w t = w, w t+1 = a, w t+1 = b].

Here in particular we use [a, b] to highlight the fact that a and b form a syntactic pair. Note p(w, a) is the same as the co-occurrence probability of words w and a if both of them are the only word generated by the discourse vector. Later we will also use

p(w, b) to denote Pr[w t = w, w t+1 = b] (not Pr[w t = w, w t+1 = b]).

We also require two additional properties of the word embeddings, namely that they are norm-bounded above by some constant times √ d, and that all partition functions are bounded below by a positive constant. Both of these properties hold with high probability over the word embeddings provided n d log d and d log n, as shown in the following lemma: Lemma 2. Assume that the composition tensor T is (K, )-bounded, where K is a constant. With probability at least 1 -δ 1 -δ 2 over the word vectors, where

δ 1 = exp(Θ(d log d) -Θ(n)) and δ 2 = exp(Θ(log n) -Θ(d))

, there exist positive absolute constants γ and β such that v i ≤ κγ for each i ∈ V and Z c ≥ β and Z c,a ≥ β for any unit vector c ∈ R d and any word a ∈ V .

We can now state the main result. Theorem 1. Suppose that the events referred to in Lemma 1 hold. Then

EQUATION

)

Here p = O( + w ) + Õ(1/ √ n + 1/d),

where is from the (K, )-boundedness of T and w is from Definition 1.

3.3. COMPOSITION:

Our model suggests that the latent discourse vectors contain the meaning of the text at each location. It is therefore reasonable to view the discourse vector c corresponding to a syntactic word pair (a, b) as a suitable representation for the phrase as a whole. The posterior distribution of c given (a, b) satisfies

Pr[c t = c | w t = a, w t = b] ∝ 1 Z c Z c,a exp ( v a + v b + T (v a , v b , •), c ) Pr[c t = c].

Since Pr[c t = c] is constant, and since Z c and Z c,a concentrate on values that don't depend on c, the MAP estimate of c given [a, b], which we denote by ĉ, satisfies

ĉ ≈ arg max c =1 exp ( v a + v b + T (v a , v b , •), c ) = v a + v b + T (v a , v b , •) v a + v b + T (v a , v b , •) .

Hence, we arrive at our basic tensor composition: for a syntactic word pair (a, b), the composite embedding for the phrase is

v a + v b + T (v a , v b , •).

Note that our composition involves the traditional additive composition v a + v b , plus a correction term T (v a , v b , •). We can view T (v a , v b , •) as a matrix-vector multiplication [T (v a , •, •)] v b , i.e. the composition tensor allows us to compactly associate a matrix with each word in the same vein as Maillard & Clark (2015) . Depending on the actual value of T , the term T (v a , v b , •) can also recover any manner of linear or multiplicative interactions between v a and v b , such as those proposed in Mitchell & Lapata (2010) .

4. LEARNING:

In this section we discuss how to learn the parameters of the syntactic RAND-WALK model. Theorem 1 provides key insights into the learning problem, since it relates joint probabilities between words (which can be estimated via co-occurrence counts) to the word embeddings and composition tensor.

By examining these equations, we can derive a particularly simple formula that captures these relationships. To state this equation, we define the PMI for 3 words as

EQUATION

)

We note that this is just one possible generalization of pointwise mutual information (PMI) to several random variables, but in the context of our model, it is a very natural definition as all the partition numbers will be canceled out. Indeed, as an immediate corollary of Theorem 1, we have Corollary 1. Suppose that the events referred to in Lemma 1 hold. Then for p same as Theorem 1

EQUATION

That is, if we consider P M I3(a, b, w) as a n × n × n tensor, Equation equation 8 is exactly a Tucker decomposition of this tensor of Tucker rank d. Therefore, all the parameters of the syntactic RAND-WALK model can be obtained by finding the Tucker decomposition of the PMI3 tensor. This equation also provides a theoretical motivation for using third-order pointwise mutual information in learning word embeddings.

4.1. IMPLEMENTATION:

We now discuss concrete details about our implementation of the learning algorithm.2 

Corpus. We train our model using a February 2018 dump of the English Wikipedia. The text is pre-processed to remove non-textual elements, stopwords, and rare words (words that appear less than 1000 within the corpus), resulting in a vocabulary of size 68,279. We generate a matrix of word-word co-occurrence counts using a window size of 5. To generate the tensors of adjective-noun-word and verb-object-word co-occurrence counts, we first run the Stanford Dependency Parser (Chen & Manning, 2014) on the corpus in order to identify all adjective-noun and verb-object word pairs, and then use context windows that don't cross sentence boundaries to populate the triple co-occurrence counts.

Training. We first train the word embeddings according to the RAND-WALK model, following Arora et al. (2015) . Using the learned word embeddings, we next train the composition tensor T via the following optimization problem min

T,{Cw},C (a,b),w f (X (a,b),w ) log(X (a,b),w ) -v w + v a + v b + T (v a , v b , •) 2 -C a -C 2 ,

where X (a,b),w denotes the number of co-occurrences of word w with the syntactic word pair (a, b) (a denotes the noun/object) and f (x) = min(x, 100). This objective function isn't precisely targeting the Tucker decomposition of the PMI3 tensor, but it is analogous to the training criterion used in Arora et al. (2015) , and can be viewed as a negative log-likelihood for the model. To reduce the number of parameters, we constrain T to have CP rank 1000. We also trained the embeddings and tensor jointly, but found that this approach yields very similar results. In all cases, we utilize the Tensorflow framework (Abadi et al., 2016) with the Adam optimizer (Kingma & Ba, 2014) (using default parameters), and train for 1-5 epochs.

5. EXPERIMENTAL VERIFICATION:

In this section, we verify and evaluate our model empirically on select qualitative and quantitative tasks. In all of our experiments, we focus solely on syntactic word pairs formed by adjective-noun phrases, where the noun is considered the root word. Arora et al. (2015) empirically verify the model assumptions of RAND-WALK, and since we trained our embeddings in the same way, we don't repeat their verifications here. Instead, we verify two key properties of syntactic RAND-WALK.

5.1. MODEL VERIFICATION:



Norm of composition tensor:

We check the assumptions that the tensor T is (K, )-bounded. Ranging over all adjective-noun pairs in the corpus, we find that 1 d T (v a , •, •) + I 2 has mean 0.052 and maximum 0.248, 1 d T (v a , •, •) + I 2 F has mean 1.61 and maximum 3.23, and 1 d T (v a , v b , •) 2 has mean 0.016 and maximum 0.25. Each of these three quantities has a well-bounded mean, but T (v a , •, •) + I 2 has some larger outliers. If we ignore the log factors (which are likely due to artifacts in the proof) in Definition 2, the tensor is (K, ) bounded for K = 4 and = 0.25.

Concentration of partition functions:

In addition to Definition 2, we also directly check its implications: our model predicts that the partition functions Z c,a concentrate around their means. To check this, given a noun a, we draw 1000 random vectors c from the unit sphere, and plot the histogram of Z c,a .Results for a few randomly selected words a are given in Figure 2 . All partition functions that we inspected exhibited good concentration.

5.2. QUALITATIVE ANALYSIS OF COMPOSITION:

We test the performance of our new composition for adjective-noun and verb-object pairs by looking for the words with closest embedding to the composed vector. For a phrase (a, b), we compute c = v a + v b + T (v a , v b , •), and then retrieve the words w whose embeddings v w have the largest cosine similarity to c. We compare our results to the additive composition method. Tables 1 and 2 show results for three adjective-noun and verb-object phrases. In each case, the tensor composition is able to retrieve some words that are more specifically related to the phrase. However, the tensor composition also sometimes retrieves words that seem unrelated to either word in the phrase. We conjecture that this might be due to the sparseness of co-occurrence of three words. We also observed cases where the tensor composition method was about on par with or inferior to the additive composition method for retrieving relevant words, particularly in the case of low-frequency phrases. More results can be found in supplementary material. 

5.3. PHRASE SIMILARITY:

We also test our tensor composition method on a adjective-noun phrase similarity task using the dataset introduced by Mitchell & Lapata (2010) . The data consists of 108 pairs each of adjective-noun and verb-object phrases that have been given similarity ratings by a group of 54 humans. The task is to use the word embeddings to produce similarity scores that correlate well with the human scores; we use both the Spearman rank correlation and the Pearson correlation as evaluation metrics for this task. We note that the human similarity judgments are somewhat noisy; intersubject agreement for the task is 0.52 as reported in Mitchell & Lapata (2010) .

Given a phrase (a, b) with embeddings v a , v b , respectively, we found that the tensor composition v a + v b + T (v a , v b , •) yields worse performance than the simple additive composition v a + v b . For this reason, we consider a weighted tensor composition 2010), we split the data into a development set of 18 humans and a test set of the remaining 36 humans. We use the development set to select the optimal scalar weight for the weighted tensor composition, and using this fixed parameter, we report the results using the test set.

v a + v b + αT (v a , v b , •) with α ≥ 0. Following Mitchell & Lapata (

We repeat this three times, rotating over folds of 18 subjects, and report the average results.

As a baseline, we also report the average results using just the additive composition, as well as a weighted additive composition βv a + v b , where β ≥ 0. We select β using the development set ("weighted1") and the test set ("weighted2"). We allow weighted2 to cheat in this way because it provides an upper bound on the best possible weighted additive composition. Additionally, we compare our method to the smoothed inverse frequency ("sif") weighting method that has been demonstrated to be near state-of-the-art for sentence embedding tasks (Arora et al., 2016) . We also test embeddings of the form p + γω a ω b T (v a , v b , •) ("sif+tensor"), where p is the sif embedding for (a, b), ω a and ω b are the smoothed inverse frequency weights used in the sif embeddings, and γ is a positive weight selected using the development set. The motivation for this hybrid embedding is to evaluate the extent to which the sif embedding and tensor component can independently improve performance on this task.

We perform these same experiments using two other standard sets of pre-computed word embeddings, namely GloVe3 and carefully optimized cbow vectors4 (Mikolov et al., 2017) . We re-trained the composition tensor using the same corpus and technique as before, but substituting these pre-computed embeddings in place of the RAND-WALK (rw) embeddings. However, a bit of care must be taken here, since our syntactic RAND-WALK model constrains the norm of the word embeddings to be related to the frequency of the words, whereas this is not the case with the pre-computed embeddings.

To deal with this, we rescaled the pre-computed embeddings sets to have the same norms as their counterparts in the rw embeddings, and then trained the composition tensor using these rescaled embeddings. At test time, we use the original embeddings to compute the additive components of our compositions, but use the rescaled versions when computing the tensor components.

The results for adjective-noun phrases are given in Tables 3. We observe that the tensor composition outperforms the additive compositions on all embedding sets apart from the Spearman correlation on the cbow vectors, where the weighted additive 2 method has a slight edge. The sif embeddings outperform the additive and tensor methods, but combining the sif embeddings and the tensor components yields the best performance across the board, suggesting that the composition tensor captures additional information beyond the individual word embeddings that is useful for this task.

There was high consistency across the folds for the optimal weight parameter α, with α = 0.4 for the rw embeddings, α = .2, .3 for the glove embeddings, and α = .3 for the cbow embeddings. For the sif+tensor embeddings, γ was typically in the range [.1, .2].

The results for verb-object phrases are given in Table 4 . Predicting phrase similarity appears to be harder in this case. Notably, the sif embeddings perform worse than unweighted vector addition.

As before, we can improve the sif embeddings by adding in the tensor component. The tensor composition method achieves the best results for the glove and cbow vectors, but weighted addition works best for the randwalk vectors.

Overall, these results demonstrate that the composition tensor can improve the quality of the phrase embeddings in many cases, and the improvements are at least somewhat orthogonal to improvements .438 .444, .448 .452, .453 .460, .465 .482, .477 .482, .481 glove .357, .336 .351, .334 .358, .345 .368, .347 .429, .434 .433, .437 cbow .471, .452 .469, .451 .476, .456 .474, .471 .489, .482 .492, .484 .370 .391, .385 .392, .387 .379, .370 .378, .351 .378, .363 glove .397, .400 .398, .404 .401, .404 .410, .420 .387, .380 .411, .409 cbow .423, .414 .423, .410 .428, .415 .428, .422 .404, .404 .420, .417 resulting from the sif embedding method. This suggests that a well-trained composition tensor used in conjunction with high quality word embeddings and additional embedding composition techniques has the potential to improve performance in downstream NLP tasks. 

A ADDITIONAL QUALITIATIVE RESULTS:

In this section we present additional qualitiative results demonstrating the use of the composition tensor for the retrieval of words related to adjective-noun and verb-object phrases.

In Table 5 , we show results for the phrases "giving birth", "solve problem", and "changing name". These phrases are all among the top 500 most frequent verb-object phrases appearing in the training corpus. In these examples, the tensor-based phrase embeddings retrieve words that are generally markedly more related to the phrase at hand, and there are no strange false positives. These examples demonstrate how a verb-object phrase can encompass an action that isn't implied simply by the object or verb alone. The additive composition doesn't capture this action as well as the tensor composition.

Moving on to adjective-noun phrases, in Table 6 , we show results for the phrases "United States", "Soviet Union", and "European Union". These phrases, which all occur with comparatively high frequency in the corpus, were identified as adjective-noun phrases by the tagger, but they function more as compound proper nouns. In each case, the additive composition retrieves reasonably relevant words, while the tensor composition is more of a mixed bag. In the case of "European Union", the tensor composition does retrieve the highly relevant words eec (European Economic Community) and eea (European Economic Area), which the additive composition misses, but the tensor composition also produces several false positives. It seems that for these types of phrases, the additive composition is sufficient to capture the meaning.

In Table 7 , we fix the noun "taste" and vary the modifying adjective to highlight different senses of the noun. In the case of "expensive taste", both compositions retrieve words that seem to be either related to "expensive" or "taste", but there don't seem to be words that are intrinsically related to the phrase as a whole (with the exception, perhaps, of "luxurious", which the tensor composition retrieves). In the case of "awful taste", both compositions retrieve fairly similar words, which mostly relate to the physical sense of taste (rather than the more abstract sense of the word). For the phrase "refined taste", the additive composition fails to capture the sense of the phrase and retrieves many words related to food taste (which are irrelevant in this context), whereas the tensor composition retrieves more relevant words.

In Table 8 , we fix the noun "friend" and vary the modifying adjective, but in all three cases, the adjective-noun phrase has basically the same meaning. In the case of "close friend" and "dear friend", both compositions retrieve fairly relevant and similar words. In the case of "best friend", both compositions retrieve false positives: the additive composition seems to find words related to movie awards, while the tensor composition finds unintuitive false positives. We note that in all three phrases, the tensor composition consistently retrieves the words "confidante", "confided" or "confides", "coworker", and "protoge", all of which are fairly relevant.

A.1 SENTIMENT ANALYSIS:

We test the effect of using the composition tensor for a sentiment analysis task. We use the movie review dataset of Pang and Lee (Pang & Lee, 2004) as well as the Large Movie Review dataset (Maas et al., 2011) , which consist of 2,000 movie reviews and 50,000 movie reviews, respectively. For a fixed review, we identify each adjective-noun pair (a, b) and compute T (v a , v b , •). We add these compositions together with the word embeddings for all of the words in the review, and then normalize the resulting sum. This vector is used as the input to a regularized logistic regression classifier, which we train using scikit-learn (Pedregosa et al., 2011) with the default parameters. We also consider a baseline method where we simply add together all of the word embeddings in the movie review, and then normalize the sum. We evaluate the test accuracy of each method using Lemma 4. Let v a be a fixed word vector, and let c be a random discourse vector. If T is (K, )bounded with d ≥ log 2 n/ 2 , we have

Pr[ T (v a , •, c) + c 2 ∈ L ± O( )] ≥ 1 -δ,

where 0 ≤ L ≤ K is a constant that depends on v a , and δ = exp(-Ω(log 2 n)).

Proof. Since c is a uniform random vector on the unit sphere, we can represent c as c = z/ z , where z ∼ N (0, I) is a standard spherical Gaussian vector. For ease of notation, let M = T (v a , •, •)+I, and write the singular value decomposition of M as M = U ΣV T . Note that Σ = diag(λ 1 , . . . , λ d ) and U and V are orthogonal matrices, so that in particular, the random variable y = V T z has the same distribution as z, i.e. its entries are i.i.d. standard normal random variables. Further, U x 2 = x 2 for any vector x, since U is orthogonal. Hence, we have

T (v a , •, c) + c 2 = 1 z 2 M z 2 = 1 z 2 U Σy 2 = d i=1 λ 2 i y 2 i d i=1 z 2 i .

Since both the numerator and denominator of this quantity are generalized χ 2 random variables, we can apply Lemma 7 to get tail bounds on both. Observe that by assumption, we have λ 2 i ≤ Kd 2 / log 2 n for all i, and

d i=1 λ 2 i ≤ Kd. Set A = d i=1 λ 2 i y 2 i and B = d i=1 z 2 i . Let λ 2 max = max 1≤i≤d λ 2 i . Note that E[A] = d i=1 λ 2 i ≤ Kd and E[B] = d.

We will apply Lemma 7 to prove concentration bounds for A, in this case we have

Pr   |A -E[A]| ≥ 2 d i=1 λ 4 i √ x + 2λ 2 max x   ≤ 2 exp(-x).

Under our assumptions, we know λ 2 max ≤ Kd 2 / log 2 n and

d i=1 λ 4 i ≤ λ 2 max d i=1 λ 2 i ≤ Kd / log n. Take x = 1 16 log 2 n, we know 2 d i=1 λ 4 i √ x + 2λ 2 max x] ≤ Kd . Therefore Pr[|A -E[A]| ≥ Kd ] ≤ 2 exp(-Ω(log 2 n)).

Similarly, we can apply Lemma 7 to B (in fact we can apply simpler concentration bounds for standard χ 2 distribution), and we get

Pr[|B -E[B]| ≥ 2 √ d √ x + 2x] ≤ 2 exp(-x).

If we take x = 1 16 log 2 n, we know 2

√ d √ x + 2x ≤ d. This implies Pr[|B -E[B]| ≥ d ] ≤ 2 exp(-Ω(log 2 n)).

When both events happen we know

| A B -E[A] E[B] | ≤ 4K = O( ) (here K is considered as a constant

). This finishes the proof.

Using this lemma, we will show that the expected condition number nE v∼D V [exp( r, v )] (where r = T (v a , •, c) + c) is concentrated Lemma 5. Let v a be a fixed word vector, and let c be a random discourse vector. If T is (K, )bounded, there exists Z a such that we have

Pr[nE v∼D V [exp( T (v a , •, c) + c, v )] ∈ Z a (1 ± O( ) ≥ 1 -δ,

where Z a = Θ(n) depends on v a , and δ = exp(-Ω(log 2 n)).

Proof. We know v = s • v where v ∼ N (0, I) and s is a (random) scaling. Let r = T (v a , •, c) + c. Conditioned on s we know r, v is equivalent to a Gaussian random variable with standard deviation σ = r s. For this random variable we know

E[exp( r, v )|s] = x 1 σ √ 2π exp - x 2 2σ 2 exp(x)dx = x 1 σ √ 2π exp - (x -σ 2 ) 2 2σ 2 + σ 2 /2 dx = exp(σ 2 /2). Hence, E[exp( r, v )|s] = exp(s 2 r 2 /2). Let g(x) = E s [exp(s 2 x/2)], we know g (x) = E s [exp(s 2 x/2) • (s 2 /2)] ≤ κ 2 /2 • g(x)

. In particular, this implies g(x + γ) ≤ exp(κ 2 γ/2)g(x) (for small γ).

By Lemma 4, we know with probability at least 1 -Ω(log 2 n), r 2 ∈ L ± O( ). Therefore, when this holds, we have

nE v∼D V [exp( r, v )] ∈ ng(L -O( )) • [1, exp(O( κ 2 /2)].

The multiplicative factor on the RHS is bounded by 1 + O( ) when is small enough (and κ is a constant). This finishes the proof. Now we know the expected partition function is concentrated (for almost all discourse vectors c), it remains to show when we have finitely many words the partition function is concentrated around its expectation. This was already proved in Arora et al. (2015) , we use their lemma below: Lemma 6. For any fixed vector r (whose norm is bounded by a constant), with probability at least 1 -exp(-Ω(log 2 n)) over the choices of the words, we have

n i=1 exp( r, v i ) ∈ nE v∼D V [exp( r, v )](1 ± z ), where z = Õ(1/ √ n).

This is essentially Lemma 2.1 in Arora et al. (2015) (see Equation A.32 ). The version we stated is a bit different because we allow r to have an arbitrary constant norm (while in their proof vector r is the discourse vector c and has norm 1). This is a trivial corollary as we can move the norm of r into the distribution of the scaling factor s for the word embedding.

Finally we are ready to prove Lemma 1.

Proof of Lemma 1. The first part is exactly Lemma 2.1 in Arora et al. (2015) .

For the second part, note that the partition function Z c,a = n i=1 T (v a , •, c) + c, v i . We will use E[Z c,a ] to denote its expectation over the randomness of the word embedding {v i }. By Lemma 5, we know for at least 1 -exp(-Ω(log 2 n)) fraction of discourse vectors c, the expected partition function is concentrated (E[Z c,a ] ∈ (1 ± O( ))Z a ). Let S denote the set of c such that Lemma 5 holds. Now by Lemma 6 we know for any x ∈ S, with probability at least 1 -exp(-Ω(log

2 n) Z c,a ∈ (1 ± z )E[Z c,a ].

Therefore we know if we consider both c and the embedding as random variables, Pr[Z c,a ∈ (1 ± O( + z ))Z a ] ≥ 1 -δ where δ = exp(-Ω(log 2 n)). Let S be the set of word embedding such that there is at least

√ δ fraction of c that does not satisfy Z c,a ∈ (1 ± O( + z ))Z a , we must have Pr[S] • √ δ ≤ δ . Therefore Pr[S] ≤ √ δ .

That is, with probability at least 1 -√ δ (over the word embeddings), there is at least 1 -√ δ fraction of c such that Z c,a ∈ (1 ± O( + z ))Z a .

B.2 ESTIMATING THE CORRELATIONS:

In this section we prove Theorem 1 and Corollary 1. The proof is very similar to the proof of Theorem 2.2 in Arora et al. (2015) . We use several lemmas in that proof, and these lemmas are deferred to Section B.3.

Proof of Theorem 1. Throughout this proof we consider two adjacent discourse vectors c, c , where c generated a single word w and c generated a syntactic pair (a, b).

The first two results in Theorem 1 are exactly the same as Theorem 2.2 in Arora et al. (2015) . Therefore we only need to prove the result for p ([a, b] ) and p(w, [a, b] ).

For p ([a, b] ), by definition of the model we know

p([a, b]) = E c [ 1 Z c 1 Z c ,a exp( c , v a + c , v b + T (v a , v b , c )].

Here Z c is the partition function n i=1 exp( c , v i ), and Z c ,a is the partition function

n i=1 exp( c , v i + T (v a , v i , c

). Let F be the event that c satisfies the equations in Lemma 1. Let F be its negation. By Lemma 1 we know Pr[F] ≥ 1 -exp(-Ω(log 2 n)). Using this event, we can write

p([a, b]) =E c [ 1 Z c 1 Z c ,a exp( c , v a + c , v b + T (v a , v b , c ))1 F ] + E c [ 1 Z c 1 Z c ,a exp( c , v a + c , v b + T (v a , v b , c ))1 F ].

The second term can be bounded by Lemma 8 and the fact that Z c Z c ,a ≥ β from Lemma 2. We know

E c [ 1 Z c 1 Z c ,a exp( c , v a + c , v b + T (v a , v b , c )1 F ] ≤ exp(-Ω(log 1.8 n)).

For the first term, we know by Lemma 1 that there exists Z, Z a that are close to Z c and Z c ,a . Therefore

p([a, b]) = E c [ 1 Z c 1 Z c ,a exp( c , v a + c , v b + T (v a , v b , c )1 F ] + E c [ 1 Z c 1 Z c ,a exp( c , v a + c , v b + T (v a , v b , c )1 F ]. ≤ (1 + z )(1 + z,a )E c [ 1 Z 1 Z a exp( c , v a + c , v b + T (v a , v b , c )1 F ] + exp(-Ω(log 1.8 n)) ≤ (1 + z )(1 + z,a ) ZZ a E c [exp( c , v a + c , v b + T (v a , v b , c )] + exp(-Ω(log 1.8 n)) ≤ (1 + z )(1 + z,a )(1 + Õ(1/d)) ZZ a exp( v a + v b + T (v a , v b , •) 2 2d ) + exp(-Ω(log 1.8 n)).

Here the last step used Lemma 10. Since both Z and Z a can be bounded by O(n), and

va+v b +T (va,v b ,•) 2 2d

is bounded by (4κ + √ 2K) 2 , we know the first term is of order Ω(1/n 2 ), and the second term is negligible.

For the lowerbound, we can have

p([a, b]) = E c [ 1 Z c 1 Z c ,a exp( c , v a + c , v b + T (v a , v b , c )1 F ] + E c [ 1 Z c 1 Z c ,a exp( c , v a + c , v b + T (v a , v b , c )1 F ]. ≥ (1 -z )(1 -z,a )E c [ 1 Z 1 Z a exp( c , v a + c , v b + T (v a , v b , c )1 F ] ≥ (1 -z )(1 -z,a ) ZZ a {E c [exp( c , v a + c , v b + T (v a , v b , c ))] -E c [exp( c , v a + c , v b + T (v a , v b , c ))1 F ]} ≥ (1 -z )(1 -z,a ) ZZ a E c [exp( c , v a + c , v b + T (v a , v b , c ))] -exp(-Ω(log 1.8 n)) ≥ (1 -z )(1 -z,a )(1 -Õ(1/d)) ZZ a exp( v a + v b + T (v a , v b , •) 2 2d ) -exp(-Ω(log 1.8 n)) .

Again the last step is using Lemma 10 and the term exp(-Ω(log 1.8 n) is negligible. Combining the upper and lower bound, we know

log p([a, b]) = v a + v b + T (v a , v b , •) 2 2d -log Z -log Z a ± p , where p = O( z + z,a ) + Õ(1/d).

Now we turn to the most complicated term log p(w, [a, b] ). By definition we know

p(w, [a, b]) = E c,c [ 1 Z c exp( c, v w ) 1 Z c 1 Z c ,a exp( c , v a + c , v b + T (v a , v b , c )].

We will follow similar idea as before. Let F be the event that both c, c satisfy the equations in Lemma 1 and F be its negation. By Lemma 1 and union bound we know Pr[F] ≥ 1 -exp(-Ω(log 2 n)).

We again separate the co-occurrence probability based on the event F:

p(w, [a, b]) =E c,c [ 1 Z c exp( c, v w ) 1 Z c 1 Z c ,a exp( c , v a + c , v b + T (v a , v b , c )1 F ] + E c,c [ 1 Z c exp( c, v w ) 1 Z c 1 Z c ,a exp( c , v a + c , v b + T (v a , v b , c )1 F ].

For the second term, we can again use Lemma 8 to show that it is bounded by exp(-Ω(log 1.8 n)). Now, using techniques similar as before, we can prove

EQUATION

Now the final step is to use the fact that c and c are close to simplify the final formula. Let

A(c ) = E c|c [exp( c, v w )], by Lemma 9 we know A(c ) ∈ (1 ± w ) exp( v w , c ). Therefore E c,c [exp( c, v w ) exp( c , v a + c , v b + T (v a , v b , c ))] =E c [exp( c , v a + c , v b + T (v a , v b , c ))E c|c [exp( c, v w )]] =E c [exp( c , v a + c , v b + T (v a , v b , c ))A(c )] =(1 ± w )E c [exp( c , v a + c , v b + T (v a , v b , c ) + c , v w )] =(1 ± w )(1 ± Õ(1/d)) exp( v w + v a + v b + T (v a , v b , •) 2 2d ).

Here the last step is again by Lemma 10. Combining this with Equation equation 9 gives the result. 

= ( v w + v a + v b + T (v a , v b , •) 2 2d -2 log Z -log Z a ) + ( v a 2 2d + v b 2 2d + v w 2 2d -3 log Z) -( v w + v a 2 2d + v w + v b 2 2d -4 log Z) -( v a + v b + T (v a , v b , •) 2 2d -log Z -log Z a ) ± 7 = T (v a , v b , v w ) d ± 7 . B.3 AUXILIARY LEMMAS

(Y -E[Y ] ≥ 2 a 2 √ x + 2 a ∞ x) ≤ exp(-x) P (Y -E[Y ] ≤ -2 a 2 √ x) ≤ exp(-x).

Additional Lemmas We will use several tools developed in Arora et al. (2015) . The first lemma allows us to bound the probabilities the discourse vector c does not satisfy the results of Lemma 1. Lemma 8. Let F be any event that depends on the discourse vector c with probability at least 1 -exp(-Ω(log 2 n)), and F be its negation. Suppose r is a vector of norm O( √ d), then

E c [exp( r, c )1 F ] ≤ exp(-Ω(log 1.8 n)).

Further, if we consider two consecutive discourse vectors c, c , redefine F to be an event that can depend on both discourse vectors, again with probability at least 1 -exp(-Ω(log 2 n)). If r, r are two vectors of norm O( √ d) we have

E c,c [exp( r, c ) exp( r , c )1 F ] ≤ exp(-Ω(log 1.8 n)).

Proof. The proof of this lemma appears on page 20 in Arora et al. (2015) , as a step in the proof of their Theorem 2.2. For completeness, we reproduce (and slightly adapt) their argument here.

Observe that

E c [exp( r, c )1 F ] = E c [exp( r, c )1 r,c >0 1 F ] + E c [exp( r, c )1 r,c <0 1 F ].

The second term of B.3 is upper bounded by

E c [1 F ] ≤ exp(-Ω(log 2 n)).

Note that the first term of B.3 can be bounded as follows:

E c [exp( r, c )1 r,c >0 1 F ] ≤ E c [exp( αr, c )1 r,c >0 1 F ] ≤ E c [exp( αr, c )1 F ] for α > 1. Therefore, to obtain a bound on E c [exp( r, c )1 r,c >0 1 F ] is suffices to bound E c [exp( r, c )1 F ] when r = Ω( √ d).

Let z denote the random variable r, c , and let r(z) = 1 F . Using Lemma A.4 in Arora et al. (2015) , we have

E c [exp(z)r(z)] ≤ E c [exp(z)1 [t,∞] (z)],

where

t satisfies that E c [1 [t,∞] (z)] = Pr[z ≥ t] = E c [r(z)] ≤ exp(-Ω(log 2 n)).

Then by Lemma A.1 of Arora et al. (2015) , we have that t ≥ Ω(log .9 n). Finally, applying Corollary A.3 of Arora et al. (2015) , we have Proof. The proof of this lemma appears on page 21 in Arora et al. (2015) , again as a step in the proof of their Theorem 2.2. For completeness, we reproduce the argument here. where the last inequality follows from our model assumptions.

To get the lower bound, observe that

E c |c [exp(K √ d c -c )] + E c |c [exp(-K √ d c -c )] ≥ 2.

Therefore, the model assumptions imply that We end with the proof of Lemma 2.

Proof of Lemma 2. Just for this proof, we use the following notation. Let I d×d be the d-dimensional identity matrix, and let x 1 , x 2 , . . . , x n be i.i.d. draws from N (0, I d×d ). Let y i = x i 2 , and note that y 2 i is a standard χ-squared random variable with d degrees of freedom. Let κ be a positive constant, and let s 1 , s 2 , . . . , s n be i. We first cover the unit sphere by a finite number of metric balls of small radius. Then we show that with high probability, the partition function at the center of these balls is indeed bounded below by a constant. Finally, we show that the partition function evaluated at an arbitrary point on the unit sphere can't be too far from the partition function at one of the ball centers provided the norms of the v i are not too large. We finish by appropriately controlling the norms of the v i .

For > d -1 , cover the unit sphere in R d with N = ( 2 + 1) d balls of radius . Let c 1 , c 2 , . . . , c N be the centers of these balls (so that each c i is a unit vector). Let α ≥ 0 be a constant. Note that v j , c i = c j , s j • c i and v k , c i + T (v l , v k , c i ) = x k , s k (I + T (v l , •, •)) T c i are Gaussian random variables with mean 0.

Let F i be the event that there exists some j, k ∈ [n] such that v j , c i ≥ 0 and v k +T (v a , v k , •), c i ≥ 0 . Note that

Pr[ Fi ] ≤ Pr[∀j ∈ [n], v j , c i ≤ 0] + Pr[∀k ∈ [n], v k + T (v a , v k , •), c i ≤ 0] = n j=1 Pr[ v j , c i ≤ 0] + n k Pr[ v k + T (v a , v k , •), c i ≤ 0] ≤ 1 2 n + 1 2 n ≤ exp(-Θ(n)).

Let γ > 0. Let G i be the event that y i < γ

√ d. Set t = ( 1 √ 2 γ 2 -1 2 -1 2 ) 2 d, so that d+2 √ dt+2t = γ 2 d.

Then by Lemma 7, Pr[ Ḡi ] ≤ exp (-t) .

Let E = N i=1 F i n i=1 G i .

Assume that the word embeddings satisfy the event E. Let c i be a center of one of the covering balls such that c -c i 2 < . Let v j , v k be vectors that satisfies x j , c i ≥ -α and v k + T (v a , v k , •), c i ≥ -α. By Cauchy-Schwarz and the definition of E, we have

v j , c = v j , c i + v j , c -c i ≥ -v j c -c i ≥ -γκ √ d = -γκd -1/2 ≥

for some appropriate universal constant . Likewise, using the boundedness property of T , we have

v k + T (v a , v k , •), c ≥ - √ K √ d = - √ Kd -1/2 ≥ .

:

√ d). Later in Section 5 we verify that the tensors we learned indeed satisfy this condition. Now we are ready to state the concentration of partition functions:1 As we will see in Section 5, in practice it is easy to identify which words form a syntactic pair, so it is possible to condition on this event in training.

code for preprocessing, training, and experiments can be found at https://github.com/ abefrandsen/syntactic-rand-walk

obtained from https://nlp.stanford.edu/projects/glove/

obtained from https://fasttext.cc/docs/en/english-vectors.html

Figures and Tables:

Figure1: Graphical models of RAND-WALK (left) and our new model (right), depicting a syntactic word pair (w t , w t ). Green nodes correspond to observed variables, white nodes to latent variables.

Figure 2: Histograms of partition functions Z c,a (x-axis is Z c,a /E[Z c,a ])

we prove Corollary 1, which is just a simple calculation based on Theorem 1: Proof of Corollary 1. By the definition of PMI3, we know P M I3 = log p(w, [a, b]) + log p(a) + log p(b) + log p(w) -log p(w, a) -log p(w, b) -log p([a, b]).

c [exp(z)r(z)] ≤ E c [exp(z)1 [t,∞] (z)] = exp(-Ω(log 1.8 n)), which completes the proof for the first part of this lemma.The second part of this lemma can be proved in much the same fashion. By Cauchy-Schwarz,(E c,c [exp( r, c ) exp( r , c )1 F ]) 2 ≤ E c,c [exp( r, c ) 2 1 F ] E c,c [exp( r , c ) 2 1 F ] ≤ E c [exp( 2r, c )E c |c [1 F ]] E c [exp( 2r , c )E c|c [1 F ]] . Now we bound E c [exp( 2r, c )E c |c [1 F ]] using the same argument as above in the first part of this proof, replacing1 F with E c |c [1 F ],r with 2r, and r(z) = 1 F with r(z) = E c |z [1 F ]. In particular, we have E c [exp( 2r, c )E c |c [1 F ]] ≤ exp(-Ω(log 1.8 n)). Likewise, we have the same bound forE c [exp( 2r , c )E c|c [1 F ]].Putting these two together, we conclude thatE c,c [exp( r, c ) exp( r , c )1 F ] ≤ E c [exp( 2r, c )E c |c [1 F ]] 1/2 E c [exp( 2r , c )E c|c [1 F ]] 1/2 ≤ exp(-Ω(log 1.8 n)),as desired.The next lemma allows us to handle the difference between two consecutive discourse vectors: Lemma 9. Let c, c be two discourse vectors that are adjacent, let v w be a word embedding satisfying v w ≤ K √ d, and let A(c) := E c |c [exp( v w , c )], then we have A(c) ∈ (1 ± w ) exp( v w , c ).

Since v w ≤ K √ d for some constant K , we have that v w , c -c ≤ v w c -c ≤ K √ d cc . Hence, A(c) = E c |c [exp( v w , c )] = exp( v w , c )E c |c [exp( v w , c -c )] ≤ exp( v w , c )E c |c [K √ d c -c )] ≤ (1 + w ) exp( v w , c ),

c |c [exp(-K √ d c -c )] ≥ 1w .Hence,A(c) = exp( v w , c )E c |c [exp( v w , c -c )] ≥ exp( v w , c )E c |c [exp(K √ d c -c )] ≥ (1w ) exp( v w , c ).The next lemma we use gives bound on E[exp( v, c )] where c is a uniform vector on the unit sphere.Lemma 10. [Lemma A.5 inArora et al. (2015)] Let v ∈ R d be a fixed vector with norm v = O( √ d). For random variable c with uniform distribution over the sphere, we have thatlog E[exp( v, c )] = v 2 2d ± c ,where c = Õ(1/d).

i.d. draws from a distribution supported on [0, κ]. Let v i = s i • x i . Define Z c = n i=1 exp( v i , c ), and define Z c,a = n i=1 exp( v i , c + T (v a , v i , c)).

Definition 1 (Syntactic RAND-WALK model). The model consists of the following: 1. Each word w in vocabulary has a corresponding embedding v w ∼ s • vw , where s ∈ R ≥0 is bounded by κ and E[s] = τ ; vw ∼ N (0, I d×d ). 2. The sequence of discourse vectors c 1 , ..., c t are generated by a random walk on the unit sphere, c t -c t+1 ≤ w / √ d and the stationary distribution is uniform. 3. For each c t , with probability 1-p syn , it generates one word w t with probability proportional to exp( c t , v wt ). 4. For each c t , with probability p syn , it generates a syntactic pair w t , w t with probability proportional to exp( c t , v wt ) and exp( c t , v w t + T (v wt , v w t , c

Table content: <table/>

Top 10 words relating to various adjective-noun phrases

Table content: <table><tr><td colspan="2">civil war</td><td colspan="2">complex numbers</td><td/><td colspan="2">national park</td></tr><tr><td>additive</td><td>tensor</td><td>additive</td><td>tensor</td><td/><td colspan="2">additive</td><td>tensor</td></tr><tr><td>war</td><td>civil</td><td>complex</td><td>complex</td><td/><td colspan="2">national</td><td>yosemite</td></tr><tr><td>civil</td><td>somalian</td><td>numbers</td><td colspan="2">eigenvalues</td><td>park</td><td>denali</td></tr><tr><td>military</td><td>eicher</td><td>number</td><td>numbers</td><td/><td>parks</td><td>gunung</td></tr><tr><td>army</td><td>crimean</td><td>function</td><td>hermitian</td><td/><td colspan="2">recreation kenai</td></tr><tr><td>conflict</td><td>laotian</td><td>complexes</td><td colspan="2">quaternions</td><td>forest</td><td>nps</td></tr><tr><td>wars</td><td>francoist</td><td>functions</td><td>marginalia</td><td/><td colspan="2">historic</td><td>teton</td></tr><tr><td>fought</td><td>ulysses</td><td>integers</td><td>azadi</td><td/><td colspan="2">heritage</td><td>refuges</td></tr><tr><td colspan="2">revolutionary liberian</td><td colspan="2">multiplication rationals</td><td/><td colspan="2">wildlife</td><td>tilden</td></tr><tr><td>forces</td><td colspan="2">confederate algebraic</td><td colspan="4">holomorphic memorial snowdonia</td></tr><tr><td>outbreak</td><td>midst</td><td>integer</td><td colspan="3">rhythmically south</td><td>jigme</td></tr><tr><td/><td colspan="6">Table 2: Top 10 words relating to various verb-object phrases</td></tr><tr><td/><td>took place</td><td colspan="2">took part</td><td/><td colspan="2">took lead</td></tr><tr><td colspan="2">additive tensor</td><td colspan="2">additive tensor</td><td colspan="3">additive tensor</td></tr><tr><td>place</td><td>occurred</td><td>part</td><td>participated</td><td>took</td><td/><td>equalised</td></tr><tr><td>took</td><td>scheduled</td><td>took</td><td colspan="2">participating lead</td><td/><td>halftime</td></tr><tr><td>death</td><td colspan="2">commenced taking</td><td>participate</td><td colspan="2">taking</td><td>nailing</td></tr><tr><td>take</td><td>event</td><td>take</td><td>culminated</td><td>take</td><td/><td>kenseth</td></tr><tr><td>taking</td><td>events</td><td>taken</td><td>organised</td><td colspan="2">went</td><td>fumbled</td></tr><tr><td>birth</td><td>culminated</td><td>takes</td><td colspan="2">participation led</td><td/><td>touchdown</td></tr><tr><td>taken</td><td>thursday</td><td colspan="2">became hostilities</td><td colspan="2">taken</td><td>furlongs</td></tr><tr><td>takes</td><td>friday</td><td>came</td><td colspan="3">culminating came</td><td>trailed</td></tr><tr><td>came</td><td>postponed</td><td>put</td><td>invasion</td><td>put</td><td/><td>keselowski</td></tr><tr><td>held</td><td>lasted</td><td>whole</td><td>undertook</td><td colspan="2">wanted</td><td>peloton</td></tr></table>

Correlation measures between human judgments and embedding-based similarity scores (Spearman, Pearson) for adjective-noun phrases across three embedding sets (top scores in each row are bolded)

Table content: <table><tr><td/><td>additive</td><td>weighted1 weighted2</td><td>tensor</td><td>sif</td><td>sif+tensor</td></tr><tr><td>rw</td><td>.446,</td><td/><td/><td/></tr></table>

Correlation measures between human judgments and embedding-based similarity scores (Spearman, Pearson) for verb-object phrases

Table content: <table><tr><td/><td>additive</td><td>weighted1 weighted2</td><td>tensor</td><td>sif</td><td>sif+tensor</td></tr><tr><td>rw</td><td>.379,</td><td/><td/><td/></tr></table>

Top 10 words relating to various verb-object phrases

Table content: <table><tr><td colspan="3">giving birth</td><td colspan="2">solve problem</td><td colspan="2">changing name</td></tr><tr><td colspan="2">additive</td><td>tensor</td><td>additive</td><td>tensor</td><td>additive</td><td>tensor</td></tr><tr><td>birth</td><td/><td>stillborn</td><td>problem</td><td>analytically</td><td>name</td><td>rebrand</td></tr><tr><td>giving</td><td/><td>unborn</td><td>solve</td><td>creatively</td><td>changing</td><td>refocus</td></tr><tr><td>place</td><td/><td>pregnant</td><td>problems</td><td>solve</td><td>change</td><td>redevelop</td></tr><tr><td>death</td><td/><td>fathered</td><td>solving</td><td colspan="2">subconsciously changed</td><td>rebranding</td></tr><tr><td>give</td><td/><td>litters</td><td>solved</td><td>devising</td><td>names</td><td>forgo</td></tr><tr><td>date</td><td/><td colspan="2">childbirth solves</td><td>devise</td><td>referring</td><td>divest</td></tr><tr><td>gave</td><td/><td>remarry</td><td colspan="2">understand proactively</td><td>title</td><td>rechristened</td></tr><tr><td colspan="3">summary newborn</td><td>resolve</td><td>solvers</td><td>word</td><td>afresh</td></tr><tr><td>gives</td><td/><td colspan="2">gestation solution</td><td>extrapolate</td><td>actually</td><td>rebranded</td></tr><tr><td>given</td><td/><td>eloped</td><td>question</td><td>rationalize</td><td colspan="2">something opting</td></tr><tr><td/><td/><td colspan="5">Table 6: Top 10 words relating to various adjective-noun phrases</td></tr><tr><td colspan="3">united states</td><td colspan="2">soviet union</td><td colspan="2">european union</td></tr><tr><td>additive</td><td colspan="2">tensor</td><td>additive</td><td>tensor</td><td>additive</td><td>tensor</td></tr><tr><td>united</td><td colspan="2">united</td><td>union</td><td>union</td><td>european</td><td>eec</td></tr><tr><td>states</td><td colspan="2">states</td><td>soviet</td><td>soviet</td><td>union</td><td>ebu</td></tr><tr><td>us</td><td colspan="2">emigrating</td><td>ussr</td><td>sfsr</td><td>europe</td><td>dismemberment</td></tr><tr><td>canada</td><td colspan="2">emirates</td><td>russian</td><td>disintegration</td><td>countries</td><td>retort</td></tr><tr><td colspan="3">countries immigrated</td><td colspan="2">communist lyudmila</td><td>federation</td><td>detracts</td></tr><tr><td colspan="4">california cartographic russia</td><td colspan="2">dismemberment nations</td><td>arguable</td></tr><tr><td>usa</td><td colspan="2">extradited</td><td>soviets</td><td>brezhnev</td><td>soviet</td><td>kely</td></tr><tr><td>america</td><td colspan="2">senate</td><td>moscow</td><td>ussr</td><td colspan="2">organisations eea</td></tr><tr><td colspan="3">kingdom lighthouses</td><td>sfsr</td><td>perestroika</td><td>socialist</td><td>geosciences</td></tr><tr><td>nations</td><td colspan="2">stateside</td><td>ukraine</td><td>zhukov</td><td>eu</td><td>bugzilla</td></tr></table>

Top 10 words relating to various adjective-noun phrases

Table content: <table><tr><td colspan="2">expensive taste</td><td colspan="2">awful taste</td><td colspan="2">refined taste</td></tr><tr><td>additive</td><td>tensor</td><td>additive</td><td>tensor</td><td>additive</td><td>tensor</td></tr><tr><td>taste</td><td>expensive</td><td>taste</td><td>taste</td><td>taste</td><td>refined</td></tr><tr><td>expensive</td><td>taste</td><td>awful</td><td>awful</td><td>refined</td><td>taste</td></tr><tr><td>cheaper</td><td>costly</td><td>smell</td><td>smell</td><td>flavor</td><td>sweeter</td></tr><tr><td>flavor</td><td>prohibitively</td><td colspan="3">unpleasant disagreeable tastes</td><td>sensuous</td></tr><tr><td>tastes</td><td colspan="2">computationally flavor</td><td>fruity</td><td>smell</td><td>elegant</td></tr><tr><td>unpleasant</td><td>cheaper</td><td colspan="2">refreshing aroma</td><td>flavour</td><td>disagreeable</td></tr><tr><td colspan="2">inexpensive luxurious</td><td colspan="2">something fishy</td><td>aroma</td><td>elegance</td></tr><tr><td>smell</td><td>sweeter</td><td>things</td><td>pungent</td><td>sour</td><td>neoclassicism</td></tr><tr><td>costly</td><td>inexpensive</td><td>really</td><td>odor</td><td colspan="2">ingredients refinement</td></tr><tr><td colspan="2">ingredients afford</td><td>odor</td><td>becuase</td><td>qualities</td><td>perfected</td></tr><tr><td/><td colspan="5">Table 8: Top 10 words relating to various adjective-noun phrases</td></tr><tr><td colspan="2">close friend</td><td colspan="2">best friend</td><td colspan="2">dear friend</td></tr><tr><td>additive</td><td>tensor</td><td>additive</td><td>tensor</td><td>additive</td><td>tensor</td></tr><tr><td>close</td><td>confidante</td><td>best</td><td>confidante</td><td>friend</td><td>friend</td></tr><tr><td>friend</td><td>confidant</td><td>friend</td><td>confides</td><td>dear</td><td>confidante</td></tr><tr><td>friends</td><td>coworker</td><td>actor</td><td colspan="3">misinterpreting colleague coworker</td></tr><tr><td>confidant</td><td>close</td><td>awards</td><td>coworker</td><td>lover</td><td>colleague</td></tr><tr><td>colleague</td><td>friend</td><td>actress</td><td>memoirists</td><td>friends</td><td>dear</td></tr><tr><td>closest</td><td>confided</td><td>award</td><td>protege</td><td colspan="2">girlfriend confidant</td></tr><tr><td colspan="4">collaborator schoolmates nominated presumes</td><td>beloved</td><td>dearest</td></tr><tr><td>confidante</td><td>classmate</td><td>friends</td><td>helpfully</td><td colspan="2">boyfriend protege</td></tr><tr><td>classmate</td><td>protege</td><td>girlfriend</td><td>matth</td><td colspan="2">classmate confided</td></tr><tr><td>brother</td><td>cuz</td><td>writer</td><td>regretfully</td><td colspan="2">roommate collaborator</td></tr></table>

Tail bound for χ 2 distribution We will use the following tail bounds for the generalized χ 2squared distribution. Lemma 7.Laurent & Massart (2000) Let y 1 , . . . , y d be i.i.d. standard normal random variables, and let a 1 , . . . , a d be nonnegative real numbers. Set Y = d i=1 a i y 2 i and a = (a 1 , a 2 , . . . , a d ). Then the following hold for any positive real number x:

Table content: <table><tr><td>P</td></tr></table>

Peer review (iclr2019):
 The paper deals with further development of RAND-WALK model of Arora et al. There are stable idioms, adjective-noun pairs and etc that are not covered by RAND-WALK, because sometimes words from seemingly different contexts can join to form a stable idiom. So, the idea of paper is to introduce a tensor T and a stable idiom (a,b) is embedded into v_{ab}=v_a+v_b+T(v_a, v_b,.) and is emitted with some probability p_sym (proportional to exp(v_{ab} times context)). The latter model is similar to RAND-WALK, so it is not surprising that statistical functions there are similarly concentrated. Finally, there exists an expression, PMI3(u,v,w), that shows the correlation between 3 words, and that can be estimated from the data directly. It is proved that Tucker decomposition of that tensor gives us all words embeddings together with tensor T. Thus, from the latter we will obtain a tool for finding embeddings of idioms (i.e. v_a+v_b+T(v_a, v_b,.)). Theoretical analysis seems correct (I have not checked all the statements thoroughly, but I would expect formulations to be true). The only problem I see is that phrase similarity part is not convincing. I cannot understand from that part whether T(v_a, v_b,.) addition to v_a+v_b gives any improvement or not.