Title: LEARNING SEMANTIC WORD RESPRESENTATIONS VIA TENSOR FACTORIZATION

Abstract: Many state-of-the-art word embedding techniques involve factorization of a cooccurrence based matrix. We aim to extend this approach by studying word embedding techniques that involve factorization of co-occurrence based tensors (Nway arrays). We present two new word embedding techniques based on tensor factorization, and show that they outperform multiple commonly used embedding methods when used for various NLP tasks on the same training data. Also, to train one of the embeddings, we present a new joint tensor factorization problem and an approach for solving it. Furthermore, we modify the performance metrics for the Outlier Detection task (Camacho-Collados & Navigli ( 2016)) to measure the quality of higher-order relationships that a word embedding captures. Our tensor-based methods significantly outperform existing methods at this task when using our new metric. Finally, we demonstrate that vectors in our embeddings can be composed multiplicatively to create different vector representations for each meaning of a polysemous word in a way that cannot be done with other common embeddings. We show that this property stems from the higher order information that the vectors contain, and thus is unique to our tensor based embeddings.

INTRODUCTION:

Word embeddings have been used to improve the performance of many NLP tasks including language modelling (Bengio et al. (2003) ), machine translation (Bahdanau et al. (2014) ), and sentiment analysis (Kim (2014) ). The broad applicability of word embeddings to NLP implies that improvements to their quality will likely have widespread benefits for the field.

The word embedding problem is to learn a mapping η : V → R k (k ≈ 100-300 in most applications) that encodes meaningful semantic and/or syntactic information. For instance, in many word embeddings, η(car) ≈ η(truck), since the words are semantically similar.

More complex relationships than similarity can also be encoded in word embeddings. For example, we can answer analogy queries of the form a : b :: c : ? using simple arithmetic in many stateof-the-art embeddings (Mikolov et al. (2013) ). The answer to bed : sleep :: chair : x is given by the word whose vector representation is closest to η(sleep) -η(bed) + η(chair) (≈ η(sit)). Other embeddings may encode such information in a nonlinear way (Jastrzebski et al. (2017) ). Mikolov et al. (2013) demonstrates the additive compositionality of their word2vec vectors: one can sum vectors produced by their embedding to compute vectors for certain phrases rather than just vectors for words. Later in this paper, we will show that our embeddings naturally give rise to a form of multiplicative compositionality that has not yet been explored in the literature. Almost all recent word embeddings rely on the distributional hypothesis (Harris) , which states that a word's meaning can be inferred from the words that tend to surround it. To utilize the distributional hypothesis, many embeddings are given by a low-rank factor of a matrix derived from co-occurrences in a large unsupervised corpus. For examples of this, see Pennington et al. (2014) ; Murphy et al. (2012) ; Levy & Goldberg (2014) and Salle et al. (2016) . Approaches that rely on matrix factorization only utilize pairwise co-occurrence information in the corpus. We aim to generalize this approach by creating word embeddings given by factors of tensors containing higher order co-occurrence data.

RELATED WORK:

Some common word embeddings related to co-occurrence based matrix factorization include GloVe (Pennington et al. (2014) ), word2vec (Levy & Goldberg (2014) ), LexVec (Salle et al. (2016) ), and NNSE (Murphy et al. (2012) ). In contrast, our work studies word embeddings given by factorization of tensors. An overview of tensor factorization methods is given in Kolda & Bader (2009) .

In particular, our work uses symmetric factorization of symmetric tensors. Theoretical foundations for this problem have been studied and outlined in (Comon et al. (2008) ). We note that while finding the best rank-R nonnegative approximation of nonnegative tensors is a well-posed problem (Lim & Comon (2009a) , Qi et al. (2016) ), relatively little is known about guarantees on the existence of best rank-R symmetric tensor approximation of a symmetric tensor, which may not exist in general, especially over R (Qi et al. (2017)) 1 . Further, it may be NP-hard to obtain these factorizations in general. Nevertheless, as is done in many applications that factor the third order cumulant, we are merely seeking a (not necessarily best) real symmetric rank-R approximation to the symmetric tensor.

Recently, under incoherency assumptions on the factors, a method using factorization of symmetric tensors was proposed to create a generic word embedding Sharan & Valiant (2017) , but the results were not evaluated extensively. Our work studies this idea in much greater detail, fully demonstrating the viability of tensor factorization as a technique for training word embeddings. 2 In general, tensor factorization has also been applied to NLP (Van de Cruys et al. (2013) ; Zhang et al. (2014) ), as has nonnegative factorization of nonnegative tensors (Van de Cruys ( 2009)).

Composition of word vectors to create novel representations has been studied in depth, including additive, multiplicative, and tensor-based methods (Mitchell & Lapata (2010) ; Blacoe & Lapata (2012) ). Typically, composition is used to create vectors that represent phrases or sentences. Our work, instead, shows that pairs of word vectors can be composed multiplicatively to create different vector representations for the various meanings of a single polysemous word.

