Structure & Discovery / NeurIPS 2015

Repair the Word Counts Before Reading the Topics

A spectral method adjusts noisy word-pair statistics before using them to estimate topics and how often those topics appear together.

Robust Spectral Inference for Joint Stochastic Matrix Factorization

Moontae Lee, David Bindel, David Mimno

Overview

A topic model can find words about control systems and words about neural circuits. It can also ask whether those topics tend to occur together. That second answer should behave like a probability. Earlier spectral methods could infer negative entries from real corpora. Moontae traces the problem to a mismatch between empirical word counts and the mathematical structure their inference algorithms expect.

Key Findings

Five topics, and four of them say "neuron layer hidden"

Picture a topic model asked for just five topics on the NIPS conference papers. The earlier Anchor Word method of Arora and colleagues keeps returning words such as neuron, layer, hidden, and signal across its lists. Moontae starts from this failure. Spectral inference promises speed, determinism, and provable guarantees, yet on real documents it often yields unusable output and leans on ad-hoc fixes. Their paper reframes the task and explains why the failure happens.

One framework for topics, pixels, and playlists

The authors call the general problem Joint Stochastic Matrix Factorization. A matrix CC holds the joint probability that two objects appear together, such as two words in a document. The goal is to approximate it as

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

Here BB gives the probability of each object within each of KK latent clusters, and AA gives the joint probability of pairs of clusters. CC and AA are joint-stochastic, meaning they behave like joint distributions. BB is column-stochastic, meaning each column sums to one. Table 1 of the paper lists the same structure for documents, images, networks, legislatures, and playlists. Topics are the special case where objects are words.

The model draws a pair of latent clusters from A, then draws each observed object from its cluster's column of B.
The model draws a pair of latent clusters from A, then draws each observed object from its cluster's column of B.

Identifiability comes from the separability assumption. Each cluster has a basis object, called an anchor word for text, that has positive probability only in that cluster. Under this assumption the factorization is unique up to reordering the clusters.

What the true matrix must look like

The authors then ask what the ideal co-occurrence matrix C∗C^* looks like. It equals BAM∗BTB A^*_M B^\mathsf{T}, where AM∗A^*_M averages WmWmTW_m W_m^\mathsf{T} over MM documents and WmW_m is document mm's topic distribution. For any vector yy, the quantity yTAM∗yy^\mathsf{T} A^*_M y is an average of squared terms and cannot be negative. So AM∗A^*_M is positive semidefinite and also entrywise nonnegative, which the authors call doubly nonnegative. The same holds for C∗C^*, which is also low-rank.

Empirical matrices built from limited data are generally full-rank and indefinite, with many negative eigenvalues. The paper argues that the earlier Anchor Word algorithms ignored this mismatch. The observed matrix for document mm uses Equation 5:

Cm=HmHmT−diag⁡(Hm)nm(nm−1).C_m = \frac{H_m H_m^\mathsf{T} - \operatorname{diag}(H_m)}{n_m(n_m-1)} .

HmH_m counts the objects in document mm, and nmn_m is its length. Subtracting the diagonal count removes each object's pairing with itself. This estimator is unbiased under the paper's sampling model, yet any single sample can still stray far from the ideal structure.

Rectifying the matrix before choosing anchors

The proposed fix projects CC toward the ideal set before inference. The paper's preferred method, Alternating Projection, cycles through three adjustments in the style of Dykstra's algorithm. One keeps only the KK largest positive eigenvalues, which forces positive semidefiniteness and rank KK. One shifts all entries equally so they sum to one. One clips negatives to zero. The authors also describe a lighter method, Diagonal Completion, which changes only the diagonal and appears in their appendix.

The rest of the pipeline follows. A new pivoted QR routine exploits sparsity, replacing random projections and keeping inference deterministic. Probabilities for each object come from simplex-constrained quadratic programs solved with exponentiated gradient. The topic-topic matrix comes from a simple formula using the anchor submatrix CSSC_{SS} and the diagonal matrix DD of anchor rows of BB:

A=D−1CSSD−1.A = D^{-1} C_{SS} D^{-1}.

Dividing by a diagonal matrix cannot create negative entries, and submatrices of positive semidefinite matrices stay positive semidefinite. The recovered AA therefore stays doubly nonnegative. The authors note that essentially this recovery appeared in earlier work but could not yield a valid topic-topic matrix without rectification.

Two-dimensional views of the NIPS vocabulary with anchor words in red. The left panel shows the poor hull from the original method, while the middle and right panels show anchors chosen after rectification covering the space better.
Two-dimensional views of the NIPS vocabulary with anchor words in red. The left panel shows the poor hull from the original method, while the middle and right panels show anchors chosen after rectification covering the space better.

What the topics and interactions look like

The experiment spans the two document corpora and two collections of item selections in Table 2.

DatasetTraining examplesVocabularyMean example length
NIPS1,3485,000380.5
NYTimes269,32515,000204.9
Movies63,04110,000142.8
Songs14,65310,000119.2

