Structure & Discovery / AISTATS 2020

A Short Document Can Borrow Evidence From the Whole Collection

Two algorithms use learned topic relationships to estimate how much of each theme a document contains, especially when the text gives few clues.

Prior-aware Composition Inference for Spectral Topic Models

Moontae Lee, David Bindel, David Mimno

Overview

A short note may contain too few words to tell whether it concerns one topic or several. If the larger collection shows that two themes often occur together, that context can help interpret the note. Moontae studies how to use those relationships after a spectral topic model has already found the topics.

Key Findings

A 36-word review and a question the topics cannot answer

Imagine a hypothetical Yelp review that reads "Great fries, slow service." Which themes does it mix, and in what proportions? The Yelp reviews that Moontae analyzes average just 36.4 words, and a model that knows only the topics has little to go on. Spectral topic models run into this gap directly. They learn from word-pair co-occurrence counts and never look at individual documents again, so they gain speed and provable guarantees but cannot say what any single document contains. The authors set out to fill that gap with two new algorithms.

Topic correlations as a prior with no formula

The spectral setup factors the word co-occurrence matrix CC as

C≈BABT.C \approx B A B^{\mathsf T}.

Here BB holds the topics, with one column per topic giving a distribution over words. AA is a joint-stochastic matrix whose entries give the joint probability of seeing each pair of topics together. If wmw_m is the topic mixture of document mm, the true version of AA is the average of wmwmTw_m w_m^{\mathsf T} over all MM documents. A probabilistic model such as Latent Dirichlet Allocation commits to a parametric prior, for example a Dirichlet. The authors argue that AA plays the same role as a generic prior and needs no parametric family. They describe it through a pair-generation view in which each document holds a rank-one matrix wmwmTw_m w_m^{\mathsf T} (see Figure 2).

Figure 2 shows the matrix view, where a joint-stochastic matrix A specifies topic-pair correlations that act as a shared prior for the whole corpus.
Figure 2 shows the matrix view, where a joint-stochastic matrix A specifies topic-pair correlations that act as a shared prior for the whole corpus.

The only existing method for this job, Thresholded Linear Inverse (TLI) from Arora and colleagues, multiplies a document's word frequencies by an approximate inverse of BB and then thresholds small entries. The authors report that it ignores AA entirely, falls short when topics correlate, needs unintuitive thresholds, and often produces NaN entries because the inversion is numerically unstable.

Dual decomposition splits the work by document

Both new methods solve the same problem, which the paper labels Equation (1):

min⁡w1,…,wM ∑m=1M∥Bwm−h~m∥22subject to wm∈ΔK−1,  1M∑m=1MwmwmT=A.\min_{w_1,\dots,w_M}\ \sum_{m=1}^{M}\lVert B w_m - \tilde h_m\rVert_2^2 \quad \text{subject to } w_m\in\Delta^{K-1},\ \ \frac1M\sum_{m=1}^{M} w_m w_m^{\mathsf T}=A.

Here h~m\tilde h_m is the document's word-frequency vector, and the simplex ΔK−1\Delta^{K-1} simply means the mixture entries are nonnegative and sum to one. The first term asks each mixture to explain its own words. The constraint asks the mixtures to agree with the learned correlations as a group.

Prior-Aware Dual Decomposition (PADD) attaches a matrix of dual variables Λ\Lambda to that constraint. For a fixed Λ\Lambda, each document becomes an independent subproblem that can run in parallel. These subproblems are nonconvex, so the authors split the quadratic into a difference of convex functions and apply Convex-Concave Programming. A master step then updates Λ\Lambda from the gap between AA and the current average outer product, projecting it to symmetric nonnegative matrices. Initialization uses the Bayes-rule topic-given-word estimates.

Building the constraint into the variables

Prior-Aware Manifold Iteration (PAMI) removes the constraint by construction. It writes WT=QRW^{\mathsf T}=QR, where RR is the Cholesky factor of MAMA and QQ has orthonormal columns. Any such WW then satisfies WWT=MAWW^{\mathsf T}=MA automatically. What remains is a Procrustes problem over orthonormal matrices with simplex conditions, solved with a manifold version of the alternating direction method of multipliers. Each round projects every document onto the simplex with a convex least-squares step, run in parallel, and then updates QQ in closed form from one small singular value decomposition. The authors note that PAMI draws a fixed factor out of the correlations and refines only the varying part. That design leans on the correlations harder than PADD does.

Testing against a known answer