Finally, we note that although other tensor factorizations such as the Higher-Order SVD (Kolda & Bader (2009) ) and Tensor Train (TT) (Oseledets (2011) ) may be adapted to find word embeddings from the co-occurance tensor, in this work we only consider the symmetric CP decomposition, leaving the study of other tensor decompositions to future work.

MATHEMATICAL PRELIMINARIES:



NOTATION:

Throughout this paper we will write scalars in lowercase italics α, vectors in lowercase bold letters v, matrices with uppercase bold letters M, and tensors (of order N > 2) with Euler script notation X, as is standard in the literature.

POINTWISE MUTUAL INFORMATION:

Pointwise mutual information (PMI) is a useful property in NLP that quantifies the likelihood that two words co-occur (Levy & Goldberg (2014) ). It is defined as:

P M I(x, y) = log p(x, y) p(x)p(y)

where p(x, y) is the probability that x and y occur together in a given fixed-length context window in the corpus, irrespective of order.

It is often useful to consider the positive PMI (PPMI), defined as:

P P M I(x, y) := max(0, P M I(x, y))

since negative PMI values have little grounded interpretation (Bullinaria & Levy (2007) ; Levy & Goldberg (2014) ; Van de Cruys (2009) ).

Given an indexed vocabulary V = {w 1 , . PMI can be generalized to N variables. While there are many ways to do so (Van de Cruys ( 2011)), in this paper we use the form defined by:

P M I(x N 1 ) = log p(x 1 , . . . , x N ) p(x 1 ) • • • p(x N )

where p(x 1 , . . . , x N ) is the probability that all of x 1 , . . . , x N occur together in a given fixed-length context window in the corpus, irrespective of their order.

In this paper we study 3-way PPMI tensors M, where m ijk = P P M I(w i , w j , w k ), as this is the natural higher-order generalization of the PPMI matrix. We leave the study of creating word embeddings with N -dimensional PPMI tensors (N > 3) to future work.

TENSOR FACTORIZATION:

Just as the rank-R matrix decomposition is defined to be the product of two factor matrices (M ≈ UV ), the canonical rank-R tensor decomposition for a third order tensor is defined to be the product of three factor matrices (Kolda & Bader (2009) ):

EQUATION

where ⊗ is the outer product:

(a ⊗ b ⊗ c) ijk = a i b j c k .

This is also commonly referred to as the rank-R CP Decomposition. Elementwise, this is written as:

x ijk ≈ R r=1

u ir v jr w kr = u :,i * v :,j , w :,k , where * is elementwise vector multiplication and u :,i is the i th row of U. In our later section on multiplicative compositionality, we will see this formulation gives rise to a meaningful interpretation of the elementwise product between vectors in our word embeddings.

Symmetric CP Decomposition. In this paper, we will consider symmetric CP decomposition of nonnegative tensors (Lim (2005) ; Kolda & Bader (2009) ). Since our N -way PPMI is nonnegative and invariant under permutation, the PPMI tensor M is nonnegative and supersymmetric, i.e. m ijk = m σ(i)σ(j)σ(k) ≥ 0 for any permutation σ ∈ S 3 .

In the symmetric CP decomposition, instead of factorizing M ≈ U, V, W , we factorize M as the triple product of a single factor matrix

U ∈ R |V |×R such that M ≈ U, U, U

In this formulation, we use U to be the word embedding so the vector for w i is the i th row of U similar to the formulations in: Levy & Goldberg (2014) ; Murphy et al. (2012) ; Pennington et al. (2014) .

WHY FACTORIZE THE THIRD MOMENT?:

Factorizing the PPMI tensor of the third moment of co-occurrence is a natural extension of current methods and justifiable for a number of other reasons. For one, if NLP tasks such as the semantic analogy task depend on how embedding vectors cluster, the goal of training a word embedding is to find a map of words to vectors such that the vectors for semantically similar words form a cluster. For identifying the clusters of a planted partition model such as the Stochastic Block Model (SBM), the spectral factorization of node interactions completely derived from pair-wise interactions is sufficient for discovering the disjoint clusters (Belkin & Niyogi (2001) ; Krzakala et al. (2013) ; Spielman ( 2007)).

The existence of polysemous words in the corpus necessitate the assumption of a Mixed Membership (MM) model, since polysemous words belong to multiple different clusters of meaning (Foulds (2017) ). In this case, it is well-known that factorizing the third moment provably recovers the parameters of planted Mixed Membership-SBM model (Anandkumar et al. (2013) ) in a way that only capturing pair-wise interactions, i.e. the second order moment (uniquely) cannot. Further, from the perspective of using Gaussian mixture models for capturing polysemy in word embeddings (Athiwaratkun & Wilson (2017) ) it is known that factorizing the third moments can provably identify the isotropic Gaussian mixture models (Anandkumar et al. (2014)) .

For an analysis of the degree to which our tensor factorization-based embeddings capture polysemy, we refer the reader to Section on multiplicative compositionality on Page 9. Another perspective is that considering the third order moment further contextualizes the co-occurrence matrix, adding information that was lost by only considering matrix factorization.

While in this work we do not require any provable results for the derived word embeddings, we are motivated by several recent developments successfully applying tensor factorization for addressing related machine learning problems.

METHODOLOGIES COMPUTING THE SYMMETRIC CP DECOMPOSITION:

The Θ(|V | 3 ) size of the third order PPMI tensor presents a number of computational challenges. In practice, |V | can vary from 10 4 to 10 6 , resulting in a tensor whose naive representation requires at least 4 * 10, 000 3 bytes = 4 TB of floats. Even the sparse representation of the tensor takes up such a large fraction of memory that standard algorithms such as successive rank-1 approximation (Wang & Qi (2007) ; Mu et al. (2015) ) and alternating least-squares (Kolda & Bader (2009) ) are infeasible for our uses. Thus, in this paper we will consider a stochastic online formulation similar to that of (Maehara et al. (2016) ).

We optimize the CP decomposition in an online fashion, using small random subsets M t of the nonzero tensor entries to update the decomposition at time t. In this minibatch setting, we optimize the decomposition based on the current minibatch and the previous decomposition at time t -1. To update U (and thus the symmetric decomposition), we first define an n-dimensional decomposition loss L (n) (M t , U) and minimize this loss with respect to U using Adam (Kingma & Ba (2014)).

At each time t, we take M t to be all co-occurrence triples (weighted by PPMI) in a fixed number of sentences (around 1,000) from the corpus. We continue training until we have depleted the entire corpus.

For M t to accurately model M, we also include a certain proportion of elements with zero PPMI (or "negative samples") in M t , similar to that of Salle et al. (2016) .

We use empirically-found hyperparameters for training using Random Search (Bergstra & Bengio (2012) ) and leave theoretical discovery of optimal hyperparameters (such as negative sample proportion) to future work.

WORD EMBEDDING PROPOSALS:

CP-S. The first embedding we propose is based on symmetric CP decomposition of the PPMI tensor M as discussed in the mathematical preliminaries section. The optimal setting for the word embedding W is:

W := argmin U ||M -U, U, U || F

Since we cannot feasibly compute this exactly, we minimize the loss function defined as the squared error between the values in M t and their predicted values:

L (3) (M t , U) = m t ijk ∈M t (m t ijk - R r=1

u ir u jr u kr ) 2 using the techniques discussed in the previous section. This idea can be extended to n-dimensional tensors by considering the suitable generalization of this loss function given by L (n) , but we only consider at most third order tensors in this work.

JCP-S. A potential problem with CP-S is that it is only trained on third order information. To rectify this issue, we propose a novel joint tensor factorization problem we call Joint Symmetric Rank-R CP Decomposition. In this problem, the input is the fixed rank R and a list of supersymmetric tensors M n of different orders but whose axis lengths all equal |V |. Each tensor M n is to be factorized via rank-R symmetric CP decomposition using a single |V | × R factor matrix U.

To produce a solution, we first define the loss at time t to be the sum of the reconstruction losses of each different tensor:

L joint ((M t ) N n=2 , U) = N n=2 L (n) (M t n , U),

where M n is an n-dimensional supersymmetric PPMI tensor. We then minimize the loss with respect to U. Since we are using at most third order tensors in this work, we assign our word embedding W to be:

W := argmin U L joint (M 2 , M 3 , U) = argmin U L (2) (M 2 , U) + L (3) (M 3 , U)

This problem is a specific instance of Coupled Tensor Decomposition which has been studied in the past (Acar et al. (2011) ; Naskovska & Haardt (2016) ). In this problem, the goal is to factorize multiple tensors using at least one factor matrix in common. A similar formulation to our problem can be found in Comon et al. (2015) , which studies blind source separation using the algebraic geometric aspects of jointly factorizing numerous supersymmetric tensors (to unknown rank). However, we attack the problem numerically while they outline some generic rank properties of such a decomposition rather. In our formulation the rank is fixed and an approximate solution must be found. Exploring the connection between the theoretical aspects of joint decomposition and quality of word embeddings would be an interesting avenue for future work.

To the best of our knowledge this is the first study of Joint Symmetric Rank-R CP Decomposition, and the first application of Coupled Tensor Decomposition to word embedding.

SHIFTED PMI:

In the same way Levy & Goldberg (2014) considers factorization of positive shifted PMI matrices, we consider factorization of positive shifted PMI tensors M, where m ijk = max(P M I(w i , w j , w k ) -α, 0) for some constant shift α. We empirically found that different levels of shifting resulted in different qualities of word embeddings -the best shift we found for CP-S was a shift of α ≈ 2.7, whereas any nonzero shift for JCP-S resulted in a worse embedding across the board. When we discuss evaluation we report the results given by factorization of the PPMI tensors shifted by the best value we found for each specific embedding.

COMPUTATIONAL NOTES:

When considering going from two dimensions to three, it is perhaps necessary to discuss the computational issues in such a problem size increase. However, it should be noted that the creation of pre-trained embeddings can be seen as a pre-processing step for many future NLP tasks, so if the training can be completed once, it can be used forever thereafter without having to take training time into account. Despite this, we found that the training of our embeddings was not considerably 2014)), but found that considering this nonnegative decomposition did not significantly change the results we got on downstream tasks either for CP decomposition or Joint CP decomposition. We thus decide to only report results on the simpler case of unrestricted CP decomposition.

