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