A provable SVD-based algorithm for learning topics in dominant admixture corpus
Topic models, such as Latent Dirichlet Allocation (LDA), posit that documents are drawn from admixtures of distributions over words, known as topics. The inference problem of recovering topics from such a collection of documents drawn from admixtures, is NP-hard. Making a strong assumption called separability, [4] gave the first provable algorithm for inference. For the widely used LDA model, [6] gave a provable algorithm using clever tensor-methods. But [4,6] do not learn topic vectors with bounded l 1 error (a natural measure for probability vectors). Our aim is to develop a model which makes intuitive and empirically supported assumptions and to design an algorithm with natural, simple components such as SVD, which provably solves the inference problem for the model with bounded l 1 error. A topic in LDA and other models is essentially characterized by a group of co-occurring words. Motivated by this, we introduce topic specific Catchwords, a group of words which occur with strictly greater frequency in a topic than any other topic individually and are required to have high frequency together rather than individually. A major contribution of the paper is to show that under this more realistic assumption, which is empirically verified on real corpora, a singular value decomposition (SVD) based algorithm with a crucial pre-processing step of thresholding, can provably recover the topics from a collection of documents drawn from Dominant admixtures. Dominant admixtures are convex combination of distributions in which one distribution has a significantly higher contribution than the others. Apart from the simplicity of the algorithm, the sample complexity has near optimal dependence on w 0 , the lowest probability that a topic is dominant, and is better than [4]. Empirical evidence shows that on several real world corpora, both Catchwords and Dominant admixture assumptions hold and the proposed algorithm substantially outperforms the state of the art [5].
This paper describes an SVD-based method for provably recovering the word-topic distributions for collections of documents taken from "dominant admixtures".  This paper incrementally improves upon [5] by removing the assumption of topic "anchor words" (high probability in one topic and 0 probability in other topics) -- instead, there are weaker assumptions of topic "catchwords" (groups of words that occur strictly more frequently in one topic) and "dominant admixtures".  The assumption behind dominant admixtures is that there is a topic within each document that stands out among other topics.While I did not fully follow the proof of Theorem 3.1, I think the paper advances the line of research that solves LDA using SVD-type techniques.  The clarity of the paper could improve greatly by explaining the implications and important points of the theorems, assumptions, and lemmas.One critique I had was that this paper did seem to be incremental relative to [5] and the authors only performed empirical comparisons versus the Recover algorithm in [5].  Why not show the reconstruction errors and perplexity numbers for Gibbs sampling as well?  Most topic-modelers are more familiar with the traditional approximate inference schemes such as Gibbs sampling and variational inference, and it is important to compare to these well-known algorithms as well so that the community can get a sense of the performance of the proposed algorithm.I also did not fully understand the implications of the topic recovery evaluation.  It seems the original "ground-truth" M comes from LDA Gibbs sampling on the real data.  Isn't it expected a priori that the estimated M_TSVD would be closer to M than M_Recover because M_Recover is more sparse due to the Anchor word assumption?  In other words, if the data-generating distribution M were modified to be highly sparse, perhaps M_Recover would be produce lower reconstruction errors.  Also, the perplexity results on real data are not consistently better than Recover, so what is the evidence that this new approach has better performance?Other comments/questions:1) The generative process of dominant admixtures was not clearly spelled out in the Notation section.2) Please clarify that A_ij is fractional.   Line 085 says that it is a frequency.3) Did you try the approach on a data set where most of the documents did not have a dominant topic?  One way to create such a data set is to just fuse multiple documents (of completely different topics) into a super-document.  How would the approach perform in this regime?4) In Table 2, the NIPS results have lower error than the other data sets. Why not use a mean document length of 1000 for each of these semi-synthetic corpora to see if the performance can be replicated for all of these data set?5) Cited paper [7] also removes the Anchor word assumption, but there was no comparison made between that work and the author's work.