EVALUATION:

In this section we present a quantitative and qualitative evaluation of our embeddings against an informationless embedding and state-of-the-art baselines. Our baselines are:

1. Random (random vectors with I.I.D. entries normally distributed with mean 0 and variance 1 2 ), for comparing against a model with no meaningful information encoded. This provides a hard baseline that all embeddings should outperform. For a fair comparison, we trained each model on the same corpus of 10 million sentences gathered from Wikipedia. We removed stopwords and words appearing fewer than 1,000 times (110 million tokens total) to reduce noise and uninformative words.

The baselines were trained using the recommended hyperparameters from their original publications, and all stochastic optimizers were used their default settings. Hyperparameters are always consistent across evaluations. The best hyperparameter settings we found for each embedding are found in Table 1 .

Because of the dataset size, the results shown should be considered a proof of concept rather than an objective comparison to state-of-the-art pre-trained embeddings. Due to the natural computational challenges arising from working with tensors, we leave creation of a full-scale production ready embedding based on tensor factorization to future work.

As is commonly done in the literature (Mikolov et al. (2013) ; Murphy et al. ( 2012)), we use 300dimensional vectors for our embeddings and all word vectors are normalized to unit length prior to evaluation.

The numbers presented for all stochastic tasks (such as the supervised ML tasks) are the mean result from 10 random restarts.