Real documents have no true mixtures, so the authors built three kinds of corpus from topics learned on NeurIPS papers, New York Times articles, and Songs playlists. Yelp reviews join the held-out set. The semi-synthetic corpus draws mixtures from a sparse Dirichlet with concentration 5/K5/K and has almost no correlation. The semi-real corpus draws them from a logistic-normal prior learned by a correlated topic model. The fully real corpus uses a 10% held-out slice that never touched training. Collapsed Gibbs sampling, given the true topics, prior, and hyperparameters, serves as the strongest benchmark. The spectral methods see only BB and AA. Metrics include precision, recall, and F1 on each document's prominent topics, mass on non-prominent topics, ℓ1\ell_1 and ℓ∞\ell_\infty error, Hellinger, and cosine distance.

Figure 3 shows the semi-synthetic corpus, where PADD tracks Gibbs across topic counts and PAMI degrades as K grows.
Figure 3 shows the semi-synthetic corpus, where PADD tracks Gibbs across topic counts and PAMI degrades as K grows.

In Figure 3, PADD stays close to Gibbs everywhere. PAMI degrades as the topic count grows because there is little correlation to extract. TLI works only for small KK. The authors report that PADD competes with Gibbs in nearly every setting while PAMI does best on short realistic documents, which matches the abstract and conclusion.

Figure 5 shows held-out real documents, where Gibbs is treated as ground truth, PADD and PAMI split on Songs from 50 topics, and TLI fails.
Figure 5 shows held-out real documents, where Gibbs is treated as ground truth, PADD and PAMI split on Songs from 50 topics, and TLI fails.

On held-out real data (Figure 5), Gibbs stands in for the truth. The two new methods split on Songs from K≥50K\ge 50, which the authors read as a difference in underlying behavior. TLI fails completely, and many of its points are missing because of NaN values even after the authors rectified the co-occurrence matrix with Alternating Projection.

Costs and loose ends

On the largest NYTimes setup at K=50K=50, PADD took 6804.5 seconds and PAMI 7117.9 in Matlab without per-document parallelism. TLI needed 6780.3 seconds with 8 cores, and 8-core Gibbs in Java took 3,420 seconds. The authors designed the comparison to study inference accuracy. These runtimes come from implementations that use different languages and amounts of parallelism. They ran 50 iterations of each method, with τ=0.05\tau=0.05 for PADD and ρ=0.01\rho=0.01 for PAMI.

Two caveats come from the authors. PADD may struggle when both the document count and document lengths are small, since AA can then sit far from the true correlations. On the real data, disagreement between the regularizer measure and a Hellinger-based log-prior measure suggests that a better weighting than the uniform Frobenius norm could improve both methods.

Questions & Answers

Q: Why is learning topics different from assigning them?

A: A topic model estimates which words characterize each topic. Assignment asks how much of each topic a particular document contains. With very few words, several mixtures can explain the document similarly well.

Q: Are the topic relationships a universal prior?

A: They are learned from a collection. They are most likely to be useful when the target documents share its relationships. A new community, domain, or time period can have different patterns.

Q: How do you know the topics of a real document?

A: The definitive mixture is unobserved. In the fully real comparison, the authors use Gibbs sampling as a reference, which measures agreement between inference methods rather than correctness against a hidden label.

Q: Can an analyst apply PADD to one difficult document at a time?

A: PADD estimates document mixtures under a shared corpus constraint. The method decomposes its updates by document, while the shared statistics still couple the solutions. A selective deployment would need to define the collection used for the joint fit and measure how estimates change when that collection changes.

Future Ideas

Apply the prior only to notes that need it

For a collection of short public comments, estimate topic mixtures with and without the corpus prior. Use the disagreement between the estimates and the amount of evidence in each note to identify cases for review. Give analysts the phrases that support each proposed topic.

Compare the policy with applying one prior strength to all notes. Use independently labeled comments, split by length and collection date. Measure topic identification and false assignment of common topic pairs, particularly after a known change in what people discuss.

Test selective routing on batches with a documented prior from their training collection. Compare fixed-batch estimates with periodic joint refits after a topic shift, and report the resulting drift and update cost.

Sources

Original abstract

Spectral algorithms operate on matrices or tensors of word co-occurrence to learn latent topics. These approaches remove the depen- dence on the original documents and produce substantial gains in efficiency with provable inference, but at a cost: the models can no longer infer any information about individ- ual documents. Thresholded Linear Inverse is developed to learn document-specific topic compositions, but its linear characteristics limit the inference quality without considering any prior information on topic distributions. We propose two novel estimation methods that respect previously unclear prior struc- tures of spectral topic models. Experiments on a variety of synthetic to real collections demonstrate that our Prior-Aware Dual De- composition outperforms the baseline method, whereas our Prior-Aware Manifold Iteration performs even better on short realistic data.