A Reduction for Efficient LDA Topic Reconstruction
We present a novel approach for LDA (Latent Dirichlet Allocation) topic reconstruction. The main technical idea is to show that the distribution over the documents generated by LDA can be transformed into a distribution for a much simpler generative model in which documents are generated from the same set of topics but have a much simpler structure: documents are single topic and topics are chosen uniformly at random. Furthermore, this reduction is approximation preserving, in the sense that approximate distributions -the only ones we can hope to compute in practice -are mapped into approximate distribution in the simplified world. This opens up the possibility of efficiently reconstructing LDA topics in a roundabout way. Compute an approximate document distribution from the given corpus, transform it into an approximate distribution for the single-topic world, and run a reconstruction algorithm in the uniform, single-topic world -a much simpler task than direct LDA reconstruction. We show the viability of the approach by giving very simple algorithms for a generalization of two notable cases that have been studied in the literature, p-separability and matrix-like topics.
This submission presents an approach to LDA topic reconstruction using word co-occurences.  Exploiting a relationship between LDA and multinomial mixture models (detailed in a separate, included paper), the authors provide a new algorithm for learning (a broad class) of separable topic models.  These results are tested on separable data and compared to Arora et al (2013)’s anchor words algorithm and a  Gibbs sampler.  I will disclaim that I am comparatively weak on the theoretical background for reviewing this paper.  I come from a background quite familiar with LDA and various approaches to estimation.  It may be worth noting for future readers that the abstract isn’t really clear that the goal here isn’t necessarily a practical algorithm as much as a theoretical contribution.  The quality of the paper seems high, although again I’m not particularly well suited to judge many of the theoretical results.   The paper considers two simulation settings, one that is favorable to the anchor words assumptions and one that is not.  In the favorable setting performance is comparable, but STA is faster.  In the unfavorable setting, STA is both faster and has much stronger performance.  From a practical perspective, what is lacking is any sense of whether this works at all on real data.  The anchor words algorithm actually works in real data and recovers semantically coherent topics.  Does the proposed algorithm work for actual documents (particularly those longer than 2 words)?  Does it scale well in the size of the vocabulary and when that vocabulary has a power-law distribution?  It also seems that much of the results of experiment one turns on the runtime of STA being better, but that turns a lot on the implementation of the algorithms (which one was used for anchor words?).  My reaction here may be due to the practical perspective I’m coming from, but it isn’t clear what the experiments would contribute for someone coming at this from a theory angle.  The paper is remarkably clear.  The authors do a nice job of signaling the work that each lemma and theorem will be doing to support the method.  While the build-up of the approach is clear there seems to be a significant leap to the actual algorithm.  It might help in Algorithm 1 to include references to the section where each step is described.  I think it would be difficult to implement without constantly referring back to parts of the paper, but it isn’t always clear where to go (e.g. I struggled down the source of the threshold in step 2, because it wasn’t clear what what would happen at p >=2 where the empirical fraction would be above 1).  Finally, it would really help if the appendix included further details of the experiment.  For example, (1) timing comparisons to Gibbs sampling are always a bit misleading because there is no clear point of termination, so it can be made to look arbitrarily bad by just running it arbitrarily long, (2) it isn’t clear which recover algorithm is used (Recover-KL, Recover-L2 etc.), (3) what is used for topic reconstruction in Gibbs? Is it a single pass of the Gibbs sampler or an average over draws (which is going to be substantially more accurate), (4) there is a curious line which is “Gibbs needs longer documents in order to work so we use lengths \ell \in {10,100}, and we keep the number of total tokens (and thus documents) fixed.”  How can you keep the number of total tokens and the number of documents fixed (I’m assuming relative to STA/Recover) if the length is different (because total tokens = number of documents * average length).    The work seems quite original to me and represents a substantial move beyond other spectral method of moments recovery algorithms in the literature.  It covers the interesting (p,t)-separable case.  I’d be curious to know how it compares to the generalization of the anchor words method provided in Huang, Fu and sidiropoulos (“Anchor-Free Correlated Topic Modeling; Identifiability and Algorithm”)  The significance of this papers substantially by community.  Amongst the community of applied users of LDA, I suspect it will have little significance at the moment because the algorithm as stated throws away essentially all the data in the documents, it makes extremely strong assumptions (like the symmetric hyper parameter which we know from Wallach et al 2009 is important) and there is no evidence it works on real applications.  It seems to represent a really new and interesting direction for theory but unfortunately I’m less well-suited to judge that.  ====================== Response to Authors Reply: Thanks for the reply- this was really helpful for clarifying the details of the evaluations.  I am sympathetic to the difficulties of doing the Gibbs runtime evaluations and I think being transparent about that in the text will help clarify to others why it is so difficult.