QUANTITATIVE TASKS:

Outlier Detection. The Outlier Detection task (Camacho-Collados & Navigli ( 2016)) is to determine which word in a list L of n+1 words is unrelated to the other n which were chosen to be related.

For each w ∈ L, one can compute its compactness score c(w), which is the compactness of L \ {w}. c(w) is explicitly computed as the mean similarity of all word pairs (w i , w j ) : w i , w j ∈ L \ {w}.

The predicted outlier is argmax w∈L c(w), as the n related words should form a compact cluster with high mean similarity.

We use the WikiSem500 dataset (Blair et al. (2016) ) which includes sets of n = 8 words per group gathered based on semantic similarity. Thus, performance on this task is correlated with the amount of semantic information encoded in a word embedding. Performance on this dataset was shown to be well-correlated with performance at the common NLP task of sentiment analysis (Blair et al. (2016) ).

The two metrics associated with this task are accuracy and Outlier Position Percentage (OPP). Accuracy is the fraction of cases in which the true outlier correctly had the highest compactness score. OPP measures how close the true outlier was to having the highest compactness score, rewarding embeddings more for predicting the outlier to be in 2 nd place rather than n th when sorting the words by their compactness score c(w).

3-way Outlier Detection. As our tensor-based embeddings encode higher order relationships between words, we introduce a new way to compute c(w) based on groups of 3 words rather than pairs of words. We define the compactness score for a word w to be:

c(w) = vi 1 =vw vi 2 =vw,vi 1 vi 3 =vw,vi 1 ,vi 2 sim(v i1 , v i2 , v i3 ),

where sim(•) denotes similarity between a group of 3 vectors. sim(•) is defined as:

sim(v 1 , v 2 , v 3 ) = 1 3 3 i=1 ||v i - 1 3 3 j=1 v j || 2 -1

We call this evaluation method OD3.

The purpose of OD3 is to evaluate the extent to which an embedding captures 3 rd order relationships between words. As we will see in the results of our quantitative experiments, our tensor methods outperform the baselines on OD3, which validates our approach.

This approach can easily be generalized to ODN (N > 3), but again we leave the study of higher order relationships to future work.

Simple supervised tasks. Jastrzebski et al. (2017) points out that the primary application of word embeddings is transfer learning to actual NLP tasks. They argue that to evaluate an embedding's ability to transfer information to a relevant task, one must measure the embedding's accessibility of information for actual downstream tasks. To do so, one must observe the performance of simple supervised tasks as training set size increases, which is commonly done in transfer learning evaluation (Jastrzebski et al. (2017) ). If an algorithm using a word embedding performs well with just a small amount of training data, then the information encoded in that embedding is easily accessible.

The simple supervised downstream tasks we use to evaluate the embeddings are as follows:

