Hierarchical Methods of Moments

Matteo Ruffini, Guillaume Rabusseau, Borja Balle

Introduction

Spectral "Method of Moments" (MoM) algorithms offer a theoretically faster alternative to the standard Expectation-Maximization (EM) approach for learning latent variable models. However, they often break down when the model is "misspecified"—for instance, when the user guesses the wrong number of underlying topics. This paper introduces SIDIWO (Simultaneous Diagonalization based on Whitening and Optimization), a robust optimization-based decomposition method that allows researchers to apply MoM hierarchically. By recursively splitting data into two "pseudo-clusters," SIDIWO achieves state-of-the-art speed and accuracy in topic modeling, even when the true number of latent states is unknown.

The Challenge of Model Misspecification

In machine learning, identifying hidden structures in massive datasets—like uncovering latent "topics" in a collection of documents—is a fundamental task. For decades, the Expectation-Maximization (EM) algorithm has been the gold standard. Yet, EM is computationally heavy and prone to getting stuck in local optima.

Method of Moments (MoM) emerged as a faster, mathematically grounded alternative. Instead of iteratively passing over the data, MoM analyzes the statistics of word co-occurrences (moments) and uses tensor decomposition to uncover topics. The catch is that MoM is notoriously brittle. If an algorithm is tasked with finding 5 topics in a dataset that actually contains 50, it often yields nonsensical results. This lack of robustness to model misspecification has historically prevented MoM from replacing EM in practical, exploratory data analysis.

SIDIWO and the Hierarchical Approach

To overcome these limitations, the authors propose SIDIWO, which reframes the tensor decomposition step as a non-convex optimization task. Instead of traditional tensor power methods, SIDIWO seeks a matrix that "nearly diagonalizes" the slices of the third-order moment tensor.

Crucially, the authors prove that when SIDIWO is asked to find fewer topics ($l$) than actually exist ($k$), it does not simply fail. Instead, it identifies "pseudo-centers"—linear combinations of the true topics that represent broad, meaningful clusters.

Leveraging this robustness, the authors build a divisive binary tree. By setting $l=2$, the algorithm splits the dataset into two groups based on the discovered pseudo-centers, and then recursively applies the same process to each subset until a full hierarchy is formed. While the general optimization is non-convex, the specific case of splitting into two ($l=2$) reduces to a one-dimensional search that can be solved optimally and rapidly via a simple grid search.

Key Results

The authors evaluated SIDIWO on synthetic data, a dataset of NIPS conference papers (1987–2015), and Wikipedia Mathematics pages.

Superior Accuracy and Speed

On synthetic data featuring 8 topics and a 100-word vocabulary, SIDIWO significantly outperformed standard Tensor Power Methods (TPM) and Alternating Least Squares (ALS).

Performance comparison of clustering methods

As shown above, SIDIWO achieved an Adjusted Rand Index (ARI) of 0.98, proving highly accurate. Furthermore, it was the fastest method tested, running in just 0.4 seconds compared to 1.9 seconds for ALS and 16 minutes for a Random Projections-based method.

Meaningful Hierarchies

Beyond raw speed and accuracy, SIDIWO excels at qualitative, exploratory analysis. On the NIPS dataset, the algorithm automatically generated a logical, interpretable tree of topics.

Hierarchical topic tree generated from NIPS papers

For example, the algorithm successfully split general machine learning concepts from neuroscience, and then further subdivided the neuroscience cluster into distinct "Neural Networks" and "Activity/Circuitry" sub-topics. This hierarchical approach inherently reduces noise, as each subsequent split focuses on a smaller, more coherent subset of the data.

Limitations and Future Work

While the $l=2$ case is easily solved, the general SIDIWO optimization remains non-convex, meaning larger splits might require more sophisticated initialization. Additionally, the current work assumes the number of topics is less than the vocabulary size. Future work could extend this to "overcomplete" models where hidden topics outnumber unique words. Finally, the authors propose applying this hierarchical MoM to healthcare analytics, such as clustering patients based on electronic health records to discover disease subtypes.

Summary updated

Abstract

Spectral methods of moments provide a powerful tool for learning the parameters of latent variable models. Despite their theoretical appeal, the applicability of these methods to real data is still limited due to a lack of robustness to model misspecification. In this paper we present a hierarchical approach to methods of moments to circumvent such limitations. Our method is based on replacing the tensor decomposition step used in previous algorithms with approximate joint diagonalization. Experiments on topic modeling show that our method outperforms previous tensor decomposition methods in terms of speed and model quality.
BibTeX
@inproceedings{ruffini2017hierarchical,
  author = {Matteo Ruffini and Guillaume Rabusseau and Borja Balle},
  title = {{Hierarchical Methods of Moments}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=r1ZIUPbubr},
}

Loading related content...

Figure