In Table 3, on NIPS with K=5K = 5, the baseline repeats frequent words across topics, as the opening scene showed. Alternating Projection separates a neural topic (neuron, circuit, cell, synaptic) from a control topic (control, action, dynamic, optimal, policy). The authors report that its topics resemble those from Gibbs sampling in Mallet. On Movies with K=15K = 15, they report a cluster of Disney animation mostly from the 1990s and a cluster of fantasy films led by Lord of the Rings, while the baseline repeats Pulp Fiction and Silence of the Lambs 15 times.

Figure 3 tests the topic-topic matrix directly. The earlier method produces large negative entries. A probabilistic reconstruction removes negatives but lacks off-diagonal structure and does not sum to one. The rectified version gives a valid joint-stochastic matrix.

Topic-topic matrices from three approaches. The first panel has negative entries, the second has no off-diagonals, and the third is a valid joint-stochastic matrix.
Topic-topic matrices from three approaches. The first panel has negative entries, the second has no off-diagonals, and the third is a valid joint-stochastic matrix.

Measuring across topic counts

Figure 4 compares the baseline, Diagonal Completion, Alternating Projection, and Gibbs sampling on six measures across all four corpora. These cover recovery error, approximation error, diagonal dominancy, specificity, inter-topic dissimilarity, and coherence. The authors report that Alternating Projection reduces recovery error in almost all cases and beats Diagonal Completion. Its specificity, dissimilarity, and coherence track Gibbs sampling, while the baseline and Diagonal Completion repeat the corpus distribution. All metrics use the original CC, though BB and AA come from the rectified matrix.

Caveats appear in the paper itself. Held-out probability is left out because relative results depend on smoothing parameters. A high coherence score can coexist with repetitive topics, since the metric rewards terms that appear together. On semi-synthetic data, differences between methods are smaller, and the authors speculate that such data is more well-behaved than real text, which may explain why the problem went unnoticed.

Results on real datasets across topic counts for six metrics. Compare the Alternating Projection and Gibbs curves against the Baseline in each panel.
Results on real datasets across topic counts for six metrics. Compare the Alternating Projection and Gibbs curves against the Baseline in each panel.

Why rectification helps and where the proof stops

Rare words often become anchors under pivoted QR, because their sparse, noisy rows stand out. That makes the anchor submatrix highly diagonally dominant and uninformative about topic correlation. The authors argue the low-rank projection suppresses noisy rare-word rows and the positive semidefinite projection restores missing diagonal information. In Songs, the baseline's dominancy becomes undefined beyond K=10K = 10 when a chosen song occurs at most once per playlist, while Alternating Projection stays valid.

On convergence, they invoke local linear convergence results of Lewis, Luke, and Malick. Two conditions are argued, one through prox-regularity of the rank-constrained set. The third, strong regularity, is expected from noise and not verified a priori. Empirically, the ratio of average distances between iterations stayed at or below 0.9794 on NYTimes. The authors also note that the original guarantees should hold better for the rectified matrix. They leave open how anchors in the rectified space form better bases, and whether recursive application to AA could learn super-topics.

Questions & Answers

Q: Why care whether a matrix entry is negative?

A: A negative topic-pair probability has no direct probabilistic interpretation. It signals that the recovered factors may not describe the joint process the model assumes.

Q: Why repair the input before recovering the topic matrix?

A: The input statistics help determine the anchors and later factors. Adjusting only the final topic matrix leaves any unreliable anchor choices in place. Rectifying the input can affect both stages.

Q: Would every use of this factorization require text?

A: The framework treats word pairs as one example of observed pairs. The same representation can describe other objects with recorded co-occurrences, subject to the model assumptions and the quality of the measurements.

Q: Does a valid topic matrix establish that each relationship is real?

A: Rectification makes the matrix obey the structural requirements of the model, and the proof describes local convergence under its assumptions. In finite data, a structural correction can also change empirical counts. For a particular relationship, look for support in held-out word pairs and persistence when documents or vocabulary choices change.

Future Ideas

Track which topic associations survive new samples

Build a topic monitor for an archive of public records. Fit the rectified model on consecutive time periods and resample documents within each period. Display a topic link only when its relative strength and rank among a topic’s partners are stable across resamples and supported by held-out co-occurrences.

Compare the monitor with the original spectral method and a probabilistic topic model at similar runtime. Measure held-out pair prediction, stability of topic words, and the number of links curators can substantiate by reading documents. Use known topic shifts and deliberate vocabulary perturbations to see which links persist for the wrong reason.

Sources

Original abstract

Spectral inference provides fast algorithms and provable optimality for latent topic analysis. But for real data these algorithms require additional ad-hoc heuristics, and even then often produce unusable results. We explain this poor performance by casting the problem of topic inference in the framework of Joint Stochastic Matrix Factorization (JSMF) and showing that previous methods violate the theoretical conditions necessary for a good solution to exist. We then propose a novel rectification method that learns high quality topics and their interactions even on small, noisy data. This method achieves results comparable to probabilistic techniques in several domains while maintaining scalability and provable optimality.