1. Word classification. We consider the task of labelling a word's part of speech based solely on its word vector using a simple supervised classifier (Logistic Regression) as suggested in Jastrzebski et al. (2017) . Performance at this task is a direct measure of the amount of syntactic information encoded in the embedding. Using different amounts of training data for the classifier will tell us how easily accessible such information is in that embedding. The dataset we use is the Penn Treebank (Marcus et al. (1994) ), which contains 35,000 PoS tagged words, and we use a 85/15 train/test split.

2. Sentiment analysis. We also consider a sentiment analysis task as described by Schnabel et al. (2015) . To train the classifier we use the suggested Large Movie Review dataset (Maas et al. (2011) ) which contains 50,000 sentiment-labeled movie reviews.

All code is implemented using scikit-learn or TensorFlow and uses the suggested train/test split.

Word similarity. To present results on the most standard word embedding evaluation technique, we evaluate the embeddings using word similarity on the common MEN, MTurk, RW, and SimLex999 datasets (Bruni et al. (2014) ; Radinsky et al. (2011) ; Luong et al. (2013) ; Hill et al. (2015) ). For an overview of word similarity evaluation, see Schnabel et al. (2015) . CP-S performs the best for OD3 by a decent margin, which is sensible given that is is trained on third order information only. This is also indicative of OD3's ability to measure the amount of third order information encoded in an embedding. Since the WikiSem500 dataset is focused on semantic relationships, performance at this task demonstrates the quality of semantic information encoded in our embeddings.

QUANTITATIVE RESULTS:

It is perhaps surprising that CP-S performs so well in the second order case of OD2, but this could be justified by the fact that third order information sheds light on second order information in a way that is not invertible. To illustrate this point, consider three words w, x, y. If w often co-occurs with both x and y, it is clear that w also often co-occurs with x, but the separate statements that w co-occurs with x and w co-occurs with y does not imply anything about the 3-way co-occurrence of (w, x, y).

Further, the pairwise co-occurrence of x and y can be extracted from the 3-way co-occurrence data: #(x, y) = z∈V #(x, y, z). It is thus believable that utilizing third order co-occurrence can lead to improved performance on tasks that rely on pairwise information.

Word classification results. The results are shown in Figure 1 . At this task, we notice that when 100% of the training data is presented, SGNS outperforms all other embeddings at this task. Since this task is a measure of quality of syntactic information encoded in an embedding, these results are an indication that perhaps SGNS encodes the most amount of syntactic information of all the embeddings presented here.

However, when training data is limited (restricting training data to 10%/30%), it is evident that our tensor-based embeddings outperform the other baselines. So even though SGNS eventually is able to provide higher quality syntactic information when enough training data is provided, this information is encoded more readily in our embeddings for supervised tasks to use, a favorable property for the sake of transfer learning. 3 . In this task, JCP-S is the dominant method across all levels of training data, further showing that exploiting both second and third order co-occurrence data leads to higher quality semantic information being encoded in the embedding.

Further theoretical research is needed to understand why JCP-S outperforms CP-S at this task, but its superior performance relative to the baselines across all levels of training data in these experiments demonstrates the quality of semantic information encoded by JCP-S.

Based on the clear relative success of our embeddings on these tasks, we can see that utilizing tensor factorization to create word representations has the propensity to encode a greater amount of semantic information than standard state-of-the-art pairwise or matrix-based word embedding methods.

Word Similarity results. We show the word similarity results in Table 4 . As we can see, our embeddings perform competitively with the state-of-the-art at these tasks. It is worth including these results as the word similarity task is a very common way of evaluating embedding quality in the literature. However, due to the many intrinsic problems with evaluating word embeddings using word similarity (Faruqui et al. (2016) ), we do not read further into these results.

MULTIPLICATIVE COMPOSITIONALITY:

We find that even though they are not explicitly trained to do so, our tensor-based embeddings capture polysemy information naturally through multiplicative compositionality. We demonstrate this property qualitatively and provide proper motivation for it, leaving automated utilization to future work.

In our tensor-based embeddings, we found that one can create a vector that represents a word w in the context of another word w by taking the elementwise product v w * v w . We call v w * v w a "meaning vector" for the polysemous word w.

For example, consider the word star, which can denote a lead performer or a celestial body. We can create a vector for star in the "lead performer" sense by taking the elementwise product v star * v actor . This produces a vector that lies near vectors for words related to lead performers and far from those related to star's other senses. To motivate why this works, recall that the values in a third order PPMI tensor M are given by:

m ijk = P P M I(w i , w j , w k ) ≈ R r=1 v ir v jr v kr = v i * v j , v k ,

where v i is the word vector for w i . If words w i , w j , w k have a high PPMI, then v i * v j , v k will also be high, meaning v i * v j will be close to v k in the vector space by cosine similarity.

For example, even though galaxy is likely to appear in the context of the word star in in the "celestial body" sense, v star * v actor , v galaxy ≈ PPMI(star, actor, galaxy) is low whereas v star * v actor , v drama ≈ PPMI(star, actor, drama) is high. Thus , v star * v actor represents the meaning of star in the "lead performer" sense.

