Anchor-Free Correlated Topic Modeling: Identifiability and Algorithm
In topic modeling, many algorithms that guarantee identifiability of the topics have been developed under the premise that there exist anchor words -i.e., words that only appear (with positive probability) in one topic. Follow-up work has resorted to three or higher-order statistics of the data corpus to relax the anchor word assumption. Reliable estimates of higher-order statistics are hard to obtain, however, and the identification of topics under those models hinges on uncorrelatedness of the topics, which can be unrealistic. This paper revisits topic modeling based on second-order moments, and proposes an anchor-free topic mining framework. The proposed approach guarantees the identification of the topics under a much milder condition compared to the anchor-word assumption, thereby exhibiting much better robustness in practice. The associated algorithm only involves one eigendecomposition and a few small linear programs. This makes it easy to implement and scale up to very large problem instances. Experiments using the TDT2 and Reuters-21578 corpus demonstrate that the proposed anchor-free approach exhibits very favorable performance (measured using coherence, similarity count, and clustering accuracy metrics) compared to the prior art.
This paper presents a provably correct method for identifying topics in documents that moves beyond the "anchor-free" assumption in existing work.
[update after author response]: the authors' explanation for decreasing accuracy as F increases makes perfect sense.  If it was in the paper that F is set equal to the number of classes, I missed it.  Please consider adding a sentence giving your explanation for the decrease, in any case.  I also appreciate the authors reporting the accuracy of a simple LDA baseline in the author response.  In general the author response addressed my major concerns. [END update after author response]  In general I think this paper is a strong contribution.  I discuss particular strengths and areas for improvement below.  Strengths:  The work gives a technique with novel provable guarantees.  It also provides an experimental evaluation of the approach.  Parts of the paper are brilliantly clear.  Figure 1 is extremely helpful for understanding the new power of the technique.  The math is succinct and clear.  Areas for Improvement:  Lines 209-218 introduce some questions about the novelty of the underlying approach, even if this paper's algorithm itself is novel.  The scalability of the technique is not great.  This is shown in both the empirical results (Fig 2) and also the complexity O(F^3.5).  However, this is not a fatal limitation.  The authors should be aware that F values in the several thousands often provide the best held-out likelihood in practice, for even moderate-sized corpora, especially when topic correlations are modeled.  The experiments could use some enhancements.  First, a vanilla LDA approach using Gibbs sampling is worth including as a simple baseline.  Second, there is a major unanswered question in how clustering accuracy (which in my view is the most important experimental metric, because it reflects best what users want out of a topic model) decreases with the number of topics.  Especially when the number of classes considered (for TDT2 at least) is larger than the number of topics, I do not understand why as F increases, classification accuracy goes from outstanding (0.98 accuracy for F=3, TDT2) to mediocre (0.74 for F=25).  The 0.98 is hard to understand by itself, when each document vector is only length 3 and you are performing a 30-way classification task.  Some explanation is necessary here.  Also, another approach that used the W vectors as feature vectors, and trained a supervised classifier on a small number of labeled documents, might yield more meaningful results.  This experimental detail was the primary reason I did not assign a higher score.  The background section could be reduced considerably in order to provide more space for experiments.  Minor:  The point about how normalization can increase noise should be clarified with an example, or more explanation.  The paper returns to this claim at multiple points in the paper but without reading [8] it is hard for me to understand why normalization amplifies noise.  Is this because documents with few supporting observations will receive equal weight in the model as those with more observations?  The phrase third or higher-order statistics (trigrams) is a little confusing, because the paper is talking about word co-occurrance within the same document, whereas trigrams refer to a more specific notion (three *consecutive* words)  Line 1 in Algorithm 1 says Epsilon = 1^TD^T whereas the text has Diag of that.  "the size of P does not grow with the size of the data if the vocabulary is fixed" -- only true if P is stored in a dense format, but normally wouldn't it be quite sparse?  I didn't understand what it meant for topics to be "uncorrelated" in the previous work, defining this more precisely would help  How many document classes were used from ModApte?  The paper characterizes its algorithm's complexity as F^3.5, but won't some steps, like line 2, depend on the number of non-zero entries of P?  Perhaps this is negligible with current eigen-decomposition code.  Two especially minor comments on first proof in the supplementary material.  It's confusing that you refer to Assumption 1 by two different names ("Assumption 1" and the "anchor-word" assumption).  I also think you should unpack the sentence: "Therefore, for non-negative matrices the equalities in (1.1) hold if and only if A is a permutation matrix."  Saying "because any non-negative square matrix with orthonormal columns must be a permutation matrix" instead of "therefore" might help.