Here we study the problem of learning labels for large text corpora where each document can be assigned a variable number of labels. The problem is trivial when the label dimensionality is small and can be easily solved by a series of one-vs-all classifiers. However, as the label dimensionality increases, the parameter space of such one-vs-all classifiers becomes extremely large and outstrips the memory. Here we propose a latent variable model to reduce the size of the parameter space, but still efficiently learn the labels. We learn the model using spectral learning and show how to extract the parameters using only three passes through the training dataset. Further, we analyse the sample complexity of our model using PAC learning theory and then demonstrate the performance of our algorithm on several benchmark datasets in comparison with existing algorithms.
The paper addresses the problem of multi-label learning for text corpora and proposes to tackle the problem using tensor factorization methods. Some analysis and experimental results for the proposed algorithm are presented.
QUALITY: I find the quality of the results in this paper rather low. The proposed probabilistic model is defined ambiguously. The authors then look at joint probability distributions of co-occurence of two and three words, which gives a matrix and a tensor, respectively. They propose to match these matrix and tensor to their sample estimates and refer to such procedure as the moment matching method, which it is not. They then apply a standard two step technique from the moment matching literature consisting of whitening and orthogonal tensor factorization. However, in their case this does not have much statistical meaning. Indeed, whitening of the covariance matrix is usually justified by the scaling unidentifiability of the problem. In their case, the mathematics works because of the orthogonal unidentifiability of the square root of a matrix. Furthermore, the proposed sample estimators do not actually estimate densities they are dealing with (see, e.g., Eq. (16) and (17)). Their theoretical analysis seems like a straightforward extension of the analysis by Anandkumar, et al. (2012, 2014), however, I find it difficult to assess this analysis due to numerous ambiguities in the problem formulation and method development. This justifies my statement in the beginning of the paragraph.
CLARITY: The paper is not well written and, therefore, is difficult to assess. Many important details are omitted, the formulation of the model is self contradicting, the standard concepts and notations are sometimes abused, some statements are wrong. I provide some examples in the detailed comment below.
ORIGINALITY AND SIGNIFICANCE: The idea to apply tensor factorization approaches to the multi-label learning is novel up to my knowledge and is a pro of the paper. However, I have problems to find other pros in this submission because the clarity is quite low and in the present form there is no novelty in the proposed procedure. Moreover, the authors claim to work with densities, but end up estimating other quantities, which are not guaranteed to have the desirable form. They also emphasize the fact that there is the simplex constraint on the estimated parameters, but this constraint is completely ignored by the algorithm and, in general, won't be satisfied in practice. If think the authors should do some more work before this paper can be published.
DETAILED COMMENTS: Since I am quite critical about the paper, I point out some examples of drawbacks or flaws of this paper:
  - The proposed model (Section 2) is not well defined. In particular, the description in Section 2 is not sufficient to understand the proposed model; the plate diagram in Figure 2 is not consistent with the text. It is not mentioned how at least some conditional distributions behave (e.g., tokens given labels or states). The diagram in Fig. 1 does not help since it isn't consistent with the text (e.g. the elements of labels or states are not conditionally / independent). The model is very close to latent Dirichlet allocation by Blei, et al. (2003), but differences are not discussed.
  - The standard terminology is often abused. For example, the proposed approach is referred to as the method of moments when it is not. In Section 2.1, the authors aim to match joint distributions (not the moments) to their empirical approximations (which are also wrong; see below). The usage of tokes and documents is interchanged without any explanations.
  - The use of the whitening approach is not justified in their setting working with joint distributions of couples and triples and it has no statistical meaning. No explanation is provided. I would definitely not call this whitening.
  - In Section 2.2, the notation is not defined and is different from what is usually used in the literature. For example, Eq. (15) does not make much sense as is. One could guess from the context that they are talking about the eigenvectors of an orthogonal tensor as defined in, e.g. Anandkumar, et al. (2014).
  - In Section 3, the authors emphasize the fact that their parameters are constrained to the probability simplex, but this constraint is not ensured in the proposed algorithm (Alg. 1).
  - Importantly, the estimators of the matrix M_2 and tensor M_3 do not make much sense to me. For example, for estimating M_2 it would be reasonable to average over all word pairs, i.e. something like [M_2]_{ij} = 1/L \sum_{w_k \not = w_l} P(w_k = v_i, w_l = v_j), where L is the number of pairs. This is different from the expression in Eq. (16), which is just a rescaled non-central second moment. Similar issue is true for the order-3 estimator.
  - The factorization procedure does not ensure non-negativity of the obtained parameters and, therefore, the rescaling is not guaranteed to belong to the probability simplex. I could not find any explanations of this issue.
  - I explain good plots in the experimental section, potentially, by the fact that the authors do algorithmically something different from what they aim to do, because the estimators do not estimate the desired entities (i.e. are not consistent). The procedure looks to me quite similar to the procedure for LDA, hence the reasonable results. However, the authors do not justify their proposed method.