In Table 5 we present the nearest neighbors of multiplicative and additive composed vectors for a variety of polysemous words. As we can see, the words corresponding to the nearest neighbors of the composed vectors for our tensor methods are semantically related to the intended sense both for multiplicative and additive composition. In contrast, for CBOW, only additive composition yields vectors whose nearest neighbors are semantically related to the intended sense. Thus, our embeddings can produce complementary sets of polysemous word representations that are qualitatively valid whereas CBOW (seemingly) only guarantees meaningful additive compositionality.

While we leave automated usage and measuring of this property to future work, it is interesting to see that this property is empirically validated in our embeddings and not the existing baselines after motivating its existence from a tensor factorization point of view.

CONCLUSION:

Our key contributions are as follows:

1. Two novel tensor factorization based word embeddings. We presented CP-S and JCP-S, which are word embedding techniques based on symmetric CP decomposition. We experimentally demonstrated that these embeddings outperform existing state-of-the-art matrix-based techniques on a number of downstream tasks when trained on the same data. 2. A novel joint symmetric tensor factorization problem. We introduced and utilized Joint Symmetric Rank-R CP Decomposition to train JCP-S. In this problem, multiple supersymmetric tensors must be decomposed using a single rank-R factor matrix. This technique allows for utilization of both second and third order co-occurrence information in word embedding training.

3.:

A new embedding evaluation metric to measure amount of third order information. We produce a 3-way analogue of Outlier Detection (Camacho-Collados & Navigli ( 2016)) that we call OD3. This metric evaluates the degree to which third order information is captured by a given word embedding. We demonstrated this by showing our tensor based techniques, which naturally encode third information, perform considerably better at OD3 compared to existing second order models.

4. Word vector multiplicative compositionality for polysemous word representation. We showed that our word vectors can be meaningfully composed multiplicatively to create a "meaning vector" for each different sense of a polysemous word. This property is a consequence of the higher order information used to train our embeddings, and was empirically shown to be unique to our tensor-based embeddings.

Tensor factorization appears to be a highly applicable and effective tool for learning word embeddings, with many areas of potential future work. Leveraging higher order data in training word embeddings is useful for encoding new types of information and semantic relationships compared to models that are trained using only pairwise data. This indicates that such techniques are useful for training word embeddings to be used in downstream NLP tasks.

:

See also -https://www.stat.uchicago.edu/ lekheng/work/msri-lect2.pdf -slide 31

In this work we are don't consider Orthogonal-ALS, proposed inSharan & Valiant (2017), and leave its extensive evaluation for future work.

The input to NNSE is an m × n matrix, where there are m words and n co-occurrence patterns. In our experiments, we set m = n = |V | and set the co-occurrence information to be the number of times wi appears within a window of 5 words of wj. As stated in the paper, the matrix entries are weighted by PPMI.

Figures and Tables:

2. Skip-gram with Negative Sampling (SGNS -Mikolov et al. (2013)), for comparison against the most visible and commonly used embedding method and for comparison against a technique related to PPMI matrix factorization (Levy & Goldberg (2014)) 3. Continuous BOW with Negative Sampling (CBOW -Mikolov et al. (2013)), for the same reasons as SGNS 4. Nonnegative Sparse Embedding 3 (NNSE -Murphy et al. (2012)), for comparison against a technique that also directly uses explicit PPMI matrix factorization 5. Global Vectors (GloVe -Pennington et al. (2014)), for comparison against another very commonly used state-of-the art embedding method as well as another matrix factorization-based embedding

Figure 1: Word classification task performance vs. % training data

. . , w |V | }, one can construct a |V | × |V | PPMI matrix M where m ij = P P M I(w i , w j ).

Table content: <table><tr><td>Many existing word embedding techniques involve factorizing this</td></tr><tr><td>PPMI matrix: Levy &amp; Goldberg (2014); Murphy et al. (2012); Salle et al. (2016).</td></tr></table>

Best tensor factorization hyperparameter values found

Table content: <table><tr><td>(Hyperparam)</td><td colspan="2">Tensor value shift Negative sample percent</td></tr><tr><td>CP-S</td><td>-3.9</td><td>0.25</td></tr><tr><td>JCP-S (second order)</td><td>0</td><td>0.15</td></tr><tr><td>JCP-S (third order)</td><td>-3.9</td><td>0.15</td></tr><tr><td colspan="3">slower than the training of order-2 equivalents such as SGNS. Explicitly, our GPU trained CBOW</td></tr><tr><td colspan="3">vectors (using the experimental settings found below) in 3568 seconds, whereas training CP-S and</td></tr><tr><td colspan="2">JCP-S took 6786 and 8686 seconds respectively.</td><td/></tr><tr><td colspan="3">Also, we are aware of the well-posedness of the nonnegative CP decomposition (Lim &amp; Comon</td></tr><tr><td>(2009b); Qi et al. (</td><td/><td/></tr></table>

Outlier Detection scores across all embeddingsOutlier Detection results. The results are shown in Table2. As we can see, the tensor factorization based methods outperform the other non-tensor based baselines for all the formulations of this task.

Table content: <table><tr><td colspan="5">(Method) OD2 OPP OD2 acc OD3 OPP OD3 acc</td></tr><tr><td>Random</td><td>0.5828</td><td>0.2504</td><td>0.5076</td><td>0.1823</td></tr><tr><td>SGNS</td><td>0.6219</td><td>0.3483</td><td>0.6109</td><td>0.32</td></tr><tr><td>CBOW</td><td>0.6012</td><td>0.3178</td><td>0.6014</td><td>0.3014</td></tr><tr><td>NNSE</td><td>0.6603</td><td>0.3467</td><td>0.5486</td><td>0.2214</td></tr><tr><td>GloVe</td><td>0.6550</td><td>0.3500</td><td>0.5990</td><td>0.2456</td></tr><tr><td>CP-S</td><td>0.6671</td><td>0.3628</td><td>0.6738</td><td>0.3358</td></tr><tr><td>JCP-S</td><td>0.7069</td><td>0.4181</td><td>0.6606</td><td>0.3247</td></tr></table>

Supervised sentiment analysis scores across all embeddings The results are shown in Table

Table content: <table><tr><td colspan="5">(Method) 10% training data 30% training data 50% training data 100% training data</td></tr><tr><td>Random</td><td>0.6999</td><td>0.7254</td><td>0.7311</td><td>0.7337</td></tr><tr><td>SGNS</td><td>0.7348</td><td>0.7590</td><td>0.7643</td><td>0.7696</td></tr><tr><td>CBOW</td><td>0.7322</td><td>0.7537</td><td>0.7591</td><td>0.7644</td></tr><tr><td>NNSE</td><td>0.7233</td><td>0.7476</td><td>0.7531</td><td>0.7572</td></tr><tr><td>GloVe</td><td>0.7310</td><td>0.7564</td><td>0.7622</td><td>0.7670</td></tr><tr><td>CP-S</td><td>0.7214</td><td>0.7454</td><td>0.7514</td><td>0.7575</td></tr><tr><td>JCP-S</td><td>0.7460</td><td>0.7681</td><td>0.7732</td><td>0.7774</td></tr><tr><td colspan="2">Sentiment analysis results.</td><td/><td/><td/></tr></table>

Word Similarity Scores (Spearman's ρ)

Table content: <table><tr><td>(Method)</td><td>MEN</td><td>MTurk</td><td>RW</td><td>SimLex999</td></tr><tr><td colspan="4">Random 0.04147 -0.0382 -0.0117</td><td>0.0053</td></tr><tr><td>SGNS</td><td>0.5909</td><td>0.5342</td><td>0.3704</td><td>0.2264</td></tr><tr><td>CBOW</td><td>0.5537</td><td>0.4225</td><td>0.3444</td><td>0.2727</td></tr><tr><td>NNSE</td><td>0.5055</td><td>0.5068</td><td>0.1993</td><td>0.1263</td></tr><tr><td>GloVe</td><td>0.4914</td><td>0.4733</td><td>0.1750</td><td>0.1403</td></tr><tr><td>CP-S</td><td>0.4723</td><td>0.4738</td><td>0.0875</td><td>0.0399</td></tr><tr><td>JCP-S</td><td>0.6158</td><td>0.5343</td><td>0.3546</td><td>0.2272</td></tr></table>

Nearest neighbors (in cosine similarity) to elementwise products of word vectors

Table content: <table><tr><td>Composition</td><td>Nearest neighbors (CP-S)</td><td>Nearest neighbors (JCP-S)</td><td>Nearest neighbors (CBOW)</td></tr><tr><td>star  *  actor</td><td>oscar, award-winning, supporting</td><td>roles, drama, musical</td><td>DNA, younger, tip</td></tr><tr><td>star + actor</td><td>stars, movie, actress</td><td>actress, trek, picture</td><td>actress, comedian, starred</td></tr><tr><td>star  *  planet</td><td>planets, constellation, trek</td><td>galaxy, earth, minor</td><td>fingers, layer, arm</td></tr><tr><td>star + planet</td><td>sun, earth, galaxy</td><td>galaxy, dwarf, constellation</td><td>galaxy, planets, earth</td></tr><tr><td>tank  *  fuel</td><td>liquid, injection, tanks</td><td>vehicles, motors, vehicle</td><td>armored, tanks, armoured</td></tr><tr><td>tank + fuel</td><td>tanks, engines, injection</td><td>vehicles, tanks, powered</td><td>tanks, engine, diesel</td></tr><tr><td>tank  *  weapon</td><td>gun, ammunition, tanks</td><td>brigade, cavalry, battalion</td><td>persian, age, rapid</td></tr><tr><td>tank + weapon</td><td>tanks, armor, rifle</td><td>tanks, battery, batteries</td><td>tanks, cannon, armored</td></tr></table>

Peer review (iclr2018):
 The paper presents the word embedding technique which consists of: (a) construction of a positive (i.e. with truncated negative values) pointwise mutual information order-3 tensor for triples of words in a sentence and (b) symmetric tensor CP factorization of this tensor. The authors propose the CP-S (stands for symmetric CP decomposition) approach which tackles such factorization in a "batch" manner by considering small random subsets of the original tensor. They also consider the JCP-S approach, where the ALS (alternating least squares) objective is represented as the joint objective of the matrix and order-3 tensor ALS objectives. The approach is evaluated experimentally on several tasks such as outlier detection, supervised analogy recovery, and sentiment analysis tasks. CLARITY: The paper is very well written and is easy to follow. However, some implementation details are missing, which makes it difficult to assess the quality of the experimental results. QUALITY: I understand that the main emphasis of this work is on developing faster computational algorithms, which would handle large scale problems, for factorizing this tensor. However, I have several concerns about the algorithms proposed in this paper: - First of all, I do not see why using small random subsets of the original tensor would give a desirable factorization. Indeed, a CP decomposition of a tensor can not be reconstructed from CP decompositions of its subtensors. Note that there is a difference between batch methods in stochastic optimization where batches are composed of a subset of observations (which then leads to an approximation of desirable quantities, e.g. the gradient, in expectation) and the current approach where subtensors are considered as batches. I would expect some further elaboration of this question in the paper. Although similar methods appeared in the tensor literature before, I don*t see any theoretical ground for their correctness. - Second, there is a significant difference between the symmetric CP tensor decomposition and the non-negative symmetric CP tensor decomposition. In particular, the latter problem is well posed and has good properties (see, e.g., Lim, Comon. Nonengative approximations of nonnegative tensors (2009)). However, this is not the case for the former (see, e.g., Comon et al., 2008 as cited in this paper). Therefore, (a) computing the symmetric and not non-negative symmetric decomposition does not give any good theoretical guarantees (while achieving such guarantees seems to be one of the motivations of this paper) and (b) although the tensor is non-negative, its symmetric factorization is not guaranteed to be non-negative and further elaboration of this issue seem to be important to me. - Third, the authors claim that one of their goals is an experimental exploration of tensor factorization approaches with provable guarantees applied to the word embedding problem. This is an important question that has not been addressed in the literature and is clearly a pro of the paper. However, it seems to me that this goal is not fully implemented. Indeed, (a) I mentioned in the previous paragraph the issues with the symmetric CP decomposition and (b) although the paper is motivated by the recent algorithm proposed by Sharan&Valiant (2017), the algorithms proposed in this paper are not based on this or other known algorithms with theoretical guarantees. This is therefore confusing and I would be interested in the author*s point of view to this issue. - Further, the proposed joint approach, where the second and third order information are combined requires further analysis. Indeed, in the current formulation the objective is completely dominated by the order-3 tensor factor, because it contributes O(d^3) terms to the objective vs O(d^2) terms contributed by the matrix part. It would be interesting to see further elaboration of the pros and cons of such problem formulation. - Minor comment. In the shifted PMI section, the authors mention the parameter alpha and set specific values of this parameter based on experiments. However, I don*t think that enough information is provided, because, given the author*s approach, the value of this parameter most probably depends on other parameters, such as the bach size. - Finally, although the empirical evaluation is quite extensive and outperforms the state-of the art, I think it would be important to compare the proposed algorithm to other tensor factorization approaches mentioned above. ORIGINALITY: The idea of using a pointwise mutual information tensor for word embeddings is not new, but the authors fairly cite all the relevant literature. My understanding is that the main novelty is the proposed tensor factorization algorithm and extensive experimental evaluation. However, such batch approaches for tensor factorization are not new and I am quite skeptical about their correctness (see above). The experimental evaluation presents indeed interesting results. However, I think it would also be important to compare to other tensor factorization approaches. I would also be quite interested to see the performance of the proposed algorithm for different values of parameters (such as the butch size). SIGNIFICANCE: I think the paper addresses very interesting problem and significant amount of work is done towards the evaluation, but there are some further important questions that should be answered before the paper can be published. To summarize, the following are the pros of the paper: - clarity and good presentation; - good overview of the related literature; - extensive experimental comparison and good experimental results. While the following are the cons: - the mentioned issues with the proposed algorithm, which in particular does not have any theoretical guarantees; - lack of details on how experimental results were obtained, in particular, lack of the details on the values of the free parameters in the proposed algorithm; - lack of comparison to other tensor approaches to the word embedding problem (i.e. other algorithms for the tensor decomposition subproblem); - the novelty of the approach is somewhat limited, although the idea of the extensive experimental comparison is good.